- 相关推荐
研究人工免疫算法中旅行商问题
0.引言
早在18世纪，爱尔兰的数学家哈密尔顿和英国的数学家托马斯就已经对旅行商问题（TSP）进行数学研究，而旅行商问题一般形式的研究则是由数学家卡尔·门格尔于19世纪三十年代在维也纳和哈佛大学首次进行研究的。对旅行商问题的研究往往是出于把它作为一个可应用于解决大规模的组合最优化问题的一般方法的一个平台，然而这并不是说在很多领域中旅行商问题找不到其具体的应用。事实上，旅行商问题有许许多多的应用，它可以看成是许多领域内复杂工程优化问题的抽象形式，诸如邮路问题、网络布线问题、物流配送问题、电路板钻孔问题等等，这些应用给旅行商问题的研究带来了活力，并且帮助指导今后的研究工作。旅行商问题本身的应用范围正在不断扩张，它的研究方法也正迎来越来越广阔的发展前景。可以看出，不论从理论还是实际应用来讲，研究TSP问题取得的每一步进展都将会有非常重大的意义。
多年来人们一直寻求求解TSP问题的算法，其中有传统的算法如动态规划法、分支极限法等，但由于其仅能用于求解规模较小的TSP问题，在实际应用中的局限性使其无法适用于求解大规模的TSP问题。近年来，现代流行的智能算法也越来越受到研究人员们的广泛关注，当然人们也正在努力的探索，试图用其求解TSP问题。这些算法包括神经网络、遗传算法、蚁群算法等。本文欲用另外一种人工智能算法--人工免疫算法,来求解TSP问题。中国硕士论文网提供大量免费硕士毕业论文,如有业务需求请咨询网站客服人员！
1.旅行商问题的概述
1.1 旅行商问题的描述：
旅行商问题，简单地说，就是某一旅行商要去n 个城市去旅行，他要把这n 个城市都逛一次而且不重复，最后回到原出发城市,问给定所有城市之间的旅行成本，哪一种旅行路径成本最小？为了简化，成本可理解为旅行商走过的最短距离。即已知n 个城市以及各城市间的距离，某一旅行商从某个城市出发访问每个城市有且仅一次，最终返回原出发城市，怎样走才能使其所走的线路最短？
用图论来描述，那就是已知带权图 G=(C，L)，寻找出总权值最小的一条路径。其中C={c1，c2，…，cn}表示n 个城市的集合，L={ lij | ci，cj∈C}是集合C 中元素（城市）两两连接的集合，每条边lij，都存在与之对应的权值dij，实际应用中dij 可以表示距离、费用、时间、油量等。
从旅行商问题的描述来看，似乎其并不是很复杂，理解起来也是很简单，但其的确是一个非常复杂的问题。对于n 个城市的旅行商问题，可供选择的路径数目我们可以这样计算：
起始城市访问其他城市有n-1 个选择，第二个城市有n-2 个选择，依此类推，倒数第2 个城市只有1 个选择，总的可选择的路径数为?n ?1?! ? (n ?1)(n ? 2)(n ? 3). . . 3 2 1。另外，我们所研究的标准的旅行商问题其旅行成本是对称的，即城市i 到城市j 的旅行成本和城市j 到城市i 的旅行成本是一样的，故对于一个包含n 个城市的旅行商问题，可供选择的路径有(n ?1)!/ 2种。当n 较小时，我们可通过罗列各种路径并从中找出最短路径，但随着值n的变大，可供选择的路径数迅速增加，用罗列的办法已经无能为力了，这时必须寻求其他解法来搜索最短的路径。
1.2 旅行商问题的数学建模：
旅行商问题( 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个不同氨基酸分子的肽链。
抗体按所走城市的顺序进行编码, 每一个抗体编码字符串形如: (C1, C2 ,…,Ci ,…,Cn )其中Ci 表示遍历城市的编号。一个字符串抗体只能代表一个候选解,但一个候选解允许有一个以上的字符串抗体相对应。在确定抗体的编码方式时, 应尽量使字符串抗体和候选解之间形成一一对应的关系, 以缩小抗体空间、提高搜索效率。可根据TSP问题有每个城市有且只能访问一次和任意的Ci不等于Cj的约束条件。另外对于有n 个城市的旅行商问题,从其中的一个城市出发,遍历其余(n-1)个城市且每个城市只去一次的路径有(n-1) ! /2条。 对这n个城市编号,其号码分别为1, 2, 3,…, n；并且把商人出发城市编为第1号,其它城市可以随意编号,把这n个城市的编号任意排列成一个长度为n的字符串都可以形成一个抗体。 因此抗体空间含有n! 个抗体,而解空间含有(n-1) ! /2个可行解。这n ! 个抗体只代表(n-1)! /2个可行解。 因此免疫算法要在抗体空间中搜索到与抗原匹配的抗体,比在解空间中搜索到最优解更难。
基于抗体的编码，初始抗体群的产生一般都是随机的产生，这样是为了能够增加整个抗体群体的多样性。
3.3 亲和力计算免疫系统通过识别在抗原和抗体之间的独特型或者抗体和抗体之间的独特型产生多种抗体，抗原和抗体之间结合强度一般用亲和力来估计——抗原与抗体之间亲和力越大，抗原与抗体之间的匹配越好。
免疫算法中的难点之一就是亲和力计算。亲和力函数的设计往往在很大程度上决定算法的优劣性。对TSP问题来说,常见的亲和力定义方法是取抗体所对应的路径长度的倒数。
对应的路径长度通常为较大的正数, 致使亲和力通常变得很小,且密集分布于一个狭窄区间内, 不利于体现抗体的优劣。另一方面,该方法没有体现抗体与抗原之间的联系。为此可进一步对其进行改进，得亲和力得定义为:
A（k）= L /L(k)其中L为抗原对应的旅行商路线的总长度,即TSP问题的最短路径。但我们往往不知道最短路径是多长，否则也没必要进行搜索。为此可以把L设为当前抗体群中的抗体的最短路径，但这往往使亲和力保持较高，并且也聚集在一个较短的空间范围内（但较简简单单的取路径的倒数有较大的改进）这为如何实现抗体的促进和抑制带来一定的难度，为此必须为抗体被扩增数进行相应的设计，见3.4。
3.4 抗体浓度抗体的浓度用于调节抗体的规模，基于浓度的选择机制，既促进亲和力高的抗体，又可抑制浓度高的抗体，从而保证了算法的收敛性及抗体群体的多样性。浓度函数的定义和定义抗体亲和力的定义一样，对算法的优劣性也同样具有非常的地位。可将抗体浓度函数定义如下式:其中, n 为抗体数量，s (abi , abj )表示抗体间的相似性。抗体的浓度表示与其相似的抗体占整个群体的比例。判断抗体间的相似性有多种方法。
一种是基于信息熵的判断方法，通过这种方法能够较容易地与生物免疫系统中的抗体对应，更能够客观地反应其含义。根据抗体群平均信息熵的概念计算抗体浓度的方法可知，抗体群的所有抗体在同一基因座上的等位基因各不相同时，抗体群的平均信息熵最大，抗体的相似性最小；反之，相似性较大。但是，在优化计算中，这种利用信息熵的概念计算抗体浓度的方法存在一定得问题，例如抗体A=（1，2，3，4，5）与抗体B=(2，3，4，5，1)之间的信息熵较大，但其却对应同一条路径。
其中D( abi , abj )表示抗体abi和abj的欧基里德距离, T为预设的指定阈值。这种算法也同样具有基于信息熵的判断方法的缺点，但该判断方法相对简单。
在此提出一种求解浓度的方法：首先，对某一个具体的抗体ab先从抗体群中寻找和其亲和力相近的抗体abk（可以将两亲和力作差，求绝对值，绝对值小于某一阈值暂且将其认为是相似抗体，以待作进一步筛选）。其次，拿这个具体抗体ab和从第一步搜寻到的其他抗体abk作比较——先从抗体ab（字符串）的第一个字符char1到抗体abk中寻找相同的字符char1，将抗体abk中的字符char1左两个右两个字符存入一个数组a中，同时也将抗体ab（字符串）的第一个字符char1左两个右两个字符存入另一个数组b中（字符串第一个字母的左两个字符为该字符串的的最后两个字符，同时最后一个字符的右两个字符为该字符串的前两个，字符串第二个字母的选择同理），判断两数组a和b中有几个相同的字符；再从第一个抗体ab中的第二个字符char2到第二个抗体abk中去找，得相同数，依次类推，将总的相同数相加作为该抗体的相似性数k。最后基于前两步对所有抗体求得相似性数ki，定义第i个抗体abi的抗体浓度为： ? =ki / sum?ki ?。
3.5 抗体促进和抑制
将抗体群中的抗体根据其亲和力大小按升序排列, 得到: {ab1 ,ab2 , …, abn }, 且A(i)<A(i+1), i = 1, 2, …,n-1。从抗体群中选择亲和力较大的m个抗体进行扩增。但扩增的数量受亲和力刺激的同时还要受浓度的调节。高亲和力、低浓度的抗体扩增数多；低亲和力、高浓度的抗体扩增数少。
3.6 人工免疫
算子为了能对未知抗原产生免疫应答,可通过免疫算子来产生新的抗体。在生物免疫系统中新抗体一般是通过变异得到的，但为了进一步提高免疫算子的多样性我们可引入遗传算法中的交叉操作算子。现对部分人工免疫算子作一些简要的介绍：
（1） 字符换位算子：字符换位操作即是对抗体A，随机取两个正整数i,j，以一定的概率交换抗体A中一对字符ci,cj的位置。
（2） 字符串移位算子：字符串移位操作是从抗体A中随机取出一个字符子串A1, 以一定的概率依次往左（或往右）移动字符串A1中的各个字符, 最左（或最右）边的一个字符则移动到最右(或最左)边的位置。
（3） 字符串逆转算子：字符串逆转操作是对抗体A中随机取出一个子字符串，以一定的概率将其首尾倒置。
（4） 字符串重组算子：字符串重组操作是在抗体A中随机取一个子字符串A1，以一定的概率使字符串A1中字符重新排列。重新排列的目的是提高抗体的亲和力，具体方法与所求解的问题有关。
（5） 优质串保留算子：如果若干个抗体与抗原之间的亲和力都很大, 且这些抗体包含了一个相同的子字符串, 则称这个子字符串为优质字符串, 简称优质串。如果抗体中存在优质串, 则在抗体产生过程中以一定概率使该优质串不受破坏。
（6） 新抗体引人算子：若抗体群中的抗体失去了多样性, 则可以产生新的抗体替换掉其中的一部分,以保持抗体群中抗体的多样性。新抗体引人操作是当抗体群中有k个抗体相同时, 对其中的（k-1）个抗体以一定概率用新产生的抗体替换。
（7） 有序交叉算子：随机取两个正整数i,j，两后代现分别按对应位置复制双亲X1、X2匹配段中的两个子串A1、A2，在对应位置交换双亲匹配段以外的城市，如果交换后，后代X1中的某一城市a与子串A1中的城市重复，则将该城市取代子串A2中的城市a具有相同位置的城市，直到与子串A1中的城市均不重复为止，对后代X2也采用相同的方法。
4. 应用实验研究
为了验证人工免疫算法的的有效性，本文针对从TSPLIB中摘取的Swiss42的TSP数据运用人工免疫算法对其用MATLAB进行多次应用实验。对抗体群规模N=50，记忆细胞的规模N1=20，交叉概率Pc=0.9，变异概率Pm=0.05，参数因子? =5，? =5，? =0.1，总的循环代数Tc=1000，进行了多次计算，每次计算随机产生不同的初始抗体。计算结果如表1所示，搜索到最优路径的情况。
实验结果表明本文提出的旅行商问题的人工免疫算法能够有效地搜索到最优值，其中的一些参数调节也能够较有效的改变搜索能力和收敛速度，但从上面的一些数据可知本文提出的算法仍有一些不足之处，如怎样选择最佳参数等。
5.结语
本文提出了一种基于人工免疫理论的基本算法来求解旅行商问题。免疫算法通过抗体与抗原间的亲和力以及抗体与抗体之间的浓度来保留优质抗体和保持抗体群种的多样性。
对高亲和力、低浓度的抗体进行促进；对低亲和力、高浓度的抗体进行抑制，并加大变异程度。由其独特的特征，在优化问题规模不大、搜索空间较小的情况下防止算法陷入局部最优，具有更强的全局搜索能力，但对更大规模的优化问题时有收敛速度较慢等不足，由此产生了各种各样的改进版的人工免疫算法，如结合遗传算法等其他算法的混合式算法，这些都为对人工免疫算法的研究带来了广阔的前景。
本硕士论文来源于中国硕士论文网，参考文献：http://www.lunwenad.com/wzlb-6.html，转载敬请保留链接，谢谢。
【研究人工免疫算法中旅行商问题】相关文章：
现代企业绩效管理问题研究05-03
论组织学习研究的若干问题06-04
感知无线电的关键问题研究05-30
新刑诉法下社区矫正问题研究09-05
大学生文学素养降低问题研究论文04-24
刑事二审程序的若干问题研究05-11
浅析中小企业招聘存在的问题及对策研究04-21
中国农村留守老年人保障问题研究05-11
森林旅游面临的主要问题及对策研究开提报告06-04
寻衅滋事罪问题研初中数学教育研究05-31