蚁群算法在水资源最优分配上的应用

原文信息

题目：Improved Ant Colony Optimization for Optimal Crop and Irrigation Water Allocation by Incorporating Domain Knowledge

作者：D. C. H. Nguyen; G. C. Dandy, Ph.D., M.ASCE; H. R. Maier, Ph.D.; and J. C. Ascough II, Ph.D.

第一作者单位：School of Civil, Environmental and Mining Engineering, Univ. of Adelaide, Adelaide, Australia

期刊：Journal of Water Resources Planning and Management

发表时间：2016.09

关键词：Irrigation; Ant colony optimization; Domain knowledge; Crop allocation;Water allocation; Heuristics; Computational efficiency

文章简介

蚁群算法是用来寻找最短路径的概率型算法，它模拟蚂蚁在搜寻食物时沿途释放信息素的过程，路径上信息素的浓度反比于通过该路径的时间。蚁群对信息素具有感知能力，类似于正反馈机制，借助于此，整个蚁群可以快速找到通向食物的最优路径。自上世纪末提出以来，蚁群算法就因其较高的计算效率而得到关注，它适合于解决具有较大搜索空间并且要求较高计算效率的问题，一个重要的运用就是优化水资源的分配。该问题通常是利用遗传算法求解，但遗传算法不能充分利用在优化过程中积累下的对搜索空间的知识。而蚁群算法可以有效地结合对空间的认识，不断缩小搜索空间的大小，最终收敛到全局最优或近似最优的解。

在蚁群算法中，决策空间是以包含节点（决策变量）和边（变量的取值）的图的形式呈现。水资源的一种分配方案即为图中一系列边组成的路径。全局更优的分配路径上会留存更多的信息素，从而在之后的迭代中更易被选中。随着迭代次数的增加，算法可以逐渐收敛于更好的分配方案。本文以水资源在作物灌溉上的分配进一步说明了模型的运用方法，问题的决策树如下图所示（Nic为季节i时的作物数，Wk为给某种作物的供水量，Nw为供水方案总数）：

图1.作物和水资源分配的决策树

在每个决策点需要确定的选择包括在某块土地上季节i种植何种作物（Ci，j）以及需要分配多少水量给该作物（Wk）。若某种作物种植时间为1年，则后续季节不再进行决策。问题的约束条件包括可用的土地面积以及可资利用的水资源量。在每一节点，蚂蚁选择某一条边（A点到B点）的概率由下式决定：

式中，t表示迭代的次数，τAB表示此时该路径上的信息素浓度，ηAB代表蚂蚁对该条路径的能见度，反映对决策空间的认识。NA为以A点为起点的边的数目，α和β分别表征信息素和能见度的重要程度。其中，信息素的计算公式如下：

可以看出，第t+1次搜索时，路径AB上信息素的浓度的一部分继承自上一次迭代（ρ为滞留系数），另一部分增量是用于鼓励每一次迭代的最优解和全局最优解，同时算法还规定了信息素浓度的上下限，以避免陷入搜索的停滞。而能见度概念的引入是为了保证选择经济效益最高的作物和最大的水资源分配方案。所以能见度实际上是决策点处对作物收益或者水资源分配方案最大预期的度量。蚁群在信息素和能见度的指导下，不断积累对搜索空间的知识，在满足迭代终止条件后（通常是达到一定的迭代次数），可认为获得近似全局最优解。

在案例研究中，作者关注了能见度概念对结果的影响。文章计算了有无能见度指导下，30次试验（每次搜索的起点都是随机的）的目标平均值（Objective Function OF）。结果如下表所示：

图2. 两种算法目标平均值的比较

上表呈现了引入能见度（ACO-SDVO-VF）与否的结果，原假设是利用了能见度的算法其目标函数平均值不显著好于不利用能见度的算法。表中的数值代表在100%水资源供应量下，两种算法的目标（收益）平均值和相同最佳值的偏差。可以看出引入能见度可以明显提升解的质量和收敛速度。在不同水资源供应量下，仍有类似结论。

编者点评

本文利用蚁群算法来解决水资源分配的优化问题，该方法也可以推广到给水管网和雨水管网的设计优化上。与常用的遗传算法相比，蚁群算法的优点在于它可以充分利用历次搜索积累的知识来逼近最优解，尤其是当搜索空间较大时，蚁群算法可以极大地提升计算效率，而这一点却是遗传算法很难实现的。本文还引入了能见度的概念，案例研究表明能见度可以提高算法的收敛速度和解的质量。本文针对的虽然是单目标优化问题，但是该算法经过适当改造后，可用于求解多目标优化问题。但是目前针对蚁群算法在复杂高维多目标优化问题上的研究仍不多，算法还有待进一步完善。