基于单亲遗传算法的管网优化  

OPTIMIZING PIPELINE NETWORK BASED ON SINGLE PARENT GENETIC ALGORITHM

作　　者：骆力明[1] 王华[1] 王炎[1] 

机构地区：[1]首都师范大学信息工程学院,北京100037

出　　处：《计算机应用与软件》2008年第6期68-70,75,共4页Computer Applications and Software

基　　金：北京市教委基金资助项目(KM200410028013)

摘　　要：管网连通分析是管网空间分析中一个很重要的功能,即针对多种因素获取管网的连通路径,该问题可以抽象为求图的最小生成树问题,传统算法只能针对一种因素求出唯一的生成树。使用遗传算法进行最小生成树的求解,可以得出满足条件的一组解,从而便于对多种因素的综合考虑。结合管网的实际需求,采用单亲遗传算法提高个体的有效性,通过引入精英选择和自适应遗传算法,有效改善了早熟和过早收敛问题,并使用实例验证了其有效性。The analysis of pipeline network connection, i. e. , to acquire the link-path of pipeline network in accordance with multiple factors, is one of the most important functions in pipeline spatial analysis. It can be abstracted as a combination optimization problem of minimum spanning tree in graph theory＇. Traditional method gets one tree against one factor only, so genetic algorithm is used to solve minimum spanning tree to get a group of condition-satisfied solutions, from which many factors can be considered synthetically. The single parent genetic algorithm is applied to improve the individual validity and elitist selection and adaptive genetic algorithm are imported as well to improve the problems of over maturity and premature convergence effectively. The effectiveness of the approach is checked by practical applications.

关 键 词：单亲遗传算法 精英选择 最小生成树 

分 类 号：O242.23[理学—计算数学] TU996.72[理学—数学]