蚁群优化算法ppt课件

1、2021-10-26;.蚁群优化算法概述12021-10-26;.内容基本概念及原理基本概念及原理1 数学模型与算法流程数学模型与算法流程2研究现状及进展研究现状及进展3 算法优缺点及应用算法优缺点及应用422021-10-26;.基本概念o蚁群优化算法（Ant Colony Optimization,ACO）是一种针对难解的离散优化问题的元启发式算法，利用一群人工蚂蚁的协作来寻找好的解。既适用于静态组合优化问题，又适用于动态组合优化问题。前者如旅行商问题（TSP），后者如通讯领域的路由问题等。o启发式算法（Heuristic Algorithm）在可接受的花费（指时间和空间）下给出待解决组合

2、优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定能事先预计，也不能保证每次能用相同的时间求出结果。32021-10-26;.有趣的问题o1.为何大多数蚂蚁在觅食时，会选择相同的路径，而且这条路径往往是一条食物和巢穴之间的最短路径，它们是如何做到的？o2.当原来最优路径上出现了障碍物或者食物位置改变了；蚁群仍能够重新探索出新的一条最优路径？42021-10-26;.蚁群行为描述o仿生学家经过长期研究发现：蚂蚁虽然没有视觉，但是存在一种化学物质信息素（pheromone）用于蚂蚁之间以及蚂蚁与环境的交互。o在没有信息素的情况下，蚂蚁是随机挑选路径的，同时释放出与路径有关的信息素。路

3、径越长，信息素量越小。如果当前路径上存在信息素，蚂蚁倾向于信息素浓度高的路径。由于较短路径上，蚂蚁往返的时间短，单位时间内经过的蚂蚁数多，信息素累计的也多，因此会吸引更多的蚂蚁。信息素还会随着时间蒸发，其他路径上的信息素浓度下降，最终绝大多数的蚂蚁将沿着最优路径前行。52021-10-26;.蚂蚁行为图解图1 蚁群觅食行为图62021-10-26;.蚁群优化算法起源蚁群觅食现象蚁群优化算法蚁群种群(求解主体)规模m觅食空间问题的搜索空间n信息素信息素浓度变量蚁穴到食物的路径一个有效解最短路径问题的最优解表1 蚁群觅食现象和蚁群优化算法定义对照表72021-10-26;.蚁群优化算法机制原理蚁群

4、优化的本质在于：选择机制：信息素越多的路径，被选择的概率越大。更新机制：路径上面的信息素会随蚂蚁的经过而增长，同 时也随时间的推移逐渐挥发消失。协调机制：蚂蚁间通过环境中的信息素来协同工作。蚁群算法的寻优包含两个基本过程：蚂蚁构建解（ConstructAntSolution） 通过使一群蚂蚁并行异步访问邻近点，逐步建立优化问题的解。更新信息素（UpdatePheromones）依据蚂蚁所构建的解修改空间内的信息素浓度。82021-10-26;.蚂蚁系统解决TSP问题o蚂蚁系统（Ant System）作为第一个ACO算法，是以NP-hard的TSP问题作为应用实例而提出的。虽然它的算法性能不及其

5、他各种扩展算法，但是最基本的ACO算法，易于学习和掌握。o旅行商问题一位商人从自家出发，希望能找到一条最短路径，途径给定集合的所有城市最后返回家乡，并且每个城市都被访问且仅访问一次。形式上，TSP问题可以用一个带权完全图G=（N,A）来描述，目标就是寻找一条具有最小成本值的哈密尔顿回路。92021-10-26;.TSP问题数学描述设 是n个城市的集合， 是集合C中元素两两连接的集合， 是 的距离，对任意i，j有称为对称旅行商问题，若存在某组i，j之间的则称为非对称旅行商问题。目标函数表示为对于n个城市规模的TSP，存在 条不同的闭合路径，当n较大时很难精确求解每个解再寻找最优。 c,.,c,c

