基于MATLAB的改进型基本蚁群算法

《基于MATLAB的改进型基本蚁群算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、维普资讯http://www.cqvip.com第24卷第3期太原重型机械学院学报V01．24№32003年9月JOURNALOFTAIYUANHEAVYMACHINERYINSTrIrLJTESep．2003文章编号：1000—159X(2003)O3—0201—04基于MATLAB的改进型基本蚁群算法李虹，孙志毅(太原重型机械学院，太原030024)摘要：蚁群算法是一种新型的模拟进化算法。是继GA、SA、TS等算法之后求解组合优化问题的一种新思路。人工蚁群算法通过模拟蚁群搜索食物的行为，采用正反馈结构、分布式计算与某种启发式算

2、子相结合的方法，能够很快地发现较好解。本文给出一种基于MATLAB的改进型基本蚁群算法。有效地降低了算法的复杂度，缩短了搜索时间，具有较强发现最好解的能力。·关键词：蚁群算法；改进中图分类号：TP301．6文献标识码：A径的?生物学家经过长期大量细致的观察研究后0引言发现：最初单个蚂蚁的行为是随机的。蚂蚁在运动过程中会在其经过的路径上留下一种叫做外激素蚁群算法(AntColonyAlgorithm)是最近几年才(Pheromone)的信息物质。蚂蚁个体之间的信息传由意大利学者M．Dorigo，V．Manierio，A．Collom

3、i等递就是依靠这种物质进行的。一方面，每只蚂蚁在人提出的一种新型的模拟进化算法。受到人们对其走过的线路上留下一定量的信息物质，且留在路自然界中真实蚁群集体行为研究成果的启发，考虑径上的信息物质随时间逐渐衰减。另一方面，后来到蚁群搜索食物的过程与旅行商问题的相似性，利的蚂蚁能够感知这种外激素并以路径上残留信息用蚁群算法求解旅行商问题(TravelingSalesman量的多少指导其行为，信息量越大的路径，被选中Problem)、指派问题(AssignmentProblem)和调度问的概率也越大。显然，蚁群搜索食物源的过程是信题(Sc

4、hedulingProblem)，取得了一些比较满意的实息量的一个正反馈过程。据此，蚁群可以快速地找验结果。蚁群算法是一种适应性好、鲁棒性强。具到由巢穴到食物源的最佳路径。图l所示为真实蚁有正反馈结构的并行算法。群系统搜索食物时的路线示意图。图中A是蚁巢，1蚁群系统基本原理E是食物所在的位置，HC为障碍物。设D和。和之间的距离均为2个单位，D自然界中像蚂蚁这样几乎没有视力的昆虫有与c、与c之间的距离为1个单位，在一个时间单很多，他们是如何找到由其巢穴到食物源之最短路元内有3O只蚂蚁由A到达点，同样有3O只蚂蚁由收稿日期：2003—

5、03—12作者篱介：李虹(1965一)，女，电子信息分院副教授，研究方向为控制理论及其应用。维普资讯http://www.cqvip.com太原重型机械学院学报2003年n)表示城市和城市之间的距离，下(t)表示t时刻残留在城市√连线上的信息量。初始时刻t=0，各条路径上有少量的信息r(0)即。根据各条路径上信息量的多少，t时刻位于某一城市的蚂蚁k(k=1，2，k，m)一次只能选择其中一个目标城市，n次后回到起点。完成一次循环，按下面的公式修改各条路径上的信息量：丁(t+n)=Ip丁(t)+△丁(1)r△r={lLk本次循环中蚂蚁

6、k经过连接城市和0_『的路径(2)圈l蚁群搜索食物路线示意圈式中0

7、蚂蚁k在t时刻由位置转移至位率是相同的，按照统计规律，即有l5只蚂蚁选择置_『时的概率为：DIt(BH)，另外l5只选择路径(Be)。由于d舢=dBH=2dDc=2dec，所以经过1个单位时间后，走过路径．[卢一。Po㈤：=J{．—三∈a··。wedBC和DC的蚂蚁个数是走过BH、DH蚂蚁个数的两。【0倍。这些蚂蚁留在路径上的信息量前者也是后者的2倍。在t=1时，新的30只蚂蚁位于点和D点，根(3)据信息量的多少，他们选择路径pc(Bc)的概率是启发因子71=1／d，是两个可以调整的参选择on(日)的两倍，即有20只蚂蚁选择前者，

8、而数，其值决定了信息量和启发因子在蚂蚁选择路径只有lO只选择后者。这一过程一直继续下去，最终时所起作用的强弱程度。P(￡)是蚂蚁在t时刻选择所有的蚂蚁都将选择由蚁穴至食物源的最短路径。转移路径的依据。2人工蚁群系统数学模型3基于MATLAB的改进型