遗传算法在厂群规划中的应用.pdf

《遗传算法在厂群规划中的应用.pdf》由会员分享，可在线阅读，更多相关《遗传算法在厂群规划中的应用.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第!卷第!期!#$年 月水资源保护%&()(*+,)-(*.)+(-/+01234!024!5674!#$作者简介：钟雨倩（89:#），女，重庆人，硕士研究生，研究方向为环境信息系统。(;2?ABCB2DE4F2=F&3K27=D36L 程序编写了解决此问题的遗传算法，对模拟的实例进行了计算，结果证明，遗传算法应用于此类问题中是可行的。关键词：遗传算法；水污染控制系统规划；厂群规划；最优规划中图分类号：+8I84!G文献标识码：&文章编号：8#H!G9（!#$）#!#!I!#H!#$%&$()(*+,),$%&#+(-$./$)#&)$)+(*0,1&+,#&)023456 789:$&)8，

2、;4=,)9*,)+!（8!#$%&%()*+)#%,&#-,.,/0$,#0 1#2&/)#3(#%，45&#($(67,0(38)*97&(#7($，45(#:0 G8#H8，45&#,；!975);)*6/75&%(7%/(,#0 1#2&/)#3(#%，9&75,#0-&%：&N72L3AB P=D=?6 7AK=2?P6B NE O27P67Q，6?Q KA?A=F 63K27=DDA BEQ4&?=N72RAQ DA 76Q=2?63 N36?=?K B 6?Q J&6NN3=F6L3A 2DA D DA BENN27 2O J&+（JA?A=F&3K27=DDA F2=?K N7

3、2FABB 2O J&O27B23R=?K DA N72L3A P6B N72K76D 5636L4 S=?633，6 F6BA BEQ N72RAB D6 DA 6NN3=F6=2?2O J&=B OA6B=L3A4?,1(-A0：KA?A=F 63K27=DAA7 N233E=2?F2?723；N36?=?K 2O BAP6KA N36?；2N=63 N36?=?K水污染控制规划中的最优规划问题可以分为排放口最优处理（水质规划）、最优化均匀处理（厂群规划）、区域最优化处理（区域处理最优规划）三种8。厂群规划和区域处理最优规划问题中的应用研究一直比较匮乏，目前尚未有比较成熟的求解手段!。在水

4、污染控制系统规划中，通常讨论的水质规划、厂群规划及区域处理最优规划问题均考虑的是流域范围内污水传输的情况。在此情况下，污水处理厂通常沿河修建，仅相邻的排污点才能实现污水相互传输，即各排污点的污水既可传输到上游的相邻污水点，也可传输到下游的相邻污水点。传统的厂群规划实际上是在沿河两岸的排污点中寻找合适的位置修建污水处理厂，却不考虑水质的约束和各污水处理厂的处理效率，显然失去了实际意义。现代优化算法 遗传算法，提供了一种求解复杂系统优化问题的通用框架，对问题的种类有很强的鲁棒性，在诸如函数优化、组合优化、生产调度、自动控制、图像处理等的众多领域得到了广泛应用，并且在一些用传统优化方法难以求解的非线

5、性、多模型、多变量、多目标的函数优化问题上，具有突出优势。本文以遗传算法为研究方法，将其应用于区域范围内的厂群规划问题上，进行了初步尝试和探索。B数学模型B4B基本模型传统厂群规划的基本模型8是一个概括笼统的模型，同样适用于本文讨论的厂群规划问题。目标费用!#&8?8&?!A!#&8!#B 8?&B?H;&B?!C 8?HC 8（8）I!节点流量平衡方程!#!$%&!%(!$&!%(&（#），%&!，#，$，!，%，%#式中：!为各点排放污水量；)%为任意两排污点的距离；为污水处理规模；%，%为污水传输量。!*改进的厂群规划模型为了使得本文所讨论的厂群规划问题较为接近实际情况，并适当地简化求解

6、过程，在基本模型基础上作进一步改进。!*!增加约束条件基本数学模型没有考虑实际情况中的约束，不能满足求解污水处理厂厂群规划问题的需要。因此在基础数学模型上增加一些新的约束，以保证求解结果更有实用性：!污水处理厂能力约束，即污水处理厂能够处理的最大污水量，设为+。$+修建的污水传输管线也有一个输水能力约束，设,为管线所能承载的最大输水量。$%$,#水只能单向流动，即若有 点向%点传输污水，%点就不可能同时也向 点传输污水。$“全部处理或全不处理策略”!。对任意排污点来说，它本身的污水加上其他排污点传输来的污水，只存在两种可能的选择：全部就地处理或者全部传输到其他排污点处理。，%&!，#，$若%则

7、必有%&!*减少变量数目在初步改进的模型中，、%、%（，%$!，#，$）均为未知变量，未知变量个数共$#个。用一般优化算法求解往往会造成“维数灾”。在进行模型计算前，需要对模型进行进一步优化，尽可能地减少变量数目。根据水的单向流动约束，令-%$%，排污点 向%点传输污水%，排污点%向 点传输污水，排污点 与%之间无污水传输（&）模型中的决策变量仅为-%（%）。为了便于标记，将-%仍然用%来标记，但此时的%取值范围为整个实数空间，个数为$（$%!）.#，模型中的变量数目大大减少了。另外，随着变量的重新定义，原模型中表达式也相应发生了变化（数学变化过程略）。式（!）变为()*/&!$&!0!0#!

8、$%&!1%0&%0+)%（+）式（#）变为&!(!$&!%#!$%&!()%（,）!*#最终的改进模型经过以上变量%的重新定义，原模型中的目标函数、约束条件等均发生相应的数学变形。另外还要考虑一个限制条件，称之为分水约束。在实际情况中，同一污水点的污水一般不可能分别传输给几个污水处理厂处理。换言之，每个排污点可以接受其他几个排污点的污水，但是只能传输给一个排污点或者不传输。用数学语言来描述各污水排放点和污水传输管线的关系，即整个系统是一个以$个污水排放点为顶点，污水传输管线（污水有传输方向）为边的有向图。若要系统满足分水约束，即是有向图的每个顶点的出度仅能为 或!。定义矩阵!$-$为各顶点出

