基于改进克隆选择算法的路径优化问题研究

曹 霞，曹 民 CAO Xia,CAO Min

（上海理工大学 光电信息与计算机工程学院，上海 200093）

0 引言

克隆选择是生物免疫系统理论的重要学说。克隆选择机制是指能在机体内选择出能识别和消灭相应抗原的免疫细胞，使之激活、分化和增殖，进行免疫应答，最终消除抗原[1]。1999年，De Castro和Von Zuben提出了基于免疫系统克隆选择理论的克隆选择算法[2]，该算法是基于抗体与抗原的亲和度的大小及比例进行抗体的选择和克隆，通过构造记忆单元来记忆优良抗体，通过随机产生的新抗体对旧抗体的替代，实现种群多样性。克隆选择算法兼顾全局与局部搜索，具有多样性好、收敛速度快、求解精度高、克服早熟问题等优势。

目前，在使用免疫算法求解路径优化问题已取得一些成果。张乐等人提出基于人工免疫理论的提取免疫疫苗和注射疫苗的新算法求解TSP问题[3]。戚玉涛等人提出了求解TSP问题免疫算法的动态疫苗策略，将先验知识引入算法中，以提高算法的求解性能[4]。刘朝华等人提出一种基于抗体局部最优免疫优势的克隆选择算法求解TSP问题，在深度搜索和广度寻优之间取得了平衡[5]。这些改进的算法在求解TSP问题中均取得了一定的效果。

为更高效地解决TSP问题，本文提出引入疫苗接种策略的克隆选择算法（Immune Clonal Selection Algorithm Introduced into Vaccination Strategy，ICSA-VS）。实验仿真证明该算法具有随机性、自适应性、多样性、收敛快等特点，避免迭代过程陷入局部最优状态，实现了免疫的自我调节功能。

1 问题描述及定义

1.1 TSP问题简述

TSP（Travelling Salesman Problem） 问题可以描述为：给定n个城市C=｛C1,C2,…,CN｝，其中任意两个城市之间的距离D（i,j）=（Ci,Cj），有一个旅行商从某一城市出发，访问各城市一次且仅有一次后再回到原出发城市，要求找出一条最短的巡回路径Lmin=｛Lmin（1 ）,Lmin（2 ）,…,Lmin（N ）｝。

1.2 克隆选择算法

定义1 抗体则是TSP问题的候选路径（实数编码），即历遍n个城市，且每个城市只经过一次的n个城市序号的排列。

定义2 抗原是求解TSP问题的最短路径。

定义3 亲和度的大小表现为抗体与抗原的结合强度。亲和力计算公式定义如下：

其中，i=1,2,…,m，L（i）是第i只蚂蚁历遍n个城市的路径长度，Lmax为最长路径长度，Lmin为最短路径长度。该式表明，蚂蚁经过n个城市的路径长度越短，其对应的亲和力越大。亲和度越大，表明抗体与抗原之间结合力越强。

定义4 抗体浓度表征抗体种群的多样性好坏，当某抗体对抗原的亲和度高，且抗体浓度低时，该抗体将被大量克隆。

两抗体Xi和Xj之间的相似性程度S（ i,j）计算公式如下：

定义5 克隆增殖是指选择亲和度高的抗体复制。克隆增殖是克隆选择算法所特有的，是依据抗体亲和力和浓度的高低进行克隆：抗体亲和力越高，浓度越低，其被克隆的概率越大，克隆的数目越多。克隆公式如下：

式（2） 中，n为城市数量，Xi（）k表示第i个抗体第k个经过的城市序号。

第i个抗体浓度计算公式为：

θ为克隆比例因子，Cfit（i）为第i个预克隆抗体的亲和力，T（i）为抗体浓度。该式表明，克隆抗体的克隆大小与该抗体的亲和力成正比，与其抗体浓度成反比。

在本文的算法中，首先对抗体的亲和力按递减的顺序排序，然后根据亲和力大小，按照克隆公式确定每个抗体的克隆个数，亲和度大的抗体，克隆规模大；亲和度小的抗体，克隆规模小。克隆增殖可以保证较优的个体有较大的生存空间，提高种群的整体素质。

定义6 克隆变异是指抗体按一定的突变概率，随机选取抗体中两个点互换位置，形成新的抗体。克隆变异可以防止算法早熟，提高算法的全局搜索能力。本算法采用自适应变异概率，根据抗体的亲和力值自适应调整变异概率。克隆变异公式如下：

从式（5）可以看出，抗体的亲和力越大，其对应的变异率就越小。

定义7 克隆选择是指将克隆抗体按亲和力排序，按序选出与疫苗数量相同的抗体。

