《蚁群算法原理介绍.pptx》由会员分享，可在线阅读，更多相关《蚁群算法原理介绍.pptx（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1蚁群算法原理介绍蚁群算法原理介绍大 纲蚁群算法的起源蚁群行为描述蚁群算法的基本思想基本蚁群算法的系统学特征TSP问题描述基本蚁群算法的数学模型基本蚁群算法的应用举例总结第1页/共30页蚁群算法起源蚁群算法起源蚁群算法蚁群算法(ant colony optimization,ACO)：Dorigo M于于1991年提出，其灵感来源于蚂蚁年提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。在寻找食物过程中发现路径的行为。通过模拟通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法。的模拟进化算法。TSP问题、分配问题、问题、分配问题、j
2、ob-shop调度问题调度问题第2页/共30页蚁群行为描述蚁群行为描述CBEF3030AD蚁蚁穴穴食食物物源源d=1d=1d=0.5d=0.5ADCBEF303015151515释放信息素与路径长度成反比释放信息素与路径长度成反比第3页/共30页蚁群行为描述蚁群行为描述ADCBEF303010102020ADCBEF30303030信息量大，路径被选概率大信息量大，路径被选概率大第4页/共30页基本蚁群算法的机制原理基本蚁群算法的机制原理ADCBEF303015151515ADCBEF30303030路径路径BFC：蚂蚁增加，信息量增加，路径被选择的机率增加；：蚂蚁增加，信息量增加，路径被选择
3、的机率增加；路径路径BEC：时间增加，：时间增加，信息量减少，路径被选择的机率减小。信息量减少，路径被选择的机率减小。第5页/共30页基本蚁群算法的系统学特征基本蚁群算法的系统学特征蚁群算法是一个系统蚁群算法是一个系统分布式计算分布式计算自组织自组织正反馈正反馈第6页/共30页蚁群算法是一个系统蚁群算法是一个系统Bertalanffy L VBertalanffy L V：系统可以确定为处于一定的相互关系中并系统可以确定为处于一定的相互关系中并系统可以确定为处于一定的相互关系中并系统可以确定为处于一定的相互关系中并与环境发生关系的各组成部分（要素）的综与环境发生关系的各组成部分（要素）的综与环
4、境发生关系的各组成部分（要素）的综与环境发生关系的各组成部分（要素）的综合体。合体。合体。合体。多元性多元性 整体性整体性 相关性相关性 系统特征系统特征蚂蚁的个体行为是系统的元素蚂蚁的个体行为是系统的元素蚁群行为的相互影响蚁群行为的相互影响蚁群能完成个体完蚁群能完成个体完成不了的任务成不了的任务整体大于部分之和整体大于部分之和第7页/共30页蚁群算法满足分布式计算蚁群算法满足分布式计算分布式系统：依赖于个体行为，但并不单独依赖于分布式系统：依赖于个体行为，但并不单独依赖于分布式系统：依赖于个体行为，但并不单独依赖于分布式系统：依赖于个体行为，但并不单独依赖于每一个体的行为。每一个体的行为。每
5、一个体的行为。每一个体的行为。在蚁群中，许多蚂蚁都为共同目的进行着同样的工在蚁群中，许多蚂蚁都为共同目的进行着同样的工在蚁群中，许多蚂蚁都为共同目的进行着同样的工在蚁群中，许多蚂蚁都为共同目的进行着同样的工作，而最终任务的完成不会由于某些个体（蚂蚁）作，而最终任务的完成不会由于某些个体（蚂蚁）作，而最终任务的完成不会由于某些个体（蚂蚁）作，而最终任务的完成不会由于某些个体（蚂蚁）的缺陷而受到影响。的缺陷而受到影响。的缺陷而受到影响。的缺陷而受到影响。第8页/共30页蚁群算法具有自组织的特征蚁群算法具有自组织的特征系统外部系统外部系统内部系统内部组织行为组织行为他组织他组织自组织自组织自组织：在
6、没有外界作用自组织：在没有外界作用下使得系统熵增加的组织下使得系统熵增加的组织无序无序有序有序第9页/共30页蚁群算法具有正反馈的特征蚁群算法具有正反馈的特征削弱未来行为削弱未来行为加强未来行为加强未来行为反馈反馈负反馈负反馈正反馈正反馈在蚁群中，在蚁群中，信息素的堆积信息素的堆积就是一个正反馈就是一个正反馈第10页/共30页自组织是正反馈和负反馈的结合自组织是正反馈和负反馈的结合自组织自组织负反馈负反馈正反馈正反馈缩小搜索范围缩小搜索范围保持搜索范围保持搜索范围第11页/共30页TSP描述描述TSPTSP问题（问题（问题（问题（Traveling Salesman ProblemTravel
7、ing Salesman Problem）：）：）：）：即旅行商问题，是数学领域中著名问题之一。假设即旅行商问题，是数学领域中著名问题之一。假设即旅行商问题，是数学领域中著名问题之一。假设即旅行商问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访有一个旅行商人要拜访有一个旅行商人要拜访有一个旅行商人要拜访NN个城市，他必须选择所要个城市，他必须选择所要个城市，他必须选择所要个城市，他必须选择所要走的路径，路径的限制是走的路径，路径的限制是走的路径，路径的限制是走的路径，路径的限制是每个城市只能拜访一次，每个城市只能拜访一次，每个城市只能拜访一次，每个城市只能拜访一次，而且最后要回到原来出
8、发的城市而且最后要回到原来出发的城市而且最后要回到原来出发的城市而且最后要回到原来出发的城市。路径的选择目标。路径的选择目标。路径的选择目标。路径的选择目标是要求得的路径路程为所有路径之中的是要求得的路径路程为所有路径之中的是要求得的路径路程为所有路径之中的是要求得的路径路程为所有路径之中的最小值最小值最小值最小值。第12页/共30页ATSP的目的的目的Hamilton圈圈第13页/共30页TSP数学语言描述数学语言描述有向图：有向图：给定一个有向图给定一个有向图 的三元组为的三元组为 ，其中，其中 是一个非空集合，其元素是一个非空集合，其元素称为有向图的结点称为有向图的结点；是一个集合，是一
9、个集合，其元素称为有向图的弧段，其元素称为有向图的弧段，是从是从 到到 上的一个映射（函数）上的一个映射（函数）一个一个 有向图有向图 ，可简记为，可简记为 第14页/共30页TSP描述描述TSP：设设 是是 个城市个城市的集合，的集合，是集合是集合 中元中元素两两连素两两连接的集合，接的集合，是是 的的Euclidean距离，即距离，即第15页/共30页C1C2C3CnLij第16页/共30页基本蚁群算法的数学模型基本蚁群算法的数学模型 ：TSP的规模的规模 ：蚁群中蚂蚁总数目，：蚁群中蚂蚁总数目，：次循环次循环 上的残留信息量上的残留信息量的集合的集合 ：禁忌表：禁忌表 ：状态转移概率：状
10、态转移概率 ：在初始时刻各条路径：在初始时刻各条路径上的信息上的信息量相等量相等第17页/共30页基本蚁群算法的数学模型基本蚁群算法的数学模型第18页/共30页基本蚁群算法的数学模型基本蚁群算法的数学模型 ：挥发系数：挥发系数 ：信息素残留因子：信息素残留因子第19页/共30页信息素更新策略信息素更新策略第20页/共30页YesNo输输出出程程序序计计算算结结果果结结束束按按照照公公式式进进行行信信息息素素更更新新满满足足结结束束条条件件？蚂蚂蚁蚁k=k+1开开始始初初始始化化迭迭代代次次数数N=N+1 蚂蚂蚁蚁k=1按按照照状状态态转转移移概概率率公公式式选选择择下下一一个个城城市市修修改改
11、禁禁忌忌表表蚂蚂蚁蚁总总数数？NoYes蚂蚁第21页/共30页图的蚁群系统（图的蚁群系统（图的蚁群系统（图的蚁群系统（GBASGBAS）可以验证，下式满足：即 是一个随机矩阵。四个城市的非对称TSP问题，距离矩阵和城市图示如下：第22页/共30页2.2.5 2.2.5 初始的蚁群优化算法初始的蚁群优化算法初始的蚁群优化算法初始的蚁群优化算法基于图的蚁群系基于图的蚁群系基于图的蚁群系基于图的蚁群系统（统（统（统（GBASGBAS）假设共4只蚂蚁，所有蚂蚁都从城市A出发，挥发因子 。此时，观察GBAS的计算过程。矩阵共有12条弧，初始信息素记忆矩阵为：第23页/共30页2.2.5 2.2.5 初始
12、的蚁群优化算法初始的蚁群优化算法初始的蚁群优化算法初始的蚁群优化算法基于图的蚁群基于图的蚁群基于图的蚁群基于图的蚁群系统（系统（系统（系统（GBASGBAS）执行GBAS算法的步骤2，假设蚂蚁的行走路线分别为：当前最优解为，这个解是截止到当前的最优解，碰巧是实际最优解第24页/共30页2.2.5 2.2.5 初始的蚁群优化算法初始的蚁群优化算法初始的蚁群优化算法初始的蚁群优化算法基于图的蚁群基于图的蚁群基于图的蚁群基于图的蚁群系统（系统（系统（系统（GBASGBAS）按算法步骤3的信息素更新规则，得到更新矩阵这是第一次外循环结束的状态。第25页/共30页2.2.5 2.2.5 初始的蚁群优化算
13、法初始的蚁群优化算法初始的蚁群优化算法初始的蚁群优化算法基于图的蚁群系基于图的蚁群系基于图的蚁群系基于图的蚁群系统（统（统（统（GBASGBAS）重复外循环，由于上一次得到的W2已经是全局最优解，因此按算法步骤3的信息素更新规则，无论蚂蚁如何行走，都只是对W2路线上的城市信息素进行增强，其他的城市信息素进行挥发。得到更新矩阵这是第一次外循环结束的状态。第26页/共30页2.2.5 2.2.5 初始的蚁群优化算法初始的蚁群优化算法初始的蚁群优化算法初始的蚁群优化算法基于图的蚁群系统基于图的蚁群系统基于图的蚁群系统基于图的蚁群系统（GBASGBAS）重复外循环，由于W2全局最优解，GBAS只记录第
14、一个最优解，因此一但得到了全局最优解，信息素的更新将不再依赖于以群的行走路线，而只是不断增强最优路线的信息素，同时进行挥发。第三次外循环后得到的信息素矩阵为：第27页/共30页2.2.5 2.2.5 初始的蚁群优化算法初始的蚁群优化算法初始的蚁群优化算法初始的蚁群优化算法基于图的蚁群系统基于图的蚁群系统基于图的蚁群系统基于图的蚁群系统（GBASGBAS）蚂蚁以一定的概率从城市i到城市j进行转移，信息素的更新在STEP 3 完成，并随K而变化。假设第K次外循环后得到信息素矩阵 ，得到当前最优解 。第K次循环前的信息素和最优解为 ，经过第K次外循环后，得到 。由于蚂蚁的一步转移概率是随机的，从 到 也是随机的，是一个马尔可夫过程。第28页/共30页第29页/共30页