基于模拟退火的遗传优化算法在TSP问题中的应用

TSP问题一直属于NP难题,目前解决TSP问题方法很多,如模拟退火算法、遗传算法以及Hopfield网络神经方法等.以上这些方法在解决TSP问题时各有优缺点,本文结合了模拟退火算法和遗传算法提出了一种新的组合优化算法,即基于模拟退火的遗传优化算法.此算法的核心思想是将遗传优化算法嵌入到模拟退火算法中,利用模拟退火算法的接受准则和随机状态产生函数来产生遗传算法的种群,然后根据遗传优化算法的结果反过来制约模拟退火的随机状态产生,从而最终得到最优解.本文首先对此方法的流程和基本步骤进行了详细的论述,然后采用C语言进行编程,对20个城市的TSP问题进行了优化求解.对结果分析可认为此种方法在解决TSP问题时存在一定的优越性.

Application on GA based on SA for TSP

TSP is always a difficult NP problem. At present, there are lots of methods to solve TSP, for example Simulated Annealing, Genetic Algorithms, Hopfield Network Nerve Algorithm, and so on. However there are kinds of merits and shortcomings while applying above methods to solve TSP. A new synthesis method named Genetic Algorithms based on Simulated Annealing is provided in the paper. The essence of the algorithm is inserting Genetic Algorithms to Simulated Annealing. On one hand, the function, formed in Simulated Annealing according to the accepting criterion and random state, provides a population to Genetic Algorithms, and on the other hand, the result of Genetic Algorithms conversely restrictes the forming of the random state, and thereby the optimum solution is founded ultimately. Firsly, the procedure and the steps of the algorithm are stated datailedly in the paper. Secondly, a TSP of 20 cities is solved by the programme with the language C according to the algorithm. Finally, the algorithm shows certain superiority to solve TSP throughing analysing above results.