免疫算法解决tsp问题(免疫算法优缺点)

导语：基于免疫算法的TSP问题求解

（1）抗体编码

本文在TSP求解中，采用的是基于城市序号的实数编码，抗体以遍历的位置的次序排列进行编码。在MATLAB代码中为一个没有重复数字的行向量来表示。设有n个城市的某个排序为x1、x2、...、xn，也就是说，将抗体看做一个数组结构，数组中包括n个元素。

（2）产生初始种群

种群（parent）中每一个体为n个城市一个排列，可以采用随机生成的方式，也可以采用输入固定数据集的方式。

（3）亲和力计算

亲和力指的是某个抗体在解空间与最优解得接近程度。在应用中根据实际的问题分析做出一个合适的函数映射，从而得到合适的适应度函数。对于TSP问题，以个体对应路。线总长作为个体的适应值，越小则表示该个体越优。在求解过程中，先求出任意两个城市之间的距离，设为cij,再计算出每个个体对应路线总长作为个体的适应值，存放于一个向量S当中，某个体x=(x1,x2,…xn),则该函数的适应值为：

（4）抗体之间的相似度计算以及浓度分析

在自然免疫系统中，抗体的抑制和促进不但受到抗体亲和力的影响，还受到自身浓度的控制，这是免疫系统一个非常重要的特点。在人工免疫算法的分析过程中，这也是一个需要特别引起注意的问题。因此算法引入了相似度以及浓度的概念，并且由此判断最后的适应度。给出抗体适应度的概率公式：

其中，fi表示抗体之间的距离。总的来说，给定一个相识度计算间距离的阈值threshold，以及抗体之间的距离distance。通过简单的数学运算得到适合的浓度和适应度。

（5）存取记忆库

引入记忆库的概念是为了保存父代优秀抗体，保持解得优良性，缩短收敛时间。每次适应评估之后，将轿优的前P个抗体存入记忆库，在每次由解群体到混合群体，从记忆库中取出较优的P个抗体放入到混合群体，这样能够组成行的抗体群。

（6）交叉、变异和抗体群的更新

交叉和变异的目的是为了让抗体朝着理想的方向进化。

本文采用的交叉方法为“随机匹配交叉策略”。首先根据交叉概率决定是，而不是随意进行的。对抗体群进行随机分组，取编号为1的抗体，例如随机产生一个C1∈[1,citynumber-1]，然后取出抗体中该位置的城市c1,然后在抗体2找到c1的位置，再把抗体1中的位置与抗体2中进行交换，知道所有城市都完成。其中过程如图3.2.1：

图3.2.1交叉示意图

在本文中变异采用插入变异策略。假设存在一个城市串[...c1,c2,c3,c4,c5,c6...]，取c2到c5进行一次转置，于是该转置部分变为c5,c4,c3,c2。然后重新插入到原城市串中，这样就算完成一次变异操作。其中具体如图3.2.2所示：

图3.2.2 变异示意图

（7）求解TSP的完整流程

①Begin：

②生成初始种群

③亲和力计算

④抗体之间相似度计算

⑤浓度计算

⑥根据抗体群产生抗体信息群

⑦交叉变异

⑧更新抗体群

⑨End；

本文内容由快快网络小林整理编辑！