群算法原理及其应用.docx
《群算法原理及其应用.docx》由会员分享，可在线阅读，更多相关《群算法原理及其应用.docx（42页珍藏版）》请在冰点文库上搜索。
群算法原理及其应用
蚁群算法原理及其应用
摘要：
蚁群算法是一种新型仿生类优化算法，是继模拟退火、遗传算法、禁忌搜索等之后的又一启发式智能优化算法。
蚁群算法由意大利学者M.Dorign等人首先提出，并成功地应用于求解一系列NP完全的组合优化问题，如：
旅行商问题、二次分配问题、车辆寻路问题和图着色问题等等。
蚁群算法从提出到现在，短短十余年的时间，以其在离散型组合优化问题中的突出表现，吸引了人们的极大关注。
本文围绕蚁群算法的理论及其应用举例说明其算法的使用方法及其程序的内容。
本文将具体说明蚁群聚类、机器人路径规划问题在matlab中的应用，并对其原理进行分析。
关键词：
蚁群算法；matlab；蚁群聚类；机器人路径规划
AntColonyAlgorithmTheoryandItsApplication
ABSTRACT:
AntColonyAlgorithmisanewevolutionoptimizationalgorithmbasedonbionics,andisanotherintelligentoptimalalgorithmafterthefireoutsimulation,theinheritance,andtheprohibitionsearchetc.AntColonyAlgorithmwasfirstproposedbyMarcoDorigoandhiscolleagues.NowithasbeensuccessfullyappliedtosolveaseriesofNP-completecombinationoptimizationproblems,suchasTravelingSalesmanProblem,QuadraticAssignmentProblem,VehicleRoutingProblem,GraphColoringProblemandsoon.AntColonyAlgorithmwiththediscretecombinationoptimizationproblemswithanoutstandingperformancehasattractedpeople’sattentionsinceitwasproposedjustadozenyearsago.
Thispaperfocusesonthetheoreticalofantcolonyalgorithmanditsapplicationtoillustratetheuseofthealgorithmandthecontentoftheprogram.Thispaperwillillustratetheantcolonyclusteringproblemandapplicationofrobotpathplanningprobleminmatlabtoanalyzeitsprinciple.
KEYWORDS:
antcolony；matlab；antcolonyclustering；robotpathplanning
1前言
蚁群算法（antcolonyoptimization,ACO），又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。
它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
该算法充分利用了蚁群搜索食物的过程与旅行商问题（TSP）之间的相似性，通过人工蚂蚁搜索食物的过程（即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径）来求解TSP问题。
为了区别于真实的蚂蚁群体，我们称这种算法为“人工蚁群系统算法”，简称“蚁群算法”。
该算法已经成功地应用于TSP（travelingsalesmanproblem）问题、QAP（quadraticassignmentproblem）问题和job-shop调度等经典组合优化问题，取得了较好的实验结果。
虽然对此方法的研究刚刚起步，但研究表明蚁群算法在求解复杂优化问题（特别是离散优化问题）方面的一些优越性，初步的研究表明该算法具有许多优良的性质。
针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。
MATLAB是Mathworks公司1984年推出的数学软件，其名称是由矩阵实验室（MatrixLaboratory）所合成，因此可知，其最早的理念是提供一套完善的矩阵运算指令，可随着数值运算需求的转变，MATLAB已经成为各种系统模拟和讯号处理等方面的标准语言。
2蚁群算法
2.1蚁群算法的基本原理
蚁群算法是受对真实蚁群行为研究的启发而提出的。
蚂蚁这种群居动物，虽然个体的行为简单，但群体的行为却极其复杂。
人们经过大量的研究，得出蚂蚁个体之间通过一种称为外激素的物质进行信息传递。
蚂蚁在移动过程中会分泌外激素，并且通过感知这种物质的存在及其强度，指导自己的移动方向。
一般情况下，蚂蚁朝着外激素强度高的方向移动。
也就是说，如果某一路径上走过的蚂蚁越多，留在这条路径上的外激素强度越大，那么蚂蚁选择该路径的概率也就越大。
这是一种信息正反馈现象。
蚂蚁之间就是通过这样的方式进行信息交换，以便快速地搜寻到食物。
昆虫学家通过大量的研究发现：
蚂蚁个体之间是通过信息交流达到找到从蚁巢到食物源的最短路径的目的。
首先，蚂蚁个体通过在其所经过的路上留下一种称之为“信息素”（pheromone）或“迹”的物质来实现与同伴之间的信息传递。
紧接着随后的蚂蚁遇到信息素时，不仅能检测出该物质的存在以及量的多少，而且可根据信息素的浓度来指导自己对前进方向的选择。
信息素随着时间的推移会逐渐挥发掉，于是路径的长短及其蚂蚁的多少就对残余信息素的强度产生影响，反过来信息素的强弱又指导着其它蚂蚁的行动方向。
因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。
这就构成了蚂蚁群体行为表现出的一种信息正反馈现象，并实现找到蚁巢到食物源的最短路径。
图1图2图3
图1中设A是蚁巢，E是食物源，H、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只蚂蚁爬过，BCD上的信息量是BHD上信息量的两倍。
此时，又有30只蚂蚁离开B和D，于是20只选择往C方向，而另外10只则选往H（图3）。
这样，更多的信息量被留在更短的路径BCD上。
随着时间的推移和上述过程的重复，短路径上的信息量便以更快的速度增长，于是会有越来越多的蚂蚁选择这条短路径，以致最终完全选择这条短路径BCD。
以上便是蚁群实现找到蚁巢到食物源的最短路径过程。
蚂蚁虽然是属于相对弱小，功能并不强大的个体，但却可以完成如此复杂的工作。
不难看出，由大量蚂蚁组成的蚁群的集体行为表现出了一种信息正反馈现象：
某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，蚂蚁个体之间就是通过这种信息的交流搜索食物，并最终沿着最短路径行进。
人工蚂蚁寻找最优路径的方法就是根据上面的真实蚂蚁寻找最优路径的方法提出的，即让人工蚂蚁根据路径上的相当于pheromone的数字信息量的强度来选择路径，并在所经过的路径上留下相当于pheromone的数字信息量，然后随着时间的推移，最优路径上的数字信息量将积累得越来越大，从而被选择的概率也越来越大，最终所有人工蚂蚁将趋向于选择该路径。
这种模拟蚁群搜索食物的过程与著名的旅行商问题非常相似，因而最初人工蚁群算法被提出用于求解旅行商问题。
可见，人工蚁群算法是一种随机搜索算法，与其他模拟进化算法一样，通过侯选解组成的群体的进化过程来寻求最优解，该过程包含两个基本阶段:
适应阶段和协作阶段。
在适应阶段，各侯选解根据积累的信息不断调整自身结构;在协作阶段，侯选解之间通过信息交流，以期望产生性能更好的解。
2.2蚁群算法模型
为了便于理解，通常以蚁群系统（AS）求解平面上n个城市的TSP问题为例来说明蚁群算法模型。
假设有N个城市，TSP问题的目标是寻找一个路径最短的最优旅行路线，旅行商经过所有城市并回到原出发城市，除出发城市外，每个城市只允许经过一次，TSP问题的可行解即为除出发城市外所有城市的一个无重复序列。
假设将m只蚂蚁放入到给定的n个城市中，那么每一只蚂蚁每一步的行动将符合下列规律：
（l）根据路径上的信息素浓度,以相应的概率来选取下一个城市；
（2）不再选取自己本次循环己经经过的城市为下一个城市；
（3）当完成一步（从一个城市到达另外一个城市）或者一个循环（完成对所有n个城市的访问）后，更新所有路径上的残留信息浓度。
蚂蚁在选择下一个城市的依据主要是两点：
（l）τij（t）—t时刻连接城市i和j的路径上残留信息的浓度，即由算法本身提供的信息；初始时刻，各条路径上的信息量相等，设下τij（0）=C（C为常数），我们以此来模拟实际蚂蚁的信息素；
（2）ηij—由城市i转移到城市j的启发信息，该启发信息是由要解决的问题给出的，由一定的算法实现。
在TSP问题中一般取ηij=1/dij。
蚂蚁k（k=1，2...，m）在运动过程中，根据各条路径上的信息量决定下一步要转移的城市，pkij（t）表示在t时刻蚂蚁k由位置i转移到位置j的概率：
pkij（t）=
也即，蚂蚁选中某一个城市的可能性是问题本身所提供的启发信息与从蚂
蚁目前所在城市到目标城市路径上残留信息量的函数。
其中：
α—为信息启发式因子,表示轨迹的相对重要性，它反映了蚂蚁在运动过程中所积累的信息素在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，表明蚂蚁之间协作性越强；
β—为期望启发式因子，表示期望值的相对重要程度，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态转移概率越接近于贪婪规则；
allowedk=（0，1，2，...，n-1）-tabuk—表示蚂蚁k下一步允许选择的城市。
与实际蚁群不同，人工蚁群系统具有记忆功能，为了避免对同一个城市的多次访问，每一只蚂蚁都保存一个列表tabuk,用于记录到目前为止蚂蚁k己经访问过的城市，列表tabuk随着进化过程做动态调整；
pkij（t）—t时刻蚂蚁k由城市i转移到城市j的概率。
经过n个时刻，所有蚂蚁都完成了一次遍历，他们本次遍历的记忆列表将满，此时应清空，将当前蚂蚁所在城市置入tabuk，准备下一次遍历，这时，计算每一只蚂蚁所走过的路径Lk，并保存最短路径Lmin={Lk|k=1，2，...，m}。
随着时间的推移以前留下的信息素逐渐衰减，蚂蚁完成一次循环以后，各路径上的信息量要根据下式作如下调整。
其中，
表示第k只蚂蚁在时刻（t，t+1）留在路径（i，j）上的信息素量，其值视蚂蚁表现的优劣程度而定。
路径越短释放的信息素就越多；
表示本次循环中路径（i,j）的信息素的增量；（1−ρ）为信息素轨迹的衰减系数，ρ∈（0,1）。
根据具体算法的不同，∆τij、∆τkij及Pkij（t）的表达形式可以不同，要根据具体问题而定。
M.Dorigo曾给出三种不同模型，分别称为蚁周系统（ant－cyclesystem）、蚁量系统（ant－quantitysystem），蚁密系统（ant－densitysystem）。
在一系列标准测试问题上运行的实验表明，蚁周算法的性能优于其他两法，表达式如下：
2.3蚁群算法的特点
（1）蚁群算法是一种自组织的算法。
在系统论中，自组织和它组织是组织的两个基本分类，其区别在于组织力或组织指令是来自于系统的内部还是来自于系统的外部，来自于系统内部的是自组织，来自于系统外部的是他组织。
如果系统在获得空间的、时间的或者功能结构的过程中，没有外界的特定干预，我们便说系统是自组织的。
在抽象意义上讲，自组织就是在没有外界作用下使得系统熵增加的过程（即是系统从无序到有序的变化过程）。
蚁群算法充分体现了这个过程，以蚂蚁群体优化为例子说明。
当算法开始的初期，单个的人工蚂蚁无序的寻找解，算法经过一段时间的演化，人工蚂蚁间通过信息激素的作用，自发的越来越趋向于寻找到接近最优解的一些解，这就是一个无序到有序的过程。
（2）蚁群算法是一种本质上并行的算法。
每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。
所以蚁群算法则可以看作是一个分布式的多agent系统，它在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。
（3）蚁群算法是一种正反馈的算法。
从真实蚂蚁的觅食过程中我们不难看出，蚂蚁能够最终找到最短路径，直接依赖于最短路径上信息激素的堆积，而信息激素的堆积却是一个正反馈的过程。
对蚁群算法来说，初始时刻在环境中存在完全相同的信息激素，给予系统一个微小扰动，使得各个边上的轨迹浓度不相同，蚂蚁构造的解就存在了优劣，算法采用的反馈方式是在较优的解经过的路径留下更多的信息激素，而更多的信息激素又吸引了更多的蚂蚁，这个正反馈的过程使得初始的不同得到不断的扩大，同时又引导整个系统向最优解的方向进化。
因此，正反馈是蚂蚁算法的重要特征，它使得算法演化过程得以进行。
（4）蚁群算法具有较强的鲁棒性。
相对于其它算法，蚁群算法对初始路线要求不高，即蚁群算法的求解结果不依赖子初始路线的选择，而且在搜索过程中不需要进行人工的调整。
其次，蚁群算法的参数数目少，设置简单，易于蚁群算法应用到其它组合优化问题的求解。
该算法也存在一些缺陷：
（1）该算法一般需要较长的搜索时间。
蚁群中各个个体的运动是随机的，虽然通过信息交换能够向着最优路径进化，但是当群体规模较大时，很难在短时间内从大量杂乱无章的路径中找出一条较好的路径。
这是因为在进化的初级阶段，各个路径上的信息量相差不明显。
通过的信息正反馈，使得较好路径上的信息量逐渐增大，经过较长一段时间，才能使得较好路径上的信息量明显高于其他路径上的信息量，随着这一过程的进行，差别越来越明显，从而最终收敛于较好的路径。
这一过程一般需要较长的时间。
（2）该算法容易出现停滞现象（stagnationbehavior），即搜索进行到一定程度后，
所有个体所发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。
2.4蚁群算法的应用
蚁群算法的应用进展以蚁群算法为代表的蚁群智能已成为当今分布式人工智能研究的一个热点，许多源于蜂群和蚁群模型设计的算法己越来越多地被应用于企业的运转模式的研究。
美国五角大楼正在资助关于群智能系统的研究工作---群体战略（SwarmStrategy），它的一个实战用途是通过运用成群的空中无人驾驶飞行器和地面车辆来转移敌人的注意力，让自己的军队在敌人后方不被察觉地安全进行。
英国电信公司和美国世界通信公司以电子蚂蚁为基础，对新的电信网络管理方法进行了试验。
群智能还被应用于工厂生产计划的制定和运输部门的后勤管理。
美国太平洋西南航空公司采用了一种直接源于蚂蚁行为研究成果的运输管理软件，结果每年至少节约了1000万美元的费用开支。
英国联合利华公司己率先利用群智能技术改善其一家牙膏厂的运转情况。
美国通用汽车公司、法国液气公司、荷兰公路交通部和美国一些移民事务机构也都采用这种技术来改善其运转的机能。
鉴于群智能广阔的应用前景，美国和欧盟均于近几年开始出资资助基于群智能模拟的相关研究项目，并在一些院校开设群体智能的相关课程。
国内，国家自然科学基金”十五”期间学科交叉类优先资助领域中的认知科学及其信息处理的研究内容中也明确列出了群智能领域的进化、自适应与现场认知主题。
蚁群优化算法最初用于解决TSP问题，经过多年的发展，已经陆续渗透到其他领域中，如，图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。
蚁群算法在若干领域己获得成功的应用，其中最成功的是在组合优化问题中的应用。
在网络路由处理中，网络的流量分布不断变化，网络链路或结点也会随机地失效或重新加入。
蚁群的自身催化与正向反馈机制正好符合了这类问题的求解特点，因而，蚁群算法在网络领域得到一定应用。
蚁群觅食行为所呈现出的并行与分布特性使得算法特别适合于并行化处理。
因而，实现算法的并行化执行对于大量复杂的实际应用问题的求解来说是极具潜力的。
在某群体中若存在众多无智能的个体，它们通过相互之间的简单合作所表现出来的智能行为即称为集群智能（SwarmIntelligence）。
互联网上的交流，不过是更多的神经元连接（人脑）通过互联网相互作用的结果，光缆和路由器不过是轴突和突触的延伸。
从自组织现象的角度上看，人脑的智能和蚁群也没有本质上的区别，单个神经元没有智能可言，单个蚂蚁也没有，但是通过连接形成的体系，是一个智能体。
3蚁群算法的实例仿真研究
3.1蚁群算法的聚类仿真
聚类分析（clusteranalysis）是数据挖掘领域中最为常见的技术之一，它可用于大规模数据集中的对象类，并能根据数据之间的相似程度自动地进行分类，使得不同类之间的相似度尽量小，而同一个类内的相似度尽量大。
蚁群聚类算法通过模拟蚁群的群体智能行为构建聚类模型,是一种基于模型的聚类分析算法,也是近年来聚类分析领域研究的热点和前沿课题。
研究发现,基于蚁群算法构建聚类分析模型在解决某些问题上往往比传统的聚类算法更接近于实际的聚类问题。
聚类分析技术在现实生活中具有非常广泛的用途。
在生物信息学中，聚类分析可以用于分析具有相似功能的基因组序列，获取生物基因组内部的固有结构以及潜在的基因规律。
在商业竞争中,聚类分析可以用于分析不同消费人群的消费行为模式，辅助商业管理者进行决策分析。
在搜索引擎中,聚类分析可以用于挖掘用户的兴趣模式。
在文档分析中，聚类分析可以用于挖掘文档的主题特征等。
3.1.1蚁群聚类仿真源代码
%AntColonyOptimizationfortheClustering
clc;
clear;
%N=number_of_test_sample;
N=150;
%n=number_of_attribute_of_test_sample;
n=4;
%K=number_of_cluster;
K=3;
%R=number_of_ants;
R=10;
%t_max=MaxIterations;
t_max=1000;
%X=test_sample_matrix;
X=[
5.13.51.40.2
4.93.01.40.2
4.73.21.30.2
4.63.11.50.2
5.03.61.40.2
5.43.91.70.4
4.63.41.40.3
5.03.41.50.2
4.42.91.40.2
4.93.11.50.1
5.43.71.50.2
4.83.41.60.2
4.83.01.40.1
4.33.01.10.1
5.84.01.20.2
5.74.41.50.4
5.43.91.30.4
5.13.51.40.3
5.73.81.70.3
5.13.81.50.3
5.43.41.70.2
5.13.71.50.4
4.63.61.00.2
5.13.31.70.5
4.83.41.90.2
5.03.01.60.2
5.03.41.60.4
5.23.51.50.2
5.23.41.40.2
4.73.21.60.2
4.83.11.60.2
5.43.41.50.4
5.24.11.50.1
5.54.21.40.2
4.93.11.50.1
5.03.21.20.2
5.53.51.30.2
4.93.11.50.1
4.43.01.30.2
5.13.41.50.2
5.03.51.30.3
4.52.31.30.3
4.43.21.30.2
5.03.51.60.6
5.13.81.90.4
4.83.01.40.3
5.13.81.60.2
4.63.21.40.2
5.33.71.50.2
5.03.31.40.2
7.03.24.71.4
6.43.24.51.5
6.93.14.91.5
5.52.34.01.3
6.52.84.61.5
5.72.84.51.3
6.33.34.71.6
4.92.43.31.0
6.62.94.61.3
5.22.73.91.4
5.02.03.51.0
5.93.04.21.5
6.02.24.01.0
6.12.94.71.4
5.62.93.61.3
6.73.14.41.4
5.63.04.51.5
5.82.74.11.0
6.22.24.51.5
5.62.53.91.1
5.93.24.81.8
6.12.84.01.3
6.32.54.91.5
6.12.84.71.2
6.42.94.31.3
6.63.04.41.4
6.82.84.81.4
6.73.05.01.7
6.02.94.51.5
5.72.63.51.0
5.52.43.81.1
5.52.43.71.0
5.82.73.91.2
6.02.75.11.6
5.43.04.51.5
6.03.44.51.6
6.73.14.71.5
6.32.34.41.3
5.63.04.11.3
5.52.54.01.3
5.52.64.41.2
6.13.04.61.4
5.82.64.01.2
5.02.33.31.0
5.62.74.21.3
5.73.04.21.2
5.72.94.21.3
6.22.94.31.3
5.12.53.01.1
5.72.84.11.3
6.33.36.02.5
5.82.75.11.9
7.13.05.92.1
6.32.95.61.8
6.53.05.82.2
7.63.06.62.1
4.92.54.51.7
7.32.96.31.8
6.72.55.81.8
7.23.66.12.5
6.53.25.12.0
6.42.75.31.9
6.83.0
升级会员 