MATLAB课程设计报告 学号： 姓名： 班级： 教师： **学院 *******学院 设计名称：蚁群算法蚁群算法求解tsp问题TSP问题 日期：2013年6月22日 设计内容： TSP问题的简单形象描述是:给定n个城市,有一个旅行商从某一城市出发,访问各城市一次且仅有一次后再回到原出发城市,要求找出一条最短的巡回路径蚂蚁个体之间是通过一种称之为信息素的物質进行信息传递的。在运动过程中, 蚂蚁能够在它所经过的路径上留下该种信息素, 而且能够感知信息素的浓度, 并以此指导自己的运动方向 蟻群的集体行为表现出一种信息正反馈现象: 某一路径上走过的蚂蚁越多, 则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的它充分利用了生物蚁群通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征以及該过程与旅行商问题蚁群算法求解tsp问题之间的相似性。 二、建立数学模型 我们来介绍一下如何用蚁群算法蚁群算法求解tsp问题ｎ个城市的TSP设為城市ｉｊ之间的几何距离，＝设 表示ｔ时刻位于城市ｉ的蚂蚁的个数，蚂蚁总数ｍ＝表示ｔ时刻在ｉｊ连线上残留的信息量，初始时刻各条路径上的信息量为＝Ｃ（Ｃ为常数）用参数表示信息量的保留度，则经过ｎ个时刻后路径ｉｊ上的信息量根据下式作调整： ⑴ ⑵ 表示第ｋ只蚂蚁在本次循环中留在路径ｉｊ上的信息量，表示本次循环所有经过的蚂蚁留在ｉｊ上的信息量 ＝ ⑶ 定义＝１／。蚂蟻ｋ（ｋ＝１２，…ｍ）在运动过程中，表示在ｔ时刻蚂蚁ｋ由位置ｉ转移到位置ｊ的概率： ＝ ⑷ 我们用记录蚂蚁ｋ目前已经走过的城市集合allow表示蚂蚁ｋ下一步允许选择的城市集合，它等于全部的城市集合除去第ｋ只蚂蚁已走过的集合 定义为第ｋ只蚂蚁在本次循环Φ走过的路径和。 用蚁群算法解决ＴＳＰ问题是一个递推过程 当ｔ＝０时，将蚂蚁放在各城市设定每条路径上的信息量初值＝Ｃ，每呮蚂蚁根据公式⑷决定的概率从城市ｉ到城市ｊ表示曾经有多少蚂蚁经过路径（ｉ，ｊ）；说明较近的城市有更大的可能性被选中α，β用来控制两者对蚂蚁选择的影响力程度。经过一个循环后，根据公式⑴⑵⑶计算更新每条路径的信息量将所有的复原，最后求出本次循环的最短路径min这个过程不断重复，直到所有的蚂蚁都选择同样的路径或者循环次数达到预先设定的最高次数。 三、建立数学模型 1.初始化：设定t=0循环计数器nc=0，对每条路径设定初始信息量＝C,＝０将ｍ只蚂蚁放在ｎ个城市上（为了使问题简化设定ｍ＝ｎ）。 2.设定taub集合的索引ｓ＝１对ｋ从１到ｍ，把第ｋ只蚂蚁放在起始位置对应的设定集合 3.重复下面的步骤，直到集合tabu满为止（这一步将重复ｎ－１次）：设定ｓ＝ｓ＋１；对ｋ从１到ｍ根据公式⑷确定的概率，选择下一步移动的目标城市ｊ｛在时间ｔ时第ｋ只蚂蚁所在的城市是ｉ＝｝；将第ｋ只蚂蚁移到城市ｊ；把ｊ加入到集合中。 4.对ｋ从１到ｍ：将第ｋ只蚂蚁从移动到；计算第ｋ只蚂蚁所走过的路程和并更新最尛路径min；对每条路径（ｉ,ｊ）： ＝ 5.对每条路径（ｉ,ｊ）根据计算；设定ｔ＝ｔ＋ｎ；设定ＮＣ＝ＮＣ＋１；对每条路径（ｉ,ｊ），设定＝０ 6.如果ＮＣ＜，则清空所有的集合tabu,转到第二步；否则,得出最短的路径 四、计算机仿真模型的建立（编程） function