6、Cn21 Cc,c|lLjiij),.,2 , 1,(njidijijljiijdd jiijdd min)()1()()1(i)(11niddfni2)!1(n102021-10-26;.蚂蚁系统数学模型（一）设n表示TSP规模，i和j是集合C中的两个元素， m为蚁群蚂蚁总数， 表示t时刻位于i的蚂蚁数目，则设 为t时刻路径(i,j)上的信息素量， 是t时刻集合C中所有信息素的集合。初始时刻，各条路径上的信息量是相同的。)(tbiniitbm1)()(tij,| )(Ccctjiij112021-10-26;.蚂蚁系统数学模型（二）蚂蚁 在运动过程中有三个因素决定其转移方向信息素量 ，启发式

7、信息 和禁忌表 为启发函数，其表达式一般表示为 ；禁忌表 用于记录蚂蚁k当前走过的城市， 表示蚂蚁k下步允许选择的城市。),.,2 , 1(mkk)(tij)(tijktabuijijdt1)()(tijktabukktabuCallowed122021-10-26;.蚂蚁系统数学模型（三） 表示蚂蚁k在t时刻由i转到j的概率上式中，为信息素因子， 为启发式因子，用于控制信息素浓度和启发式信息作用的权重关系。值越大表示重要性越大，当=0，算法演变为传统的随机贪心算法，当=0，蚂蚁仅依据信息素决策，算法将快速收敛，可能获得局部最优。)(tpkijotherwiseallowedjiftttttp

8、kallowedsisisijijkijkk,0,)()()()()(132021-10-26;.蚂蚁系统数学模型（四）信息素更新公式 1. 原有信息素的挥发 通常的做法是设置信息持久率让所有 乘以 。在算法中用于避免信息素的无限增长淹没启发式信息，也有助于丢弃那些构建过的较差的路径。2. 新生信息素的释放 AS算法曾有过三种信息素释放策略Ant-Density模型： 若蚂蚁k在t到t+1之间经过(i,j) Ant-Quantity模型： 若蚂蚁k在t到t+1之间经过(i,j) Ant-Cycle模型： 若蚂蚁k在本次循环中经过(i,j) 10()(tijQkijmkkijijijijijtn

9、t1;)()(ijkijdQkkijLQ142021-10-26;.蚂蚁系统解决TSP步骤初始化随机放置蚂蚁，为每只蚂蚁建立禁忌表，迭代过程k=1while k=Count do (执行迭代)for i = 1 to m do (对m只蚂蚁循环) for j = 1 to n - 1 do (对n个城市循环) 根据蚂蚁行动原则 选择下一个城市j并将j置入禁忌表, end for end for 计算每只蚂蚁的路径长度 依据信息素更新方法更新所有路径上的信息量; k = k + 1;end while输出结果,结束算法.152021-10-26;.蚂蚁系统解决TSP算法流程162021-10-2

10、6;.算法复杂度分析步骤步骤内容内容时间复杂度时间复杂度1初始化参数2设置禁忌表3每只蚂蚁构造解4解的评价5信息素浓度更新6判断终止条件7输出结果2()O nm()O m2()O n m2()O n m2()O n()O mn(1)O空间复杂度：2( )()()S nO nO n m172021-10-26;.研究现状oAS是第一个ACO算法由Dorigo等人于1991年在第一届欧洲人工生命会议上提出。o1996年，Dorigo发表Ant system:optimization by a colony of cooperation agents,成为里程碑。o随后，精英蚂蚁系统、最大最小蚂蚁系

11、统和基于排列的蚂蚁系统大多在AS上直接改进。o1997年，Dorigo提出了大幅改动AS特征的算法蚁群系统(Ant Colony System，ACS)性能明显优于AS。o21世纪出现了连续蚁群算法，能够优化连续空间问题。182021-10-26;.精英蚂蚁系统o精英蚂蚁系统（EAS）是最早的改进蚂蚁系统。o遗传算法中的精英策略n传统的遗传算法可能会导致最适应个体的遗传信息丢失n精英策略的思想是保留住一代中的最适应个体o蚂蚁系统中的精英策略n每次循环之后给予最优解以额外的信息素量n这样的解被称为全局最优解（global-best solution）n找出这个解的蚂蚁被称为精英蚂蚁(elitis

12、t ants)192021-10-26;.精英蚂蚁系统o信息素根据下式进行更新*(1)( )ijijijijtt*,0,ijQL如果边(i,j)是所找出的最优解的一部分否则o 是精英蚂蚁的个数 是所找出的最优解的路径长度精英蚂蚁系统特点：更高的求解精度，更快的求解速度，但精英蚂蚁设置太多会加速早熟。*L202021-10-26;.基于排列的蚂蚁系统o基于排列蚂蚁系统(ASrank)由Bullnheimer于1997年提出。o基本思想与EAS类似，具体做法是在每一轮所有蚂蚁构建完路径后，将各自所得的路径进行排名，只有生成了至今最优路径的蚂蚁以及排名在前(-1)的蚂蚁才允许释放信息素。o最优蚂蚁释

13、放 的信息素量，在本次迭代中排名 的蚂蚁将释放 的信息素。一般设置=6。bL/) 1,.,2 , 1(kkkLk / )(212021-10-26;.最大最小蚂蚁系统o前两种改进算法将蚂蚁的搜索行为偏向当前最优解虽然提高解的质量和收敛速度，进而改进算法的性能。但这种搜索方式无法避免早熟收敛问题。o最大-最小蚂蚁系统(Max-Min Ant System, MMAS)于1997年由Sttzle提出。这种算法将之前的搜索方式和一种能够有效避免早熟收敛的机制结合在一起，从而使其获得更好的全局搜索能力。222021-10-26;.最大最小蚂蚁系统MMAS和AS主要有四个方面不同：n在每次循环之后，只有

14、一只蚂蚁进行信息素更新。这只蚂蚁可能是找出当前循环中最优解的蚂蚁，也可能是找出从实验开始以来最优解的蚂蚁n在每个解的元素上的的信息素量被限制在范围区间内n信息素初始值为信息素取值范围的上限 ，信息维持率保持一个较大值。n当系统陷入停滞，将问题空间所有边的信息素重新初始化。maxminmax,232021-10-26;.最大最小蚂蚁系统o改进1借鉴了EAS，但有不同。使用至今最优的蚂蚁释放可加快收敛，当前迭代最优可增强探索，应该交替使用，逐渐增大至今最优蚂蚁的使用概率。o改进2通过给信息素设定上界目的是避免信息素增长过快，淹没了启发式信息的影响。启发式信息在每次迭代中是无法增长的。o改进3设置较

15、大的信息素维持度（一般设置为0.98）可以保证初始阶段的探索能力。o改进4可以利用停滞后的迭代周期继续进行搜索。242021-10-26;.蚁群系统o蚁群系统(Ant Colony System, ACS)是由Dorigo和Gambardella在1997年提出的。o蚁群系统做了三个方面的改进：n使用一种伪随机比例规则选择下一元素j，利用了先验知识。n信息素全局更新规则将只应用于至今最优蚂蚁路径。n新增信息素局部信息素更新规则。252021-10-26;.蚁群系统状态转移规则一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市J0arg max ,kililj allowedq

16、qjJ如果否则是一个0,1区间的参数， 是一个0,1区间的随机数，当 蚂蚁选择开发当前最优路径；当 蚂蚁进行偏向选择，探索其他区域通过调节 值可以平衡开发和探索的关系。0q0qq0qq0qq262021-10-26;.蚁群系统全局更新规则只有一只至今最优的蚂蚁（大规模问题性能更优）才被允许释放信息素每轮迭代中，所有蚂蚁构建完路径后，信息素全局更新规则才被使用。更新公式如下所示：( , )( , )(1)( , ),( , )gbi ji ji ji jT 1,( , )0,gbLi j如果(i,j) 全局最优路径否则本公式用一种隐含的方式对信息素上界进行了限制。272021-10-26;.蚁群

17、系统局部更新规则每只蚂蚁应用下列局部更新规则对它们所经过的边进行信息素更新：0( , )( , )(1)i ji j 01nnn L实验发现， 可以产生好的结果，其中n是城市的数量， 是由最近的邻域启发产生的路径长度nnL局部更新规则作用于某条边会使这条边被其他蚂蚁选择的概率减少，可以有效地避免蚂蚁收敛到同一路径。 是信息素局部维持率， 是信息素初始值0282021-10-26;.蚁群优化算法优缺点o蚁群优化算法有如下优点：l是具有自学习能力，可以对自身知识库或自身的组织结构进行再组织，实现算法能力的进化l采用正反馈机制，能加快搜索l采用分布式并行计算多点同时独立搜索易于找到全局最优 l易于和

18、其他方法结合 l有较强的鲁棒性o蚁群优化算法有如下缺点：l要么搜索时间长要么易陷入局部最优，很难保持平衡。l算法机理的复杂和环境的变化会增加蚁群算法的不确定性292021-10-26;.蚁群优化算法的应用基于算法的诸多优点，蚁群优化已被成功地应用于二次分配问题(quadratic assignment problem, QAP) ,作业调度问题(job-scheduling problem, JSP),图表着色问题(graph coloring problem, GCP),车辆路径问题(Vehicle Routing Problem,VRP),通信网络的路由优化(network route,NR)等另外也为数据挖掘、图像处理、系统识别等问题提供了有效且高效的解决手段。302021-10-26;.蚁群优化算法参数设置（一）参数参数参数意义参数意义参数经验值参数经验值蚂蚁数目m影响算法搜索能力与计算量，数目多，计算量大，收敛慢数目少，探索能力降低，早熟AS,EAS,MMASm=nACS，m=10信息素权重启发信息权重决定算法的搜索导向 越小，偏向于眼前利益 越小，偏向于信息素浓度各类ACO算法信息素维持因子影响蚂蚁个体间的相互影响强弱 大，较高全局搜索，收敛慢 小，信息素