基于遗传算法的免疫算法对TSP问题的改进与研究

李月

(中国传媒大学 计算机学院，北京 100024)

基于遗传算法的免疫算法对TSP问题的改进与研究

李月

(中国传媒大学 计算机学院，北京 100024)

基于生物学种群遗传原理的遗传算法，在解决种群迭代次数过多的复杂问题中，由于遗传算子总是以随机的方式来迭代子代种群，在遗传过程中难免会出现退化的现象，因此引入免疫算法来对其进行改进。通过增加免疫算子，即抽取问题的特征信息，经过疫苗检验和退火选择降低算法的退化概率，从而对遗传算法进行了改进。最后，应用TSP问题来具体说明免疫算法是如何对遗传算法进行优化与改进的。

遗传算法；免疫算法；TSP问题

1 引言

近年来遗传算法应用非常广泛，其基于生物学 “物竞天择，适者生存”种群遗传原理来解决了很多传统方法很难解决的复杂问题，比如组合优化类问题、工程类问题、图像处理等等，就连机器人领域也有遗传算法的应用。但在解决问题的过程中遗传算法也暴露了很多问题，为了解决这些问题，又引进了另一个同样基于生物学原理的算法——免疫算法。免疫算法通过生物学免疫原理改进了遗传算法，解决了遗传算法的退化问题。本文通过使用TSP问题来研究免疫算法对遗传算法所做的改进。

2 遗传算法

2.1 遗传算法生物学原理

遗传算法顾名思义就是依据遗传学衍化过来，它的生物学原理是根据生物学家达尔文所提出的进化论。它来源于自然选择。而自然选择的核心概括为三方面：遗传、变异和选择。

遗传就是子代继承亲代，并保持相似的特性。自然界中的生物都有遗传性，亲代将自身的信息遗传给子代，因此子代就可以保持和亲代相同或者相似的性状，就是这个特性，才使得物种能够在生物界中稳定的存在。遗传学进步很大程度上促进和推动了进化论。

变异和遗传不同，它体现出了不同子代之间以及子代和亲代之间的差异性表现，生物因为就了变异的基因才能产生生物个体之间的不同。而变异则是随机发生的，变异的选择与积累使得生命体之间产生多样性。它为生物的进化发展产生了可能。

选择就是指生物体本身具有淘汰与保留的特征，它决定了生物进化的方向。生物上指的是自然选择，也就是适者生存。自然界中的生物通过互相生存斗争选择出存留下来的生物基因，从而形成了自然选择。因此具有了适应性变异特征的生物体将被保留下来，相反不具有的个体将被自然界所淘汰，那些有利于生物生存下去的的变异基因就遗传下去，日积月累，经过了一代代的生存环境的选择，逐步产生了新的物种。

染色体是生物的遗传性状的主要载体，基因通过染色体将特性传递给后代，而上问所讲的三个内容都是通过染色体来实现的。生物的进化论表明了自然界中的生物通过长期自然选择的进化，科学家们从中获得启发，将自然选择过程中蕴含的一些优秀的思想应用于工程技术领域，发展成为遗传算法。

2.2 遗传算法原理

遗传算法简称GA，Genetic Algorithms，是由美国Holland教授提出的仿照自然界的生物的遗传特性以及进化论从而形成的一种随机搜索最优化方法，又叫基因进化算法，或进化算法[1]。属于启发式搜索算法一种。 “优胜劣汰，适者生存”是生物进化理论最为核心的思想，遗传算法将其深化，把生物进化这种奇异的本领看成一种值得效仿的东西。遗传算法在应用于实际中的问题时，针对于优化问题抽象为编码，每一个编码内容表示为一个个体，而个体的组合称为群体。首先选择适应度函数将这些个体编码进行筛选，并通过遗传学当中的基因复制、交叉以及变异的方法，保留适应度高的个体，这种方法可以保证当前选择的群体中拥有很高适应度的个体将以更大的概率被保留，这些被保留的个体将通过繁衍和复制得到新的种群，新的种群将会继承上一代的基因信息，并且比上一代更加优秀。通过这样一代代传承，种群中个体适应度将会不断提高，直到这些个体达到了一定的条件。[1]

