原标题:【文献综述】城市给水与排水系统的优化:现状与发展趋势

姓名:彭帅 学号:17021210850

澳门金沙在线官网,原文题目:Optimization of Potable Water Distribution and Wastewater
Collection Networks: A Systematic Review and Future Research Directions

【嵌牛导读】:蚁群算法(ACO)是受自然界中蚂蚁搜索食物行为的启发,是一种群智能优化算法。粒子群优化具有相当快的逼近最优解的速度,可以有效的对系统的参数进行优化。

作者:Wanqing Zhao ; Thomas H. Beach ; Yacine Rezgui

【嵌牛鼻子】:优化算法

第一作者单位:Cardiff School of Engineering, Cardiff University,
Cardiff, U.K.

【嵌牛提问】:蚁群算法与粒子群算法优缺点?

期刊:IEEE Transactions on Systems, Man, and Cybernetics: Systems

【嵌牛正文】:

发表时间:May 2016

蚁群算法(ACO)是受自然界中蚂蚁搜索食物行为的启发,是一种群智能优化算法。它基于对自然界真实蚁群的集体觅食行为的研究,模拟真实的蚁群协作过程。算法由若干个蚂蚁共同构造解路径,通过在解路径上遗留并交换信息素提高解的质量,进而达到优化的目的。蚁群算法作为通用随机优化方法,已经成功的应用于TSP等一系列组合优化问题中,并取得了较好的结果。但由于该算法是典型的概率算法,算法中的参数设定通常由实验方法确定,导致方法的优化性能与人的经验密切相关,很难使算法性能最优化。

关键词:Artificial intelligence, hydraulics, network optimization,
wastewater collection networks (WWCNs), water distribution networks
(WDNs)

蚁群算法中每只蚂蚁要选择下一步所要走的地方,在选路过程中,蚂蚁依据概率函数选择将要去的地方,这个概率取决于地点间距离和信息素的强度。

供水系统和排水系统是复杂的城市用水基础设施的基本成分。这样的供水和排水网络需要加以合理的设计以有助于未来的改装、扩建和维护活动。因此,需要适当的优化方法来降低设计成本,提高效率,同时也需要满足消费者获取清洁水和排放废水的需求。本文首先回顾了对城市供水系统和排水系统所使用的优化手段,然后从城市供水、排水系统的目标和约束出发,对不同的优化方法讨论了其复杂性和优缺点,并以此为基础对未来的优化方法进行了讨论。

(t+n) = (t)+Δ(t+n)

城市供水系统与排水系统的优化方法复杂而多样。为了对这些方法进行分析,首先要以一定的方法对各种优化方法进行分类,本文对优化方法的分类如图1所示。

上述方程表示信息素的保留率,1-表示信息素的挥发率,为了防止信息的无限积累,取值范围限定在0~1。Δij表示蚂蚁k在时间段t到(t
+n)的过程中,在i到j的路径上留下的残留信息浓度。

澳门金沙在线官网 1

在上述概率方程中,参数α和β:是通过实验确定的。它们对算法性能同样有很大的影响。α值的大小表明留在每个节点上信息量受重视的程度,其值越大,蚂蚁选择被选过的地点的可能性越大。β值的大小表明启发式信息受重视的程度。

图1在给水与排水系统优化中所使用的算法分类

这两个参数对蚁群算法性能的影响和作用是相互配合,密切相关的。但是这两个参数只能依靠经验或重复调试来选择。

这些优化方法中,传统的确定性优化方法、现代的元启发式优化方法与多目标优化方法是在给水系统与排水系统中都得到了广泛应用。­元启发式优化方法中,又可以细分为两类:一类在每一步只得到一个解(如模拟退火算法),另一类在每一步都得到一组解(如遗传算法)。还有一些算法是只在供水系统或是只在排水系统中使用,如分解的优化方法(以Dijkstra最短路径算法为例)一般只用于供水系统,而直观的启发式优化方法(以用于目标检测的SSD算法为例)一般只用于排水系统。

在采用蚁群-粒子群混合算法时,我们可以利用PSO对蚁群系统参数α和β的进行训练。具体训练过程:假设有n个粒子组成一个群落,其中第i个粒子表示为一个二维的向量xi
= ( xi1 , xi2 ) , i

01

= 1,
2,⋯,n,即第i个粒子在搜索空间的中的位置是xi。换言之,每个粒子的位置就是一个潜在的解。将xi带入反馈到蚁群系统并按目标函数就可以计算出其适应值,根据适应值的大小衡量解的优劣。

城市供水系统的优化

蚁群算法的优点:

对于供水系统与排水系统,目前都可以利用各种软件进行建模并加以分析。建设一套城市供水系统或排水系统,都是在给定了水力学等一系列约束的条件下,通过选取合适的给水/排水系统构建方式(管道、泵站等的设计)以最小的成本满足各种约束。以城市供水系统为例。其优化方程可以写作图2的形式。其中水头损失可以用海澄-威廉公式进行计算。

蚁群算法与其他启发式算法相比,在求解性能上,具有很强的鲁棒性(对基本蚁群算法模型稍加修改,便可以应用于其他问题)和搜索较好解的能力。

澳门金沙在线官网 2

蚁群算法是一种基于种群的进化算法,具有本质并行性,易于并行实现。

图2城市供水系统的优化方程

蚁群算法很容易与多种启发式算法结合,以改善算法性能。

图2中的方程含义如下:

蚁群算法存在的问题:

(1):目标函数(成本)的最小化;

TSP问题是一类经典的组合优化问题,即在给定城市个数和各城市之间距离的条件下,找到一条遍历所有城市且每个城市只能访问一次的总路程最短的路线。蚁群算法在TSP问题应用中取得了良好的效果,但是也存在一些不足:

(2):管道种类的范围;

(1),如果参数α和β设置不当,导致求解速度很慢且所得解的质量特别差。

(3)(4):表示每段管道都属于某一种管道;

(2),基本蚁群算法计算量大,求解所需时间较长。

(5):每个节点流量守恒;

(3),基本蚁群算法中理论上要求所有的蚂蚁选择同一路线,该线路即为所求的最优线路;但在实际计算中,在给定一定循环数的条件下很难达到这种情况。

(6)(7):管道中水头损失的水力学关系;

另一方面,在其它的实际应用中,如图像处理中寻求最优模板问题,我们并不要求所有的蚂蚁都找到最优模板,而只需要一只找到最优模板即可。如果要求所有的蚂蚁都找到最优模板,反而影响了计算效率。

(8):水头损失需要满足的约束条件。

蚁群算法收敛速度慢、易陷入局部最优。蚁群算法中初始信息素匮乏。蚁群算法一般需要较长的搜索时间,其复杂度可以反映这一点;而且该方法容易出现停滞现象,即搜索进行到一定程度后,所有个体发现的解完全一致,不能对解空间进一步进行搜索,不利于发现更好的解。

整体的优化目标便是寻找一种管网设计方式,使得成本最小化。

粒子群优化具有相当快的逼近最优解的速度,可以有效的对系统的参数进行优化。粒子群算法的本质是利用当前位置、全局极值和个体极值3个信息,指导粒子下一步迭代位置。其个体充分利用自身经验和群体经验调整自身的状态是粒子群算法具有优异特性的关键。PSO算法的优势在于求解一些连续函数的优化问题。

这个问题可由0-1背包问题多项式归约得到,因此属于NP难问题。与此同时,它也是一个非线性的组合最优化问题。传统的优化算法最早被用来解决该问题,但传统的优化算法其时间复杂度是管道数量的指数函数;使用线性规划的方法可以降低复杂度,但其往往无法跳出局部最优解;动态规划方法在面对环状管网的计算非常复杂;使用拉格朗日法进行解决,也有可能陷入局部最优。在这样的情形下,元启发式算法便发挥了其作用。其中遗传算法(使用0-1或整数编码处理离散管径)及其变种在供水管网的优化中最为常用,蚁群、粒子群、差异演化等算法也在城市供水系统的优化中得到了一些应用,且有部分研究显示蚁群算法在复杂网络中的表现稍好于遗传算法。

PSO算法存在的问题:

供水系统优化的另一种思路是将复杂的大网络分解为若干个子网络进行优化,这在漏损控制中十分常见。当考虑多个目标时,多目标优化的方法便需要加以考虑。多目标优化的解常用帕累托前沿面的形式表示,而在供水系统中进行多目标优化则常用各种遗传算法的变种,如NSGA-II。

问题最主要的是它容易产生早熟收敛(尤其是在处理复杂的多峰搜索问题中)、局部寻优能力较差等。PSO算法陷入局部最小,主要归咎于种群在搜索空间中多样性的丢失。

目前对于不同的优化算法,尚未对其进行大规模计算分析,以衡量这些算法的时间复杂度差异;这意味着目前尚难以确定寻优效率较高,且计算时间较少的优化算法。

不同算法的混合模型主要分为两类:(1)全局优化算法与局部优化算法混合;(2)全局优化算法与全局优化算法混合。纵观各种与PSO算法相关的混合算法,大多数基本上采用一种策略对其改进,要么与其他算法,要么加入变异操作,同时采用两种策略的混合算法较少。

02

上述策略中,两者之间有一定的矛盾性,全局算法与局部算法相混合,尽管可以提高局部收敛速度,但也加剧了陷入局部极小的可能;全局算法与全局算法的混合,算法的局部细化能力仍然没有改善。但如果只加入变异操作,则算法的探测能力得到提高,但也损害了其局部开发能力。

