一种新型的自适应小生境遗传算法解决NP组合问题

一种新的自适应小生境遗传算法在多峰NP组合问题中研究与应用摘要：为了求解多峰优化问题，本文将遗传算法分成了两个阶段。第一个阶段，把个体不重复的均匀的散布在整个解空间内，不仅提高多样性，而且把所有可能的峰值点搜集起来。第二阶段，借用小生境遗传算法的思想，在每一个候选峰值点附近进行局部求精搜索，一直到所有候选峰值点搜索完。用这种方法可以比较细密的搜遍整个可行解域，对求多峰函数比较适合，起到密网捕鱼一个不漏的效果，并用N皇后问题进行验证收到较好的效果。关键字：遗传算法、小生境、自适应、距离密度、进化趋势、N皇后前言许多优化问题中都有多个全局最优解和多个局部最优解，我们更多的是要把所有的全局最优解和局部最优解全部找出，然后决策人员结合生产生活的实际情况，权衡各方利弊，在所有的最优或较优解中选出适合的某几个最优解，这类问题常称为多峰搜索问题或多模态函数优化问题，见文献［1］。这就需要寻解能力较强的遗传算法，一次寻找多个最优解以供参考选择，但传统的遗传算法通常只能求一个最优解难以满足要求，见文献⑵和［3］。目前研究遗传算法求多峰优化问题主要集中在数值问题上，例如文献［1］提出用协同多群体并结合小生境的思想取得较好的效果，虽然该文也提出了解决多峰组合问题的思路，但是不仅需要求适应值与海明距离的函数关系，而且需要对其进行平滑，相当繁琐。其他的遗传算法解决多峰的组合问题还是凤毛麟角。与数值问题相比组合问题具有离散性强，差异性大，不规则等特点，而且很多组合问题是NP难的，用通常的方法求解非常困难，因此有必要专门研究讨论该问题。本文以求最大值为例提出一种改进的自适应的小生境遗传算法，试图提高对多峰组合问题的寻优能力，寻找尽可能多的解，经实验效果比较明显。为了寻找尽可能多的解，我们需要算法尽可能的搜遍整个解空间，为此可以让个体比较均匀的分散在整个解空间中，并且尽可能不重复的遍历整个解空间。算法描述算法基本思想算法思想简介通常随机生成的初始群体，并不一定保证均匀覆盖整个解空间（如图一）。因此我们必须通过一定的措施使初始群体更加均匀的散满整个解空间，形成均匀群体，然后每隔一定距离选择其中适应值较优的个体作为候选的小生境核（如图二）。最后借用小生境遗传算法的思想一次选择一定数目的候选小生境核，并保证群体中的个体都集中在这些小生境内，在每一个小生境核周围进行局部的细致搜索（如图三）。如果在某一个小生境内找到一个比当前核更优的个体，则可假设这个更优个体附近更接近全局最优解，因此以这个更优个体为新核，对这个小生境的搜索就迁移到新核附近（如图四）。当在某个小生境内找到一个最优解或该小生境与某个已求解距离很近或搜索时间超过一定代数后，算法停止对当前小生境的搜索，

转而搜索候选核中没有搜索过的其他小生境，周而复始一直搜索遍历完所有候选小生境核。图一初始群体图二均匀群体图三 图四在每个小生境内搜索 小生境向更优解迁移图一初始群体图二均匀群体图三 图四在每个小生境内搜索 小生境向更优解迁移算法基本流程该算法分为两个阶段，第一阶段主要是让初始群体尽可能的均匀化；第二阶段主要是借用小生境遗传算法的方法，在每一个小生境范围内搜索。第一阶段首先计算群体中两两个体的距离和每个个体的距离密度，选择距离密度比较大的若干对个体，每一对个体按照距离密度进行交叉变异，然后用子个体替换父个体，这个过程一直重复到连续几代群体的多样性不再增加为止，在这个过程中记下多样性最好的几代群体，最后在这些多样性好的群体中选择合适的候选小生境核，并放到预备小生境核队列中。第二阶段主要在一定量的小生境核内进行进化，根据进化程度和适应值来调整交叉变异策略，并且随着迭代代数的增加不断减小小生境半径。整个算法流程如下图：

第一阶段 第二阶段图五算法第一阶段描述选择算子为了实现群体均匀分布于解空间，我们根据每个个体的距离密度进行选择，而不是根据适应值进行选择。距离密度越大选择概率越高，反之越低。设N是群体规模，％表示个体i和j的距离。在文献［4］中，距离密度定义为个体i和其余N-1个个体距离之和，即：

D=Nd=Il月（ximXjm）2，并声称一个个体距离密度越小，说明其周围个j=1,j-i'j=1,j-im=1体越集中；密度越大越分散。笔者认为此种定义和断言有待改进，例如，在图六中对个体）求距离密度，从图中可以看到这样一个事实：C比A集中，B比C分散。按照文献［4］的计算方法：D=1.5<D=1.7;Db=1.3<D=1.7，A比。集中，C比B分散，这与事实不符。因此文献［4］的定义方法需要改进，在此给出两种衡量距离密集程度的方法。实不符。因此文献［4］的定义方法需要改进，在此给出两种衡量距离密集程度的方法。ABC"=0.5d0i=0.1d01=0.1d/0.5d02=0.6d02=0.1d03=0.5d03=0.6d03=1.5图六定义1在规模为N的群体中，任意个体i与其余N-1个个体距离的倒数之和称为个体i的距离密度，记作R，用公式表示为：D=EdjT，j-iijR值越大个体i周围越密集，反之越分散。该方法强调了与个体i距离特别近的那些个体，如果个体j与个体i特别近它对i的距离密度影响越大。但此种方法也有缺陷，如图七，按这种定义A中D0=21，B中D0=22，B应当密集些，但事实上群体B更分散些。造成这种现象的原因是式Q用到的函数V=j在（0,1］变化过快，扁有细微的扰动Di就变化很大，在1,+8）中变化较慢，反而抹杀了扁的差别。另一方面群体中可能出现个体i,j相同分母为0的情况。3*2* 3*1+2*3*2* 3*1+2*1*LI*0*AB图七考虑到个体j距i越近对距离密度影响越大，ABd=0.1d=0.050101d=0.1d=1.000202d=1.0d=1.000303越远影响越小，把这些影响力量化并把所有个体的影响力累加起来可以作为距离密度的衡量。为了量化这种影响力，可以把它表示成一个关于距离的递减的函数，如果先考虑线性递减函数，则有如下定义:定义2在规模为N的群体中，设Em>£皿>0，dm为个体间最大距离，对任意个体i

\Md+\Md+EM7iJ=1,J&I交叉变异策略这里交叉变异也用了自适应方法，让密集借用文献［5］和［6］的自适应交叉变异的思想这里交叉变异也用了自适应方法，让密集个体进行较多的交叉变异以分散开来，个体越分散交叉变异的概率越小，用下式确定交叉变异概率：D<Di avg，D>Di avgk+k—k)£iD<Di avg，D>Di avgkavg nub其中D表示群体的平均距离密度，让距离密度高于平均距离密度的个体以较高的固定概其中D表示群体的平均距离密度，让距离密度高于平均距离密度的个体以较高的固定概率k进行交叉变异；低于平均距离密度的个体交叉变异的概率随着Di的减小而线性递减。2替换数目的确定随着迭代的进行，多样性不断提高，群体越来越均匀，改进的余地会越来越小，因为当群体比较均匀时仍大幅度的进行交叉变异，反而破坏了群体的均匀性。因此替换数目应随迭代代数不断减少，用下式计算：rc(t)=max(kt+rc,rc)，其中k<0；rc是最maxmin max大替换数目；rc.是最小替换数目，通常取2；t是迭代代数；rc(t)第t代的替换数目。算法第二阶段描述1.进化趋势的量化进化趋势即群体最近进化的方向，用来衡量群体进化的优劣程度，用它可以反馈调节进化策略。文献［7］用适应值变化率k化策略。文献［7］用适应值变化率k=f(t)-f(t-10)

