英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
基于贪婪算法和删除交叉算子的混合免疫算法求解TSP
郭潘 李肯立 欧阳爱家 李克勤
摘要 本文介绍了免疫算法（IA）、贪婪算法（GA）和删除交叉算子（DO）的基本原理。在此基础上，构造了求解旅行商问题的混合免疫算法（HIA）。HIA算法利用遗传算法初始化TSP的路径，利用DO删除路径，采用动态置换算子（DMO）提高搜索精度，提高了混合后全局最优的可能性。实验结果表明，与其它算法相比，HIA算法能够得到更好的解，且计算量小。
关键词 删除交叉算子 动态突变 贪婪算法 免疫算法 TSP问题
1 介绍
TSP问题是一类工程性强，适用性广的经典组合优化问题。TSP问题可以正式的被描述为：已知N个城市C={C1，C2，hellip;，CN}，两个随机选择的城市之间的距离表示为d（C i，C j），那么只需一次通过C内所有城市的闭合路径的解将为C pi;={C pi;（1），C pi;（2），hellip;，C pi;（N）}，以最小化总行程距离 Nminus;1i=1d（C pi;（i），C pi;（i 1）） d（C pi;（N），C pi;（1））。TSP有多种类型，如多目标TSP（Shim等人，2002，2012），动态TSP（Cheong and White 2012），杜宾TSP（Le 等人，2012），序列相关TSP（Alkaya and Duman，2013），双TSP（Carrabs等人，2013）。对于大规模TSP问题，人们往往会在一定的时间内给出一个可接受的近似解。TSP问题的近似算法可分为旅游构造算法和旅游改进算法。旅游构建算法从一个非法解开始，逐步改变路径，直到获得合法的路径。这类算法包括Clarke-Wright算法（Clarke and Wright， 1964）、最近邻算法（Hurkens and Woeginger， 2004）、贪婪算法（Hassin and Keinan， 2008）和Christofides算法（An等人，2012），等等。旅游改善算法在获得初始合法解之后，采用一定的策略寻找质量更好的解决方案。这些类型的算法包括局部搜索策略（Opt，LK，LKH，LKcirculation，Karapetyan and Gutin 2011），等等）、禁忌搜索（Pedro等人，2013），模拟退火（Kalender等人，2013），布谷鸟搜索算法（Ouarab等人，2013），粒子群算法（Beheshti等人，2013），蚁群优化算法（Gan等人，2010；Cecilia等人，2013；Mavrovouniotis和Yang 2013；Mora等人，2013），神经网络（Yang and Yi， 2013），模因算法（Badillo等人，2013），GA–PSO–ACO（Deng等人，2012），人工蜂群算法（Marinakis等人，2011；Kıran等人，2013）、遗传算法（Yuantal.2013；Nagatandsoler， 2012）、多智能体优化系统（Xie和Liu ，2009）和人工疫苗（Montiel和Diaz Delgadillo ，2013）等。
人工免疫系统通过模拟生物免疫系统的免疫反应、免疫记忆和免疫调节机制，构建了一个具有较强坚固性的自组织人工智能系统。随着对人工免疫系统研究的不断深入，人工免疫问题已经成为继神经网络、模糊逻辑和进化计算之后的又一个研究热点（Dasgupta和Forrest，1999）。基于免疫理论，目前已经提出了几种启发式算法。1995年，亨特和他的同事提出了第一个人工免疫系统模型，即B细胞网络模型（亨特和库克，1995年）。春（1997）提出了另一种基于免疫网络理论的免疫算法，该算法根据个体的价值和相似性进行选择操作，从而抑制相似个体，保持种群的多样性。从这个角度看，该算法具有在全局寻找最优能力。De Castro和Von Zuben（2002）提出了一种模仿免疫系统克隆选择的克隆选择算法。具体来说，该算法通过对选定个体进行克隆和变异操作，进行局部最优的搜索，用随机产生的个体替换种群中具有低适应值的个体，以保证种群的多样性。
免疫算法中的选择、交叉、变异和免疫算子是影响算法全局搜索性能的重要因素。然而，免疫算法在免疫操作中的搜索方向总是被忽略了。为了获得高性能的备用解，搜索方向应该能够指示免疫算法在某些区域内的潜在方向。在免疫操作中采用随机数通常会使候选解在搜索空间中处于随机位置。如果最优解的位置离当前的搜索空间较远，而当前的搜索空间无法初步识别，则会降低最优解的定位速度，特别是在多优化问题中。
对于免疫算法收敛速度慢、精度低的问题，提出了求解TSP问题的HIA算法。本文的主要工作概括是：采用混合方法，用免疫算法对个体进行全局搜索，用贪婪算法初始化种群，用交叉删除算子对染色体进行局部搜索。在对个体进行升级时，采用基于动态变异概率的高频变异算子对变异算子进行改进。这些策略强调了免疫算法潜在的搜索方向，使后代有机会朝着这个方向前进，寻找其他高质量的空间。因此，强化的高级抗体可实现成熟的鉴定，并在深度开发和广泛勘探之间取得平衡。对TSP问题的结论表明，HIA算法具有可靠的全局收敛性和较快的收敛速度。
我们论文的其余部分安排如下：有向图和TSP的定义在第2节中。然后，我们描述了IA、GA和DO的基本原理。第3,4节提出了TSP的HIA算法。第五节给出了实验结果和分析。最后，在第6节对第五节的工作进行了总结。
2 TSP说明
定义1 有向图假定有向图D的三元组由V，E和F组成，其中V是一个非空集，其元素称为有向点的节点；E是一个集，其元素称为分段弧（边）；F是E到Vtimes;V的映射（函数）。
定义2 假设C={c1，c2，hellip;，cn}是n个城市的集合。L={lij | cj，cjsub;C}是由C集中的两个随机因素（城市）连接而成的集合。dij（i，j=1,2，，n）是lij的欧几里德距离，
dij =(xi minus;xj)2 (yi minus;yj)2 (1)
G = (C, L)是有向图。TSP的目的是寻找有向图D中的最短Hamilton圈，它实质上是访问C={c1，c2，hellip;，cn}中所有因子（城市）且只发生一次的最短闭路程。
隐喻的说，TSP可以简单地描述为：假设有n个城市，一个旅行推销员从一个城市出发，一个接一个地旅行到所有其他城市，然后返回最初的城市。寻找一条最短的路线。
TSP可分为对称旅行商问题和非对称旅行商问题。如果A到B的距离与B到A的距离相同，则称为对称TSP，否则称为非对称TSP。对称TSP问题将是本文研究的重点。
给定的TSP数据包括有限完备图中各边的权重，其目的是搜索具有最小总权重的Hamilton循环。具有n个城市的TSP有不同的封闭路径，解决这一问题的最佳方法是全局搜索，但当n较大时，用全局搜索无法找到精确的最优解。由于TSP问题具有很高的代表性和广泛的适用性，许多问题都可以作为TSP问题来建模和求最优解。
3 基本算法
3.1 免疫算法
3.1.1 基本原则
免疫系统是保护生物体免受病原体或细菌入侵的自然防御系统。对这些病原体的永久性免疫应答周期表现出许多动态特征（Zhang and Qian ，2011；Zhang 等人，2014）。
生物免疫系统是一种高度进化的生物系统，目的是将外界有害抗原与体内组织相区分，从而维持机体的稳定。从计算的角度看，生物免疫系统是一个高度的并发、分布、自适应、自组织的系统。它在学习、识别和记忆能力方面都是十分优秀的。
免疫系统具有以下特点：
–产生多种抗体的能力。免疫系统可以产生大量抗体来抵抗各种抗原。
–自我调节机制。免疫系统具有维持平衡的机制，在抑制或增强抗体后，可以通过产生适量的必需抗体来进行自身调节。
–免疫记忆功能。产生抗体的部分细胞将作为记忆保存，在未来同类抗原入侵时，相应的记忆细胞将立即被触发，并产生大量抗体。
免疫算法是在人工免疫基础理论（IEEE 2013）的基础上发展起来的，是人工免疫理论应用和研究的拓展和发展。由于人工免疫是以生物免疫系统的基本概念和理论为基础的，因此生物免疫系统理论被认为是免疫算法的最直接的来源。免疫算法主要针对免疫系统的抗原识别、免疫记忆和免疫调节等特点，将免疫系统的概念和理论应用到计算中。其中，抗原识别是通过表达抗原表面表位与抗体表面对应点之间的相互匹配和选择来完成识别的过程。免疫记忆是指免疫系统能够将与抗原反应的抗体作为记忆细胞来维持和记忆，当同类抗原再次入侵时，系统会立即识别反应的过程。当抗原对免疫细胞的刺激因产生大量抗体而减少时，免疫调节发生在免疫反应过程中。在这样的背景下，抗体的分化和增殖受到抑制，抗原和抗体之间以及两种抗体之间的平衡可以得到一定程度的维持。此外，免疫算法的核心在于免疫的疫苗，它植根于生物疫苗的概念和理论。生物疫苗是医学科学家根据免疫系统的免疫记忆特性发明的，通过疫苗注射可以实现抗原的快速识别。
生物疫苗是医学科学家根据免疫系统的免疫记忆特性而发明的，通过疫苗注射可以实现抗原的快速识别。免疫算法是在抽象和反映人工免疫理论的基础上，结合遗传算法求解科学、技术和工程领域各种组合搜索和优化计算问题的计算模型。采用该模型时，我们可以将问题和解决方案分别抽象为抗原和抗体，模型中的疫苗对应于待解决问题的解决方案的某些特征信息。免疫算法继承了遗传算法的遗传算子，具有较强的全局搜索能力。除此之外，加入的免疫算子使免疫算法能够有效地防止遗传算法后期的退化，加快收敛速度。此外，根据相关理论，免疫算法的收敛概率为1，说明其具有较强的收敛性。
免疫算法和遗传算法都采用全局搜索策略，优先考虑群体中个体之间的信息交换。因此，他们有很多共同点。例如，它们具有几乎相同的算法结构，迭代过程由初始种群的生成、评估准则的计算、种群中个体之间的信息交换和新种群的生成组成。另外，这两种算法具有并行性和内在的优越性，可以与其他智能计算方法相结合。
然而，免疫算法和遗传算法之间确实存在一些差异，主要表现在个体的评价、选择和产生方式上。在遗传算法中（Xu等人，2014），通过计算个人能力对个人进行评估，这是算法中选择父母个人的唯一标准。在免疫算法中，对个体的评估是通过计算个体的可信度来完成的，个体的选择是基于此。个体的密切关系包含抗体-抗原的密切关系（匹配度）和抗体-抗体的密切关系（相似度）。它反映了真实免疫系统的多样性，因此它对个体的评价更为全面，因此在免疫算法中个体选择更为合理。另外，免疫算法中的交叉、变异等免疫操作也可以产生新的个体。尽管交叉和变异等固有免疫操作广泛应用于免疫研究中，但算法中缺少的一些机制可以用来产生新的抗体。这些机制包括克隆选择、免疫记忆和免疫接种，同时免疫算法可以促进或抑制抗体的产生。这反映了免疫反应的自我调节功能，保证了个体的多样性。此外，免疫算法收敛速度快，最大可能找出局部最优解（Ding等人，2012；Chen等人，2013）。
3.1.2 基本定义
定义3 生物科学中的抗原：抗原是一种能够刺激免疫系统并诱导其产生免疫反应，然后与相应的免疫反应产物发生体内或体外特异性反应的物质。在本文的算法中，抗原是指所有可能的错误基因，它们都是个体的非最优的基因。
定义4 生物科学中的抗体：抗体是指在抗原刺激免疫系统后，在免疫细胞转化为浆细胞的过程中，能够实现与抗原歧化的特异性结合的免疫球蛋白。本文中的抗体是指在一定的校正个体基因基础上产生的新个体，校正一定个体基因的过程称为疫苗接种，其目的是在疫苗产生时通过免疫消除免疫效应。
定义5 免疫疫苗：这里的免疫疫苗是指根据环境演变或需要解决的问题，对获得的最佳个体基因进行评估。
定义6 免疫算子：与生物科学中的免疫理论相似，免疫算子分为两类：泛免疫和多免疫，这两类分别对应于生物科学中的非特异性免疫和特异性免疫。泛免疫是群体中个体的变异操作后，在每个阶段进行免疫操作的免疫类型。目的免疫是指个体对其突变操作有一定判断后，仅在应用点出现免疫反应的免疫类型。前者主要发生在个体进化的初始阶段，在进化过程中基本不起作用，否则，通常情况下很可能发生同化，后者通常伴随着种群进化的整个过程，是免疫操作中常用的算子。
定义7 免疫调节：在免疫过程中，许多抗体的产生会降低抗原对免疫细胞的刺激，抑制抗体的分化和增殖。同时产生的抗体之间存在着相互刺激和相互制约的关系。抗原和抗体之间以及不同抗体之间的相互制约，使抗体保持在一定的强度，进一步保持机体中的免疫平衡。
定义8免疫记忆：免疫记忆是指免疫系统能够记忆和保存对抗原有反应的抗体。当同类抗原再次入侵时，相应的记忆细胞就会被激活，从而产生大量的抗体。免疫反应时间短，抗原识别是通过表达抗原表面的表位与抗体表面的化学对位之间的相互匹配和选择来完成识别的过程。匹配过程也是一个不断学习抗原的过程，最终选择最合适的抗体与抗原结合，后者会被淘汰。
3.1.3 免疫算法的发展
1. 免疫育苗的提取
在免疫算法中，疫苗是指从先验知识中提取的一种特征信息，详细地解决问题。它可以看作是待解决问题的最佳个体匹配模型的估计。作为一种独特的个体更新和优化机制，疫苗的正确选择是有效实现免疫操作的前提，对算法的运行效率和性能具有重要意义。对于某一问题的疫苗选择过程，可以根据问题的特征信息来制作疫苗。根据实际问题的不同，提取方法也不同。例如，在解决TSP问题时，可以将不同城市之间的距离都视为疫苗；在应用于模型识别的分类和聚类时，可以将样本与模板或样本之间的特征值距离也视为疫苗；每一代的最佳解决方案可以看作是疫苗以及动态建立疫苗数据库。当当前的最佳疫苗比库中最差的疫苗具有更高的可信度时，最差的疫苗将被替换。
- 疫苗接种操作
如上所述，疫苗来自对问题的先验知识。信息量和准确性对算法的性能有很大影响。假设群体规模为N，根据概率alpha;从抗体群体中选择alpha;times;N抗体。对其进
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[241489]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
