一种用于TSP问题的改进免疫遗传算法研究

摘要:受生物免疫原理启发而产生的人工免疫算法,是一种新型的随机启发式搜索算法。基于生物免疫系统机制,本文提出了一种改进的用于TSP优化的免疫算法。算法包括初种群优化,免疫选择,交叉,变异,同时采取免疫记忆,免疫网络促进与抑制操作。文中详细讨论了算法的相关概念及算法步骤,通过对TSP测试数据[6]进行仿真实验,实验结果表明了本文的改进算法的有效性。

关键词:免疫遗传算法 TSP 初始种群优化

1 引言

遗传算法(Genetic Algorithm,简称GA)[1]是一种常用的大规模并行搜索优化算法,它模拟了达了达尔文“适者生存”的规律和随机信息交换思想,仿效生物的遗传方式。从随机生成的初始解群出发,采用选择、交叉、变异等算子进行操作,产生优于父代的子代,如此循环执行,使优化过程以大概率趋于全局最优。但其本身还存在许多不足,尤其在解群分布不均匀时易出现末成熟收敛,陷入局部极优,其原因在于GA中基于适应度的多样性保持策略没能保持群体的多样性。

为了解决上述问题,文献[2-5]提出了使遗传算法具有免疫功能的免疫遗传算法。其算法一般包括六大块组成:抗原的识别,初始抗体的产生,适应度计算,向记忆细胞分化,抗体的促进和抑制,抗体产生(选择,交叉,变异)。

免疫遗传算法既保留了遗传算法的搜索待性,克服了遗传算法在局部搜索解空间上效率较差的缺点,又在很大程度上避免末成熟收敛。但由于其每一代种群的产生仍只通过简单的遗传算子(选择,交叉,变异)产生,收敛效果不是很理想,因此,本文提出了一种针对上述情况的用于TSP(Traveling Salesman Problem, 旅行商问题)的改进免疫算法。文中首先描述用于TSP寻优问题的改进免疫算法的实现过程,然后通过对TSP问题测试数据进行仿真。仿真结果说明该算法收敛速度快,较易实现。

2 旅行商问题(TSP)

Traveling salesman prolem (TSP)问题是经典的NP难问题,是典型的组合优化问题,具有很强的应用背景,例如,VISI芯片设计,路径优化,网络路由,机器人控制等许多问题都可以建模为TSP问题。TSP问题其核心思想就是要寻找一条遍历L个城市的最短路径,在数学上可以描述为以下优化问题

其中,C为城市集合,为城市编号,i=1,2,3,……, ,为编号i和j的两城市之间的距离。

3 用于TSP的改进免疫算法描述

3.1 基本概念

抗原:算法中的抗原一般是指城市之间的距离距阵,及其约束条件(距离最小)

抗体:算法中的抗体一般是指生成的各个路径

抗体与抗体之间的亲合度:用于表明抗体之间的相似度,本文采用基于信息熵的亲合度计算[5],即:

式中为抗体之间亲合度,为抗体u与v的平均信息量

抗体与抗原之间的亲合度:用于表明抗体对抗原的识别程度,本算法中抗体与抗原的亲合度定义为:最长路径值和抗体的路径长度值之差及其与所有差值和之比

式中 为城市个数,为城市距离中最大两城市之间的距离,为存在的可能最大路径值

式中 表示抗体与抗原之间的亲合度, 表示路径 的长度值。

3.2 算法描述与算法步骤

如果把实际求解问题的城市距离视为外来入侵的抗原,那么,免疫响应中产生的抗体视为问题的解,则不同亲和度抗体的进化与成熟机制就是寻找最优路径(路径值最短)。本文的改进算法主要是针对传统的遗传算法以及文献[9]所使用的基于信息熵的免疫遗算法的收敛效率问题所提出来的。算法采用实数编码,减少二进制编码的计算量,提高了搜索的效率;引入抗体群优化策略,可以在初始或经遗传算子进化生成的种群中提高抗体与搞原的亲合度,从而提高算法的搜索效率。

