摘要
TSP问题是典型的NP-hard组合优化问题,GA是求解此类问题的一种方法。但它存在如何较快地找到最优解并防止“早熟”收敛的问题。文章针对上述问题并结合TSP问题的特点,提出了改进的遗传算法。它从相似性的思想出发,按适应值相似性将群体分级,在不同的级内采用不同的操作,产生数目不等的新解并利用加速算子使其更接近局部极小值。改进后的算法较好地解决了群体多样性与收敛性的矛盾。实验结果表明,该文算法的改进是有效的。
TSP is a classical NP-hard combinatorial optimization problem.GA is a method for solving this problem.But it is hard for GA to find global optimization quickly and prevent premature convergence.This paper,in order to solve the problem,considering the characteristic of TSP,puts forward an improved genetic algorithm,which based on similitude,classifying the population by similitude.Each level with its respective operations generates new solutions in different numbers and accelerates the new solutions to approach the local minimum by accelerated operator.The improved algorithm can solve the conflict between population diversity and algorithm convergence.The experimental re suit indicates that it is effective.
出处
《计算机工程与应用》
CSCD
北大核心
2006年第13期91-93,共3页
Computer Engineering and Applications
基金
国家自然科学基金资助项目(编号:70371070/G0116)
湖北省自然科学基金资助项目(编号:2004ABA029)
上海市教委科研资助项目(编号:05EZ34)
上海市重点学科建设资助项目(编号:T0502)
关键词
TSP问题
遗传算法
分级
精英选择策略
启发式交叉算子
贪婪倒位变异算子
TSP Problem, Genetic Algorithm, classification, elitist selection strategy, heuristic crossover operator, greedy inverse mutation operator
