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

遗传算法与群智能优化算法简介主要内容智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-GeneticAlgorithm群智能优化算法蚁群优化算法-AntColonyOptimization粒子群优化算法-ParticleSwarmOptimization...北京交通大学计算机与信息技术学院22022/10/19智能优化算法简介20世纪80年代以来，一些优化算法得到发展GA、EP、ACO、PSO、SA、TS、ANN及混合的优化策略等基本思想：模拟或揭示某些自然现象或过程为用传统的优化方法难以解决的NP-完全问题提供了有效的解决途径由于算法构造的直观性与自然机理，因而通常被称作智能优化算法（intelligentoptimizationalgorithms），或现代启发式算法（meta-heuristicalgorithms）[智能优化算法及其应用，王凌，清华大学出版社，2001]北京交通大学计算机与信息技术学院32022/10/19智能优化算法简介-问题的NP-完全特性求解n个城市的TSP问题。典型的组合优化问题，是NP-完全的要准确求解该问题只能用枚举类的办法要枚举的解的个数为(n-1)!例：n=24，则要枚举的解的个数为：

23!=25,852,016,738,884,976,640,000北京交通大学计算机与信息技术学院42022/10/19n2425262728293031时间1s24s10m4.3h4.9d136.5d10.8y325y北京交通大学计算机与信息技术学院52022/10/19北京交通大学计算机与信息技术学院72022/10/19智能优化算法简介-常用的智能优化算法遗传算法（GeneticAlgorithm，GA）演化规划（EvolutionaryProgramming，EP）蚁群优化算法（AntColonyOptimization，ACO）粒子群优化算法（ParticleSwarmOptimization，PSO）模拟退火算法（SimulatedAnnealing，SA）禁忌搜索算法（TabuSearch，TS）人工神经网络（ArtificialNeuralNetwork，ANN）…北京交通大学计算机与信息技术学院82022/10/19遗传算法(GeneticAlgorithm)1975年，Holland出版了著名的《AdaptationinNaturalandArtificialSystems》，标志着遗传算法的诞生。在一定程度上解决了传统的基于符号处理机制的人工智能方法在知识表示、信息处理和解决组合爆炸等方面所遇到的困难基于“适者生存”原则，是并行优化算法，其自组织、自适应、自学习及群体进化的能力适合大规模复杂优化问题将问题求解表示为“染色体”，通过选择（selection）、交叉（crossover）和变异（mutation）操作的迭代，实现种群的演化，最后终收敛到“最适应环境”的个体，从而求得问题的最优解（满意解）北京交通大学计算机与信息技术学院102022/10/19遗传算法-简单遗传算法简单遗传算法（SimpleGeneticAlgorithms，SGA），又称基本遗传算法、标准遗传算法基于二进制编码，是最基本的遗传算法，其遗传进化操作过程简单、容易理解，是其他遗传算法的雏形和基础三种基本操作选择：通常用比例选择，即选择概率正比于个体的适配值，使适配值高的个体在下一代中被选中的概率大，提高种群平均适配值交叉：交换两父代个体的部分信息构成后代个体，使得后代继承父代的有效模式，有助于产生优良个体变异：随机改变个体中的某些基因，有助于增加种群多样性，避免早熟收敛北京交通大学计算机与信息技术学院112022/10/19北京交通大学计算机与信息技术学院122022/10/19随机产生N个个体构成初始种群P(0),令k=0对种群P(k)中各个体进行评价终止？令m=0从种群中选择两个体rand()>pc将所选个体作为临时个体对临时个体以概率pm执行变异操作，产生两个新个体并放入P(k+1)中，令m=m+2对选中个体执行交叉操作生成两个临时个体输出优化结果m<N？ynynyn遗传算法-交叉用于组合出新的个体，在解空间中进行有效搜索，同时降低对有效模式的破坏概率二进制编码的GA通常采用单点交叉和多点交叉。单点交叉：随机选定一个交叉位置，然后对换交叉点后的子串。多点交叉：随机选择多个位置，然后对换相应子串。两点交叉：北京交通大学计算机与信息技术学院142022/10/1910110010001110101100100011101001110001010110011100010101遗传算法-交叉（续）实数编码的GA通常采用算术交叉：双个体算术交叉：x1、x2为父代个体，α∈(0,1)为随机数

