研究人工免疫算法中旅行商问题

0.引言

早在18世纪，爱尔兰的数学家哈密尔顿和英国的数学家托马斯就已经对旅行商问题（TSP）进行数学研究，而旅行商问题一般形式的研究则是由数学家卡尔·门格尔于19世纪三十年代在维也纳和哈佛大学首次进行研究的。对旅行商问题的研究往往是出于把它作为一个可应用于解决大规模的组合最优化问题的一般方法的一个平台，然而这并不是说在很多领域中旅行商问题找不到其具体的应用。事实上，旅行商问题有许许多多的应用，它可以看成是许多领域内复杂工程优化问题的抽象形式，诸如邮路问题、网络布线问题、物流配送问题、电路板钻孔问题等等，这些应用给旅行商问题的研究带来了活力，并且帮助指导今后的研究工作。旅行商问题本身的应用范围正在不断扩张，它的研究方法也正迎来越来越广阔的发展前景。可以看出，不论从理论还是实际应用来讲，研究TSP问题取得的每一步进展都将会有非常重大的意义。

多年来人们一直寻求求解TSP问题的算法，其中有传统的算法如动态规划法、分支极限法等，但由于其仅能用于求解规模较小的TSP问题，在实际应用中的局限性使其无法适用于求解大规模的TSP问题。近年来，现代流行的智能算法也越来越受到研究人员们的广泛关注，当然人们也正在努力的探索，试图用其求解TSP问题。这些算法包括神经网络、遗传算法、蚁群算法等。本文欲用另外一种人工智能算法--人工免疫算法,来求解TSP问题。中国硕士论文网提供大量免费硕士

毕业论文

1.旅行商问题的概述

1.1 旅行商问题的描述：

旅行商问题，简单地说，就是某一旅行商要去n 个城市去旅行，他要把这n 个城市都逛一次而且不重复，最后回到原出发城市,问给定所有城市之间的旅行成本，哪一种旅行路径成本最小？为了简化，成本可理解为旅行商走过的最短距离。即已知n 个城市以及各城市间的距离，某一旅行商从某个城市出发访问每个城市有且仅一次，最终返回原出发城市，怎样走才能使其所走的线路最短？

从旅行商问题的描述来看，似乎其并不是很复杂，理解起来也是很简单，但其的确是一个非常复杂的问题。对于n 个城市的旅行商问题，可供选择的路径数目我们可以这样计算：

旅行商问题( TSP)在数学上可以描述为以下优化问题。

2.人工免疫算法的基本原理2.1 生物免疫系统及其运行机制生物免疫系统是自然界生物所必备的防御系统, 它是一种由众多细胞、分子和组织等子系统构成的复杂系统，这些子系统之间存在着复杂的相互联系，具有识别“自己”和“非己”，消除和消灭异物的功能。生物免疫系统又分为先天免疫系统和自适应免疫系统。先天免疫系统是一种与生俱来的天然防御系统，具有识别一定微生物并消灭这种微生物的能力，但对于绝大数外来侵入病毒的杀伤力较弱，这时候自适应免疫系统就开始发挥它的重要作用了，它能够自适应的学习外来侵入病毒物质或分子的模式结构，中立或消除该种物质。

自适应免疫系统的运行机制可以简单的概括为：在抗原的激励下，巨噬细胞分化抗原为颗粒状物质，抗原呈递细胞将这些物质呈递到巨噬细胞的表面；通过识别的途径，被激活T细胞分化和分泌淋巴因子，并使B细胞应答；B细胞对来自激活的T细胞的信号做出反应——被激活并进行分化和繁殖，分泌出抗体蛋白；抗体缠住、中立并毁灭这些抗原，其他多余的T细胞和B细胞变为记忆细胞。这样反复循环若干代数将最终产生能够消灭抗原的有效抗体。

免疫系统中B细胞的功能主要是产生抗体,抗体由氨基酸排列组成, 氨基酸的不同排列方式形成不同的抗体;而T细胞则主要实现免疫调节功能。

2.2人工免疫系统及人工免疫算法的基本步骤

