MBA论文：研究人工免疫算法中旅行商问题 由硕士毕业论文中心，硕士论文组整理提供，本文阐述了研究人工免疫算法中旅行商问题
0.引言
早在18世纪，爱尔兰的数学家哈密尔顿和英国的数学家托马斯就已经对旅行商问题（TSP）进行数学研究，而旅行商问题一般形式的研究则是由数学家卡尔·门格尔于19世纪三十年代在维也纳和哈佛大学首次进行研究的。对旅行商问题的研究往往是出于把它作为一个可应用于解决大规模的组合最优化问题的一般方法的一个平台，然而这并不是说在很多领域中旅行商问题找不到其具体的应用。事实上，旅行商问题有许许多多的应用，它可以看成是许多领域内复杂工程优化问题的抽象形式，诸如邮路问题、网络布线问题、物流配送问题、电路板钻孔问题等等，这些应用给旅行商问题的研究带来了活力，并且帮助指导今后的研究工作。旅行商问题本身的应用范围正在不断扩张，它的研究方法也正迎来越来越广阔的发展前景。可以看出，不论从理论还是实际应用来讲，研究TSP问题取得的每一步进展都将会有非常重大的意义。
多年来人们一直寻求求解TSP问题的算法，其中有传统的算法如动态规划法、分支极限法等，但由于其仅能用于求解规模较小的TSP问题，在实际应用中的局限性使其无法适用于求解大规模的TSP问题。近年来，现代流行的智能算法也越来越受到研究人员们的广泛关注，当然人们也正在努力的探索，试图用其求解TSP问题。这些算法包括神经网络、遗传算法、蚁群算法等。本文欲用另外一种人工智能算法--人工免疫算法,来求解TSP问题。中国硕士论文网提供大量免费硕士毕业论文,如有业务需求请咨询网站客服人员！
1.旅行商问题的概述
1.1 旅行商问题的描述：
旅行商问题，简单地说，就是某一旅行商要去n 个城市去旅行，他要把这n 个城市都逛一次而且不重复，最后回到原出发城市,问给定所有城市之间的旅行成本，哪一种旅行路径成本最小？为了简化，成本可理解为旅行商走过的最短距离。即已知n 个城市以及各城市间的距离，某一旅行商从某个城市出发访问每个城市有且仅一次，最终返回原出发城市，怎样走才能使其所走的线路最短？
用图论来描述，那就是已知带权图 G=(C，L)，寻找出总权值最小的一条路径。其中C={c1，c2，…，cn}表示n 个城市的集合，L={ lij | ci，cj∈C}是集合C 中元素（城市）两两连接的集合，每条边lij，都存在与之对应的权值dij，实际应用中dij 可以表示距离、费用、时间、油量等。
从旅行商问题的描述来看，似乎其并不是很复杂，理解起来也是很简单，但其的确是一个非常复杂的问题。对于n 个城市的旅行商问题，可供选择的路径数目我们可以这样计算：
起始城市访问其他城市有n-1 个选择，第二个城市有n-2 个选择，依此类推，倒数第2 个城市只有1 个选择，总的可选择的路径数为?n ?1?! ? (n ?1)(n ? 2)(n ? 3). . . 3 2 1。另外，我们所研究的标准的旅行商问题其旅行成本是对称的，即城市i 到城市j 的旅行成本和城市j 到城市i 的旅行成本是一样的，故对于一个包含n 个城市的旅行商问题，可供选择的路径有(n ?1)!/ 2种。当n 较小时，我们可通过罗列各种路径并从中找出最短路径，但随着值n的变大，可供选择的路径数迅速增加，用罗列的办法已经无能为力了，这时必须寻求其他解法来搜索最短的路径。
1.2 旅行商问题的数学建模：
旅行商问题( TSP)在数学上可以描述为以下优化问题。
2.人工免疫算法的基本原理2.1 生物免疫系统及其运行机制生物免疫系统是自然界生物所必备的防御系统, 它是一种由众多细胞、分子和组织等子系统构成的复杂系统，这些子系统之间存在着复杂的相互联系，具有识别“自己”和“非己”，消除和消灭异物的功能。生物免疫系统又分为先天免疫系统和自适应免疫系统。先天免疫系统是一种与生俱来的天然防御系统，具有识别一定微生物并消灭这种微生物的能力，但对于绝大数外来侵入病毒的杀伤力较弱，这时候自适应免疫系统就开始发挥它的重要作用了，它能够自适应的学习外来侵入病毒物质或分子的模式结构，中立或消除该种物质。
MBA论文：研究人工免疫算法中旅行商问题 由博士论文网，论文中心为您整理提供信息资讯。