用免疫算法求解TSP问题-Read

用免疫算法求解TSP问题1．免疫算法的生物学基础免疫系统是哺乳动物抵御外来有害物质侵害的防御系统，动物一生始终处于复杂多变的、充满伤害的自然环境中，能够平安无事、进行正常的生命活动，免疫系统在其中起着重要的作用。免疫是生物体的特异性生理反应,由具有免疫功能的器官、组织、细胞、免疫效应分子及基因等组成。免疫系统通过分布在全身的不同种类的淋巴细胞识别和清除侵入生物体的抗原性异物。当生物系统受到外界病毒侵害时,便激活自身的免疫系统,其目标是尽可能保证整个生物系统的基本生理功能得到正常运转。免疫功能主要是通过分布全身的免疫细胞来实现的，免疫细胞主要有巨噬细胞、抗体及淋巴细胞等。其中淋巴细胞主要有B细胞和T细胞两种类型，它们是免疫反应中的主要作用细胞根据Burnet的细胞克隆选择学说和Jerne免疫网络学说：生物体内先天具有针对不同抗原特性的多样性B细胞克隆，抗原侵入机体后，在T细胞的识别和控制下，选择并刺激相应的B细胞系，使之活化、增殖并产生特异性抗体结合抗原：同时，抗原与抗体、抗体与抗体之间刺激和抑制关系形成的网络调节结构维持着免疫平衡。图I所示为免疫系统的反应过程的一种抽象描述。当人工免疫系统受到外界攻击时,内在的免疫机制被激活,其目标是保证整个智能信息系统的基本信息处理功能正常运作。免疫系统以其有限的资源，能够有效地应付数量庞大得几近无限的不同种类的病毒的侵害，这一特性无疑引起了人们特别的关注。在学科交叉性越来越大的今天，人们在从医学的角度，分析和研究这一特性的同时，也希望能以此作为启发，设计出新的具有突破性的应用方法，以解决某些应用领域中目前难以解决的难题，免疫算法正是这一思路的产物，是受生物免疫系统的启示而设计出来的一种具有对多峰值函数进行多峰值搜索及全局寻优能力的新型算法。2．免疫算法的提出在生命科学领域中，人们已经对遗传(Heredity)与免疫(Immunity)等自然现象进行了广泛深入的研究。六十年代Bagley和Rosenberg等先驱在对这些研究成果进行分析与理解的基础上，借鉴其相关内容和知识，特别是遗传学方面的理论与概念，并将其成功应用于工程科学的某些领域，收到了良好的效果。时至八十年代中期，美国Michigan大学的Hollan教授不仅对以前的学者们提出的遗传概念进行了总结与推广，而且给出了简明清晰的算法描述，并由此形成目前一般意义上的遗传算法(GeneticAlgorithm)GA。由于遗传算法较以往传统的搜索算法具有使用方便、鲁棒性强、便于并行处理等特点，因而广泛应用于组合优化、结构设计、人工智能等领域。另一方面，Farmer和Bersini等人也先后在不同时期、不同程度地涉及到了有关免疫的概念。遗传算法是一种具有生成+检测(generateandtest)的迭代过程的搜索算法。从理论上分析，迭代过程中，在保留上一代最佳个体的前提下，遗传算法是全局收敛的。然而，在对算法的实施过程中不难发现两个主要遗传算子都是在一定发生概率的条件下，随机地、没有指导地迭代搜索，因此它们在为群体中的个体提供了进化机会的同时，也无可避免地产生了退化的可能。在某些情况下，这种退化现象还相当明显。另外，每一个待求的实际问题都会有自身一些基本的、显而易见的特征信息或知识。然而遗传算法的交叉和变异算子却相对固定，在求解问题时，可变的灵活程度较小。这无疑对算法的通用性是有益的，但却忽视了问题的特征信息对求解问题时的辅助作用，特别是在求解一些复杂问题时，这种忽视所带来的损失往往就比较明显了。实践也表明，仅仅使用遗传算法或者以其为代表的进化算法，在模仿人类智能处理事物的能力方面还远远不足，还必须更加深层次地挖掘与利用人类的智能资源。从这一点讲，学习生物智能、开发、进而利用生物智能是进化算法乃至智能计算的一个永恒的话题。所以，研究者力图将生命科学中的免疫概念引入到工程实践领域，借助其中的有关知识与理论并将其与已有的一些智能算法有机地结合起来，以建立新的进化理论与算法，来提高算法的整体性能。基于这一思想，将免疫概念及其理论应用于遗传算法，在保留原算法优良特性的前提下，力图有选择、有目的地利用待求问题中的一些特征信息或知识来抑制其优化过程中出现的退化现象，这种算法称为免疫算法(ImmuneAlgorithm)IA。下面将会给出算法的具体步骤，证明其全局收敛性，提出免疫疫苗的选择策略和免疫算子的构造方法，理论分析和对TSP问题的仿真结果表明免疫算法不仅是有效的而且也是可行的，并较好地解决了遗传算法中的退化问题。3．免疫算法中涉及的术语简介抗原：在生命科学中，是指能够刺激和诱导机体的免疫系统使其产生免疫应答，并能与相应的免疫应答产物在体内或体外发生特异性反应的物质。在我们的算法中，是指所有可能错误的基因，即非最佳个体的基因。抗体：在生命科学中，是指免疫系统受抗原刺激后，免疫细胞转化为浆细胞并产生能与抗原发生特异性结合的免疫球蛋白，该免疫球蛋白即为抗体。在本文中是指根据疫苗修正某个个体的基因所得到的新个体。其中，根据疫苗修正某个个体基因的过程即为接种疫苗，其目的是消除抗原在新个体产生时所带来的负面影响。免疫疫苗：根据进化环境或带球问题，所得到的对最佳个体基因的估计。免疫算子：同生命科学中的免疫理论类似，免疫算子也分两种类型：全免疫和目标免疫，二者分别对应于生命科学中的非特异性免疫和特异性免疫。其中，全免疫是指群体中每个个体在变异操作后，对其每一环节都进行一次免疫操作的免疫类型；目标免疫则指个体在进行变异操作后，经过一定判断，个体仅在作用点处发生免疫反应的一种类型。前者主要应用于个体进化的初始阶段，而在进化过程中基本上不发生作用，否则将很有可能产生通常意义上所说的“同化现象”；后者一般而言将伴随群体进化的全部过程,也是免疫操作的一个常用算子。免疫调节：在免疫反应过程中，大量的抗体的产生降低了抗原对免疫细胞的刺激，从而抑制抗体的分化和增殖，同时产生的抗体之间也存在着相互刺激和抑制的关系，这种抗原与抗体、抗体与抗体之间的相互制约关系使抗体免疫反应维持一定的强度，保证机体的免疫平衡。免疫记忆：指免疫系统将能与抗原发生反应的抗体作为记忆细胞保存记忆下来，当同类抗原再次侵入时，相应的记忆细胞被激活而产生大量的抗体，缩短免疫反应时间。抗原识别：通过表达在抗原表面的表位和抗体分子表面的对位的化学基进行相互匹配选择完成识别，这种匹配过程也是一个不断对抗原学习的过程，最终能选择产生最适当的抗体与抗原结合而排除抗原。 4．免疫算法的算法思想、具体步骤免疫算法主要包括如下几个关键步骤：(1)产生初始群体：对初次应答，初始抗体随机产生;而对再次应答，则借助免疫机制的记忆功能，部分初始抗体由记忆单元获取。由于记忆单元中抗体具有较高的适应度和较好的解群分布，因此可提高收敛速度。(2)根据先验知识抽取疫苗(3)计算抗体适应度(4)收敛判断若当前种群中包含了最佳个体或达到最大进化代数，则结束算法;否则进行以下步骤。(5)产生新抗体每一代新抗体主要通过两条途径产生：(a)基于遗传操作生成新抗体:采用赌轮盘选择机制，当群体相似度小于阀值A0时，多样性满足要求，则抗体被选中的概率正比于适应度;反之，按下述(b)的方式产生新抗体，交叉和变异操作均采用单点方式。(b)随机产生P个新抗体：为保证抗体多样性，模仿免疫系统细胞的新陈代谢功能，随机产生P个新抗体，使抗体总数为N+P，再根据群体更新，产生规模为N的下一代群体。(6)群体更新：对种群进行接种疫苗和免疫选择操作，得到新一代规模为N的父代种群，返回步骤3免疫算法的流程图如下：根据流程图具体过程为：①随机产生初始父代种群A1；②根据先验知识抽取疫苗；③若当前群体中包含最佳个体,则算法停止运行并输出结果;否则继续；④对于目前的第k代父本种群Ak进行交叉操作，得到种群Bk；⑤对Bk进行变异操作，得到种群Ck；⑥对Ck进行接种疫苗操作，得到种群Dk；⑦对Dk进行免疫选择操作，得到新一代父本Ak+1,转至③。5．免疫算法的收敛性一代种群的规模为n0，则所有种群的规模均为n0，种群中的所有个体均为l位的q进制编码。算法中的交叉操作选择一点或多点均可。变异操作是对每个基因位以概率PM相互独立地进行变异，变异后处于其它任一状态的概率均为1/q-1。算法的状态转移情况可用如下的随机过程来表述：其中从Ak到Dk的状态转换构成了马尔可夫链，而Ak+1的状态与前面各变量的状态均有关。但是随机过程{Ak|k=1,2,…,}显然仍是一个马尔可夫过程。设X为搜索空间,即所有个体的空间，将规模为n0的群体认为是状态空间S=Xn0中的一个点，其每个坐标分别是X中的个体。用|S|表示S中状态的数量，用，i=1，2，…，|S|，表示si是S中的某一状态，用表示si，sj作为X的子集时的包含关系。用表示随机变量V在第k代时处于状态si。设f是X上的适应度函数，令则可如下定义算法的收敛性。定义1如果对于任意的初始分布均有，则称算法收敛。该定义表明：算法收敛是指当算法迭代到足够多的次数以后，群体中包含全局最佳个体的概率接近于1。这种定义即为通常所说的概率1收敛。定理免疫算法是概率1收敛的。定理的证明过程略。不过，这里需要说明的一点是，如果把免疫算子从免疫算法中略去，可以证明该算法将不再保证收敛到全局最优值，或者说它是强不收敛的。6．TSP问题描述TSP问题是优化搜索算法尝试求解的经典问题之一，属于NP完全问题。TSP问题是旅行商问题的简称，即一个商人从某一城市出发，要遍历所有目标城市，其中每个城市必须而且只须访问一次。TSP问题是寻找一条最短的遍历n个城市的路径，或者说搜索整数子集X={1，2，…，n}(X的元素表示对n个城市的编号)的一个排列{V1，V2，..…Vn)，使取最小值，式中的表示城市到城市的距离。由于它是诸多领域内出现的多种复杂问题的集中概括和简化形式，所以成为各种启发式的搜索、优化算法的间接比较标准。该问题是一个典型的NP问题，即随着规模的增加，可行解的数目将做指数级增长。6.免疫算子的构造方法免疫算子包括全免疫和目标免疫两种。对于TSP问题，要找到适用于整个抗原(即全局问题求解)的疫苗极为困难，所以不妨采用目标免疫。具体而言，在求解问题之前先从每个城市点的周围各点中选取一个路径最近的点，以此作为算法执行过程中对该城市点进行目标免疫操作时所注人的疫苗。每次遗传操作后，随机抽取一些个体注射疫苗，然后进行免疫检测，即对接种了疫苗的个体进行检测：若适应度提高，则继续；反之，若其适应度仍不如父代，说明在交叉、变异的过程中出现了严重的退化现象，这时该个体将被父代中所对应的个体所取代。在选择阶段，先计算其被选中的概率，后进行相应的条件判断。7．免疫疫苗的选取具体步骤如下：(1)分析待求问题,搜集特征信息假设在某一时刻,某人从一城市出发,欲前往下一个目标城市.一般而言,他首先考虑的选择目标是距离当地路程最近的城市.如果目标城市恰恰就是前面走过的某一城市时,则下一个要到达的目标更替为除该城市之外的距离最小的城市,并以此类推.这种方法虽然不能作为全局问题的解决方案,但在一个很小范围内,比如只有三四个城市的情况(相对于全局问题而言,这属于一种局部问题),这种考虑往往不失为一个较好的策略.当然,能否作为最终的解决方案,还需要进一步的判断.(2)根据特征信息制作免疫疫苗基于上述认识，就TSP问题的特点而言,在最终的解决方案中,即最佳路径的选取里，必然包括而且在很大程度上包括相邻城市间距离最短的路径。TSP问题的这种特点即可作为求解问题时以供参考的一种特征信息或知识，故能够视为从问题中抽取疫苗的一种途径。所以在具体实施过程中，只需使用一般的循环迭代方法找出所有城市的邻近城市即可(当然，某一城市既可能是两个或多个城市的邻近城市，也可能都不是)；疫苗不是一个个体，故不能作为问题的解。它仅仅具备个体在某些基因位上的特征。(3)接种疫苗设TSP问题中所有与城市Ai距离最近的城市为Aj，并且二者非直接连接而是处于某一路径的两段：Ai-1----Ai----Ai+1和Aj-1----Aj-----Aj+1，则当前的遍历路径为：P={A0,…,Ai-1,Ai,Ai+1,…,Aj-1,Aj,Aj+1,…,AN}，其对应的路径长度为：(1)在免疫概率Pi发生条件下，对城市Ai而言,免疫算子将把其邻近城市Aj排列为它的下一个目标城市，而使原先的遍历路径调整为：πc={A0,…,Ai-1,Ai,Aj,Ai+1,…,Aj-1,Aj+1,…,AN}，则相应的路径长度变化为：(2)比较式(1)和式(2)，因为Aj是所有城市中(即全局中)与城市Ai距离最近的点，在由Ai----Aj-----Ai+1所构成的三角形中l1一定为最短边或次短边(此时l2一定为最短边.因为若ai<l1，则与Ai最近的城市为Ai+1而非Aj)，而在Aj-1，Aj和Aj+1之间却不一定具有这个性质。所以在多数情况下，l3较aj-1+aj的减少量要大于l1+l2较ai的增加量。而且更加重要的是在这一个局部环境内，算子对路径做了一次最佳调整。当然，这次调整究其能否对整个路径有所贡献，还有待于选择机制的进一步判断。但是，从分析过程中，不难得出下列关系：，式中,P(A)表示事件A发生的概率。上述所谓的“调整”过程，即为是TSP问题求解时基于某一特定疫苗的免疫注射过程。8．免疫算法的程序求解框图如图所示。具体过程如下：(1)个体编码和适应度函数算法实现中，将TSP问题的目标函数对应于抗原，问题的解对应于抗体。抗体采用以遍历城市的次序排列进行编码，每一抗体码串形如:V1，V2，…，Vn，其中，Vi表示遍历城市的序号。适应度函数取路径长度Td倒数，即：表示第i个抗体所表示的遍历城市的路径长度。(2)交叉与变异算子采用单点交叉，其中交叉点的位置随机确定。对于免疫操作，算法中加人了对遗传个体基因型特征的继承性和对进一步优化所需个体特征的多样性进行评测的环节，在此基础上设计了一种部分路径变异法。该方法每次