蚁群优化算法PPT.ppt

蚁群优化算法AntColonyOptimization*算法介绍群智能算法群智能是一种由简单智能的个体通过某种形式的聚集协同而表现出智能行为。它在没有集中控制,不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础。群智能算法通过模仿生物界的进化机理和群体协作行为而提出的仿生类随机搜索算法。去人工蜂群算法细菌觅食算法萤火虫算法粒子群算法人工鱼群算法鸟群算法*蚁群算法的提出GambardellaMacroDorigo*蚁群算法的发展2001年至今1996年-2001年意大利学者Dorigo1991年Dorigo1991年启发各种改进算法的提出,应用领域更广引起学者关注,在应用领域得到拓宽ACO首次被系统的提出自然界中真实蚁群集体行为*蚁群算法原理如何找到最短路径?类比:大肠杆菌在人体肠道内觅食的过程信息素:信息素多的地方显然经过这里的蚂蚁多,因而会有更多的蚂蚁聚集过来。正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。*蚁群算法原理自然蚂蚁的智能特点*蚁群算法原理人工蚂蚁的模型*蚁群算法原理自然蚁群与人工蚁群相似之处在于:都是优先选择信息素浓度大的路径。两者的区别在于:(1)人工蚁群有一定的记忆能力,能够记忆已经访问过的节点。(2)人工蚁群选择路径时不是盲目的,而是按一定规律有意识地寻找最短路径。例如在TSP问题中,可以预先知道当前城市到下一个目的地的距离。*求解组合优化问题的蚁群算法*基本蚁群算法蚂蚁k(k=1,2,…,m)根据各个城市间连接路径上的信息素浓度决定其下一个访问城市,设表示t时刻蚂蚁k从城市i转移到城市j的概率,其计算公式为:信息更新公式为: