大洪水算法

2024-10-23

大洪水算法（精选4篇）

大洪水算法篇1

摘要：大洪水算法是一种求解组合优化问题的独特方法, 该方法通过模拟洪水上涨的过程来达到求解一些困难组合优化问题的目的。本文将其推广到多目标情形, 并以旅行商问题为例, 设计了相应的求解算法, 经大量数据测试和验证, 获得了较好的结果。

关键词：大洪水算法,多目标,旅行商问题

1 引言

旅行商问题 (Travelling Salesman Problem, 简称TSP) 是组合优化领域一个著名的经典难题, 迄今为止尚未完全解决。一般叙述为:有一旅行商从城市1出发, 欲遍历其余城市至少一次, 最后再回到城市1, 在各城市之间距离已知的情况下, 问应当选择怎样的行走路线, 才能使总行程最短。由于许多实际问题在本质上都可归结为一个简单的TSP问题, 因此寻找适合有效的算法尤为重要。目前业已存在的精确型算法有线性规划算法、动态规划算法和分支定界算法, 但这些精确型算法本质上而言都是指数级算法, 除了分支定界算法有时被用来求近似解, 或者与一些启发式算法相结合, 其他算法在实际中均较少采用。精确型算法在大规模组合问题上的失效 (组合爆炸) , 也迫使人们不得不转向近似算法或启发式算法, 如遗传算法、模拟退火法、蚁群算法等。

20世纪90年代, 人们在研究模拟退火算法在其他领域的应用时, 发现了一种行之有效的算法, 因为其遍历过程与圣经中的诺亚方舟的大洪水有相似之处, 所以将其称之为大洪水算法。该算法最先于1990年由Dueck在“New Optimization Heuristics”一文中提出, 在用Threshold Accepting算法对背包问题进行测试的过程中, 产生了两种优化算法, 其中之一就是大洪水算法[1,2]。该算法用于组合优化问题, 与爬山算法、模拟退火算法有诸多相似。这里可以用一个形象化的比喻来说明, 有一空地因一直不间断地下雨而产生洪水, 空地上某人正在爬山, 他可以向任意方向行动。随着水平面不断上涨, 为了生存他必须不断找到更高处, 一段时间之后, 最终他将会到达空地的最高点, 即得到最优解。

早在20世纪90年代初提出的大洪水算法, 最初是用于求解TSP问题, 随后又被应用于其他问题的求解中, 如复杂系统优化[2]、蛋白质结构预测等。然而目前有关方面的应用并不多, 国内这方面的研究还非常稀缺。

2 多目标TSP问题及其模型

多目标旅行商问题 (多目标TSP) 是经典TSP的扩展和延伸, 科学管理和经济决策中的大量问题都可以归结为多目标优化问题。对于很多决策者来说需要优化的目标往往不止一个, 如在实际TSP问题中, 城市之间的权重属性有多个, 常常需要考虑路程最短、时间最少、费用最省、风险最小等多方面的因素, 因此研究这种多目标TSP问题就具有很现实的实际意义。

由于多目标意义下的解是一种“折衷解”“非劣解”, 因而多目标TSP解的含义可定义如下:

若给定图G的各边弧上有L个权值, 则使得回路上相应的L个目标值都尽可能小的解就称为这个多目标TSP的 (Pareto) 有效解。

假定有一回路解H, 若不存在任何其他回路解Q, 使得Zr (Q) ≤Zr (H) , r=1, 2, …, L, 其中, 至少有一个不等式严格成立 (Zr为相应的目标函数值) , 则H为一个非劣解或Pareto解[3]。

记G= (V, E) 为赋权图, V={1, 2, …, n}为顶点集, E为边集, 各顶点间的权值drij已知 (drij>0, drii=∞, i, j∈V, r=1, 2, …, L) , 并设

$x_{i j} = {\begin{cases} 1, 边 (i, j) 在解回路上 \\ 0, 其他 \end{cases}$

则多目标TSP问题可写为如下的数学规划模型:

$\begin{array}{l} \min Ζ = {\sum_{i = 1}^{n} \sum_{j = 1}^{n} d_{i j}^{1} \cdot x_{i j}, \sum_{i = 1}^{n} \sum_{j = 1}^{n} d_{i j}^{2} \cdot x_{i j}, \dots, \sum_{i = 1}^{n} \sum_{j = 1}^{n} d_{i j}^{L} \cdot x_{i j}} \\ s . t . {\begin{cases} \sum_{j = 1}^{n} x_{i j} = 1, i \in V, \\ \sum_{i = 1}^{n} x_{i j} = 1, j \in V \\ \sum_{i \in S} \sum_{j \in S} x_{i j} \leq | S | - 1, \forall S \subset V, \\ x_{i j} \in {0, 1} \end{cases} \end{array}$

其中, |S|为集合S中所含图G的顶点个数。前两个约束表示对每个顶点而言有且只有一条边进、一条边出, 第三个约束则保证了没有任何子回路解的产生。对一般的TSP而言, 有dij=dji (i, j∈V) , 称为对称问题。

3 多目标TSP的大洪水算法

基于目标极大化的大洪水算法基本思想为:

Step 1 计算回路初始解;

Step 2 设定参数值UP>0;

Step 3 选择初始WaterLevel>0;

Opt:

Step 4 进行邻域或局部搜索以改进当前解, 得到一个新的解;

Step 5 基于新得到的解, 计算目标函数E;

Step 6 如果E>WaterLevel, 用新得到的解带代替初始解, WaterLevel+UP;否则转Opt。

其中, UP为洪水上涨的速度, 亦可理解为“Rain Speed”。

大洪水算法相对于其他算法来说最大的优势在于, 算法只依赖于一个参数UP, UP值能够决定运算速度并对最终解造成影响。如果UP取值过大, 算法虽然运行很快, 但是产生的结果不甚理想;如果UP取值足够小, 那么经过长时间运算后将会给出一个相对好的解。而对于形如TSP这样的极小化问题, 洪水算法亦可理解为干旱算法, 相应地, UP也变为洪水蒸发速度, 原先的登山者也可以为找寻水资源的鱼类所取代[4]。

由此, 可将多目标TSP的大洪水算法步骤按伪码形式叙述如下:

如果实际问题有权重优先级, 只需考虑为参数UPi (i=1, 2, …, L) 分别设置相应的数值, 就能满足这种要求。

上述求解多目标TSP的算法用Delphi 10.0实现, 在Windows XP环境下编译通过。

4 算例测试

采用文献[5]中的数据实例来验证大洪水算法的有效性, 并与其他算法进行比较。

取

对该算例, 运用大洪水算法进行求解, 得到的非劣解以及与蚁群算法、模拟退火算法 (SA) 、边交换法 (2-Opt) 比较如表1所示, 其中, 取参数UP1=0.01, UP2=0.01, 蚁群算法中的α, β=1, 2, 3, ρ=0.5～0.9, 迭代次数均为5000, 各运行30轮。

可以看出, 表中结果已经显示出大洪水算法的一些优点。经30轮的运算后, 用大洪水算法得到的非劣解与蚁群算法相同, 但较之模拟退火和边交换法要优越很多。实验中还发现, 在迭代次数很大的情况下, 大洪水算法的效率最高, 计算运行速度最快, 边交换法其次, 蚁群算法稍逊, 但是它能够给出相对多的非劣解, 速度最慢的是模拟退火算法。

关于参数UP1, UP2, 可以用实验方法确定其最佳组合。例如, 对于单目标TSP问题, 文献[1]中由实验得出选择参数UP的合理准则为当前解的目标值与WaterLevel值之间平均差值的1%左右。因此, 如果同时考虑运算效率和计算结果, 大洪水算法不失为一种相对较好的选择。

5 结束语

大洪水算法仅依赖于一个参数, 结构简单易于执行, 也便于理解。具体求解中, 可通过人为比较选择, 或者预先设定一个集合, 记录当前已得到的非劣解, 然后用新求出的解与之比较, 判断是否已经改进了非劣解, 再确定是否停止运算, 输出结果。在某些领域里, 大洪水算法, 尤其是根据应用对象的特征经过改进后的算法能够得出比其他优化算法更为经济有效的结果, 因此, 对该算法的进一步深入研究将为生产和实践中有关应用提供更为丰富的求解手段和工具。

参考文献

[1]Dueck G.New optimization heuristics:the greatdeluge algorithm and the record-to-record travel[J].Journal of Computational Physics, 1993, 104 (1) :86~92.

[2]Ravi W.Optimazation of complex system reliabilityby a modified great deluge algorithm[J].Asia-PacificJournal of Operational Research, 2004, 21 (4) :487~497.

[3]马良, 朱刚, 宁爱兵.蚁群优化算法[M].北京:科学出版社, 2008.

[4]Weigert G, Horn S, Werner S.Optimization ofmanufacturing process by distributed simulation[J].International Journal of Production Research, 2006, 44:3677~3692.

[5]马良, 蒋馥.多目标旅行售货员问题的蚂蚁算法求解[J].系统工程理论方法应用, 1999, 8 (4) :23~27.

历史上的“大洪水” 篇2

首先，让我们看看《圣经》上是怎样说的：“在2月17日，天窗打开了，巨大的渊薮全部被冲溃。大雨伴着风暴持续了40个白天和40个黑夜。”而诺亚的方舟，也足足在水中漂流了40天，最后才搁浅在高山之巅。

公元前3500年的苏美尔资料中这样写到：“那种情形恐怖得让人难以接受，风在空中可怕地呼叫着，大家都在拼命逃跑，什么都不顾了。都以为战争开始了……”著名的古文书《波波卡-吴夫》，书中是这样记载的：“大洪水来了，天地变得一片漆黑，还有黑色的雨不停地下。人们拼命地跑……但还是被灭绝了。”

据说，古巴比伦的《吉尔伽美什史诗》是世界上现存史料中对大洪水记载最完整的，因为它是由从大洪水中幸免于难的人口述而成的。在它的记载里，洪水伴随着风暴，几乎在一夜之间淹没了大陆，只有居住在山上和逃到山上的人才得以生存。

让我们看看中国关于上古的这次大洪水的记载：《山海经·海内篇》记载：“洪水滔天”，“鲧窃息壤以湮洪水”；《孟子·腾文公》记载：“当尧之时，天下犹未平。洪水横流，泛滥于天下。”“水逆行，泛滥于中国”；《淮南子·览冥训》曰：“望古之际，四极废，九州裂，天不兼覆，地不周载，火炎炎而不灭，水泱泱而不息。”

大洪水传说中惊人的相似之处

在各民族的传说中，有一些地方让人百思不得其解。

首先，所有受到提醒的人，都是被预先告之并受命准备好了船只，在洪水来临的时候，依靠船只保证了性命；而且都在最后使用飞鸟去探求究竟，并且都是在飞鸟衔来了新的植物后，才离开了方舟。如，诺亚放飞了3次鸽子，直到鸽子衔回了橄榄枝。

其次，受到警告的人都是男女两人，并且都在劫难后开始了新的种族繁衍。如中国的伏羲兄妹，英伦群岛的比德和碧蓝，希腊的奥尼恩夫妇等等。

再有就是，大洪水的水位描写和时间描写，几乎完全一致。洪水都是淹没了平原、村庄、树木和矮小的丘陵。最后只有逃到了高山上的人才得以活命。持续时间100到120天。

还有也是最难以理解的就是，几乎都发生在北半球！而南半球很少听到类似的传说。

真的有“大洪水”吗？

1922年，考古学家伦德纳·武力爵士，在波斯湾附近的美索不达米亚平原考察时，发现了一座掩埋在地下的苏美尔古吾饵城。在古遗址之下，发现了整整有2米多厚的黏土层。在这层沉积层之上是古城的遗址。对黏土层的分析表明，这层黏土属于洪水沉积后的淤土，也就是说，在人类的这个历史时期之前，曾经有过一场洪水，洪水的规模之大，足以摧毁旧的苏美尔文明。

不可否认，目前人类在大陆上找到的证据和痕迹并不足以直接证明大洪水的存在。但是，从历史资料、各民族的历史传说和一些不太明显的地址特征中，可以让我们大胆地进行这样的假设和推想：大约在1万年前，一场大洪水席卷了北半球，所有低于大约1000米的山峰都被淹没。洪水的高峰期约持续了40天左右；到洪水最后消退，是大约100～120天以后的事了。这场大规模的灾害，毁灭了地球上绝大部分的人类。幸存下来的人类，大多是平时居住在高原和山区的人们，他们的进化程度远比居住在富饶的平原和大河流域的人群低得多。洪水退后，他们进入了平原，接受了原来的文化遗产。但是这就造成了一个现象：

从上古到现在，似乎我们的文化经历了一个断层。

毁灭人类的全球性“海浸事件”

但是，现在就有了一个问题：如此大的一场大洪水，几乎将整个北半球淹没，可是这样的海量的水是从哪里来的呢？真的是雨水吗？

单靠降雨是不可能在几个月甚至几年、几十年内造成如此大的水量。绝不可能！那么水究竟是从哪里来的呢？答案只有一个：是海水！就像我们成语里说的：“沧海桑田”，所谓上古的大洪水事件是一次巨大的、全球性的海浸事件！而连绵数月的雨水，只不过是伴随洪水的天气现象，只是在这场几乎毁灭了人类的大洪水中起了推波助澜的作用。

这样就又导出了一个问题，也是最有意思并且最值得讨论和探索的现象，是什么造成了这次几乎毁灭人类的全球性“海浸事件”？是神的愤怒，还是一种天文现象导致的气候或磁场异常触发了这场全球性的海浸事件？

关于大洪水的结论

在世界上任何一个有足够时间跨度的民族历史和传说中，都有着惊人相似的“大洪水”的传说。而且传说中的时间、地点、人物、内容都有着惊人的相似之处。

综上所述，我们是否能得出这样的结论：

一、大洪水确实发生过，大致的时间是公元前8000年到1.4万年之间；二、一种巨大能量的突然作用，导致了这次“史前大洪水”或者更确切地说，是“史前全球性海浸事件”。而如此巨大的能量，目前看，应当而且只能来自于我们的星球之外；三、这次“史前大洪水”造成了一个史前文化断层，就像我们传说中消失的“亚特拉蒂斯”。

平滑系数试算法放大洪水过程线篇3

关键词：洪水过程线,同频率放大,直接法,平滑系数试算法

一般计算洪峰流量及各个时段的放大系数时采用如下公式:

undefined

本文暂称此方法为直接法。在实际中会发现, 按直接法进行放大, 由于典型洪水过程洪峰及各时段洪量的不同频率, 放大后的洪水过程在各时段的衔接处会出现跳跃, 因为时段前后2个流量点分别乘以了不同的放大系数。如图1, 典型洪水的时段分段处前一时刻的流量为Q前, 放大系数为K前;时段分段处后一时刻的流量为Q后, 放大系数为K后。若典型洪水过程中, Q前

Q前×K前>Q后×K后

使放大的洪水过程处于下降阶段, 时段衔接处出现了跳跃现象。为解决这种现象, 有必要研究设计洪水过程线放大的方法。

1平滑系数试算法介绍

直接法将每一个时段作为一个放大系数分组, 在分组内每一个流量的放大系数是相同的。平滑系数放大法将包含比一个时段更长的时段范围作为一个放大系数分组, 在分组内放大系数是渐变的, 这样可消除时段衔接处的跳跃问题。

以图2为例, 洪峰时刻为tm、洪峰流量为Qm;最大6 h起止时刻分别为t1a、t1b, 洪量为W6h;最大24 h起止时刻分别为t2a、t2b, 洪量为W24h;最大72 h为t3a、t3b, 洪量为W72h。整个洪水过程为72 h, Δt=1 h。设计值分别为Qmp、W6hp、W24hp、W72hp。

平滑系数试算法的计算步骤如下。

(1) 计算典型洪水所有时段的起止时刻得到tm、t1a、t1b、t2a、t2b、t3a、t3b。

(2) 计算洪峰流量放大系数

undefined

(3) 确定放大系数分组。将包含比一个时段更长的时段范围作为一个放大系数分组。如放大最大6 h控制段, 可以选择早于t1a时刻作为起点 (假设为t1a′) , 晚于t1b时刻作为终点 (假设为t1b′) 的一个分组, 但应包含在下一个控制时段之内, 即t1a′>t2a、t1b′

(4) 分组内放大系数的计算。在最大6 h时段分组内, 洪峰的放大系数Km为已知, 当该分组计算完毕时, 分组端点t1a′时刻与t1b′时刻的放大系数为已知, 作为下一分组的已知端点, 进行下一分组计算。

假设分组内远离洪峰端点的放大系数为Kx (此Kx为试算值 (见图3) , 由步骤 (5) 给出并不断试算) , 则分组内t1a′～tm之间的放大系数Ki由Km与Kx用直线内插计算, 公式如下:

undefined

tm～t1b′之间的计算公式类似。

(5) Kx的试算。

1) 由步骤 (4) 得到第一分组内每一个流量点的放大系数, 即可计算出放大后的第一控制时段的设计洪水过程线, 统计第一控制时段的洪量Wx。

如Wx=W6hp, 则假设的Kx与由Kx得到的第一控制时段的洪水过程线即为所求。

2) 以Kx为自变量, 则方程f (Kx) =W6h-Wx是一个单调递减的方程, 因为Kx增大则时段内Ki增大, Qpi增大, 洪量Wx增大。这样方程f (Kx) =0的根可用二分法逼近试算:

①假设K的下边界条件Kxmin=0, 上边界条件Kxmax=Km×10 000 (洪峰放大系数的10 000倍) ;

②令Kx=0.5 (Kxmin+Kxmax) , 计算得到f (Kx) ;

③如果f (Kx) >0, 则

Kx的下边界条件Kxmin=Kx, Kxmax不变

转到步骤②

如果f (Kx) <0, 则

Kx的上边界条件Kxmax=Kx, Kxmin不变

转到步骤②

如果f (Kx) =0或f (Kx) 是一个很小的可以接受的值, 则结束试算, 此时的Kx即为所求。

(6) 对每一个分组进行试算, 即可得到所要求的设计洪水过程线。

如上计算中, 假设放大系数分组端点在两控制时段起、止的中点时刻, 当然也可以选择其他的初始值, 分组端点的初始值也存在进行多种比较的必要。这是因为按如上方法计算的放大系数分组端点处仍然可能存在突变, 只不过端点不一定在洪量控制时段衔接处而已。这与放大系数分组端点的选取有关。当放大的设计洪水过程线存在问题时, 可重新选择端点进行放大, 以灵活调整放大结果。

由于Kx需要试算, 所以有可能会出现找不到一个合适的Kx。方程f (Kx) =W6h-Wx为单调递减, 如Kx=0时, f (Kx) <0, 则方程无根。这与典型洪水过程有关, 也与放大系数分组端点的选取有关。当遇到这种情况时, 可通过改变放大系数分组端点来重新进行放大计算。如仍无法得到计算结果, 则应检查典型洪水与设计洪水成果的合理性。

2应用实例

为了进行比较, 应用某小流域实测洪水过程线及设计值, 分别应用直接法与平滑系数试算法进行放大。设计值见表2。

应用直接法和平滑系数试算法分别放大洪水过程, 结果见表3。从表中可见, 用直接法放大的设计洪水过程线在第14、15时刻的时段衔接处, 发生了跳跃问题;而用平滑系数试算法放大的设计洪水过程线比较平滑, 与典型过程线起伏一致, 在第14、15时刻的时段衔接处, 没有发生跳跃问题。放大的设计洪水过程线比较见图4。

3结语

(1) 用平滑系数法放大得到的设计洪水过程线, 在时段衔接处平滑过渡, 能较好地反映典型洪水过程的特性。但以直接法为比较对象, 平滑系数法放大的过程线在洪峰前后时段的流量可能偏大或偏小, 对水库调洪结果可能产生影响, 因此在使用中应注意检查设计洪水过程线的合理性。

(2) 用平滑系数法放大多个频率的设计洪水过程线容易产生不同频率洪水过程线的交叉现象, 因此, 在计算之后必须进行检查, 如存在交叉, 可通过适当修改某一设计频率某一时段的放大系数分组端点来进行调整。

参考文献

大洪水算法篇4

设计洪水过程线是防洪规划和防洪工程设计的基本依据。由于传统的分时段同频率放大法, 需徒手修均洪水过程, 任意性较大, 而且典型的模式会被削弱, 影响洪水的峰量关系。因此, 一些学者提出基于现代优化技术自动放大洪水过程的方法, 如基于遗传算法、模拟退火算法的设计洪水过程线推求[1,2]。然而, 遗传算法与选取的交叉、变异概率关系很大, 易早熟, 而且对于求解等式约束的优化问题效率不高, 结果不甚理想。模拟退火算法对整个搜索空间的状况了解不多, 不便于使搜索过程进入最有希望的搜索区域, 从而使得模拟退火算法的运算效率不高。

粒子群优化算法 (PSO) 是一种源于对鸟群捕食行为的研究而发明的进化计算技术, 最先由Eberhart博士和Kennedy博士与1995年提出[3,4]。该算法具有计算简便, 收敛速度快等优点, 但是在处理高维复杂优化问题时, 也存在易早熟、易停滞在局部极值点的不足。目前, 国内外学者提出了许多改进方法:如基于模拟退火的粒子群算法、基于灰色关联度的粒子群算法、基于免疫的粒子群算法, 以及基于混沌的粒子群算法等等[5,6,7]。这些方法是在基本粒子群算法的基础上, 借鉴其他优化方法的优点, 综合而成新的改进算法, 以期提高全局寻优的能力。但是, 这些处理将会大大增加了算法本身的复杂性, 影响了计算速度。本文根据惯性权值对粒子群算法优化性能影响的规律, 提出自适应随机惯性权 (Adaptive Random Inertia Weight, ARIW) 策略, 并在此基础上建立洪水过程线的放大模型, 以期以简便的方法来提高粒子群算法全局寻优的精度和速度, 从而在满足洪峰洪量约束的条件下推求出满意的设计洪水过程线。

1基本粒子群优化算法

粒子群算法的基本思想是[8]:优化问题的每一个解被称为一个粒子。定义一个适应度函数来衡量每个粒子解的优越程度。每个粒子根据自己和其他粒子的“飞行经验”群游, 从而达到从全空间搜索最优解的目的。

每个粒子在解空间中同时向两个点接近, 第一个点是整个粒子群中所有粒子在历代搜索过程中所达到的最优解, 被称为全局最优解;另一个点则是每个粒子在历代搜索过程中自身所达到的最优解, 这个解被称为个体最优解。每个粒子在n维空间中的一个点, 用Xi= (xi1, xi2, …, xin) 表示第i个粒子, 第i个粒子的个体最优解表示为XPi= (xpi1, xpi2, …, xpin) , 其所对应的个体最优值为Pi;全局最优解表示为XG= (xg1, xg2, …, xgn) , 其所对应的全局最优值为G;Xi的第k次迭代的速度表示为V $_{i}^{k}$ = (v $_{i 1}^{k}$ , v $_{i 2}^{k}$ , …, v $_{i n}^{k}$ ) , 其计算公式如下:

$\begin{array}{l} v_{i d}^{k + 1} = w v_{i d}^{k} + c_{1} r_{1} (x p_{i d}^{k} - x_{i d}^{k}) + c_{2} r_{2} (x g_{d}^{k} - x_{i d}^{k}) \\ x_{i d}^{k + 1} = x_{i d}^{k} + v_{i d}^{k + 1} (1) \\ (i = 1, 2, \dots, m; d = 1, 2, \dots, n) \end{array}$

式中:m为粒子群中粒子的个数;n为解向量的维数;c1, c2分别为两个正常数, 通常取2.0;r1, r2为2个独立的、介于[0, 1]的随机数;w为惯性权值, 调整其大小可以改变搜索能力的强弱。

为使粒子速度不致过大, 可设定速度上限vmax, 当|vid|>vmax时, 取vid=vmax。

粒子群优化算法的步骤如下:

步骤1 随机给出n维空间初始化粒子向量的粒子X $_{i}^{0}$ 和速度V $_{i}^{0}$ , 设定迭代次数。

步骤2 计算每个粒子在当前状态下的适应度函数值yi, 本文以目标函数作为适应度函数。

步骤3 将步骤2中计算的适应度函数值yi与自身的最优值Pi进行比较, 如果yi优于Pi, 则用新的适应度函数值代替前一轮的自身最优值, 用相应新粒子代替原来的粒子, 得到此状态下的每个粒子的个体最优解XPi。

步骤4 将yi中的最优值y*i与全局最优值G进行比较, 如果y*i优于G, 则用y*i代替前一轮的全局最优值, 用相应新粒子代替原来的粒子, 得到此状态下的粒子群的全局最优解XG。

步骤5 利用公式 (1) 将粒子进行移动, 从而产生新的粒子群, 重复步骤2至步骤5, 直至完成设定的迭代次数或满足事先给定的精度要求为止。

对于公式 (1) , Shi Y 建议采用线性递减权 (Linearly Decreasing Weight, LDW) 策略[9,10], 即:

$w^{k} = (w_{i n i} - w_{e n d}) (Κ_{\max} - k) / Κ_{\max} + w_{e n d} (2)$

式中:k为当前进化代数;Kmax为最大进化代数;wini为初始惯性权值;wend为进化至最大代数时的惯性权值。

试验表明权值w将影响PSO的全局与局部搜索能力, w值较大, 全局搜优能力强, 局部搜优能力弱, 反之, 则局部搜优能力增强, 而全局搜优能力减弱。线性递减权策略迭代初期局部搜索能力较弱, 即使初始粒子已接近全局最优点, 也往往错过, 而在迭代后期, 则因全局搜索能力变弱, 而易陷入局部极值[11]。针对此问题, 本文提出基于自适应随机惯性权的粒子群算法, 以期提高PSO算法的全局搜优的性能和效率。

2自适应随机惯性权粒子群算法

2.1自适应随机惯性权策略

