第三部分蚁群算法1讲课.pptVIP

* 第三章蚁群算法 改进的蚁群算法 Macro Dorigo Gambardella 主要内容 3.1 群智能 3.1.1 群智能的概念 3.1.2 群智能算法 3.2 蚁群优化算法原理 3.2.1 蚁群算法的起源 3.2.2 蚁群算法的原理分析 基本蚁群优化算法 3.3.1 蚂蚁系统的模型与实现 3.3.2 蚂蚁系统的参数设置和基本属性 主要内容 改进的蚁群优化算法 3.4.1 蚂蚁系统的优点与不足 3.4.2 带精英策略的蚂蚁系统 基于排序的蚂蚁系统 最大－最小蚂蚁系统 3.4.5 蚁群系统 各种蚁群优化算法的比较 3.5 蚁群优化算法的应用 典型应用 3.5.2 车间作业调度（JSP） 医学诊断的数据挖掘 3.5.4 蚁群算法在电信路由优化中的应用 型 3.1 群智能 3.1.1 群智能的概念 群智能（ Swarm Intelligence, SI ） 人们把群居昆虫的集体行为称作“群智能”（“群体智 能”、“群集智能”、“集群智能”等） 特点 个体的行为很简单，但当它们一起协同工作时，却能 够突现出非常复杂（智能）的行为特征。 3.1 群智能 3.1.2 群智能的算法 描述 群智能作为一种新兴的演化计算技术已成为研究焦点， 它与人工生命，特别是进化策略以及遗传算法有着极为 特殊的关系。 特性 指无智能的主体通过合作表现出智能行为的特性，在没 有集中控制且不提供全局模型的前提下，为寻找复杂的 分布式问题求解方案提供了基础。 3.1 群智能 3.1.2 群智能的算法 优点 与大多数基于梯度的应用优化算法不同，群智能依靠的是概率有哪些信誉好的足球投注网站算法。 虽然概率有哪些信誉好的足球投注网站算法通常要采用较多的评价函数，但是与梯度方法及传统 的演化算法相比，其优点还是显著的 稳健性：无集中控制约束，不会因个别个体的故障影响整个问题的 求解，确保了系统具备更强的鲁棒性； 扩展性：活动既不受中央控制，也不受局部监管，以非直接的信息 交流方式确保了系统的扩展性 并行性：并行分布式算法模型，可充分利用多处理器 灵活性：对问题定义的连续性无特殊要求； 易行性：算法实现简单。 典型算法 蚁群算法（蚂蚁觅食）粒子群算法（鸟群捕食） 3.2 蚁群优化算法原理 3.2.1 蚁群算法的起源 20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启 发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进 化策略、遗传算法等，这些算法成功地解决了一些实际问题。 20世纪90年代意大利学者M．Dorigo，V．Maniezzo，A．Colorni等 从生物进化的机制中受到启发，通过模拟自然界蚂蚁有哪些信誉好的足球投注网站路径的行 为，提出来一种新型的模拟进化算法——蚁群算法，是群智能理论 研究领域的一种主要算法。 这种方法能够被用于解决大多数优化问题或者能够转化为优化求解 的问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚 类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、 机器人控制、决策支持以及仿真和系统辩识等方面．虽然研究时间 不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题（特 别是离散优化问题）方面有一定优势。 3.2 蚁群优化算法原理 3.2.1 蚁群算法的起源 蚁群的自组织行为 “双桥实验” 蚂蚁在运动过程中，通过遗 留在来往路径上的挥发性化 学物质（信息素,Pheromone） 来进行通信和协调。因此由 大量蚂蚁组成的蚁群集体行 为便表现出一种信息正反馈 现象： 某一路径上走过的蚂蚁越 多，则后来者选择该路径的 概率就越大。 3.2 蚁群优化算法原理 3.2.1 蚁群算法的起源 蚁群的自组织行为 “双桥实验” 3.2 蚁群优化算法原理 3.2.1 蚁群算法的起源 提出蚁群系统 1992年，意大利学者M. Dorigo在其博士论文中提出 蚂蚁系统（Ant System）。 近年来，M. Dorigo等人进一步将蚂蚁算法发展为一种通 用的优化技术——蚁群优化（ant colony optimization, ACO）。 3.2 蚁群优化算法原理 3.2.2 蚁群算法的原理分析 蚁巢 食物 蚂蚁从A点出发，速度相同，食物在D点，随机选择路线ABD或ACD。 假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步。 经过9个时间单位时：走ABD的蚂蚁到达终点，走ACD的蚂蚁刚好走到 C点，为一半路程。