基于改进蚁群算法的供水管网优化计算

王广宇，解建仓，张建龙

(1 西安理工大学 教育部西北水资源与环境生态重点实验室，陕西 西安 710048；2 山西省水利建设开发中心，山西 太原 030002)

供水管网是一个工程造价很高、组成十分复杂的系统，对其进行科学的优化设计是降低工程造价和保证供水安全的重要途径。供水管网规划是供水系统中的重要一环，随着水资源日益紧缺和水资源开发利用率的提高，供水管网改扩建等工程所需的投入逐渐增大。因此，供水管网的规划和设计是否科学、实用，直接影响工程的投资、运行管理费用及系统的可靠性，这就对供水管线路径的合理规划设计研究提出了更高的要求。自前苏联学者罗巴乔夫、莫什宁等首次将经济观点引入到供水管网设计领域以来，供水管网技术经济计算已得到迅速的发展[1]。常用的优化方法包括空间分析法、线性规划法、动态规划法、枚举法、最优控制法、广义简约梯度法[2-4]等，相继被引入供水管网的优化领域。但是包含遗传算法、模拟退火算法、神经网络算法在内的许多新方法目前仍然是以理论研究为主，工程应用还比较少见。由于实际的优化问题常常表现出高维、多峰值、非线性、不连续、非凸性及带噪声等复杂特性，本研究重点从工程应用角度对管网建模和优化算法进行研究，以Dorigo等[5-6]提出的蚁群优化算法(ACO algorithm)为基础，分析该方法应用于求解组合优化[7]、电路布线[8]、数据挖掘[9]、沉降预测[10]等问题时存在的不足，并结合蚁群算法的最新研究进展[11-14]，针对管道供水路径优化问题的特点，提出一种基于改进蚁群算法的供水管网优化计算方法，以期为供水路径的优化提供支持。

1 管网供水问题及数学模型的建立

1.1 管网供水问题

水利工程长距离输水有多种方式，如埋地管道输水、明渠输水、箱涵输水等。相比较而言,埋地管道输水具有供水保证率高、损失水量少、运行管理方便、维护工作量小以及防污染性强等优点，尤其是在输水线路沿线冲沟较多的情况下可考虑采用此方式。在管道供水时，应充分利用蓄水工程的水头，采用有压重力流输水，以节省能耗、降低工程运行成本。输水管线布置应尽量取直，以减少水头损失及控制工程的规模，降低工程造价。尽量靠近现有道路或规划道路布设，以方便施工和运行维护管理，并尽量避开不良土质地带。

管网规划与布置是管道系统规划中的关键部分，管网布设的合理与否，对工程投资、运行状况和管理维护有很大影响。因此对管网规划与布设方案的确定，应通过多种方案进行反复计算和比较，以达到经济合理的目的，减少工程投资并确保系统运行可靠。管网设计时应按照管网总长度最短、投资最小的原则，确定管网中各级管道的走向和长度，得到管道总长度最小的树状管网。在供水中各需水区也都有自己的优势和劣势，在一个完整的供水过程中选择哪一条线路取决于很多复杂的因素，如成本、时间、地质地貌等。因此，如何在最短的路径上、以最低成本完成各需水区的供水管道布设，即供水水源与需水区之间的供水管道路径优化，是顺利实现供水的关键。

1.2 数学模型的建立

1.2.1 基本假设 ① 不考虑管道材质和供水过程中的输水损失；② 不考虑人为因素对输水管道的影响；③ 每个需供水点对水资源需求的紧迫程度相同。

1.2.2 数学模型 在对需水地区管道供水的路径进行选择时，主要目标是要求供水所需的总成本(包括输水所需管线长度、需水区之间的距离以及其他所需费用等)最低。设水源中心规划铺设供水管道m条，需要对n个需水区配备水资源，需水区的需水量为qi(0

(1)

输水管道k对需水区i承担的输水任务由下式表示：

(2)

根据规划的总成本最低目标，则该问题的数学模型如下。

(1)目标函数。目标函数可表示为：

(3)

式中：Z表示总成本(亿元)，dij为需水区i到j之间的路径长度(km)。

(2)约束条件。① 输水管道设计流量约束可表示为：

(4)

② 每个需水区的需求只有1条输水管道满足，所有的输水任务则由m条管道协同完成：

(5)

③ 要求到达某一需水区的输水管道有且只有1条，其约束的条件为：

(6)

(7)

2 改进蚁群算法的设计

尽管蚁群算法具有较强的鲁棒性、简单性、自调节性、易进行分布式计算、可与其他方法兼容等特点，但尚存在一些缺陷：(1)算法较复杂，需要较长的搜索时间；(2)搜索进行到一定程度后，容易出现停滞现象，不能对解空间进一步搜索，不利于发现全局最优解。通过对基本蚁群算法模型的研究，可以依据以下2个方面对算法进行改进：(1)选择策略。信息素浓度与路径被选择的概率成正比。(2)更新策略。路径上的信息素浓度与蚂蚁的经过量成正比，与经过的时间成反比。

2.1 路径选择策略

在算法的初始时刻，当将m只蚂蚁随机地放到n个需水区时，对于大规模的路径选择问题，蚂蚁在选择下一需水区时要考虑所有可能的需水区集合，需要很长的搜索时间，搜索效率比较低。因此，为减少搜索时间，可将蚂蚁要选择的需水区数量限制在一个子集范围内，这些子集是距离蚂蚁所在地较近的需水区。路径选择的改进主要包括以下几个方面。

(8)

3)启发信息的归一化。由于蚂蚁转移的概率受启发信息影响很大，当参数的初始值选择不合适，或者启发信息中的一项过早地起决定性作用，导致收敛过快而得到非最优解。因此考虑将该参数限制在适当的范围，可将启发式信息进行归一化处理，以取得较好的搜索效果。归一化处理步骤如下：

