蚁群算法.doc

蚁群算法
目录
1 蚁群算法基本思想 1
蚁群算法简介 1
蚁群行为分析 1
蚁群算法解决优化问题的基本思想 2
蚁群算法的特点 2
2 蚁群算法解决TSP问题 3
关于TSP 3
蚁群算法解决TSP问题基本原理 3
蚁群算法解决TSP问题基本步骤 5
3 案例 6
问题描述 6
解题思路及步骤 6
MATLB程序实现 7
清空环境 7
导入数据 7
计算城市间相互距离 7
初始化参数 7
迭代寻找最佳路径 7
结果显示 7
绘图 7
1 蚁群算法基本思想
蚁群算法简介
蚁群算法(ant colony algrothrim,ACA)是由意大利学者多里戈(Dorigo M)、马聂佐( Maniezzo V )等人于20世纪90初从生物进化的机制中受到启发,通过模拟自然界蚂蚁搜索路径的行为,提出来的一种新型的模拟进化算法。该算法用蚁群在搜索食物源的过程中所体现出来的寻优能力来解决一些系统优化中的困难问题,其算法的基本思想是模仿蚂蚁依赖信息素,通过蚂蚁间正反馈的方法来引导每个蚂蚁的行动。
蚁群算法能够被用于解决大多数优化问题或者能够转化为优化求解的问题,现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面。
蚁群算法是群智能理论研究领域的一种主要算法。
蚁群行为分析
E
A
B
C
D
F
d=3
d=2
m=20
t=0
E
A
B
C
D
F
d=3
d=2
m=10
m=10
t=1
E
A
B
C
D
F
d=3
d=2
m=10
t=7
m=10
E
A
B
C
D
F
d=3
d=2
m=10
t=9
m=10
E
A
B
C
D
F
d=3
d=2
m=20
T>8
m=20
蚂蚁释放的信息素与路径长度成反比
路径上信息素浓度越大,路径被选概率越大
蚁群算法解决优化问题的基本思想
用蚂蚁的行走路径表示待优化问题的可行解,整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息量较多,随着时间的推进,较短路径上积累的信息浓度逐渐增高,选择该路径的蚂蚁个数愈来愈多。最后,整个蚂蚁会在正反馈的作用下集中到最佳路径上,此时对应的便的待优化问题的最优解。
蚁群算法的特点
(1)采用正反馈机制,使得搜索过程不断收敛,最终逼近最优解;
(2)每个个体可能通过释放信息素来改变周围的环境,且每个个体能够感知周围环境的实时变化,个体间通过环境进行间接通讯;
(3)搜索过程采用分布式计算方式,多个个体同时进行并行计算,大大提高了算法的计算能力和运行效率;
(4)启发式的概率搜索方式不容易陷入局部最优,易于寻找到最优解。
2 蚁群算法解决TSP问题
关于TSP
G=(N, E),N={1,2,3,…,n},E={(i,j) | i,j∈N}
城市之间的距离