基于线性递减权策略的权值变化较为单一, 对搜索能力的调节也就有限, 因此在实际过程中未必能适应复杂的多峰值的情况。本文提出的自适应随机惯性权策略, 按照某一概率分布为每一代粒子群中的各个粒子随机选择惯性权值, 并随进化代数调整概率分布函数。考虑在工程中使用时的方便、简单, 本文使用三角形分布作为随机惯性权值的概率密度函数的形式, 具体做法如下。

利用公式 (2) 计算出wk值, k=0, 1, 2, …, Kmax-1, 以点 $(w_{i n i}, 0), (w_{e n d}, 0), (w^{k}, \frac{2}{w_{i n i} - w_{e n d})}$ 为顶点的三角形为第k代随机惯性权的概率密度函数形式, 三角形的面积为1, 当k=0时, 为直角三角形, 其他为斜三角形, 如图1所示。

利用概率密度函数推求概率分布函数, 经计算, 当k=0时, 分布函数F0 (x) 如下式所示:

$\begin{array}{l} F_{0} (x) = \\ {\begin{cases} 0 x \leq w_{e n d} \\ \frac{1}{(w_{i n i} - w_{e n d})^{2}} x^{2} - \frac{2 w_{e n d}}{(w_{i n i} - w_{e n d})^{2}} x + \\ \frac{w_{e n d}^{2}}{(w_{i n i} - w_{e n d})^{2}} w_{e n d} < x \leq w_{i n i} \\ 1 x > w_{i n i} \end{cases} (3) \end{array}$

当k>0时, 分布函数Fk (x) 如下式所示:

$\begin{array}{l} F_{k} (x) = \\ {\begin{cases} 0 x \leq w_{e n d} \\ \frac{1}{(w^{k} - w_{e n d}) (w_{i n i} - w_{e n d})} x^{2} - \frac{2 w_{e n d}}{(w^{k} - w_{e n d}) (w_{i n i} - w_{e n d})} x + \\ \frac{w_{e n d}^{2}}{(w^{k} - w_{e n d}) (w_{i n i} - w_{e n d})} w_{e n d} < x \leq w_{i n i} \\ - \frac{1}{(w_{i n i} - w^{k}) (w_{i n i} - w_{e n d})} x^{2} + \frac{2 w_{i n i}}{(w_{i n i} - w^{k}) (w_{i n i} - w_{e n d})} x - \\ \frac{w_{i n i} w_{e n d} + (w_{i n i} - w_{e n d}) w^{k}}{(w_{i n i} - w^{k}) (w_{i n i} - w_{e n d})} w^{k} < x \leq w_{i n i} \\ 1 x > w_{i n i} \end{cases} (4) \end{array}$

由分布函数计算出相应的反函数, 结果如式 (5) 、式 (6) 所示:

当k=0时

$F_{0}^{- 1} (x) = w_{e n d} + (w_{i n i} - w_{e n d}) \sqrt{X} 0 \leq x \leq 1 (5)$

当k>0时

$F_{k}^{- 1} (x) = {\begin{cases} w_{e n d} + \sqrt{(w_{i n i} - w_{e n d}) x (w^{k} - w_{e n d})} \\ 0 \leq x \leq (w^{k} - w_{e n d}) / (w_{i n i} - w_{e n d}) \\ w_{i n i} - \sqrt{(w_{i n i} - w_{e n d}) (1 - x) (w_{i n i} - w^{k})} \\ (w^{k} - w_{e n d}) / (w_{i n i} - w_{e n d}) \leq x \leq 1 \end{cases} (6)$

下面介绍一个定理。

定理1 若随机变量X的分布函数为FX (x) , 则随机变量函数U=FX (x) 为服从[0, 1]上均匀分布的随机变量。

证明:若U的分布函数为FU (u) , 则按分布函数的定义及其特性有:

$\begin{array}{l} F_{U} (u) = Ρ {U < u} = Ρ {F_{X} (X) < u} = Ρ {X < F_{X}^{- 1} (u)} \\ = F_{X} [F_{X}^{- 1} (u)] = u 0 \leq u \leq 1 \end{array}$

易知u<0, FU (u) =0;u>1, FU (u) =1, U为[0, 1]上均匀分布的随机变量。证毕。

由定理1可以得到

$X = F_{X}^{- 1} (U)$

于是, 若获得了U的随机数u1, u2, …, um, 代入公式:

$x_{i} = F_{X}^{- 1} (u_{i}) i = 1, 2, \dots, m (7)$

可求得X的随机数x1, x2, …, xm。

因此, 基于自适应随机惯性权的粒子群算法只需在基本算法的步骤5之前增加一步:随机产生m个[0, 1]区间均匀分布的随机数, 分别代入式 (5) 或式 (6) 得到此状态下各个粒子的惯性权值。

综上所述, 可以看出自适应随机惯性权策略有以下特点。

①随机地为每个粒子选取惯性权值, 使得在迭代初期也可能获得较小的权值, 从而增强局部搜优的能力, 而在迭代后期也可能获得较大的权值, 减少陷入局部极小点的机会。

②按照三角形的概率密度随机产生惯性权值, 在迭代初期随机惯性权的期望值较大, 而迭代后期期望值较小, 即在初期保持较强的全局搜索能力, 而后期保持较强的局部搜索能力, 概率密度函数随迭代次数相应地变化, 灵活地调整全局搜索与局部搜索的能力。

③粒子群中的每个粒子均有各自的惯性权值, 这将有助于保持种群的多样性。

④方法简单, 应用方便, 只需随机产生m个[0, 1]区间均匀分布的随机数, 分别代入式 (5) 或式 (6) 即可。

2.2性能测试

本文采用经典测试函数 Rastrigin函数, 对LDW和ARIW 2种PSO算法的寻优性能进行测试, 并作比较。

Rastrigin函数是一个多峰函数, 有很多正弦凸起的局部极小点, 各变量相互独立。它的全局极小点在X*= (0, 0, …, 0) 处, f (X*) =0。

$\begin{array}{l} f (X) = \sum_{d = 1}^{n} [x_{d}^{2} - 10 \cos (2 π x_{d}) + 10] \\ - 5.12 < x_{d} < 5.12 (8) \end{array}$

对此测试函数采取10维进行测试, 2种算法种群粒子数取30, 速度上限Vmax取为10, 取c1=c2=2.0, wini=0.9, wend=0.4。

测试以2种方式进行, 先给定寻优应达到的精度ε, 在|F-F*|<ε时, 比较2种算法所需的进化代数, F为算法搜优达到的适应值, F*为全局极小值。本文分别取ε=1, 5, 并设定最大的迭代次数Kmax=10 000, 对2种算法分别进行100次试验, 比较它们所需进化代数的平均值。其次给定最大进化代数, 比较2种算法寻优的精度, 即与全局极小值的误差。本文分别取最大进化代数为1 000和2 000次, 并对2种算法分别进行100次试验, 比较它们误差的平均值。

将给定的参数值代入式 (3) ～ (6) 计算得出随机惯性权的分布函数及其反函数, 利用LDW和ARIW 2种方法进行计算, 结果如表1和表2所示。

从表1、表2中可以得出以下结论。

①LDW和ARIW都是随着迭代次数的变化自动调整惯性权值, 有较强的全局搜优能力, 因此, 对多峰函数的寻优效果是令人满意的。

②无论哪种方式的比较ARIW均优于LDW。这是由于ARIW比LDW在惯性权值的选择上更加灵活, 能够更有效地调节全局搜索和局部搜索能力。特别是当控制精度不是很高时, ARIW所需迭代的次数大大小于LDW所需迭代的次数, 充分体现出ARIW的空间搜优能力。

③在2 000次的ARIW试验中, 选最优一次试验结果为最终结果, 则Rastrigin函数的最优解和最优值分别为:X*= (3.586×10-10, 4.732×10-11, -4.675×10-10, -4.321×10-10, -5.794×10-10, 3.635×10-11, 4.299×10-10, 9.017×10-11, 4.118×10-10, 4.711×10-11) 和f (X*) =0.000 0。结果是令人满意的, 说明ARIW很适合于求解多峰函数优化问题。

3洪水过程线放大优化模型

要满足设计洪水过程线与典型洪水过程线尽量相似的要求, 就必须使2个过程不同时段的流量斜率基本相同。同时, 要求放大后的洪峰流量与设计标准一致, 不同控制时段的洪水总量与设计标准一致。按照这些要求, 建立了如下模型:

$\begin{array}{l} m i n f = \sum_{i = 2}^{n u m} | \frac{Q_{p} (i) - Q_{p} (i - 1)}{Δ t} - \frac{Q_{d} (i) - Q_{d} (i - 1)}{Δ t} | \\ {\begin{cases} Q_{p}^{\max} = Q_{m p} \\ W_{1} = \int_{t_{1 s}}^{t_{1 e}} Q_{p} d t = W_{1 p} \\ W_{3} = \int_{t_{3 s}}^{t_{3 e}} Q_{p} d t = W_{3 p} \end{cases} (9) \end{array}$

式中:Qmp, W1p, W3p分别为设计标准对应的洪峰流量和最大的1日、3日洪量 (时段可以根据需要选定, 本文以1日、3日时段为例) ;Q $_{p}^{\max}$ , W1, W3分别为所推求的设计洪水过程的洪峰流量和最大的1日、3日洪量;t1s, t1e分别为最大1日洪量的开始时刻和结束时刻;t3s, t3e分别为最大3日洪量的开始时刻和结束时刻;num为洪水过程离散的个数。

采用罚函数的方法将各等式约束转化在目标函数中, 然后利用自适应随机惯性权粒子群算法进行求解。

4算例

本文以汉江上游石泉水库设计洪水计算为例。石泉水库设计标准为100年一遇。典型洪水选用1958年典型3日洪水过程, 其洪水特征值和根据频率分析结果得出的百年一遇洪水特征值如表3所示。

整个典型洪水过程由离散的19个点组成, 离散时段为4小时, 第7个点与第13个点之间的面积为最大的1日洪量。设计洪水过程线上的点限制在对应的典型洪水过程线上的点与设计洪水洪峰流量之间。由于离散时段相等, 因此目标函数可变为:

$m i n f = \sum_{i = 2}^{19} | [Q_{p} (i) - Q_{p} (i - 1)] - [Q_{d} (i) - Q_{d} (i - 1)] |$

为了计算方便, 将各点的值缩小到1/1 000, 设定粒子最大速度为1, 群体个数定为30, 进化代数为100, 利用自适应随机惯性权粒子群算法进行计算, 并同遗传算法、模拟退火算法、基本粒子群算法以及手工修均法进行比较, 计算结果还原后见表4。

由计算过程和计算结果可以得到:遗传算法在变量较多, 且有等式约束条件下, 其寻优结果和对约束的满足程度较差;模拟退火算法求解结果略优于遗传算法, 但与粒子群算法的计算结果还有一定差距;手工修匀法任意性较大, 不易找出满意的洪水过程;改进的粒子群算法在原算法的基础上简单地增加两步运算, 却大大提高了寻优的效果, 不仅能够很好地满足约束条件而且寻优的结果也是最令人满意的。另外, 该方法的计算要比遗传算法和模拟退火算法简单, 并且寻优的速度较快。因此, 基于自适应随机惯性权粒子群算法的洪水过程线放大模型与传统模型相比, 有更高的全局寻优精度和更快的计算速度, 能够在满足洪峰洪量约束的条件下推求出满意的设计洪水过程线。设计洪水过程线如图2所示。

从图2中可以看到除了点15与16之间的两线段斜率相差较大外, 其他各段均近似平行。设计洪水过程线既要保持设计洪峰值, 又要保持时段的洪量值, 必然是以典型洪水模式的削弱为代价。如果点15的值从当前的7966提高到区间[8952, 9454], 此时点14与16之间的线段斜率相差最小, 但最大3日洪量将由30.2变为[30.3, 30.4], 即要保持典型洪水过程模式就要削弱等式约束。但是, 与其他方法相比, 本文提出的改进粒子群算法能在较好的满足各等式约束条件下保持典型洪水过程模式。

5结语

粒子群算法从生物群体的社会行为中得到启示, 是一种新颖的智能计算优化方法, 和其他优化算法相比, 粒子群算法不仅具有全局寻优能力, 收敛速度快的优点, 而且编程简单, 使用方便, 但鉴于其发展历史尚短, 在理论基础与应用推广上都还存在一些问题, 有待进一步改进和完善。本文提出了基于自适应随机惯性权的粒子群算法, 推导出了权值选择的计算公式。在进化过程中, 按某一概率分布为每个粒子随机选取惯性权值, 并随进化的代数自适应地调整随机惯性权的概率分布, 以此有效地调整算法的全局搜索与局部搜索能力。

在此基础上, 本文建立了洪水过程放大的优化模型, 使用改进的粒子群算法对模型进行求解并同传统的方法进行了详细地比较, 实例表明基于自适应随机惯性权粒子群算法的洪水过程放大模型不但可以较好的满足洪峰洪量的约束, 而且能够较好的保持典型洪水过程的模式, 使用简单, 易于推广应用。

摘要：针对基本粒子群算法在处理高维复杂问题时易陷入局部极值点的不足, 提出自适应随机惯性权的粒子群优化算法, 并基于此算法建立起洪水过程的放大模型。在进化过程中, 为粒子群中的各个粒子随机选取惯性权值, 并随进化代数自适应地调整随机惯性权值的概率分布, 提高了算法全局寻优的性能。实例表明:该模型不但可以有效保持典型洪水的模式, 避免手工修均的任意性, 而且可以很好地满足洪峰洪量的约束要求, 有较高的精度。

关键词：设计洪水,粒子群,随机惯性权

参考文献

[1]许叶新.遗传算法在设计洪水过程线推求中的应用[J].甘肃科学学报, 2003, 15 (3) :41-45.

[2]席秋义, 谢小平, 黄强, 等.基于遗传算法和并行组合模拟退火算法的洪水过程缩放模型研究[J].水力发电学报, 2006, 25 (1) :108-112.

[3]Kennedy J, Eberhart R C.Particle swarmopti mization[A].Pro-ceedings of IEEE International Conference on Neural Networks[C].Piscataway, NJ:IEEE Press, 1995:1 942-1 948.

[4]Eberhart R C, Kennedy J.Anewopti mizer using particle swarmtheory[A].Proceedings of the sixth International Symposium onMicro Machine and Human Science[C].Nagoya, Japan:IEEEPress, 1995:39-43.

[5]于繁华, 刘寒冰, 戴金波.求解多目标优化问题的灰色粒子群算法[J].计算机应用, 2006, 26 (12) :2 950-2 952.

[6]高尚, 杨静宇, 吴小俊, 等.基于模拟退火算法思想的粒子群优化算法[J].计算机应用与软件, 2005, 22 (1) :103-104.

[7]王希云, 刘瑞芳.混沌粒子群算法及其在桁架结构优化设计中的应用[J].太原科技大学学报, 2006, 27 (6) :478-480.

[8]龙云, 王建全.基于粒子群游算法的同步发电机参数辨识[J].大机电技术, 2003, 32 (1) :8-11.

[9]Shi Y, Eberhart R C.A modified particle swarm opti mizer[A].Proceedings of the IEEE Congress on Evolutionary Computation[C].Piscataway, NJ:IEEE Press, 1998:303-308.

[10]Shi Y, Eberhart R C.Empirical study of particle swarmopti mi-zation[A].Proceedings of the IEEE Congress on EvolutionaryComputation[C].Piscataway, NJ:IEEE Press, 1999:1 945-1 950.

【大洪水算法】推荐阅读：

暴雨洪水05-12

洪水风险05-21

洪水特性06-16

溃坝洪水07-13

洪水评价07-27

特大洪水08-13

洪水特征09-23

洪水的古诗08-28

实时洪水预报06-25

洪水控制工程07-02

>> 查看更多相关文档