摘要
旅行商问题,也称货郎担问题,属于完全NP问题,而遗传算法在解决组合排列问题方面占有很重要的地位。针对TSP问题,提出了一种改进的遗传算法。利用交挟启发交叉算子和可变交叉概率实现局部搜索,加快算法的收敛速度,利用变挟变异算子和可变变异概率维持群体的多样性防止算法早熟收敛。Java仿真实验结果表明,改进后的算法明显优于传统的遗传算法,说明该算法具有良好的有效性和可行性。
TSP （traveling salesman problem） is also referred to as traveling salesman problem. TSP is NP-complete problem, and genetic algorithms （GA） whichresolvestheproblemofcombinationarrangementoccupiesaveryimportantposition. A modified genetic algorithm is suggested. By employing exchange heuristic crossover operator and variable crossover probability to achieve local search algorithm, which accelerates convergence, by employing the mutation operator and variable mutation probability to maintain the diversity of groups, which prevents genetic algorithm to convergence in advance. Through Java simulation results show that the improved algorithm is superior to the traditional genetic algorithm and has good validity and feasibility.
出处
《计算机工程与设计》
CSCD
北大核心
2007年第24期5909-5911,共3页
Computer Engineering and Design
基金
国家电子信息产业发展基金项目(信运部[2005]635号)
