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

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

求解完全图上的哈密尔顿圈是典型的组合优化问题,遗传算法是解决此类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.