遗传算法与蚁群算法简介-课件

遗传算法与群智能优化算法简介1-主要内容n智能优化算法简介问题的NP-完全特性常用的智能优化算法n遗传算法-Genetic Algorithmn群智能优化算法蚁群优化算法-Ant Colony Optimization粒子群优化算法-Particle Swarm Optimization.2024/7/272-智能优化算法简介n20世纪80年代以来，一些优化算法得到发展GA、EP、ACO、PSO、SA、TS、ANN及混合的优化策略等n基本思想：模拟或揭示某些自然现象或过程n为用传统的优化方法难以解决的NP-完全问题提供了有效的解决途径n由于算法构造的直观性与自然机理，因而通常被称作智能智能优化算法化算法（intelligent optimization algorithms），或现代启代启发式算法式算法（meta-heuristic algorithms）n智能优化算法及其应用，王凌，清华大学出版社，20012024/7/273-智能优化算法简介-问题的NP-完全特性n求解n个城市的TSP问题。典型的组合优化问题，是NP-完全的要准确求解该问题只能用枚举类的办法要枚举的解的个数为(n-1)!例：n=24，则要枚举的解的个数为：23!=25,852,016,738,884,976,640,000n2425262728293031时间1s 24s 10m 4.3h 4.9d 136.5d 10.8y 325y2024/7/274-2024/7/275-2024/7/276-2024/7/277-智能优化算法简介-常用的智能优化算法n遗传算法（Genetic Algorithm，GA）n演化规划（Evolutionary Programming，EP）n蚁群优化算法（Ant Colony Optimization，ACO）n粒子群优化算法（Particle Swarm Optimization，PSO）n模拟退火算法（Simulated Annealing，SA）n禁忌搜索算法（Tabu Search，TS）n人工神经网络（Artificial Neural Network，ANN）n2024/7/278-主要内容n智能优化算法简介问题的NP-完全特性常用的智能优化算法n遗传算法-Genetic Algorithmn群智能优化算法蚁群优化算法-Ant Colony Optimization粒子群优化算法-Particle Swarm Optimization2024/7/279-遗传算法(Genetic Algorithm)n1975年，Holland出版了著名的Adaptation in Natural and Artificial Systems，标志着遗传算法的诞生。n在一定程度上解决了传统的基于符号处理机制的人工智能方法在知识表示、信息处理和解决组合爆炸等方面所遇到的困难n基于“适者生存”原则，是并行优化算法，其自组织、自适应、自学习及群体进化的能力适合大规模复杂优化问题n将问题求解表示为“染色体”，通过选择（selection）、交叉（crossover）和变异（mutation）操作的迭代，实现种群的演化，最后终收敛到“最适应环境”的个体，从而求得问题的最优解（满意解）2024/7/2710-遗传算法-简单遗传算法n简单遗传算法（Simple Genetic Algorithms，SGA），又称基本遗传算法、标准遗传算法n基于二进制编码，是最基本的遗传算法，其遗传进化操作过程简单、容易理解，是其他遗传算法的雏形和基础n三种基本操作选择：通常用比例选择，即选择概率正比于个体的适配值，使适配值高的个体在下一代中被选中的概率大，提高种群平均适配值交叉：交换两父代个体的部分信息构成后代个体，使得后代继承父代的有效模式，有助于产生优良个体变异：随机改变个体中的某些基因，有助于增加种群多样性，避免早熟收敛2024/7/2711-随机产生N个个体构成初始种群P(0),令k=0对种群P(k)中各个体进行评价终止？令m=0从种群中选择两个体rand()pc将所选个体作为临时个体对临时个体以概率pm执行变异操作，产生两个新个体并放入P(k+1)中，令m=m+2对选中个体执行交叉操作生成两个临时个体输出优化结果m f(1*),f(00*)f(11*),f(01*),f(10*)f(*0*)f(*1*),f(0*0)f(1*1),f(0*1),f(1*0)f(*0)f(*1),f(*00)f(*11),f(*01),f(*10)即竞争力强的低阶模式的有效基因位为“0”，那么该类模式在群体中的数量将按指数增长，包含“0”的1，2阶模式使GA搜索偏离最优解，就形成了3阶模式欺骗问题。2024/7/2726-遗传算法-主要特点n处理参数集合的编码，而不是参数本身n始终保持整个种群而不是个体的进化；即使某个体在某时刻丢失了有用的特性，这种特性也会被其它个体保留并发展下去n只需要知道问题本身所具有的目标函数的信息，且不受连续、可微等条件的约束，因而具有广泛的适用性n启发式搜索，可适用于有噪声和多峰值的复杂空间2024/7/2727-主要内容n智能优化算法简介问题的NP-完全特性常用的智能优化算法n遗传算法-Genetic Algorithmn群智能优化算法蚁群优化算法-Ant Colony Optimization粒子群优化算法-Particle Swarm Optimization2024/7/2728-群智能优化算法n群智能优化算法是一种近年来新兴的优化方法，其模拟社会性动物的各种群体行为，利用群体中个体间的信息交互和合作来实现寻优目的n群智能优化算法包括很多算法，如人工蜂群算法和人工鱼群算法等，不过研究比较深入、应用比较广泛的是蚁群优化算法和粒子群优 化算法。也有人将遗传算法和差分演化算法（Differential Evolution Algorithm）归入群智能优化算法中。2024/7/2729-n与基于梯度的优化算法不同，群智能优化算法依靠的是概率搜索，其优点是：无集中控制约束，不会因个别个体而影响整个问题的求解，确保了系统的鲁棒性以非直接的信息交流方式确保了系统的扩展性并行分布式算法模型对问题定义的连续性无特殊要求算法实现简单2024/7/2730-主要内容n智能优化算法简介问题的NP-完全特性常用的智能优化算法n遗传算法-Genetic Algorithmn群智能优化算法蚁群优化算法-Ant Colony Optimization粒子群优化算法-Particle Swarm Optimization2024/7/2731-蚁群优化算法(Ant Colony Optimization)n蚁群优化算法（蚂蚁算法），是一种分布式智能模拟算法n由M.Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为n基本思想是模拟蚂蚁依赖信息素进行通信而显示出的社会行为n是一种随机的通用试探法，可用于求解各种不同的组合优化问题n初始的蚁群优化算法是基于图的蚁群系统，过程如下（以求解对称的TSP问题为例）：2024/7/2732-n问题的描述：n个城市N=1,2,n，任两城市的边A=(i,j)|i,j N，城市间的距离为D=(dij)nnn设有m只蚂蚁，其出发城市可随机确定n路径的构造为TSP图中的每一条弧(i,j)赋信息素初值ij(0)，通常的做法是随机生成一个解，设其目标值为f0，则ij(0)=1/f0设置城市间的启发式信息ij，通常ij =1/dij设第k只蚂蚁在城市i，则其根据下面的概率选择下一个城市：其中另外，每一蚂蚁有一个表list，用于记录其访问过的城市；当访问了所有的城市后，就可以在其经过的路径上更新信息素与表示信息素与启发式信息的相对重要程度，通常=1或2，=2或3 表示蚂蚁k可选的城市集合，即其还未访问过的城市集合2024/7/2733-n信息素更新策略（局部更新）所有蚂蚁周游完成后更新信息素：首先以一定的比例(1-)减少每条边上的信息素（表示信息素的挥发），然后更新各自路径上的信息素，即更新信息素的方式为其中信息素的挥发机制可以避免信息素大量积累，也体现了生物界的“遗忘”现象；表示蚂蚁k在边(i,j)上留下的信息素，如果蚂蚁没有经过该边，则其留下的信息素为0，即其中，表示蚂蚁k构造的路径的长度，Q是一常数（比如1）此机制体现了：构造的路径越短，蚂蚁留下的信息素越多；某边经过的蚂蚁越多，其上积累的信息素也就越多2024/7/2734-全局更新：对于一次迭代中最好的那只蚂蚁，单独更新其经过路径上的信息素n上面的蚁群优化算法的不足信息素的累积造成“停滞”现象：蚂蚁基本上走同一条路径要得到更好的优化能力往往需要与局部搜索算法结合：对最好的路径执行局部搜索n蚁群算法的改进精英策略：对已发现的最好路径给予额外的增强，从而增大较好路径的选择概率负反馈机制：蚂蚁走过一条边时，立即减少该边上的信息素，以减少该边再次被选中的概率Max-Min蚂蚁系统：将信息素的浓度限制在min,max的范围内，避免搜索停滞T.Stutzle,H.Hoos,MAX-MIN Ant System,FGCS,2000,16:889-914 2024/7/2735-蚁群优化算法-较成功的算法算法名称算法名称提出者提出者年份年份Ant System(AS)Dorigo et al.1991Elitist ASDorigo et al.1992Ant-QGambardella,Dorigo1995Ant Colony SystemDorigo,Gambardella1996Max-Min ASStutzle,Hoos1996Rank-Based ASBullnheimer et al.1997AntsManiezzo1999BWASCordon et al.2000Hyper-Cube ASBlum et al.20012024/7/2736-蚁群优化算法-较成功的应用问题类型型问题名称名称作者作者年份年份路径规划旅行商问题Dorigo et al.1991,1996Dorigo,Gambardella1997Stutzle,Hoos1997,2000车辆路径规划Gambardella et al.1999Reimann et al.2004有序排列Gambardella,Dorigo2000分配问题二次分配Stutzle,Hoos2000Maniezzo1999课表编排Socha et al.2002,2003图着色Costa,Hertz19972024/7/2737-蚁群优化算法-较成功的应用(续)问题类型型问题名称名称作者作者年份年份调度问题工程调度Merkle et al.2002开放车间Blum2005子集问题集覆盖Lessing et al.2004其他约束满足Solnon2000,2002分类规则Parpinelli et al.2002Martens et al.2006贝叶斯网络Campos et al.2002蛋白质折叠Shmygelska,Hoos2005M.Dorigo,T.Stutzle著,张军等译,蚁群优化,清华大学出版社,2007.2024/7/2738-主要内容n智能优化算法简介问题的NP-完全特性常用的智能优化算法n遗传算法-Genetic Algorithmn群智能优化算法蚁群优化算法-Ant Colony Optimization粒子群优化算法-Particle Swarm Optimization2024/7/2739-粒子群优化算法(Particle Swarm Optimization)n粒子群优化算法（Particle Swarm Optimization,PSO,也称为微粒群优化算法）是由Kennedy和Eberhart于1995年提出来的n所谓粒子是指不考虑群体中的成员的质量和体积，只考虑速度和加速状态2024/7/2740-n 设第i个粒子表示为Xi=(xi1,xi2,xiD)，有最好适应值的位置记为Pi=(pi1,pi2,piD)，也称为Pbest。设符号g表示群体中所有粒子经历过的最好位置，也称为gbest。设Vi=(vi1,vi2,viD)表示粒子i的速度。在每一代，粒子i的第d维(1 d D)根据如下方程变化：vid=wvid+c1rand1()(pid-xid)+c2rand2()(pgd-xid)xid=xid+vid 其中w为惯性权重，c1和c2为加速常数，rand1()和rand2()为在0,1内选取的随机函数。此外，微粒的速度vid的上限为Vmax。粒子群优化算法-基本原理2024/7/2741-(1)初始化：随机生成一群规模为m的微粒，包括位置和速度(2)评价：计算每个微粒的适应度(3)更新Pbest：对每个微粒，将其适应值与其经历过的最好位置做比较，如果较好，则将其位置作为该微粒的当前最好位置Pbest(4)更新gbest：对每个微粒，将其适应值与全局最好位置做比较，如果较好，则将其记为gbest(5)更新vid和xid：根据上述公式改变微粒的速度和位置(6)如达到满意的适应值或预设的最大代数Gmax，则结束，否则转(2)粒子群优化算法-基本过程2024/7/2742-粒子群优化算法-参数设置n最大速度Vmax：决定了空间搜索的粒度，通常设为每维变化范围的10%到20%n惯性权重w：使粒子保持运动惯性，使其具有扩展搜索空间的趋势，有能力探索新的区域。为了使算法在前期有较高的搜索能力，在后期有较快的收敛速度，可令w随时间线性减小，如由1.4到0，由0.9到0.4，由0.95到0.2等n加速常数c1和c2：通常可固定为2。2024/7/2743-n最后，我们赞同“无免费午餐”的观点，因此应尽可地了解问题的本身特点，针对问题给出算法设计，绝不能无目的的模拟计算2024/7/2744-谢谢！2024/7/2745-