快捷搜索:
您的位置:bv1946伟德入口 > 互联网 > 城市给水与排水系统的优化,蚁群算法与粒子群

城市给水与排水系统的优化,蚁群算法与粒子群

2019-10-12 04:04

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

姓名:彭帅 学号:17021210850

一、最优化问题的分类

引言

韦德国际1946手机版官网,TSP(Traveling Salesman Problem)即旅行商问题,是数学领域中著名问题之一。这个问题是这样的:假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径长度为所有路径之中的最小值。TSP是一个典型的组合优化问题,且是一个NP完全难题,关于NP的这个概念本文就不做详细介绍了,但简单的说就是:TSP问题目前尚不能找到一个多项式时间复杂度的算法来求解。

原文题目:Optimization of Potable Water Distribution and Wastewater Collection Networks: A Systematic Review and Future Research Directions

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

1. 根据约束类型分类:

(1)无约束问题
(2)约束问题

问题分析

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

【嵌牛鼻子】:优化算法

2.根据目标函数及约束函数的类型分类:

最优化问题也称为规划问题
如果最优化问题的目标函数为f(x),约束条件为gi(x)>=0,i=1,2,..,m,则:

1.识别本质

这个问题乍一看,有那么一点像“最短路径问题”,然后我们就会自然地想到用Dijkstra算法去求得“从某一个城市出发,到其他所有剩余城市的最短路径”,再或者如果是个真实地图,我们可以用启发式的“A星算法”快速搜索出“从某一个城市到另一个指定城市间的最短路径”。的确,如果是这样真的挺好,但仔细想,这个问题并非单纯这么简单,它还要求去寻找“从某个城市开始,分别经过其它城市一次且仅一次,最后再回到这个出发城市的最短巡回路径”。

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

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

(1)线性规划:

当f(x)和gi(x)均为线性函数时

2.深入分析

所以该怎么求解呢,我们很容易想到一种类似于穷举的思路:现在假设我们要拜访11个城市,从城市1出发,最后回到城市1。显然,从城市1出来后,我们随即可以选择剩余的10个城市之一进行拜访(这里所有城市都是连通的,总是可达的,而不连通的情况属于个人特殊业务的装饰处理,不是本文考虑范畴),那么很显然这里就有10种选择,以此类推,下一次就有9种选择…总的可选路线数就是:10!。也就是说需要用for循环迭代10!次,才能找出所有的路线,进而筛选出最短的那条来。如果只拜访个10个城市或许还好的话(需要迭代3628800次),那要拜访100个城市(需要迭代9.3326215443944 * 10^157)简直就是计算机的噩梦!更多个城市的话,计算的时间开销可想而知!
更一般地,如果要拜访n 1个城市,总的可选路线数就是n!,进而时间复杂度就是O(n!),从这里我们同理也可以看出,这个算法的时间复杂度是非多项式的,它的开销大是显而易见的。所以问题的关键不在于寻找两两城市间的最短路径,而在于去寻找一那条最短的巡回路径,换句话说,就是寻找一组拜访城市的先后次序序列 n1n2n3…nini 1…nnn1。

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

【嵌牛正文】:

(2)非线性规划:

当f(x)和gi(x)不全为线性函数时

解决方案

这是个NP完全问题,穷举算法的效率又不高,那我们该如何通过一个多项式时间复杂度的算法快速求出这个先后次序呢?目前比较主流的方法是采用一些随机的、启发式的搜索算法,比如遗传算法、蚁群算法、模拟退货算法、粒子群算法等。但这些算法都有一个缺点,就是不一定能求出最优解,只能收敛于(近似逼近)最优解,得到一个次优解,因为他们本质都是随机算法,大多都会以类似“一定概率接受或舍去”的思路去筛选解。各算法的实现思路都有不同,但也或多或少有互相借鉴的地方,有的与随机因子有关、有的与初始状态有关、有的与随机函数有关、有的与选择策略有关……本文主要讲述遗传算法和蚁群算法的求解思路,关于其他更多类型的搜索算法可以在网上查阅,都有很多资料哒。
所以,综合上述分析,我们不难看出TSP问题的求解大概是由两步构成的:

  1. 计算两两城市间的最短路径:利用类似Dijkstra、Flord、A星的算法求出最短路线。
  2. 计算最短巡回路径:利用类似遗传算法、蚁群算法的搜索算法求巡回拜访的次序。

关于1中需要说明一点,就是现实生活中我们的地图往往不是一个完全图,而是一个非完全图,甚至有些节点仅仅是道路的分岔口,而不是城市节点。

  • 完全图:两两城市间都有直达的路线,这条路线不需要经过中间其他节点;

    韦德国际1946手机版官网 1

  • 非完全图:偶尔有两个城市间的路线需要经过其他中间节点。

    韦德国际1946手机版官网 2

