货郎担问题与单亲遗传算法  

Solution TSP in Partheno-genetic Algorithm

作　　者：雷建平[1] 沈成武[1] 闻骥骏[1] 

机构地区：[1]武汉理工大学

出　　处：《武汉理工大学学报》2003年第6期80-83,共4页Journal of Wuhan University of Technology

基　　金：国家自然科学基金项目资助 (19772 0 38)

摘　　要：用单亲遗传算法解组合优化的货郎担问题 ,给出了基因重组的换位 ,移位和倒排等概率操作方法。通过 9节点的算例 ,证实了该算法对组合优化问题是可行的 ,有较快的收效速度。但过早的收敛将影响结果精度 ,使全局优化解的出现机率很小。为此 ,对染色体种群的个体数量 ,终止条件的选取等进行了算值实验 ,并提出了计算终止的 2个准则 ,计算结果表明合理的收敛条件 ,可以使寻优过程充分 ,所得的解为全局最优解的可信度大为提高。The solution of the combinatorial optimization traveling salesman problem (TSP) by means of partheno-genetic algorithm provides the operation methods for exchange, moving and pour arrangement of genetic rearrangement. The example of 9 nodes proves the feasibility of the means with comparatively fast convergence speed. However, too early convergence will affect the precision of the result and minimize the probability to arrive at result of global optimization. Therefore, result of example experiment is carried out on the individual number of gene and the choice of termination conditions. And two principles of calculation ceasing are put forward. The calculation results indicate that reasonable convergent conditions make sufficient approach process, and that solution thus gained as the solution of global optimization greatly promotes the reliability of it.

关 键 词：单亲遗传算法 组合优化 货郎担问题(TSP) 

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