当前位置:首页 >> 机械/仪表 >>

基于MATLAB的蚁群算法仿真研究


《装备制造技术》 2008 年第 11 期

基于 MATLAB 的蚁群算法仿真研究
野莹莹 1 , 付丽君 1, 程立英 2
(1.沈阳理工大学信息科学与工程学院, 辽宁 沈阳 110168; 沈阳师范大学物理科学与技术学院, 2. 辽宁 沈阳 110034 )
摘要: 介绍了基于 MATLAB 的蚁群算法仿真研究,对佛罗里达州

六城市旅行商问题进行了 MATLAB 仿真, 计算结果显示, 作为新型 进化算法, 蚁群算法能够解决复杂组合优化问题。 关键词: 蚁群算法; MATLAB; 模拟进化算法; 优化 中图分类号: 18 TP 文献标识码:A 文章编号: 1672- 545X (2008) 0013- 02 11-

蚁群算法 (Ant Colony Algorithm 是一种新型模拟进化算 ) 意大利学者多戈里等人从生物进化 法。20 世纪 90 年代初期, 和仿生学的角度出发, 研究蚂蚁寻找路径的自然行为, 提出蚁 群算法[1]。目前, 蚁群算法已经成为国际智能计算领域关注的 热点和前沿课题。 MATLAB 是 Mathworks 公司 1984 年推出的数学软件, 其 名称是由矩阵实验室 (Matrix Laboratory 所合成, ) 因此可知, 其 最早的理念是提供一套完善的矩阵运算指令,可随着数值运 算需求的转变, MATLAB 已经成为各种系统模拟和讯号处理 等方面的标准语言[5]。

2

蚁群算法的系统模型
下面以解决旅行商问题 (TSP 来建立系统模型。 ) 旅行商问

题是要求旅行商在个相互连通的城市中,寻找出一条连接所 有城市的最短通路的问题[4]。 作为组合优化领域里典型的易于 TSP 描述却难以处理的 NP 完全难题, 问题可能的路径数目与 城市数目是呈指数型增长的, 求解非常困难。 求解个 n 城市的对称旅行商问题的实现过程如下。假设 有 m 只蚂蚁, 将它们随机放入到 n 个城市当中。 i (t)表示t时刻 b
n

位于城市 i 的蚂蚁个数, 那么 m=Σ bi (t)。城市 i 和城市 j 之间
i=1

1

蚁群算法原理
蚁群算法是受对真实蚁群行为研究的启发而提出的。蚂

的距离为 d(i, 2, …,) t 时刻在 ij 连线上残留的信息 j=1, 3, n , ij 量为 τij (t)。 在初始时刻, τij (t) = C 为常数 , 设 (C ) 在各条路径上 信息量相等。蚂蚁 k 在运动过程中,根据各条路径上的信息量 决定转移方向。pij (t)表示在时刻蚂蚁由位置 i 转移到位置 j 的 概率:
∈ α β ∈ ∈ ij ij ∈ ∈ ∈ ∈ ∈ ∈k∈allowedk ∈ ∈ ∈ ∈

蚁这种群居动物, 虽然个体的行为简单, 但群体的行为却极其 复杂。 人们经过大量的研究, 得出蚂蚁个体之间通过一种称为 外激素的物质进行信息传递。蚂蚁在移动过程中会分泌外激 素, 并且通过感知这种物质的存在及其强度, 指导自己的移动 蚂蚁朝着外激素强度高的方向移动。也就 方向。一般情况下, 是说, 如果某一路径上走过的蚂蚁越多, 留在这条路径上的外 激素强度越大, 那么蚂蚁选择该路径的概率也就越大。 这是一 种信息正反馈现象。蚂蚁之间就是通过这样的方式进行信息 交换, 以便快速地搜寻到食物 。
[2]

k

τ η (t) τij ηij (t)
α β

pij (t)=

k

Σ

, j∈allowedk 其他

(1 )

0,

其中 η ij 表示由城市 i 转移到城市 j 的期望程度, 一般取 ηij (t)= 1 。α , β 分别表示蚂蚁在运动过程中所积累的信息及 dij 启发式因子, 在蚂蚁路径选择中所起到的不同作用。 与真实蚂 蚁蚁群不同, 人工蚁群具有一定的记忆功能, tabu k (k∈1,2, 用 …,m)来记录蚂蚁 k 目前已经走过的城市。 随着时间的推移, 以 前留下的信息逐渐消逝, 用参数(1- p)表示信息消逝的程度, 经过 N 个时刻, 蚂蚁完成一个循环。 各个路径上的信息量要根 据下式作调整: τij (t+n)= ρ τij (t)+△τij (t+N) · (2 )

β

