论文部分内容阅读
摘要：本文主要介绍了遗传算法的基本思想，及基本遗传算法的求解步骤。通过对遗传算法的数学原理的分析，进一步认识了遗传算法的数学本质。然后介绍了目前一些改进的遗传算法的发展状况。最后结合遗传算法的特性，简要介绍了遗传算法在给水管网优化设计中的应用方法。
Abstract
In this paper the basic concept of the Genetic Algorithm (GA) and the procedure of the Simple Genetic Algorithm (SGA) were introduced。 Through the analysis of the mathematical principle of GA， the mathematical essence of the GA was discovered。 Then the developments of the modified GA were showed。 At last， the application of GA in the design of water and wastewater distribution networks was introduced briefly in combination with the characteristic of GA。
中图分类号：S611文献标识码：A 文章编号：
至从改革开放以来，我国经济不断发展，城市化发展速度惊人，大中城市扩建，中小城市升级，建制镇增多。城市化发展必然带来给水系统的变化和发展，而给排水系统设施的建设也是制约城市化发展的因素之一。伴随着改革开放，我国城镇给排水事业有了长足的发展，为国家的高速经济发展和人民生活水平不断提高提供了重要的基础设施保障条件。作为给水设施的重要组成部分，给水管网建设和运行管理科学技术的发展，已经成为我国城镇给排水科学技术进步的重要标志之一。由于给水管网建设投资巨大，管网设计的复杂性，传统的设计方法主要依据经验，缺乏合理性，同时为坚持可持续发展的理念，响应国家有关节能减排的号召，有必要对给排水管网进行优化，以降低能耗、节省费用。随着系统工程、最优化理论的不断发展，很多新的优化方法和算法不断被引入管网优化设计中。[3]
1 遗传算法
1.1 遗传算法概要
遗传算法( Genetic Algorithms 简称GA)研究的历史比较短，20世纪60年代末期到70年代初期，主要由美国Michigan大学的John Holland 教授与其同事、学生们研究形成了一个较完整的理论和方法。[2]它是一种通过模拟自然进化过程搜索最优解的随机寻优的数学规划方法。该算法是基于自然遗传和自然优选机理的寻优方法，所谓自然遗传和自然优选来自于达尔文的进化论学说，该学说认为在生物进化过程中，任一动植物经过若干代的遗传和变革，使之能够适应新的环境，是优胜劣汰的结果，这种自然遗传思想也同样适用于求解最优化问题。
遗传算法用一串数据或数组作为优化问题解的代码，这一串数据或数组称为染色体，这一表示过程称为编码。它的求解过程是首先产生一定数量的染色体形成一个种群，通过一个与目标函数相关的函数评价各染色体，即各方案的优劣，优劣的程度称为染色体的适应度。 然后进行选择过程，染色体被选择的概率与其适应度有关，适应度大的染色体被选择的概率大，反之亦然。被选择的染色体再进行交叉操作和变异操作，交叉操作和变异操作保持了种群中个体特性的多样性，防止陷入局部最优解，经过上述运算后产生新一代的种群。然后，如此迭代一定的次数后，产生的最优的染色体即为优化问题的最优解。[1]
2 遗传算法在给排水管网中的应用
2.1 遗传算法给水管网优化问题中的应用
给水管网是城市供水系统的重要组成部分，它占整个给水工程投资的70 %～80 %。随着城市规模的扩大，管网也不断向着大型化、复杂化的方向发展，这使得优化设计在给水管网设计中变得尤为重要。给水管网的优化问题涉及因素众多，是一个混合离散變量的非线性多目标优化问题。将目标函数集中在经济最优目标上，同时为保证供水可靠性，设定最小管径约束，以防单纯经济考虑导致树状网的出现。这样给水管网的优化问题就转化为在给定管线布置及可供管径规格等条件下求解最优管径和最优水源流量问题。[4]近年来，遗传算法已经有了一些分配系统规划和设计的应用研究，并显示了较大的优越性。[3]
一、遗传算法进行给水管网优化问题的主要步骤
（1）编码。考虑到计算处理的方便性，常用二进制编码与市面可用管径一一对应。如果市面可用管径有8种，则用三位二进制编码可以将其表示为一个基因型。每一组管网设计的组合对应着每一组基因型的组合，即一个染色体。多个带有染色体的个体就组成一个种群。[3]在进行优化调度时，针对泵站中存在定速泵和变速泵两类情形，分别以二进制和实数编码表达定速泵和变泵的转速比，并以编码串组合来表达管网中所有水泵的运行状态，形成用以表达某种调度方案的染色体个体，再由一定量染色体个体组合形成种群。这种编码方式的优点类于既能保证决策变量与编码结构在形式上的统一，也避免了用多位二进制编码映射实数值时的额外计算开销，从而提高了算法的搜索效率。[6]
（2）产生一定规模的初始种群。正如前面所述，产生初始种群的方法有两种，一种是随机产生，另一种是某些先验可转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选取样本。后者的做法可以极大地提高算法的效率，以便得到更好的结果。
种群个数的选取不能过大或小，这样会影响算法的效率，现有的办法是通过试验寻求最佳N值。
（3）定义适应度函数。遗传算法的遗传操作是通过适应度来实现的，而目前采用的目标函数多为管网经济目标函数，如：
式中：为每年扣除的折旧和大修费；为利率；为投资回收年限；、、为管网造价系数；为管径；为管段长度；供水能量变化系数；为电费；为水的密度；为重力加速度；为输入管网的总流量；为二级泵站扬程；为泵站效率。
式中除了、等一系列常系数外，定线时已经确定，和是根据提交管径后水力计算的结果确定的。因此，管网优化实际是求一个拓扑结构已经（管网走向和各段管长定）的网络结构各管段管径的最优组合，使得目标函数值最小化的最优化问题。
除了能量平衡和流量平衡已通过水力计算部分纳入目标函数之外，上述经济目标函数还就满足最小允许流速、最小服务水头等约束条件，以罚函数形式纳入目标函数中：
(10)
其中，为各个约束变量；为惩罚因子，其功能是根据情况放大或缩小惩罚函数的值，以避免惩罚项与造价项的师级不匹配。在实际计算适应度时，将上式取倒数得适应度的评价函数为：
然后分析计算遗传种群中每个个体的水力特性、管网费用及个体的适应度。
（4）对遗传群体执行选择，交叉和变异算子，产生新一代遗传种群。
交叉率一般取值为0。4~0。9，交叉方式可以采用上述的单点交叉、多点交叉或均匀交叉，一般来说多点交叉和均匀交叉的效果要好；变异率通常取值很小，一般取0。001~0。1。对于具体问题而言，衡量参数设置恰当与否，要依据多次运行的收敛情况和解的质量来判断。
（5）重复步骤（3）和（4），直至达到算法终止条件。模拟终止条件是设定最大进化代数，一般视具体情况而定，取100~500代。
（6）从最终的遗传群体中选择若干个最优个体作为管径优化設计方案。[3]
在面对具体问题时，灵活的编码方式、适应度函数选择和参数选取是非常重要的，如果在此基础上还不能得到满意的解，则往往需要对基本遗传算法的改进，采用改进的遗传算法进行求解，如伪并行遗传算法、用遗传表达混乱遗传算法等。
三、遗传算法解决给水管网优化设计问题的优点：
(1) 遗传算法的寻优过程是一种随机寻优过程，最优解不会在狭窄的区域内收敛，不至于形成局部最优解；
(2) 易于处理离散变量函数的优化问题，避免了管径调整；
(3) 应用遗传算法进行环状管网优化设计时，无需预先分配流量模式，而是通过遗传进化过程寻找能满足管网水力特性和管网造价低的管径组合方案。[2]
与此同时，在实际工程中采用遗传算法作为优化手段是不够的，在对较复杂管网进行应用时，得到的管网方案主要流向形成了供水管网的枝状优化树，其他位置往往都是由满足约束条件的临界管径联接成环。管网优化设计的目标应当是经济性、可靠性和供水水质安全性的全面优化。但是由于水质安全性不易量化，管网运行正常时和故障时用水量会发生变化，以及管网拓扑结构的复杂性，使得至今还没有成熟的理论来分析管网的安全性，因而也无法将可靠性因素很好地量化以纳入适应度函数中。现在常用的方法是以经济性为目标函数，而将其他因素作为约束条件，据此建立适应度函数，来评价个体的适应度，这样处理的结果使得最终方案在供水安全性上不够完善。事实上，现有很多研究成果表明，对环状管网来说，流量优化分配是个凹规划问题，即它的解往往现出在约束区域的边界上。如果没有与供水水质和供水安全性相关的下限约束条件，则优化的结果会使某些管段的流量为零，成为树状网。应当依据实际情况对遗传算法获取的优化结果加以修正，在经济和安全上寻求一个最佳的平衡点，才能真正达到优化设计的目的。[3]
3 结论与建议
遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性。通过众多学者的研究证明，遗传算法在给排水管网优化问题的应用是可行的。
在应用改进的遗传算法解决给水管网优化问题时，应从其收敛性出发，通过对编码方式、遗传操作和适应度函数设计等方面的研究，来提高其计算效率，获得更优的结果。
众多学者研究证明，通过先验知识产生的初始种群有助于提高遗传算法的计算效率，并能够得到更优的结果。因此，把遗传算法极强搜索寻优能力和其它算法的高效求可行解的能力相结合也是非常有前景的。如有学者提出利用细胞自动机算法(CAs)的高效求可行解能力，来为遗传算法提供初始种群[8]，证明可以提高遗传算法的效率，并取得良好的结果。
遗传算法的终止策略主要靠设定进化代数决定，考虑用其它的方法来增加算法终止的可能性。如有学者提出应用平均欧几里德距离对下一代种群的适应度进行概率性的评估，来决定是否终止算法。[7]
参考文献：
[1]王小平,曹立明.遗传算法－理论、应用与软件实现[M].西安:西安交通大学出版社,2002,1.
[2]刘守亮,吕谋,李培刚.遗传算法在给水管网优化设计中的应用.青岛理工大学学报.2005,26(6):99~102.
[3]朱家松,龚健雅,郑皓.遗传算法在管网优化设计中的应用.武汉大学学报信息科学版.2003,28(3):363~367.
[4]卜义惠,赵洪宾,周建华.用遗传算法求解给水管网系统优化改扩建模型.给水排水.2003,29(12):89~92.
[5]段玉倩,贺家李.遗传算法及其改进.电力系统及其自动化学报.1998,10(1):39~52.
[6]信昆仑,刘遂庆,陶涛,李树平.伪并行遗传算法在供水管网优化调度中的应用.同济大学学报自然科学版.2006,34(12):1662~1667.
[7]Heng-Chou CHEN,Oscal T.-C.CHEN.Population Fitness Probability for Effectively Terminating Evolution Operations of a Genetic Algorithm. IEICETRANS . INF .& SYST.2006, E89(12):3012~3014
[8]Edward Keedwell, Soon-Thiam Khu. A hybrid genetic algorithm for the design of water distributeon networks. Engineering Applications of Artificial Intelligence. 2005,18:461~472.
Abstract
In this paper the basic concept of the Genetic Algorithm (GA) and the procedure of the Simple Genetic Algorithm (SGA) were introduced。 Through the analysis of the mathematical principle of GA， the mathematical essence of the GA was discovered。 Then the developments of the modified GA were showed。 At last， the application of GA in the design of water and wastewater distribution networks was introduced briefly in combination with the characteristic of GA。
中图分类号：S611文献标识码：A 文章编号：
至从改革开放以来，我国经济不断发展，城市化发展速度惊人，大中城市扩建，中小城市升级，建制镇增多。城市化发展必然带来给水系统的变化和发展，而给排水系统设施的建设也是制约城市化发展的因素之一。伴随着改革开放，我国城镇给排水事业有了长足的发展，为国家的高速经济发展和人民生活水平不断提高提供了重要的基础设施保障条件。作为给水设施的重要组成部分，给水管网建设和运行管理科学技术的发展，已经成为我国城镇给排水科学技术进步的重要标志之一。由于给水管网建设投资巨大，管网设计的复杂性，传统的设计方法主要依据经验，缺乏合理性，同时为坚持可持续发展的理念，响应国家有关节能减排的号召，有必要对给排水管网进行优化，以降低能耗、节省费用。随着系统工程、最优化理论的不断发展，很多新的优化方法和算法不断被引入管网优化设计中。[3]
1 遗传算法
1.1 遗传算法概要
遗传算法( Genetic Algorithms 简称GA)研究的历史比较短，20世纪60年代末期到70年代初期，主要由美国Michigan大学的John Holland 教授与其同事、学生们研究形成了一个较完整的理论和方法。[2]它是一种通过模拟自然进化过程搜索最优解的随机寻优的数学规划方法。该算法是基于自然遗传和自然优选机理的寻优方法，所谓自然遗传和自然优选来自于达尔文的进化论学说，该学说认为在生物进化过程中，任一动植物经过若干代的遗传和变革，使之能够适应新的环境，是优胜劣汰的结果，这种自然遗传思想也同样适用于求解最优化问题。
遗传算法用一串数据或数组作为优化问题解的代码，这一串数据或数组称为染色体，这一表示过程称为编码。它的求解过程是首先产生一定数量的染色体形成一个种群，通过一个与目标函数相关的函数评价各染色体，即各方案的优劣，优劣的程度称为染色体的适应度。 然后进行选择过程，染色体被选择的概率与其适应度有关，适应度大的染色体被选择的概率大，反之亦然。被选择的染色体再进行交叉操作和变异操作，交叉操作和变异操作保持了种群中个体特性的多样性，防止陷入局部最优解，经过上述运算后产生新一代的种群。然后，如此迭代一定的次数后，产生的最优的染色体即为优化问题的最优解。[1]
2 遗传算法在给排水管网中的应用
2.1 遗传算法给水管网优化问题中的应用
给水管网是城市供水系统的重要组成部分，它占整个给水工程投资的70 %～80 %。随着城市规模的扩大，管网也不断向着大型化、复杂化的方向发展，这使得优化设计在给水管网设计中变得尤为重要。给水管网的优化问题涉及因素众多，是一个混合离散變量的非线性多目标优化问题。将目标函数集中在经济最优目标上，同时为保证供水可靠性，设定最小管径约束，以防单纯经济考虑导致树状网的出现。这样给水管网的优化问题就转化为在给定管线布置及可供管径规格等条件下求解最优管径和最优水源流量问题。[4]近年来，遗传算法已经有了一些分配系统规划和设计的应用研究，并显示了较大的优越性。[3]
一、遗传算法进行给水管网优化问题的主要步骤
（1）编码。考虑到计算处理的方便性，常用二进制编码与市面可用管径一一对应。如果市面可用管径有8种，则用三位二进制编码可以将其表示为一个基因型。每一组管网设计的组合对应着每一组基因型的组合，即一个染色体。多个带有染色体的个体就组成一个种群。[3]在进行优化调度时，针对泵站中存在定速泵和变速泵两类情形，分别以二进制和实数编码表达定速泵和变泵的转速比，并以编码串组合来表达管网中所有水泵的运行状态，形成用以表达某种调度方案的染色体个体，再由一定量染色体个体组合形成种群。这种编码方式的优点类于既能保证决策变量与编码结构在形式上的统一，也避免了用多位二进制编码映射实数值时的额外计算开销，从而提高了算法的搜索效率。[6]
（2）产生一定规模的初始种群。正如前面所述，产生初始种群的方法有两种，一种是随机产生，另一种是某些先验可转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选取样本。后者的做法可以极大地提高算法的效率，以便得到更好的结果。
种群个数的选取不能过大或小，这样会影响算法的效率，现有的办法是通过试验寻求最佳N值。
（3）定义适应度函数。遗传算法的遗传操作是通过适应度来实现的，而目前采用的目标函数多为管网经济目标函数，如：
式中：为每年扣除的折旧和大修费；为利率；为投资回收年限；、、为管网造价系数；为管径；为管段长度；供水能量变化系数；为电费；为水的密度；为重力加速度；为输入管网的总流量；为二级泵站扬程；为泵站效率。
式中除了、等一系列常系数外，定线时已经确定，和是根据提交管径后水力计算的结果确定的。因此，管网优化实际是求一个拓扑结构已经（管网走向和各段管长定）的网络结构各管段管径的最优组合，使得目标函数值最小化的最优化问题。
除了能量平衡和流量平衡已通过水力计算部分纳入目标函数之外，上述经济目标函数还就满足最小允许流速、最小服务水头等约束条件，以罚函数形式纳入目标函数中：
(10)
其中，为各个约束变量；为惩罚因子，其功能是根据情况放大或缩小惩罚函数的值，以避免惩罚项与造价项的师级不匹配。在实际计算适应度时，将上式取倒数得适应度的评价函数为：
然后分析计算遗传种群中每个个体的水力特性、管网费用及个体的适应度。
（4）对遗传群体执行选择，交叉和变异算子，产生新一代遗传种群。
交叉率一般取值为0。4~0。9，交叉方式可以采用上述的单点交叉、多点交叉或均匀交叉，一般来说多点交叉和均匀交叉的效果要好；变异率通常取值很小，一般取0。001~0。1。对于具体问题而言，衡量参数设置恰当与否，要依据多次运行的收敛情况和解的质量来判断。
（5）重复步骤（3）和（4），直至达到算法终止条件。模拟终止条件是设定最大进化代数，一般视具体情况而定，取100~500代。
（6）从最终的遗传群体中选择若干个最优个体作为管径优化設计方案。[3]
在面对具体问题时，灵活的编码方式、适应度函数选择和参数选取是非常重要的，如果在此基础上还不能得到满意的解，则往往需要对基本遗传算法的改进，采用改进的遗传算法进行求解，如伪并行遗传算法、用遗传表达混乱遗传算法等。
三、遗传算法解决给水管网优化设计问题的优点：
(1) 遗传算法的寻优过程是一种随机寻优过程，最优解不会在狭窄的区域内收敛，不至于形成局部最优解；
(2) 易于处理离散变量函数的优化问题，避免了管径调整；
(3) 应用遗传算法进行环状管网优化设计时，无需预先分配流量模式，而是通过遗传进化过程寻找能满足管网水力特性和管网造价低的管径组合方案。[2]
与此同时，在实际工程中采用遗传算法作为优化手段是不够的，在对较复杂管网进行应用时，得到的管网方案主要流向形成了供水管网的枝状优化树，其他位置往往都是由满足约束条件的临界管径联接成环。管网优化设计的目标应当是经济性、可靠性和供水水质安全性的全面优化。但是由于水质安全性不易量化，管网运行正常时和故障时用水量会发生变化，以及管网拓扑结构的复杂性，使得至今还没有成熟的理论来分析管网的安全性，因而也无法将可靠性因素很好地量化以纳入适应度函数中。现在常用的方法是以经济性为目标函数，而将其他因素作为约束条件，据此建立适应度函数，来评价个体的适应度，这样处理的结果使得最终方案在供水安全性上不够完善。事实上，现有很多研究成果表明，对环状管网来说，流量优化分配是个凹规划问题，即它的解往往现出在约束区域的边界上。如果没有与供水水质和供水安全性相关的下限约束条件，则优化的结果会使某些管段的流量为零，成为树状网。应当依据实际情况对遗传算法获取的优化结果加以修正，在经济和安全上寻求一个最佳的平衡点，才能真正达到优化设计的目的。[3]
3 结论与建议
遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性。通过众多学者的研究证明，遗传算法在给排水管网优化问题的应用是可行的。
在应用改进的遗传算法解决给水管网优化问题时，应从其收敛性出发，通过对编码方式、遗传操作和适应度函数设计等方面的研究，来提高其计算效率，获得更优的结果。
众多学者研究证明，通过先验知识产生的初始种群有助于提高遗传算法的计算效率，并能够得到更优的结果。因此，把遗传算法极强搜索寻优能力和其它算法的高效求可行解的能力相结合也是非常有前景的。如有学者提出利用细胞自动机算法(CAs)的高效求可行解能力，来为遗传算法提供初始种群[8]，证明可以提高遗传算法的效率，并取得良好的结果。
遗传算法的终止策略主要靠设定进化代数决定，考虑用其它的方法来增加算法终止的可能性。如有学者提出应用平均欧几里德距离对下一代种群的适应度进行概率性的评估，来决定是否终止算法。[7]
参考文献：
[1]王小平,曹立明.遗传算法－理论、应用与软件实现[M].西安:西安交通大学出版社,2002,1.
[2]刘守亮,吕谋,李培刚.遗传算法在给水管网优化设计中的应用.青岛理工大学学报.2005,26(6):99~102.
[3]朱家松,龚健雅,郑皓.遗传算法在管网优化设计中的应用.武汉大学学报信息科学版.2003,28(3):363~367.
[4]卜义惠,赵洪宾,周建华.用遗传算法求解给水管网系统优化改扩建模型.给水排水.2003,29(12):89~92.
[5]段玉倩,贺家李.遗传算法及其改进.电力系统及其自动化学报.1998,10(1):39~52.
[6]信昆仑,刘遂庆,陶涛,李树平.伪并行遗传算法在供水管网优化调度中的应用.同济大学学报自然科学版.2006,34(12):1662~1667.
[7]Heng-Chou CHEN,Oscal T.-C.CHEN.Population Fitness Probability for Effectively Terminating Evolution Operations of a Genetic Algorithm. IEICETRANS . INF .& SYST.2006, E89(12):3012~3014
[8]Edward Keedwell, Soon-Thiam Khu. A hybrid genetic algorithm for the design of water distributeon networks. Engineering Applications of Artificial Intelligence. 2005,18:461~472.