蚁群算法基本知识

《蚁群算法基本知识》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、智能算法第七章：蚁群算法谷俊峰工业装备结构分析国家重点实验室工程力学系运载工程与力学学部提纲7.1蚁群优化算法概述7.2蚁群优化算法的实现7.3蚁群优化算法的研究现状7.4蚁群优化算法——技术问题7.5蚁群优化算法应用现状7.1蚁群优化算法起源¢蚂蚁属于群居昆虫¢单个蚂蚁的行为极其简单,但由这样的单个简单的个体所组成的蚁群群体却表现出极其复杂的行为,能够完成复杂的任务。7.1蚁群优化算法起源¢蚂蚁觅食¢蚂蚁没有发育完全的视觉感知系统，甚至很多种类完全没有视觉，他们在寻找食物的过程中是如何选择路径的呢？¢蚂蚁往往像军队般有纪律、有秩序的搬运食物，他们是通过什么方式进行群体间的交流协作呢？¢

2、大部分的蚂蚁都是按照途中的最近的路线走，小小的蚂蚁是如何有这么高的智能的呢？7.1蚁群优化算法起源20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。¢1991年意大利米兰理学院M.Dorigo提出AntSystem,用于求解TSP等组合优化问题。¢1995年Gramdardella和Dorigo提出Ant-Q算法，建立了AS和Q-learning的联系。¢1996年二人又提出AntColonySystem¢1997年有人提出Max-MinAntSystem¢1999

3、年Dorigo等人把先前各种算法归结为AntColonyOptimizationmeta-heuristic的统一框架下，Dorigo给出抽象而规范的算法描述.¢目前，被较广泛的应用7.1蚁群优化算法应用领域¢蚁群优化算法自1991年由Dorigo提出并应用于TSP问题以来，已经发展了近20年。¢具有鲁棒性强、全局搜索、并行分布式计算、易与其他问题结合等优点¢应用领域不断扩张，如车间调度问题、车辆路径问题、分配问题、子集问题、网络路由问题、蛋白质折叠问题、数据挖掘、图像识别、系统辨识等。¢这些问题大都是NP难的组合优化问题，用传统算法难以求解或者无法求解，各种蚁群算法及其改进版本的出现，

4、为这些难题提供了有效而高效的手段。7.1蚁群算法原理¢蚁群是如何完成这些复杂的任务的呢?人们经过大量研究发现,蚂蚁个体之间是通过一种称之为外激素(pheromone)的物质进行信息传递.从而能相互协作,完成复杂的任务.¢蚁群之所以表现出复杂有序的行为,个体之间的信息交流与相互协作起着重要的作用.7.1蚁群算法原理¢蚂蚁在运动过程中,能够在它所经过的路径上留下外激素,而且蚂蚁在运动过程中能够感知外激素的存在及其强度,并以此指导自己的运动方向,蚂蚁倾向于朝着外激素强度高的方向移动.¢由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就

5、越大.蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。7.1简化的蚂蚁寻食过程蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。7.1简化的蚂蚁寻食过程本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。7.1简化的蚂蚁寻食过程假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了

6、食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈

7、效应。7.1简化的蚂蚁寻食过程食物食物食物巢穴巢穴巢穴7.1简化的蚂蚁寻食过程7.1自然蚁群与人工蚁群算法¢基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。¢人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。¢人工蚁群和自然蚁群的区别：¢人工蚁群有一定的记忆能力，能够记忆已