x1'=αx1+(1-

α)x2

x2'=αx2+(1-

α)x1多个体算术交叉：x1,…,x2为父代个体;αi∈(0,1)且∑αi=1

x'=α1x1+α2x2+…+αnxn

组合优化中的置换编码GA通常采用部分映射交叉(partiallymappingcrossover,PMX)：随机选择两个交叉点，交换交叉点之间的片段；对于其他基因，若它不与换过来的片段冲突则保留，若冲突则通过部分映射来确定最后的基因

p1=[264|7358|91] p1'=[234|1876|95]

p2=[452|1876|93] p2'=[412|7358|96]北京交通大学计算机与信息技术学院152022/10/19遗传算法-交叉（续）单位置次序交叉（C1）类似于OX。选择一个交叉位置，保留父代个体p1交叉位置前的基因，并在另一父代个体p2中删除p1中保留的基因，将剩余基因填入p1的交叉位置后来产生后代个体p1'。如父代个体同前，交叉位置为4，则后代个体为p1'=[2647|51893]，p2'=[4521|67389]线性次序交叉（LOX）与OX相比，仅填入基因起始位置不同：首先随机确定两个交叉位置，并交换交叉点之间的片段；在原先父代中删除将从另一父代个体交换过来的基因，然后从第1个基因位置起依次在两个交叉位置外填入剩余基因。如父代个体和交叉点同前，则片段[7358]和[1876]将交换，在p1中删除[1876]后剩余[24359]，然后将其填入p1'，得到[243|1876|59]，相应地p2'=[421|7358|69]北京交通大学计算机与信息技术学院172022/10/19遗传算法-交叉（续）基于位置的交叉（PX）与OX类似，只是它不再选取连续的基因片段，而是随机选取一些位置，然后交换被选中位置上的基因，并在原先父代个体中删除从另一父代个体交换过来的基因，接着从第一个基因位置起依次在未选中位置填入剩余基因。如父代个体同前，假设随机选取的位置点为2、3、6、8，则后代为p1'=[65

2437891]，p2'=[26

4185793]。循环交叉（CX）北京交通大学计算机与信息技术学院182022/10/19遗传算法-变异二进制或十进制用另一种基因替换某一位置或某些位置上的基因实数编码采用扰动的方式：x‘=x+ηξ，其中η为扰动幅度，ξ为扰动变量组合优化互换、逆序、插入等北京交通大学计算机与信息技术学院192022/10/19遗传算法-函数优化示例求整数函数f(x)=x2在区间[0,31]上取最大值的点用基本遗传算法求解问题是求最大值点，目标函数可取为x2。用5位的二进制位串表示个体，对应区间[0,31]上的32个整数。随机地选取4个位串作为初始种群，位串与对应的整数如下： 01101 13 11000 24 01000 8 10011 19北京交通大学计算机与信息技术学院202022/10/19根据目标函数，对每个位串计算适值为每个位串指定一个与其适应值成正比的繁殖概率根据遗传操作生成下一代种群假设选择的两对父代个体分别为1和2，2和4北京交通大学计算机与信息技术学院212022/10/19编号位串参数值目标函数值选择概率101101131690.144211000245760.4923010008640.055410011193610.309总计11701.000交叉过程（假设使用单点交叉，交叉概率pc=0.95）

位串1、2： 011|01 011|00

110|00 110|01