② 从步骤①中找出最大和最小启发信息ηmax和ηmin；

4) 选择概率的全局策略。每只蚂蚁按照各条路径上的信息素数量和启发式信息独立选择下一座需水区。当蚂蚁完成周游后，在其访问的每一条边上留下信息素。在t时刻蚂蚁k在需水区i选择需水区j的转移概率，除了与下一需水区之间的距离及路径上的信息素有关外，还与蚂蚁周游一圈的全局距离相关。因此，在对需水区优选、距离虚拟化及启发信息归一化改进的基础上，可在概率的选择中加入全局距离策略，表示如下：

(9)

2.2 信息素更新策略

(1)信息素的局部更新。信息素的局部更新可以采用蚁群系统的更新策略，即局部更新只对循环中最优的蚂蚁适用，而不适用于所有的蚂蚁。信息素的局部更新按下式进行：

τ(i,j)=(1-ρ)·τ(i,j)+ρ·Δτ(i,j);

(10)

Δτ(i,j)=1/L*。

(11)

式中：τ(i,j)为蚂蚁在需水区i到需水区j之间的信息素量；ρ为信息素挥发强度系数；Δτ(i,j)为需水区i到需水区j之间的信息素增量；L*为按照优先选取最近需水区的原则所确定的一个回路的长度。

(2)信息素的全局更新。主要改进包括：① 每次迭代结束后，只更新最优解路径上的信息，从而更好地利用了历史信息；② 将各条路径上的信息素限制于[τmin，τmax]，超出范围的值将会被强制设置为最大值或者最小值，可以避免算法过早地收敛于非全局最优解；③ 初始时刻，各条路径上的信息素初设值为最大值，便于算法更好地发现优化解。信息素的全局更新公式为：

(12)

(13)

式中：Δτbest(i，j)为最优解路径上的信息素增量；Lbest为最优路径的长度。

(3)蚂蚁数量的自适应调整。虽然蚁群算法能够获得较高质量的解，但是对于大规模的问题，特别是复杂系统问题，算法容易停滞。此时，可以用增加蚂蚁数量的办法来解决。增加蚂蚁的数量如下：

mt+1(i，j)=mt(i，j)+Δm。

(14)

式中：mt+1(i，j)、mt(i，j)分别为t+1和t时刻需水区i、j之间的蚂蚁数；Δm(Δm=0.5mt(i，j))为增加蚂蚁的数量。

受MMAS算法的启发，在改进的算法中每当出现停滞时，可以自适应地提高信息素水平的最小阈值来增大搜索空间，以期发现最优解。当算法停滞后，在增加蚂蚁的同时，将所有路径上的信息素水平调整为：

(15)

式中：δ∈[0,1]的随机数。

(4)增加随机干扰。经过一段时间的运行，仍可能收敛到局部最短路径。为避免过早收敛而停滞，当大部分蚂蚁(当蚂蚁数超过蚂蚁总数的2/3时)的搜索路径是当前的最短路径时，可对局部最短路径上的信息素水平增加随机干扰，以增加搜索的多样性。可按如下公式增加干扰：

τ(i,j)=0.5τ(i,j)+0.5r。

(16)

式中：r为[0,1]的随机数。

3 实例计算与分析

巴家咀水库位于甘肃省东部泾河支流蒲河中游的黄土高原沟壑区，设计灌溉面积9 648 hm2，为西峰区日供水4.38万m3。同时，水库肩负着下游陕甘2省10个区县14万人、19 095 hm2耕地及312国道的防洪安全任务，是集防洪、供水、灌溉、发电等功能于一体的大型综合水利枢纽。表1为巴家咀水库供水区域各需水区的距离及需水量。

