应用改进的遗传算法求解TSP问题

旅行商问题,也称货郎担问题,属于完全NP问题,而遗传算法在解决组合排列问题方面占有很重要的地位.针对TSP问题,提出了一种改进的遗传算法.利用交换启发交叉算子和可变交叉概率实现局部搜索,加快算法的收敛速度,利用变换变异算子和可变变异概率维持群体的多样性防止算法早熟收敛.Java仿真实验结果表明,改进后的算法明显优于传统的遗传算法,说明该算法具有良好的有效性和可行性.

Based on improved genetic algorithm for TSP

TSP (traveling salesman problem) is also referred to as traveling salesman problem. TSP is NP-complete problem, and genetic algorithms (GA) which resolves the problem of combination arrangement occupies a very important position. 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.