截图
简介
这是蚁群优化算法ppt，包括了基本概念及原理，数学模型与算法流程，研究现状及进展，算法优缺点及应用等内容，欢迎点击下载。
蚁群优化算法ppt是由红软PPT免费下载网推荐的一款课件PPT类型的PowerPoint.
蚁群优化算法概述 内容 基本概念 蚁群优化算法（Ant Colony Optimization，ACO） 是一种针对难解的离散优化问题的元启发式算法，利用一群人工蚂蚁的协作来寻找好的解。 既适用于静态组合优化问题，又适用于动态组合优化问题。前者如旅行商问题（TSP），后者如通讯领域的路由问题等。 启发式算法（Heuristic Algorithm） 在可接受的花费（指时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定能事先预计，也不能保证每次能用相同的时间求出结果。 有趣的问题 1.为何大多数蚂蚁在觅食时，会选择相同的路径，而且这条路径往往是一条食物和巢穴之间的最短路径，它们是如何做到的？ 2.当原来最优路径上出现了障碍物或者食物位置改变了；蚁群仍能够重新探索出新的一条最优路径？ 蚁群行为描述 仿生学家经过长期研究发现：蚂蚁虽然没有视觉，但是存在一种化学物质—信息素（pheromone）用于蚂蚁之间以及蚂蚁与环境的交互。 在没有信息素的情况下，蚂蚁是随机挑选路径的，同时释放出与路径有关的信息素。路径越长，信息素量越小。如果当前路径上存在信息素，蚂蚁倾向于信息素浓度高的路径。由于较短路径上，蚂蚁往返的时间短，单位时间内经过的蚂蚁数多，信息素累计的也多，因此会吸引更多的蚂蚁。信息素还会随着时间蒸发，其他路径上的信息素浓度下降，最终绝大多数的蚂蚁将沿着最优路径前行。 蚂蚁行为图解 蚁群优化算法起源 蚁群优化算法机制原理 蚁群优化的本质在于： 选择机制：信息素越多的路径，被选择的概率越大。 更新机制：路径上面的信息素会随蚂蚁的经过而增长，同 时也随时间的推移逐渐挥发消失。 协调机制：蚂蚁间通过环境中的信息素来协同工作。 蚁群算法的寻优包含两个基本过程： 蚂蚁构建解（ConstructAntSolution） 通过使一群蚂蚁并行异步访问邻近点，逐步建立优化问题的解。 更新信息素（UpdatePheromones）依据蚂蚁所构建的解修改空间内的信息素浓度。 蚂蚁系统解决TSP问题 蚂蚁系统（Ant System） 作为第一个ACO算法，是以NP-hard的TSP问题作为应用实例而提出的。虽然它的算法性能不及其他各种扩展算法，但是最基本的ACO算法，易于学习和掌握。 旅行商问题 一位商人从自家出发，希望能找到一条最短路径，途径给定集合的所有城市最后返回家乡，并且每个城市都被访问且仅访问一次。形式上，TSP问题可以用一个带权完全图G=（N，A）来描述，目标就是寻找一条具有最小成本值的哈密尔顿回路。 TSP问题数学描述 设 是n个城市的集合， 是集合C中元素两两连接的集合， 是 的距离，对任意i，j有 称为对称旅行商问题，若存在某组i，j之间的 则称为非对称旅行商问题。 目标函数表示为 对于n个城市规模的TSP，存在 条不同的闭合路径，当n较大时很难精确求解每个解再寻找最优。 蚂蚁系统数学模型（一） 设n表示TSP规模， i和j是集合C中的两个元素， m为蚁群蚂蚁总数， 表示t时刻位于i的蚂蚁数目，则 设 为t时刻路径(i，j)上的信息素量， 是t时刻集合C中所有信息素的集合。初始时刻，各条路径上的信息量是相同的。 蚂蚁系统数学模型（二） 蚂蚁 在运动过程中有三个因素决定其转移方向信息素量 ，启发式信息 和禁忌表 为启发函数，其表达式一般表示为 ； 禁忌表 用于记录蚂蚁k当前走过的城市， 表示蚂蚁k下步允许选择的城市。 蚂蚁系统数学模型（三） 表示蚂蚁k在t时刻由i转到j的概率 上式中，α为信息素因子， β为启发式因子，用于控制信息素浓度和启发式信息作用的权重关系。值越大表示重要性越大，当α=0，算法演变为传统的随机贪心算法，当β=0，蚂蚁仅依据信息素决策，算法将快速收敛，可能获得局部最优。 蚂蚁系统数学模型（四） 信息素更新公式 1. 原有信息素的挥发 通常的做法是设置信息持久率 让所有 乘以 。在算法中用于避免信息素的无限增长淹没启发式信息，也有助于丢弃那些构建过的较差的路径。 2. 新生信息素的释放 AS算法曾有过三种信息素释放策略 Ant-Density模型： 若蚂蚁k在t到t+1之间经过(i，j) Ant-Quantity模型： 若蚂蚁k在t到t+1之间经过(i，j) Ant-Cycle模型： 若蚂蚁k在本次循环中经过(i，j) 蚂蚁系统解决TSP步骤 蚂蚁系统解决TSP算法流程 算法复杂度分析 研究现状 AS是第一个ACO算法由Dorigo等人 于1991年在第一届欧洲人工生命会议上提出。 1996年，Dorigo发表Ant system:optimization by a colony of cooperation agents，成为里程碑。 随后，精英蚂蚁系统、最大最小蚂蚁系统和基于排 列的蚂蚁系统大多在AS上直接改进。 1997年，Dorigo提出了大幅改动AS特征的算法—蚁群系统(Ant Colony System，ACS)性能明显优于AS。 21世纪出现了连续蚁群算法，能够优化连续空间问题。 精英蚂蚁系统 精英蚂蚁系统（EAS）是最早的改进蚂蚁系统。 精英蚂蚁系统 信息素根据下式进行更新 基于排列的蚂蚁系统 基于排列蚂蚁系统(ASrank)由Bullnheimer于1997年提出。 基本思想与EAS类似，具体做法是在每一轮所有蚂蚁构建完路径后，将各自所得的路径进行排名，只有生成了至今最优路径的蚂蚁以及排名在前(ω-1)的蚂蚁才允许释放信息素。 最优蚂蚁释放 的信息素量，在本次迭代中排名 的蚂蚁将释放 的信息素。一 般设置ω=6。 最大最小蚂蚁系统 前两种改进算法将蚂蚁的搜索行为偏向当前最优解虽然提高解的质量和收敛速度，进而改进算法的性能。但这种搜索方式无法避免早熟收敛问题。 最大最小蚂蚁系统 MMAS和AS主要有四个方面不同： 在每次循环之后，只有一只蚂蚁进行信息素更新。这只蚂蚁可能是找出当前循环中最优解的蚂蚁，也可能是找出从实验开始以来最优解的蚂蚁 在每个解的元素上的的信息素量被限制在 范围区间内 信息素初始值为信息素取值范围的上限 ，信息维持率保持一个较大值。 当系统陷入停滞，将问题空间所有边的信息素重新初始化。 最大最小蚂蚁系统 改进1借鉴了EAS，但有不同。使用至今最优的蚂蚁释放可加快收敛，当前迭代最优可增强探索，应该交替使用，逐渐增大至今最优蚂蚁的使用概率。 改进2通过给信息素设定上界目的是避免信息素增长过快，淹没了启发式信息的影响。启发式信息在每次迭代中是无法增长的。 改进3设置较大的信息素维持度（一般设置为0.98）可以保证初始阶段的探索能力。 改进4可以利用停滞后的迭代周期继续进行搜索。 蚁群系统 蚁群系统(Ant Colony System， ACS)是由Dorigo和Gambardella在1997年提出的。 蚁群系统状态转移规则 一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市J 蚁群系统全局更新规则 只有一只至今最优的蚂蚁（大规模问题性能更优）才被允许释放信息素 每轮迭代中，所有蚂蚁构建完路径后，信息素全局更新规则才被使用。更新公式如下所示： 蚁群系统局部更新规则 每只蚂蚁应用下列局部更新规则对它们所经过的边进行信息素更新： 蚁群优化算法优缺点 蚁群优化算法有如下优点： 是具有自学习能力，可以对自身知识库或自身的组织结构进行再组织，实现算法能力的进化 采用正反馈机制，能加快搜索 采用分布式并行计算多点同时独立搜索易于找到全局最优 易于和其他方法结合 有较强的鲁棒性 蚁群优化算法有如下缺点： 要么搜索时间长要么易陷入局部最优，很难保持平衡。 算法机理的复杂和环境的变化会增加蚁群算法的不确定性 蚁群优化算法的应用 基于算法的诸多优点，蚁群优化已被成功地应用于 二次分配问题(quadratic assignment problem， QAP) ， 作业调度问题(job-scheduling problem， JSP)， 图表着色问题(graph coloring problem， GCP)， 车辆路径问题(Vehicle Routing Problem，VRP)， 通信网络的路由优化(network route，NR)等 蚁群优化算法参数设置（一） 蚁群优化算法参数设置（二） Questions?
展开
