一种基于遗传算法求解TSP问题的优化算法  

A Optimization Method Based on Genetic Algorithm for Solving TSP

作　　者：韩凤娇[1] 

机构地区：[1]西南大学计算机与信息科学学院,重庆400715

出　　处：《网络安全技术与应用》2012年第7期36-39,共4页Network Security Technology & Application

摘　　要：旅行商问题是组合优化的一个经典问题,也是评价算法好坏的一个标准,它要求在给定的一张图中寻找一条哈密尔顿回路,使得该回路在所有的回路中长度最短。然而,该问题是一个NP完全问题,其求解时间会随着问题规模的扩大急剧上升。因此,只能希望在允许的时间内寻求问题的一个较优的解来替代。本文借助生物学的相关理论与思想采用遗传算法对该问题进行求解,最后通过对遗传算法的进一步分析,提出了一种可行的改进算法,达到了获得较优解的目的。Traveling salesman problem is a classic combinatorial optimization problem,but also a standard quality assessment algorithm,it calls for a given picture in search for a Hamilton loop to make it in all the loop of the circuit shortest length.However,this problem is a NP complete problem;the solution time will rise sharply with the expansion of the scale.Therefore,we can only hope in allowing time for problem a relatively optimal solution to replace.This essay based on the related theories and thoughts of biology,using genetic algorithm to solve the TSP problem,and eventually puts forward a feasible and improved algorithm to get the optimal solution through further analysis of the genetic algorithm.

关 键 词：遗传算法 TSP问题 NP问题 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]