单亲遗传算法的应用有哪些?

单亲遗传算法的应用有哪些?

应用单亲遗传算法进行树状管网优化布置

周荣敏1,林性粹2
(1.郑州大学 水环学院2.西北农林科技大学)

摘 要:树状管网布置优化属于典型的组合优化问题。本文针对树状管网布置的特点,以图论和遗传算法为理论基础,应用改进遗传算法 单亲遗传算法进行树状管网优化布置,并设计了相应的适应度函数、单亲换位算子和逆转算子。与Dijkstra算法和Kruskal算法相比,单亲遗传算法直接以管网投资最小为优化目标,能够获得一批管网投资最小的布置方案,且算法的寻优效率较高,收敛性和稳定性较好。

关键词:单亲遗传算法;树状管网;优化布置

收稿日期:2000 05 17
作者简介:周荣敏(1971-),女,河南新野人,博士,讲师,主要从事节水灌溉方面的研究。

1 树状管网遗传优化布置的基本原理

树状管网具有图论中树的性质,有ND个节点的树状管网对应于一棵过ND个节点、有ND-1条边的树。树状管网优化布置的目标是寻找管网投资最小的树状管网布置形式,实质上就是以管网初步连接图为依据,以管道造价为权值,求管网投资最小的生成树。一个有ND个节点和NP条待选边的管网初步连接图,有许多个可行的树状管网布置形式,由于管网内流量分配模式不同,管网投资和水力性能差异较大。若用枚举法寻求所有生成树,计算量较大,求解效率低。若用图论中Dijkstra算法和Kruskal算法[1],只能分别获得一个管网总长度和路径最短的布置方案,但其管网投资未必最校遗传算法(Genetic Algorithms GA)是一种新兴的全局优化算法,其仅以目标函数值为搜索依据,通过群体优化搜索和随机执行基本遗传运算,实现遗传群体的不断进化,适合解决离散组合优化问题和复杂非线性问题[2]。树状管网布置优化属于典型的组合优化问题,可以应用遗传算法进行树状管网优化布置:首先选择一种合适的编码方式表示树状管网布置问题,然后以随机方式从NP条边中选取ND-1条边构成一个管网连接子图,利用深度优先搜索算法(DFS)判断其连通性。如果一次搜索能找到ND个节点,则该连接子图是一个连通图。过ND个顶点且有ND-1条边的连通图一定一棵支撑树,即所选择的ND-1条边构成一个树状管网。

已知树状管网布置形式和各节点需水量(假定流出管网为正,流入管网为负),根据管网节点连续性方程[3],由式(1)求树状管网中各管段流量:??

BT+qT+QT=0

(1)