用免疫算法求解tsp问题

《用免疫算法求解tsp问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、用免疫算法求解TSP问题1．免疫算法的生物学基础免疫系统是哺乳动物抵御外来有害物质侵害的防御系统，动物一生始终处于复杂多变的、充满伤害的自然环境中，能够平安无事、进行正常的生命活动，免疫系统在其中起着重要的作用。免疫是生物体的特异性生理反应,由具有免疫功能的器官、组织、细胞、免疫效应分子及基因等组成。免疫系统通过分布在全身的不同种类的淋巴细胞识别和清除侵入生物体的抗原性异物。当生物系统受到外界病毒侵害时,便激活自身的免疫系统,其目标是尽可能保证整个生物系统的基本生理功能得到正常运转。免疫功能主要是通过分布全身的免疫细胞来实现

2、的，免疫细胞主要有巨噬细胞、抗体及淋巴细胞等。其中淋巴细胞主要有B细胞和T细胞两种类型，它们是免疫反应中的主要作用细胞根据Burnet的细胞克隆选择学说和Jerne免疫网络学说：生物体内先天具有针对不同抗原特性的多样性B细胞克隆，抗原侵入机体后，在T细胞的识别和控制下，选择并刺激相应的B细胞系，使之活化、增殖并产生特异性抗体结合抗原：同时，抗原与抗体、抗体与抗体之间刺激和抑制关系形成的网络调节结构维持着免疫平衡。图I所示为免疫系统的反应过程的一种抽象描述。当人工免疫系统受到外界攻击时,内在的免疫机制被激活,其目标是保证整个智

3、能信息系统的基本信息处理功能正常运作。免疫系统以其有限的资源，能够有效地应付数量庞大得几近无限的不同种类的病毒的侵害，这一特性无疑引起了人们特别的关注。在学科交叉性越来越大的今天，人们在从医学的角度，分析和研究这一特性的同时，也希望能以此作为启发，设计出新的具有突破性的应用方法，以解决某些应用领域中目前难以解决的难题，免疫算法正是这一思路的产物，是受生物免疫系统的启示而设计出来的一种具有对多峰值函数进行多峰值搜索及全局寻优能力的新型算法。2．免疫算法的提出在生命科学领域中，人们已经对遗传(Heredity)与免疫(Immun

4、ity)等自然现象进行了广泛深入的研究。六十年代Bagley和Rosenberg等先驱在对这些研究成果进行分析与理解的基础上，借鉴其相关内容和知识，特别是遗传学方面的理论与概念，并将其成功应用于工程科学的某些领域，收到了良好的效果。时至八十年代中期，美国Michigan大学的Hollan教授不仅对以前的学者们提出的遗传概念进行了总结与推广，而且给出了简明清晰的算法描述，并由此形成目前一般意义上的遗传算法(GeneticAlgorithm)GA。由于遗传算法较以往传统的搜索算法具有使用方便、鲁棒性强、便于并行处理等特点，因而广

5、泛应用于组合优化、结构设计、人工智能等领域。另一方面，Farmer和Bersini等人也先后在不同时期、不同程度地涉及到了有关免疫的概念。遗传算法是一种具有生成+检测(generateandtest)的迭代过程的搜索算法。从理论上分析，迭代过程中，在保留上一代最佳个体的前提下，遗传算法是全局收敛的。然而，在对算法的实施过程中不难发现两个主要遗传算子都是在一定发生概率的条件下，随机地、没有指导地迭代搜索，因此它们在为群体中的个体提供了进化机会的同时，也无可避免地产生了退化的可能。在某些情况下，这种退化现象还相当明显。另外，每一

6、个待求的实际问题都会有自身一些基本的、显而易见的特征信息或知识。然而遗传算法的交叉和变异算子却相对固定，在求解问题时，可变的灵活程度较小。这无疑对算法的通用性是有益的，但却忽视了问题的特征信息对求解问题时的辅助作用，特别是在求解一些复杂问题时，这种忽视所带来的损失往往就比较明显了。实践也表明，仅仅使用遗传算法或者以其为代表的进化算法，在模仿人类智能处理事物的能力方面还远远不足，还必须更加深层次地挖掘与利用人类的智能资源。从这一点讲，学习生物智能、开发、进而利用生物智能是进化算法乃至智能计算的一个永恒的话题。所以，研究者力图将

7、生命科学中的免疫概念引入到工程实践领域，借助其中的有关知识与理论并将其与已有的一些智能算法有机地结合起来，以建立新的进化理论与算法，来提高算法的整体性能。基于这一思想，将免疫概念及其理论应用于遗传算法，在保留原算法优良特性的前提下，力图有选择、有目的地利用待求问题中的一些特征信息或知识来抑制其优化过程中出现的退化现象，这种算法称为免疫算法(ImmuneAlgorithm)IA。下面将会给出算法的具体步骤，证明其全局收敛性，提出免疫疫苗的选择策略和免疫算子的构造方法，理论分析和对TSP问题的仿真结果表明免疫算法不仅是有效的而且

8、也是可行的，并较好地解决了遗传算法中的退化问题。3．免疫算法中涉及的术语简介抗原：在生命科学中，是指能够刺激和诱导机体的免疫系统使其产生免疫应答，并能与相应的免疫应答产物在体内或体外发生特异性反应的物质。在我们的算法中，是指所有可能错误的基因，即非最佳个体的基因。抗体：在生命科学中，是指免