基于粒子群算法的遗传算法研究
秦广军1+, 王欣艳2, 王文义3
1
郑州大学信息工程学院,郑州 (450052)
2
东北大学软件学院,沈阳 (110004)
3
中原工学院 计算机科学与技术系,郑州 (450007)
E-mail：gjqin@gs.zzu.edu.cn，wingxiny@neusoft.com.cn，zgjsj@sina.com.cn
摘 要: 针对传统遗传算法中存在的易陷入局部最优解和后期收敛速度慢的问题,基于粒子群算法,对传统遗传算法作了改进,提出了一种基于粒子群算法的遗传算法.该算法的基本思想是使用粒子群算法来构造变异算子和分割种群.通过对三个多峰函数的优化,与传统遗传算法进行比较,定量的研究了该算法.实验结果表明,该算法很好的保持了种群的多样性,有效地克服早熟现象,显著提高遗传算法的收敛速度.
关键词: 遗传算法;粒子群算法;变异算子;种群多样性;早熟收敛
1. 引言
遗传算法(Genetic algorithm)是由美国Michigan大学的J. Holland教授于1975年首先提出的,它是一种借鉴生物界自然选择机制的随机化搜索算法,其主要特点是群体搜索策略和群体中个体间的信息交换,与进化规划(EP)、进化策略(ES)以及近年来新出现的遗传程序设计(GP)共同构成了现代进化计算的四大分支.遗传算法因其简单、通用、鲁棒性强等特点,在组合优化问题求解、规划设计、机器学习和人工生命等领域中得到了广泛应用.
目前,在遗传算法的应用中,还存在着易陷入局部最优解和后期收敛速度慢的问题,基因缺失被认为是造成这一问题的主要原因.由于群体是有限的,进化后期,当某个模式在种群中占优势时,传统的遗传机制会进一步强化这种优势,破坏种群的多样性,使得多数个体非常相似,搜索区域迅速集中,陷入局部最优解,过早收敛.GA的全局收敛理论是基于进化代数的无限大为前提的,但在实际应用中,这是不可能的.变异算子有助于增加种群的多样性,但如果变异概率过小,不易产生新的个体结构;变异概率过大,又会导致搜索的盲目性、随机性变大.而且,变异操作是无方向制导的,也会导致变异得到的个体由于适应度低而被淘汰.因此,如何在有限种群规模上,有限的代数内,使用变异操作来保持种群多样性成为研究的热点.如CHC算法、变异概率可变的自适应遗传算法(AGA)、大变异算子、进化稳定策略等.这些改进取得了一定的效果,但仍然没能摆脱变异算子的随机、盲目性.
本文借鉴粒子群算法(PSO: particle swarm algorithm)的思想,提出了一种改良的变异算子(PSO变异)和种群分割策略.该算法用粒子群算法的进化公式来代替传统遗传算法中的变 作者简介:1秦广军(1977－),男,河南安阳人,硕士研究生,主要研究领域为遗传算法,集群与并行计算;
23
[1]
[2]
[3]
[4]
王欣艳(1979－),女,硕士研究生,辽宁沈阳人,主要研究领域为信息安全,软件工程; 王文义,男,河南郑州人,教授,硕导,主要研究领域为集群与并行计算,软件工程.
- 1 -
http://www.paper.edu.cn
异算子,让变异算子根据个体距离迄今最优解的远近来自动调整变异幅度和方向,总是在迄今最优解附近变异,避免了变异的盲目性;将种群分为相互重叠的多个子种群分别进化,有利于保持种群的多样性,而且子种群间的重叠也使其不会变成孤岛,同时,也可避免PSO变异算子陷入局部最优解和降低种群多样性的可能.在PSO变异算子和种群分割共同作用下,有效地避免了传统遗传算法的早熟收敛问题,不仅在子种群内增强了局部搜索能力,而且保证了进化过程中搜索空间的规模,提高了收敛速度.
2. PSO算法概述
粒子群算法(PSO)是1995年由美国普渡大学的Kennedy和Eberhart提出的一种集群优化算法,它是受鸟群和鱼群群体运动的行为方式启发而提出的一种具有代表性的集群智能方法.PSO算法中,在D维空间m个粒子组成粒子群,每个粒子都是D维搜索空间中的一个可能解.粒子在解空间中运动,并根据粒子自身迄今最优解和全种群迄今最优解动态调整进化速度和方向.
第i个粒子在D维空间中的飞行参数如下:
坐标:Yi=(yi1,yi2,......,yiD); 速度:Vi=(vi1,vi2,......,viD); 历史最优位置:Li=(li1,li2,......,liD);
整个粒子群的所有粒子在D维空间中的历史最优坐标为:Lg=(lg1,lg2,......,lgD); 粒子在飞行过程中根据Li和Lg按公式①调整速度和位置:
⎧vid(t+1)=vid(t)+c1⋅r1⋅(lid(t)−yid(t))+c2⋅r2⋅(lgd(t)−yid(t))
⑴ ⎨
ytytvt(+1)=()+(+1)idid⎩id
2]上的常数,称为权重因子;r1、r2为式中t为进化代数,d(1≤d≤D)为维数;c1、c2为[0，
[0，1]上的随机数,每次计算时都重新产生.
与GA算法基于达尔文“适者生存,优胜劣汰”的思想不同,PSO算法是通过个体之间的协作来寻找最优解,它利用了生物群体中信息共享会产生进化优势的思想.GA算法中所有个体都竞争成为最优解,在竞争过程中,个体间互相共享信息,所以整个种群的移动是均匀的向最优区域移动,但是这种相互共享机制和个体间的相互淘汰,会导致种群多样性的丧失;而PSO算法中则是所有个体并行进化,只有群体的最优位置传递信息给其它粒子,这是单向的信息流动,个体之间不直接共享信息,整个搜索更新过程是跟随当前最优解的过程,这有利于维护种群的多样性.GA算法的个体不具有记忆功能,每个个体只反映其目前状态,其进化幅度和方向不能适时调整;PSO算法的个体(粒子)则具有记忆功能,可根据历史信息和当前状态来指导控制进化幅度和方向,多数情况下,所有粒子都能更快的收敛于最优解.
3. 基于粒子群算法的遗传算法(PSOGA)思想和实现
传统的变异算子是对群体中的部分个体实施随机变异,与历史状态和当前状态都没有关系,也不考虑和最优解的距离.在进化初期,这有利于局部搜索和增加种群的多样性;在进化后期,当群体趋于稳定时,它又会破坏这种稳定.变异概率过大时,遗传模式被破坏的可能性也越大,使得具有高适应度的个体结构很快被破坏;但是过小,又会使搜索过程缓慢,以致停滞不前.
- 2 -
http://www.paper.edu.cn
为了避免这种盲目性和维护种群的多样性,本文将粒子群算法引入,改进了种群分割
[5,6,7,8]
策略,用PSO算法重构变异算子.
PSOGA算法的整体思路是,让遗传算法从宏观来看,类似PSO算法,以利用PSO算法的个体间协作进化的机制;而微观上,进化过程仍然是GA算法.
3.1 种群分割
从第1节GA和PSO的对比中可以看出,PSO算法PSO的优点在于个体间是协作而非竞争,这使得PSO算法可以很好的维护种群多样性.种群的分割就是模拟PSO算法的这一特点,将GA算法的种群分成大小不同的若干个子种群,这些子种群就相当于PSO中的粒子.它们之间可以相互部分覆盖,覆盖的目的是为了在这些子种群间隐性的进行信息交换,避免因分割而造成进化孤岛.通过覆盖,各子种群可以相互协作并行进化,而不再是竞争;竞争只发生在相邻两个子种群中被覆盖的小区域内.
设总进化代数为T,当前进化到第t代,总种群为Πt={xt1,...,xti,...,xtn},(1≤i≤n),n为种群规模,且对于任意1≤i 这种带有覆盖的种群分割策略,有利于保持种群的多样性,同时也可避免在进化后期陷入某个局部区域. 当进化相邻的下一个窗口时,可能已经计算出的最优解不再是最优,这时需要重新修订它.因此,对于α的选取,要尽可能小,以尽量减少修订带来的额外操作;但是必须有,以保证窗口间信息的交换.此外,因为处在这个区域内的个体在相邻两个窗口内会计算两次,因0.1)内.种群的分割此也要求α的选取要尽可能小.所以α的取值被限定在一个较小的区域(0， 在维护种群多样性的同时,也是为了在变异算子中引入PSO算法的思想做准备. 3.2 重构变异算子 变异算子的重构,就是用PSO公式作为变异算子,让个体依据自身迄今最优解和子种群内迄今最优解以及个体进化的速度来决定变异方向和幅度,这使个体在进化的过程中可以将其进化史作为导向标. ii 对应的xmax代替PSO中的lid,用xti代替PSO中的yid值,用Πt中第i位上的历史最优fmax jii 用子种群的历史最优Fmax(j为该粒子团在子种群中的位置)对应的Xmax代替lgd,用xmax的i 来代替vid.xmax的累积差由公式⑵计算: 累积差的算术平均∆xmax i ∆xmax,t i =[ ∑(x k=2 t i max,kiiii−xmax,k−1)]/t=∆xmax,t−1+(xmax,t−xmax,t−1)/t ⑵ 则PSO变异算子为公式⑶: iiiiii⎧⎪∆xmax,t+1=∆xmax,t+c1⋅r1⋅(xmax−xt)+c2⋅r2⋅(Xmax−xt) ⑶ ⎨i ii ⎪⎩xt+1=xt+∆xmax,t+1 ii 公式⑶的第一部分通过权重因子c1、c2和随机数r1、r2以及信息反馈xmax、Xmax预测 - 3 - http://www.paper.edu.cn 了变异的幅度和方向;第二部分则具体实施了变异操作.因此,PSO变异操作就具备了自学习能力,在变异之前的预测,也使变异操作不再是简单的随机变异,而是提高个体对进化环境适应能力的变异. 3.3 算法的伪码描述 PSOGA算法的伪码描述: 初始化参数; P0=按约束条件随机产生n个个体; 对P0排序; 分割P0; ijiii 、Fmax、xmax、∆xmax、Xmax; 初始化fmax While 中止条件不满足时 i 收集子种群中的最优解Xmax; While 小于子种群数目时 取子种群; 评估子种群内各个体; 选择子种群内最优解; 选择算子; 交叉算子; PSO变异算子; While 小于子种群内个体数目时 End 对子种群内个体排序; End End 输出全局最优解和局部最优解; End 4 算法性能分析 为了分析该算法的性能,从文献[9]中选取了如下⑷、⑸、⑹三个典型函数: ⎧⎪f(x,y)=(4-2.1x2+x4/3)x2+xy+(-4+4y2)y2 六峰值驼背函数⎨1 ⎪-3≤x≤3-2≤y≤2⎩ ,求最小值 ⑷ ⎧ ⎪f(x,x)=100(x2-x2)2+(1-x1)2 1De Jong函数F2⎨212 ⎪-2.048≤xi≤2.048,(i=1.2)⎩ ⎧ ⎪f(x,x)=100(x2-x2)2+(1-x1)2 1RosenBrock函数⎨212 ⎪-2.048x2.048,(i=1.2)≤≤i⎩ ,求最小值 ⑸ ,求最大值 ⑹ 上述三个函数是遗传算法中常用的标准测试函数,它们各具特点.函数⑷有六个局部极小值,一个全局最小值,考察了算法逃离局部最优点的能力.函数⑸是一个病态函数,仅有一个全 - 4 - http://www.paper.edu.cn 局极小点,但难以进行全局极小化.函数⑹有一个全局极大点和局部最大点,且极易陷入局部最大点. 为了衡量本文算法的性能, 设计了两组实验,每组都重复进行了50次,最大进化代数取500,初始种群规模为50,覆盖因子α取值0.01,权重因子c1、c2都取值2,计算精度为10−4.通过对收敛次数和平均收敛代数(平均收敛代数指在多次重复实验中,收敛趋于稳定且取到极值时的最小进化代数的均值)的测量来比较这两种算法的性能.在两组实验中,PSOGA和SGA都使用实数编码,选择算子和交叉算子也都采用简单遗传算子. 4.1 实验1 变异算子采用PSO变异算子,子种群数目为5,采用均匀分割. Table 1 The evolution epochs of two algorithms 表1 两种算法的性能对比 函数 PSOGA 六峰值驼背函数 DeJong函数2 RoseBrock函数 49 50 50 收敛次数 SGA 41 36 43 平均收敛代数 PSOGA 35.2 51.4 41.0 PSOGA 242.1 276.5 182 结果表明,PSOGA比SGA在收敛性能和搜索能力上有很大提高,加速比最大达到了9.61,最小也达到了4.4.由于采用了平均收敛代数指标来衡量算法的性能,表中的收敛代数比第一次取到最优解时的代数要大许多,在50次重复实验中,有几例可以不超过10代就能第一次搜索到最优解. 4.2 实验2 PSOGA和实验1同样,SGA也采用种群分割策略,种群数目为5,采用均匀分割. Table 2 Comparisons on performance of the PSO mutation operator 表2 PSO变异算子的性能测试 函数 PSOGA 六峰值驼背函数 DeJong函数2 RoseBrock函数 50 50 49 收敛次数 SGA 44 40 43 平均收敛代数 PSOGA 34.0 48.8 42.3 PSOGA 180.0 203.5 137 结果表明,PSO变异算子比传统变异算子性能要高出许多,三个函数几乎都能取到最优解. 从表2和表1的比较可以看出,SGA由于使用了本文的种群分割策略,其性能明显提升,平均收敛代数显著下降;PSOGA则趋于稳定,两张表得出的数据基本一致. 通过上述实验对比,表明了本文的算法在改善收敛速度、克服早熟收敛方面有较好的表现,在增强局部搜索能力方面也有明显的改观. 5. 结束语 本文将PSO算法的思想引入SGA算法,提出了一种遗传算法改进的新方案.该算法的核心是有覆盖的种群分割和PSO变异算子.有覆盖的种群分割从维护种群多样性的角度避免了早熟收敛,PSO变异算子则从避免传统变异算子的随机性、盲目性角度出发,避免了早熟收敛,提高了收敛效率.初步实验结果表明,PSOGA算法可以较好的保持种群的多样性,克服早熟现象,提高收敛效率,在局部搜索能力方面也得到了改善,更容易找到全局最优解. - 5 - http://www.paper.edu.cn 未来的工作,仍需进一步分析PSO变异算子的性能,分析其起作用的数学机理,对于覆盖因子α和子种群数目对算法性能的影响也需要作进一步的实验和分析. 参考文献: [1] Eshelma L J. The CHC adaptive search algorithm: How to have safe search when engaging in non-traditional genetic recombination. In: Founfation of Genetic Algorithm. Morgan Kaufmann Publishers,1991,265-283 [2] Srinivas M and Patnaik L M. Adaptive probabilities of crossover and mutations in Gas. IEEE Trans. On SMC, 1994,24(4):656-667 [3] Ma JS, Liu GZ, Jia YL . The big mutation: an operation to improve the performance of genetic algorithms. Control Theory and Application, 1998,15(3):404-407(in Chinese with English abstract) [4] 苏小红,杨博,王亚东,基于进化稳定策略的遗传算法, 软件学报, Vol.14 No.11, 2003,14(11):1863-1868. [5] 蒙祖强,蔡自行,一种基于超群体的并行遗传算法,计算机工程与应用,2001.21,第28-30页 [6] 林焰,郝聚民,纪卓尚,戴寅生,隔离小生境遗传算法研究,系统供学报,第15卷第1期,第86-91页,2000.3 [7] 丁永生,计算智能—理论、技术与应用,北京:科学出版社,2004年8月第1版 [8] B.T.Skinner,H.T.Nguyen,D.K.Liu,Performance study of a multi-deme parallel genetic algorithm with adaptive mutation,2nd international conference on autonomous rebots and agents, December 13-15,2004 [9] 周明,孙树栋,遗传算法原理及应用,北京:国防工业出版社,1999年7月第1版 Research on Genetic Algorithm Based on Particle Swarm Algorithm QIN Guang-Jun1+, WANG Xin-Yan2, WANG Wen-Yi3 School of Information Engineering, Zhengzhou University, Zhengzhou 450052, China 2 Software College , Northeastern University, Shenyang 110004, China 3 School of Computer Science and Technology, Zhongyuan University of Technology, Zhengzhou 450007, China + Corresponding author: Phn: +86-0371-67766039-2214, E-mail: gjqin@gs.zzu.edu.cn 1 Abstract Premature convergence and weak local optimization are two key problems existing in the conventional genetic algorithm. To overcome the shortcomings, an improved genetic algorithm based on the particle swarm algorithm is proposed. The basic principle of the algorithm is that a new mutation operator is constructed and population is divided into parts. Three typical multimodal functions are optimized with tow algorithms and optimization results are used to evaluate the optimization efficiency of the algorithm. The experimental results show that the optimization efficiency of the algorithm improves can effectively avoid premature and maintain the polymorphism in the colony, and also greatly improve the convergent speed. Keywords：genetic algorithm; particle swarm algorithm; mutation operator; population diversity; premature convergence; - 6 - 因篇幅问题不能全部显示，请点此查看更多更全内容