9、度矩阵，矩阵中的各元素对应表示各污水点有无传输污水给其他的点2%&!，若%3，其他（.）则分水约束可表示为!$%&!2%$!（/）经过上述的数学处理，得到最终的改进模型。目标函数()*/&!$&!0!0#!$%&!1%0&%0+)%（0）约束条件&!(!$&!%#!$%&!()%（1）%$,$+若%，则%$，即2%&，%!$%&!2%$!其中2%&!，若%3，其他，%&!，#，$)%，!#遗传算法和模型求解*!求解步骤本文用遗传算法求解的主要步骤如图!所示，这也是遗传算法的常规计算流程&。*!*!编码和初始种群的生成本文采用实数编码的遗传算法进行厂群规划问.#图!基本遗传算法计算过程流程图题的

10、求解。如上文所述，模型中的决策变量仅为!#（!#），数目为$（$#）%$。用$%$的上三角阵!来表示各排污点之间的污水传输量!#（!#），定义!&!#$!#$&!&!$#，$&（#）模型中!#的正负表示污水传输的方向，此上三角矩阵包括了所有排放点之间污水传输的情况。对角线元素!均为&，表示各排污点自身不进行污水传输。本文实数编码的遗传算法中，生成的初始种群中个体数目（种群规模）设为(。由于决策变量!#的数目为$（$#）%$个，且每个!#均满足约束条件!#)，因此种群中每个个体（解变量编码）是$（$#）%$维向量，向量中的各元素是 )，)上随机产生的实数。初始种群中(个个体对应了(组初始解。遗传

