《群算法原理及其应用》由会员分享，可在线阅读，更多相关《群算法原理及其应用（28页珍藏版）》请在金锄头文库上搜索。
1、蚁群算法原理及其应用摘要：蚁群算法是一种新型仿生类优化算法，是继模拟退火、遗传算法、禁忌搜索等之后的又一启发式智能优化算法。蚁群算法由意大利学者 M.Dorign 等人首先提出，并成功地应用于求解一系列 NP 完全的组合优化问题，如：旅行商问题、二次分配问题、车辆寻路问题和图着色问题等等。蚁群算法从提出到现在，短短十余年的时间，以其在离散型组合优化问题中的突出表现，吸引了人们的极大关注。本文围绕蚁群算法的理论及其应用举例说明其算法的使用方法及其程序的内容。本文将具体说明蚁群聚类、机器人路径规划问题在 matlab 中的应用，并对其原理进行分析。关键词：蚁群算法；matlab ；蚁群聚类；机器人
2、路径规划Ant Colony Algorithm Theory and Its ApplicationABSTRACT: Ant Colony Algorithm is a new evolution optimization algorithm based on bionics,and is another intelligent optimal algorithm after the fire out simulation,the inheritance,and the prohibition search etc.Ant Colony Algorithm was first propos
3、ed by Marco Dorigo and his colleagues.Now it has been successfully applied to solve a series of NP-complete combination optimization problems,such as Traveling Salesman Problem,Quadratic Assignment Problem,Vehicle Routing Problem,Graph Coloring Problem and so on.Ant Colony Algorithm with the discret
4、e combination optimization problems with an outstanding performance has attracted peoples attention since it was proposed just a dozen years ago.This paper focuses on the theoretical of ant colony algorithm and its application to illustrate the use of the algorithm and the content of the program. Th
5、is paper will illustrate the ant colony clustering problem and application of robot path planning problem in matlab to analyze its principle.KEY WORDS: ant colony；matlab； ant colony clustering；robot path planning1 前 言蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法 ，是一种用来在图中寻找优化路径的机率型算法。它由 Marco Dorigo 于 1
6、992 年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。该算法充分利用了蚁群搜索食物的过程与旅行商问题(TSP)之间的相似性，通过人工蚂蚁搜索食物的过程 (即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径)来求解 TSP问题。为了区别于真实的蚂蚁群体，我们称这种算法为“人工蚁群系统算法” ，简称“蚁群算法”。该算法已经成功地应用于 TSP ( traveling salesman problem)问题、QAP(quadratic assignment problem)问题和 job-shop 调度等经典组合优化问题，取得了较好的实验结果。虽然对此方法的
7、研究刚刚起步，但研究表明蚁群算法在求解复杂优化问题(特别是离散优化问题)方面的一些优越性，初步的研究表明该算法具有许多优良的性质。针对 PID 控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。MATLAB 是 Mathworks 公司 1984 年推出的数学软件，其名称是由矩阵实验室(Matrix Laboratory)所合成，因此可知，其最早的理念是提供一套完善的矩阵运算指令，可随着数值运算需求的转变，MATLAB 已经成为各种系统模拟和讯号处理等方面的标准语言。2 蚁群算法2.1 蚁群算法
8、的基本原理蚁群算法是受对真实蚁群行为研究的启发而提出的。蚂蚁这种群居动物，虽然个体的行为简单，但群体的行为却极其复杂。人们经过大量的研究，得出蚂蚁个体之间通过一种称为外激素的物质进行信息传递。蚂蚁在移动过程中会分泌外激素，并且通过感知这种物质的存在及其强度，指导自己的移动方向。一般情况下，蚂蚁朝着外激素强度高的方向移动。也就是说，如果某一路径上走过的蚂蚁越多，留在这条路径上的外激素强度越大，那么蚂蚁选择该路径的概率也就越大。这是一种信息正反馈现象。蚂蚁之间就是通过这样的方式进行信息交换，以便快速地搜寻到食物。昆虫学家通过大量的研究发现：蚂蚁个体之间是通过信息交流达到找到从蚁巢到食物源的最短路径
9、的目的。首先，蚂蚁个体通过在其所经过的路上留下一种称之为“信息素”（pheromone）或“迹” 的物质来实现与同伴之间的信息传递。紧接着随后的蚂蚁遇到信息素时，不仅能检测出该物质的存在以及量的多少，而且可根据信息素的浓度来指导自己对前进方向的选择。信息素随着时间的推移会逐渐挥发掉，于是路径的长短及其蚂蚁的多少就对残余信息素的强度产生影响，反过来信息素的强弱又指导着其它蚂蚁的行动方向。因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。这就构成了蚂蚁群体行为表现出的一种信息正反馈现象，并实现找到蚁巢到食物源的最短路径。图 1 图 2 图 3图 1 中设 A 是蚁巢，E 是食物源，H
10、、C 为障碍物，由于障碍物的存在，由 A外出觅食或由 E 返回巢穴的蚂蚁只能经由 H 或 C 到达目的地。BH 和 HD 距离为 1单位，BC 和 DC 距离为 0.5 单位。假设蚂蚁以“1 单位长度/单位时间”的速度往返于A 和 E，每经过一个单位时间各有 30 只蚂蚁离开 A 和 E 到达 B 和 D。初始时，各有 30 只蚂蚁在 B 和 D 点遇到障碍物，开始选择路径。由于此时路径上无迹，蚂蚁便以相同的概率随机地走两条路中的任意一条，因而 15 只选往H，15 只选往 C（图 2） 。经过一个单位时间以后，路径 BHD 被 15 只蚂蚁爬过，而路径 BCD 上则被 30 只蚂蚁爬过， B
11、CD 上的信息量是 BHD 上信息量的两倍。 此时，又有 30 只蚂蚁离开 B 和 D，于是 20 只选择往 C 方向，而另外 10 只则选往 H（图 3） 。这样，更多的信息量被留在更短的路径 BCD 上。随着时间的推移和上述过程的重复，短路径上的信息量便以更快的速度增长，于是会有越来越多的蚂蚁选择这条短路径，以致最终完全选择这条短路径 BCD。 以上便是蚁群实现找到蚁巢到食物源的最短路径过程。蚂蚁虽然是属于相对弱小，功能并不强大的个体，但却可以完成如此复杂的工作。不难看出，由大量蚂蚁组成的蚁群的集体行为表现出了一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，蚂
12、蚁个体之间就是通过这种信息的交流搜索食物，并最终沿着最短路径行进。人工蚂蚁寻找最优路径的方法就是根据上面的真实蚂蚁寻找最优路径的方法提出的，即让人工蚂蚁根据路径上的相当于 pheromone 的数字信息量的强度来选择路径，并在所经过的路径上留下相当于 pheromone 的数字信息量，然后随着时间的推移，最优路径上的数字信息量将积累得越来越大，从而被选择的概率也越来越大，最终所有人工蚂蚁将趋向于选择该路径。这种模拟蚁群搜索食物的过程与著名的旅行商问题非常相似，因而最初人工蚁群算法被提出用于求解旅行商问题。可见，人工蚁群算法是一种随机搜索算法，与其他模拟进化算法一样，通过侯选解组成的群体的进化过
13、程来寻求最优解，该过程包含两个基本阶段:适应阶段和协作阶段。在适应阶段，各侯选解根据积累的信息不断调整自身结构;在协作阶段，侯选解之间通过信息交流，以期望产生性能更好的解。2.2 蚁群算法模型为了便于理解，通常以蚁群系统(AS)求解平面上 n 个城市的 TSP 问题为例来说明蚁群算法模型。假设有 N 个城市，TSP 问题的目标是寻找一个路径最短的最优旅行路线，旅行商经过所有城市并回到原出发城市，除出发城市外，每个城市只允许经过一次，TSP 问题的可行解即为除出发城市外所有城市的一个无重复序列。假设将 m 只蚂蚁放入到给定的 n 个城市中，那么每一只蚂蚁每一步的行动将符合下列规律：(l)根据路径
14、上的信息素浓度,以相应的概率来选取下一个城市；(2)不再选取自己本次循环己经经过的城市为下一个城市；(3)当完成一步(从一个城市到达另外一个城市) 或者一个循环(完成对所有 n 个城市的访问) 后，更新所有路径上的残留信息浓度。蚂蚁在选择下一个城市的依据主要是两点：(l)ij(t) t 时刻连接城市 i 和 j 的路径上残留信息的浓度，即由算法本身提供的信息；初始时刻，各条路径上的信息量相等，设下 ij(0)= C(C 为常数)，我们以此来模拟实际蚂蚁的信息素；(2)ij由城市 i 转移到城市 j 的启发信息，该启发信息是由要解决的问题给出的，由一定的算法实现。在 TSP 问题中一般取 ij=
15、1/dij。蚂蚁 k(k =1，2.，m) 在运动过程中，根据各条路径上的信息量决定下一步要转移的城市，p kij(t)表示在 t 时刻蚂蚁 k 由位置 i 转移到位置 j 的概率：pkij(t)= 0)()(ijkalowedsissjttifotherwisaldjk也即，蚂蚁选中某一个城市的可能性是问题本身所提供的启发信息与从蚂蚁目前所在城市到目标城市路径上残留信息量的函数。其中：为信息启发式因子,表示轨迹的相对重要性，它反映了蚂蚁在运动过程中所积累的信息素在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，表明蚂蚁之间协作性越强；为期望启发式因子，表示期望值的相对
16、重要程度，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态转移概率越接近于贪婪规则；allowedk=(0，1，2，.，n-1)-tabu k表示蚂蚁 k 下一步允许选择的城市。与实际蚁群不同，人工蚁群系统具有记忆功能，为了避免对同一个城市的多次访问，每一只蚂蚁都保存一个列表 tabuk,用于记录到目前为止蚂蚁 k 己经访问过的城市，列表 tabuk 随着进化过程做动态调整；pkij(t)t 时刻蚂蚁 k 由城市 i 转移到城市 j 的概率。经过 n 个时刻，所有蚂蚁都完成了一次遍历，他们本次遍历的记忆列表将满，此时应清空，将当前蚂蚁所在城市置入 tabuk ，准备下一次遍历，这时，计算每一只蚂蚁所走过的路径 Lk ，并保存最短路径 L min=Lk|k=1， 2， . ， m。随着时间的推移以前留下的信息素逐渐衰减，蚂蚁完成一次循环以后，各路径上的
