-1-
中国科技论文在线
基于人工免疫算法的旅行商问题研究
丁蕾 1，叶炳 2
中国矿业大学信息与电气工程学院 江苏徐州 （221008）
摘 要：旅行商问题（TSP）是计算数学中研究最为深入的问题之一，它是一个典型的组合
优化问题，在实际中的应用非常广泛，而且长期以来被作为 NP-Complete 问题的理想平台。
文中提出了一种基于模拟生物免疫系统的人工免疫算法来求解旅行商问题，结合前人对浓
度、亲和力和抗体扩增数的定义和设置，提出了自己对浓度函数、亲和力函数和抗体扩增数
的设置，并通过对 TSPLIB 中 Swiss42 的 TSP 数据进行仿真研究，搜索到了 TSP 数据库中用
其他方法多次求解所得的最优路径，表明该算法能够有效的收敛于最优解，是一种理想的解
决 TSP 问题的智能优化算法。
关键词：旅行商问题；人工免疫算法；亲和力；浓度
0.引言
早在18世纪，爱尔兰的数学家哈密尔顿和英国的数学家托马斯就已经对旅行商问题
（TSP）进行数学研究，而旅行商问题一般形式的研究则是由数学家卡尔·门格尔于19世纪
三十年代在维也纳和哈佛大学首次进行研究的。对旅行商问题的研究往往是出于把它作为一
个可应用于解决大规模的组合最优化问题的一般方法的一个平台，然而这并不是说在很多领
域中旅行商问题找不到其具体的应用。事实上，旅行商问题有许许多多的应用，它可以看成
是许多领域内复杂工程优化问题的抽象形式，诸如邮路问题、网络布线问题、物流配送问题、
电路板钻孔问题等等，这些应用给旅行商问题的研究带来了活力，并且帮助指导今后的研究
工作。旅行商问题本身的应用范围正在不断扩张，它的研究方法也正迎来越来越广阔的发展
前景。可以看出，不论从理论还是实际应用来讲，研究TSP问题取得的每一步进展都将会有
非常重大的意义。
多年来人们一直寻求求解TSP问题的算法，其中有传统的算法如动态规划法、分支极限
法等，但由于其仅能用于求解规模较小的TSP问题，在实际应用中的局限性使其无法适用于
求解大规模的TSP问题【5】【11】。近年来，现代流行的智能算法也越来越受到研究人员们的广
泛关注，当然人们也正在努力的探索，试图用其求解TSP问题。这些算法包括神经网络、遗
传算法、蚁群算法等【5】【11】。本文欲用另外一种人工智能算法--人工免疫算法,来求解TSP
问题。
1.旅行商问题的概述
旅行商问题的描述：
旅行商问题，简单地说，就是某一旅行商要去 n 个城市去旅行，他要把这 n 个城市都逛
一次而且不重复，最后回到原出发城市,问给定所有城市之间的旅行成本，哪一种旅行路径
成本最小？为了简化，成本可理解为旅行商走过的最短距离。即已知 n 个城市以及各城市间
的距离，某一旅行商从某个城市出发访问每个城市有且仅一次，最终返回原出发城市，怎样
走才能使其所走的线路最短？【4】
用图论来描述，那就是已知带权图 G=(C，L)，寻找出总权值最小的一条路径。其中
C={c1，c2，…，cn}表示 n 个城市的集合，L={ lij | ci，cj∈C}是集合 C 中元素（城市）两两
连接的集合，每一条边 lij，都存在与之对应的权值 dij，实际应用中 dij可以表示距离、费用、
时间、油量等【8】。
-2-
中国科技论文在线
从旅行商问题的描述来看，似乎其并不是很复杂，理解起来也是很简单，但其的确是一
个非常复杂的问题。对于 n 个城市的旅行商问题，可供选择的路径数目我们可以这样计算：
起始城市访问其他城市有 n-1 个选择，第二个城市有 n-2 个选择，依此类推，倒数第 2 个城
市只有 1 个选择，总的可选择的路径数为 1 ! ( 1)( 2)( 3). . . 3 2 1n n n n 。另外，
我们所研究的标准的旅行商问题其旅行成本是对称的，即城市 i 到城市 j 的旅行成本和城市
j 到城市 i 的旅行成本是一样的，故对于一个包含 n 个城市的旅行商问题，可供选择的路径
有 ( 1)!/ 2n 种。当 n 较小时，我们可通过罗列各种路径并从中找出最短路径，但随着值 n
的变大，可供选择的路径数迅速增加，用罗列的办法已经无能为力了，这时必须寻求其他解
法来搜索最短的路径。
旅行商问题的数学建模：
旅行商问题( TSP)在数学上可以描述为以下优化问题【3】:
1
1
11 ),(),(min
n
i
nii CCdCCdTd
St ci ∈C, C = {c1,c2,c3,…,cn}
i = 1, 2, 3,…,n
式中 C 为城市集合，ci 为城市编号，d(ci , cj)为编号为 ci 和 cj的两城市之间的成本,且有
d(ci,cj)=d(cj,ci) 。
简而言之, TSP问题的实质是针对 n 个坐标(n 个城市的位置)在一定条件(城市之间路径
相互连通的限制)下,寻找最短路径 C={c1，c2，…，cn} (其中 ci 表示第 i 个城市的编号) ,
使得
1
1
11 ),(),(
n
i
nii CCdCCd 取最小值。
2.人工免疫算法的基本原理
生物免疫系统及其运行机制
生物免疫系统是自然界生物所必备的防御系统, 它是一种由众多细胞、分子和组织等子
系统构成的复杂系统，这些子系统之间存在着复杂的相互联系，具有识别“自己”和“非己”，
消除和消灭异物的功能。生物免疫系统又分为先天免疫系统和自适应免疫系统。先天免疫系
统是一种与生俱来的天然防御系统，具有识别一定微生物并消灭这种微生物的能力，但对于
绝大数外来侵入病毒的杀伤力较弱，这时候自适应免疫系统就开始发挥它的重要作用了，它
能够自适应的学习外来侵入病毒物质或分子的模式结构，中立或消除该种物质。
自适应免疫系统的运行机制可以简单的概括为：在抗原的激励下，巨噬细胞分化抗原为
颗粒状物质，抗原呈递细胞将这些物质呈递到巨噬细胞的表面；通过识别的途径，被激活T
细胞分化和分泌淋巴因子，并使B细胞应答；B细胞对来自激活的T细胞的信号做出反应——
被激活并进行分化和繁殖，分泌出抗体蛋白；抗体缠住、中立并毁灭这些抗原，其他多余的
T细胞和B细胞变为记忆细胞。这样反复循环若干代数将最终产生能够消灭抗原的有效抗体。
免疫系统中B细胞的功能主要是产生抗体,抗体由氨基酸排列组成, 氨基酸的不同排列方式
形成不同的抗体;而T细胞则主要实现免疫调节功能【1】【2】【6】。
人工免疫系统及人工免疫算法的基本步骤
人工免疫系统即根据生物免疫系统的运行机制构造的一种仿生系统。在构造人工免疫系
统时, 首先要构造的就是人工抗原和抗体,在人工免疫系统中, 一个抗体或抗原可以用一个
-3-
中国科技论文在线
字符串表示，生物抗体由氨基酸的不同排列组成，因此, 人工抗体（字符串）中的字符应相
当于生物抗体中的氨基酸。为使人工免疫系统具有与生物免疫系统类似的自我调节机制,可
以用亲和力来描述抗体和抗原之间的匹配程度，用浓度来描述每种抗体在整个抗体群中所占
份额。抗体和抗原之间的亲和力反映了候选解和最优解的接近程度, 也即反映候选解对约束
条件和目标函数的满足程度。对于亲和力较大的抗体作为记忆细胞加以重点保留，又通过浓
度调节来保持抗体的多样性；再对经过选择的抗体群（通过亲和力和浓度进行促进抑制得到
的抗体群）进行繁殖变异产生新的抗体群。不断地循环，最终也将会找到满足要求的最优解。
基于生物免疫系统的运行机制可构造人工免疫算法的基本步骤如下图所示【1】【7】【8】【10】：
抗原识别
产生初始抗体
结束
抗体的促进和抑制
记忆细胞更新
亲和力、浓度计算
满足终止条件? Y
N
产生新抗体群
图1 一般免疫算法步骤
步骤1：抗原识别——对实际问题进行抽象，产生目标函数和约束条件作为抗原。
步骤2：产生初始抗体——若抗原为新抗原，则随机产生N个抗体构成初始抗体群，记忆库
为空集；若抗原为已经出现的抗原，则从记忆库中随机选择部分记忆细胞，以及随
机产生部分抗体构成规模为N的初始抗体群。
步骤3：亲和力、浓度计算——亲和力反映了候选解和最优解的接近程度，浓度反应了候选
解之间的相似性。
步骤4：记忆细胞更新——与抗原有最大亲和力的抗体加给记忆细胞。 由于记忆细胞数目有
限，新产生的具有更高亲和力的抗体替换较低亲和力的抗体。
步骤5：终止条件——当达到给定代数或已经连续几代都没能找到更好的解则终止，否则转
到步骤（6）重复执行。
步骤6：抗体的促进和抑制——高亲和力抗体受到促进，高浓度抗体受到抑制。通常通过计
算抗体成活的期望值来实施。
步骤7：产生新抗体群——通过人工免疫算子产生多种抗体，再加上记忆细胞中的抗体代替
原抗体群，形成下一代抗体群。
3.旅行商问题的人工免疫算法
旅行商问题的人工免疫算法的基本步骤:
-4-
中国科技论文在线
人工免疫算法的映射关系:抗原对应为遍历各城市的最短路径；抗体对应为一条遍历路
径；亲和力对应为抗体所决定的路径与抗原的最短路径的匹配程度。算法的基本步骤:
步骤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】【9】：
抗体的编码方式模拟了生物抗体的蛋白质结构, 把每个城市看成是一个氨基酸分子, 将
城市之间的边看作是连接氨基酸分子的肽键。一条遍历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个可行解。 因
此免疫算法要在抗体空间中搜索到与抗原匹配的抗体,比在解空间中搜索到最优解更难。
基于抗体的编码，初始抗体群的产生一般都是随机的产生，这样是为了能够增加整个抗
体群体的多样性。
亲和力计算
免疫系统通过识别在抗原和抗体之间的独特型或者抗体和抗体之间的独特型产生多种
抗体，抗原和抗体之间结合强度一般用亲和力来估计——抗原与抗体之间亲和力越大，抗原
与抗体之间的匹配越好。
免疫算法中的难点之一就是亲和力计算。亲和力函数的设计往往在很大程度上决定算法
的优劣性。对TSP问题来说,常见的亲和力定义方法是取抗体所对应的路径长度的倒数,如下
式所示【7】:
A（k） = 1 / L ( k )
其中
1
1
11 ),(),()(
n
i
nii CCdCCdkL
。
该亲和力定义方法只是简单地将目标函数取倒数,它有两个主要缺点: 一方面由于抗体
-5-
中国科技论文在线
对应的路径长度通常为较大的正数, 致使亲和力通常变得很小,且密集分布于一个狭窄区间
内, 不利于体现抗体的优劣。另一方面,该方法没有体现抗体与抗原之间的联系。为此可进
一步对其进行改进，得亲和力得定义为:
A（k）= L /L(k)
其中L为抗原对应的旅行商路线的总长度,即TSP问题的最短路径。但我们往往不知道最短路
径是多长，否则也没必要进行搜索。为此可以把L设为当前抗体群中的抗体的最短路径，但
这往往使亲和力保持较高，并且也聚集在一个较短的空间范围内（但较简简单单的取路径的
倒数有较大的改进）这为如何实现抗体的促进和抑制带来一定的难度，为此必须为抗体被扩
增数进行相应的设计，见。
抗体浓度
抗体的浓度用于调节抗体的规模，基于浓度的选择机制，既促进亲和力高的抗体，又可
抑制浓度高的抗体，从而保证了算法的收敛性及抗体群体的多样性。浓度函数的定义和定义
抗体亲和力的定义一样，对算法的优劣性也同样具有非常的地位。可将抗体浓度函数定义如
下式【8】:
n
1i
ji )ab,s(abn
1
其中, n 为抗体数量，s (abi , abj )表示抗体间的相似性。抗体的浓度表示与其相似的抗
体占整个群体的比例。判断抗体间的相似性有多种方法：
一种是基于信息熵的判断方法，通过这种方法能够较容易地与生物免疫系统中的抗体对
应，更能够客观地反应其含义。根据抗体群平均信息熵的概念计算抗体浓度的方法可知，抗
体群的所有抗体在同一基因座上的等位基因各不相同时，抗体群的平均信息熵最大，抗体的
相似性最小；反之，相似性较大。但是，在优化计算中，这种利用信息熵的概念计算抗体浓
度的方法存在一定得问题，例如抗体A=（1，2，3，4，5）与抗体B=(2，3，4，5，1)之间
的信息熵较大，但其却对应同一条路径。
另一种抗体相似性判断方法是考察两个抗体编码串的欧基里德距离(Euclidean distance)
是否小于指定阈值, 是则相似,否则不相似。相似性函数如下【8】:
其中D( abi , abj )表示抗体abi和abj的欧基里德距离, T为预设的指定阈值。这种算法也同
样具有基于信息熵的判断方法的缺点，但该判断方法相对简单。
在此提出一种求解浓度的方法：首先，对某一个具体的抗体ab先从抗体群中寻找和其亲
和力相近的抗体abk（可以将两亲和力作差，求绝对值，绝对值小于某一阈值暂且将其认为
是相似抗体，以待作进一步筛选）。其次，拿这个具体抗体ab和从第一步搜寻到的其他抗体
abk作比较——先从抗体ab（字符串）的第一个字符char1到抗体abk中寻找相同的字符char1，
将抗体abk中的字符char1左两个右两个字符存入一个数组a中，同时也将抗体ab（字符串）的
第一个字符char1左两个右两个字符存入另一个数组b中（字符串第一个字母的左两个字符为
s(abi,abj )=
0, 其他
1，D(abi, abj)≥T
-6-
中国科技论文在线
该字符串的的最后两个字符，同时最后一个字符的右两个字符为该字符串的前两个，字符串
第二个字母的选择同理），判断两数组a和b中有几个相同的字符；再从第一个抗体ab中的第
二个字符char2到第二个抗体abk中去找，得相同数，依次类推，将总的相同数相加作为该抗
体的相似性数k。最后基于前两步对所有抗体求得相似性数ki，定义第i个抗体abi的抗体浓度
为： i i=k / sum k 。
抗体促进和抑制
将抗体群中的抗体根据其亲和力大小按升序排列, 得到: {ab1 ,ab2 , …, abn }, 且A(i)
<A(i+1), i = 1, 2, …,n-1。从抗体群中选择亲和力较大的m个抗体进行扩增。但扩增的数量受
亲和力刺激的同时还要受浓度的调节。高亲和力、低浓度的抗体扩增数多；低亲和力、高浓
度的抗体扩增数少。抗体被扩增数为:
]
k
A(k))exp(-[roundN(k)
）（
其中round为取整函数；A(k)为第k个抗体的亲和力， ）（k 为第k个抗体的浓度； 、
、 为是参数因子，通过对这三个参数的调节，可以适当的控制扩增数。
人工免疫算子
为了能对未知抗原产生免疫应答,可通过免疫算子来产生新的抗体。在生物免疫系统中
新抗体一般是通过变异得到的，但为了进一步提高免疫算子的多样性我们可引入遗传算法中
的交叉操作算子。现对部分人工免疫算子作一些简要的介绍：
（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也采用相同的方法。
-7-
中国科技论文在线
4. 应用实验研究
为了验证人工免疫算法的的有效性，本文针对从TSPLIB中摘取的Swiss42的TSP数据运
用人工免疫算法对其用MATLAB进行多次应用实验。对抗体群规模N=50，记忆细胞的规模
N1=20，交叉概率Pc=，变异概率Pm=，参数因子 =5， =5， =，总的循环代
数Tc=1000，进行了多次计算，每次计算随机产生不同的初始抗体。计算结果如表1所示，
搜索到最优路径的情况如图2所示。
表1：运行1000代后得平均长度和最优长度的计算结果
计算次数 1 2 3 4 5
平均长度
最优长度 1284 1279 1293 1273 1286
图2 Pc=、Pm=情况下搜索到42个城市的TSP最优路径长度（1273）变化图
经过多次计算搜索到得最短路径长度为1273。最优路径为：
28 3 4 5 7 2 1 33 35 34 21 36 37 32 18 8 38 16 17
15 20 14 6 27 19 13 12 26 11 9 42 24 10 22 41 25 40 23
39 31 30 29
实验结果表明本文提出的旅行商问题的人工免疫算法能够有效地搜索到最优值，其中的
一些参数调节也能够较有效的改变搜索能力和收敛速度，但从上面的一些数据可知本文提出
的算法仍有一些不足之处，如怎样选择最佳参数等。
5.结语
本文提出了一种基于人工免疫理论的基本算法来求解旅行商问题。免疫算法通过抗体
与抗原间的亲和力以及抗体与抗体之间的浓度来保留优质抗体和保持抗体群种的多样性。
对高亲和力、低浓度的抗体进行促进；对低亲和力、高浓度的抗体进行抑制，并加大变异
-8-
中国科技论文在线
程度。由其独特的特征，在优化问题规模不大、搜索空间较小的情况下防止算法陷入局部
最优，具有更强的全局搜索能力，但对更大规模的优化问题时有收敛速度较慢等不足，由
此产生了各种各样的改进版的人工免疫算法，如结合遗传算法等其他算法的混合式算法，
这些都为对人工免疫算法的研究带来了广阔的前景【3】。
参考文献
[1] 莫宏伟编著.人工免疫系统原理与应用[M]. 哈尔滨:哈尔滨工业大学出版社，2002
[2] 黄席樾主编. 现代智能算法理论及应用[M]. 北京：科学出版社，2005
[3] 黎湖广，邹北骥，欧阳广，王伟. 一种求解TSP问题的改进人工免疫算法[J].科学技术与工程，
2007,7(1):60-63
[4] 郭靖扬. 旅行商问题概述[J]. 大众科技，2006, (8):229-230
[5] 沈润泉，何本阳. 旅行商问题的几种解决途径[J]. 福建电脑，2008, ( 4):19
[6] 施建刚，陈罡，高喆. 人工免疫算法综述[J].软件导刊，2008, 7(11):68-69
[7] 李茂军，舒宜，童调生. 旅行商问题的人工免疫算法[J].计算机科学，2003, 30(3):80-82
[8] 戚玉涛，焦李成，刘芳. 基于并行人工免疫算法的大规模TSP问题求解[J].电子学报，2008, 36(8):3551
[9] 李金城，藤红丽. 改进免疫算法在旅行商问题中的应用[J]. 常熟理工学院学报（自然科学），2008,
22(4):109-113
[10] 王朋义，杜军平. 基于人工免疫算法的旅游突发事件预警研究[J]. 北京工商大学学报（自然科学版），
2008, 26(3):67.
[11]王剑文，戴光明，谢柏桥，张全元.求解TSP问题算法综述[J]. 计算机工程与科学，2008,30(2):72-74
Research on Traveling Salesman Problem based on
Artificial Immune Algorithm
Ding Lei，Ye Bing
School of Information and Electrical Engineering ,China University of Mining & Technology,
Xuzhou,Jiangshu,China,( 221008)
Abstract
The Traveling Salesman Problem（TSP） is one of the most intensively studied problems in
computational mathematics. It is a classic combinatorial optimization problem. In practice, the
application of TSP is very broad, and for a long time it has been regarded for NP-Complete problem as
an ideal platform. This paper presents an artificial immune algorithm based on biological immune
system to solve the Traveling Salesman Problem. Refer to the definitions and settings of concentration,
affinity and amplification of the number of antibody by predecessors; I give my settings about the
concentration function, affinity function and amplification of the number of antibody. Through the
Swiss42 TSP data which get from TSPLIB, I have done several simulation experiments by MATLAB
and at last I have searched the optimal path which was given by TSPLIB using other methods to solve,
show that the algorithm is efficiently, and it is an ideal solution to the problem of intelligent TSP
optimization algorithm.
Keywords：Traveling Salesman Problem; Artificial Immune Algorithm; affinity; concentration
