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

韩凤娇

西南大学计算机与信息科学学院 重庆 400715

0 引言

旅行商问题是经典组合优化问题，也是一个NP完全问题。它的求解会随着问题规模扩大而导致求解时间急速增长。为此我们可以利用遗传算法这一智能的算法，来试图获得问题的较优解，并通过反复改进实验最终寻求较快较优解决方法。

TSP即旅行商问题或称货郎担问题，该问题描述为：有n个城镇，其中任意两个城镇间都有道路(若没有则规定该边上的权值为+∞)。一个售货员要去这n个城镇售货，从某城镇出发，一次访问其余n-1个城镇且每个城镇只能访问一次，最后又回到原出发地。问售货员要如何安排经过n个城镇的行走路线才能使他走过的路程最短。

求解旅行商问题，其实质是在一个赋权图中寻找一条权值最小的哈密尔顿回路。哈密尔顿回路是指：有任意图G=(V，E)，G中进过所有节点一次且仅一次(除起点重复一次)的圈。从中也可以看出，旅行商问题是一个最优化的求解问题，它要求问题的解满足以下三点：(1)它必须是一条回路；(2)该回路能够经过每个事先给出的城镇且不重复访问已经过的城镇；(3)回路的路径长度是所有可以满足(1)、(2)的若干回路中最短的。

1 遗传算法介绍

遗传算法(Genetic Algorithm)是一类借鉴生物界的进化规律(适者生存，优胜劣汰遗传机制)演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，已被人们广泛地应用于组合优化、机器学习、信号处理和人工生命等领域。

遗传算法的基本运算过程如下：