遗传算法在TSP问题中的应用

摘要:文章首先介绍TSP问题与遗传算法的基本特点及其基本步骤。接着讨论用遗传算法解决TSP问题的编码、适应度函数设计方面的采用的方法,以及选择算子,交叉算子和变异算子的应用现状以及效果,最后对解决TSP问题的前景提出了展望。

关键词:TSP;遗传算法;遗传操作;算子

中图分类号:TP311 文献标识码:A文章编号:1009-3044(2010)03-672-02

Application in TSP Based on Genetic Algorithm

LI Hua-zhong, YANG Jing-hua

(Computer Science and Technology Institute of Hua Yu College from Henan Agricultural University, Shangqiu 476113, China)

Abstract: First, the passage introduced the problem of TSP, the basic feature and procedure of Genetic algorithm. Then discussed the way of coding, the function of fitness of solving TSP by Genetic algorithm. The application and effect of selection operator, crossover operator and mutation operator. At last, how to solve TSP in the future will be given.

Key words: TSP; genetic algorithm; genetic operation; operator

旅行商问题(TSP),也称为货郎担问题,是一个较古老的问题。最早可以追溯到1759年Euler提出的骑士旅行问题。1948年,由美国兰德公司推动,TSP成为近代组合优化领域的一个典型难题。应该说,TSP是一个具有广泛应用背景和重要理论价值的组合优化难题,它已经被证明属于NP难题。对TSP问题的大量研究使得TSP问题成为了一个著名的组合优化问题目前,求解TSP问题的较为常用的方法有二叉树描述法、启发式搜索法、最近邻法、神经网络法、模拟退火法和遗传算法等。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局概率搜索算法,具有良好的全局寻优能力,成为解决问题的有效方法之一。

1 TSP问题描述

TSP(旅行商问题)的简单描述是:一名商人欲到n个城市推销商品,每两个城市i和j之间的距离为d,存在i,j如何使商人每个城市走一遍后回到起点,且所走的路径最短。用数学符号表示为:设n维向量表示一条路径X=(C1, C2, ……,Cn),目标函数为

minF(x)=∑n+1i=1d(Ci,Ci+1)+d(C1+ Cn)

用图语言来描述TSP,给出一个图G=(V, E),每边e∈E上有非负权值w(e),寻找G的Hamilon圈C,使得C的总权W(C)=∑e∈E(C) w(e)最小。TSP搜索空间随着城市数n的增加而增大,所有的旅程路线组合数为(n-1)!/2。5个城市的情形对应120/10=12条路线,10个城市的情形3628800/20=181440条路线,100个城市的情形则对应有4.6663×10155条路线。在次庞大的搜索空间中寻求最优解,对于常规方法和现有的搜索而言,存在诸多的计算困难。借助遗传算法的搜索能力解决TSP问题是很自然的想法。

2 遗传算法的特点及基本步骤

2.1 遗传算法的特点

遗传算法是模拟达尔文的“适者生存” 的自然进化论与蒙德尔的遗传变异理论而提出的一种求解复杂系统全局优化问题的通用计算框架。它的主要特点是群体搜索策略和群体中个体之间的信息交换。它适用范围于处理传统搜索方法难于解决的复杂和非线性问题。可广泛用于组合优化,机器学习.自适应控制,规划设计和人工生命等领域。遗传算法是一种有向随机搜索法,其遗传算子原则上执行盲目搜索,体现了随机搜索的特点,故能广泛搜索整个解空间而跳出局部。通过不断计算各染色体的适应值,选择最好的染色体,从而获得最优解。基于遗传算法的本质是处理复杂问题的一种启发性随机搜索算法故用于TSP是有效的。

2.2 遗传算法的基本步骤

遗传算法是通过借鉴生物界自然选择和自然遗传机制而产生的一种计算方法,与其他的优化算法一样,遗传算法也是一种迭代算法。从选定的初始解出发,通过不断地迭代,逐步改进当前解,直到最后搜索到最优解或满意解。其迭代过程是从一组初始解(群体)出发,采用类似于自然选择和有性繁殖的方法,在继承原有优良基因的基础上生成具有更好性能的下一代解的群体。遗传算法的运算过程为:对给定问题,给出变量的编码方法,定义适应度函数。1)初始化。令t=0,给出正整数(最大迭代次数),交叉概率Pc及变异概率Pm,随机生成M个个体作为初始群体P(0);2)个体评价。计算P(t)中各个体的适应度;3)选择。对群体P(t)进行选择操作,得到中间群体;4)交叉。把交叉操作作用于中间群体;5)变异。把变异操作作用于交叉之后所得到的群体,则得到第(t+1)代群体P(t+1);6)若t

3 遗传算法用于TSP问题

3.1 编码表示

用遗传算法求解TSP时,算法的编码表示是算法设计的重点,它对遗传基因的操作有一定的限制。TSP的编码策略主要包括二进制表示、顺序表示、路径表示、矩阵表示和边表示等。由于二进制编码具有如下的特点数据冗长,并且表达能力有限,计算机无法承受如此巨大的计算量甚至根据调整不同的参数时,所运行的时间,有时会达到近几个小时,从时间效率来说,工作效率实在是低下,并达到无法忍受的程度,所以实际中很少使用。顺序表示是指将所有城市依次排列构成一个顺序表,对于一条旅程,可以依次旅行经过顺序处理每个城市,每个城市在顺序表中的顺序就是一个遗传因子的表示。每次处理完一个城市,从顺序表中去掉该城市。处理完所有城市后,将每个城市的遗传因子连接起来,即成为一条旅程的基因表示(染色体编码)。

路径表示是表示旅程岁应的基因编码的最自然,最简洁的表示方法。

3.2 初始化群体和适应度函数及其终止条件的设定

根据编码方法,随机产生初始群体,直到达到所需规模为止。适应度函数,由于是求最短路径,适应度函数一般采用求函数最大值,例如取路径总长度T的倒数,即fitness=l/T。其中,

T=∑n+1i=1d(Ci,Ci+1)+d(C1+ Cn)