面向TSP问题的免疫遗传算法研究

2023-02-07

遗传算法一直在组合优化问题中有着广泛的应用, 而旅行商问题 (Traveling Salesman Problem, TSP) 则是一个典型的有序组合优化问题, 可以看成是许多工程领域复杂优化问题的抽象形式本文通过对利用生物免疫机制提出的一种改进的遗传算法——免疫遗传算法的研究, 并分析了TSP问题的基本特征, 利用这种改进的遗传算法对这种典型的组合优化问题进行求解, 这里给出了利用该算法求解TSP问题的详细过程, 显示出了该算法在克服简单遗传算法盲目搜索和收敛速度慢的卓越能力。

1 免疫遗传算法介绍

免疫遗传算法是基于生物免疫机制提出的一种改进的遗传算法, 它将求解问题的目标函数对应为入侵生命体的抗原, 而问题的解对应为免疫系统产生的抗体, 通过抗原和抗体的亲和力 ( (Affinity) 描述可行解与最优解的逼近程度。生物免疫系统对抗原会自动产生相应的抗体来抵御, 这一过程被称为免疫应答。在此过程中, 部分抗体作为记忆细胞保存下来, 当同类抗原再次侵入时, 记忆细胞被激活并产生大量抗体, 使再次应答比初次应答更迅速, 体现了免疫系统的记忆功能。同时, 抗体与抗体之间也相互促进和抑制, 以维持抗体的多样性及免疫平衡, 这种平衡是依据浓度机制完成的, 即抗体的浓度越高, 则越受抑制, 反之亦然, 体现了免疫系统的自我调节功能。抗体的浓度计算是系统保持种群多样性的基本手段之一。

2 免疫遗传算法求解TSP问题

TSP (Traveling Salesman Problem, 简称TSP) 这是一个典型的NP完全性问题。其大意是有若干个城市任何两个城市之间的距离都是确定的, 现要求旅行商从某城市出发, 必须经过每一个城市且只能在每个城市逗留一次, 最后回到原出发城市。问如何事先确定好一条最短的路线, 使其旅行的费用最少。现给出免疫遗传算法求解TSP问题的具体步骤。

(1) 抗体的编码。对于n个城市的TSP问题, 我们对这n个城市分别编号为1, 2, 3…n, 遍历这n个城市的最短距离就是该算法的抗原, 把这n个城市的编号任意排列成一个长度为n的字符串就形成一个抗体, 将每个抗体的第一个基因位 (即字符串的第一个字符) 固定为出发的城市编号1, 这样每个抗体只有 (n-1) 个基因位可任意排列, 抗体空间只包含 ( (n-1) !个抗体, 同样解空间只包含 (n-2) !/2个可行解 (从其中一个城市处发, 遍历其余 (n-1) 个城市只去一次的路径) 。这种编码方式同时也更加符合旅行商问题的实际情况, 只是从固定的第一个城市出发, 最终又返回到第一个城市。

(2) 抗原输入。先选取N个城市, 根据事先对抗体的编码, 选取1作为起始点, 随机生成遍历所有城市的M条路径作为抗原。

(3) 初始抗体的产生。对初次应答, 在TSP问题中, 用最近邻域法生成一些遍历路径, 比较路径的长短, 选择其中较短的x条作为抗体, 并定义一个约束函数以包含所有城市的最小正方形的周长为抗体, 从而产生初始抗体。而对再次应答, 则借助免疫机制的记忆功能, 部分初始抗体由记忆单元获取。由于记忆单元中抗体具有较高的适应度和较好的解群分布, 因此可提高对TSP问题的收敛速度。

(4) 计算抗体适应度。分别计算输入的抗原和所产生抗体之间的亲和度以及抗体与抗体之间的亲和度。抗原和抗体间的亲和度有多种表示形式, 如Euclidean距离、Manhattan距离以及Hamming距离。

(5) 抗体的促进和抑制。对于TSP问题免疫浓度控制的基本过程: (1) 统计代, 个体中抽取免疫基因m个, 设m=4, 基因长度为4, 得到初始解群, p1 (1000) , p2 (1011) , p3 (1010) , p4 (1001) ; (2) 计算第1个符号1出现在基因座1上的概率; (3) 计算抗体1和抗体2的相似度, 并计算抗体3和抗体4的相似度。可得; (4) 计算抗体的选择概率。

选择概率由轮盘赌选择法计算, 为亲和度常数, 然后根据计算出的P选择个体进入下一代。

(6) 群体更新。即把新产生的群体作为当前群体, 同时淘汰掉抗体适应度最差的5%, 再随机生成5%的抗体加入子代中去, 进行下一代的进化。

(7) 免疫算子的引入。免疫遗传算法在进行每一次迭代过程中, 都要进行选择、交叉和变异等遗传操作, 使进入下一代种群个体的平均适应度比上一代高。而下一代还要重复上一代的这些提高种群适应度的操作, 从而必然使某些个体存在“退化”现象。免疫算子是由提取疫苗、接种疫苗和免疫选择3个步骤完成的。为了提高算法的通用性以及应用上的便利性, 在种群进化过程中, 从其最佳个体的基因中提取有效信息, 进而开辟一条制作免疫疫苗的途径。

基于以上思想, 这里给出TSP问题中疫苗自适应选取及接种方法。

(1) 分析待求问题, 搜集特征信息。假设在某一时刻, 从一城市出发欲前往下一个目标城市, 一般首先考虑距离当地路程最近的城市, 如果它己被访问过, 则可选择剔除该城市之外的距离最小的城市。

(2) 根据特征信息制作免疫疫苗。就TSP问题的特征而言, 在最终的解决方案中, 即在最佳路径里必然包括而且很大程度上包括了相邻城市间距离最短的路径, 显然, 这种特点可作为求解问题时以供参考的一种特征信息或知识, 从而视为从问题中抽取疫苗的一种途径, 所以一般以所有城市与其邻近城市组成疫苗。

(3) 疫苗接种。接种疫苗可以以很大的概率使其适应度提高, 疫苗所对应的模式将在群体中呈指数级扩散。否则, 它将被抑制或呈指数级衰减。

(8) 终止条件判别。若满足终止条件, 输出最优解, 计算结束;否则转4。

3 实例仿真

在Visual C++编译环境下, 本文编写了利用免疫遗传算法求解30个城市的TSP问题的程序。这里将算法和程序界面分离, 程序将算法功能用DLL方式进行封装。这里算法采用的编码方式为浮点数编码, 取群体规模为100, 编码长度为10, 交叉概率pc=0.8, 变异概率pm=0.1, 具体计算过程: (1) 读取城市坐标文件。 (2) 城市计算结束后, 生成两个文件, 一是gacitysfile.txt, 它记录了计算得到的最优路径信息;二是gaitersfile.txt, 它记录了计算过程中的迭代信息。可利用提供的Matlab的M文件gatspsta.m读取以上两个文件, 画出这30个城市的路径优化过程图和求解路径图。

摘要：本文利用免疫遗传算法中抗原识别、保持抗体的多样性和免疫记忆等特性来求解TSP问题, 提高TSP问题的总体搜索能力, 也证明了该算法的有效性和优越性。

关键词：免疫遗传算法,TSP