11、算法从这(个初始点开始，进行遗传进化运算，直到计算出符合条件的最优解为止。*!*适应度值的评估检测计算(（+）中每个染色体个体的适应度值。适应度函数的定义一般与具体求解的问题有关。在本文中，对于约束条件!#)，已经在产生初始种群时加以约束，其余的约束条件将利用惩罚策略)把其归并到目标函数上去，使本文中的厂群规划问题转化为无约束问题。设惩罚因子,#*&，,$*&，-为一足够大的正数。含有惩罚项的新的目标函数为.（!#）&-，若&#，$，$中存在任意一个/$（）0&-，若&#，$，$中存在任意一个#$#
#2#3 4#$&#/#（）54 6，#&#，$，否则（#$）其中/#（）+7 !$&（#

12、,）/$（）&!$&（#)）5&，若/（）$&,#，否则（#-）6&#$#
#,$，若!%&，若!&（#.）由于本文求解的是最小化问题，令.+（.（8）+.（8），即最终得到适应度函数.+（.（!#）&.（!#）（#/）一般情况下，适应度函数设计应该满足非负要求，以保证选择算子中的概率选择有意义。*!*#算法终止条件若满足算法终止条件输出最优解，否则执行下列选择、交叉、变异运算。*!*$遗传算子针对厂群规划问题，本文选择了锦标赛选择算子、算术交叉算子、非均匀变异算子-。*算例假设有一个水污染控制系统可分为.个小区（位置及编号参见图$），每个小区都可设一座潜在的污水处理厂，各小区的污水可以自

13、己处理，也可以传输到其他小区的污水处理厂进行处理。需以费用最小为目标，在满足约束条件情况下，规划出水污染控制系统中的污水处理厂位置、规模，及各小区之间污水传输的情况（包括污水传输管线的布局及污水流向）。图 各小区（污水处理厂）位置分布示意图在 01(2（3454267 890(:62;(?）的支持下，用程序编写解决厂群规划问题的遗传算法。在求解具体问题时，输入具体的参数设置和相关数据，就可进行求解。此例中，设定群体大小(+&，迭代次数为#&次。适应度函数中，一足够大的正数-取#&。经过多次试验，最终选取遗传算法中的惩罚因子,#+&，,$+.&。遗传算法程序运算结束得到最优解及遗传进化过程中解的

14、变化和种群平均值变化图（图,），遗传运算运行时间为 ABC。遗传计算运行#&代后，得到充分进化后的最优解及其对应的适应度函数，最优解所对应的适应度函数值为/$!#$%&(%，最小费用值是取其相反数的结果。图!解的变化和种群平均值变化#整理程序运算结果，得到各小区的污水处理规模（)*+,）：!#-.!(!*(!%(#.!/(#%(!.(#$*$#各小区之间的污水传输矩阵：!(#(#/#(#-(!0!(#/，小区 的全部污水传输到小区，传输量为(#/)*+,；!*0!(#-，小区*的全部污水传输到小区，传输量为(#-)*+,；其余小区之间不进行污水传输。%#污水处理和传输的最小费用：)12$#$%

15、(%元相应的污水处理厂修建位置以及各排污点之间的污水传输管线布局平面图，如图%。图中，黑色标识的点为污水处理厂的修建位置，有向线段表示污水管线的布局及污水传输的方向。图&传输管线布局示意图3!结果分析算例研究中，模型的变量数目为&（&!）即/个，变量数目较大，约束条件较多且不规则。理论上，污水处理厂厂群规划问题可以用混合整数规划法和试探法进行求解，.。但实际求解中，这两种方法效果均不理想。试探法是以搜索尽可能多的组合方案情况为代价的，虽然效率高于随机搜索法，但此方法仍然存在计算量大、花费时间多等问题。将其用在比较复杂的污水处理厂厂群规划问题中时不一定能取得最优解。线性混合整数规划（4567）对

16、于实例研究中这种解数目规模比较大，约束条件较为复杂的问题，求解非常困难且线性化误差太大。厂群规划的线性混合整数规划解变量数目为.&-，当污水处理厂被选位置增多时，解变量的数目急剧增长。在这种情况下，混合整数规划模型失去了实际意义。实例中，.个排污点均可设立污水处理厂，任意 个排污点之间均可进行污水传输，组合情况非常多。本文利用遗传算法，在较短时间内得到了该模拟的例子中污水处理厂的修建位置、规模及污水管线布局的最优化结果。理论上，经过充分进化后，遗传算法是可以以概率“”的方式寻求问题的最优解的8。通过解的变化和种群平均值变化图对照种群进化变化表可知，在遗传进化运算中，从第/%$代后解的进化过程趋

17、于平缓；到达第$(代左右，解的适应度值不再发生变化。(代后，本文所得到的是进化完全的解值。因此，用遗传算法求解该最优化问题是有效可行的。从另一个角度来说，此问题可以尝试使用其他非线性规划方法进行求解以作对比分析，以说明遗传算法求解的最优化效果。具体用何种非线性数学方法，能够求出模型解，仍需要进一步研究和讨论。!结论本文讨论的厂群规划问题考虑到了污水传输管线布局中允许各个排污点之间的污水任意传输的情况，是一种较为复杂的厂群规划问题，更加适用于区域范围内的厂群规划。本文提出了改进的厂群规划数学模型，大大减少了变量数目，简化了运算；增加了约束条件，使厂群规划模型更有实际意义。本文针对改进的厂群规划模

18、型，进行了实数编码的遗传算法求解，得到了模型的最优解，结果说明了遗传算法求解此类问题的可行性。本文将遗传算法应用到厂群规划问题上进行了初步尝试，更为广泛和深入的应用有待进一步研究和探讨。参考文献：傅国伟，程声通3水污染控制系统规划 5 3北京：清华大学出版社，$8/3（下转第*页）8变（用!表示）；前者一般较小，后者可能较大，一般情况下!#。也就是说气候变化下相对湿度的改变量应包含!和!#两部分，即!#!。而前面的计算中采用的是!#。从式（$）中可见，气温升高使水面蒸发量增大，相对湿度加大使水面蒸发量减小，气候变化对水面蒸发量影响值为两者之和，由此可知，用!$和!#计算的!%，远大于由!$和!

19、#!计算的!%$，甚至出现!%!&、!%$&的相反结果。如前面计算的!%即为!%，得到的即是!%!%!&的结果；如果以!$&()*与!%&或$%(&*与!$(%&，或!$%()*与!+&计算!%，得到的即是!%!%$&的结果。表明如果能综合考虑气候变化中气温升高、降水增减及相对湿度加大（指温室效应引起的相对湿度的加大）对水面蒸发的共同影响，即由!$和!#!(计算气候变化造成的水面蒸发量的增量!%，则得到的!%不应是正值，而是与实测资料统计得出的水面蒸发量递减一致的负值（即!%&）。这一结论在鄱阳湖区和江苏省已得到了实测资料的检验。根据以上几点认识，可以得出以下一个重要的推论：随着气候变化的继续

20、，水面蒸发量递减趋势不仅在过去几十年一直持续存在，而且在今后仍会维持。这一推论对当前科学界普遍流行的“气候变化使水面蒸发加剧，水循环增强”的观点提出了质疑。事关重大，希望水文、水资源领域的专家和学者积极参与对此质疑的讨论与争论。从江苏省沿海地区（如海安、阜宁、盐城、大丰闸、遥望闸、石梁河水库等测站）地面,-&%实测年蒸发量%./%0$&年 较%.-%0%./&年 平 均 减 小%+.(-11 上看，海面蒸发量也呈减小趋势，这为作者提出上述质疑提供了一定的支持。但中国近海洋面与世界洋面蒸发的变化是否与此一致，还有待研究。以上仅为作者通过部分工作得到的结论，暂未得到大范围实测水文、气象资料的验证，

21、因此，对于水面蒸发量递减与气候变化之间究竟存在怎样的关系，不仅需要收集大范围实测水文、气象资料作全面的论证，更需要从理论上做深入的研究。!结语本文以鄱阳湖区为例，通过资料分析与模拟计算，提出了实测水面蒸发量递减与气候变化对水面蒸发影响两个问题，认为两者之间可能存在着必然关系，需要对其进行全面论证与深入研究。建议水文部门与气象部门合作，研制能直接给出相对湿度变化或水面蒸发量变化情景值的气候变化预测模型。同时，建议有关部门将全国各地近 2&年来水面蒸发量变化趋势及其空间分布规律分析追加为全国水资源综合规划中水资源评价的工作内容。此外，如果本文提出的结论与推论成立，则过去几十年在气候变化对江河径流影

22、响方面的研究成果需要进行全面校核与更改；气候变化对水循环影响方面的已成认识，也需要重新斟酌。参考文献：%张建云，章四龙，李岩3 水文科学面临的气候变化问题4 5 5张建云3中国水文科学与技术研究进展 全国水文学术讨论会论文集3南京：河海大学出版社，$&2：+%+3$闵骞3水面蒸发预测模型研究 4 5 5张建云3中国水文科学与技术研究进展 全国水文学术讨论会论文集3南京：河海大学出版社，$&2：6&66%+3+陈德亮，高歌3气候变化对长江流域汉江和赣江径流的影响 7 3湖泊科学，$&+，%)（增刊）：%&)%232万晓凌，马倩3江苏省蒸发能力特征分析 4 5 5黄河水利委员会水文局3全国水文水资

23、源科技信息成果论文集3郑州：黄河水利委员会，$&2：%-&%-23（收稿日期：$&)&/&%!编辑：高渭文）（上接第$/页）$蔡明，白丹3 遗传算法在水污染控制系统最优规划中的应用 7 3西安理工大学学报，$&$，%/（%）：)/-%3+云庆夏，黄光球，王站权3 遗传算法和遗传规划 一种搜索寻优技术 8 3北京：冶金工业出版社，%.6：+$)&32卢名高，刘庆吉3 最优化应用技术 8 3 北京：石油工业出版社，%.63)周明，孙树栋3 遗传算法原理及应用 8 3 北京：国防工业出版社，%.3-9:;?=，A:B;C3=DEDFGH IJKLMGFN1O GE MDIJ FG1DHLEFMLJ IPPJGDQ FL 1GEG1GRD FMIEOGDEF PLJJSFGLE TML1 SMUIEVIOFDVIFDM OWOFD1O 7 3 9IFDM DOLSMHD，%.，+（)）：%$-)%$6636程声通，陈毓龄3环境系统分析 8 3北京：高等教育出版社，%.&：%2+%2)3/张文修，梁怡3遗传算法的数学基础 8 3 西安：西安交通大学出版社，$&：.%$3（收稿日期：$&)&编辑：高渭文）+