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

1基于免疫算法的TSP问题求解摘要：TSP问题(TravelingSalesmanProblem)是一个典型的组合优化问题，有效地解决TSP问题在可计算理论上有着重要的理论价值，本文介绍了一种基于免疫算法的解决TSP问题的方法，体现了免疫算法在进化计算过程中的抗原学习、记忆机制、浓度调节机制以及多样性抗体保持策略等优良特性，这使得免疫算法有较强的收敛性和较好的求解结果。关键词：TSP、免疫算法、记忆机制、抗体SolvingTheTSPProblemBasedonImmuneAlgorithmAbstract：TheTSP(TravelingSalesmanProblem)isatypicalcombinatorialoptimizationproblemeffectivelysolvetheproblemincomputabilitytheoryTSPhasimportanttheoreticalvalue,thispaperpresentsamethodtosolvetheTSPimmunealgorithmbasedonimmunealgorithmreflectsantigenlearningprocessofevolutionarycomputation,memorymechanism,theantibodyconcentrationwasadjustedtomaintainthediversityofmechanismsandstrategiesofexcellentfeatures,whichmakesitimmunealgorithmhasstrongconvergenceandbettersolutionresults.Keywords：TSP,ImmuneAlgorithm,Memorymechanism,Antibody1.引言近年来，越来越多的学者把生物免疫系统的一些行为引入到传统的仿生算法中，构造出的免疫算法可以大大提高传统仿生算法的效率。生物免疫系统的免疫功能是通过抗体消灭入侵的病原体的（抗原）来实现的，人工免疫算法就是模拟生物免疫系统的这一功能实现的。TSP问题是典型的组合优化问题，本文描述了免疫算法中的一种框架结构，该算法在进化计算过程中的抗原学习、记忆体制、浓度调节机制和抗体多样性保持策略都有着优良特性，加快了求解的效率，更有效的避免了在进化过程中的未成熟收敛，表明了免疫算法在解决组合优化问题时的优良性能。22.免疫算法2.1免疫算法的生物学基础生物免疫系统是由某些特殊的化学分子、细胞、组织、器官组成的分布式复杂自适应系统。免疫系统的主要功能是区分体内所有的细胞或分子是否对身体有害，并对有害的物质进行清除。生物免疫过程：生物体内具有针对不同抗原特性的多样的B细胞，抗原侵入机体后，在T细胞的识别和控制下，选择并刺激相应的B细胞系，使之分化、复制产生特异性抗体与对应的抗原相结合。免疫记忆则是指免疫系统在对侵入的抗原产生抗体之后，会将抗体作为记忆细胞保存下来，当同类抗原再次入侵时，会快速产生大量抗体，缩短了免疫反应的时间。并且在免疫反应过程中，产生大量的抗体之后，抗原对免疫细胞的刺激减小，从而抑制了抗体的继续产生，同时产生的抗体之间也存在着相互制约的关系，这种相互制约的关系保证了机体的免疫平衡。免疫系统有很强的自适应性，入侵的抗原有性异物对于免疫系统来说具有不可预知性，免疫系统无法预先产生抗体来对付抗原。但是免疫系统会有一个自适应的机制来保证初次应答的成功，并通过免疫记忆细胞的产生，使得二次应答更加地高效。2.2免疫算法的描述免度算法是抽取和反映生机体免疫系统的上述特点，结合工程应用而描述的一种计算模型，抗原对应于待求解的问题，而抗体则对应于问题的一个解。免疫算法的结构如图1所示。抗原的识别初始抗体产生抗体适应度评价抗体长生（新陈代谢，交叉，变异）抗体产生的刺激与抑制群体更新输出结果满足终止记忆细胞库图1免疫算法结构框图3算法的主要步骤如下：步骤1抗原产生：最优化问题的目标函数和约束条件的描述。步骤2初始抗体产生：把抗体定义为目标函数在约束条件下的可行解。步骤3亲和力计算：计算解群中每一个解的亲和力或者适应度，并为后面的记忆细胞的产生提供依据。步骤4产生记忆细胞：按亲和度的高低进行排序，从中选择亲和度较高的个体构成新的群体,取前几个抗体构成记忆库。步骤5抗体的促进和抑制：计算抗体的浓度，并结合前面的抗体适应度来确定抗体的死亡和分裂的概率。步骤6群体更新：利用交叉和变异算子对抗体进行进化更新。步骤7终止条件判断：判断是否满足终止条件(找到最优解或达到最大迭代次数)：是则算法结束；否则继续。3.基于免疫算法的TSP问题求解3.1TSP问题的描述TSP问题寻找一条最短的遍历n个城市的路径，或者说搜索整数子集X={1，2,...n}(X的元素表示对n个城市的编号)的一个排列{V1，V2，...Vn}，使)1,()1,()(1n1iViVidViVidiTd取最小值，式中的d(Vi，Vi+1)表示城市Vi到城市Vi+1的距离。由于它是诸多领域内出现的多种复杂问题的集中概括和简化形式，所以成为各种启发式的搜索、优化算法的间接比较标准。在工程中，很多问题可以抽象为TSP问题，并且TSP问题经常被作为测试对象用于各种算法的性能比较，因此TSP问题是一个既有理论价值又有广泛的工程应用价值的组合优化问题。3.2免疫算法对TSP问题的求解（1）抗体编码方式及适应度函数抗体采用以遍历城市的次序排列进行编码，每一抗体码串形如:V1，V2，...Vn其中，Vi从表示遍历城市的序号。程序中抗体定义为一维数组A(N)，N表示为TSP问题中的城市数目，数组中的各个元素A(i)(i{l，2，...，N}的取值为1至N间的整数，分别表示城市的序号，根据问越的约束条件，每一数组内的各元素值互不相同。适应度函数取路径长度Td的倒数，即Fitness（i）=1/Td(i)，)1,()1,()(1n1iViVidViVidiTd表示第i个抗体所表示的遍历城市路径长度。（2）初始抗体群的产生初始抗体在解空间中用随机的方法产生I个初始抗体，形成初始抗体群。若4待求解问题与记忆细胞中抗体相匹配时，则由匹配的记忆细胞组成初始抗体群，不足部分的抗体随机产生。（3）新抗体的产生字符换位操作：单对字符换位操作是对抗体A(N)=(V1，V2,…Vn)，随机取两个正整数i，j(1i，jn，i≠j)，以一定的概率P(0P1)交换抗体A中一对字符Vi，Vj的位置；多对字符换位操作是预先确定一个正整数u，随机取一个正整数r(1ru)，在抗体A(N)中随机取r对字符作字符换位操作。字符串移位操作：单个字符串移位操作是对抗体A(N)=(V1，V2，...Vn)，随机取两个正整数i，j(1i，jn，i≠j)，从A中取出一个字符子串A1，A1=(Vi，Vi+1,…Vj)，以一定的概率P(0P1)依次往左(或往右)移动字符串An中的各个字符，最左(或最右)边的一个字符则移动到最右(或最左)边的位置；多个字符串换位操作是预先确定一个正整数u，随机取一个正整数r(1ru)，再在抗体A中随机取r个字符子串作字符串移位操作。字符串逆转操作：单个字符串逆转操作是对抗体A(N)=(V1，V2,…Vn)，随机取两个正整数i，j(1i，jn，i≠j)，从A中取出一个字符子串A1，A1=(Vi，Vi+1，...Vj)，以一定的概率P(0P1)使字符串A1中的各个字符首尾倒置；多个字符串逆转操作是预先确定一个正整数u，随机取一个正整数r(1ru)，再在抗体A中随机取r个字符子串作字符串逆转操作。字符重组操作：字符重组操作是在抗体A(N)=(V1，V2,…Vn)中，随机取一个字符子串A1，A1=(Vi，Vi+1,…Vj)，以一定的概率P(0P1)使字符串A1中字符重新排列，重新排列的目的是提高抗体的亲和力。\（4）免疫记忆抗体记忆机制是免疫算法的一个很大的优势。系统在完成一个问题的求解后，能保留一定规模的求解过程中的较优抗体，在系统接收同类抗原时，以所保留的记忆细胞作为初始群体，从而提高了问题求解的收敛速度，体现了免疫算法二次应答时的快速求解能力。在求解过程中每一代的抗体群更新时，将适应度最好的M个抗体存入记忆细胞库，并比较库中是否有与入选抗体相同的记忆细胞，保证记忆细胞的多样性。3.3实验仿真及其结果实验模拟了42个城市之间求最短路径问题，实验给出了42个城市之间的相互距离。该实验设定的各参数为：pCharChange=1;%字符换位概率pStrChange=0.4;%字符串移位概率pStrReverse=0.4;%字符串逆转概率pCharReCompose=0.4;%字符重组概率MaxIterateNum=1500;%最大迭代次数经过1500次迭代进化，如下图所示，在900次进化之后基本稳定在最佳路径1300左右。理论上一个最佳结果为1273。基本上在经过1500次进化后，该算法基本上可以找到42个城市之间的最短路径约1300。54.总结本文系统的介绍了一种模拟生物免疫系统的免疫算法，给出了算法的基本步骤，并且详细介绍了基于免疫算法如何求解TSP问题，以及在解决TSP问题上，免疫算法相比于传统算法有更好的优化性能，免疫算法在免疫识别、免疫记忆，免疫调节，多样性保持等方面有着很大的优势。5.参考文献[1]焦李成，杜海峰，刘芳等.免疫优化计算、学习与识别[J].北京：科学出版社，2009.[2]吴昳恬.基于免疫算法的TSP问题求解[D].苏州：苏州大学,2010:1-45.[3]李茂军，罗安.人工免疫算法及其应用[J].控制理论及其应用，2004(4)26.[4]刘克胜，曹先彬，郑浩然，王煦法.基于免疫算法的TSP问题求解[J].计算机工程,2000(26)1.