第6章群体智能(及蚁群算法)讲义

《第6章群体智能(及蚁群算法)讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.1SwarmIntelligenceSwarmIntelligenceSwarmIntelligenceWhydoanimalsswarm?DefenseagainstpredatorsEnhancedpredatordetectionMinimizingchanceofcaptureEnhancedforagingsuccessBetterchancestofindamateDecreaseofenergyconsumptionSwarmIntelligenceSwarmIntelligenceAntColonyNestExamplesCemete

2、ryOrganizationandBroodSortingSwarmIntelligenceSwarmIntelligenceSwarmIntelligenceSwarmIntelligenceSwarmIntelligenceSwarmIntelligenceSwarmIntelligenceSwarmIntelligenceSwarmIntelligenceSwarmIntelligenceSwarmIntelligenceSwarmIntelligenceSwarmIntelligence6.2蚁群算法AntColonyAlgorithms真实世

3、界的蚂蚁行为蚁群算法（AntAlgorithms）蚂蚁几乎是没有视力的，它们是如何找到食物和家之间的路径的？在觅食过程中,蚂蚁在它所经过的路径上留下浓度与食物源质量成比例的信息素(pheromone),并能够感知信息素的存在及其浓度,以此指导自己的运动方向,倾向于朝着信息素浓度高的方向移动.蚁群算法（AntAlgorithms）于是,蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大,因此质量好、距离近的食物源会吸引越来越多的蚂蚁,信息素浓度的增长速度会更快.蚂蚁个体之间就是通过这种信息的交流达到寻找食物和

4、蚁穴之间最短路径的目的2021/10/5292.2.2简化的蚂蚁寻食过程蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。2021/10/530本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。2021/10/531假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不

5、同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD

6、路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。蚁群算法（AntAlgorithms）我们感兴趣的是对解空间的探索，而非简单的数路径；应允许蚂蚁们以概率的方式选择路径以及确定最佳路径，概率与信息素的浓度成比例。不希望蚂蚁们简单地根据最高浓度来选择路径，如果这样的话，搜索会迅速地陷入局部最优。一个蚂蚁选择一个确定路径的概率，不仅取决于信息素浓度，同时也取决于该蚂蚁所看到的信息。信息素的痕迹不能无限增加，因此，需要引入“挥发”机制。蚁群算法（AntAlgorithms）由此获得灵感而设计出的算法称蚁群算法antalgorithms(或蚁群系统ant

7、systems)蚁群算法（系统）是一种基于群体策略的搜索方法。蚁群算法（AntAlgorithms）蚁群算法可以用于解决许多组合优化问题,只要：能做到用一个图来阐述将要解决的问题；能定义一种正反馈过程(如TSP问题中的残留信息)；问题结构本身能提供解题用的启发式信息(如TSP问题中城市间的距离),约束机制的建立(如TSP问题中已访问城市的列表)。2021/10/5356.2.1蚁群优化算法概述起源应用领域研究背景2021/10/536蚁群优化算法起源20世纪90年代意大利学者M．Dorigo，V．Maniezzo，A．Colorni等从生物进化的机制中受

8、到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法——蚁群算