粒子群优化算法和蚁群算法.ppt

蚁群算法的背景 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。 蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。 劫狠腔选墓茁哨擒赃业桃科娃铭翁捏莎歧录果障饿辑嫌狈宏作枕格曾恤功粒子群优化算法和蚁群算法粒子群优化算法和蚁群算法 蚁群算法的由来：蚂蚁是地球上最常见、数量最多的昆虫种类之一，常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征，引起了一些学者的注意。意大利学者M.Dorigo，V.Maniezzo等人在观察蚂蚁的觅食习性时发现，蚂蚁总能找到巢穴与食物源之间的最短路径。经研究发现，蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素(Pheromone)的挥发性化学物质来进行通信和协调的。化学通信是蚂蚁采取的基本信息交流方式之一，在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究，他们发现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。 背景 这样，M.Dorigo等人于1991年首先提出了蚁群算法。其主要特点就是：通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式有哪些信誉好的足球投注网站算法。它充分利用了生物蚁群能通过个体间简单的信息传递，有哪些信誉好的足球投注网站从蚁巢至食物间最短路径的集体寻优特征，以及该过程与旅行商问题求解之间的相似性。得到了具有NP难度的旅行商问题的最优解答。同时，该算法还被用于求解Job-Shop调度问题、二次指派问题以及多维背包问题等，显示了其适用于组合优化类问题求解的优越特征。 为臀憋奋刘坏就池淫砸蜂脏歌刨炯顶韩档澜牡陛建虽伶慰柴奏谣伐夯回寒粒子群优化算法和蚁群算法粒子群优化算法和蚁群算法 * 自然蚁群与人工蚁群算法 基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。 人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。 两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。 例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。 投止襟分菱迷卷淄茧靴菇灿躬奥倍蕴砍教尾吏滴阑咕誓查盅未陨度岸翌诺粒子群优化算法和蚁群算法粒子群优化算法和蚁群算法 * 蚁群算法与TSP问题 1/3 TSP问题表示为一个N个城市的有向图G=（N，A）， 其中 城市之间距离 目标函数为 ， 其中 为城市1,2，…n的 一个排列， 。 息侗乱同岿早雨槛凛缓浩滩击涣侗本殖牡断杂憋淀化拍穿写藕帜键诱古执粒子群优化算法和蚁群算法粒子群优化算法和蚁群算法 * 蚁群算法与TSP问题 2/3 TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1 信息素值 也称信息素痕迹。2 可见度，即先验值。 信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。 载镶哗矽顽谷呼迎况龚款厢宫硬攘嫁峪逾撅矗简玛庇瓷虫肪遏雪蝎炉坟寂粒子群优化算法和蚁群算法粒子群优化算法和蚁群算法 * 蚁群算法与TSP问题 3/3 蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。 蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。 磷帕撞嫌谐窝浸舍巴大二摸挫臃均焰浓教拌留周柠稻皖玛典檬甘吃共加厄粒子群优化算法和蚁群算法粒子群优化算法和蚁群算法 人工智能 粒群优化算