定义8 克隆删除算子是指删除亲和力低于父代抗体的子代抗体，并用其父代抗体代替。

定义9 抗体补充算子是指随机产生抗体规模为T的候选抗体加入新抗体群，该算子可以增加抗体群的多样性。

1.3 基于引入疫苗策略的克隆选择算法

本文算法在传统免疫克隆选择算法的基础上采用实数编码方式，根据求解问题的要求将抗体种群按亲和度大小选出候选疫苗种群，采用轮盘赌算法划分疫苗和预克隆抗体，根据预克隆抗体亲和度和浓度大小进行克隆和变异抗体，并将疫苗和克隆变异后的抗体交叉接种，最后加入克隆循环补充算子和删除算子。以下是对引入疫苗策略的描述：

定义10 疫苗可以利用所求问题的一些特征信息或问题的先验知识提取，是对最佳个体基因的估计，具备最佳个体局部基因为上可能特征[6]。本文采用轮盘赌随机选择算法从候选疫苗种群（亲和度较高的抗体群）中选出疫苗，将剩余的候选疫苗种群作为预克隆抗体。

定义11 疫苗交叉接种是指将选中的两个疫苗，通过置换各自部分基因，从而产生两个子代的过程。交叉的目的是为了产生下一代新的优良个体，通过交叉操作，可以有效提高算法的搜索能力[7]。本文算法采用多点交叉，先在疫苗的位串无重复的随机选定多个交叉点，并将交叉点之间的疫苗间续地相互交换，产生两个新的后代。多点交叉如图1所示。

图1 多点交叉示意图

2 算法流程图（如图2所示）

3 结果分析

本文使用的是全国31个省会城市作为实例进行测试。改进的克隆选择算法的参数设置如下：抗体种群规模为36，选取候选疫苗库的比例因子为0.7，克隆比例因子为380，抗体变异概率0.01。实验仿真结果如图3、图4所示。由图1可知，本文算法收敛的，在迭代次数达到50次后，最优路径保持在15 669.9634。图4为本文算法优化后的路线图。

图2 算法流程图

图3 亲和度收敛过程

图4 最优化路径图

为验证程序求解效率，本文同时对基于遗传算法（GA）、免疫算法（IA） 和蚁群算法（ACO）解决TSP问题[8]进行了测试，测试的种群规模为36。将4种算法各运行30次，实验最优结果如表1。图5、图6为4种算法的亲和度收敛过程和最优路径图。

从图5可以看出ICSA-VS在迭代50次后，最短路径数值趋于稳定，与其他算法相比，迭代次数最少。虽然IA在算法的运行时间上需要的最少，但是寻优效果没有ICSA-VS好。图6为4种算法优化后的线路图。就最短路径来看，ACO得出的最短路径为15 660.2378，与ICSA-VS的相对误差为0.062%。结合进化代数、计算时间和最短路径来看，ICSA-VS求解TSP问题的效率相对其他算法好。

4 结 论

本文在克隆选择算法基础上引入疫苗接种策略，对路径优化问题建立模型并求解，实验结果表明，该算法采用疫苗选取、克隆增殖、克隆抑制、交叉等策略，使算法具有多样性、随机性、自适应性、收敛性。通过仿真实验，综合进化代数、计算时间和最短路径方面来看，ICSA-VS算法求解问题的效率相对其他算法更好。

表1 4种算法仿真结果对比

图5 4种算法收敛性比较

图6 4种算法得出的最优路径线路图

[1]田玉玲，段富.免疫优化算法、模型及应用[M].北京：国防工业出版社，2013.

[2]De Castro L N,Von Zuben F J.Learning and optimization using the clonal selection principle[J].IEEE Transactions on Evolutionary Computation,2002,6(3):239-251.

[3]张乐，陆金桂.改进的免疫算法求解TSP问题[J].计算机工程与设计，2005,26(4):978-984.

[4]戚玉涛，刘芳，焦李成.求解TSP问题免疫算法的动态疫苗策略[J].西安电子科技大学学报,2008,35(1):37-42.

[5]刘朝华，张英杰，吴建辉.一种求解TSP问题的改进克隆选择算法[J].系统仿真学报，2010,22(7):1627-1631.

[6]丛爽.智能控制系统及其应用[M].合肥：中国科学技术大学出版社，2013.

[7]李荣钧，刘小龙,等.基于微生物行为机制的粒子群优化算法[M].广州：华南理工大学出版社，2015.

[8]包子阳，余继周.智能优化算法及其MATLAB实例[M].北京：电子工业出版社，2016.