城市排水系统的优化

因此如果将局部搜索和变异操作同时混合到PSO算法中,通过适当的调节,发挥各自的优点,提高算法的开发能力,增加变异操作防止算法早熟,来共同提高PSO算法的全局寻优能力。

对于城市排水系统,其优化方程更为复杂,可用图3进行表述。在城市排水系统中,常用曼宁公式计算污水的水力学行为。

融合策略:

澳门金沙在线官网 3

(1)针对蚁群算法初始信息素匮乏的缺点,采用其他算法生成初始信息素分布,利用蚁群算法求精确解,从而提高时间效率和求解精度。(使用的其他算法的求解结果以什么规则转换成蚁群算法的信息素初值,需要通过多次实验)

图3城市排水系统的优化方程

(2)将其他算法(如遗传算法)引入到蚁群算法系统的每次迭代过程中。以蚁群系统每一代形成的解作为其他算法的初始种群,然后经过其他算法的多次迭代,试图寻找更好的解,从而加快蚁群系统的收敛速度,提高求解速率。

在图3中的方程含义如下:

(3)蚁群算法中α,β的选取往往是通过经验来取得的,而选取不当时会造成算法的性能大大降低,因此可以利用其他算法对蚁群系统参数α,β进行训练。

(1):目标函数(成本)的最小化;

(4)对于蚁群算法出现过早收敛于非全局最优解以及时间过长的缺点,可以通过使用蚁群算法进行搜索,然后用其他算法对蚁群算法得到的有效路由路径,通过选择、交叉、变异等优化过程,产生性能更优的下一代群体。

(2):管道种类的范围;

(5)PSO算法由于局部寻优能力较差,因此可以在搜索过程中融入确定性局部搜索算法。

(3)-(5):每段管道的流量约束;

(6)-(9):管道节点的高程约束;

(10):管道的充满度不能超过最大设定值;

(11)-(13):检查井的高程约束。

这一系列的方程都建立在管网最大设计流量的基础上。

对于城市排水系统的优化设计,离散微分动态规划化是过去最为常用的传统优化方法,但是受大型网络的限制,且需要在计算管径时添加一些与中心角相关的假设。早期的启发式算法中,则往往对管道中水深与半径的关系进行了一些假定,导致结果偏离最优解。现代的元启发式算法中,模拟退火算法、紧急搜索与元胞自动机都在排水系统的优化中得到了不少应用,而遗传算法同样应用广泛。在城市排水系统的优化中,将精英遗传算法与自适应遗传算法相结合的精英自适应遗传算法有着良好的优化效果。蚁群优化算法也可以用于城市排水系统的优化,但其需要对排水系统优化问题中的一些连续变量(如管道坡度或高程)进行离散化,这使得蚁群优化算法的效果受到了一定影响。粒子群算法的应用较为少见,其在城市排水系统的优化中有一定的发挥潜力。

对于城市排水系统的多目标优化,将元胞自动机与NSGA相结合可以发挥二者的优势,并规避二者的一些劣势。使用元胞自动机可以对遗传算法的局部搜索能力进行补充,同时又可以利用遗传算法的全局搜索能力,从而起到良好的多目标优化效果。在城市排水系统的多目标优化中,目标函数往往为成本与内涝量。

虽然元启发式算法在解决城市排水系统中有着全局搜索能力较强,计算复杂度较低等优势,但由于城市排水系统的问题空间往往特别大,且存在着大量约束,元启发式算法生成初始可行解的难度往往较高。一种解决方法是将元启发式算法与传统优化算法(如二次规划)相结合,利用传统优化算法解决一些需要连续优化,且约束较强的部分问题。

03

展望

虽然目前对城市供水系统与排水系统,存在着大量的方法进行优化,但对于这些不同的优化方法,尚缺乏一个有效的平台比较不同方法复杂度。未来可以建立一套问题库,在问题库中包含不同类型的城市供水/排水系统,将不同的算法在相同的计算平台上进行大规模计算分析,从而能够更好地比较不同算法解决不同问题的效率与复杂度。

本文对城市供水系统与排水系统中优化算法的使用现状进行了综述,对不同的优化算法进行了分类讨论,并关注了这些算法的使用条件与使用方法。在本文最后,作者指出,目前对于这些不同的优化算法,尚缺乏一个通用的有效手段对不同算法的复杂性进行比较,并认为在统一基准上进行的大规模计算分析是一种可行的手段。本文中所提到的不同算法,在未来的研究中可以根据不同的问题加以利用;同时对不同优化算法的复杂性加以评估,也是一个未来可以考虑的方向。

澳门金沙在线官网 4返回搜狐,查看更多

责任编辑:

相关文章