利用改进的遗传算法优化设计管网改造项目
王兴畏，彭世尼，黄小美
(重庆大学 城市建设与环境工程学院，重庆，400030)
摘要：采用对遗传算法中的基本操作进行控制的思路，提出对传统遗传算法改进的方法，并且将其与城市燃气管网的水力计算相联系，以解决城市管网改造工程中存在的问题。同时，结合MATLAB语言对算法的基本操作加以说明，使优化算法更加直观，易于理解。通过对遗传算法基本过程的控制，有效地实现了水力计算的目的，管网的可靠性较以往手工计算或传统的遗传算法的结果有较大提高。利用改进的遗传算法能够实现对管网改造项目的优化设计，为设计研究带来便利且准确性提高。
关键词：管网改造项目；水力计算；遗传算法；基本操作；优化
中图分类号：TU996 文献标志码：A 文章编号：1672-7207(2012)S1-0310-04
Optimizing design of network reconstruction projects using improved genetic algorithm
WANG Xing-wei, PENG Shi-ni, HUANG Xiao-mei
(College of Urban Construction and Environmental Engineering, Chongqing University, Chongqing 400030, China)
Abstract: The ideas of improved traditional methods of genetic algorithm were put forward through the way of controlling the basic operations. In order to solve these project problems, the method was associated with the hydraulic calculation. Moreover, for the purpose of making the algorithm more intuitive and easy to be understood, the basic operations with MATLAB were illustrated. The improved genetic algorithm can achieve the optimal pipe network design in reconstruction projects, which is also convenience to design and research.
Key words: reconstruction projects; hydraulic calculation; genetic algorithm; basic operations; optimization
随着燃气事业的发展，已有的城市燃气管网已不能满足人民生活的需要，因此迫切需要在已有的燃气管网基础上进行改建或扩建。对于城市燃气管网系统改、扩建项目来说，目前主要存在两个方面的问题：一方面，城市燃气管网的需求规模不断扩大，急需对管网结构进行改造、新建，从节约投资的角度考虑，应尽量在保留原来管网的基础上进行扩建或改造；另一方面，由于城市化的发展，城市管网规模不断扩大，手工水力计算不仅耗时而且计算中出现的问题修正困难，特别是大型管网计算难度很大。因此，水力计算越来越重要。
近年来，应用系统分析方法，尤其是利用遗传算法解决燃气输配管网问题取得了一定成果[1]。针对改建、扩建管网项目的发展现状，本文作者尝试将遗传算法改进后引入到城市燃气管网的水力计算中以解决城市管网改建、扩建工程中存在的问题。
1 遗传算法原理
遗传算法是从20世纪60年代对自然和人工自适应系统的研究中发展而来。由Goldberg进行归纳总结，形成了遗传算法的基本框架[2]。
遗传算法根据不同的目标函数及一系列遗传操作对个体进行筛选，其实是一个迭代过程，反复将选择、交叉、变异操作作用于群体。这样周而复始，群体中个体适应度不断提高，直至满足一定限制条件。此时，群体中适应度最高的个体即为待优化参数的最优 解[3-4]。
遗传算法进行水力管网优化就是通过迭代和筛选，不断提高管段管径所形成的个体的适应度，形成的每个个体都是管段管径的数组，最终适应度最高的个体即为最优个体[5]。利用这种方法得到的最优个体其实就是管径的一组最优组合数据。由于适应度函数是经过燃气管网优化的目标函数转换后计算而来的，因此，最优个体对应的计算结果即是在满足管段流量和节点压力的情况下经济效益最高的。
2 针对管网改造项目改进的遗传算法
顾名思义，管网的改建是在已有管网的基础上，对其中某些管段的管径与走向进行优化，以满足整个管网的管段流量与节点压力。而管网的扩建即是在保留已有管网的基础上，通过增加新的管段的方法，来满足各用气点的需求，同时保证整个环网的安全稳定运行。在进行管网的改建与扩建的过程中，还要考虑管网整改后的经济效益。
2.1 针对管网改造项目的遗传算法操作原理
以前采用遗传算法进行管网优化时，一般管网信息都用二进制数字串来表达[6]。对于燃气管网来说，管网各管段的管径是用一个数字串来表达，因此，这个数字串就包含了管网的管径信息。例如，一个有5条管段的管网，管径分别为76，133，89，108和89 mm；如果用二进制编码方法，则该管网管径信息的编码为：
0000|0011|0001|0011|0001
如果采用实数编码方法，则为
76|133|89|108|89
从上面的例子可以看出：二进制编码既不自然又增添了麻烦，并且在以后的操作步骤中还需要将二进制数字串解码为真实管径的操作[7]。所以，采用实数编码方法，在实际的计算时较传统的遗传算法更加简便。
对原本已有的燃气管网进行改建、扩建时，考虑到施工的情况及全局经济效益的需求，应该在尽量减少对已有管网改变的基础上进行施工作业，并且要保证改建、扩建的管段与整个管网和谐运行，整个管网的压力与流量都满足规范要求。在遗传算法时，由于要进行选择、交叉和变异的基本操作，因此，在进行管网的改建与扩建时，就相当于已有的管段管径全部或大部分都是确定的，需要在此基础上增加或改变少量管段，最终使新建的管段与原有的管段形成的管网获得较大的经济效益。为了实现这一目标，就需要保证在使用遗传算法的时候，确定的管段的管径在经历了选择、交叉与变异的过程中，一直保持着原有管段的信息，每次个体适应度的计算都是由这些原有管段与新建管段组合的个体信息来进行量化评价。要实现上述目标，就要对传统的选择运算、交叉运算、变异运算等遗传算子的确定过程进行优化。
2.2 遗传算法过程
图1所示为遗传算法流程。
图1 遗传算法流程
Fig.1 Flow chart of genetic algorithms module
2.2.1 产生初始群体
利用传统的遗传算法产生初始群体时，对于有N条管段的管网系统，需要随机产生N个个体形成初始群体，每个个体就是由所有管段的管径按照一定顺序连接在一起的数字串，这个顺序就是管段的编号顺序。因此，不同的个体代表了不同的管段管径选择情况。而个体的产生方法是调用随机函数产生随机数，每个随机数对应着一种管径；管网由多少管段组成就调用多少次随机函数。要产生N个个体，只需重复N次个体产生操作就可以了。这样就生成了我们所需要的初始群体。
然而，对于改建和扩建项目，由于需要在确定某些管段管径的情况下改变或新建某些管段，最终达到新管段与原有确定管径的管段组成的整个系统运行工况良好，即要求在确定某些管段管径的情况下，使产生的整个个体的适应度较高。因此，需要对传统的遗传算法进行优化。对于有N条管段的管网系统，如果其中有M条管段的管径已确定，因此需要随机产生另外的N-M个个体，与已经确定的M条管段的个体合并形成初始群体。
值得注意的是，在形成初始群体的时候，需要将已定管径的管段个体放在初始群体的最后。这样，每个个体就是由所有管段的管径按照一定顺序连接在一起的数字串，这个顺序就是管段的编号顺序，其中已知管径管段排在后面。因此，不同的个体代表了不同的管段管径选择情况。这样形成的初始群体，都满足管网改建与扩建工程中已确定部分管段的情形。起初，这个初始群体中的大多数个体肯定很难满足要求，但是通过遗传运算，择优汰劣，最后选择出满足目标函数要求的优秀个体[8]。
2.2.2 评价
评价个体亦即计算个体的适应度。遗传算法中使用适应度来度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大；而适应度较低的个体遗传到下一代的概率就相对小一些[9]。对于每一代的每一个个体都要进行适应度的计算，可以将每一代的种群视为一个二维数组population，则适应度W的计算如下。
初始适应度计算:
for i=1:1:popsize
for j=1:NB
W=W+(1.56*population(i, j)^1.01-28.94)*L(j);
end
W=(1/7+0.07)*W[10]；
end
式中：popsize为每代种群的个体数；NB为管段数；i为种群的个体号；j为个体的管段号；L为管段的长度；population(i, j)为种群中第i个个体中第j个元素[11]。
通过初始适应度的计算后，还要对此代种群中的每个个体(即配径方案)进行管网平差计算[12]，得到管段流量、节点压降，然后对W进行修正，得到个体的最终适应度，且适应度越大越好[13]。
2.2.3 选择
选择操作是建立在对个体的适应度进行评价的基础之上的，是对这一代种群中每个个体进行随机选择进入下一代种群。在选择操作中，对群体中的所有个体按其适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。应该是更满足目标函数即适应度较高的个体将有更多机会遗传到下一代，而适应度较低的个体遗传到下一代的机会就相对较少[14]。
由于所形成的每个个体的管段信息都满足改、扩建项目的基本要求，因此，经过选择操作，最终的结果是选择出满足改、扩建项目管段要求的适应度较高的个体。
2.2.4 交叉
交叉操作的设计和实现与所研究的问题密切相关，要求它既不要太多地破坏个体编码串中表示优良性的优良模式，又要能够有效地产生一些较好的新个体模式。首先需要在种群中随机找2个个体进行配对，然后进行算术交叉。
for j=point1:1:point2
temp=population(index(i), j );
population(index(i), j )=population(index(i+1), j );
population(index(i+1), j )=temp;
end
式中：index为记录的个体配对信息数组；point1和point2为产生的2个随机数[15]。
例如配对的2个个体是A和B，在point1=3，point2=6时，交叉示例如下，其中最后两条管段为已确定管径的管段：
A: 76 76 |89 76 133|108 B:133 89|76 108 133|108
↓
A:76 76 |76 108 133|108 B:133 89|89 76 133 |108
可见：经过交叉操作，已经确定管径的管段并没有发生变化，仍然能保留原来管段信息。
2.2.5 变异
由于发生变异是在同一个个体上随机确定的两点之间，不能排除已定管径的管段进行变异操作，这样会导致已定管径管段信息发生变化。因此，针对改扩建项目，就需要对发生变异的过程进行控制，将进行变异操作的两点排除在已定管径的管段之外。
3 结论
(1) 对遗传算法的基本操作过程进行改进，即经过了改进的选择、交叉与遗传等操作之后，最终选出来的个体是在保证已确定管段管径基础上适应度最高的个体。同时，形成的新群体的个体中代表已确定管径的各管段仍然保持着原有管径的信息，满足管网改造项目的需求。
(2) 用遗传算法进行管网水力计算过程中，管径的确定是最主要且复杂的步骤，通过改进，解决了改、扩建项目中管径的确定问题，大大优化了管网改造项目的过程。
参考文献：
[1] 段常贵, 徐彦锋, 吴继臣, 等. 遗传算法在煤气管径优化中的应用研究[J]. 煤气与热力, 1999, 19(2): 19-22.
DUAN Chang-gui, XU Yan-feng, WU Ji-chen, et al．Applied research of genetic algorithm on gas pipe diameter optimization[J]. Gas & Heat, 1999, 19(2): 19-22.
[2] 王小平, 曹立命. 遗传算法—理论、应用与软件实现[M]. 西安: 西安交通大学出版社, 2002.
WANG Xiao-ping, CAO Li-ming. Genetic algorithm—Theory, application and software implementation[M]. Xi’an: Xi’an Jiaotong University Press, 2002.
[3] 张进, 王卫敏, 荆振锋, 等. 遗传算法在水力管网优化中的应用[J]. 制冷, 2010, 2(2): 76-79.
ZHANG Jin, WANG Wei-min, JING Zhen-feng, et al. Application progress of genetic algorithm in optimization of water pipe network[J]. Refrigeration, 2010, 2(2): 76-79.
[4] Dawn Robin Dott. Optimal network design for natural gas pipe lines[D]. Alberta, Canada: The University of Calgary, 1997.
[5] 张铃, 张钹. 遗传算法机理的研究[J]. 软件学报, 2000(7): 945-952.
ZHANG Ling, ZHANG Bo. Research on the mechanism of genetic algorithms[J]. Journal of Software, 2000(7): 945-952.
[6] 周明, 孙树栋. 遗传算法原理及应用[M]. 北京: 国防工业出版社, 2000.
ZHOU Ming, SUN Shu-dong. Principle and application of genetic algorithm[M]. Beijing: National Defense Industry Press, 2000.
[7] Davis L. Adapting operator probabilities in genetic algorithm [D]. Edinburgh: University of Edinburgh. Department of Artificial Intelligence, 1995.
[8] 黄戡, 刘宝琛, 彭建国, 等. 基于遗传算法和神经网络的隧道围岩位移智能分析[J]. 中南大学学报: 自然科学版, 2011, 42(1): 213-219.
HUANG Kan, LIU Bao-chen, PENG Jian-guo, et al. Intelligent back-analysis of tunnel surrounding rock displacement based on genetic algorithm and neural network[J]. Journal of Central South University: Science and Technology, 2011, 42(1): 213- 219.
[9] 王建刚. 城市天然气输配管网的数学模型及优化[D]. 西安: 西安电子科技大学, 2008: 50-57.
WANG Jian-gang. The mathematical model and optimization of city natural gas pipeline network[D]. Xi’an: XIDIAN University, 2008: 50-57.
[10] 冷婷婷. 遗传算法在城市燃气管网优化中的应用[D].重庆: 重庆大学, 2004: 37-40.
LENG Ting-ting. The optimal design of urban gas by genetic algorithm[D]. Chongqing: Chongqing University, 2004: 37-40.
[11] 孙祥, 徐流美, 吴清. MATLAB7.0基础教程[M]. 北京: 清华大学出版社, 2006.
SUN Xiang, XUN Liu-mei, WU Qing. MATLAB7.0 basis tutorial[M]. Beijing: Tsinghua University Press, 2006.
[12] 严铭卿. 燃气管网综合优化原理[J]. 煤气与热力, 2003, 12(12): 741-745.
YAN Ming-qing. Composite optimization principle of gas network[J]. Gas & Heat, 2003, 12(12): 741-745.
[13] 梁昔明, 朱灿, 颜东煌. 基于物种选择的遗传算法求解约束非线性规划问题[J]. 中南大学学报: 自然科学版, 2009, 40(1): 185-189.
LIANG Xi-ming, ZHU Can, YAN Dong-huang. Novel genetic algorithm based on species selection for solving constrained non-linear programming problems[J]. Journal of Central South University: Science and Technology, 2009, 40(1): 185-189.
[14] 李华昌, 谢淑兰, 易忠胜. 遗传算法的原理与应用[J]. 矿冶, 2005, 14(1): 87-90.
LI Hua-chang, XIE Shu-lan, YI Zhong-sheng. Theory and application of genetic algorithm[J]. Mining and Metallurgy, 2005, 14(1): 87-90.
[15] 排新颖, 马善立. 一种改进的遗传算法及其应用[J]. 科学技术与工程, 2011, 11(20): 4836-4842.
PAI Xin-ying, MA Shan-li. An improved genetic algorithm and its application[J]. Science Technology and Engineering, 2011, 11(20): 4836-4842.
(编辑 李向群)
收稿日期：2012-01-15；修回日期：2012-02-15
基金项目：国家自然科学基金资助项目(50908244)
通信作者：王兴畏(1984-)，男，江苏徐州人，博士研究生，从事城市燃气输配与应用研究；电话：15803055936；E-mail: wangxw920@126.com
