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

1、一种新型的自适应小生境遗传算法解决多值NP组合问题前言传统的遗传算法通常只能一个最优解，但在许多解优化问题中，都有多个全局最优解和多个局部最优解，我们更多的是要把所有的全局最优解和局部最优解全部找出，然后决策人员结合生产生活的实际情况，权衡各方利弊，在所有的最优或较优解中选出适合的某几个最优解。这就需要寻解能力超强的遗传算法，一次寻找多个最优解以供参考。因此本文以求最大值为例提出一种新型的自适应的小生境遗传算法，试图提高对多峰函数的寻优能力，寻找尽可能多的解，经实验效果比较明显。为了寻找尽可能多的解，我们需要算法尽可能的搜遍整个解空间，为此可以让个体比较均匀的分散在整个解空间中，并且尽可能不重

2、复的遍历整个解空间。算法描述算法基本思想算法思想简介通常随机生成的初始群体，并不一定保证均匀覆盖整个解空间（如图一）。因此我们必须通过一定的措施使初始群体更加均匀的散满整个解空间，形成均匀群体，然后每隔一定距离选择其中适应值较优的个体作为候选的小生境核（如图二）。最后借用小生境遗传算法的思想一次选择一定数目的候选小生境核，并保证群体中的个体都集中在这些小生境内，在每一个小生境核周围进行局部的细致搜索(如图三)。如果在某一个小生境内找到一个比当前核更优的个体，则可假设这个更优个体附近更接近全局最优解，因此以这个更优个体为新核，对这个小生境的搜索就迁移到新核附近（如图四）。当在某个小生境内找到一个

3、最优解或该小生境与某个已求解距离很近或搜索时间超过一定代数后，算法停止对当前小生境的搜索，转而搜索候选核中没有搜索过的其他小生境，周而复始一直搜索遍历完所有候选小生境核。图一初始群体图二均匀群体图三在每个小生境内搜索图四小生境向更优解迁移算法基本流程该算法分为两个阶段，第一阶段主要是让初始群体尽可能的均匀化；第二阶段主要是借用小生境遗传算法的方法，在每一个小生境范围内搜索。第一阶段首先计算群体中两两个体的距离和每个个体的距离密度，选择距离密度比较大的若干对个体，每一对个体按照距离密度进行交叉变异，然后用子个体替换父个体，这个过程一直重复到连续几代群体的多样性不再增加为止，在这个过程中记下多样性

4、最好的几代群体，最后在这些多样性好的群体中选择合适的候选小生境核，并放到预备小生境核队列中。第二阶段主要在一定量的小生境核内进行进化，根据进化程度和适应值调整交叉变异策略，并且随着迭代代数的增加不断减小小生境半径。整个算法流程如下图：第一阶段第二阶段图五 SHAPE * MERGEFORMAT 算法第一阶段描述选择算子为了实现群体均匀分布于解空间，我们根据每个个体的距离密度进行选择，而不是根据适应值进行选择。距离密度越大选择概率越高，反之越低。设N是群体规模，dij表示个体i和j的距离。在文献1中，距离密度定义为个体i和其余N-1个个体距离之和，即：，并声称一个个体距离密度越小，说明其周围个体

5、越集中；密度越大越分散。笔者认为此种定义和断言有待改进，例如，在图六中对个体0求距离密度，从图中可以看到这样一个事实：C比A集中，B比C分散。按照文献1的计算方法：，A比C集中，C比B分散，这与事实不符。因此文献1的定义方法需要改进，在此给出两种衡量距离密集程度的方法。图 六Ad01=0.5d02=0.5d03=0.5Bd01=0.1d02=0.6d03=0.6Cd01=0.1d02=0.1d03=1.5定义1 在规模为N的群体中，任意个体i与其余N-1个个体距离的倒数之和称为个体i的距离密度，记作Di，用公式表示为： eq oac(,1)Di值越大个体i周围越密集，反之越分散。该方法强调了与

6、个体i距离特别近的那些个体，如果个体j与个体i特别近它对i的距离密度影响越大。但此种方法也有缺陷，如图七，按这种定义A中D0=21，B中D0=22， B应当密集些，但事实上群体B更分散些。造成这种现象的原因是式 eq oac(,1)用到的函数在变化过快，dij有细微的扰动Di就变化很大，在中变化较慢，反而抹杀了dij的差别。另一方面群体中可能出现个体i,j相同分母为0的情况。AB图七Ad01=0.1d02=0.1d03=1.0Bd01=0.05d02=1.00d03=1.00考虑到个体j距i越近对距离密度影响越大，越远影响越小，把这些影响力量化并把所有个体的影响力累加起来可以作为距离密度的衡量

7、。为了量化这种影响力，可以把它表示成一个关于距离的递减的函数，如果先考虑线性递减函数，则有如下定义：定义2 在规模为N的群体中，设，为个体间最大距离，对任意个体i的距离密度为：。交叉变异策略借用文献2的自适应交叉变异的思想，这里交叉变异也用了自适应方法，让密集个体进行较多的交叉变异以分散开来，个体越分散交叉变异的概率越小，用下式确定交叉变异概率：，其中其中表示群体的平均距离密度，让距离密度高于平均距离密度的个体以较高的固定概率进行交叉变异；低于平均距离密度的个体交叉变异的概率随着Di的减小而线性递减。替换数目的确定随着迭代的进行，多样性不断提高，群体越来越均匀，改进的余地会越来越小，因为当群体

8、比较均匀时仍大幅度的进行交叉变异，反而破坏了群体的均匀性。因此替换数目应随迭代代数不断减少，用下式计算：，其中；是最大替换数目；是最小替换数目，通常取2；t是迭代代数。算法第二阶段描述进化趋势的量化进化趋势即群体最近进化的方向，用来衡量群体进化的优劣程度，用它可以反馈调节进化策略。文献3用适应值变化率来表征，交叉变异策略首先确定整个群体的交叉变异概率的范围，所有个体的均限于此范围内。小生境半径的确定试验讨论理论分析参考文献：蔡良伟基于距离测度的实数编码自适应遗传退火算法深圳大学学报理工版，2004，Vol21，No4Srinivas，and Patnaik，daptive probabilities of crossover and m