随机蛙跳算法和NSGA2算法

《随机蛙跳算法和NSGA2算法》由会员分享，可在线阅读，更多相关《随机蛙跳算法和NSGA2算法（32页珍藏版）》请在金锄头文库上搜索。

1、智能算法及应用技术结课综述Name: MoonlightranEmail: 目录1. 随机蛙跳(SFLA)算法11.1 SFLA 理论基础11.2 SFLA 的基本原理31.3 SFLA 的基本概念41.4 SFLA 的参数设置41.5 SFLA 的运算流程51.6 SFLA函数优化中实例101.7粒子群算法(PSO )函数优化142. 多目标优化算法(NSGAII)192.1 多目标优化问题描述192.2 基本概念192.3非支配排序算法(NSGA)202.4带精英策略的非支配排序遗传算法(NSGAII)222.5 NSGA-II函数优化实例27单目标和多目标优化算法介绍随机蛙跳算法和带精英

2、策略的非支配排序算法通常的优化问题可以分为单目标优化问题和多目标优化问题。针对这两类问 题，分别介绍随机蛙跳算法(SFLA)和带精英策略的非支配排序算法(NSGAII), 并且给出这两类算法在函数优化中的应用实例。1随机蛙跳(SFLA)算法随机蛙跳算法是由 Kevin Lanes 和 Mustafa Eusuff 于 2003 年共同提出，该算 法结合了基于遗传特性的模因算法和基于行为的粒子群算法的优点，适合解决各 类组合优化问题。混合蛙跳算法具有设置参数少、简单易于理解、鲁棒性强等特 点，已在语音情感识别、作业车间调度、复杂函数优化问题求解等领域得到成功 应用。1.1 SFLA 理论基础SF

3、LA 是一种群体仿生类启发式进化计算方法，该算法将模因算法和粒子群 优化算法的思想相结合，并经过适度扩展，因而兼具二者的优点。作为 SFLA 的理论基础，模因算法和粒子群优化算法有必要进行简要介绍。1.1.1模因算法Moscato 受 Dawkin 提出的 meme 概念的启示，于 1989 年首次提出了模因算 法。该算法源于文化进化理论中的隐喻思想，结合了全体成员参与搜索的思想和 有选择性的特定个体搜索的机制，可以通过启发式搜索解决优化问题。模因算法 在原理上与遗传算法很相似，不同的是该算法在原始遗传算法步骤中的交叉和变 异步骤之后增加了一个小范围的局部进化过程，故模因算法也曾被叫做增加了局

4、 部搜索功能的遗传算法。给出模因算法的运算流程如图 1.1 所示。图 1.1 模因算法流程1.1.2粒子群算法Kennedy 和 Eberhart 受鸟群的群体飞行特性启发于 1995 年提出粒子群优化 算法，该算法是一种基于群体智能的自适应优化计算方法。假设有一群鸟，其中 的所有个体均被称作一个“粒子”，这样的“粒子”被赋予速度和位置两种属性，在 可行域中按照一定的规则飞行，目标是经过一定的进化次数找出待解问题的最佳 参考方案。进化过程中，所有个体不断追随两个关键的极值以调整自己的位置和 速度。其中一个极值是该粒子本身搜索到的最佳位置 P ，即粒子自身的最优值； best 另外一个是粒子群中

5、的所有成员中当前最优个体所在的位置 G ，即全局最优解。粒子群优化算法中个体的速度、位置更新公式如下： bestVk+i = k-iVk + c rand()(Pk - Xk) + c rand()(Gk - Xk) (1.1)i i 1 ibest i 2 bestiXk+1 = Xk +Vk+1(1.2)i ii其中，Vk为第k次迭代中第i个粒子的速度。iXk为第k次迭代中第i个粒子的位置。iPk 为第 k 次迭代中第 i 个粒子的自身最优位置。ibestGk 为第 k 轮进化中的全局最优位置。bestRand()为位于范围0,1之间的随机数。为粒子的惯性因子，C为粒子的认知因子，控制Pk