算法流程如图1所示：

图1 遗传算法流程

(1)要产生初始群体，这里的群体概念就如上文提到的，是由通过某一编码方式表示的个体组成的。这里选择二进制进行编码，基因是用0或1表示，还有其他方法比如互换编码，这种编码常用于解决排序问题，在著名的旅行商问题中，通过遍历题目中的城市，形成的序列可以通过一串基因编码来表示。还有树形编码和值编码等等，不同的实际问题可以选择不同的方式进行编码。

(2)计算群体中每个个体的适应度值，这里会涉及到适应度函数这个概念。适应度函数的解可以评价遗传算法个体的好坏，适应度函数的结果值越大，就越接近最优解，也表明了个体更优。因此，必须在这个过程中，我们需要确定一种转换规则，这种规则可以使目标函数值和个体适应度函数之间发生转换。

(3)选择算法，这一步选择了个体中优秀的基因，适应度高的个体将以更大的概率遗传到下一代群体中，反之则被淘汰。根据轮盘赌选择算法，个体被选中的概率是与一个比值相关，这个比值是由个体的适应度函数值与群体中所有的个体适应度函数的和来决定的，值的大小为两个的比值。

(4)交叉运算，根据两个配对的生物体，将他们的染色依据设定好的交叉概率将他们之间的部分基因进行交换，因此将产生出两个新的个体。其中的交叉方式也有很多对应于二进制编码，有单交叉点法、双交叉点法等等。

(5)变异，个体的基因编码会根据变异的概率被其他基因所取代，由此产生出新的个体，变异决定了局部搜索，并保证了种群的多样性。单一般变异概率比较小，而交叉概率通常情况下设置的较大。最后产生新一代群体，这几个步骤一直循环，一直到满足停止准则就可以跳出。这里的停止准则可以理解为连续N代后的子代种群的最优的个体适应度都小于等于父代最优个体的适应度，就可以终止运算，但是不同的实际问题这里的终止条件不同。

2.3 遗传算法的优劣

遗传算法可以应用在很多领域，原因就在于它的特点：

•遗传算法的操作对象是经过编码得到的参数，并不是原参数，这样的好处是与问题领域无关可以快速随机的搜索。而且搜索通过使用评价函数来进行启发，过程简洁，但是功能很强大。

•鲁棒性强：遗传算法通过“适者生存”这一进化原理，能在不同问题中通过在功能之间的协调平衡从而达到很高的生存能力。

•遗传算法是群体搜索，可以使用并行处理，并不是通过没有目的的穷举，而是基于启发式的搜索方法。

遗传算法的优点绝对不止上面三条，但是除了优点，还有一些缺点更值得我们关注：

•在实际过程中会发生早熟收敛问题.

•由于遗传算子产生于一定的条件概率下，迭代搜索过程是随机的，因此这些算子能使群体中的个体发生进化，也会使他们发生退化。

2.4 遗传算法的应用

(1)函数优化。遗传算法的一个非常典型的应用领域是函数优化，也是评价遗传算法性能的常用方法。在解决函数优化问题时，相比起其他算法，该算法在针对非线性、多模型、多目标这类特殊问题时表现极好。

(2)组合优化。在问题空间非常大的条件下，对于从复杂的组合问题出优化出最优解，遗传算法效果最好。例如，旅行商问题、装箱问题、背包问题等等，这些问题再采用传统方式时，则变得很难解决。[2]

(3)机器人。在使机器人变得更加智能的过程中，也离不开遗传算法的帮助。遗传算法可以为机器人规划行动路径，对于机器人各个关节结构的协同运转也起到了很关键的作用。

(4)在图像处理、生产调度等问题也有很好的应用。

3 基于遗传算法的免疫算法

3.1 免疫算法生物学原理

图2是免疫算法的生物学原理，抗原与T细胞接触，被T细胞的受体识别，把自身的信息传递给T细胞，从而活化了T细胞。活化的T细胞通过分泌淋巴因子来进一步活化B细胞，促进B细胞活化、增值与分化，并产生抗体来与抗原进行结合，抗体在产生过程中也会经过选择、交叉和变异等过程更新抗体群体；在这个过程中，抗原与抗体以及抗体与抗体之间互相的刺激和抑制关系维持着免疫平衡[4]。而图中的记忆细胞也是T细胞分化成的，这些记忆细胞会保存抗原侵入的一些信息，等到再有同样的抗原侵入时会立刻产生大量特异性抗体。

