确定型模型的建立
1、模型的基本假设与前提
①模型中包含一个回收中心和多个回收客户点，每辆车都由回收中心出发，经由各个客户点完成回收任务后，再次回到回收中心。
②回收中心的容量没有限制。
③每个回收客户点的回收量已知。
④回收中心同各回收客户点相对位置坐标己知，且路径长度对称。
⑤每个回收客户点仅被一辆车服务一次。
⑥每辆车的载重能力和总容积限制已知，单个回收客户点的回收量不能超出单车载重能力和容积约束的1/2。
⑦对于每一辆车，只有当其路径上所有回收量大于最小载重量和最小容积时才能出车。 ⑧每辆车每次任务的总行驶里程不能超过车辆允许最大行驶距离。
⑨回收的货物可以混装。
⑩单位运输成本同运输距离呈线性关系。
2、模型参数及变量定义
P:所有节点集合，P={i}，i=0表示回收中心，i=1，2，…，n 表示回收客户
点
S:回收客户点集合，且P=SU{0}
V:所有车辆集合，V={k}，k=1，2，…，m
D:各节点间距离矩阵，D=)1)*(1(][++n n ij d
ij d :各节点间距离，且0==jj ii d d ,ji ij d d =,P j i ∈?,
k C 0:第k 辆车的固定成本，即增加一辆车所产生的费用
k C ：第k 两车的单位距离费用
k Z max
：第k 辆车的额定最大载重量 k Z min
：第k 辆车的额定最小载重量 k R max
：第k 辆车的额定最大容积 k R min
：第k 辆车的额定最小容积
k L ：第k 辆车允许的最大行驶距离
i w ：第i 个回收客户点出货物的总重量
i v ：第i 个客户点处货物的总体积
ijk x ：0-1变量，当第k 辆车从i 至j 进行回收时，值为1，否则为0
ik y ：0-1变量，当第k 辆车服务第i 个回收客户点时，值为1，否则为0
（3）目标函数 ???
? ??+=∑∑∑∑∈∈∈∈V k P i P j V k ijk ij k k x d C C F 0min （1）
(4)约束条件
∑∈=V k ik y
1 )n 2,1(??∈S i n=3,m=
2 （2）
∑∈=P j ik ijk y x )2,1(),2,1,0(m V k n P i ??∈??∈ （3）
∑∈=P i jk ijk y x ),2,1(),2,1,0(m V k n P j ??∈??∈ （4）
k s i ik i Z y w max
≤∑∈ ),2,1(m V k ??∈ （5） ∑∈≥S i k ik i Z y w min
),2,1(m V k ??∈ (6) k S i ik i R y v max
≤∑∈ ),2,1(m V k ??∈ (7)
∑∈≥S i k ik i
R y
v min ),2,1(m V k ??∈ (8) ∑∑∈∈≤P i P j k ijk ij L x d ),2,1(m V k ??∈ (9)
点进行回收开至辆车从点，第否则
j i k ijk x 1,0{= ),2,1(m V k ??∈ （10） 的货物辆车回收点，第否则
i ik y k 1,0{= ),2,1(m V k ??∈ (11) 目标函数（1）表示车辆使用、运行成本最小；约束条件（2）保证每个客户点均被服务；
（3）、（4）保证驶入和驶出某个客户点的车辆为同一辆，保证每个节点仅被服务一次；（5）、
（6）为车辆最大、最小载重限制；（7）、（8）为车辆最大、最小容积约束；（9）为车辆最大行驶距离约束；（10）、（11）为变量ijk x 、ik y 取值。
不确定型模型的建立
1、模型的基本假设与前提
①模型中包含一个回收中心和多个回收客户点，每辆车都由回收中心出发，经由各个客户点完成回收任务后，再次回到回收中心。
②回收中心的容量没有限制。
③每个回收客户点回收物品的重量和体积均为随机变量，且服从的分布己知。
④回收中心同各回收客户点相对位置坐标己知，且路径长度对称。
⑤每个回收客户点仅被一辆车服务一次。
⑥每辆车的载重能力和总容积限制已知，允许单个回收客户点的回收量在一定置信水平下满足单车辆的载重能力和容积限制。
⑦对于每一辆车，只有当其路径上所有回收量大于最小载重量和最小容积时才能出车。 ⑧允许每辆车每次任务的总行驶里程在一定置信水平下满足车辆允许最大行驶距离。 ⑨单位运输成本同运输距离呈线性关系，回收的货物可以混装。
2、模型参数及变量定义
P:所有节点集合，P={i}，i=0表示回收中心，i=1，2，…，n 表示回收客户
点
S:回收客户点集合，且P=SU{0}
V:所有车辆集合，V={k}，k=1，2，…，m
D:各节点间距离矩阵，D=)1)*(1(][++n n ij d
ij d :各节点间距离，且0==jj ii d d ,ji ij d d =,P j i ∈?,
k C 0:第k 辆车的固定成本，即增加一辆车所产生的费用
k C ：第k 两车的单位距离费用
k Z max
：第k 辆车的额定最大载重量 k Z min
：第k 辆车的额定最小载重量 k R max
：第k 辆车的额定最大容积 k R min
：第k 辆车的额定最小容积 k L ：第k 辆车允许的最大行驶距离
i w ：第i 个回收客户点出货物的总重量
i v ：第i 个客户点处货物的总体积
ijk x ：0-1变量，当第k 辆车从i 至j 进行回收时，值为1，否则为0
ik y ：0-1变量，当第k 辆车服务第i 个回收客户点时，值为1，否则为0
γ:目标函数的置信水平
1α:单车辆载重能力约束置信水平
2α:单车辆容量约束置信水平
3α:单车辆总行驶里程约束置信水平
F :目标函数在置信水平为刀时所取的最小值
Pr{.}:{.}中事件成立的概率
(3)构建需求不确定情况下车辆配置及路径优化问题的机会约束模型:
目标函数:F min （1） 约束条件:γ≥≤+∑∑∑∑∈∈∈∈}Pr{
0V k P i P j V k ijk ij k k F x d C C （2）
∑∈=V k ik y 1 )n 2,1(??∈S i （3）
∑∈=P j ik ijk y x )2,1(),2,1,0(m V k n P i ??∈??∈ （4） ∑∈=P i jk ijk
y x
),2,1(),2,1,0(m V k n P j ??∈??∈ （5） 1max min },Pr{α≥∈≤≤
∑∈S i k ik i k V k Z y w Z （6） 2max min },Pr{α≥∈≤≤
∑∈S i k ik i k V k R y v R （7） 3},Pr{α≥∈≤∑∑∈∈P i P j k ijk ij V k L x d
（8）
点进行回收开至辆车从点，第否则
j i k ijk x 1,0{= ),2,1(m V k ??∈ （9） 的货物辆车回收点，第否则
i ik y k 1,0{= ),2,1(m V k ??∈ （10） 目标函数(1)表示目标函数(车辆使用、运行成本最小，同时使车辆回收货物小于/大于车辆额定载重/容积时)在置信水平为γ厂时所取的最小值;约束条件(2)表示目标函数取得最小值的
概率应不小于置信水平γ;约束条件(3)保证每个客户点均被服务，且每辆车均从回收中心出发;(4)(5)保证驶入和驶出某一客户点的车辆为同一辆，保证每个节点仅被服务一次;(6)表示满足单车辆载重限制的概率应不小于置信水平1α;(7)表示满足车辆容量限制的概率应大于置信水平2α;（8）表示车辆最大行驶路程约束的概率应大于置信水平3α;(9)(10)为变量ijk x 、ik y 取值。
蚁群算法
1、觅食示意图
2、蚂蚁觅食原理
如图所示, 设A 是巢穴, E 是食物源, HC 为一障隘物. 由于障随物存在, 蚂蚁只能经由H 或C 由A 到达E, 或由E 到达A.
设每个时间单位有30 只蚂蚁由A 到达B, 有30 只蚂蚁由E 到达D 点, 蚂蚁过后留下的激素物质量(以下我们称之为信息) 为1. 为方便, 设该物质停留时间为1.
在初始时刻, 由于路径BH、BC、DH、DC 上均无信息存在, 位于B 和E 的蚂蚁可以随机选择路径. 从统计的角度可以认为它们以相同的概率选择BH、BC、DH、DC.
经过一个时间单位后, 在路径BCD 上的信息量是路径BHD 上信息量的二倍.
t= 1 时刻, 将有20 只蚂蚁由B 和D 到达C, 有10 只蚂蚁由B 和D 到达H. 随着时间的推移, 蚂蚁将会以越来越大的概率选择路径BCD, 最终完全选择路径BCD. 从而找到由蚁巢到食物源的最短路径.
3、基本蚂蚁算法的特点可以概括如下:
(1)、较强的鲁棒性，对蚂蚁算法的模型稍加修改，便可以应用于其它问题。
(2)、分布式计算，蚂蚁算法是一种基于种群的进化算法，可以避免过早的收敛，
本质上具有并行性，其搜索过程不是从一点出发，而是从多个点同时进行，这种分布式多智能体的协作是异步并发进行的，分布并行的模式将大大提高整个算法的运行效率和快速反应的能
力。
(3)、易于与其它方法结合，蚁群算法很容易与多种启发式算法结合，以改善算法的性能，如同遗传算法、禁忌搜索算法、人工免疫算法等算法的结合都衍生出多种混合算法。
(4)、正反馈，从而能迅速找到好的解。
(5)、强启发式，能在早期的寻优中迅速找到合适的解决方案.
4、具体算法
设蚁群中蚂蚁的数量为m , dij ( i , j = 1 , 2 , ?, n) 表示点i 和点j 之间的距离.
bi ( t) 表示t 时刻位于点i 的蚂蚁的个数. 显然 ∑ bi ( t) =m.
τij ( t) 表示t 时刻在点i , j 连线上残留的信息量.
初始时刻,各条路径上信息量相等,设τ ij (0) = C( C 为常数) . 蚂蚁k ( k = 1 ,2 , ?, m) 在运动过程中,根据各条路径上的信息量决定转移方向.
在t 时刻蚂蚁k 由点i 转移到点j 的概率k
k tabu t ij ij ij ij k tabu j n t t tabu j k ij t p ?∈∑=?,)()]([)()]([,0{)(βαβ
ατητ (11) ηij —先验知识或称为能见度, 在TSP 问题中为点i 转移到点j 的启发信息;
α—在路径ij 上残留信息的重要程度;
β—启发信息的重要程度;
tab k u —记录蚂蚁k 当前所走过的城市, 称为记忆列表, 集合tab k u 随着进化过程作动态调整. 经过n 个时刻, 所有蚂蚁都完成了一次遍历. 此时, 计算每一只蚂蚁所走过的路径k L , 并保存最短路径Lmin = min { Lk ， k = 1 , 2 , ?, m} .
在蚂蚁完成一次循环以后, 各路径上的信息量进行如下调整
ij ij ij t n t ττρτ?+-=+)()1()( (12)
∑=?=?l
s k ij
ij 1ττ (13) 为蚂蚁k 在本次循环中在点i 和点j 之间留下的信息量, 一般有两种更新方式：
（1）、每只蚂蚁每前进一步都会释放信息素并更新经过路径上的信息素浓度
（2）、只在结束整个循环后才更新.
5、步骤
(l)、参数初始化:令t=0，循环次数c N =0，设置最大循环次数max c N ，将l 只蚂蚁随机地放到n 个城市，将每条边(i ，j)上的信息素设为一个常数，且0=?ij τ，将出发点城市设置到禁忌表中;
(2、)按状态转移式(11)选择下一个城市;
(3)、修改禁忌表，即选择好之后将蚂蚁移动到下一个城市，并把该城市移动到蚂蚁个体的禁忌表中;
(4)、循环执行第(2)步和第(3)步，直到每只蚂蚁都生成一条路径;
(5)、计算第s 只蚂蚁所走路径的总长度Ls;
(6)、根据式(12)和式(13)更新所有路径上的信息量;
(7)、若循环次数从max c c N N ≥，则循环结束并输出计算结果，否则清空禁忌表并转到第(2)步。
蚁群算法简述及实现 1 蚁群算法的原理分析 蚁群算法是受自然界中真实蚁群算法的集体觅食行为的启发而发展起来的一种基于群体的模拟进化算法,属于随机搜索算法,所以它更恰当的名字应该叫“人工蚁群算法”,我们一般简称为蚁群算法。M.Dorigo等人充分的利用了蚁群搜索食物的过程与著名的TSP问题的相似性,通过人工模拟蚁群搜索食物的行为来求解TSP问题。 蚂蚁这种社会性动物,虽然个体行为及其简单,但是由这些简单个体所组成的群体却表现出及其复杂的行为特征。这是因为蚂蚁在寻找食物时,能在其经过的路径上释放一种叫做信息素的物质,使得一定范围内的其他蚂蚁能够感觉到这种物质,且倾向于朝着该物质强度高的方向移动。蚁群的集体行为表现为一种正反馈现象,蚁群这种选择路径的行为过程称之为自催化行为。由于其原理是一种正反馈机制,因此也可以把蚁群的行为理解成所谓的增强型学习系统(Reinforcement Learning System)。 引用M.Dorigo所举的例子来说明蚁群发现最短路径的原理和机制,见图1所示。假设D 和H之间、B和H之间以及B和D之间(通过C)的距离为1,C位于D和B的中央(见图1(a))。现在我们考虑在等间隔等离散世界时间点(t=0,1,2……)的蚁群系统情况。假设每单位时间有30只蚂蚁从A到B,另三十只蚂蚁从E到D,其行走速度都为1(一个单位时间所走距离为1),在行走时,一只蚂蚁可在时刻t留下浓度为1的信息素。为简单起见,设信息素在时间区间(t+1，t+2)的中点(t+1.5)时刻瞬时完全挥发。在t=0时刻无任何信息素,但分别有30只蚂蚁在B、30只蚂蚁在D等待出发。它们选择走哪一条路径是完全随机的,因此在两个节点上蚁群可各自一分为二,走两个方向。但在t=1时刻,从A到B的30只蚂蚁在通向H的路径上(见图1(b))发现一条浓度为15的信息素,这是由15只从B走向H的先行蚂蚁留下来的;而在通向C的路径上它们可以发现一条浓度为30的信息素路径,这是由15只走向BC的路径的蚂蚁所留下的气息与15只从D经C到达B留下的气息之和(图1(c))。这时,选择路径的概率就有了偏差,向C走的蚂蚁数将是向H走的蚂蚁数的2倍。对于从E到D来的蚂蚁也是如此。 （a）（b）（c） 图1 蚁群路径搜索实例 这个过程一直会持续到所有的蚂蚁最终都选择了最短的路径为止。 这样,我们就可以理解蚁群算法的基本思想:如果在给定点,一只蚂蚁要在不同的路径中选择,那么,那些被先行蚂蚁大量选择的路径(也就是信息素留存较浓的路径)被选中的概率就更大,较多的信息素意味着较短的路径,也就意味着较好的问题回答。
蚁群算法的数学模型 蚂蚁),2,1(k m k ???=在运动过程中，运动转移的方向由各条路径上的信息量浓度决定。为方便记录可用),,2,1(t m k abu k ???=来记录第 k 只蚂蚁当前已走过的所有节点，这里可以称存放节点的表为禁忌表；这个存放节点的集合会随着蚂蚁的运动动态的调整。在算法的搜索过程中，蚂蚁会智能地选择下一步所要走的路径。 设 m 表示蚂蚁总数量，用)1,,1,0,(d -???=n j i ij 表示节点 i 和节点 j 之间的距离，)(ij t τ表示在 t 时刻ij 连线上的信息素浓度。 在初始时刻，m 只蚂蚁会被随机地放置，各路径上的初始信息素浓度是相同的。在 t 时刻，蚂蚁 k 从节点i 转移到节点 j 的状态转移概率为 ??? ????=∈=∑∈other p allowed t t t t k ij k allowed k ij ij ij ij k ij ,0j ,) ()()()(p k βαβαητητ ()1-2 其中，{}k k tabu c allowed -=表示蚂蚁 k 下一步可以选择的所有节 点，C 为全部节点集合；α为信息启发式因子，在算法中代表轨迹相对重要程度，反映路径上的信息量对蚂蚁选择路径所起的影响程度，该值越大，蚂蚁间的协作性就越强；β可称为期望启发式因子，在算法中代表能见度的相对重要性。ij η是启发函数，在算法中表示由节点i 转移到节点 j 的期望程度，通常可取ij ij d /1=η。在算法运行时每只蚂蚁将根据(2-1)式进行搜索前进。 在蚂蚁运动过程中，为了避免在路上残留过多的信息素而使启发
一种自适应蚁群算法及其仿真研究 作者：王颖， 谢剑英 作者单位：上海交通大学自动化研究所,上海,200030 刊名： 系统仿真学报 英文刊名：JOURNAL OF SYSTEM SIMULATION 年，卷(期)：2002,14(1) 被引用次数：191次 参考文献(3条) 1.Dorigo M;Maniezzo Vittorio;Colorni Alberto The Ant System: Optimization by a colony of cooperating agents 1996(01) 2.Dorigo M;Gambardella L M Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem[外文期刊] 1997(01) 3.Schoonderwoerd R;Holland O;Bruten J;Rothkrantz L Ant-based Load Balancing in Telecommunications Networks 1997(02) 本文读者也读过(2条) 1.陈崚.沈洁.秦玲.陈宏建基于分布均匀度的自适应蚁群算法[期刊论文]-软件学报2003,14(8) 2.张纪会.高齐圣.徐心和.ZHANG Jihui.GAO Qisheng.XU Xinhe自适应蚁群算法[期刊论文]-控制理论与应用2000,17(1) 引证文献(194条) 1.颜晨阳前馈神经网络连续二元蚁群训练模型[期刊论文]-软件导刊 2011(6) 2.马军.王岩改进的蚁群算法求解旅行Agent问题[期刊论文]-计算机工程与应用 2010(11) 3.楼小明一种改进的自适应蚁群算法求解TSP问题[期刊论文]-黑龙江科技信息 2009(24) 4.闵亨峰供应链节点间配送线路规划蚁群算法[期刊论文]-天津科技大学学报 2006(3) 5.卢正鼎.刘会明基于蚁群算法的理性自适应路由研究[期刊论文]-计算机工程与科学 2006(12) 6.方崇.黄伟军南宁市内河水质的投影寻踪回归分析[期刊论文]-人民长江 2010(8) 7.唐连生.程文明.梁剑.张则强基于行程时间可靠性的车辆路径问题研究[期刊论文]-统计与决策 2008(10) 8.刘学辉P2P网络架构下蚁群算法的应用研究[期刊论文]-无线电通信技术 2007(3) 9.许鹏动态车间调度算法[期刊论文]-航空制造技术 2007(z1) 10.李卓君改进的蚁群算法在VRP中的应用研究[期刊论文]-武汉商业服务学院学报 2006(1) 11.李少辉.刘弘.王静莲蚁群算法在P2P网络架构下的Web服务中的应用[期刊论文]-计算机工程与应用 2006(20) 12.梁栋.霍红卫自适应蚁群算法在序列比对中的应用[期刊论文]-计算机仿真 2005(1) 13.许志红.张培铭基于蚁群算法的智能交流接触器优化设计[期刊论文]-电工电能新技术 2005(3) 14.刘鹏.姜伟.刘新妹.殷俊龄基于蚂蚁算法的PCB板路径优化研究[期刊论文]-电子世界 2012(2) 15.徐滨.张亦改进的蚂蚁算法车辆运行调度算法研究[期刊论文]-计算机仿真 2011(10) 16.陆克芬.方崇.张春乐基于人工鱼群算法的投影寻踪评价方法研究[期刊论文]-安徽农业科学 2009(23) 17.付永强.王启志一种快速收敛的蚁群算法[期刊论文]-福建电脑 2009(9) 18.方崇.李慧颋PMA-PP分析模型在内河水质科学评价中的应用[期刊论文]-地球与环境 2009(4) 19.马洪伟.赵志刚.吕慧显.李京基于蚁群聚类和裁剪方法的RBF神经网络优化算法[期刊论文]-青岛大学学报（工
工程技术 Project technique 云模型在机器人路径规划算法中的研究 马文辉 崔 莹 (齐齐哈尔医学院现代教育技术中心 161000 中国一重技师学院黑龙江省齐齐哈尔市 161000) 【摘 要】传统的遗传算法由于在进化过程中易出现早熟收敛、不能保证种群多样性的现象。本文提出了一种基于云模型的简单、有效的移动机器人避障路径规划算法,采用一维云算子进化变异,同时进化式变异和突变均利用了历史搜索结果,有效避免遗传算法的缺点。模拟数据也证明了该算法的可行性。 【关键词】云模型;进化算法;路径规划;机器人 1 引 言 机器人规划是在已有环境下绕过障碍物找到一个可行的或最优路径从源位置到目标位置,这个问题已得到广泛的研究,各种智能算法不断涌现,这些方法应用于路径规划会使移动机器人在动态环境中更灵活,更具智能化。如人工势场,随机路标规划,基于传感器的方法等。它们都有其优点和缺点。基于遗传算法的机器人路径规划是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。由于其思想简单、易于实现以及表现出来的健壮性,但是因为遗传算法本身的缺陷(早熟、局部能力搜索差),还不能保证计算机效率和路径的可靠性,因此还存在很大的改进发展空间。云模型是对模糊理论隶属函数概念的创新与发展,已成功应用于智能控制、大系统评估、网络安全等。 2 云模型改进机器人路径规划方法 云模型所表达的概念的整体特性可以用期望Ex(Expected value),熵En(Entropy),超熵He(Hyper entropy)这3个数字特征来整体表征。Ex是云滴在论域空间分布的期望,是最能够代表定性概念的点,或者说是这个概念量化的最典型样本。En代表定性概念的可度量粒度,反映了能够代表这个定性概念的云滴的离散程度,亦是在论域空间可被概念接受的云滴的取值范围。He是熵的不确定性度量,即熵的熵,由熵的随机性和模糊性共同决定。用3个数字特征表示的定性概念的整体特征记做C(Ex,En,He)。 基于云模型的优良特性,结合遗传算法的基本原理,本文使用一种自适应、高精度、快速随机搜索机器人路径规划的算法,该算法不但比传统遗传算法精度高,而且能够很好地避免遗传算法易陷入局部最优解和选择压力过大造成的早熟收敛等问题。本文中Ex代表父代个体的优良特征即代表父代路径;En和He表示继承过程的不确定性和模糊性即可被接受的路径范围,利用正态云算子完成概念空间到数值空间的转换,产生种群下一代路径,实现遗传操作。在遗传算法中,当种群的多数个体适应值相差不大时交叉操作就显得无能为力,算法陷入局部解而不能由交换解决,突然变异能够使之摆脱局部收敛而跃出局部解,但是后期的变异可能破坏已产生最优解模块。基于云模型的改进算法可以有效避免遗传算法的这个缺点,因为进化式变异和突变均利用了历史搜索结果。 3 实验方法 3.1 实验的初始设置。P(Eχ,En,He),Eχ=20,En=0.618, He=0.05,k=10,λlocal=3,λglobal=9。 3.2 将优秀路径带入公式(1)产生下一代 Θ[j]=1/(sqrt(2×pi)×sqrt(He))×pow(e,-(j-En)^2/(2×En)) (2) X[j]=(sqrt(2×pi)×sqrt(Θ[j]))×pow(e,-(j-qath[i] [j]))×(j-qath[i][j])/(qath[i][j])(3) path[i][j]=pow(e,-(X[j])-quani[j])×(X[j]-qath[i] [j])/(2×Θ[j])(4) 其中:i∈优秀路径群,j∈路径基因 3.3 计算适应函数fit()。ppercent[i]为第i条路径长度, qpercent[i]为第i条路径惩罚算子 fit[i]=1/appercent[i]+βqpercent[i](5) 其中:α为路径长度因子,β惩罚因子。 3.4 进化过程。进化过程中,若出现跨代精英,En和He减小 为原来的1/k(k为大于1的实数)。当若干进化代没有发现新的跨代精英,即连续平凡代数达到一定的阈值λlocal时,路径可能陷入了一个局部最优邻域,此时需要跳出这个小局部,并在该局部附近尝试寻找新的局部最优,方法是提高En和He为原来的k倍。 3.5 变异过程。当经过若干代进化没有得到适应性更加优 异的路径,而且进化式变异没有效果时,路径可能陷入局部,需要进行一次突变操作。进行局部求变和突变的连续平凡代数阈值之间的关系为λglobal>λlocal。突变方法为取历史跨代精英个体的平均值,熵为相应历史精英个体的方差。 在本算法中进化和变异是统一的,进化式变异是进化和变异融合,可以用来进行局部求精或跳出小局部,而突变则用来在全局范围内寻找新的极值搜索区域.算法可以判断出当前的进化状况,进而可以自适应地进行调整 。 图1 初始最优路径状态 图2 第12代精英路径状态4 结 论 本文采用云模型理论改遗传算法在机器人路径中的应用,不需要繁琐的交叉、变异,具有良好的可操作性。模拟数据验证了这种方法对全局优化性能改善的可行性,可以使该算法优化速度获得一定程度的提高,有效地克服了基本遗传算法收敛速度慢、易限于局部最优解的缺陷。 【参考文献】 [1]Rosell,J.,Iniguez,P.:Pat h planning using Harmonic Functions and Probabilistic Cell Decomposition.Proc.of t he IEEE Int.Conf.on Robotics and Automation(2005):1803-1808. [2]Kazemi,M.,Mehrandezh,M.:RoboticNavigationUsing Harmon2 icFunction-basedProbabilisticRoadmaps.Proc.of t he IEEE Int. Conf.on Robotics and Automation(2004):4765-4770. [3]李德毅,杜益.不确定性人工智能[M].北京:国防工业出版社,2005. [4]戴朝华,朱云芳,陈维荣,林建辉.云遗传算法及其应用[J].电子学 报,2007-7. [5]段海滨,王道波等.基于云模型理论的蚁群算法改进研究[J].哈尔 滨工业大学学报,2005-1. [6]周明,孙树栋.遗传算法原理及应用[J].北京:国防工业出版社,2002-5. [7]陈国良.遗传算法及其应用[M].北京:人民邮电出版社,2001. — 1 2 1 —
蚁群算法报告及代码 一、狼群算法 狼群算法是基于狼群群体智能,模拟狼群捕食行为及其猎物分配方式,抽象出游走、召唤、围攻3种智能行为以及“胜者为王”的头狼产生规则和“强者生存”的狼群更新机制,提出一种新的群体智能算法。 算法采用基于人工狼主体的自下而上的设计方法和基 于职责分工的协作式搜索路径结构。如图1所示,通过狼群个体对猎物气味、环境信息的探知、人工狼相互间信息的共享和交互以及人工狼基于自身职责的个体行为决策最终实现了狼群捕猎的全过程。 二、布谷鸟算法 布谷鸟算法 布谷鸟搜索算法,也叫杜鹃搜索,是一种新兴启发算法CS 算法，通过模拟某些种属布谷鸟的寄生育雏来有效地求解最优化问题的算法.同时，CS 也采用相关的Levy 飞行搜索机制 蚁群算法介绍及其源代码。 具有的优点：全局搜索能力强、选用参数少、搜索路径优、多目标问题求解能力强，以及很好的通用性、鲁棒性。 应用领域：项目调度、工程优化问题、求解置换流水车间调度和计算智能 三、差分算法 差分算法主要用于求解连续变量的全局优化问题，其主要工作步骤与其他进化算法基本一致，主要包括变异、交叉、选择三种操作。 算法的基本思想是从某一随机产生的初始群体开始，利用从种群中随机选取的两个个体
的差向量作为第三个个体的随机变化源，将差向量加权后按照一定的规则与第三个个体求和而产生变异个体，该操作称为变异。然后，变异个体与某个预先决定的目标个体进行参数混合，生成试验个体，这一过程称之为交叉。如果试验个体的适应度值优于目标个体的适应度值，则在下一代中试验个体取代目标个体，否则目标个体仍保存下来，该操作称为选择。在每一代的进化过程中，每一个体矢量作为目标个体一次，算法通过不断地迭代计算，保留优良个体，淘汰劣质个体，引导搜索过程向全局最优解逼近。 四、免疫算法 免疫算法是一种具有生成+检测的迭代过程的搜索算法。从理论上分析，迭代过程中，在保留上一代最佳个体的前提下，遗传算法是全局收敛的。 五、人工蜂群算法 人工蜂群算法是模仿蜜蜂行为提出的一种优化方法，是集群智能思想的一个具体应用，它的主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，通过各人工蜂个体的局部寻优行为，最终在群体中使全局最优值突现出来，有着较快的收敛速度。为了解决多变量函数优化问题，科学家提出了人工蜂群算法ABC模型。 六、万有引力算法 万有引力算法是一种基于万有引力定律和牛顿第二定律的种群优化算法。该算法通过种群的粒子位置移动来寻找最优解，即随着算法的循环，粒子靠它们之间的万有引力在搜索空间内不断运动，当粒子移动到最优位置时，最优解便找到了。 GSA即引力搜索算法，是一种优化算法的基础上的重力和质量相互作用的算法。GSA 的机制是基于宇宙万有引力定律中两个质量的相互作用。 七、萤火虫算法 萤火虫算法源于模拟自然界萤火虫在晚上的群聚活动的自然现象而提出的，在萤火虫的群聚活动中，每只萤火虫通过散发荧光素与同伴进行寻觅食物以及求偶等信息交流。一般来说，荧光素越亮的萤火虫其号召力也就越强，最终会出现很多萤火虫聚集在一些荧光素较亮的萤火虫周围。人工萤火虫算法就是根据这种现象而提出的一种新型的仿生群智能优化算法。在人工萤火虫群优化算法中，每只萤火虫被视为解空间的一个解，萤火虫种群作为初始解随机的分布在搜索空间中，然后根据自然界萤火虫的移动方式进行解空间中每只萤火虫的移动。通过每一代的移动，最终使的萤火虫聚集到较好的萤火虫周围，也即是找到多个极值
蚁群算法matlab精讲及仿真 4.1基本蚁群算法 4.1.1基本蚁群算法的原理 蚁群算法是上世纪90年代意大利学者M.Dorigo,v.Maneizz。等人提出来的,在越来越多的领域里得到广泛应用。蚁群算法，是一种模拟生物活动的智能算法，蚁群算法的运作机理来源于现实世界中蚂蚁的真实行为，该算法是由Marco Dorigo 首先提出并进行相关研究的，蚂蚁这种小生物，个体能力非常有限，但实际的活动中却可以搬动自己大几十倍的物体，其有序的合作能力可以与人类的集体完成浩大的工程非常相似，它们之前可以进行信息的交流，各自负责自己的任务，整个运作过程统一有序，在一只蚂蚁找食物的过程中，在自己走过的足迹上洒下某种物质，以传达信息给伙伴，吸引同伴向自己走过的路径上靠拢，当有一只蚂蚁找到食物后，它还可以沿着自己走过的路径返回，这样一来找到食物的蚂蚁走过的路径上信息传递物质的量就比较大，更多的蚂蚁就可能以更大的机率来选择这条路径，越来越多的蚂蚁都集中在这条路径上，蚂蚁就会成群结队在蚁窝与食物间的路径上工作。当然，信息传递物质会随着时间的推移而消失掉一部分，留下一部分，其含量是处于动态变化之中，起初，在没有蚂蚁找到食物的时候，其实所有从蚁窝出发的蚂蚁是保持一种随机的运动状态而进行食物搜索的，因此，这时，各蚂蚁间信息传递物质的参考其实是没有价值的，当有一只蚂蚁找到食物后，该蚂蚁一般就会向着出发地返回，这样，该蚂蚁来回一趟在自己的路径上留下的信息传递物质就相对较多，蚂蚁向着信息传递物质比较高的路径上运动，更多的蚂蚁就会选择找到食物的路径，而蚂蚁有时不一定向着信
息传递物质量高的路径走，可能搜索其它的路径。这样如果搜索到更短的路径后，蚂蚁又会往更短的路径上靠拢，最终多数蚂蚁在最短路径上工作。【基于蚁群算法和遗传算法的机器人路径规划研究】 该算法的特点： (1)自我组织能力，蚂蚁不需要知道整体环境信息，只需要得到自己周围的信息，并且通过信息传递物质来作用于周围的环境，根据其他蚂蚁的信息素来判断自己的路径。 (2)正反馈机制，蚂蚁在运动的过程中，收到其他蚂蚁的信息素影响，对于某路径上信息素越强的路径，其转向该路径的概率就越大，从而更容易使得蚁群寻找到最短的避障路径。 (3)易于与其他算法结合，现实中蚂蚁的工作过程简单，单位蚂蚁的任务也比较单一，因而蚁群算法的规则也比较简单，稳定性好，易于和其他算法结合使得避障路径规划效果更好。 (4)具有并行搜索能力探索过程彼此独立又相互影响，具备并行搜索能力，这样既可以保持解的多样性，又能够加速最优解的发现。 4.1.2 基本蚁群算法的生物仿真模型 a为蚂蚁所在洞穴,food为食物所在区,假设abde为一条路径,eadf为另外一条路径,蚂蚁走过后会留下信息素,5分钟后蚂蚁在两条路径上留下的信息素的量都为3,概率可以认为相同,而30分钟后baed路径上的信息素的量为60,明显大于eadf路径上的信息素的量。最终蚂蚁会完全选择abed这条最短路径,由此可见,
用蚁群算法用于数据挖掘 一．数据挖掘背景介绍： 数据挖掘和知识发现(Date Mining and Knowledge Discovery，简称ＤＭＫＤ)技术是指从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中提取隐含的、未知的、潜在的、有用的信息的过程。 随着计算机技术迅速发展,数据库技术也得到了广泛的应用。现在的数据库系统可以高效地实现数据的录入、查询、统计计算等功能。如果用数据库管理系统来存储数据，用机器算法来分析数据，挖掘数据背后的知识，这样就产生了数据库中的知识发现(即KDD)和数据挖掘(即DM)。KDD和DM是指识别出存在于数据库中有效的、新颖的、具有潜在效用的、最终可理解的模式的非平凡过程。 数据挖掘的任务分成很多种，包括数据描述(characterization)、数据分类(classification)、数据关联(association)、区别分析(discrimination)、数据回归、数据聚类(clustering)、数据预测(prediction)。 我们这里要用蚁群算法解决的是数据分类这样一个问题：我们预先定义一组类，然后把数据系中的每一个数据根据该数据的属性，归入这些类中的一个。 比如说病情诊断：在医院里，病人感觉不适，进行检查，并且医生对一些以前的状况进行询问，可以得到很多各种方面的参数，比方对于SARS病情，可以得到的一些相关参数：体温，咳嗽，肺部X照射是否有阴影，以及各种症状持续时间，病人前一段时间接触过何种人群等等，这些大量的数据比较容易得到，但是如何根据这些大量的病人的病情参数来判断是否确实为SARS病症并不是一件很简单的事情，这就是我们的数据分类工作要做的事情。 我们要对数据进行分类，首先要有进行分类的规则，我们把判别规则表示为如下形式：IF < conditions > THEN < class > 其中判别规则的前导部分（IF 部分）是一个条件项的集合.条件项就是一个只有<属性，关系符，属性取值>三个元素的简单的条件。不同的条件项用逻辑运算符连接，一般是AND。所以规则的前导部分就是一个由许多简单的条件由逻辑连接而成的复合条件。符合这个条件的数据将被纳入规则后部的class中。 从规则有意义和可理解性来考虑，简单条件不能太多，而属于规则的数目也不能太多。
2.1 蚁群算法的基本原理 蚁群优化算法是模拟蚂蚁觅食的原理，设计出的一种群集智能算法。蚂蚁在觅食过程中能够在其经过的路径上留下一种称之为信息素的物质，并在觅食过程中能够感知这种物质的强度，并指导自己行动方向，它们总是朝着该物质强度高的方向移动，因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。某一条路径越短，路径上经过的蚂蚁越多，其信息素遗留的也就越多，信息素的浓度也就越高，蚂蚁选择这条路径的几率也就越高，由此构成的正反馈过程，从而逐渐的逼近最优路径，找到最优路径。 蚂蚁在觅食过程时，是以信息素作为媒介而间接进行信息交流，当蚂蚁从食物源走到蚁穴，或者从蚁穴走到食物源时，都会在经过的路径上释放信息素，从而形成了一条含有信息素的路径，蚂蚁可以感觉出路径上信息素浓度的大小，并且以较高的概率选择信息素浓度较高的路径。 (a) 蚁穴 1 2 食物源 A B (b) 人工蚂蚁的搜索主要包括三种智能行为： （1）蚂蚁的记忆行为。一只蚂蚁搜索过的路径在下次搜索时就不再被该蚂蚁选择，因此在蚁群算法中建立禁忌表进行模拟。 （2）蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种信息素的物质，当其他蚂蚁进行路径选择时，会根据路径上的信息素浓度进行选择，这样信息素就成为蚂蚁之间进行通信的媒介。 （3）蚂蚁的集群活动。通过一只蚂蚁的运动很难达到事物源，但整个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，路径上留下的信息素数量也就越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路径的信息素强度，而通过的蚂蚁比较少的路径上的信息素会随着时间的推移而挥发，从而变得越来越少。3.3.1蚂蚁系统 蚂蚁系统是最早的蚁群算法。其搜索过程大致如下： 在初始时刻，m 只蚂蚁随机放置于城市中， 各条路径上的信息素初始值相等，设为：0(0)ij ττ=为信息素初始值，可设0m m L τ=，m L 是由最近邻启发式方法构 造的路径长度。其次，蚂蚁(1,2,)k k m = ，按照随机比例规则选择下一步要转
蚁群算法的改进与应用 摘要：蚁群算法是一种仿生优化算法，其本质是一个复杂的智能系统，它具有较强的鲁棒性、优良的分布式计算机制和易于与其他方法结合等优点。但是现在蚁群算法还是存在着缺点和不足,需要我们进一歩改进,如：搜索时间长、容易出现搜索停滞现象、数学基础还不完整。本文首先说明蚁群算法的基本思想,阐述了蚁群算法的原始模型及其特点，其次讨论如何利用遗传算法选取蚁群算法的参数，然后结合对边缘检测的蚁群算法具体实现过程进行研究分析，最后对本论文所做的工作进行全面总结,提出不足之处,并展望了今后要继续研究学习的工作内容。 关键词：蚁群算法;边缘检测;阈值;信息素;遗传算法; 1 前言 蚁群算法是近年来提出的一种群体智能仿生优化算法，是受到自然界中真实的蚂蚁群寻觅食物过程的启发而发现的。蚂蚁之所以能够找到蚁穴到食物之间的最短路径是因为它们的个体之间通过一种化学物质来传递信息，蚁群算法正是利用了真实蚁群的这种行为特征，解决了在离散系统中存在的一些寻优问题。该算法起源于意大利学者 Dorigo M 等人于 1991 年首先提出的一种基于种群寻优的启发式搜索算法，经观察发现，蚂蚁在寻找食物的过程中其自身能够将一种化学物质遗留在它们所经过的路径上，这种化学物质被学者们称为信息素。这种信息素能够沉积在路径表面，并且可以随着时间慢慢的挥发。在蚂蚁寻觅食物的过程中，蚂蚁会向着积累信息素多的方向移动，这样下去最终所有蚂蚁都会选择最短路径。该算法首先用于求解著名的旅行商问题（Traveling Salesman Problem，简称 TSP）并获得了较好的效果，随后该算法被用于求解组合优化、函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由等问题。 尽管目前对 ACO 的研究刚刚起步，一些思想尚处于萌芽时期，但人们已隐隐约约认识到，人类诞生于大自然，解决问题的灵感似乎也应该来自大自然，因此越来越多人开始关注和研究 ACO，初步的研究结果已显示出该算法在求解复杂优化问题（特别是离散优化问题）方面的优越性。虽然 ACO 的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种自然生物的新型系统寻优思想无疑具有十分光明的前景。但该算法存在收敛速度慢且容易出现停滞现象的缺点，这是因为并不是所有的候选解都是最优解，而候选解却影响了蚂蚁的判断以及在蚂蚁群体中，单个蚂蚁的运动没有固定的规则，是随机的，蚂蚁与蚂蚁之间通过信息素来交换信息，但是对于较大规模的优化问题，这个信息传递和搜索过程比较繁琐，难以在较短的时间内找到一个最优的解。 由于依靠经验来选择蚁群参数存在复杂性和随机性,因此本文最后讨论如何利用遗传算法选取蚁群算法的参数。遗传算法得到的蚁群参数减少了人工选参的不确定性以及盲目性。 2 基本蚁群算法 2.1 蚁群算法基本原理 根据仿生学家的研究结果表明,单只蚂蚁不能找到从巢穴到食物源的最短路 径,而大量蚂蚁之间通过相互适应与协作组成的群体则可以,蚂蚁是没有视觉的,但是是通过蚂蚁在它经过的路径上留下一种彼此可以识别的物质,叫信息素,来相互传递信息,达到协作的。蚂蚁在搜索食物源的过程中,在所经过的路径上留下信息素,同时又可以感知并根据信息素的浓度来选择下一条路径,一条路径上的浓度越浓,蚂蚁选择该条路径的概率越大,并留下信息素使这条路径上的浓度加强,这样会有更多的蚂蚁选择次路径。相反,信息素浓度少的路
目录..................................................................... I 摘要.................................................................... V Abstract ................................................................. VI 第一章引言.. (1) 非对称TSP问题（ATSP）及其求解方法概述 (1) 人工蚁群算法的主要思想和特点 (1) 主要工作 (2) 第二章 ATSP问题分析 (3) ATSP问题的数学模型 (3) ATSP问题与TSP问题的比较 (3) 第三章求解ATSP问题的人工蚁群算法 (4) ATSP问题的蚁群算法表示 (4) 人工蚁群算法的实现 (4) 人工蚁群算法的流程图 (5) 蚁群的规模、算法终止条件 (6) 路径选择方法和信息素的更新方法 (7) 第四章实验和分析 (10) 测试环境 (10) 测试用例 (10) 实验结果及参数分析 (10) 的测试结果 (10) 的测试结果 (12) 的测试结果 (13) 的测试结果 (13) 相关参数修改后的测试结果 (14) 第五章总结 (16) 致谢 (17) 参考文献 (17)
摘要 旅行商问题(TSP问题)是组合优化的著名难题。它具有广泛的应用背景,如计算机、网络、电气布线、加工排序、通信调度等。已经证明TSP问题是NP难题,鉴于其重要的工程与理论价值,TSP常作为算法性能研究的典型算例。TSP的最简单形象描述是:给定n个城市,有一个旅行商从某一城市出发,访问各城市一次且仅有一次后再回到原出发城市,要求找出一条最短的巡回路径。TSP分为对称TSP和非对称TSP两大类,若两城市往返距离相同,则为对称TSP,否则为非对称TSP 。本文研究的是对称的ATSP。 实质上，ATSP问题是在TSP问题上发展而来的，它们的区别就在于两座城市之间的往返距离是否相同。例如，有A,B两个城市，在TSP问题中，从A到B的距离是等于从B到A得距离的，是一个单向选择的连通问题。而在ATSP问题中，从A到B的距离就不一定等于从B到A的距离，所以这是双向选择的联通问题。 本文主要阐述了用人工蚁群算法的原理和一些与其相关联的知识结构点。通过对算法原理的理解，及在函数优化问题上的应用，与优化组合问题的研究来了解ATSP问题以及人工蚁群算法解决实际问题上的应用与研究。 关键词：ATSP ；组合优化；人工蚁群算法；TSP
摘要 自意大利学者M. Dorigo于1991年提出蚁群算法后，该算法引起了学者们的极大关注，在短短十多年的时间里，已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛应用，并取得了较好的效果。本文首先讨论了该算法的基本原理，接着介绍了旅行商问题，然后对蚁群算法及其二种改进算法进行了分析，并通过计算机仿真来说明蚁群算法基本原理，然后分析了聚类算法原理和蚁群聚类算法的数学模型，通过调整传统的蚁群算法构建了求解聚类问题的蚁群聚类算法。最后，本文还研究了一种依赖信息素解决聚类问题的蚁群聚类算法，并把此蚁群聚类算法应用到对人工数据进行分类，还利用该算法对2005年中国24所高校综合实力进行分类，得到的分类结果与实际情况相符，说明了蚁群算法在聚类分析中能够收到较为理想的结果。 【关键词】蚁群算法；计算机仿真；聚类；蚁群聚类
Study on Ant Colony Algorithm and its Application in Clustering Abstract： As the ant colony algorithm was proposed by M. Dorigo in 1991,it bringed a extremely large attention of scholars, in past short more than ten years, optimized, the network route, the function in the combination optimizes, domains and so on data mining, robot way plan has obtained the widespread application, and has obtained the good effect.This acticle discussed the basic principle of it at first, then introduced the TSP,this acticle also analysed the ant colony algorithm and its improved algorithm, and explanated it by the computer simulates, then it analysed the clustering algorithm and the ant clustering algorithm, builded the ant clustering algorith to solution the clustering by the traditioned ant algorithm. At last, this article also proposed the ant clustering algorith to soluted the clustering dependent on pheromon. Carry on the classification to the artificial data using this ant clustering algorithm; Use this algorithm to carry on the classification of the synthesize strength of the 2005 Chinese 24 universities; we can obtain the classified result which matches to the actual situation case. In the next work, we also should do the different cluster algorithm respective good and bad points as well as the classified performance aspect the comparison research; distinguish the different performance of different algorithm in the analysis when the dates are different. Key words： Ant colony algorithm; Computer simulation; clustering; Ant clustering 目录
用ACO 算法求解机器人路径优化问题 4.1 问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则(如最小能量消耗，最短行走路线，最短行走时间等)，在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 4.2 算法理论 蚁群算法（Ant Colony Algorithm，ACA），最初是由意大利学者Dorigo M. 博士于1991 年首次提出，其本质是一个复杂的智能系统，且具有较强的鲁棒性，优良的分布式计算机制等优点。该算法经过十多年的发展，已被广大的科学研究人员应用于各种问题的研究，如旅行商问题，二次规划问题，生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Dorigo 提出了精英蚁群模型（EAS），在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢，并不能取得较好的效果。次年Dorigo 博士在文献[30]中给出改进模型（ACS），文中 改进了转移概率模型，并且应用了全局搜索与局部搜索策略，来得进行深度搜索。 Stützle 与Hoos给出了最大-最小蚂蚁系统（MAX-MINAS），所谓最大-最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优，设定下限鼓励深度搜索。 蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的，蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物，蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能，可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图 2-1 所示，AE 之间有
蚁群算法 主讲人：郝娟指导老师：张著洪
目录 1蚁群算法概述 (21) 1.1蚁群算法的提出与发展 (21) 1.2蚁群算法原理 (22) 1.3数学模型的建立 (25) 2蚁群算法的仿真分析 (29) 2.1蚁群算法流程 (30) 2.2蚁群算法的计算机仿真 (30) 2.3分析与总结 (34) 3蚁群算法的优化 (38) 3.1基本蚁群算法的缺点 (38) 3.2改进与优化方法 (40) 3.3优化蚁群算法方案的仿真分析 (43) 4小结 (44)
第一章蚁群算法概述 生物学家通过对蚂蚁的长期研究发现，虽然每只蚂蚁智能不高，也没有集中的指挥，但它们却可以协同工作，依靠群体能力发挥出超出个体的智能。蚁群算法(ant colony algorithm, ACA)是最新发展的一种模拟蚂蚁群体智能行为的仿生优化算法，具有较强的鲁棒性、分布式计算机制、易于与其它算法结合等优点。尽管目前蚁群算法的严格理论基础尚未奠定，国内外的相关研究还处在实验探索和初步应用阶段，但蚁群算法己经由当初的单一TSP旅行商问题领域渗透到多个应用领域，有着广泛的应用前景。 1蚁群算法的提出与发展 根据蚂蚁“寻找食物”的群体智能行为，意大利学者M.Dorigo于1991年在法国召开的第一届欧}}l}l人工生命会议(European Conference on Artificial Life, ECAL中第一次提出了蚁群算法的基本模型。到1992年，M.Dorigo又在其博士学位论文中进一步阐述了蚁群算法的核心思想。由于在模拟仿真中使用了人工蚂蚁的概念，因此也称蚂蚁系统(ant system, AS )。 近年来，蚁群算法逐渐被国内学者了解和研究，相继出现了一些介绍性的文献，其后在蚁群算法的应用研究方面(如组合优化问题、网络路由调度问题等)开展了许多研究工作。 2蚁群算法原理 2.1生物学原型 蚂蚁系统是最早建立的蚁群算法模型，其模型的建立来源于对蚂蚁寻找食物行为的研究。蚂蚁视力很有限，但是蚂蚁寻找食物的过程中却有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径，并且能随环境的变化而变化，适应性地搜索新的路径，产生新的选择。 经过研究发现，在从食物源到蚁穴并返回的过程中，蚂蚁能在其走过的路径上分泌一种化学物质一信息素，通过这种方式形成信息素轨迹。信息素轨迹可以使蚂蚁找到其返回食物源(或蚁穴)的路径，其他蚂蚁也可以利用该轨迹找到由同伴发现的食物源的位置。由蚂蚁个体的特征可以看出，蚂蚁除了对信息素有感知外几乎无法获知环境的信息，因而当环境中不存在信息素时，蚂蚁的行为是完全随机的。也就是说，蚂蚁在一个新的环境中的初始行走是完全随机的。另外，蚂蚁的搜索不是孤立的。事实上，假如只有一只蚂蚁进行搜索，由于蚂蚁的短视，很难找到最佳路径。当蚂蚁走过一条路径时，在上面留下的信息素会吸引更多的蚂蚁走这条路。当这条路径上通过的蚂蚁越来越多，以至信息素强度增大，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。 图2.1 蚁群的初始路径
蚁群优化算法
目录 [隐藏]
? ?
比较
1 2
蚁群算法的提出： 人工蚂蚁与真实蚂蚁的异同
o o ? ? ? ? ?
3 4 5 6 7
2.1 2.2
相同点比较 不同点比较
蚁群算法的流程图 基本蚁群算法的实现步骤 蚁群算法的 matlab 源程序 蚁群算法仿真结果 版权声明
[编辑]蚁群算法的提出：
人类认识事物的能力来源于与自然界的相互作用，自然界一直是人类创造力 的源泉。 自然界有许多自适应的优化现象不断地给人以启示，生物和自然中的生 态系 统可以利用自身的演化来让许多在人类看来高度复杂的优化问题得到几乎完美 的解决。近些年来，一些与经典的数学问题思想不同的，试图通过模拟自然生态 系统 来求解复杂优化问题的仿生学算法相继出现，如蚁群算法、遗传算法、粒子群算 法等。 这些算法大大丰富了现在优化技术，也为那些传统最优化技术难以处理的 组 合优化问题提供了切实可行的解决方案。 生物学家通过对蚂蚁的长期的观察发现，每只蚂蚁的智能并不高，看起来没 有集中的指挥，但它们却能协同工作，集中事物，建起坚固漂亮的蚁穴并抚养后 代， 依靠群体能力发挥出超出个体的智能。 蚁群算法是最新发展的一种模拟昆虫王国 中蚂蚁群体智能行为的仿生优化算法，它具有较强的鲁棒性、优良的分布式计算 机 制、易于与其他方法相结合等优点。尽管蚁群算法的严格理论基础尚未奠定，国 内外的相关研究还处于实验阶段， 但是目前人们对蚁群算法的研究已经由当初单 一 的旅行商问题(TSP)领域渗透到了多个应用领域，由解决一维静态优化问题发展 到解决多维动态组合优化问题， 由离散域范围内的研究逐渐扩展到了连续域范围 内的