基于树型编码的MRST混合遗传算法及其并行处理  

A Tree Coded Hybrid Genetic Algorithm of Minimum Rectilinear Steiner Tree and Its Parallel Model

作　　者：杨昌玲[1] 严晓浪[1] 

机构地区：[1]杭州电子工业学院CAD所

出　　处：《微电子学》1999年第2期89-95,共7页Microelectronics

基　　金：国家"九五"攻关项目

摘　　要：提出一个关于最小矩形边斯坦纳树（ＭｉｎｉｍｕｍＲｅｃｔｉｌｉｎｅａｒＳｔｅｉｎｅｒＴｒｅｅ，ＭＲＳＴ）的混合遗传算法。该算法根据ＭＲＳＴ问题的特点，采用了树形结构编码方案以及相应的遗传操作方法，在群体设定时均匀划分空间，依据遗传群体的环境参量动态地调整遗传算法的进化策略；在执行遗传操作时与爬山法相结合，在群体更新时引进模拟退火更新机制，大大加强其寻优能力。最后，提出了该算法基于ＭＩＭＤ模型的扩展分布式并行算法。算法复杂性分析以及实验结果表明该算法有效。An adaptive evolution genetic algorithm for Minimum Rectilinear Steiner Tree(MRST) problem is investigated, which is tree coded according to the characteristics of MRST.The algorithm uses tree like genetic operation, partitions the solution space uniformly and tunes the evolution strategies adaptively based on the genetic environment parameters. Evolution inversion operation and simulated annealing technique for alternation of generations are introduced to enhance its ability of searching optimal solutions. Finally, an extended distributed parallel algorithm for the GA and MIMD model is presented. Both analysis on the complexity and experimental results show the effectiveness of the algorithm.

关 键 词：遗传算法 MRST 树形结构编码 并行算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O242.23[自动化与计算机技术—计算机科学与技术]