计算智能课程设计

《计算智能课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算智能课程设计计算智能课程设计TSP的人工智能求解班级：信息与计算科学082姓名：杨佳佳学号：2008062046完成日期：2011年11月1日第13页共13页计算智能课程设计目录TSP的人工智能求解3摘要3一、问题提出3二、问题分析3三、模型建立41、求解TSP问题的人工蚂蚁行为规则42、蚂蚁算法求解TSP问题蚂蚁行为量化43、蚂蚁算法求解TSP问题的算法描述54、蚂蚁算法求解TSP问题的参数选择6四、模型求解及结果分析71考察参数，，对结果的影响(表1)72考察参数C对结果的影响(表2)73、考察参数Q对结果的影响(表3)84、考察参数M对结果的影响(表4)9五、MATLAB代码

2、9参考文献:12第13页共13页计算智能课程设计TSP的人工智能求解摘要:TSP问题（TravellingSalesmanProblem）,即旅行商问题是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路劲的选择目标是要求的路径路程为所有路径的最小值。在此次课题中，我们采用蚁群算法（antcolonyoptimization,ACO），它是一种用来在图中寻找优化路径的机率型技术，由MarcoDorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物的过程中发现路径的行为。通过

3、实验应用蚂蚁算法TSPLIB中城市数为29的bays29．tsp问题进行求解数据来源于标准的TSP数据库，通过选择不同的参数，并经程序计算，最后选取效果最优的一组参数。关键词：TSP问题蚁群算法一、问题提出有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路劲的选择目标是要求的路径路程为所有路径的最小值。第13页共13页计算智能课程设计二、问题分析如果利用排列组合的方法把所有的路径都计算出来，并逐一比较，选出最小的路径。虽然该方法在理论上是可行的，但路径的个数成指数增长，当城市个数较大时，该方法的求解时间是很长的，甚至

4、不可能完成。以每秒1亿次的计算速度来估算，如果TSP问题包含20个城市，求解时间长达350年；如果要处理30个城市，则求解时间更长达1+10e16年。如此长的时间，在实际中完成是难以想象的。基于以上分析，我们采取蚁群算法可以大大提高计算效率。三、模型建立1、求解TSP问题的人工蚂蚁行为规则应用蚂蚁的行为特性求解TSP问题时，每只人工蚂蚁的行为还必须符合下列规律：(1)根据路径上的信息素浓度，以某种概率来选取下一步的路径。(2)不再选取自己本次循环已经走过的路径作为下一步的路径(可以通过一个数据结构来控制这一点)。(3)当完成一次循环后，根据整个路径长度来释放相应浓度的信息素，并更新走过

5、路径上的信息素浓度。2、蚂蚁算法求解TSP问题蚂蚁行为量化用蚂蚁算法求解TSP问题时需要解决三个问题:(1)信息素浓度如何刻画;(2)信息素浓度如何调整;(3)蚂蚁的选择策略如何确定。而且这三个问题都必须予以量化，并且在量化的过程中必须和所优化的目标以及已知条件建立某种联系。为此，引入变量，△，△，，其中1≤i，j≤n，1≤k≤m，n表示TSP问题的规模，即城市数，而m则表示人工蚂蚁的个数。表示在t时刻边(i，j)上的信息素浓度。当蚂蚁完成一次循环后，相应边上的信息素浓度为，第13页共13页计算智能课程设计即等于上一时间段残留下的信息素浓度加上当前时间段新增加的信息素浓度其中为一个取值

6、范围在0到1之间的常数，显然，1-表示在时间段t到t+1之间信息素浓度的挥发强度因子，，其中△是第k只蚂蚁在时间t到t+1之间，在边(i，j)上增加的信息素浓度。对于M.Dorigo提出的△的三种计算模型ant-cyclesystem、ant-quantitysystem和ant-densitysystem，后两种模型中利用的是局部信息，而前者利用的是全局信息，经过实验对比，在求解TSP问题时ant-cyclesys-tem性能较好，因而本文采用它作为基本模型:△其中Q是一个常量，用来表示蚂蚁完成一次完整的路径搜索后，所释放的信息素总量，Lk表示第k只蚂蚁的路径总费用，它等于第k只蚂蚁

7、经过的各段路径所需费用的总和。显然，蚂蚁不会在其没有经历过的路径上释放信息素。定义第k只蚂蚁当前时刻在顶点，下一步选择顶点，即选择路径（i,j）的概率为:其中，为路径(i，j)所需费用，，为两个参数，分别用来控制信息素浓度和路径长度的相对重要程数，分别用来控制信息素浓度和路径长度的相对重要程度，是第k只蚂蚁在满足人工蚂蚁行为规律3个条件的前提下，下一步可以选择的路径集合。3、蚂蚁算法求解TSP问题的算法描述根据上面的分析，再引入一个控制“蚂蚁不