遗传算法与蚁群算法简介.ppt

遗传算法与群智能优化算法简介,主要内容,智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-Genetic Algorithm群智能优化算法蚁群优化算法-Ant Colony Optimization粒子群优化算法-Particle Swarm Optimization.,北京交通大学计算机与信息技术学院,2,2023/6/25,智能优化算法简介,20世纪80年代以来，一些优化算法得到发展GA、EP、ACO、PSO、SA、TS、ANN及混合的优化策略等基本思想：模拟或揭示某些自然现象或过程为用传统的优化方法难以解决的NP-完全问题提供了有效的解决途径由于算法构造的直观性与自然机理，因而通常被称作智能优化算法（intelligent optimization algorithms），或现代启发式算法（meta-heuristic algorithms）智能优化算法及其应用，王凌，清华大学出版社，2001,北京交通大学计算机与信息技术学院,3,2023/6/25,智能优化算法简介-问题的NP-完全特性,求解n个城市的TSP问题。典型的组合优化问题，是NP-完全的要准确求解该问题只能用枚举类的办法要枚举的解的个数为(n-1)!例：n=24，则要枚举的解的个数为：23!=25,852,016,738,884,976,640,000,北京交通大学计算机与信息技术学院,4,2023/6/25,1s,24s,10m,4.3h,4.9d,136.5d,10.8y,325y,北京交通大学计算机与信息技术学院,5,2023/6/25,北京交通大学计算机与信息技术学院,6,2023/6/25,北京交通大学计算机与信息技术学院,7,2023/6/25,智能优化算法简介-常用的智能优化算法,遗传算法（Genetic Algorithm，GA）演化规划（Evolutionary Programming，EP）蚁群优化算法（Ant Colony Optimization，ACO）粒子群优化算法（Particle Swarm Optimization，PSO）模拟退火算法（Simulated Annealing，SA）禁忌搜索算法（Tabu Search，TS）人工神经网络（Artificial Neural Network，ANN）,北京交通大学计算机与信息技术学院,8,2023/6/25,主要内容,智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-Genetic Algorithm群智能优化算法蚁群优化算法-Ant Colony Optimization粒子群优化算法-Particle Swarm Optimization,北京交通大学计算机与信息技术学院,9,2023/6/25,遗传算法(Genetic Algorithm),1975年，Holland出版了著名的Adaptation in Natural and Artificial Systems，标志着遗传算法的诞生。在一定程度上解决了传统的基于符号处理机制的人工智能方法在知识表示、信息处理和解决组合爆炸等方面所遇到的困难基于“适者生存”原则，是并行优化算法，其自组织、自适应、自学习及群体进化的能力适合大规模复杂优化问题将问题求解表示为“染色体”，通过选择（selection）、交叉（crossover）和变异（mutation）操作的迭代，实现种群的演化，最后终收敛到“最适应环境”的个体，从而求得问题的最优解（满意解）,北京交通大学计算机与信息技术学院,10,2023/6/25,遗传算法-简单遗传算法,简单遗传算法（Simple Genetic Algorithms，SGA），又称基本遗传算法、标准遗传算法基于二进制编码，是最基本的遗传算法，其遗传进化操作过程简单、容易理解，是其他遗传算法的雏形和基础三种基本操作选择：通常用比例选择，即选择概率正比于个体的适配值，使适配值高的个体在下一代中被选中的概率大，提高种群平均适配值交叉：交换两父代个体的部分信息构成后代个体，使得后代继承父代的有效模式，有助于产生优良个体变异：随机改变个体中的某些基因，有助于增加种群多样性，避免早熟收敛,北京交通大学计算机与信息技术学院,11,2023/6/25,北京交通大学计算机与信息技术学院,12,2023/6/25,随机产生N个个体构成初始种群P(0),令k=0,对种群P(k)中各个体进行评价,终止？,令m=0,从种群中选择两个体,rand()pc,将所选个体作为临时个体,对临时个体以概率pm执行变异操作，产生两个新个体并放入P(k+1)中，令m=m+2,对选中个体执行交叉操作生成两个临时个体,输出优化结果,mN？,y,n,y,n,y,n,遗传算法-选择,适者生存：适应值高的个体的生存概率大，即被选中用来繁殖下一代的概率大。常用的选择方法有：比例选择（轮盘选择）基于排名的选择：由好到坏排序，然后以一定方式给每一个体分配选择概率（线性、非线性等方式，要求好的个体被选择的概率大，所有个体所分配的概率之和为1）锦标赛选择：在父代个体随机选k个，然后选最好的。,北京交通大学计算机与信息技术学院,13,2023/6/25,适应值：第i个个体的选择概率：产生随机数：选择满足下式的第i个个体：,遗传算法-交叉,用于组合出新的个体，在解空间中进行有效搜索，同时降低对有效模式的破坏概率二进制编码的GA通常采用单点交叉和多点交叉。单点交叉：随机选定一个交叉位置，然后对换交叉点后的子串。多点交叉：随机选择多个位置，然后对换相应子串。两点交叉：,北京交通大学计算机与信息技术学院,14,2023/6/25,1 0 1 1,0 0 1 0,0 0 1,1 1 0,1 0 1 1,0 0 1 0,0 0 1,1 1 0,1 0,0 1,1 1 0,0 0,1 0,1 0 1,1 0,0 1,1 1 0,0 0,1 0,1 0 1,遗传算法-交叉（续）,实数编码的GA通常采用算术交叉：双个体算术交叉：x1、x2为父代个体，(0,1)为随机数x1=x1+(1-)x2 x2=x2+(1-)x1 多个体算术交叉：x1,x2为父代个体;i(0,1)且i=1x=1x1+2x2+nxn 组合优化中的置换编码GA通常采用部分映射交叉(partially mapping crossover,PMX)：随机选择两个交叉点，交换交叉点之间的片段；对于其他基因，若它不与换过来的片段冲突则保留，若冲突则通过部分映射来确定最后的基因p1=2 6 4|7 3 5 8|9 1 p1=2 3 4|1 8 7 6|9 5p2=4 5 2|1 8 7 6|9 3 p2=4 1 2|7 3 5 8|9 6,北京交通大学计算机与信息技术学院,15,2023/6/25,遗传算法-交叉（续）,Non-ABEL交叉：p1i=p1p2i,p2i=p2p1ip1=2 6 4 7 3 5 8 9 1 p1=7 3 6 2 9 8 5 1 4p2=4 5 2 1 8 7 6 9 3 p2=5 7 1 6 2 8 9 3 4Non-ABEL群置换操作产生后代方式简单，过分打乱了父串，不利于保留有效模式次序交叉（OX）首先随机确定两个交叉位置，并交换交叉点之间的片段，并从第2交叉位置起在原先父代个体中删除将从另一父代个体交换过来的基因，然后从第2交叉位置后开始填入剩余基因。p1=2 6 4|7 3 5 8|9 1p2=4 5 2|1 8 7 6|9 3,北京交通大学计算机与信息技术学院,16,2023/6/25,2 6 4|7 3 5 8|9 1,4 5 2|1 8 7 6|9 3,p1=4 3 5|1 8 7 6|9 2,p2=2 1 6|7 3 5 8|9 4,遗传算法-交叉（续）,单位置次序交叉（C1）类似于OX。选择一个交叉位置，保留父代个体p1交叉位置前的基因，并在另一父代个体p2中删除p1中保留的基因，将剩余基因填入p1的交叉位置后来产生后代个体p1。如父代个体同前，交叉位置为4，则后代个体为p1=2 6 4 7|5 1 8 9 3，p2=4 5 2 1|6 7 3 8 9线性次序交叉（LOX）与OX相比，仅填入基因起始位置不同：首先随机确定两个交叉位置，并交换交叉点之间的片段；在原先父代中删除将从另一父代个体交换过来的基因，然后从第1个基因位置起依次在两个交叉位置外填入剩余基因。如父代个体和交叉点同前，则片段7 3 5 8和1 8 7 6将交换，在p1中删除1 8 7 6后剩余2 4 3 5 9，然后将其填入p1，得到 2 4 3|1 8 7 6|5 9，相应地p2=4 2 1|7 3 5 8|6 9,北京交通大学计算机与信息技术学院,17,2023/6/25,遗传算法-交叉（续）,基于位置的交叉（PX）与OX类似，只是它不再选取连续的基因片段，而是随机选取一些位置，然后交换被选中位置上的基因，并在原先父代个体中删除从另一父代个体交换过来的基因，接着从第一个基因位置起依次在未选中位置填入剩余基因。如父代个体同前，假设随机选取的位置点为2、3、6、8，则后代为p1=6 5 2 4 3 7 8 9 1，p2=2 6 4 1 8 5 7 9 3。循环交叉（CX）,北京交通大学计算机与信息技术学院,18,2023/6/25,遗传算法-变异,二进制或十进制用另一种基因替换某一位置或某些位置上的基因实数编码采用扰动的方式：x=x+，其中为扰动幅度，为扰动变量组合优化互换、逆序、插入等,北京交通大学计算机与信息技术学院,19,2023/6/25,遗传算法-函数优化示例,求整数函数f(x)=x2在区间0,31上取最大值的点用基本遗传算法求解问题是求最大值点，目标函数可取为x2。用5位的二进制位串表示个体，对应区间0,31上的32个整数。随机地选取4个位串作为初始种群，位串与对应的整数如下：011011311000240100081001119,北京交通大学计算机与信息技术学院,20,2023/6/25,根据目标函数，对每个位串计算适值为每个位串指定一个与其适应值成正比的繁殖概率根据遗传操作生成下一代种群假设选择的两对父代个体分别为1和2，2和4,北京交通大学计算机与信息技术学院,21,2023/6/25,交叉过程（假设使用单点交叉，交叉概率pc=0.95）位串1、2：0 1 1|0 10 1 1|0 01 1 0|0 01 1 0|0 1 位串2、4：1 1 0|0 01 1 0|1 11 0 0|1 11 0 0|0 0变异过程（假设变异概率pm=0.05，且此处无变异）评价第二代种群,北京交通大学计算机与信息技术学院,22,2023/6/25,遗传算法-数学解释,Holland为解释基于二进制编码的基本遗传算法建立了模式定理和隐含并行性定理模式定理的含义：在SGA中，阶次低、定义长度短且适配值超过平均适配值的模式在种群中的数目的期望值以指数级递增（遗传算法存在找到全局最优解的可能性）隐含并行性定理：遗传算法所处理的有效模式的总数约与群体规模的三次方成正比积木块假设的含义：通过短定义距、低阶及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解（说明在遗传算子的作用下能生成全局最优解）,北京交通大学计算机与信息技术学院,23,2023/6/25,遗传算法-改进,编码方式的改进二进制编码使得个体串很长（特别是精度要求较高的时候）根据需要采用格雷编码、浮点数编码、自然数编码等对遗传操作的改进改进选择策略、交叉算子、变异算子对控制参数的自适应调整，如自适应调整交叉概率和变异概率等对执行策略的改进混合遗传算法、小生境技术、免疫遗传算法、单亲遗传算法、并行遗传算法,北京交通大学计算机与信息技术学院,24,2023/6/25,遗传算法-欺骗问题,完全欺骗问题一致欺骗问题序列欺骗问题基本欺骗问题具体请参考：李敏强,寇纪淞.遗传算法的模式欺骗性分析.中国科学(E辑),2002,32(1):95-102.,北京交通大学计算机与信息技术学院,25,2023/6/25,遗传算法-欺骗问题举例,设编码空间0,13上的最优解位串为“11l”，若模式适应值满足：f(0*)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阶模式欺骗问题。,北京交通大学计算机与信息技术学院,26,2023/6/25,遗传算法-主要特点,处理参数集合的编码，而不是参数本身始终保持整个种群而不是个体的进化；即使某个体在某时刻丢失了有用的特性，这种特性也会被其它个体保留并发展下去只需要知道问题本身所具有的目标函数的信息，且不受连续、可微等条件的约束，因而具有广泛的适用性启发式搜索，可适用于有噪声和多峰值的复杂空间,北京交通大学计算机与信息技术学院,27,2023/6/25,主要内容,智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-Genetic Algorithm群智能优化算法蚁群优化算法-Ant Colony Optimization粒子群优化算法-Particle Swarm Optimization,北京交通大学计算机与信息技术学院,28,2023/6/25,群智能优化算法,群智能优化算法是一种近年来新兴的优化方法，其模拟社会性动物的各种群体行为，利用群体中个体间的信息交互和合作来实现寻优目的群智能优化算法包括很多算法，如人工蜂群算法和人工鱼群算法等，不过研究比较深入、应用比较广泛的是蚁群优化算法和粒子群优 化算法。也有人将遗传算法和差分演化算法（Differential Evolution Algorithm）归入群智能优化算法中。,北京交通大学计算机与信息技术学院,29,2023/6/25,与基于梯度的优化算法不同，群智能优化算法依靠的是概率搜索，其优点是：无集中控制约束，不会因个别个体而影响整个问题的求解，确保了系统的鲁棒性以非直接的信息交流方式确保了系统的扩展性并行分布式算法模型对问题定义的连续性无特殊要求算法实现简单,北京交通大学计算机与信息技术学院,30,2023/6/25,主要内容,智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-Genetic Algorithm群智能优化算法蚁群优化算法-Ant Colony Optimization粒子群优化算法-Particle Swarm Optimization,北京交通大学计算机与信息技术学院,31,2023/6/25,蚁群优化算法(Ant Colony Optimization),蚁群优化算法（蚂蚁算法），是一种分布式智能模拟算法由M.Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为基本思想是模拟蚂蚁依赖信息素进行通信而显示出的社会行为是一种随机的通用试探法，可用于求解各种不同的组合优化问题初始的蚁群优化算法是基于图的蚁群系统，过程如下（以求解对称的TSP问题为例）：,北京交通大学计算机与信息技术学院,32,2023/6/25,问题的描述：n个城市N=1,2,n，任两城市的边A=(i,j)|i,j N，城市间的距离为D=(dij)nn设有m只蚂蚁，其出发城市可随机确定路径的构造为TSP图中的每一条弧(i,j)赋信息素初值ij(0)，通常的做法是随机生成一个解，设其目标值为f0，则ij(0)=1/f0设置城市间的启发式信息ij，通常ij=1/dij设第k只蚂蚁在城市i，则其根据下面的概率选择下一个城市：其中另外，每一蚂蚁有一个表list，用于记录其访问过的城市；当访问了所有的城市后，就可以在其经过的路径上更新信息素,北京交通大学计算机与信息技术学院,33,2023/6/25,与表示信息素与启发式信息的相对重要程度，通常=1或2，=2或3,表示蚂蚁k可选的城市集合，即其还未访问过的城市集合,信息素更新策略（局部更新）所有蚂蚁周游完成后更新信息素：首先以一定的比例(1-)减少每条边上的信息素（表示信息素的挥发），然后更新各自路径上的信息素，即更新信息素的方式为其中信息素的挥发机制可以避免信息素大量积累，也体现了生物界的“遗忘”现象；表示蚂蚁k在边(i,j)上留下的信息素，如果蚂蚁没有经过该边，则其留下的信息素为0，即其中，表示蚂蚁k构造的路径的长度，Q是一常数（比如1）此机制体现了：构造的路径越短，蚂蚁留下的信息素越多；某边经过的蚂蚁越多，其上积累的信息素也就越多,北京交通大学计算机与信息技术学院,34,2023/6/25,全局更新：对于一次迭代中最好的那只蚂蚁，单独更新其经过路径上的信息素上面的蚁群优化算法的不足信息素的累积造成“停滞”现象：蚂蚁基本上走同一条路径要得到更好的优化能力往往需要与局部搜索算法结合：对最好的路径执行局部搜索蚁群算法的改进精英策略：对已发现的最好路径给予额外的增强，从而增大较好路径的选择概率负反馈机制：蚂蚁走过一条边时，立即减少该边上的信息素，以减少该边再次被选中的概率Max-Min蚂蚁系统：将信息素的浓度限制在min,max的范围内，避免搜索停滞T.Stutzle,H.Hoos,MAX-MIN Ant System,FGCS,2000,16:889-914,北京交通大学计算机与信息技术学院,35,2023/6/25,蚁群优化算法-较成功的算法,北京交通大学计算机与信息技术学院,36,2023/6/25,蚁群优化算法-较成功的应用,北京交通大学计算机与信息技术学院,37,2023/6/25,蚁群优化算法-较成功的应用(续),北京交通大学计算机与信息技术学院,38,2023/6/25,M.Dorigo,T.Stutzle著,张军等译,蚁群优化,清华大学出版社,2007.,主要内容,智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-Genetic Algorithm群智能优化算法蚁群优化算法-Ant Colony Optimization粒子群优化算法-Particle Swarm Optimization,北京交通大学计算机与信息技术学院,39,2023/6/25,粒子群优化算法(Particle Swarm Optimization),粒子群优化算法（Particle Swarm Optimization,PSO,也称为微粒群优化算法）是由Kennedy和Eberhart于1995年提出来的所谓粒子是指不考虑群体中的成员的质量和体积，只考虑速度和加速状态,北京交通大学计算机与信息技术学院,40,2023/6/25,设第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。,北京交通大学计算机与信息技术学院,41,2023/6/25,粒子群优化算法-基本原理,(1)初始化：随机生成一群规模为m的微粒，包括位置和速度(2)评价：计算每个微粒的适应度(3)更新Pbest：对每个微粒，将其适应值与其经历过的最好位置做比较，如果较好，则将其位置作为该微粒的当前最好位置Pbest(4)更新gbest：对每个微粒，将其适应值与全局最好位置做比较，如果较好，则将其记为gbest(5)更新vid和xid：根据上述公式改变微粒的速度和位置(6)如达到满意的适应值或预设的最大代数Gmax，则结束，否则转(2),北京交通大学计算机与信息技术学院,42,2023/6/25,粒子群优化算法-基本过程,粒子群优化算法-参数设置,最大速度Vmax：决定了空间搜索的粒度，通常设为每维变化范围的10%到20%惯性权重w：使粒子保持运动惯性，使其具有扩展搜索空间的趋势，有能力探索新的区域。为了使算法在前期有较高的搜索能力，在后期有较快的收敛速度，可令w随时间线性减小，如由1.4到0，由0.9到0.4，由0.95到0.2等加速常数c1和c2：通常可固定为2。,北京交通大学计算机与信息技术学院,43,2023/6/25,最后，我们赞同“无免费午餐”的观点，因此应尽可地了解问题的本身特点，针对问题给出算法设计，绝不能无目的的模拟计算,北京交通大学计算机与信息技术学院,44,2023/6/25,Beijing Jiaotong University,Beijing 100044,China,45,2023/6/25,谢谢！,