《多目标蚁群算法及其实现》由会员分享，可在线阅读，更多相关《多目标蚁群算法及其实现（5页珍藏版）》请在装配图网上搜索。
1、多目标蚁群算法及其实现李首帅(指导老师：张勇【摘要】多目标优化问题对于现阶段来说，是十分热门的。本文将对多目标规划当中的旅 行商问题，通过基于MATLAB的蚁群算法来解决，对多目标问题进行局部优化。【关键词】旅行商问题；蚁群算法；MATLAB一、背景介绍旅行商问题是物流领域当中的典型问题，它的求解十分重要。蚁群算法是受自然界中真 实蚁群的集体行为的启发而提出的一种基于群体的模拟进化算法，属于随机搜索算法。M. Dorigo等人充分利用了蚁群搜索食物的过程与旅行商问题(TSP)之间的相似性，通过人工模 拟蚁群搜索食物的行为(即蚂蚁个体之间通过间接通讯与相互协作最终找到从蚁穴到食物 源的最短路径)
2、来求解TSP问题。为区别于真实蚁群,称算法中的蚂蚁为“人工蚂蚁”。人们 经过大量研究发现,蚂蚁个体之间是通过一种称之为信息素(pheromone)的物质进行信息传 递，从而能相互协作，完成复杂的任务。蚁群之所以表现出复杂有序的行为，个体之间的信息 交流与相互协作起着重要的作用。蚂蚁在运动过程中，能够在它所经过的路径上留下该种物 质，而且能够感知这种物质的存在及其强度，并以此指导自己的运动方向。蚂蚁倾向于朝着该 物质强度高的方向移动。因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈 现象:某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通 过这种信息的交流达到
3、搜索食物的目的。二、蚁群算法原理介绍1.蚁群在路径上释放信息素；2碰到还没走过的路口，就随机挑选一条路走。同时释放与路径长度有关的信息素；3. 信息素浓度与路长成反比；4. 最优路径上的信息浓度越来越大；5. 最终蚁群找到最优路径。其实自然界中，蚁群这种寻找路径的过程表现是一种正反馈的过程，与人工蚁群的优化 算法很相近。所以我们简单功能的工作单元视为蚂蚁，则上述的搜寻路径过程可以用来解释 人工蚁群搜寻过程。人工蚁群和自然界蚁群各具特点。人工蚁群具有一定的记忆能力。它能够记忆已经访问 过的节点;另外,人工蚁群在选择下一条路径的时候并不是完全盲目的,而是按一定的算法规 律有意识地寻找最短路径。而自
4、然界蚁群不具有记忆的能力，它们的选路凭借外激素，或者道路的残留信息来选择，更多地体现正反馈的过程。人工蚁群和自然界蚁群的相似之处在于, 两者优先选择的都是含“外激素”浓度较大的路径；两者的工作单元（蚂蚁）都是通过在其所 经过的路径上留下一定信息的方法进行间接的信息传递。三、基于MATLAB的蚁群算法求解旅行商问题TSP问题描述如下：设有n个城市C=（1, 2,.,n），任意两个城市i，j之间的距离为d,求一条经过每 个城市的路径n =（n （1），n （2），.，n （n），使得距离最小。第一步:初始化将m只蚂蚁随机放到n个城市，每只蚂蚁的禁忌表为蚂蚁当前所在城市，各边信息初始 化为c。禁忌表
5、体现了人工蚂蚁的记忆性，使得蚂蚁不会走重复道路，提高了效率。第二步：构造路径在t时刻，蚂蚁k从城市i转移到城市j的概率为:如果j e Jr其中，Tab u是保存了每只蚂蚁k已经到访过的城市集合，J=N-Tabu,kkka，B是系统参数，分别表示信息素、距离对蚂蚁的选择路径的影响程度。T （i,）表示边L（i,j） 上的信息度强度。9 cj）表示由i到j的期望程度，一般为1/d。ija =0的时候，为最邻近城市选取概率最大。B =0的时候，蚂蚁完全只根据信息浓度确定路径。第三步：更新信息在所有蚂蚁找到一条合法的路径后对信息进行更新。t （t +1）=（1 - p丄 C）+Y At k （t, t
6、 +1）ijijijmAt kijQ,若蚂蚁经过C j） k o,否则其中p为信息素的挥发速率，小于1的正数，可取0.5。Atj表示蚂蚁在本次运行中留在路径L（i，j）上的信息速度。At kij表示蚂蚁k放置在边上L（i，j）的信息速度。Q表示蚂蚁所留轨迹为正常数(10,10000)。Lk表示第k只蚂蚁在本次周游中所走过的路径长度和。第四步：输出结果若迭代次数小于预定的迭代次数，且无退化行为(找到的都是相同的解)则转步骤二, 否则输出目前的最优解。四、数据实验及结果通过计算机仿真，令参数为m=31, a =1, p =5, p =0.5,NC_max=200,Q=100,城市的数目为31。如图
7、所示:五、结论本文设计了一种基于MATLAB实现的蚁群算法，用以求解组合优化难题中的典型代表旅 行商问题。对31个城市旅行商问题进行了测试，所得结果能达到优化作用，实现了本文的 研究目标。可以发现蚁群算法的优点：不依赖于所求问题的具体数学表达式描述，具有很强的找到 全局最优解的优化能力，正反馈、较强的鲁棒性、全局性、普遍性，优良的分布式并行计算 机制，易于与其他方法相结合。缺点：模型普适性不强，不能直接应用于实际优化问题，局 部搜索能力较弱，易出现停滞和局部收敛、收敛速度慢等问题，长时间花费在解的构造上， 导致搜索时间过长，算法最先基于离散问题，不能直接解决连续优化问题。由于蚁群算法对图的对称性以及目标函数无特殊要求，因此可以解决各种对称、非对称 问题，线性、非线性问题。参考文献1 黄友锐，智能优化算法及其应用（不要加书名号），国防工业出版社，20082 雷德明，严新平，多目标智能优化算法及其应用，科学出版社，2009
多目标蚁群算法及其实现
