小生境遗传算法

生物学上，小生境是指特定环境下的一种组织结构。在自然界中，往往特征，形状相似的物种相聚在一起，并在同类中交配繁衍后代。在SGA中，交配完全是随机的，在进化的后期，大量的个体集中于某一极值点上，在用遗传算法求解多峰值问题时，经常只能找到个别的几个最优值，甚至往往得到是局部最优解。利用小生境我们可以找到全部最优解。小生境技术就是将每一代个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个群，再在种群中，以及不同种群中之间，杂交，变异产生新一代个体群。同时采用预选择机制和排挤机制或分享机制完成任务。基于这种小生境的遗传算法（NichedGeneticAlgorithms，NGA），可以更好的保持解的多样性，同时具有很高的全局寻优能力和收敛速度，特别适合于复杂多峰函数的优化问题。模拟小生境技术主要建立在常规选择操作的改进之上。Cavichio在1970年提出了基于预选择机制的选择策略，其基本做法是：当新产生的子代个体的适应度超过其父代个体的适应度时，所产生的子代才能代替其父代而遗传到下一代群体中去，否则父代个体仍保留在下一代群体中。由于子代个体和父代个体之间编码结构的相似性，所以替换掉的只是一些编码结构相似的个体，故它能够有效的维持群体的多样性，并造就小生境的进化环境。DeJong在1975年提出基于排挤机制的选择策略，其基本思想源于在一个有限的生存环境中，各种不同的生物为了能够延续生存，他们之间必须相互竞争各种有限的生存资源。因此，在算法中设置一个排挤因子CF（一般取CF=2或3），由群体中随机选取的1/CF个个体组成排挤成员，然后依据新产生的的个体与排挤成员的相似性来排挤一些与预排挤成员相类似的个体，个体之间的相似性可用个体编码之间的海明距离来度量。随着排挤过程的进行，群体中的个体逐渐被分类，从而形成一个个小的生成环境，并维持群体的多样性。Goldberg等在1987年提出了基于共享机制（Sharing）的小生境实现方法。这种实现方法的基本思想是：通过反映个体之间的相似程度的共享函数来调节群体中各个个体的适应度，从而在这以后的群体进化过程中，算法能够依据这个调整后的新适应度来进行选择运算，以维持群体的多样性，创造出小生境的进化环境。共享函数（SharingFunction）是表示群体中两个个体之间密切关系程度的一个函数，可记为S（d）其中表示个体i和j之间的关系。例如，个体基因型之间的海明距离就可以为一种共享函数。这里，个体之间的密切程度主要体现为个体基因型的相似性或个体表现型的相似性上。当个体之间比较相似时，其共享函数值就比较大；反之，当个体之间不太相似时，其共享函数值比较小。共享度是某个个体在群体中共享程度的一中度量，它定义为该个体与群体内其它各个个体之间的共享函数值之和，用S表示：S=（i=1，，M）在计算出了群体中各个个体的共享度之后，依据下式来调整各个个体的适应度：F（X）=F（X）/S（i=1，，M）由于每个个体的遗传概率是由其适应度大小来控制的，所以这种调整适应度的方法就能够限制群体中个别个体的大量增加，从而维护了群体的多样性，并造就了一种小生境的进化环境。下面介绍一个基于小生境概念的遗传算法。这个算法的基本思想是：首先两两比较群体中各个个体之间的距离，若这个距离在预先的距离L之内的话，在比较两者之间的适应度大小，并对其中适应值较低的个体施加一个较强的罚函数，极大地降低其适应度，这样，对于在预先指定的某一距离L之内的两个个体，其中较差的个体经处理后其适应度变得更差，他在后面的进化过程被淘汰的概率就极大。也就是说，在距离L内将只存在一个优良个体，从而既维护了群体的多样性，又使得各个个体之间保持一定的距离，并使得个体能够在整个约束的空间中分散开来，这样就实现了一种小生境遗传算法。这个小生境算法的描述如下：算法NicheGA（1）设置进化代数计数器；随机生成M个初始群体P（t），并求出各个个体的适应度F（i=1，2，M）。（2）依据各个个体的适应度对其进行降序排列，记忆前N个个体（NM）.(3)选择算法。对群体P（t）进行比例选择运算，得到P（t）。（4）交叉选择。对选择的个体集合P（t）作单点交叉运算，得到P（t）。（5）变异运算。对P（t）作均匀变异运算，得到P（t）。（6）小生境淘汰运算。将第（5）步得到的M个个体和第（2）步所记忆的N个个体合并在一起，得到一个含有M+N个个体的新群体；对着M+N个个体，按照下式得到两个个体x和x之间的海明距离：||x-x||=()当||x-x||L时，比较个体x和个体x的适应度大小，并对其中适应度较低的个体处以罚函数：Fmin(x，x)=Penalty（7）依据这M+N个个体的新适应度对各个个体进行降序排列，记忆前N个个体。（8）终止条件判断。若不满足终止条件，则：更新进化代数记忆器tt+1，并将第（7）步排列中的前M个个体作为新的下一代群体P(t),然后转到第（3）步：若满足终止条件，则：输出计算结果，算法结束。[例]Shubert函数的全局最优化计算。minf(x,x)={}{}s.t.-10x10（i=1，2）上述函数共有760个局部最优点，其中有18个是全局最优点，全局最优点处的目标函数值是f（x，x）=-186.731。用上述小生境遗传算法求解该例题时，可用下式进行目标函数值到个体适应度的变换处理：F（x，x）=L=202（二进制编码串长度，其中每个变量用10位二进制编码来表示）M=50T=500p=0.1p=0.1L=0.5(小生境之间的距离参数)Penlty=10（罚函数）使用上述参数进行了50次，试算，每次都可得到许多全局最优解下表为其中一次运算所得到的最好的18个个体。从该表可以看出，从小生境的角度来数，该算法得到了一个较好的结果。上述算法的特点保证了在一个函数峰内只存在一个较优的个体，这样每一个函数峰就是一个小生境。基于小生境遗传算法的Shubert函数优化算法计算结果个体标号xxf（x，x）15.48284.8581-186.73125.4830-7.7083-186.73134.85815.4831-186.73144.8581-7.0838-186.7315-4.4252-7.4983-186.7316-7.0832-7.0838-186.73175.4827-1.4249-186.73180.85805.4831-186.73194.8580-0.8009-186.73010-0.8009-7.7084-186.73011-0.80094.8581-186.73012-7.7088-0.7999-186.73013-7.7088-7.0831-186.73014-1.4256-0.8009-186.73015-0.8011-1.4252-186.73016-7.70755.4834-186.73017-7.70884.8579-186.73018-7.0825-1.4249-186.730下面再介绍一种隔离小生境技术的遗传算法隔离小生境技术的基本概念及进化策略依照自然界的地理隔离技术,将遗传算法的初始群体分为几个子群体,子群体之间独立进化,各个子群体的进化快慢及规模取决于各个子群体的平均适应水平.由于隔离后的子群体彼此d立,界限分明,可以对各个子群体的进化过程灵活控制。生物界中,竞争不仅存在于个体之间,种群作为整体同样存在着竞争,适者生存的法则在种群这一层次上同样适用.在基于隔离的小生境技术中,是通过将种群的规模同种群个体平均适应值相联系来实现优胜劣汰、适者生存这一机制的.子群体平均适应值高,则其群0体0规0模0就大,反之,群0体0规0模就小.生物界在进化过程中,适应环境的物种能得到更多的繁0殖机会,其后代不断地增多,但这种增加不是无限制的,否则就会引起生态环境的失衡.在遗传算法中,群体的总体规模是一定的,为了保证群体中物种的多样性,就必须限制某些子群体的规模,称子群体中所允许的最大规模为子群体最大允许规模(maximumallowedscale),记为S.生物界中同样会出现某些物种因不适应环境数量逐渐减少,直至灭0绝0的现象.在隔离小生境机制中,为了保持群体的多样性,有时需要有意识地保护某些子群体,使之不会过早地被淘汰,并保持一定的进化能力.子群0体的进化能力是和子群0体的规0模相联系的,要保证子群体的进化能力,必须规定每一子群体生存的最小0规0模,称为子群体最小生0存0规0模(minimumlivescale),记为S.在群体进化过程中,如果某一子群体在规定的代数内,0持续表现最差,应该使这个子群体灭0绝,代之以搜索空间的新解,这一最0劣0子0群0体0灭0绝0的机制,定义为劣种不活(theworstdie).子群体在进化过程中,如果出现两个子群体相似或相同的现象,则去掉其中的一个,代之以搜索空间的新解,这种策略称为同种互斥或种内竞争(intraspecificcompetition).解群中出现的新的子群体,在进化的初期往往无法同已经得到进化的其它子群体相竞争,如果不对此施加保护,这些新解往往在进化的初期就被淘汰掉,这显然是我们所不希望的.为了解决这个问题,必须对新产生的解加以保护,这种保护新解的策略叫幼弱保护(immatureprotection).子群体在进化过程中,如果收敛到或接近局部最优解,会出现进化停滞的现象,此时应当以某种概率将该子群体去掉,代之以搜索空间的新解,此种策略称为新老更替(thenewsupersedingtheold).在进化过程中,表现最优的个体进化为最优解的概率最大,应当使它充分进化,故新老更替策略不能用于最优子群体,这种做法称为优种保留(thebestlive).优种保留可以作用于最好的一个子群体,也可以作用于最好的几个子群体.基于隔离小生境技术的遗传算法步骤1)编码:针对具体问题,选择合适的编码方案,完成问题解空间向遗传算法解空间的转化.2)产生初始群体:随机产生N个初始个体.3)初始群体隔离:将N个初始个体均分给K个子群体,每个子群体含有的个体数均为N/K.4)计算适应值:计算群体中所有个体的适应值.并保存适应值最高的个体.5)确定子群体规模:子群体的规模同子群体的平均适应值相关,子群体的平均适应值越大,其在下一代中拥有的个体就越多;反之,在下一代中拥有的个体就少.但数目必须满足最大允许规模和最小保护规模的限制,即第t+1代第k个子群体的规模n(t+1)满足S≤n(t+1)≤S.确定子群体规模的具体方法如下,首先给每个子群体都预分配S个个体,剩下的个体根据子群体的平均适应值利用赌轮法选择,直到总的群体数量达到N为止.子群体的平均适应值一般可简单取为f(t)=(1)式中f(t)为t代第k个子群体的平均适应值;f(t)为t代第k个子群体中第i个个体的适应值;n(t+1)为t代第k个子群体的规模.子群体k第t+1代的规模n(t+1)为：n(t+1)=N.f(t)/（2）子群体规模的确定也可以根据其平均适应水平用赌轮法确定.6)保护解除判定:对群体中施加保护的群体,进行保护解除判定,对满足保护解除条件的,撤除保护.7)劣种不活判定:对解群中没有保护而连续几代表现又最差的群体,予以剔除并产生等规模的新子群体.8)同种互斥判定:随机挑选出两个子群体,依据某种原则判定其相似程度,对满足相似条件的两个子群体,去掉其中的一个,产生同等规模的新解.9)新老更替判定:判定解群中是否存在已经进化停滞的子群体,如果有,进行新老更替,产生同等规模的新解,但对包含最优个体的子群体要保留(最优保留机制).10)重新计算适应值:对新产生的子群体计算适应性值,并施加幼弱保护措施.11)子群体进化:由于子群体的规模同其在群体中的平均表现水平相联系,故子群体的规模是不断变化的.根据公式(2)确定的规模,选择出子群体的繁殖个体,利用交叉和变异算子产生下一代解群.12)收敛性判定,如果满足收敛性条件,或已经进化了规定的代数,则结束进化过程;否则返回第4步。除了上面的还有下面几种常用的的小生境算法：1确定性拥挤算