6、移动的幅度。1ic为粒子的社会因子，控制Gk移动的幅度。2粒子群优化算法的运算流程为：Stepl：初始化粒子的速度和位置。Step2 :计算所有粒子的适应值。Step3:比较各个粒子的当前适应值与其历史最优位置P的适应值，如果前best者优，则置此粒子当前最佳位置为 P 。bestStep4：比较各个粒子的当前适应值与其全局最优位置G 的适应值，若前best者优，则置此粒子当前全局最佳位置为G 。bestStep5：采用式(1.1)和式(2.1)更新种群中个体的速度和位置。Step6：判断：若满足停止准则，则算法终止，否则转Step2。上述两种算法核心思想的有机结合，即形成了所研究的混合蛙跳算

7、法。1.2 SFLA 的基本原理SFLA 是基于群体智能的仿生类优化算法，种群（解集）由一些具有相同结 构的青蛙（解）组成。SFLA模仿了青蛙群体的集体觅食活动。为了寻找当前有限的食物源，在空间受限的一块区域内，一群青蛙首先按一 定规则找准各自的初始位置。位置确定后，每只青蛙开始利用各自携带的个性化 信息在自己所在位置附近寻找食物更丰富的位置，并通过跳跃更新自己的位置。 寻找的规则是，蛙群通过充分发挥自身的自组织性，分别由个数基本相同的青蛙 组团搜索，形成局部范围内的小团体，即为子种群。子种群内部，由局部精英个 体带领其它个体进行搜索。每个子群搜索结束之后，所有个体重新组织起来，混 合后重新按

8、照规则分组，再执行组内搜索。组团搜索和群体混合迭代执行，直至 找到最丰富的食物源。对于SFLA,每只青蛙被看作一个候选解，确定初始位置即为青蛙种群的初 始化过程。组团搜索对应于种群的划分并执行局部搜索，此过程是 SFLA 最核 心的步骤，本质上青蛙个体的位置更新发生于此阶段。子群的混合形成算法的混 合运算，即全局信息交换。全局信息交换与局部深度搜索相互作用，为SFLA跳 出局部极值提供了保证。1.3 SFLA 的基本概念1青蛙：承载思想与信息的个体，构成种群的元素。2种群：由一定数量的青蛙组成的集合。3子种群：种群的子集。由所有青蛙构成的群体根据相应规则被划分为多 个并行、独立的子集，这些子集

9、被称为子种群，即局部小团体。4适应度：用来评价青蛙个体好坏的度量标准。5局部搜索：子种群内部个体的更新操作。按照一定的更新机制，子群内 部的青蛙个体执行跳跃操作，从而消息得以在小团体内部传播和扩散。6混合运算：将各个子种群合并为一个种群的操作。将各个局部小团体进 行合并，形成一个统一的群体，便于个体间的信息交流，为下一轮进化提供条件。7. 控制参数：SFLA执行需要的控制参数，主要有：所有青蛙个体总数（种 群规模），最大混合迭代次数，局部小团体（子种群）的个数，子种群内部进化 代数，各局部团体中青蛙的个数，青蛙个体的维数，青蛙最大跳动步长等。8. 执行终止条件：（1）在若干连续进化代数内，全局

10、最优解没有得到刷新；（2）算法执行到初始设定的最大混合迭代次数。满足二者之一，算法即被强制终止。1.4 SFLA 的参数设置SFLA的参数设置对算法的搜索性能具有非常重要的影响。SFLA主要包括 五个关键的参数，具体为：群体中青蛙个体数量F，算法的最大混合迭代次数G, 子种群数量m，各子种群的局部进化代数N,青蛙的最大允许跳跃距离D 。maxSFLA 的参数设置具体解释如下：（1）群体中青蛙个体数量F：又称种群规模，指所有青蛙个体总数。一般 而言是算法最重要的参数。青蛙个体数量越多，算法搜索到全局最优值的可能性 也相应越大，但太大的种群规模会对搜索速度造成不利影响。（2）算法的最大混合迭代次数

11、G：此参数需要合理设置，如果G过大，则 导致算法复杂度增加；相反，如果 G 太小，将造成青蛙种群之间缺乏交流，影 响青蛙向最优个体靠近。该参数的选取一般与问题的规模相关，规模越大，G的 取值也相应越大。（3）子种群数量m：此参数也需要合理地选择，m如果过小，导致每个子 种群内部青蛙个数过多，参与局部搜索的个体相应过少，因此信息难以在子种群 间充分交换，失去局部搜索的优势；但当 m 太大时，会造成每个子种群规模太 小，因此会削弱局部模因搜索的优势，造成算法易于早熟收敛。（4）各子种群的局部进化代数N：此参数也需要合理设置，过小的N会造 成子种群内部青蛙个体频繁跳跃，减少了局部个体信息交流的机会；

12、反之，若N 过大，将会增加局部区域内算法早熟的可能性。（5）青蛙的最大允许跳跃距离D :此参数可在一定程度上控制算法的全max局寻优能力。若D 太小，青蛙将在局部小范围跳动，容易陷入局部最优，削弱max算法的全局搜索能力；而如果D 过大，青蛙将在可行域内大步跳跃，又容易造max成错过最佳寻优位置。SFLA 的研究起步相对较晚，就算法的参数设置而言，学术界尚未形成可遵 循的指导性原则，多数情况下通过仿真实验测试得到一组设置。这也给不同学者 针对经典SFLA的改进效果对比造成了一定困难。1.5SFLA 的运算流程SFLA 首先从可行域中随机地产生一组初始解构成初始种群，每个解对应于 一只青蛙；接着

13、计算各个青蛙的适应度值，按照适应度降序排列；然后以某种规 则把整个青蛙种群划分为一定数量的子种群，在每个子种群内执行局部搜索，即 根据指定的策略更新子种群内的最差青蛙，促使被更新个体向局部最优位置靠近 子种群进化结束后，各子种群之间进行信息交换实现混合运算。交替执行局部搜 索和混合运算直至满足停止条件。为说明 SFLA 的算法机理，以函数优化问题为例进行研究，问题如下：严 f(X)(1.3) s.t. x e l, u 其中l,u:= xes 11 x u ,k = 1,2,.S。利用混合蛙跳算法求解该问题 kkk时，分为四个步骤：1. 初始化2.子种群划分3. 局部搜索4. 其种群混合1.5

14、.1 初始化从可行域中随机产生F个解xi,x2xf作为初始种群，问题的纬数为S, xi= xi,xixi为S纬空间的一个解(i = 1,2,F)。经典的SLFA初始化过程是12 S随机初始化的，种群分布不均匀，不利于算法在整个可行域空间上进行均匀搜索，进而有影响了算法的全局寻优的缺点，算法的初始化过程如图2中的伪代码所示:1.初始化I = I F do%对毎个个体班行初始化并计算适应度值For j - .S dox(jj)二 rand (LAX-MIN) - MIN %随机初始化；：id forp(f) fitness(x(r?:) %计算毎牛牛体的适应度End tor图1.2经典SFLA的初

15、始化过程1.5.2子种群划分计算每个解的目标函数值f 3)(i二1,2,F)，将目标函数值按照降序排列，并且将目标函数的最优值记为xg作为整个种群的最优解。将整个种群划分为m个子种群Y, Y，Y，每个子种群包含n个解，即满足F = m*n。其中，第一个 1 2 m解进入Y，第二个解进入Y，直到第m个解进入Y ,然后将第m +1个解进入Y， 12m1以此类推，直至所有的解分配完毕。每个子种群中，目标函数最好和最差的解分别记为xb和xw。经典混合蛙跳算法中子种群的划分如图1.3中伪代码所示：2. 了种帶划分For t- .G do % G表示混介迭代次数For i二1: F此 按照适应度降序对全部个体进行排序和族群划分Foi- j=:(F-i)do if (心5 + 1) swap(XjXXj+l)End forEnd forEnd for/c 1bor i- . n doFor j - m dovKj；匸)一兀伉；k-k