f(—10)来衡量，该思路虽有定依据但刻画得也不够精确，例如图八中，若用上式变化率的计算方法，t=10与t=12的变化趋势一样的，但事实上t=10时进化，t=12是退化。要想用上式变化率检测到t=11后是退化必须等到t=21后才行，显得滞后和不精确。造成这种现象的原因是只考虑了两端t=0，t=10的变化，没有考虑中间的适应值变化。f(0)=af(10)=b,,,■11111111111111111.,f⑵=a(12)斗02 1012图八由于进化趋势与最近几代的适应值增减有关，而且与当前代越接近关系越密切衡量越准确，因此可用E°)=EwG*G)描述进化程度。其中sG)表示第i和i-1相邻两代的进化；w(i)i=t-c

描述第i代进化的权重系数，i与t越接近权重w(i)越大；EQ刻画了从t-。代到第t代c「+1展)」0-1连续c代的进化趋势，E「+1展)」0-1七一W(i-t)f(i)-f(i七一W(i-t)-0<f(i)-f(i-1)<0；wO=W+

f(i)-f(i-1)<-0 MW,W分别为最大最小权重系数。另外也可简单的取:Mm80=f(i)-f(i-1)，wG)=i+1-(t-c)。2,交叉变异策略首先确定整个群体的交叉变异概率的范围，所有个体的概率均限于此范围内。通常群体的平均适应值较低时，说明进化还不成熟，应加快进化速度;平均适应值较高时，说明比较接近最优解，应该进行局部求精，减少交叉变异的概率。另一方面，当最近进化缓慢时，应加大概率促进进化；当进化过快时，应适当的抑制进化速度防止早熟。因此我们确定的交叉变异的浮动范围为平均适应值f和进化趋势EG)的函数：Pf,E(t)=p+axfL-PxEQ，avgPf，E应p+axfL-PxE(t)” avg其中，p、p分别是固定的最大最小概率；系数以不仅要把!调节到［0，1］内，而avg且确定了适应值对概率浮动的影响；系数P用来调节进化趋势EG)的对概率的作用效果。C然后对群体中每个个体，适应值大的实行小概率进化，以保持优良基因；适应值小的实行大的概率进化，加快寻优步伐。依此原则每个个体根据各自的适应值在群体概率范围内确定自己的概率。如果用线性关系则有下面方法:Lr定自己的概率。如果用线性关系则有下面方法:Lrpf，e(t立pf，e讥—M——avg f f_m——avg c \ minmax Jf-f )+pf，EQ。imaxmavgc其中，f,f,f 分别是群体的最小、平均、最大适应值。minavgmax小生境半径的确定在对每个小生境搜索时，随着迭代代数的增加，应越来越趋向局部求精。因此某个小生境半径随着该小生境的迭代代数的增加而不断减小，但为了保证能遍历完解空间每一个区域，小生境半径应该有个下限R通常取0.6倍个体间的平均距离。成）=maXRm-k*t,Rm），其中Rm是最大的小生境半径，k是小生境半径减少的步长。试验讨论理论分析参考文献：李民强，寇纪淞，林丹，李书全.遗传算法的基本理论与应用.科学出版社CampbellPJ.Reviews:Geneticalgorthmsinsearch,optimizationandmachinelearningbyDavidE.Goldberg[J].MathematicsMagazine,1989,62(3):206-207RudolphG.Convergenceanalysisofcanonicalgeneticalgorithms[J].IEEETransactionsonNeuralNetworks,1994,5(1):96〜101.蔡良伟.基于距离测度的实数编码自适应遗传退火算法.深圳大学学报理工版，200