使用蚁群算法求解现实问题时,首先生成一定数量的人 工蚂蚁蚁群, 并为每一只人工蚂蚁建立一个解或解的一部分。 每只人工蚂蚁从问题的初始状态出发, “外激素” 根据 的浓度, 选择下一个要转移到的状态, 直到建立起一个解。 每只蚂蚁根 据所找到的解的好坏程度,在所经过的状态上释放与解的质 量成正比的 “外激素” 之后, 。 每只人工蚂蚁又重新开始新一轮 的求解过程, 直到预先确定的寻找过程结束, 或者已经寻找到 陷入局部最优, 可以 满意解。为了避免寻找过程过早的停滞, “外激素” 更新机制[3]。 引入

收稿日期: 2008- 08- 21 基金项目: 沈阳理工大学青年教师科研启动专项基金资助项目 作者简介: 野莹莹 (1977— , 辽宁朝阳人, ) 女, 讲师, 硕士, 研究方向: 智能自动化及应用; 付丽君 (1961— , 辽宁沈阳人, ) 女, 副教授, 硕士, 研究方 向: 智能自动化及应用; 程立英 (1976— 女, ) 河北衡水人, 助教, 硕士, 主要研究方向: 计算机图形学、 图像处理, 计算机仿真。

13

Equipment Manufactring Technology No.11 ,2008 其中 ρ 表示信息素的保留率, (1- ρ 表示信息素的挥发 则 )
m k=1

114 140 229 0

251 84 273

率。△τij =Σ △τij , 其中△τij 表示第 k 只蚂蚁在本次循环中留 △τ 在路径上 i j 的信息量, ij 表示本次循环中留在路径上 i j 的信息量。 根据信息素更新策略的不同,多戈里给出了三种不同模 型, 分别称为 ant- quantity 模型、 cycle 模型和 ant- density 模 ant试验证明求解 TSP 问题时, cycle 模型性能比前两种模 ant型。 型好。ant- cycle 模型为: △τij =
k

k

k

148 163 468 251 0 number_of_ants =20 ;%蚂蚁数 MaxIterations =100 ; % 迭代次数 alpha =1 ; %值 beta = 9 ; %值 rho = 0.9 ; %值

129 194 250 84 273 0 ]; % 城市之间的距离矩阵

target_length =3 ; % 路径长度最小值 (3 ) ACSTSP (distances_matrix,number_of_ants, MaxIterations, alpha, beta, rho, target_length); %函数文件 经过多次运行得到的结果中, 以从 Gainesville 出发得到的 仿真结果为最终解。 其他运算结果只是出发城市不同, 其他结 果均与以下最佳路径和最佳长度相同。 BestTourLength =1059 %最佳路径长度 BestTour = 1 5 2 4 3 6 1 %最佳路径 从仿真结果来看, 利用蚁群算法求的结果与实际相符合。 需要注意的是参数设置在仿真试验中至关重要,不过只能通 过实验的方法得到, 没有确切的理论作为基础。

!

Q筑L ,如果蚂蚁 k 经过 ij 0,如果蚂蚁 k 在巡回中不经过 ij

K

