多目标蚁群算法及其实现VIP专享VIP免费

多目标蚁群算法及其实现李首帅（2012101020019）指导老师：张勇【摘要】多目标优化问题对于现阶段来说，是十分热门的。本文将对多目标规划当中的旅行商问题，通过基于MATLAB的蚁群算法来解决，对多目标问题进行局部优化。【关键词】旅行商问题；蚁群算法；MATLAB一、背景介绍旅行商问题是物流领域当中的典型问题，它的求解十分重要。蚁群算法是受自然界中真实蚁群的集体行为的启发而提出的一种基于群体的模拟进化算法,属于随机搜索算法。M.Dorigo等人充分利用了蚁群搜索食物的过程与旅行商问题(TSP)之间的相似性,通过人工模拟蚁群搜索食物的行为(即蚂蚁个体之间通过间接通讯与相互协作最终找到从蚁穴到食物源的最短路径)来求解TSP问题。为区别于真实蚁群,称算法中的蚂蚁为“人工蚂蚁”。人们经过大量研究发现,蚂蚁个体之间是通过一种称之为信息素(pheromone)的物质进行信息传递,从而能相互协作,完成复杂的任务。蚁群之所以表现出复杂有序的行为,个体之间的信息交流与相互协作起着重要的作用。蚂蚁在运动过程中,能够在它所经过的路径上留下该种物质,而且能够感知这种物质的存在及其强度,并以此指导自己的运动方向。蚂蚁倾向于朝着该物质强度高的方向移动。因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。二、蚁群算法原理介绍1.蚁群在路径上释放信息素；2.碰到还没走过的路口，就随机挑选一条路走。同时释放与路径长度有关的信息素；3.信息素浓度与路长成反比；4.最优路径上的信息浓度越来越大；5.最终蚁群找到最优路径。其实自然界中，蚁群这种寻找路径的过程表现是一种正反馈的过程，与人工蚁群的优化算法很相近。所以我们简单功能的工作单元视为蚂蚁，则上述的搜寻路径过程可以用来解释人工蚁群搜寻过程。人工蚁群和自然界蚁群各具特点。人工蚁群具有一定的记忆能力。它能够记忆已经访问过的节点;另外,人工蚁群在选择下一条路径的时候并不是完全盲目的,而是按一定的算法规律有意识地寻找最短路径。而自然界蚁群不具有记忆的能力，它们的选路凭借外激素，或者道路的残留信息来选择，更多地体现正反馈的过程。人工蚁群和自然界蚁群的相似之处在于,两者优先选择的都是含“外激素”浓度较大的路径;两者的工作单元(蚂蚁)都是通过在其所经过的路径上留下一定信息的方法进行间接的信息传递。三、基于MATLAB的蚁群算法求解旅行商问题TSP问题描述如下：设有n个城市C=（1，2,...,n），任意两个城市i，j之间的距离为d，求一条经过每个城市的路径π=（π（1），π（2），...，π（n）），使得距离最小。第一步:初始化将m只蚂蚁随机放到n个城市，每只蚂蚁的禁忌表为蚂蚁当前所在城市，各边信息初始化为c。禁忌表体现了人工蚂蚁的记忆性，使得蚂蚁不会走重复道路，提高了效率。第二步：构造路径在t时刻，蚂蚁k从城市i转移到城市j的概率为：其中，Tabuk是保存了每只蚂蚁k已经到访过的城市集合，Jk={N-Tabuk}，α,β是系统参数，分别表示信息素、距离对蚂蚁的选择路径的影响程度。τ(i,j)表示边L(i,j)上的信息度强度。ji,表示由i到j的期望程度，一般为1/dij。α=0的时候，为最邻近城市选取概率最大。β=0的时候，蚂蚁完全只根据信息浓度确定路径。第三步：更新信息在所有蚂蚁找到一条合法的路径后对信息进行更新。mkijijijtttpt1,11否则若蚂蚁经过,0,,1,jiLQttkkij其中p为信息素的挥发速率，小于1的正数，可取0.5。ij表示蚂蚁在本次运行中留在路径L(i，j)上的信息速度。kij表示蚂蚁k放置在边上L(i，j)的信息速度。0,,,,,,pkkiJsJjsisijijijik如果Q表示蚂蚁所留轨迹为正常数(10,10000)。Lk表示第k只蚂蚁在本次周游中所走过的路径长度和。第四步：输出结果若迭代次数小于预定的迭代次数，且无退化行为（找到的都是相同的解）则转步骤二，否则输出目前的最优解。四、数据实验及结果通过计算机仿真，令参数为m=31,α=1,β=5,ρ=0.5,NC_max=200,Q=100,城市的数目为31。如图所示：五、结论本文设计了一种基于MATLAB实现的蚁群算法，用以求解组合优化难题中的典型代...