由于本文着重叙述步骤2),更侧重于搜索算法本身,所以后续文章一律将地图简化为一个完全图。因为就算是非完全图,我们也完全可以事先地、离线地采用步骤1)中的算法求解,得到两两城市间的最短路线,存入数据库,作为持久数据提供给后续在线的、需由用户指定拜访的城市的步骤2)使用,所以简化成完全图是合乎情理的。

发表时间:May 2016

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

(3)二次规划:

当f(x)为二次函数,而gi(x)全为线性函数时

结语

本章就先讲到这啦,下一篇会着重讲述“遗传算法”,因为它在算法思想、最优解准确率、适用面等各方面表现都比较好(一方面是我自己的感受,一方面很多论文也这样写到),所以我选择把它的设计与实现过程分享给大家作为参考(如果不嫌弃的话)。

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

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

3.根据变量的类型分类

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

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

(1)整数规划:

对于最优化问题,如果变量x=(x1,x2,…,xn)T的各分量只能取整数,则相应的最优化问题称为整数规划。

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

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

(2)混合整数规划:

如果变量x=(x1,x2,…,xn)T 的部分分量只能取整数,则相应的最优化问题称为混合整数规划。

韦德国际1946手机版官网 3

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

(3)0-1规划:

如果变量x=(x1,x2,…,xn)T 的各分量只能取0和1,则相应的最优化问题称为0-1规划。

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

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

二、最优化问题的基本模型要素

最优化模型一般包括变量、约束条件和目标函数三要素:

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

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

1.变量:

指最优化问题中待确定的某些量。变量可用x=(x1,x2,…,xn)T表示。

01

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

2.约束条件:

指在求最优解时对变量的某些限制,包括技术上的约束、资源上的约束和时间上的约束等。列出的约束条件越接近实际系统,则所求得的系统最优解也就越接近实际最优解。约束条件可用 gi(x)≤0表示i=1,2,…,m,m 表示约束条件数;或x∈R(R表示可行集合)。

城市供水系统的优化

蚁群算法的优点:

3.目标函数:

最优化有一定的评价标准。目标函数就是这种标准的数学描述,一般可用f(x)来表示,即f(x)=f(x1,x2,…,xn)。要求目标函数为最大时可写成;要求最小时则可写成。目标函数可以是系统功能的函数或费用的函数。它必须在满足规定的约束条件下达到最大或最小。  问题的分类  最优化问题根据其中的变量、约束、目标、问题性质、时间因素和函数关系等不同情况,可分成多种类型(见表)。最优化方法

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

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

三、常见的最优化方法

韦德国际1946手机版官网 4

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

1. 梯度下降法(Gradient Descent)

梯度下降法是最早最简单,也是最为常用的最优化方法。梯度下降法实现简单,当目标函数是凸函数时,梯度下降法的解是全局解。一般情况下,其解不保证是全局最优解,梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向,因为该方向为当前位置的最快下降方向,所以也被称为是”最速下降法“。最速下降法越接近目标值,步长越小,前进越慢。

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

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

2. 牛顿法(Newton's Method)和拟牛顿法(Quasi-Newton Methods)

  • 牛顿法
    牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x) = 0的根。牛顿法最大的特点就在于它的收敛速度很快。
  • 拟牛顿法
    拟牛顿法是求解非线性优化问题最有效的方法之一,其本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷,它使用正定矩阵来近似Hessian矩阵的逆,从而简化了运算的复杂度。拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化,构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法,尤其对于困难的问题。另外,因为拟牛顿法不需要二阶导数的信息,所以有时比牛顿法更为有效。如今,优化软件中包含了大量的拟牛顿算法用来解决无约束,约束,和大规模的优化问题。

图2中的方程含义如下:

蚁群算法存在的问题:

3. 共轭梯度法(Conjugate Gradient)

共轭梯度法是介于最速下降法与牛顿法之间的一个方法,它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点,共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一。在各种优化算法中,共轭梯度法是非常重要的一种。其优点是所需存储量小,具有步收敛性,稳定性高,而且不需要任何外来参数。

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

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

4. 启发式优化方法

启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法,而不是系统地、以确定的步骤去寻求答案。启发式优化方法种类繁多,包括经典的模拟退火方法、遗传算法、蚁群算法以及粒子群算法等等。

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

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

5. 拉格朗日乘数法的基本思想

作为一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有(n k)个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。
将一个含有n个变量和k个约束条件的约束优化问题转化为含有(n k)个变量的无约束优化问题,拉格朗日乘数法从数学意义入手,通过引入拉格朗日乘子建立极值条件,对n个变量分别求偏导对应了n个方程,然后加上k个约束条件(对应k个拉格朗日乘子)一起构成包含了(n k)变量的(n k)个方程的方程组问题,这样就能根据求方程组的方法对其进行求解。

(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进行表述。在城市排水系统中,常用曼宁公式计算污水的水力学行为。

融合策略:

韦德国际1946手机版官网 5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

03

展望

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

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

韦德国际1946手机版官网 6返回搜狐,查看更多

责任编辑:

本文由bv1946伟德入口发布于互联网,转载请注明出处:城市给水与排水系统的优化,蚁群算法与粒子群

关键词: