适应性精英种群策略的遗传算法用于多模函数优化.ppt

Applied soft computing 11 (2011) 20172034,Genetic algorithm with adaptive elitist-population strategies for multimodal function optimization 适应性精英种群策略的遗传算法用于多模函数优化 Yong Liang , Kwong-Sak Leung,Keywords: Genetic algorithm Multimodal optimization Niching strategy,摘要,引入了一种新技术,适应性精英种群搜索方法。此方法适应性地调整种群大小，根据个体的不相似性和新型的依赖方向的精英遗传算子，提出了一个适应性精英种群遗传算法（AEGA）,1.介绍,现实中的许多问题需要优化算法能够搜索多个最优解。近年来已经提出了各种种群多样性改进机制，使得GA通过搜索保持了种群的多样性，允许GA识别多模函数的多个最优解，但并没有说明算法对于效率的改进。多模GA的效率必须平衡两方面的矛盾：,1.介绍,精英搜索vs.多样性保持：精英策略在GA中被广泛采用，用于改善全局最优搜索能力，但精英策略关注某些“最优”个体，而减少了种群多样性，而GA又需要保持种群多样性来发现多个最优解。如何平衡精英搜索和多样性保持对于构建有效率的多模GA是很重要的。 算法有效性vs.冗余种群：许多 GA使用大规模种群来提高获得全局和多个最优解的几率。但大种群将明显增加算法计算的复杂性，并产生很多多余个体，降低了GA的效率。,2.新的适应性精英种群搜索技术,（1）个体的相对方向 对于高维的多模函数最大化问题，定义两个个体Pi和Pj的相对上升方向，为了方便定义，通过交叉产生的后代个体Ci和Cj作为参考点，通过比较父代和子代的适应度值，定义两个个体的相对方向。个体Pi相对于Pj的方向定义为： 如果f(Ci)-f(Pi)0，Pi的相对上升方向是移向Pj； 如果f(Ci)-f(Pi)=0，Pi的相对上升方向是flat； 如果f(Ci)-f(Pi)0，Pi的相对上升方向是远离Pj； 同理可以定义Pj相对于Pi的上升方向。,2.新的适应性精英种群搜索技术,（1）个体的相对方向 两个个体的相对上升方向有四种情况： Back to back: Pi远离Pj，同时Pj远离Pi； Face to face: Pi移向Pj，同时Pj移向Pi； One-way: Pi远离Pj，同时Pj移向Pi，或者Pj远离Pi，同时Pi移向Pj； Flat: f(Ci)-f(Pi)=0或f(Cj)-f(Pj)=0,Pi,Ci,Pj,Cj,Pi,Ci,Pj,Cj,Pi,Ci,Pj,Cj,Back to back,Face to face,One-way,2.新的适应性精英种群搜索技术,（2）不相似的个体 处于多模函数不同峰上的点被看做不相似的个体，依据个体的相对上升方向和个体间的距离d判断个体的不相似性。个体间距离的阈值为ds，不相似性的原则为： 如果两个个体的相对方向是back to back，或d=ds，则两个个体是不相似的并处于不同的峰上； 如果两个个体的相对方向是face to face，one-way或flat 并且dds，则两个个体是相似的并处于同一峰上。,3.基于适应性精英种群的遗传算法,基于生境迁移的动态小生境遗传聚类算法： （a）精英遗传算子 精英交叉算子用于搜索精英个体，精英变异算子用于产生并 保护处于未探索到的峰上的精英个体。 精英交叉算子： 随机选择两个个体Pi和Pj，利用交叉策略产生后代Ci和Cj；,3.基于适应性精英种群的遗传算法,精英交叉算子： 对Pi和Pj应用不相似性判断原则； 若Pi和Pj是不相似的：如果子代的适应度大于父代，则用子代替换其父代；如果所有父代和子代的适应度相同，则选择距离最大的两个个体替换父代个体。 若Pi，Pj，Ci，Cj都是相似的：如果所有父代和子代的适应度相同，则从四个个体中随机选择一个个体替换父代个体Pi；否则从四个个体中选择适应度最好的个体替换Pi。然后移去Pj。,3.基于适应性精英种群的遗传算法,精英变异算子： 随机选择个体Pi，利用变异策略产生后代Ci； 判断Pi和Ci的不相似性； 若Pi和Ci是相似的：如果f(Ci)f(Pi)，将Ci替代Pi进入下一代；如果f(Ci)=f(Pi)，则Pi进入下一代。 若Pi和Ci是不相似的：Pi直接进入下一代；将Ci与其距离阈值范围内的所有个体Pj进行比较（d(Ci,Pj)ds），如果不存在这样的Pj或f(Pj) f(Ci)，则Ci是未开发的或至少处于一个不同的峰，Ci进入下一代；如果f(Ci) f(Pj)，则移去Ci。,3.基于适应性精英种群的遗传算法,（b）种群控制条件 上述的精英交叉变异算子保留了很多低适应度的个体，降低了寻优的效率，设计如下的种群控制条件： 如果新产生的个体经过若干代后，适应度仍很低，则删除此个体； 如果种群规模由N增至（1）倍，则删除适应度低的个体。,3.基于适应性精英种群的遗传算法,（c）基于适应性精英种策略演化算法 Step 1. 初始化种群。 Step 2. 评价个体的适应度。 Step 3. 执行精英交叉和变异策略，并评价种群适应度。 Step 4. 根据种群控制条件控制种群规模。 Step 5. 重复step3step4直到到达给定的最大代数。,4.实验,比较算法,Deterministic Crowding Probabilistic Crowding Sequential Fitness Sharing Clearing Procedure Clustering Based Niching (CBN) Clonal Selection Species Conserving Genetic Algorithm (SCGA),实验,Comparing AEGA with other algorithms for finding all multiple optima of the problems in the final population of AEGA, the 100 individuals decrease to 5 individuals corresponding to the 5 multiple optima, while, on the contrary, the final population of other seven algorithms still have 100 individuals The change processes of the AEGAs population sizes Comparing AEGA with other algorithms for finding the multiple high fitness optima of the problems The effect o