《蚁群算法赵岩》PPT课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,软件工程（外包）,赵岩,蚁群算法,蚁群算法的研究概况,蚁群算法的基本原理,蚁群算法的优缺点,蚁群算法的应用范围,算例（TSP）,蚁群算法,蚁群算法的研究概况,蚁群算法的基本原理,蚁群算法的优缺点,蚁群算法的应用范围,算例（TSP）,蚁群算法简史,蚁群算法是一种由自然界真实蚂蚁觅食行为提炼而成的优化算法，于1991年，由意大利学者M.Dorigo在其博士论文中提出，并成功的解决了旅行商(TSP)问题。,1996年，Dorigo M等人在IEEE Transactions on Systems,Man,and Cybernetics-Part B上发表了“Ant system:optimization by a colony of cooperating agents”一文，系统地阐述了蚁群算法的基本原理和数学模型，蚁群算法逐渐引起了世界许多国家研究者的关注，其应用领域也得到了迅速拓宽。,1998年10月在比利时布鲁塞尔召开了第一届蚁群算法国际研讨会(ANTS)，标志着蚁群算法的正式国际化。,2000年，MDorigo和Bonabeau E等人在国际顶级学术刊物Nature上发表了蚁群算法的研究综述，从而把这一领域的研究推向了国际数学的最前沿。,而在我国，最早关于蚁群算法的研究见于，1997年10月张纪会与徐心和发表的“一种新的进化算法蚁群算法”论文。,蚁群算法的研究现状,目前，蚁群算法己经成为一个备受关注的研究热点和前沿性课题。人们对蚁群算法的研究已经由当初的TSP领域渗透到多个应用领域，由解决,一维静态,优化问题发展到解决,多维动态,组合优化问题，由,离散域,范围内研究逐渐拓展到了,连续域,范围内研究。同时在蚁群算法的模型改进以及,其他仿生优化算法的融合,方面也取得了相当丰富的研究成果，从而使这种新兴的仿生优化算法展现出前所未有的生机。,蚁群算法,蚁群算法的研究概况,蚁群算法的基本原理,蚁群算法的优缺点,蚁群算法的应用范围,算例（TSP）,蚂蚁觅食原理：,自然界中，蚂蚁这种视盲生物，在没有任何先知经验的情况下总能找到从其巢穴到食物源的最佳路径，甚至在该路径上放置障碍物之后，它们仍然能很快重新找到新的最佳路线。,这是因为在蚂蚁个体之间是通过一种称为,信息素,的物质进行信息传递的。蚂蚁在运动过程中，不但能够在它所经过的路径上,留下,该物质，而且能够,感知,这种物质的存在及其强度，并朝着该物质,强度高,的方向移动，为此指导自己的运动方向。因此，由大量蚂蚁组成的蚁群集体行为表现出一种信息正反馈现象。在一定时间内较短路径通过的蚂蚁要,多于,较长路径，而某一路径上走过的蚂蚁越多，则后来的蚂蚁选择该路径的,概率,就越大。,t=0,20只蚂蚁出发；t=1，路径1、2各10只蚂蚁；t=4，到达食物源；t=5，相遇，路径1、2各5只；t=8，前5只到达巢穴；t=9是前5只蚂蚁面再次临选择，此时AB轨迹数20，AC轨迹数15。,人工蚂蚁的特性,共同目标总是寻找最小费用的可行解，,人工蚂蚁可以释放和识别“信息素”，,“信息素”会随着时间蒸发、衰减，,人工蚂蚁具有,记忆,，用来储存当前路径的信息，,当前蚂蚁可以转移至可行领域中的任一点，,蚂蚁按某种概率决策规则移至领域节点，,人工蚂蚁处理,离散,状态。,蚁群算法的基本步骤,蚁群算法的系统学特征,系统性:,整体大于部分之和,分布式计算:,强适应能力，依赖于个体行为，但不单独依赖于与个体行为，体现了容错能力（行为的冗余）,自组织性:,仿生算法共有的特性，由此具有鲁棒性，（组织力或组织指令来源于系统内部还是外部）,正反馈性:,信息素累计，算法演化过程得以进行的基础，也造成了初值敏感性和群体迷失现象。,蚁群算法,蚁群算法的研究概况,蚁群算法的基本原理,蚁群算法的优缺点,蚁群算法的应用范围,算例（TSP）,蚁群算法的优点,不依赖于所求问题的具体数学表达式描述，具有很强的找到全局最优解的优化能力。,该算法具有正反馈、较强的鲁棒性、全局性、普遍性、优良的分布式并行计算机制、易于与其他方法相结合等诸多优点。,蚁群算法的缺点：,蚁群算法的成功主要在实验层次上，很少有理论来解释利用蚁群算法为什么能够成功地解决这些问题，它没有坚实的数学基础；,蚁群算法的模型普适性不强，其模型不能直接应用于实际优化问题；,蚁群算法的局部搜索能力较弱，易于出现停滞和局部收敛、收敛速度慢等问题，因而往往需要嵌入一些专门的辅助技巧；,长时间花费在解的构造上，从而导致搜索时间过长，,算法最先基于离散问题，不能直接解决连续优化问题。,蚁群算法,蚁群算法的研究概况,蚁群算法的基本原理,蚁群算法的优缺点,蚁群算法的应用范围,算例（TSP）,蚁群算法的应用领域,由于蚁群算法对,图的对称性,以及,目标函数,无特殊要求，因此，可以解决各种对称、非对称问题，线性非线性问题。其本质是,图上寻优,，蚁群算法已经成功地运用于求解,旅行商,（TSP）,问题,、,调度问题,、,图形着色、机器人路径规划,、,数据挖掘,、,聚类分析、机器学习与推理,、,网络路由,、,无线网络配置,、,频率分配,、,数字滤波,、,二次分配,、,序列求序,、,武器-目标配置,及各种组合优化问题，并取得了较好的结果；广泛应用于,电力,、,通信,、,化工,、,交通,、,机器人,、,冶金,等多个领域中。,蚁群算法,蚁群算法的研究概况,蚁群算法的基本原理,蚁群算法的优缺点,蚁群算法的应用范围,算例（TSP）,算例,(TSP),旅行商问题（TSP）:给定n个城市和两个两个城市之间的距离，要求确定一条经过各个城市一次当且仅当一次的最短路径。即要求确定一条长度最短Haimilton回路。,第一步、初始化（蚁周算法）,将m只蚂蚁随机放到n个城市，每只蚂蚁的禁忌表为蚂蚁当前所在城市，各边信息初始化为c。,禁忌表体现了人工蚂蚁的记忆性，使得蚂蚁不会走重复道路，提高了效率。,第二步、构造路径,在t时刻，蚂蚁k从城市i转移到城市j的概率为：,为边（i，j）的轨迹强度，,为边（i，j）的能见度，为 ，,轨迹的相对重要程度，（0,5）,能见度的相对重要程度（1,5）。,第三步、更新信息,在所有蚂蚁找到一条合法路径后对信息进行更新。,（0 1）表示边上信息素的蒸发系数（0.1，0.9），0.7最优。,1-表示信息素的持久性系数，,表示第k只蚂蚁在本次迭代中留在边(i,j)上的信息素,Q表示蚂蚁所留轨迹为正常数（10,10000），,L,k,表示第k只蚂蚁在本次周游中所走过的路径的长度和。,第四步、输出结果,若迭代次数小于预定的迭代次数且无退化行为（找到的都是相同的解）则转步骤二，,否则，输出目前的最优解。,实现过程,