应用改进蚁群算法进行管道供水路径优化，步骤如下。

Step 1 参数初始化。设时间t=0；迭代次数计算器Nc=0，预定的最大循环次数Nc max；每条路径上的信息素初值为τij(t)=τmax；信息素增量的初始值设为0；信息素挥发强度系数为ρ；地貌状况及林地状况对路径的影响程度分别为aij和bij；设置初始化禁忌表为空tabuk=Φ，将m只蚂蚁随机放在n个节点上。

Step 3 按照式(8)计算虚拟化的节点距离，同时计算启发信息并归一化。

Step 4 对于每1只蚂蚁(fori=1 tom)，根据状态概率转移公式(9)计算的概率选择节点j，j∈(C-tabuk)(C={c1,c2,…,cn}为n个节点集合，C为需水区集合)，将节点j置于当前解集。

Step 5 修改禁忌表，并将蚂蚁移动到新的节点，将该节点移动到该蚂蚁个体的禁忌表中。

Step 6 计算各蚂蚁的路径长度Lk；记录当前的最好解，如果优于当前的最好解，则用其替换当前的最好解。

Step 7 根据改进后的信息素更新公式更新每条路径上的信息量。

Step 8 判断算法是否停滞，若停滞则按照式(14)进行蚂蚁数量的自适应调整，并按照式(15)修改相应路径上的信息素；判断某一路径上的蚂蚁数是否超过蚂蚁总数的2/3，若超过则按照式(16)进行随机干扰；否则，进入Step 9。

Step 9 若迭代次数小于预定的迭代次数(Nc max)且无退化行为(即找到的都是相同解)则转到Step 4；若循环次数大于预定的迭代次数(Nc max)，则循环结束并输出程序计算结果。

Step 10 输出目前的最优解。

表 1 巴家咀水库供水区域之间的距离及需水量

借鉴文献[15]的研究成果，本研究的参数取值分别为：α=1，β=3.5，ρ=0.3，m=200，τmax=10，τmin=0.1，Nc max=100，τ0=τmax，μ=1.0，aij=0.8和bij=0.3。以MATLAB为应用平台，按照上述路径优化步骤，对改进的蚁群算法编写程序，以实现对供水管线优化问题的求解。

根据巴家咀水库供水规划的要求，拟以巴家咀水库为中心，设计4条供水管道，设计流量1.2 m3/s，根据改进的蚁群算法，得到4条最优的供水路径布设如图1，分别为：① 水库→五郎铺→彭原→草滩→米家川；② 水库→温泉→文安→什社→官坳；③ 水库→后官→董志→南庄→纸坊；④ 水库→肖金→显胜。

图1 基于改进蚁群算法的巴家咀水库最优的布设路径

为验证改进蚁群算法的合理性，在采用相同初始值的情况下，分别利用基本蚁群算法和改进蚁群算法进行5次优化计算，结果比较详见表2。由表2可以看出，利用改进蚁群算法所得到的平均路径、最短路径和最差路径分别为139.635 5，138.214 7和142.301 9 km，基本蚁群算法的结果为145.042 1，140.582 7和149.215 5 km，5次的计算结果均表明改进蚁群算法优于基本蚁群算法。此外，改进蚁群算法的平均迭代次数为314次，也明显优于基本蚁群算法的638次，说明其收敛速度更快。根据式(3)计算供水成本可知，采用改进蚁群算法和基本蚁群算法的最短路径所需总成本分别为11.32和11.51亿元。通过比较可知，改进蚁群算法所计算的路径能够降低工程投资。

表 2 基本蚁群算法和改进蚁群算法优化计算结果的比较

4 结 论

本研究根据巴家咀水库管道供水路径优化的问题，提出了一种改进的蚁群算法。该算法结合黄土高原沟壑区的地貌情况，引入虚拟路径距离，对启发信息进行归一化处理，将蚂蚁要选择的节点数量限制在距蚂蚁所在地较近的一个子集范围内，并利用全局策略进行节点的概率选择；同时，信息素的更新充分利用历史的最优路径进行更新，并将其限制在最大值和最小值之间，可以避免收敛过早；为使蚁群算法获得高质量的最优解，防止改进算法出现停滞，利用蚂蚁数量自适应调整和增加随机干扰的策略，增加了搜索的多样性，避免算法陷入局部最优解。

由于改进蚁群算法中引入了虚拟路径的概念，因此该算法能很好地适用于复杂地质、地貌形态的输电线路优化、管网设计、道路铺设等问题。实例计算分析表明，改进蚁群算法可以提高全局搜索能力和收敛速度，能快速有效地解决供水路径的最优解或近似最优解，可以为供水管道的设计优化选择提供参考，具有一定的指导意义。本研究虽然对蚁群算法进行了改进研究，但该算法还不够成熟，真实蚁群的行为特征、蚁群算法的并行实现、与其他算法的结合、蚁群算法的群体智能等还有待于进一步探索和研究。

