研究人工免疫算法中旅行商问题

《研究人工免疫算法中旅行商问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、研究人工免疫算法中旅行商问题　　0.引言早在18世纪，爱尔兰的数学家哈密尔顿和英国的数学家托马斯就已经对旅行商问题（TSP）进行数学研究，而旅行商问题一般形式的研究则是由数学家卡尔·门格尔于19世纪三十年代在维也纳和哈佛大学首次进行研究的。对旅行商问题的研究往往是出于把它作为一个可应用于解决大规模的组合最优化问题的一般方法的一个平台，然而这并不是说在很多领域中旅行商问题找不到其具体的应用。事实上，旅行商问题有许许多多的应用，它可以看成是许多领域内复杂工程优化问题的抽象形式，诸如邮路问题、网络布线问题、物流配送问题、电路板钻孔问题等等，这些应用给旅行商问题的研究带来了活力，

2、并且帮助指导今后的研究工作。旅行商问题本身的应用范围正在不断扩张，它的研究方法也正迎来越来越广阔的发展前景。可以看出，不论从理论还是实际应用来讲，研究TSP问题取得的每一步进展都将会有非常重大的意义。　　多年来人们一直寻求求解TSP问题的算法，其中有传统的算法如动态规划法、分支极限法等，但由于其仅能用于求解规模较小的TSP问题，在实际应用中的局限性使其无法适用于求解大规模的TSP问题。近年来，现代流行的智能算法也越来越受到研究人员们的广泛关注，当然人们也正在努力的探索，试图用其求解TSP问题。这些算法包括神经网络、遗传算法、蚁群算法等。本文欲用另外一种人工智能算法--人工

3、免疫算法,来求解TSP问题。中国硕士论文网提供大量免费硕士毕业论文,如有业务需求请咨询网站客服人员！　　1.旅行商问题的概述　　1.1旅行商问题的描述：　　旅行商问题，简单地说，就是某一旅行商要去n个城市去旅行，他要把这n个城市都逛一次而且不重复，最后回到原出发城市,问给定所有城市之间的旅行成本，哪一种旅行路径成本最小？为了简化，成本可理解为旅行商走过的最短距离。即已知n个城市以及各城市间的距离，某一旅行商从某个城市出发访问每个城市有且仅一次，最终返回原出发城市，怎样走才能使其所走的线路最短？　　用图论来描述，那就是已知带权图G=(C，L)，寻找出总权值最小的一条路径。其

4、中C={c1，c2，…，cn}表示n个城市的集合，L={lij

5、ci，cjC}是集合C中元素（城市）两两连接的集合，每条边lij，都存在与之对应的权值dij，实际应用中dij可以表示距离、费用、时间、油量等。　　从旅行商问题的描述来看，似乎其并不是很复杂，理解起来也是很简单，但其的确是一个非常复杂的问题。对于n个城市的旅行商问题，可供选择的路径数目我们可以这样计算：　　起始城市访问其他城市有n-1个选择，第二个城市有n-2个选择，依此类推，倒数第2个城市只有1个选择，总的可选择的路径数为?n?1?!?(n?1)(n?2)(n?3)...321。另外，我们所研究的标准的旅行

6、商问题其旅行成本是对称的，即城市i到城市j的旅行成本和城市j到城市i的旅行成本是一样的，故对于一个包含n个城市的旅行商问题，可供选择的路径有(n?1)!/2种。当n较小时，我们可通过罗列各种路径并从中找出最短路径，但随着值n的变大，可供选择的路径数迅速增加，用罗列的办法已经无能为力了，这时必须寻求其他解法来搜索最短的路径。　　1.2旅行商问题的数学建模：　　旅行商问题(TSP)在数学上可以描述为以下优化问题。　　2.人工免疫算法的基本原理2.1生物免疫系统及其运行机制生物免疫系统是自然界生物所必备的防御系统,它是一种由众多细胞、分子和组织等子系统构成的复杂系统，这些子系统

7、之间存在着复杂的相互联系，具有识别“自己”和“非己”，消除和消灭异物的功能。生物免疫系统又分为先天免疫系统和自适应免疫系统。先天免疫系统是一种与生俱来的天然防御系统，具有识别一定微生物并消灭这种微生物的能力，但对于绝大数外来侵入病毒的杀伤力较弱，这时候自适应免疫系统就开始发挥它的重要作用了，它能够自适应的学习外来侵入病毒物质或分子的模式结构，中立或消除该种物质。　　自适应免疫系统的运行机制可以简单的概括为：在抗原的激励下，巨噬细胞分化抗原为颗粒状物质，抗原呈递细胞将这些物质呈递到巨噬细胞的表面；通过识别的途径，被激活T细胞分化和分泌淋巴因子，并使B细胞应答；B细胞对来自激

8、活的T细胞的信号做出反应——被激活并进行分化和繁殖，分泌出抗体蛋白；抗体缠住、中立并毁灭这些抗原，其他多余的T细胞和B细胞变为记忆细胞。这样反复循环若干代数将最终产生能够消灭抗原的有效抗体。　　免疫系统中B细胞的功能主要是产生抗体,抗体由氨基酸排列组成,氨基酸的不同排列方式形成不同的抗体;而T细胞则主要实现免疫调节功能。　　2.2人工免疫系统及人工免疫算法的基本步骤　　人工免疫系统即根据生物免疫系统的运行机制构造的一种仿生系统。在构造人工免疫系统时,首先要构造的就是人工抗原和抗体,在人工免疫系统中,一个抗体或抗原可以用一个字符