基于小生境技术的遗传优化算法改进.pdf

《基于小生境技术的遗传优化算法改进.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于小生境技术的遗传优化算法改进赵苗齐丽丽李建晶(河北工业大学计算机科学与软件学院，天津300401)[摘要】针对遗传算法用于多模态最优化问题时存在无法同时找到所有的全局最优值和尽可能多的局部最优解的现象，提出了一种基于小生境技术的改进遗传算法来提高算法的搜索能力；通过仿真实验数据表明，改进的小生境遗传算法不但具有良好的全局收敛可靠性，而且具有快的收敛速度。[关键词】小生境技术；遗传优化；收敛速度1．引言遗传算法【l】是模拟自然界生物群体进化过程的一种随机优化方法，具有不依赖于问题模型的特性、寻优过程的自适应性、隐含的并行性以及解决复杂非线性问题的鲁棒性等优点，并在

2、许多复杂优化问题都找到了令人满意的解。但大量的经验表明，标准遗传算法存在早熟收敛现象和后期搜索速度慢的缺点，使得简单遗传算法(simplegeneticalgorithm，SGA)在多模函数优化【2，4J问题上的计算性能不佳，在大量的实际优化问题的求解计算中，不仅要求在可行域内寻找全局最优解，而且往往需要搜索多个全局最优解和有意义的局部最优解，从而为决策者提供多种选择或者多方面的信息。为了能够搜索到全部全局最优解和尽量多的局部最优解，本文提出一种基于小生境技术的改进遗传算法，采用了提高全局搜索能力的基于相似个体交叉和(斗戗)确定性择优机制的小生境技术131(简称为N

3、OSI：NicheofSimilarIndividuals)，并在进化后期小生境已基本形成时，通过对遗传算法的交叉算子改进，进行境内交叉来提高局部搜索性能找到尽可能多的局部最优解。数据表明，引入小生境技术后的改进遗传算法的全局收敛和局部收敛可靠性和收敛速度明显地优于经典遗传算法。2．基于相似个体结构交叉和(时入)择优机制的小生境技术Goldber指出，在进化算法几种流行的选择机制中，(旷入)选择机制具有最强的选择压。(卜+入)选择允许斗个父代个体和入个子代个体共同竞争，确定性地选择斗个高适应值的个体进入新的种群。当在整个种群中进行随机配对的交叉操作时，用(斗+入)选

4、择能产生最快的局部收敛速度。收敛时，种群的平均适应值等于最佳个体的适应值，这说明，整个种群的个体全部相同，个体多样性损尽。因此，在应用(旷入)选择机制提供强的选择压的同时，追求个体多样性并改善交叉操作的进化就成为我们设计GAs的主要目标。在自然界中，普遍地存在“人以群分，物以类聚”的小生境现象。受生物学小生境现象的启发，在改善全局搜索性能作者简介：赵苗，女。河北宁量人。碛士。研究方向：图像处理。的设计思考中，我们把整个种群分解成若干个小生境(子种群)，每个小生境由一对具有适应值的个体所组成，小生境中的父代个体交叉操作后立即应用(2+2)选择机制，确定性地选择2个个体

5、进入下一代。变异操作按概率进行，仅对种群中最佳个体变异时应用(1+1)选择，以保证全局的收敛性，对其它个体仅做随机变异，不作选择。全体小生境在其内部完成一代进化操作后在整个种群范围内进行重构。设小生境的数量为m，小生境的规模为n，这--4,生境技术GAs(简称为NOSI)的简单描述为：将种群中mxn个个体按适应值大小排序后，自然地形成m个由n个相似个体构成的小生境。小生境中的交叉操作降低了子代个体的不确定性，(2+2)选择提供了最强的选择压，两种机制的共同作用可获得最快的局部搜索速度。rfl个小生境并行地进化，在获得最快的局部收敛速度的前提下增加了在互不相交的子空间

6、中独立地进行搜索的概率，减少了整个种群局部收敛的可能性。随机变异和重构操作使NOSI在整个搜索空间中动态地构造小生境，为全局收敛提供了可靠的保证。交叉操作后的(2+2)选择和最佳个体变异后的(1+1)选择隐含了最佳个体保留机制，因此，能使NOSI收敛到全局最优解。算法的流程如下：随机地生成规模为mxn的初始种群计算每个个体的适应值，构造m个小生境while(种群不满足停止规则时)将种群中全体个体按适应值大小排序；将排序后的种群顺序地配成n对父代个体；对每对父代个体的基因进行重组，父代与子代共同竞争作(2+2)选择；按概率作随机变异操作，若为最佳个体，则作(1+1)选

7、择；重新计算适应值endwhile3．境内交叉算子要实现境内个体交叉，首先要将种群中的个体进行小生境聚类，也就是要将种群中的个体分属到某个小生境当中。一39—该算法按照个体的共享度进行排序。共享度高的个体将会被确定为小生境的中心，所有与该中心个体距离小于小生境半径阈值的个体将被划分到该小生境当中。境内交叉算子不允许两个不同小生境的个体进行交叉操作，而是从同一个小生境中任选两个个体进行简单算术交叉操作。假设个体A和B是同-d,生境的两个父代个体，则通过交叉操作得到的两个子代个体x和Y分别为：(a∈【0，l】)f)(寻O[XA十(1咀)XBIY=(1·a)x№xB经