[参考文献]

[1] 周 鹏,张 骏,史忠科.分段路径寻优算法研究及实现 [J].计算机应用研究,2005,16(12):241-243.

Zhou P,Zhang J,Shi Z K.Algorithm for searching shortest path piecewise and its implementation [J].Application Research of Computers,2005,16(12):241-243.(in Chinese)

[2] 王顺久,张欣莉,倪长健,等.水资源优化配置原理及方法 [M].北京:中国水利水电出版社,2007.

Wang S J,Zhang X L,Ni C J,et al.Principles and methods of water optimal allocation [M].Beijing:China Water Power Press,2007.(in Chinese)

[3] 沈建峰,许 诚,陈 峰.遗传算法在反舰导弹航路规划中的应用 [J].飞行力学,2005,23(3):52-55,66.

Shen J F,Xu C,Chen F.Application of genetic algorithm to antiship missile route planning [J].Flight Dynamics,2005,23(3):52-55,66.(in Chinese)

[4] 王天平,解建仓,张建龙,等.基于动态生态环境需水量的水土资源优化配置 [J].水土保持学报,2011,25(6):176-180.

Wang T P,Xie J C,Zhang J L,et al.Land and water resources optimal allocation based on dynamic eco-environmentai water requirements [J].Journal of Soil and Water Conservation,2011,25(6):176-180.(in Chinese)

[5] Dorigo M,Di C G,Gambardella L M.Ant algorithms for discrete optimization [J].Artificial Life,1999,5(2):137-172.

[6] Dorigo M,Gambardella L M.Ant colony system:A cooperative learning approach to the traveling salesman problem [J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.

[7] 汪 镭,吴启迪.蚁群算法在连续空间寻优问题求解中的应用 [J].控制与决策,2003,18(1):45-48,57.

Wang L,Wu Q D.Ant system algorithm in continuous space optimization [J].Control and Decision,2003,18(1):45-48,57.(in Chinese)

[8] 李 鹏,朴在林,王剑委.基于改进蚁群算法的农网送电线路设计路径寻优 [J].农业工程学报,2009,25(11):232-235.

Li P,Piao Z L,Wang J W.Optimal route searching for the design of rural power transmission line based on improved ant colony algorithms [J].Transactions of the Chinese Society of Agricultural Engineering,2009,25(11):232-235.(in Chinese)

[9] Rafel S P,Heitor S L,Alex A F.Data mining with an ant co1ony optimization algorithm [J].IEEE Transactions on Evolutionary Computing,2002,6(4):321-332.

[10] 韦 凯,宫全美,周顺华.隧道长期不均匀沉降预测的蚁群算法 [J].同济大学学报:自然科学版,2009,37(8):993-998.

Wei K,Gong Q M,Zhou S H.Ant colony algorithms of long-term uneven settlement prediction in tunnel [J].Journal of Tongji University:Natural Science,2009,37(8):993-998.(in Chinese)

[11] 张志民,张小娟,李明华,等.一种引入奖励与惩罚机制的蚁群算法 [J].计算机仿真,2006,23(7):161-163.

Zhang Z M,Zhang X J,Li M H,et al.Ant colony algorithm with strategy of award and penalty [J].Computer Simulation,2006,23(7):161-163.(in Chinese)

[12] 李梅娟,陈雪波,刘臣奇.基于改进蚁群算法拣选作业优化问题的求解 [J].计算机工程,2009,35(3):219-221.

Li M J,Chen X B,Liu C Q.Solution of order picking optimization problem based on improved ant colony algorithm [J].Computer Engineering,2009,35(3):219-221.(in Chinese)

[13] 李进军,许瑞明,刘德胜,等.求解航路规划优化问题的改进蚁群算法 [J].系统仿真学报,2007,19(14):3276-3280.

Li J J,Xu R M,Liu D S,et al.Improved ant colony algorithm for route planning optimization [J].Journal of System Simulation,2007,19(14):3276-3280.(in Chinese)

[14] 杨剑锋.蚁群算法及其应用研究 [D].杭州:浙江大学,2007.

Yang J F.Ant colony algorithm and its application [D].Hang-zhou:Zhejiang University,2007.(in Chinese)

[15] 徐红梅,陈义保,刘加光,等.蚁群算法中参数设置的研究 [J].山东理工大学学报:自然科学版,2008,22(1):7-11.

Xu H M,Chen Y B,Liu J G,et al.The research on the parameters of the ant colony algorithm [J].Journal of Shandong University of Technology:Science and Technology,2008,22(1):7-11.(in Chinese)