完全图哈密尔顿圈遗传算法的MATLAB模拟实现  

The Simulation of Genetic Algorithm for Hamilton Circle on Complete Graph in MATLAB Environment

作　　者：刘奕君[1] 张立[2] 赵强[1] 

机构地区：[1]徐州医学院医学信息学院,江苏徐州221000 [2]徐州医学院医学影像学院,江苏徐州221000

出　　处：《西华大学学报（自然科学版）》2015年第4期13-16,共4页Journal of Xihua University:Natural Science Edition

基　　金：徐州市科技计划项目(XM13B021);徐州市科技计划项目(XM12B077)

摘　　要：求解完全图上的哈密尔顿圈是典型的组合优化问题,遗传算法是解决此类NP问题的一种较理想的方法。对基本的遗传算法进行改进,在选择操作和变异操作中加入贪心优化思想,使算法获得更优的全局最优解。在MATLAB环境下模拟实现了哈密尔顿圈的经典问题——TSP(travelling salesman problem)旅行商问题,从而验证了该算法的可行性和正确性。Solving Hamilton-circle on a complete graph is a typical combinatorial optimization problem. Genetic algorithm is a good way to solve such an NP problem. In this paper,the basic genetic algorithm is improved. Particularly,the greedy optimization ideas are applied to the selection and mutation operation in order to obtain global optimal solutions with the algorithm. In the MATLAB environment,the algorithm was simulated to implement classical Hamilton circle- TSP（ travelling salesman problem） and the results verify the feasibility and correctness of the algorithm.

关 键 词：哈密尔顿圈 遗传算法 贪心思想 MATLAB 全局最优解 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论] TP312[自动化与计算机技术—计算机科学与技术]