摘要
旅行商问题是算法应用中的基本问题,遗传算法具有通用性、智能性、鲁棒性、全局性和并行性的特点,正好适合于该问题的求解。但基本遗传算法在解决旅行商问题时效率不高,并且容易陷于局部最优解。为了解决这一问题,提出了一种改进的遗传算法。文章首先对旅行商问题进行了描述,对遗传算法进行了介绍,对其中的个体选择、交叉算法等重要因素做了一定地改进。最后,用一个简单的实例对基本遗传算法和改进的遗传算法进行了比较,发现改进的遗传算法在解决旅行商问题上的效率问题上有了一定的提高。
TSP is a basic issue in the application of algorithm,and the genetic algorithm is universal,intelligent,robust and overall.It is just these characteristics that are suitable for solving the TS problem.But the efficiency of the basic genetic algorithm to solve the traveling salesman is not high,and the algorithm easily results in a local optimal solution.In order to solve this problem,a modified genetic algorithm is found.The article first describes the traveling salesman problem,and then introduces the genetic algorithm,of which it improves important individual choice,cross-algorithm etc.factors.Finally,the standard genetic algorithm and modified genetic algorithm are compared by a simple example and find that the efficiency of the modified genetic algorithm to solve the traveling salesman problem is higher in some extent.