《AI-第5章 搜索与优化策略（2）.pptx》由会员分享，可在线阅读，更多相关《AI-第5章 搜索与优化策略（2）.pptx（96页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、人工智能导论5.1 概述5.2 状态空间搜索5.3 与或树搜索5.4 5.4 5.4 5.4 智能优化搜索智能优化搜索智能优化搜索智能优化搜索第五章第五章 搜索与优化策略搜索与优化策略5.4 5.4 智能优化搜索智能优化搜索NP（Non-deterministic Polynomial）问题是计算机科学领域中非常重要的一个问题。u主要涉及计算复杂性的度量u有限时间内无法精确求解的问题是保证信息安全的基石45.4.1 5.4.1 NPNP问题问题1 1确定性算法与非确定性算法FAFFAFA1 1）猜测阶段。算法）猜测阶段。算法F F猜测某个输出猜测某个输出g g是一个解。是一个解。2 2）验证阶
2、段）验证阶段。算法。算法F F用确定性算法检查这个用确定性算法检查这个g g是否真的是解是否真的是解。验证验证的结果有的结果有 是，否是，否 两种可能。若验证为是则找到了一个解。若验证为两种可能。若验证为是则找到了一个解。若验证为否则说明还没有找到解否则说明还没有找到解。因为。因为算法猜测的结果可能是错误的，所以验证算法猜测的结果可能是错误的，所以验证为否不能说明无解，只是解还暂时没有找到而已。为否不能说明无解，只是解还暂时没有找到而已。2 2判定问题与优化问题u仅仅要求回答“是”或“否”的问题。u求解判定问题的算法称为判定算法。这些算法只产生“0”或“1”作为输出，即二值决策。u寻找一个最优
3、解，使代价函数达到最优值。u如果一个优化问题可以在多项式时间内求解，则对应的判定问题也可以在多项式时间内求解；u如果一个判定问题不能在多项式时间内求解，那么与它对应的优化问题也不能在多项式时间内求解。3 3P P类与NPNP类问题u在多项式时间内使用确定性算法可解的所有判定问题的集合。u在多项式时间内使用非确定性算法可解的所有判定问题的集合。u因为任何确定性算法都可以作为一个不确定性算法的检验阶段u是否存在一个问题是NP类问题且不是P类问题4 4NPNP难与NPNP完全问题u如果任何一个NP完全问题能在多项式时间内解决，那么NP完全类中的每一个问题都存在一个多项式时间的解。ANPuANP；u对
4、于BNP，问题B可以在多项式时间内转换为问题A。NP完全NPCNP-CompleteANP难NP-HardP、NP、NP完全和NP难问题之间的关系u对任意一个NP类判定问题B，如果存在一个NP完全问题A能够在多项式时间内转换为问题B，则问题B也是NP完全的。u例如，判定一个布尔表达式是否可满足的问题（SAT问题）布尔表达式可满足是指布尔表达式可满足是指布尔表达式可满足是指布尔表达式可满足是指：对于一个布尔表达式，如果至少存在一种该表达式的赋值使整个表达式为真，则这个布尔表达式是可满足的1什么是优化问题（Optimalization Problem）u在满足一系列相关限制条件（约束）下，选择一组
5、参数（变量），使设计指标（目标）达到最优值uuuu无约束优化无约束优化无约束优化无约束优化问题和有约束优化有约束优化有约束优化有约束优化问题。u有约束优化问题又可分为等式约束优化等式约束优化等式约束优化等式约束优化问题和不等式约不等式约不等式约不等式约束优化束优化束优化束优化问题。u例如：无约束优化问题：求函数f(x)的最小值。等式约束优化问题：求当x为素数时函数f(x)的最小值。不等式约束优化问题：求当x0时函数f(x)的最小值。105.4.2 5.4.2 优化问题优化问题求解优化问题的策略u需要建立精确的数学解析式，一般要求导u例如梯度下降法、线性规划法等等u不一定总能得到理论最优解2 2
6、求解优化问题的数学解析方法u求解导数为0的点。u因为最优解肯定是极值点，其导数必定为0。u对于等式约束优化问题可通过拉格朗日乘数法将其转换成为无约束优化问题求解。u对于不等式约束优化问题可通过KKT条件(Karush-Kuhn-Tucker Condition)将其转化成无约束优化问题求解。用解析法通过迭代求解u梯度下降法、牛顿法、共轭梯度法、单纯形法等等。u蒙特卡洛（Monte Carlo）法、线性规划法、二次规划法、复合形法、拉格朗日乘数法等等。梯度下降法u用当前位置的负梯度方向作为下一步搜索方向。u梯度方向就是指定点处函数值增加幅度最大的方向。其负方向就是当前点的最快下降方向，所以也被称
7、为“最速下降法”u当目标函数是凸函数时，梯度下降法的解是全局最优解。u但是在一般情况下，梯度下降法只能得到一个局部最优解表示步长因子，f(x)表示梯度方向。步长因子可以是定值，也可以每步都变化。如果步长因子过大，则容易震荡不能收敛到极小点；如果步长因子过小，则收敛速度会非常慢牛顿法u一种在实数域和复数域上近似求解方程的方法，用于求函数零点。u用函数f(x)的泰勒级数的前面几项来寻找方程f(x)=0的根u优点：收敛速度很快，具有局部二阶收敛性。u缺点：对于高维向量求二阶导数时，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。基本牛顿法初始点需要足够“靠近”极小点，否则有可能导
8、致算法不收敛。其它迭代方法u对牛顿法改进，用正定矩阵来近似Hessian矩阵的逆，不需要每步求解复杂的Hessian矩阵的逆矩阵，从而简化了运算复杂度u不需要二阶导数，并且一般优于最速下降法u具体实现有DFP算法、BFGS算法、Broyden类算法等。u介于梯度下降法与牛顿法之间的一个方法。u仅利用一阶导数信息，但既克服了梯度下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点。u不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化问题最有效的算法之一。u所需存储量小，具有较快收敛速度，稳定性高，且不需要任何外来参数，适合于维数较高优化问题。3 3求解优化问题
9、的随机搜索法u肯定带有随机性，但又不是盲目乱搜索。u是启发式搜索，通过启发式信息合理运用随机性，尽可能概率性收敛于最优解。u对数据前后之间的依赖性要求很低，很适合于并行化实现。u爬山搜索法u模拟退火法u仿生群体法爬山搜索法u贪心算法试图在每一步中找到当前局部的最优解u爬山搜索法只接受比当前解更好或至少相等的解作为下一步当前解。u对解好坏评价是根据待解问题的目标函数值来判断。u爬山搜索法第一个解一般随机产生。然后新解可以是在当前解的邻域内随机选取或者选取最优解u算法的总迭代次数达到设定上限；u最优解没有更新的迭代次数达到设定上限；u当前解已经满足目标要求。爬山搜索法极容易陷入局部最优爬山搜索法极
10、容易陷入局部最优爬山搜索法极容易陷入局部最优爬山搜索法极容易陷入局部最优模拟退火法u当物体处于较高温度时，物体内部分子热运动比较剧烈，其随机波动的幅度很大；u当物体逐渐降温时（即退火过程），分子热运动也慢慢减缓，其随机波动幅度也逐渐下降；u最后当物体凉透之后，分子热运动处于一个稳定的能量极低点，此时就相当于收敛到了一个系统最优值。u从一较高初始温度开始，u随着温度不断下降，解空间中的跳转概率也逐渐下降；u最后概率性收敛于全局最优解。模拟退火法u初温T0：算法第0步时的初始温度，一般设置较大。u终温Tn：最低温度阈值。当温度降到此值后，则算法停止。此时的当前解就是最终解。一般终温是接近0的正数。
11、u降温系数d：降温过程一般是：Ti+1=dTi。u降温系数很关键，一般是小于1但接近1的一个值。降温系数大意味着温度衰减慢，有利于找到最优解，但是减慢了系统收敛速度。u由于允许概率地接受恶化解，所以不容易陷入局部最优。u解与初始值无关。u但是为了寻求最优解，模拟退火算法通常要求较高的初温，较慢的降温速率，较低的终止温度以及各温度下足够多次的采样。所以缺点是往往收敛过程较长。仿生群体法u受到自然界生物群体一些活动的启示，通过借鉴某种生物行为而达到优化搜索目的。u也被称为进化计算（Evolutionary Computation）、仿生计算（Bio-inspired Computation）或者群
12、体计算（Swarm Computation）。u群体性：以一个群体为模拟对象，一般称为种群（Population）。u随机性：群体中每个个体有自身的行为和活动。不同个体之间可能有较大差异。u选择性：作为个体集合的群体有明显优化方向。经过多轮迭代之后，群体可以概率性覆盖到全局最优解。u普适性：不需要对待解问题进行完整解析分析，只要对求解目标进行合理表示，然后就可以自动获得较优解。原则上这类算法可适用于任意函数类。u遗传算法（Genetic Algorithm）u蚁群算法（Ant Colony Optimization）u粒子群算法（Particle Swarm Optimization）u自适应
13、协方差矩阵进化策略算法（Covariance Matrix Adaptation Evolution Strategy）u鱼群算法，鸟群算法，放生群体法u编码表示策略：用某种方法来表示一个个体u适应函数：用一个函数来评估个体对环境的适应性，就是对一个解的好坏进行评价，所以也称为目标函数u变异算子：随机改变个体特性从而得到另一个新个体u交叉算子：把两个个体混合后得到新的个体u选择算子：从一个群体中中取出多个较优个体，用于繁衍下一代仿生群体法1 1）确定个体编码表示策略，对待解决问题进行表示；）确定个体编码表示策略，对待解决问题进行表示；2 2）随机生成）随机生成n n个不同个体构成初始种群个不同
14、个体构成初始种群X(0)=xX(0)=x1 1,x x2 2,x,xn n ；3 3）计算当前群体）计算当前群体X(t)X(t)中每个个体中每个个体x xi i的适应度的适应度F(xF(xi i)；4 4）应用选择算子产生中间代）应用选择算子产生中间代Xr(t)Xr(t)；5 5）对）对Xr(t)Xr(t)应用进化算子，产生新一代群体应用进化算子，产生新一代群体X(t+1)X(t+1)；6 6）进化代数增一，即）进化代数增一，即t=t+1t=t+1；7 7）如果不满足终止条件则转至第）如果不满足终止条件则转至第3 3）步，否则结束。）步，否则结束。1遗传算法与进化计算u从Darwin的进化论和
15、Mendel的遗传学说抽象出了基于“进化”观点的学习理论u一类模拟生物进化、自然选择过程与机制求解问题的自组织、自适应人工智能技术。u遗传算法（Genetic Algorithm）是进化计算的一个典型代表。u生物进化过程（从简单到复杂，从低级向高级）本身是一个自然的、并行的、稳健的优化过程。u这一优化过程的目标是对环境的自适应性。u生物种群通过“优胜劣汰”及遗传变异来达到进化（优化）的目的。u进化过程通过繁殖、变异、竞争和选择这四种基本形式实现。u如果把待解决的问题理解为对某个目标函数的全局优化，则进化计算就是建立在模拟生物进化过程基础上的随机搜索优化技术。245.4.3 5.4.3 遗传算法
16、遗传算法遗传算法u建立在自然选择和遗传学机理基础上的迭代自适应概率性搜索算法。u由美国Michigan大学J.H.Holland于1975年提出。uHolland提出用简单的位串形式编码表示各种复杂结构，并用简单的变换来改进这种结构。u他证明了遗传算法可以在搜索空间中收敛到全局最优解。ll26遗传算法的基本思想27产生初产生初始种群始种群计算计算适应度适应度是否满足是否满足优化准则优化准则最佳个体最佳个体选择选择交叉交叉变异变异编码编码（性状到基因）（性状到基因）解码解码（基因到性状）（基因到性状）Y YNN父父 代代子子代代开始开始结束结束28遗传算子29遗传算法的特点30遗传算法的特点2.
17、遗传算法的简单例子3132例如，一个二进制串算法如下:二进制位串与，则分别表示区间的两个端点1和233u一个个体由串长为22的随机产生的二进制串组成染色体的基因码，我们可以产生一定数目的个体组成种群，种群的大小（规模）就是指种群中的个体数目。例如产生初始种群如下：s1=x1=0.637197s2=x2=-0.958972s3=x3=1.602466 34u对于个体的适应度计算，考虑到本例目标函数在定义域内均大于0，而且是求函数最大值，所以直接引用目标函数作为适应度函数：35I.选择根据适应度大小进行选择、复制。36初始位串及适应度初始位串及适应度编号编号位串位串(s)(s)十进制值十进制值(x
18、)(x)适应度适应度(f(x)(f(x)f(x)/f(x)/f(x)f(x)1 1100010111011000101110110101000111101010001110.6371970.6371972.5863452.58634537.4%37.4%2 200000011100000000111000000001000000000010000-0.958972-0.9589721.0788781.07887815.6%15.6%3 3111000000011110000000111111000101111110001011.6024661.6024663.2506503.25065047.
19、0%47.0%37p转动这个按权重划分的转盘3次，从而产生3个下一代的种群。p这3个位串是上一代种群的复制，有的位串可能被复制一次或多次，有的可能被淘汰。p适应度最好的有较多的拷贝，平均的折中，而最差的被淘汰了。选择操作初始位串复制结果初始位串复制结果编号编号位串位串(s)(s)f(x)/f(x)/f(x)f(x)期望得到的复期望得到的复制数制数1 10110111010101101110101001010111110010101111137.4%37.4%1.121.122 20000001110000000011100000000100000000001000015.6%15.6%0.47
20、0.473 31101111000011011110000100111011111001110111147.0%47.0%1.411.4138u下面是经过选择操作的两个个体，执行单点交叉：39u假设已经以极小概率选择了s3的第5个遗传因子(即第5位)变异，遗传因子由原来的0变成1，产生新的个体为1 10 0计算该个体的适应度：401 10 0 41问题编码策略u原则一（有意义积木块编码原则）应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案。u原则二（最小字符集编码原则）应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。u目前还没有一套严密、完整的理论及评价准则
21、来帮助我们设计编码方案。这两条原则仅仅给出了设计编码方案的指导性大纲，并不适合于所有问题。42编码方法u二进制编码方案是遗传算法中最常用的一种编码方法。它所构成的个体基因型是一个二进制编码符号串。u二进制编码符号串的长度与问题求解精度有关。设某一参数的取值范围是Umin,Umax，则二进制编码的编码精度为：u假设某一个体的编码是x=blbl-1bl-2b2b1。则其对应的解码公式为：43编码方法u编码、解码操作简单易行；u交叉、变异等遗传操作便于实现；u符合最小字符集编码原则；u便于利用图式（模式）定理对算法进行理论分析。44编码方法u普通二进制编码不便于反映所求问题的结构特征。为改进这个弱点
22、，人们提出用格雷码对个体进行编码。u格雷码的编码方法：连续两个整数所对应的编码值之间仅仅有一个码位是不相同的，其余码位都完全相同。u假设有一个m位自然二进制编码为B=bmbm-1b2b1，其对应格雷码为G=gmgm-1g2g1。则由自然二进制编码到格雷码的转换公式为：u由格雷码到二进制码的转换公式为：45编码方法u任意两个整数之差是这两个整数所对应格雷码间的海明距离。这也是遗传算法中使用格雷码进行个体编码的主要原因。u自然二进制码单个基因座的变异可能带来表现型的巨大差异（例如从127变到255）。而格雷码编码串之间的一位差异，对应的参数值（表现型）也只是微小的差别。这样就增强了遗传算法的局部搜
23、索能力，便于对连续函数进行局部空间搜索。46编码方法u浮点数编码方法是指个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于其决策变量的个数。u例如，若某一个优化问题含有5个变量xi(i=1,2,5)。每个变量都有其对应的上下限。则x：5.80 6.90 3.50 3.80 5.00就表示了一个个体的基因型。u在浮点数编码方法中，必须保证基因值在给定的区间限制范围内。遗传算法中所使用的交叉、变异的遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限制范围内。47编码方法u适合于在GA中表示范围较大的数；u适合于精度要求较高的GA；u便于较大空间的遗传搜索；u改善了GA
24、的计算复杂性，提高了运算效率；u便于GA与经典优化方法的混合使用；u便于设计针对问题的专门知识的知识型遗传算子；u便于处理复杂的决策变量约束条件。48编码方法u符号编码方法是指个体编码串中的基因值取自一个无数值含义，只有代码含义的符号集。这个符号集可以是一个字母表，如A,B,C,D,；也可以是一个数字序号表，如1,2,3,；还可以是一个代码表，如C1,C2,C3,等等。u对于使用符号编码的遗传算法，需要认真设计交叉、变异等遗传运算操作方法，以满足问题的各种约束要求。u符合有意义积木块编码原则；u便于在GA中利用所求解问题的专门知识；u便于GA与相关近似算法之间的混合使用。49编码方法u一般常见
25、的优化问题中往往含有多个决策变量。例如六峰值驼背函数就含有两个变量。对这种含有多个变量的个体进行编码的方法就称为多参数编码方法。u多参数编码最常用和最基本的一种方法是：将各个参数分别以某种编码方法进行编码，然后在将它们的编码按一定顺序连接在一起就组成了表示全部参数的个体编码。这种编码方法称为多参数级联编码方法。u在进行多参数级联编码时，每个参数的编码方式可以是二进制编码、格雷码、浮点数编码或符号编码等等任一种编码方式。每个参数可以具有不同的上下界，也可以有不同的编码长度和编码精度。50遗传算子u选择算子就是从种群中选择出生命力强的、较适应环境的个体。这些选中的个体用于繁殖下一代，产生新种群。u
26、选择的依据是每个个体的适应度。适应度越大被选中的概率就越大，其子孙在下一代产生的个数就越多。u常见的选择方法有比例法、最优保存策略、无回放随机选择、排序法等等。51选择算子u比例法是一种回放式随机采样方法，也称为赌轮选择法。u基本思想：各个个体被选中的概率与其适应度大小成正比。设群体大小为n，个体i的适应度为fi，则个体i被选中的概率为：u由于随机操作的原因，这种选择方法的选择误差比较大。有时甚至连适应度比较高的个体也选择不上。52选择算子u方法：当前群体中适应度最高的一个个体不参与交叉运算和变异运算，而是用它来替换掉本代群体中经过遗传操作后产生的适应度最低的个体。u最优保存策略可保证迄今为止
27、所得的最优个体不会被遗传运算破坏。这是遗传算法收敛性的一个重要保证条件。u但是另一方面，它也容易使得某个局部最优个体不易被淘汰掉反而快速扩散，从而使得算法的全局搜索能力不强。u最优保存策略可以推广，即在每一代的进化过程中保留多个最优个体不参加遗传运算，而直接将它们复制到下一代群体中。这种选择方法也称为稳态复制。53选择算子u基本思想：根据每个个体在下一代群体中的生存期望值来进行随机选择。u操作过程：计算群体中每个个体在下一代群体中的生存期望数目ni：若某一个体被选中参与交叉运算，则它在下一代中的生存期望数目减去0.5。若某一个体未被选中，则它在下一代中的生存期望数目减去1.0。随着选择过程的进
28、行，若某一个体的生存期望数目小于0时，则该个体就不再有机会被选中。u这种选择操作方法能够较低一些选择误差，但操作不太方便。54选择算子u主要思想：对群体中的所有个体按其适应度大小进行排序，按照排序结果来分配各个个体被选中的概率。u操作过程：1.对群体中的所有个体按其适应度大小进行降序排序。2.根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体。3.以各个个体所分配的概率值作为其遗传概率，基于这些概率值用比例法（赌轮）来产生下一代群体。u由于使用了随机性较强的比例选择方法，所以排序法仍具有较大的选择误差。55交叉算子56交叉算子u单点交叉最简单，是简单遗传算法使用的交
29、换算子。u单点交叉从种群中随机取出两个字符串。假设串长为L。然后随机确定一个交叉点，它在1到L-1间的正整数取值。于是将两个串的右半段互换再重新连接得到两个新串。u单点交叉的特点是：若邻接基因座之间的关系能提供较好的个体性状和较高的个体适应度，则这种单点交叉操作破坏这种个体性状和较低个体适应度的可能性最小。57交叉算子u双点交叉是指在个体编码串中随机设置了两个交叉点，然后在进行部分基因交换。即交换两个交叉点之间的基因段。58交叉算子u将单点交叉和双点交叉的概念加以推广，可得到多点交叉的概念。即在个体编码串中随机设置了多个交叉点，然后进行基因交换。u多点交叉算子一般不太使用。因为它有可能破坏一些
30、好图式。事实上，随着交叉点数的增多，个体的结构被破坏的可能性也逐渐增大。这样就很难有效地保存较好的图式，从而影响遗传算法的性能。59交叉算子u算术交叉是指由两个个体的线性组合而产生出的两个新个体。u为了能够进行线性组合运算，算术交叉的操作对象一般是由浮点数编码所表示的个体。u假设在两个个体XtA、XtB之间进行算术交叉，则交叉运算后所产生的两个新个体是：式中，为一个参数。它可以是一个常数，此时所进行的交叉运算称为均匀算术交叉。它也可以是一个由进化代数所决定的变量，此时所进行的交叉运算称为非均匀算术交叉。60变异算子61变异算子u基本位变异是指对个体编码串中以变异概率Pm随机指定某一位或某几位基
31、因座上的基因值作变异运算。u基本位变异操作改变的只是个体编码串中的个别几个基因座上的基因值，并且变异发生的概率也比较小，所以其发挥的作用比较慢，作用的效果也不明显。u均匀变异是指分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。u均匀变异操作特别适合应用于遗传算法的初期运行阶段。它使得搜索点可以在整个搜索空间内自由地移动，从而可以增加群体的多样性，使算法处理更多的图式。u例如某变异点的新基因值可为：其中，是基因值的取值范围，r是0,1上的均匀随机数。62变异算子u均匀变异可使得个体在搜索空间内自由移动。但是另一方面，它却不便于对某一重点区域进行局
32、部搜索。u为此，我们对原有基因值作一个随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后，相当于整个解向量在界空间中做了一个轻微的变动。这种变异操作方法就是非均匀变异。u非均匀变异的具体操作过程与均匀变异相类似，但它重点搜索原个体附近的微小区域。例如某变异点的新基因值可为：其中，是非均匀分布的一个随机数，要求随着进化代数t的增加，接近于0的概率也逐渐增加。u非均匀变异可使得遗传算法在其初始阶段（t较小时）进行均匀随机搜索，而在其后期运用阶段（t比较大时）进行局部搜索。63变异算子u高斯变异是改进遗传算法对重点搜索区域的局部搜索性能的另一种方法。u所谓高斯变
33、异操作是指进行变异操作时，用一个符合均值为、方差为2的正态分布随机数来替换原有基因值。u高斯变异的具体操作过程与均匀变异相类似。64 蚁群算法(Ant Colony Algorithm)u一种模拟进化算法。u由意大利学者M.Dorigo等人对自然界中真实蚁群集体行为研究基础上，于1991年首先提出的。蚁群算法模拟了自然蚂蚁的协作过程，用一定数目的蚂蚁共同求解，用蚂蚁的移动线路表示所求问题的可行解集，通过正反馈、分布式协作和隐并行性找最优解。蚁群算法已成功应用于求解TSP 问题、任务分配问题、调度问题等组合优化问题，并取得了较好的实验结果。受其影响，蚁群系统模型逐渐引起了其它研究者的注意，并用该
34、算法来解决一些实际问题。655.4.4 5.4.4 蚁群算法蚁群算法蚁群算法原理（1）u一种群居昆虫，个体行为极其简单，而群体行为却相当复杂。u蚂蚁个体之间通过外激素(pheromone，也称为信息素)进行信息传递，能相互协作完成复杂的任务。u协作能力：一群蚂蚁很容易找到从蚁巢到食物源的最短路径,而单个蚂蚁则不能。u自适应能力：如果在蚁群的运动路线上突然出现障碍物时,它们能够很快重新找到最优路径。蚁群算法原理（2）u蚂蚁碰到一个还未走过路口时就随机选择一条路径前行，并释放出信息素。信息素浓度会随着时间衰减。u越短的路上积累的信息素越多，越长的路上积累的信息素越少。当后来的蚂蚁再次碰到这个路口时
35、，选择信息素较多的路径的概率相对较大。这样便形成了一个正反馈机制。u最优路径上的信息素越来越多，而其他路径上的信息素则随着时间逐渐减少。最终整个蚁群会找出最优路径。6768蚁群系统模型 u能察觉其它蚂蚁遗留的信息素；u能释放自己的信息素；u所遗留的信息素数量会随时间而逐步减少。u选择机制：信息素越多的路径，被选中的概率越大；u更新机制：路径越短，信息素增加越快；u协作机制：个体之间通过信息素进行交流；u随机性：单个蚂蚁个体在周围没有信息素指引时按照概率随机选择方向。蚁群算法的核心公式蚁群算法的核心公式蚁群算法的特点 1）蚁群算法是一种自组织算法）蚁群算法是一种自组织算法u算法开始时，单个蚂蚁无
36、序地进行寻找解；算法开始时，单个蚂蚁无序地进行寻找解；u一段时间迭代之后，由于正反馈机制，蚂蚁群体趋向于接近最一段时间迭代之后，由于正反馈机制，蚂蚁群体趋向于接近最优解；优解；u这是一个从无序到有序的过程这是一个从无序到有序的过程。2）蚁群算法是一种本质上并行的算法）蚁群算法是一种本质上并行的算法u每只蚂蚁的搜索过程彼此独立，仅仅依靠信息素进行通信每只蚂蚁的搜索过程彼此独立，仅仅依靠信息素进行通信。3）蚁群算法是一种正反馈的算法）蚁群算法是一种正反馈的算法u蚂蚁之所以可以找到最短路径，是依赖最短路径上的信息素堆蚂蚁之所以可以找到最短路径，是依赖最短路径上的信息素堆积而成的，而信息素的堆积是一个
37、正反馈过程积而成的，而信息素的堆积是一个正反馈过程。4）蚁群算法具有较强的）蚁群算法具有较强的鲁棒性鲁棒性u蚁群算法的求解结果不依赖初始路线的选择，而且在搜索过程蚁群算法的求解结果不依赖初始路线的选择，而且在搜索过程中不需要进行人工调整；中不需要进行人工调整；u蚁群算法的参数数目小，设置简单蚁群算法的参数数目小，设置简单。蚁群算法存在的问题u由于蚂蚁个体运动过程的随机性，当群体规模设置较大时，很难在短时间内从杂乱无章的路径中找出一条较好路径。u搜索进行到一定程度后，所有蚂蚁发现的解完全一致。此时不能进一步搜索解空间，不利于发现全局最优解。u求解结果具有较大的分散性735.4.5 5.4.5 粒
38、子群算法粒子群算法u生物群体普遍能够表现出一定智能行为，即群体智能（Swarm Intelligence）。u群(Swarm)：某种具有交互作用的组织或智能体的集合。u在群体中，个体的结构很简单，而它们的群体行为却会相当复杂。个体行为和群行为之间存在着某种紧密联系。u个体行为构成和支配了群行为；同时，群行为又影响和改变个体的自身行为。个体之间的交互在构建群行为中起到重要作用。它帮助群体改善了对环境的经验知识。u对不同群的研究得到了不同算法。其中最引人注目的是对鸟群和蚁群的研究而建立的粒子群算法和蚁群算法。粒子群算法u由Kennedy和Eberhart在1995年提出。u该算法模拟鸟集群飞行觅食
39、的行为，鸟之间通过集体的协作使群体达到最优目的。u群体智能（Swarm Intelligence）优化方法的典型代表之一。粒子群算法u一群鸟在随机搜索食物。u在这个区域里只有一块食物。u所有的鸟都不知道食物在那里，但是它们知道当前的位置离食物还有多远。u那么找到食物最简单有效的方法就是搜寻目前离食物最近鸟的周围区域。u在搜寻过程中，每只鸟的位置变化以成功超越其它个体的社会心理意向为基础。u因此一只鸟的搜寻行为受到其它鸟搜寻行为的影响。粒子群算法uPSO中每个优化问题的解都是搜索空间中的一只鸟，称之为“粒子”。u每个粒子都有一个由优化函数决定的适应值，u每个粒子还有一个速度决定其飞翔的方向和距离
40、，u所有粒子都追随当前的最优粒子在解空间中搜索。粒子群算法uPSO初始化为一群随机粒子，然后叠代找到最优解。u每一次叠代中，粒子跟踪两个极值来更新自己。一个极值是粒子本身所找到的最优解。这个解叫做个体极值pBest；一个极值是整个种群当前找到的最优解。这个极值是全局极值gBest。即，全局PSO算法。也可以不用整个种群而只用其中一部分近邻的最优位置。即，局部PSO算法。u粒子通过不断学习和更新，最终飞至空间中最优解所在的位置。KennedyKennedy和和EberhartEberhart最早提出用下列公式对粒子更新：最早提出用下列公式对粒子更新：其中，其中，c c1 1和和c c2 2是非负
41、常数，称为学习是非负常数，称为学习因子因子；r r1 1和和r r2 2是介于是介于0,10,1之间的随机数之间的随机数。假设在一个假设在一个n n维搜索空间中，有维搜索空间中，有m m个粒子组成一个群体，在某一时刻个粒子组成一个群体，在某一时刻t t：第第i i个粒子的位置为一个个粒子的位置为一个n n维向量：维向量：Xi(t)=(xXi(t)=(xi1i1,x,xi2i2,x,xinin)第第i i个粒子的飞翔速度也是一个个粒子的飞翔速度也是一个n n维向量：维向量：Vi(t)=(vVi(t)=(vi1i1,v,vi2i2,v,vinin)第第i i个粒子迄今为止搜索到的最优位置为：个粒子
42、迄今为止搜索到的最优位置为：Pi=(pPi=(pi1i1,p,pi2i2,.,p,.,pinin)整个粒子群迄今为止搜索到的最优位置为：整个粒子群迄今为止搜索到的最优位置为：Pg=(pPg=(pg1g1,p,pg2g2,.,p,.,pgngn)目标函数目标函数f计算粒子的适应度计算粒子的适应度f(Xi(t)，根据适应度大小衡量粒子的优劣。，根据适应度大小衡量粒子的优劣。粒子群算法79n由于在早期的粒子群算法中，粒子速度主要是根据粒子的当前位置和由于在早期的粒子群算法中，粒子速度主要是根据粒子的当前位置和个体最优值及全局最优值进行更新，因此很容易在算法运行后期出现个体最优值及全局最优值进行更新，
43、因此很容易在算法运行后期出现“振荡振荡”现象。现象。n所谓所谓“振荡振荡”现象是指随着粒子群中的粒子聚集在目标的周围，在全现象是指随着粒子群中的粒子聚集在目标的周围，在全局最优解的附近振荡，导致在较大的迭代次数内才能收敛于全局最优局最优解的附近振荡，导致在较大的迭代次数内才能收敛于全局最优解。解。nEberhartEberhart和和ShiShi在在19981998年将惯性因子引入粒子速度的更新公式中，即年将惯性因子引入粒子速度的更新公式中，即算法中惯性因子算法中惯性因子w随着迭代的进行由最大加权因子随着迭代的进行由最大加权因子wmax线性减小到最线性减小到最小加权因子小加权因子wmin。一般
44、是将一般是将wmax设置为设置为0.9，wmin设置为设置为0.4。粒子群算法流程图81(1)(1)随机初始化粒子群，即随机初始化粒子群，即t=0t=0时随机为每个粒子指定一个位置时随机为每个粒子指定一个位置Xi(0)Xi(0)及速度及速度Vi(0)Vi(0)；(2)(2)计算每个粒子的适应度值计算每个粒子的适应度值f(Xi(t)f(Xi(t)；(3)(3)比较每个粒子的当前适应度值比较每个粒子的当前适应度值f(Xi(t)f(Xi(t)和个体最优值和个体最优值f(Pi)f(Pi)，如果如果f(Xi(t)f(Pi)f(Xi(t)f(Pi)，那么，那么Pi=Xi(t)Pi=Xi(t)；(4)(4)
45、比较每个粒子的当前适应度值比较每个粒子的当前适应度值f(Xi(t)f(Xi(t)和全局最优值和全局最优值f(Pg)f(Pg)，如果如果f(Xi(t)f(Pg)f(Xi(t)f(Pg)，那么，那么Pg=Xi(t)Pg=Xi(t)；(5)(5)按下列公式更改每个粒子的速度矢量和位置：按下列公式更改每个粒子的速度矢量和位置：(6)(6)如果满足终止条件，则输出如果满足终止条件，则输出PgPg；否则，；否则，t=t+1t=t+1，转，转(2)(2)。全局粒子群算法过程全局粒子群算法过程82PSOPSO算法中需要调节的参数，以及经验设置：算法中需要调节的参数，以及经验设置：粒子数粒子数m(m(种群大小种
46、群大小)：一般取：一般取20-4020-40。对于比较难的问题。对于比较难的问题或者特定类别的问题，粒子数可以取到或者特定类别的问题，粒子数可以取到100100或或200200。粒子的长度粒子的长度n(n(空间维数空间维数)：这是由优化问题决定的，就是：这是由优化问题决定的，就是问题解的长度。问题解的长度。粒子的坐标范围：由优化问题决定，每一维可设定不同粒子的坐标范围：由优化问题决定，每一维可设定不同的范围。的范围。学习因子：学习因子：c c1 1和和c c2 2通常等于通常等于2 2，在一些文献中也有其它取，在一些文献中也有其它取值。但是一般值。但是一般c c1 1和和c c2 2相等，并且
47、范围在相等，并且范围在0 0和和4 4之间。之间。中止条件：最大循环数以及最小偏差要求，由具体问题中止条件：最大循环数以及最小偏差要求，由具体问题确定。确定。粒子群算法的参数粒子群算法的参数粒子群算法特点u同遗传算法类似，但没有遗传算法中的交叉和变异操作，u而是粒子在解空间追随最优粒子进行搜索。u简单容易实现，u既适合科学研究，又特别适合工程应用，u没有过多参数需要调整。根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称为。845.4.6 5.4.6 智能智能优化搜索应用案例优化搜索应用案例u经典的组合优化难题，是NPC问题u从n个城市中的一个出
48、发，u遍历其它所有城市然后回到出发城市，u每个城市必须走过并且只能走过一次，u整个环路的路径之和最小。u穷举对称型TSP时间复杂度为5.4.6 5.4.6 智能智能优化搜索应用案例优化搜索应用案例1.用遗传算法解决TSPu每一个城市用一个码（数字或者字母）表示，则城市访问序列就构成一个码串u这种编码方法所对应的交叉运算和变异运算实现起来比较困难。u常规运算会产出不满足约束或者无意义的路线1.用遗传算法解决TSP对于一个城市列表V，假定对各个城市的一个访问顺序为T=(t1,t2,tn,tn+1)规定每访问完一个城市，就从未访问城市列表W=V-t1,t2,ti-1（i=1,2,3,n）中将该城市去
49、掉然后用第i个所访问城市ti在未访问城市列表W中的对应位置序号gi(1gin-i+1)表示具体访问哪个城市如此这样一直到处理完V中所有的城市。将全部gi顺序排列在一起所得的一个列表G=(g1 g2 g3 gn)就表示一条巡回路线1.用遗传算法解决TSPu设有7个城市分别为V=(a,b,c,d,e,f,g)。对于如下两条巡回路线：Tx=(a,d,b,f,g,e,c,a)Ty=(b,c,a,d,e,f,g,b)Gx=(1 3 1 3 3 2 1)Gy=(2 2 1 1 1 1 1)1.用遗传算法解决TSPu对任意两个个体的编码串进行遗传操作之后，得到的新编码串必须对应合法的TSP路径u个体基因型和
50、个体表现型之间具有一一对应的关系。u经过遗传运算后得到的任意的编码串都对应于一条合法的TSP路径。u可以用基本遗传算法来求解TSP。u可以使用通常的单点或者多点交叉算子；u可使用常规的一些变异算子。u只是基因座gi(i=1,2,3,n)所对应的等位基因值应从1,2,3,n-i+1中选取。1.用遗传算法解决TSPu下面两个TSP个体编码经过单点交叉之后可得两个新个体T x=(a,d,b,f,c,e,g,a)T y=(b,c,a,d,g,f,e,b)Gx=(1 3 1 3 3 2 1)单点交叉Gx=(1 3 1 3 1 1 1)Gy=(2 2 1 1 1 1 1)Gy=(2 2 1 1 3 2 1