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

提出一个关于最小矩形边斯坦纳树（ＭＲＳＴ）的混合遗传算法。该算法根据ＭＲＳＴ问题的特点,采用了树形结构编程方案以及相应的遗传操作方法,在群体设定时均匀划分空间,依据遗传群体的环境参量动态地调整遗传算法的进化策略;在执行遗传操作时与爬山法相结合,在群体更新时引进模拟退火更新机制,大大加强其寻优能力。最后,提出了该算法基于ＭＩＭＤ模型的扩展分布式并行算法。算法复杂性分析以及实验结果表明该算法有效。