位串2、4： 110|00 110|11 100|11 100|00变异过程（假设变异概率pm=0.05，且此处无变异）评价第二代种群北京交通大学计算机与信息技术学院222022/10/19编号位串参数值目标函数值10110012144211001256253110112772941000016256总计1754遗传算法-改进编码方式的改进二进制编码使得个体串很长（特别是精度要求较高的时候）根据需要采用格雷编码、浮点数编码、自然数编码等对遗传操作的改进改进选择策略、交叉算子、变异算子对控制参数的自适应调整，如自适应调整交叉概率和变异概率等对执行策略的改进混合遗传算法、小生境技术、免疫遗传算法、单亲遗传算法、并行遗传算法北京交通大学计算机与信息技术学院242022/10/19遗传算法-欺骗问题完全欺骗问题一致欺骗问题序列欺骗问题基本欺骗问题具体请参考：李敏强,寇纪淞.遗传算法的模式欺骗性分析.中国科学(E辑),2002,32(1):95-102.北京交通大学计算机与信息技术学院252022/10/19遗传算法-主要特点处理参数集合的编码，而不是参数本身始终保持整个种群而不是个体的进化；即使某个体在某时刻丢失了有用的特性，这种特性也会被其它个体保留并发展下去只需要知道问题本身所具有的目标函数的信息，且不受连续、可微等条件的约束，因而具有广泛的适用性启发式搜索，可适用于有噪声和多峰值的复杂空间北京交通大学计算机与信息技术学院272022/10/19主要内容智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-GeneticAlgorithm群智能优化算法蚁群优化算法-AntColonyOptimization粒子群优化算法-ParticleSwarmOptimization…北京交通大学计算机与信息技术学院282022/10/19群智能优化算法群智能优化算法是一种近年来新兴的优化方法，其模拟社会性动物的各种群体行为，利用群体中个体间的信息交互和合作来实现寻优目的群智能优化算法包括很多算法，如人工蜂群算法和人工鱼群算法等，不过研究比较深入、应用比较广泛的是蚁群优化算法和粒子群优化算法。也有人将遗传算法和差分演化算法（DifferentialEvolutionAlgorithm）归入群智能优化算法中。北京交通大学计算机与信息技术学院292022/10/19与基于梯度的优化算法不同，群智能优化算法依靠的是概率搜索，其优点是：无集中控制约束，不会因个别个体而影响整个问题的求解，确保了系统的鲁棒性以非直接的信息交流方式确保了系统的扩展性并行分布式算法模型对问题定义的连续性无特殊要求算法实现简单北京交通大学计算机与信息技术学院302022/10/19主要内容智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-GeneticAlgorithm群智能优化算法蚁群优化算法-AntColonyOptimization粒子群优化算法-ParticleSwarmOptimization…北京交通大学计算机与信息技术学院312022/10/19蚁群优化算法(AntColonyOptimization)蚁群优化算法（蚂蚁算法），是一种分布式智能模拟算法由M.Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为基本思想是模拟蚂蚁依赖信息素进行通信而显示出的社会行为是一种随机的通用试探法，可用于求解各种不同的组合优化问题初始的蚁群优化算法是基于图的蚁群系统，过程如下（以求解对称的TSP问题为例）：北京交通大学计算机与信息技术学院322022/10/19问题的描述：n个城市N={1,2,…,n}，任两城市的边 A={(i,j)|i,j∈N}，城市间的距离为D=(dij)n×n设有m只蚂蚁，其出发城市可随机确定路径的构造为TSP图中的每一条弧(i,j)赋信息素初值τij(0)，通常的做法是随机生成一个解，设其目标值为f0，则τij(0)=1/f0设置城市间的启发式信息ηij，通常ηij

=1/dij设第k只蚂蚁在城市i，则其根据下面的概率选择下一个城市：

其中另外，每一蚂蚁有一个表list，用于记录其访问过的城市；当访问了所有的城市后，就可以在其经过的路径上更新信息素北京交通大学计算机与信息技术学院332022/10/19α与β表示信息素与启发式信息的相对重要程度，通常α

=1或2，β

=2或3

表示蚂蚁k可选的城市集合，即其还未访问过的城市集合信息素更新策略（局部更新）所有蚂蚁周游完成后更新信息素：首先以一定的比例(1-ρ)减少每条边上的信息素（