图2 生物免疫机制的抽象模型

3.2 免疫算法的基本原理及对遗传算法的改进

上章的内容中，介绍了遗传算法的缺点主要因为遗传算子总是以随机的方式进行子代迭代，因此在遗传过程中会出现退化的现象，而且在求解过程中，遗传算法对特征信息利用也明显不够。很多实践以及理论表明，仅仅通过遗传算法在研究很多复杂问题上还是远远不足的，因此借助其他算法的优秀的相关知识与理论和遗传算法结合起来是很有必要的，可以很大程度上提高算法的整体性能。这里可以引入免疫算子相关操作。因此该算法的核心在于考虑免疫算子的构造，免疫算子包括两个步骤来确定，一个是为了提高子群适应度而对个体进行接种疫苗，另一个是为了避免发生退化来进行免疫选择[5]。

免疫算法针对遗传算法的步骤进行了改进(如图3)。

图3 免疫算法的流程示意

(1)初始化抗体群体，提取出求解问题的基本特征。这里涉及疫苗的概念，这里的疫苗实际上是对实际问题中的目标函数和约束条件的描述，这些先验知识的提取就是抽取疫苗，而在免疫算法中抗原在实际问题中对应的就是要求解的问题。

(2)计算抗体的适应度当满足条件时停止，否则就进行交叉和变异操作，根据不同的抗体和抗原的亲和力值的高低，使用轮盘赌选择两个抗体，以一定的概率将这两个抗体变异编码基因，再进行交叉操作后，最终可以得到到新的抗体。

(3)整个免疫算法的核心。

首先介绍一下免疫算子，在生物原理中的免疫系统由两种免疫机制，特异性和非特异性免疫，它和这两种免疫方式相对应，分别为目标免疫和全免疫。全免疫是在初始化阶段进行的，即群体中每个个体发生变异后，每个环节都要发生一次免疫；而目标免疫就顾名思义是在特定点发生免疫反应，它在伴随着每代抗体群体进化的过程中都发挥作用。免疫算子包括接种疫苗和免疫选择两个内容，接种疫苗是按照疫苗，也就是实际问题抽取出来的先验知识对个体某基因位做出修改，得到的个体将以更大的概率拥有更高的适应度[4]。

免疫选择在注射免疫之后执行，它分为两步，首先检测接种的疫苗，如果他的适应度低于它的父代，说明发生了退化，说明这个个体不如他的父代，因此用父代代替这个个体。相反，如果子代的适应度高，那他将作为新的父代，继续执行下一次迭代。第二步是退火选择，依赖于适应度函数的结果，以一概率选择子代群体加入新的父代群体。整个流程的最后一步就是更新群体，并且迭代循环这个过程。在免疫算法的流程中，疫苗非常重要，它决定了算法的运行效率，但是它的好坏并不影响算法收敛性，而疫苗只会影响免疫算子中的接种疫苗这一步[5]。

3.3 免疫算法的应用及现状

免疫算法从提出至今，在不断改进的基础上，其功能越发强大，而它的应用领域也越来越多：包括在TSP组合优化问题、图像处理、机器人(多智能体决策系统和分布式自动机器人系统等)、人工神经网络的规划等等问题都有其应用，领域涉及非常广泛。但是由于免疫算法发展并不如遗传算法那么好，在很多方面需要投入更多的研究。第一个问题就是免疫算法性能的研究，其中最低程度上包括了收敛性问题以及有效性等等，但目前相关的研究成果不多。还有就是免疫算法和其他算法的对比研究也并不深入，这个研究对于认识人工免疫系统特点有很重要的意义。

4 两种算法TSP问题的比较

TSP问题称为旅行商问题，假设一个旅行商人要去n个城市，他需要选择行走路线，从而达到每个城市只能走一次，最终回到原点城市，路径选择的目标是得到最短路径。这是一种组合优化问题。而组合优化问题会在很多部分中产生极值点，复杂性比较强，因此想要准确求出问题的最优解采用传统方法是很困难的。

