改进型蚁群算法及其在TSP中的应用

蚁群算法求解tsp问题

维普资讯 doc.guandang.net

第4 1卷第 2期 20 0 5年 4月

兰州大学学报 (自然科学版 ) J u n lo a z o nvri N tr c ne) o r a fL n h u U ie t s y( aua Si cs l e — —

V 14 0 l. 1NO .

2

A r 2 0 p. 0 5

文章编号: 4 52 5 (0 50 .0 80 0 5_0 92 0 )20 7-3

改进型蚁群算法及其在 TS中的应用 P 田富鹏 (西北民族大学现代教育技术学院,甘肃兰州 70 3 1 300 摘要:绍了蚁群算法的基本原理,对其优,点作了详细的分析 .于蚁群算法的缺点——需要介并缺基

较长的计算时间,收敛速度慢,出了一种改进型的蚁群算法,以有效提高收敛速度,把该算法应提可并 用到 TS P问题中,得了很好的效果 .取

关键词:群算法; S;息素蚁 T P信 中图分类号: TP1 1 8文献标识码: A

现今,计算机科学技术迅猛发展并深人人们与其他各学科相互交叉和渗透 . 0纪 8年代以 2世 0

下面用一个例子来说明 ( r o的基本蚁群 Doi ) g

的生活,中一个很大的特点就是计算机科学正算法原理【 .其 1 J设 A是蚂蚁的巢穴,E是食物源,HC为一障来,些新颖的优化算法,一如遗传算法,工神经碍物 .现今蚂蚁要从 A到 E人,由于中间有障碍

网络,模拟退火,忌搜索,化规划等,禁进都是科学物 HC,可知道蚂蚁有 A—H—E或 A— C E—,同理 家们通过细致的观察与研究后模拟某些自然现象可知从 E到 A存在相似的情况.图 1说明了路线 a 或过程而得到了发展,为解决复杂问题提出了新关系,中 A到 B等于 E到 D, H=DH=1单位,其 B个

的思路和手段 .蚁群算法 ( t oo yag r h又 An ln loi m) c t称为人工蚁群算法也是其中一种优秀的智能优化算法,原理主要来源于蚁群活动 .所周知蚂蚁其众是一种群居性昆虫,个体甚微,为群体却表现它作 出十分独特的生物特征和生命行为 . 0纪 9年 2世 0 H H H

C

代初期,意大利学者 Doio等从生物进化和仿生 r g学角度出发,究蚂蚁寻找路径的自然行为,出研提 了蚁群算法,用该方法解 TS并 P问题,二次分配问 () a () b ( C )

题和作业调度等问题,得了较好结果 .群算法取蚁是一种模拟进化算法,应用到计算机领域,行从进

图 1基本蚁群系统示意图 Fi.1 Th sca tc ln y t m g e ba i n oo y s se

组合优化问题的求解已经取得了显著的成果.它 C=DC=05单位 .初始情况

下假设每个单位时 .个是继模拟退火算法,传算法,工神经网络算 B遗人间内有 3蚂蚁分别从 A到达 B,同时有 3只蚂 0只 0法,禁忌搜索算法等启发式搜索算法用于求解复杂组合优化问题的又一选择. 蚁从 E到 D,蚁过后留下的信息素为 1设信息蚂,素保留时间为 1位.它们分别到达 B,单 D点后,由于路径 BH, C, B DC, H上都没有信息素,此对 D在

1蚁群算法的基本原理

所 b经过一个蚁群算法是对真实蚁群行为进行研究而提出于路径的选取是等值的,以有了图 1 . 又 0这的 .生学家经过大量观察研究发现,个蚂蚁的单位后,各有 3只蚂蚁到达 B和 D,时同样面仿单行为能力相当有限,由大量蚂蚁组成的蚁群却而蚂蚁个体之间是通过一种叫信息素的物质进行信对着路径的选取,由于路径 BH, C, B DC, DH上已即 H, DC, DH上留有信具有非凡的能力 .经过科学家们细致的研究,现经有蚂蚁通过,路径 B BC,发

息素,根据信息素多少进行等比例选取,得图 1.可 c 各息传递,到一种正反馈作用,起能很好的协调蚁群随着时间的推移,路径上的信息素会越来越不相等,以选取路径时的概率也就产生了偏差,所最活动 . 收稿日期:2 0 -3 0 . 0 5 0 - 8

作者简介:田富鹏 09 3)男,教授 . 6 -,副