弹性TSP及其并行遗传优化  

Elastic TSP Model and its Parallel Genetic Optimization

作　　者：宋勇[1] 陈贤富[1] 戴蓓倩[1] 

机构地区：[1]中国科学技术大学电子科学与技术系,安徽合肥230027

出　　处：《小型微型计算机系统》2006年第5期842-845,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(70071043)资助

摘　　要：受生物神经系统中突触联结强度随外部激励自适应调节机制的启发,针对图论问题,提出一种权值自适应弹性调节方法,构建了一个弹性TSP模型,分析了该模型的特征及意义.从区域隔离和基因流动两个角度出发,研究了弹性TSP的一种并行遗传优化方法.对本地子群和迁移子群的相同高频边(这些高频边构成“共同边集”)进行弹性共振处理,对不同的而在历史“共同边集”中出现的高频边进行弹性恢复处理.在该算法的试验研究中寻找到了中国144城市TSP的新的更优路径,表明该算法对于求解复杂的组合优化问题具有较高的求解性能.Inspired by the thought of synapsis intensifying in biological neural systems, aiming at the problems in graph theory, this paper presented an elastic adjusting method for connecting right value, formed an elastic TSP model and also analyzed its features and significance. Based on this model, considering two factors of affecting the colony evolution： species insulation and gene flowage, investigated a parallel implementation method of elastic TSP, which resonated the common high-frequency edges （these edges are called as ＂common edge set＂ ） between local population and the immigrated sub-population, but rebounded the different ones that existed in the ＂common edge set＂ of last time. In the experimental research, found a better solution of 30355. 119Km for CHN144 TSP instance, which showed that the proposed method has good performance in solving complicated combinational optimization.

关 键 词：遗传算法 弹性TSP 并行优化 联想记忆 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]