4.1 遗传算法求解TSP问题的思想

对于遗传算法来说，解决的重点包括编码方案的选择，适应度函数的设计，如何设置约束条件，以及选择机制等等内容，这些问题解决好了，对于求解实际问题来说就能使遗传算法可以发挥它的优势。

(1)编码方案 在TSP问题中，由于最终目标是找到一条路径策略，使得路径之和最小，并且每个城市且只能出现一次，最终回到初始城市，所以这里使用二进制编码就不太合适，可以使用互换编码，即把一个城市节点看做一个基因，编码遍历过得城市序列。

(2)适应度函数 适应度函数可以评价出一个个体的优劣，对每个个体进行评估，它是算法的关键，在实现优胜劣汰起到重要的作用。还是研究待求解问题，找出一条路径之和最小的解，因此可以把路径之和的倒数作为算法的适应度函数。路径越短，分数越高。即

(1)

其中Td表示这个个体的总路径长度。

(3)选择运算 选择算法的目的是选择适应度值高的个体，赋予它高概率进行后代遗传，这是优胜劣汰最重要的一步。在这里使用轮盘赌选择方法，把该个体的适应度值和群体适应度总值计算比值，得到的结果作为这个个体的遗传概率。因此公式为

(2)

(4)交叉 首先要设置交叉概率，交叉概率应该设置的比较大，可以设置为80%或者更高，这样可以让得到更多的交叉新个体。最好的解决方式是采用自适应的方法。交叉方式有很多种，这里可以采用部分匹配交叉的方式，简单举个例子来说明部分匹配交叉方式。

A= 3 1 ‖ 2 4 5 ‖6 7 8

B= 5 2 ‖ 8 6 3 ‖7 1 4

将这两个个体进行交叉，来获得新个体

A’=3 1 ‖ 8 6 3 ‖6 7 8

B’=5 2 ‖ 2 4 5 ‖7 1 4

可以看出得到的两个个体中里面有重复的城市号，因此需要将这两个进行调整将A’第一个3替换成B’最后一个4，将A’中倒数第三个6替换成B’中第二个2，将A’中最后一个8替换成B’中第一个5，得到结果如下：

A”=4 1 ‖ 8 6 3 ‖2 7 5

B”=8 6 ‖ 2 4 5 ‖7 1 3

(5)变异 变异是基于变异概率来执行，变异概率应当设的很小，一般为0.05，变异有两种方法，一种是内变异另一种是外变异，内变异指的是个体内部两个基因互换，是自己内部发生的一种变异；外变异指的将某一基因用外部基因替换。在TSP问题中使用内变异更加合理，这样可以由一个初始串经过变异得到很多新的个体。

但是交叉或者变异的结果有时可能是无效解，这时候可以选择抛弃这个个体，生成新的有效个体，也可以人为的进行调整。而交叉概率和变异概率有时候会给结果带来截然不同的结果，可能会使算法退化。

4.2 改进遗传算法

免疫算法在改进遗传算法的问题上主要有疫苗的提取和免疫算子构造这两方面，因此主要介绍这两个问题在解决TSP问题上的是如何实现的。

(1)抽取疫苗 疫苗是问题的特征信息，在解决问题的过程中，时刻以问题的特性作为我们的参考依据。首先要做的就是分析TSP问题，当处于某一城市，首先应当选择离自己最近的一个城市作为下一个目的地，但是如果最近的城市是走过的城市，就取次近的城市作为下一个节点，以此类推。因此可以把这个策略作为疫苗。

(2)免疫算子的构造 注射疫苗：在一个个体上，随机选取某一基因也就是某一个城市，按照上述疫苗描述将选定的下一个城市节点写到该城市的后面，并将这个选定的下一个城市节点从之前的位置删除。例如图4所示。

图4 城市遍历示意图

原来的序列为123456，我们选定2号城市，离它最近的是5，因此我们将5移到2之后，将5原来位置删去，得到的序列为125346，在由253组成的三角形中，d25一定为最短边，而在由456组成的三角形中，d46就不一定。因此多数情况下我们可以得到d25+d53-d23