表示信息素的挥发），然后更新各自路径上的信息素，即更新信息素的方式为其中信息素的挥发机制可以避免信息素大量积累，也体现了生物界的“遗忘”现象；

表示蚂蚁k在边(i,j)上留下的信息素，如果蚂蚁没有经过该边，则其留下的信息素为0，即

其中，表示蚂蚁k构造的路径的长度，Q是一常数（比如1）此机制体现了：构造的路径越短，蚂蚁留下的信息素越多；某边经过的蚂蚁越多，其上积累的信息素也就越多北京交通大学计算机与信息技术学院342022/10/19全局更新：对于一次迭代中最好的那只蚂蚁，单独更新其

经过路径上的信息素上面的蚁群优化算法的不足信息素的累积造成“停滞”现象：蚂蚁基本上走同一条路径要得到更好的优化能力往往需要与局部搜索算法结合：对最好的路径执行局部搜索蚁群算法的改进精英策略：对已发现的最好路径给予额外的增强，从而增大较好路径的选择概率负反馈机制：蚂蚁走过一条边时，立即减少该边上的信息素，以减少该边再次被选中的概率Max-Min蚂蚁系统：将信息素的浓度限制在[min,max]的范围内，避免搜索停滞[T.Stutzle,H.Hoos,MAX-MINAntSystem,FGCS,2000,16:889-914]

北京交通大学计算机与信息技术学院352022/10/19蚁群优化算法-较成功的算法北京交通大学计算机与信息技术学院362022/10/19算法名称提出者年份AntSystem(AS)Dorigoetal.1991ElitistASDorigoetal.1992Ant-QGambardella,Dorigo1995AntColonySystemDorigo,Gambardella1996Max-MinASStutzle,Hoos1996Rank-BasedASBullnheimeretal.1997AntsManiezzo1999BWASCordonetal.2000Hyper-CubeASBlumetal.2001蚁群优化算法-较成功的应用北京交通大学计算机与信息技术学院372022/10/19问题类型问题名称作者年份路径规划旅行商问题Dorigoetal.1991,1996Dorigo,Gambardella1997Stutzle,Hoos1997,2000车辆路径规划Gambardellaetal.1999Reimannetal.2004有序排列Gambardella,Dorigo2000分配问题二次分配Stutzle,Hoos2000Maniezzo1999课表编排Sochaetal.2002,2003图着色Costa,Hertz1997蚁群优化算法-较成功的应用(续)北京交通大学计算机与信息技术学院382022/10/19问题类型问题名称作者年份调度问题工程调度Merkleetal.2002开放车间Blum2005子集问题集覆盖Lessingetal.2004其他约束满足Solnon2000,2002分类规则Parpinellietal.2002Martensetal.2006贝叶斯网络Camposetal.2002蛋白质折叠Shmygelska,Hoos2005M.Dorigo,T.Stutzle著,张军等译,《蚁群优化》,清华大学出版社,2007.主要内容智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-GeneticAlgorithm群智能优化算法蚁群优化算法-AntColonyOptimization粒子群优化算法-ParticleSwarmOptimization…北京交通大学计算机与信息技术学院392022/10/19粒子群优化算法(ParticleSwarmOptimization)粒子群优化算法（ParticleSwarmOptimization,PSO,也称为微粒群优化算法）是由Kennedy和Eberhart于1995年提出来的所谓粒子是指不考虑群体中的成员的质量和体积，只考虑速度和加速状态北京交通大学计算机与信息技术学院402022/10/19

设第i个粒子表示为Xi

=(xi1,xi2,…,xiD)，有最好适应值的位置记为Pi=(pi1,pi2,…,piD)，也称为Pbest。设符号g表示群体中所有粒子经历过的最好位置，也称为gbest。设Vi=(vi1,vi2,…,viD)表示粒子i的速度。在每一代，粒子i的第d