一种改进的遗传算法解决旅行商问题

标准遗传算法在解决旅行商问题时效率不高，容易陷于局部最优解。为了解决这一问题，提出了一种改进的遗传算法。改进后的算法在选择操作时，采取了精英个体保留策略和锦标赛方法，扩大染色体的选择范围，加大了适应度好的染色体被选中的概率；交叉操作时加入父染色体中边的信息；在参数选择上，使交叉概率和变异概率与染色体的个体适应值联系，保护适应度好的染色体进入下一代。用程序实现了两种算法，通过比较，改进后的遗传算法提高了解决旅行商问题的效率。

Modified Genetic Algorithm for Traveling Salesman Problem

Traditional genetic algorithms have low efficiency and tend to be trapped by local optimizations. An improvement is proposed to solve this problem. Elitism and 2-tournament selection are used to expand the selection of chromosomes, so that the ones with better fitness have more chances to be selected. Crossover operation adds the edge information of parents chromosomes. Crossover and multation probability are related to individual fitness, and this guaratees that chromosomes with better fitness can survive into the next generation. Two algorithms are implementd. Experiments show that the new algorithm improvs the efficiency of the traveling salesman problem.