疫苗检测：这个步骤中和之前在介绍原理时所介绍的一样，新的子代和父代进行比较，选择好的作为新的父代，然后在执行退火选择算法，其中的概率表达式为：

(3)

其中，f(xi)为适应度函数。

5 总结

遗传算法采取了自然界中适者生存的理念，将遗传学的内容引入到工程技术中，解决了很多问题，这是一种随机的，启发式的算法，每一代都以高概率遗传优秀的个体，并且得到优秀后代，通过交叉、变异等操作，一代代进行迭代，最终产生最优的个体。虽然遗传算法自身存在缺陷，但是这种算法实现简单，功能强大，是很多后续算法的基础。

针对遗传算法出现退化现象以及对于问题的特征信息的关注度不高的问题，引入了免疫算法，基于遗传算法的免疫算法增加了疫苗的概念，即对问题分析，抽取他的特征信息，在最重要的免疫算子阶段注射疫苗，并且通过疫苗检验和退火选择降低算法的退化概率，从而增强了算法的功能。

免疫算法实际上依据的生物原理是免疫系统，将问题抽象为抗原，抗体作为解决问题的解，通过交叉变异以及免疫算子等操作，得到相对而言最优的抗体。免疫算法和遗传算法很多思想相似，但是应用的生物学背景不一样。免疫算法较遗传算法在处理很多问题上更加有效，对于多峰值的搜索问题也更加高效并且准确，免疫算法在应用领域上完善了遗传算法，而他并非仅仅是改进遗传算法，而且用有更大的发展前景，目前免疫算法的研究还不是那么深入，有很多领域值得研究，在未来相信免疫算法会有更大的发展。算法之间的结合来解决实际问题也有着更多实用价值，毕竟一种算法总是有他的局限性，通过几种算法的结合，相信会发挥更大的作用。

[1]陈国良，王煦法，庄镇泉.遗传算法及其应用[M].北京：国防出版社，2001.

[2]王宏生，孟国艳.人工智能及其应用[M].北京：国防工业出版社，2009.

[3]陈光.遗传算法在人工智能中的应用[J].福建电脑，2005，(11)：40-41.

[4]王磊，潘进，焦李成.免疫算法[J].电子学报.2000，(07).

[5]吴昳恬.基于免疫算法的TSP问题求解[J].科技信息，2011，(36)：451-452.

[6]TangZ，YamaguchiT，TashimaK，etal.Multiple-valuedimmunenetworkmodelanditssimulations[C].Proceedingsofthe27thInternationalSymposiumonMultiple-valuedlogic，Autigonish，Canada，May28-30，1997：233-238.

[7]王小平，曹立明.遗传算法理论应与软件实现[M].西安：西安交通大学出版社，2002：129.

[8]王煦法，等.一种基于免疫原理的遗传算法[J].小型微型计算机系统，1999，20(2)：117-120.

[9]孙晓亮.邵定宏基于疫苗接种的免疫算法[J].计算机工程与设计，2007，(16).

[10]LeeW，LeeS，LeeBH，etal.AnEfficientPlanningAlgorithmforMulti-headSurfaceMountingMachinesUsingaGeneticAlgorithm[J].JournalofUniversalComputerScience，1999，5(12)：833-854.

(责任编辑：王谦)

Improvement and Research on TSP Problem by Immune Algorithm Based on Genetic Algorithm

LI Yue

(School of Computer Science，Communication University of China，Beijing 100024，China)

Genetic algorithm based on the genetic principle of biological population，in the complex problem of solving the number of population iterations，because the genetic operators always in a random way to iterate the progeny population，in the genetic process will inevitably degenerate，so the immune algorithm is introduced to improve it.By increasing the immune operator，that is，extracting the characteristic information of problems，the degradation probability of the algorithm is reduced by the vaccine test and the annealing method，and the genetic algorithm is improved.Finally，the TSP problem is used to describe how the immune algorithm can optimize and improve the genetic algorithm.

immune algorithm；genetic algorithm；TSP

2017-04-06

李月(1992-)，女(汉族)，北京市人，中国传媒大学硕士研究生.E-mail：nemoly@sina.com

TN

A

1673-4793(2017)04-0058-06