本文算法的主要步骤如下:

步骤1: 算法初始化:抗原输入及参数的设定:输入城市坐标值(或随机生成坐标值),并通过欧几里得距离计算公式:

计算抗原值;

同时设定种群规模N,相似度阈值γ, 交叉率Pm,变异率Pc;

步骤2:抗体的编码:抗体的编码采用实数编码,抗体的长度为N(城市的个数)

步骤3:产生初始抗体群,记忆库:先检查记忆库,如果为空则在可可行解空间随机产生初始抗体群,否则,从记忆库中选择和随机产生的其余抗体共同组成初始抗体群。

步骤4:抗体种群的优化:由于TSP问题的任何一条路径都是闭合路径,则从任一城市出发,要到达的下一个城市选择为未到过的城市中距离该城市最近的一个,这样更能使种群朝着有利方向收敛。

步骤5:对上述抗体群体进行评估:计算抗体与抗原适应度值及各抗体的浓度值,

以个体选择率为标准进行评估。定义选择率为,,式中,表示抗体与抗原的亲合度,表示抗体的浓度。抗体的浓度是指抗体群体中相似抗体所占的比重,即: =与抗体i相似度大于γ的抗体数/N;

步骤6:将抗体种群基于选择率进行选择操作,再对选择出的抗体实施交叉、变异操作。

步骤7:记忆优良个体:计算变异后的抗体群体的亲和度,选择高亲和度的抗体,加入记忆细胞库。

步骤8:终止条件判断:判断是否满足终止条件;是则算法结束;否则返回步骤4.

步骤9:输出最优路径。

4 仿真实验及分析

为了测试本文算法的性能并和相关算法进行比较,本文分别选用国际上通用的TSP测试库中的Eil 51-cities和Berlin 52-cities数据为例进行测试[6]。

相关参数:种群数目N:100,交叉率Pc=0.7变异率Pm=0.1, 相似度阈值γ=0.02

方法一:遗传算法;

方法二:文(5)中所提的基于信息熵的免疫遗传算法;

方法三:本文方法;

其运行的结果如下列图:

在相同参数设置下,从图1中我们看到在100次迭代次数以内,本文算法算法具有较快的收敛性,从图2中我们看到虽然最终三种算法都能求得最优解,但采用不同的算法,收敛速度不同,而本文的算法明显优于GA与IGA,其在170代左右就能求得最优解,而GA与IGA由分别需650代与340代左右。综合上述仿真实验结果可知:本文提出的用于TSP优化路径与相关算法比较,它能够在较少的迭代代数下,求出最优解,加快点收敛的效率。

5结语

本文是基于生物免疫系统机制,在文[5](基于信息熵的免疫算法)的基础上,提出了一种改进的用于TSP路径优化的免疫遗传算法。文中详细的讨论了该算法的步骤和过程,最后对两测试数据包进行了实验仿真,并和相关算法进行了比较,初步仿真实验结果表明:本文提出的算法应该有效的, 值得进一步研究和应用于实际复杂问题的优化计算中。

参考文献

[1] 云庆夏编著.进化算法[M].北京:冶金工业出版社,2OOO-05.

[2]高岩,位耀光,付冬梅,张蔚.免疫遗传算法的研究及其在函数优化中的应用.《微计算机信息》,2007,23(6):183～184.

[3] 杨孔雨,王秀峰.免疫记忆遗传算法信其完全收敛性研究.计算机工程与应用,2005,12:47～50.

[4] Jiao L C,WangL.A novel genetic algorithm based immunity.IEEE Transactions on System Man,and Cybernetics,2000,30(5):552~561

[5] 杨四海,TSP的等价解及其对免疫遗传算法的干扰.华侨大学学报(自然科学版)1期,2007年1月.

[6] 焦李成,杜海峰,刘芳,公茂果,免疫优化、计算、学习与识别,2006-6,408～412.

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文