遗传算法与蚁群算法简介 教育学习

遗传算法与群智能优化算法简介,优质课件,主要内容,智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-GeneticAlgorithm群智能优化算法蚁群优化算法-AntColonyOptimization粒子群优化算法-ParticleSwarmOptimization.,2,优质课件,智能优化算法简介,20世纪80年代以来，一些优化算法得到发展GA、EP、ACO、PSO、SA、TS、ANN及混合的优化策略等基本思想：模拟或揭示某些自然现象或过程为用传统的优化方法难以解决的NP-完全问题提供了有效的解决途径由于算法构造的直观性与自然机理，因而通常被称作智能优化算法（intelligentoptimizationalgorithms），或现代启发式算法（meta-heuristicalgorithms）智能优化算法及其应用，王凌，清华大学出版社，2001,3,优质课件,智能优化算法简介-问题的NP-完全特性,求解n个城市的TSP问题。典型的组合优化问题，是NP-完全的要准确求解该问题只能用枚举类的办法要枚举的解的个数为(n-1)!例：n=24，则要枚举的解的个数为：23!=25,852,016,738,884,976,640,000,1s,24s,10m,4.3h,4.9d,136.5d,10.8y,325y,4,优质课件,5,优质课件,6,优质课件,7,优质课件,智能优化算法简介-常用的智能优化算法,遗传算法（GeneticAlgorithm，GA）演化规划（EvolutionaryProgramming，EP）蚁群优化算法（AntColonyOptimization，ACO）粒子群优化算法（ParticleSwarmOptimization，PSO）模拟退火算法（SimulatedAnnealing，SA）禁忌搜索算法（TabuSearch，TS）人工神经网络（ArtificialNeuralNetwork，ANN）,8,优质课件,主要内容,智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-GeneticAlgorithm群智能优化算法蚁群优化算法-AntColonyOptimization粒子群优化算法-ParticleSwarmOptimization,9,优质课件,遗传算法(GeneticAlgorithm),1975年，Holland出版了著名的AdaptationinNaturalandArtificialSystems，标志着遗传算法的诞生。在一定程度上解决了传统的基于符号处理机制的人工智能方法在知识表示、信息处理和解决组合爆炸等方面所遇到的困难基于“适者生存”原则，是并行优化算法，其自组织、自适应、自学习及群体进化的能力适合大规模复杂优化问题将问题求解表示为“染色体”，通过选择（selection）、交叉（crossover）和变异（mutation）操作的迭代，实现种群的演化，最后终收敛到“最适应环境”的个体，从而求得问题的最优解（满意解）,10,优质课件,遗传算法-简单遗传算法,简单遗传算法（SimpleGeneticAlgorithms，SGA），又称基本遗传算法、标准遗传算法基于二进制编码，是最基本的遗传算法，其遗传进化操作过程简单、容易理解，是其他遗传算法的雏形和基础三种基本操作选择：通常用比例选择，即选择概率正比于个体的适配值，使适配值高的个体在下一代中被选中的概率大，提高种群平均适配值交叉：交换两父代个体的部分信息构成后代个体，使得后代继承父代的有效模式，有助于产生优良个体变异：随机改变个体中的某些基因，有助于增加种群多样性，避免早熟收敛,11,优质课件,随机产生N个个体构成初始种群P(0),令k=0,对种群P(k)中各个体进行评价,终止？,令m=0,从种群中选择两个体,rand()pc,将所选个体作为临时个体,对临时个体以概率pm执行变异操作，产生两个新个体并放入P(k+1)中，令m=m+2,对选中个体执行交叉操作生成两个临时个体,输出优化结果,mf(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阶模式欺骗问题。,26,优质课件,遗传算法-主要特点,处理参数集合的编码，而不是参数本身始终保持整个种群而不是个体的进化；即使某个体在某时刻丢失了有用的特性，这种特性也会被其它个体保留并发展下去只需要知道问题本身所具有的目标函数的信息，且不受连续、可微等条件的约束，因而具有广泛的适用性启发式搜索，可适用于有噪声和多峰值的复杂空间,27,优质课件,主要内容,智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-GeneticAlgorithm群智能优化算法蚁群优化算法-AntColonyOptimization粒子群优化算法-ParticleSwarmOptimization,28,优质课件,群智能优化算法,群智能优化算法是一种近年来新兴的优化方法，其模拟社会性动物的各种群体行为，利用群体中个体间的信息交互和合作来实现寻优目的群智能优化算法包括很多算法，如人工蜂群算法和人工鱼群算法等，不过研究比较深入、应用比较广泛的是蚁群优化算法和粒子群优化算法。也有人将遗传算法和差分演化算法（DifferentialEvolutionAlgorithm）归入群智能优化算法中。,29,优质课件,与基于梯度的优化算法不同，群智能优化算法依靠的是概率搜索，其优点是：无集中控制约束，不会因个别个体而影响整个问题的求解，确保了系统的鲁棒性以非直接的信息交流方式确保了系统的扩展性并行分布式算法模型对问题定义的连续性无特殊要求算法实现简单,30,优质课件,主要内容,智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-GeneticAlgorithm群智能优化算法蚁群优化算法-AntColonyOptimization粒子群优化算法-ParticleSwarmOptimization,31,优质课件,蚁群优化算法(AntColonyOptimization),蚁群优化算法（蚂蚁算法），是一种分布式智能模拟算法由M.Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为基本思想是模拟蚂蚁依赖信息素进行通信而显示出的社会行为是一种随机的通用试探法，可用于求解各种不同的组合优化问题初始的蚁群优化算法是基于图的蚁群系统，过程如下（以求解对称的TSP问题为例）：,32,优质课件,问题的描述：n个城市N=1,2,n，任两城市的边A=(i,j)|i,jN，城市间的距离为D=(dij)nn设有m只蚂蚁，其出发城市可随机确定路径的构造为TSP图中的每一条弧(i,j)赋信息素初值ij(0)，通常的做法是随机生成一个解，设其目标值为f0，则ij(0)=1/f0设置城市间的启发式信息ij，通常ij=1/dij设第k只蚂蚁在城市i，则其根据下面的概率选择下一个城市：其中另外，每一蚂蚁有一个表list，用于记录其访问过的城市；当访问了所有的城市后，就可以在其经过的路径上更新信息素,与表示信息素与启发式信息的相对重要程度，通常=1或2，=2或3,表示蚂蚁k可选的城市集合，即其还未访问过的城市集合,33,优质课件,信息素更新策略（局部更新）所有蚂蚁周游完成后更新信息素：首先以一定的比例(1-)减少每条边上的信息素（表示信息素的挥发），然后更新各自路径上的信息素，即更新信息素的方式为其中信息素的挥发机制可以避免信息素大量积累，也体现了生物界的“遗忘”现象；表示蚂蚁k在边(i,j)上留下的信息素，如果蚂蚁没有经过该边，则其留下的信息素为0，即其中，表示蚂蚁k构造的路径的长度，Q是一常数（比如1）此机制体现了：构造的路径越短，蚂蚁留下的信息素越多；某边经过的蚂蚁越多，其上积累的信息素也就越多,34,优质课件,全局更新：对于一次迭代中最好的那只蚂蚁，单独更新其经过路径上的信息素上面的蚁群优化算法的不足信息素的累积造成“停滞”现象：蚂蚁基本上走同一条路径要得到更好的优化能力往往需要与局部搜索算法结合：对最好的路径执行局部搜索蚁群算法的改进精英策略：对已发现的最好路径给予额外的增强，从而增大较好路径的选择概率负反馈机制：蚂蚁走过一条边时，立即减少该边上的信息素，以减少该边再次被选中的概率Max-Min蚂蚁系统：将信息素的浓度限制在min,max的范围内，避免搜索停滞T.Stutzle,H.Hoos,MAX-MINAntSystem,FGCS,2000,16:889-914,35,优质课件,蚁群优化算法-较成功的算法,36,优质课件,蚁群优化算法-较成功的应用,37,优质课件,蚁群优化算法-较成功的应用(续),M.Dorigo,T.Stutzle著,张军等译,蚁群优化,清华大学出版社,2007.,38,优质课件,主要内容,智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-GeneticAlgorithm群智能优化算法蚁群优化算法-AntColonyOptimization粒子群优化算法-ParticleSwarmOptimization,39,优质课件,粒子群优化算法(ParticleSwarmOptimization),粒子群优化算法（ParticleSwarmOptimization,PSO,也称为微粒群优化算法）是由Kennedy和Eberhart于1995年提出来的所谓粒子是指不考虑群体中的成员的质量和体积，只考虑速度和加速状态,40,优质课件,设第i个粒子表示为Xi=(xi1,xi2,xiD)，有最好适应值的位置记为Pi=(pi1,pi2,piD)，也称为Pbest。设符号g表示群体中所有粒子经历过的最好位置，也称为gbest。设Vi=(vi1,vi2,viD)表示粒子i的速度。在每一代，粒子i的第d维(1dD)根据如下方程变化：vid=wvid+c1rand1()(pid-xid)+c2rand2()(pgd-xid)xid=xid+vid其中w为惯性权重，c1和c2为加速常数，rand1()和rand2()为在0,1内选取的随机函数。此外，微粒的速度vid的上限为Vmax。,粒子群优化算法-基本原理,41,优质课件,(1)初始化：随机生成一群规模为m的微粒，包括位置和速度(2)评价：计算每个微粒的适应度(3)更新Pbest：对每个微粒，将其适应值与其经历过的最好位置做比较，如果较好，则将其位置作为该微粒的当前最好位置Pbest(4)更新gbest：对每个微粒，将其适应值与全局最好位置做比较，如果较好，则将其记为gbest(5)更新vid和xid：根据上述公式改变微粒的速度和位置(6)如达到满意的适应值或预设的最大代数Gmax，则结束，否则转(2),粒子群优化算法-基本过程,42,优质课件,粒子群优化算法-参数设置,最大速度Vm