0.引言 早在18世纪，爱尔兰的数学家哈密尔顿和英(3)

　　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为预设的指定阈值。这种算法也同样具有基于信息熵的判断方法的缺点，但该判断方法相对简单。