摘要
TSP问题是典型的NP-hard组合优化问题,遗传算法是求解此类问题的一种方法,但它存在如何较快地找到全局最优解,并防止"早熟"收敛的问题。针对上述问题并结合TSP问题的特点,提出将遗传算法与模拟退火算法相结合形成遗传模拟退火算法。为了解决群体的多样性和收敛速度的矛盾,采用了部分近邻法来生成初始种群,生成的初始种群优于随机产生初始种群。仿真实验结果证明,该算法相对于基本遗传算法的收敛速度、搜索质量和最优解输出概率方面有了明显的提高。
TSP is a classical NP-hard combinatorial optimization problem.Genetic algorithm is a method for solving this problem.But it is hard for genetic algorithm to find global optimization quickly and prevent premature convergence.This paper,in order to solve the problem,considers the characteristic of TSP,and puts forward a genetic simulated annealing algorithm, a hybrid of genetic and simulated annealing algorithm.In order to solve the inconsistency between diversity and convergent speed, this paper also adopts part greedy method to produce original population.The original population produced by this method is superior to the randomly produced original population.The simulation results demonstrate that, the proposed algo- rithm achieves considerable improvements, with respect to the basic genetic algorithm, in convergence speed, search quality and optimal solution output rate.
出处
《计算机工程与应用》
CSCD
北大核心
2010年第29期40-42,46,共4页
Computer Engineering and Applications
关键词
混合遗传算法
模拟退火算法
旅行商问题
hybrid genetic algorithm
simulated annealing algorithm
traveling salesman problem
