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

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

周荣敏¹，林性粹²
(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)求树状管网中各管段流量：??