算法的具体步骤如下: △τ 步骤 1 初始化。设置初始时间 t=0、最大迭代次数、 ij (0 =0、τij ) ) (0 =C。将 m 只蚂蚁随机放入 n 个城市当中。 步骤 2 设置循环。 步骤 3 蚂蚁以概率 pij (t)选择城市, 下一个城市 j。 步骤 4 移动蚂蚁到下个城市 j, 并保存城市 j, 更新 tabuk。 步骤 5 若遍历完 m 只蚂蚁, 则转到第 6 步, 否则转到步骤 3。 步骤 6 更新每条路径上的信息量。 步骤 7 若达到最大迭代次数则循环结束, 输出结果, 否则 转到步骤 2。
k

4

结束语
蚁群算法作为新型的进化算法,有着广泛的应用前景。

MATLAB 是一种强大的计算工具软件,利用其进行仿真研究

3

仿真实验

是众多仿真手段之一。仿真实验结果表明蚁群算法是一种求 解组合优化问题的有效算法。 蚁群算法研究的时间不长, 不像 其他算法那样已经形成系统的分析方法和具有坚实的数学基 础。在理论和实践方面还有许多问题需要深入的研究。
参考文献: [1] Dorigo M,Caro G D,Gambardella L M. Ant Algorithms for Discrete Opt imization[J]. Artificial Life,1999,5(2):137- 172. [2] 蔡自兴,徐光祐.人工智能及应用 [M]. 北京: 清华大学出版社,2004. [3] 张纪会,高齐圣, 徐心和.自适应蚁群算法 [J]. 控制理论与应用 , 2000,(2):1- 3. [4] 陈志平, 徐宗本.计算机数学[M]. 北京:科学出版社,2001. [5] 薛定宇, 阳 泉. 基于 MATLAB/Smiulink 的系统仿真技术与应用[M]. 北京: 清华大学出版社,2002.

3.1 实验条件 利用 MATLAB 7.0 作为仿真软件。考察佛罗里达州的 6 个 城 市 Gainesville、 Jacksonville、 Miami、 Orlando、 Tallahassee 和 Tampa 的旅行商问题。Gainesville、 Jacksonville、 Miami、 Orlando、 Tallahassee 和 Tampa 分别代表 1~6 号城市。 参数设置为 α=1、β=9、 ρ=0.9 蚂蚁数目为 20。试验结 束条件为迭代次数达到 100 次。 3.2 实验结果 主程序如下所示: distances_matrix = [ 0 73 73 0 333 114 148 129 348 140 163 194 0 229 468 250

333 348

Simulation of Ant Colony Algorithm Based on MATLAB
YE Ying-ying1 , FU Li-jun2, CHENG Li-ying3 (1. School of Information Science and Engineering, Sheyang Ligong University, Shenyang 110168,China; 2. College of Physics Science and Technology, Shenyang Normal University, Shenyang 110034, China) Abstract: The simulation of ant colony algorithm based on MATLAB is introduced. The simulation for six cities of Florida is based on MATLAB. The results show that ant colony algorithm can solve complex combinatorial optimization problem as novel simulated evolutionary algorithm. Keywords: Ant colony algorithm; MATLAB; Simulated evolutionary algorithm; Optimization

14


相关文章:
基于MATLAB的蚁群算法解决旅行商问题 (附带源程序、仿真)
基于MATLAB的蚁群算法解决旅行商问题 (附带源程序、仿真)_信息与通信_工程科技_专业资料。附带源程序 绝对好使!摘要:旅行商问题的传统求解方法是遗传算法,但此算法...
蚁群算法仿真
基于蚁群算法的改进及其... 3页 7下载券 蚁群算法原理的仿真研究 4页 免费 ...蚁群算法采用 matlab 开发的仿真平台:算法实现,路径显示,人机交互控制等 希望对...
基于MATLAB的蚁群算法实验研究程序的应用
单位:五邑大学和陕西国威消防工程有限公司 整理收集作者:崔卫国 学历:硕士研究基于 MATLAB 的蚁群算法实验研究程序的应用 %蚁周模型,解决 TSP 问题 function AS(...
matlab蚁群算法精讲及仿真图
蚁群算法 matlab 精讲及仿真 4.1 基本蚁群算法 4.1.1 基本蚁群算法的原理 蚁群...【基于蚁群算法和遗传 算法的 机器人路径规划研究】 该算法的特点: (1)自我...
基于蚁群算法的TSP问题研究 开题报告
基于蚁群算法的TSP问题研究 开题报告_计算机软件及应用_IT/计算机_专业资料。四川...和实现步骤, 并在 MATLAB 环境中进行仿真,分析蚁群算法中各关键参数对算法性能...
蚁群算法的数学模型
蚁群算法的数学模型_数学_自然科学_专业资料。蚁群算法的数学模型蚂蚁 k(k ? 1,2 ? ??, m) 在运动过程中,运动转移的方向由各条路径上 的信息量浓度决定。...
蚁群优化算法及编程实现
26 蚁群优化算法及编程实现摘要蚁群优化算法是人工智能研究领域中一个非常重要重要...对蚁群优化算法进行 Matlab 编程实现,并且选取不同参数进行仿真结果测试,验证参数...
基于蚁群优化的自组网路由算法的研究与仿真
基于蚁群算法的可信网络路... 5页 2财富值 蚁群算法matlab源码 6页 免费 ...仿真结果表明所提出的基于蚂 蚁算法的移动自组网路由算法具有良好的性能,大大...
多目标蚁群算法及其实现
本文将对多目标规划当中的旅行商问题,通过基于 MATLAB 的蚁群算法来解决,对多...四、数据实验及结果通过计算机仿真, 令参数为 m=31,α =1,β =5,ρ =0....
蚁群算法MATLAB程序实例整理
蚁群算法MATLAB程序实例整理_信息与通信_工程科技_专业资料 暂无评价|0人阅读|0次下载|举报文档蚁群算法MATLAB程序实例整理_信息与通信_工程科技_专业资料。function ...
更多相关标签:
蚁群算法matlab程序 | matlab蚁群算法工具箱 | 蚁群算法 matlab | 蚁群算法matlab代码 | 蚁群算法matlab实例 | 蚁群优化算法 matlab | 蚁群算法 tsp matlab | 蚁群算法 vrp matlab |