人工免疫系统即根据生物免疫系统的运行机制构造的一种仿生系统。在构造人工免疫系统时, 首先要构造的就是人工抗原和抗体,在人工免疫系统中, 一个抗体或抗原可以用一个字符串表示，生物抗体由氨基酸的不同排列组成，因此, 人工抗体（字符串）中的字符应相当于生物抗体中的氨基酸。为使人工免疫系统具有与生物免疫系统类似的自我调节机制,可以用亲和力来描述抗体和抗原之间的匹配程度，用浓度来描述每种抗体在整个抗体群中所占份额。抗体和抗原之间的亲和力反映了候选解和最优解的接近程度, 也即反映候选解对约束条件和目标函数的满足程度。对于亲和力较大的抗体作为记忆细胞加以重点保留，又通过浓度调节来保持抗体的多样性；再对经过选择的抗体群（通过亲和力和浓度进行促进抑制得到的抗体群）进行繁殖变异产生新的抗体群。不断地循环，最终也将会找到满足要求的最优解。

步骤1：抗原识别——对实际问题进行抽象，产生目标函数和约束条件作为抗原。

步骤2：产生初始抗体——若抗原为新抗原，则随机产生N个抗体构成初始抗体群，记忆库为空集；若抗原为已经出现的抗原，则从记忆库中随机选择部分记忆细胞，以及随机产生部分抗体构成规模为N的初始抗体群。

步骤3：亲和力、浓度计算——亲和力反映了候选解和最优解的接近程度，浓度反应了候选解之间的相似性。

步骤4：记忆细胞更新——与抗原有最大亲和力的抗体加给记忆细胞。 由于记忆细胞数目有限，新产生的具有更高亲和力的抗体替换较低亲和力的抗体。

步骤5：终止条件——当达到给定代数或已经连续几代都没能找到更好的解则终止，否则转到步骤

（6）重复执行。

步骤6：抗体的促进和抑制——高亲和力抗体受到促进，高浓度抗体受到抑制。通常通过计算抗体成活的期望值来实施。

步骤7：产生新抗体群——通过人工免疫算子产生多种抗体，再加上记忆细胞中的抗体代替原抗体群，形成下一代抗体群。

3.旅行商问题的人工免疫算法

3.1 旅行商问题的人工免疫算法的基本步骤:

人工免疫算法的映射关系:抗原对应为遍历各城市的最短路径；抗体对应为一条遍历路径；亲和力对应为抗体所决定的路径与抗原的最短路径的匹配程度。算法的基本步骤:

步骤1:随机生成一个规模为N的初始抗体群path。

步骤2:计算抗体群path中的每个抗体的亲和力Affi和浓度density。

步骤3:选择亲和力较高的抗体生成记忆细胞群体MemoryLab，其规模为N1。

步骤4:依据亲和力和浓度对路径path中各个抗体的进行选择并繁殖,得新抗体群path2。亲和力越高、浓度越低则繁殖越多;反之, 则繁殖越少。

步骤5:通过人工免疫算子对抗体群path2进行变异等操作,得到抗体群path3。亲和力越低则变异率越高;亲和力越高则变异率越低。

步骤6: 将path3 并入path, 计算抗体群path中的每个抗体对抗原的亲和力。删除亲和力低的和重复的抗体,使群体总规模保持为N。

步骤7: 重复执行步骤2到步骤7,直到循环次数达到设定值或经过若干次循环仍没有找到更优解。

3.2 抗体的编码以及初始抗体群体的产生：

抗体的编码方式模拟了生物抗体的蛋白质结构, 把每个城市看成是一个氨基酸分子, 将城市之间的边看作是连接氨基酸分子的肽键。一条遍历n个城市的路径则相当于一条包含n个不同氨基酸分子的肽链。

基于抗体的编码，初始抗体群的产生一般都是随机的产生，这样是为了能够增加整个抗体群体的多样性。

3.3 亲和力计算免疫系统通过识别在抗原和抗体之间的独特型或者抗体和抗体之间的独特型产生多种抗体，抗原和抗体之间结合强度一般用亲和力来估计——抗原与抗体之间亲和力越大，抗原与抗体之间的匹配越好。

免疫算法中的难点之一就是亲和力计算。亲和力函数的设计往往在很大程度上决定算法的优劣性。对TSP问题来说,常见的亲和力定义方法是取抗体所对应的路径长度的倒数。

对应的路径长度通常为较大的正数, 致使亲和力通常变得很小,且密集分布于一个狭窄区间内, 不利于体现抗体的优劣。另一方面,该方法没有体现抗体与抗原之间的联系。为此可进一步对其进行改进，得亲和力得定义为:

A（k）= L /L(k)其中L为抗原对应的旅行商路线的总长度,即TSP问题的最短路径。但我们往往不知道最短路径是多长，否则也没必要进行搜索。为此可以把L设为当前抗体群中的抗体的最短路径，但这往往使亲和力保持较高，并且也聚集在一个较短的空间范围内（但较简简单单的取路径的倒数有较大的改进）这为如何实现抗体的促进和抑制带来一定的难度，为此必须为抗体被扩增数进行相应的设计，见3.4。

3.4 抗体浓度抗体的浓度用于调节抗体的规模，基于浓度的选择机制，既促进亲和力高的抗体，又可抑制浓度高的抗体，从而保证了算法的收敛性及抗体群体的多样性。浓度函数的定义和定义抗体亲和力的定义一样，对算法的优劣性也同样具有非常的地位。可将抗体浓度函数定义如下式:其中, n 为抗体数量，s (abi , abj )表示抗体间的相似性。抗体的浓度表示与其相似的抗体占整个群体的比例。判断抗体间的相似性有多种方法。

其中D( abi , abj )表示抗体abi和abj的欧基里德距离, T为预设的指定阈值。这种算法也同样具有基于信息熵的判断方法的缺点，但该判断方法相对简单。

3.5 抗体促进和抑制

3.6 人工免疫

算子为了能对未知抗原产生免疫应答,可通过免疫算子来产生新的抗体。在生物免疫系统中新抗体一般是通过变异得到的，但为了进一步提高免疫算子的多样性我们可引入遗传算法中的交叉操作算子。现对部分人工免疫算子作一些简要的介绍：

（1） 字符换位算子：字符换位操作即是对抗体A，随机取两个正整数i,j，以一定的概率交换抗体A中一对字符ci,cj的位置。

（2） 字符串移位算子：字符串移位操作是从抗体A中随机取出一个字符子串A1, 以一定的概率依次往左（或往右）移动字符串A1中的各个字符, 最左（或最右）边的一个字符则移动到最右(或最左)边的位置。

（3） 字符串逆转算子：字符串逆转操作是对抗体A中随机取出一个子字符串，以一定的概率将其首尾倒置。

（4） 字符串重组算子：字符串重组操作是在抗体A中随机取一个子字符串A1，以一定的概率使字符串A1中字符重新排列。重新排列的目的是提高抗体的亲和力，具体方法与所求解的问题有关。

（5） 优质串保留算子：如果若干个抗体与抗原之间的亲和力都很大, 且这些抗体包含了一个相同的子字符串, 则称这个子字符串为优质字符串, 简称优质串。如果抗体中存在优质串, 则在抗体产生过程中以一定概率使该优质串不受破坏。

（6） 新抗体引人算子：若抗体群中的抗体失去了多样性, 则可以产生新的抗体替换掉其中的一部分,以保持抗体群中抗体的多样性。新抗体引人操作是当抗体群中有k个抗体相同时, 对其中的（k-1）个抗体以一定概率用新产生的抗体替换。

4. 应用实验研究

实验结果表明本文提出的旅行商问题的人工免疫算法能够有效地搜索到最优值，其中的一些参数调节也能够较有效的改变搜索能力和收敛速度，但从上面的一些数据可知本文提出的算法仍有一些不足之处，如怎样选择最佳参数等。

5.结语

本文提出了一种基于人工免疫理论的基本算法来求解旅行商问题。免疫算法通过抗体与抗原间的亲和力以及抗体与抗体之间的浓度来保留优质抗体和保持抗体群种的多样性。

对高亲和力、低浓度的抗体进行促进；对低亲和力、高浓度的抗体进行抑制，并加大变异程度。由其独特的特征，在优化问题规模不大、搜索空间较小的情况下防止算法陷入局部最优，具有更强的全局搜索能力，但对更大规模的优化问题时有收敛速度较慢等不足，由此产生了各种各样的改进版的人工免疫算法，如结合遗传算法等其他算法的混合式算法，这些都为对人工免疫算法的研究带来了广阔的前景。

本硕士论文来源于中国硕士论文网，

参考文献