基于个体相似性评价策略的改进遗传算法

汤可宗　张　彤　罗立民

1(东南大学计算机科学与工程学院　江苏 南京 210094)2(景德镇陶瓷学院信息工程学院　江西 景德镇 333403)



基于个体相似性评价策略的改进遗传算法

汤可宗1张彤2罗立民1

1(东南大学计算机科学与工程学院江苏 南京 210094)2(景德镇陶瓷学院信息工程学院江西 景德镇 333403)

遗传算法是一种通过模拟自然进化过程搜索最优解的方法。但这种算法在求解最优解过程中总是以计算时间为代价来换得最优解的产生。对此，提出一种基于个体相似`性评价策略的改进遗传算法，融入了一种新的旋转交叉算子，每个子个体根据其与父个体的相似度和可信度来确定个体的适应度值，仅当可信度值低于某个阈值时，个体才做真实的适应度计算。实验结果显示，相似性评价策略计算得到的个体适应度值接近真实的适应度值，并且改进的算法求得最优解需要的评价次数明显要少于传统遗传算法，而在测试准测上的数据表明：提出的改进遗传算法相对于传统遗传算法，性能较好且求得的最优解也较为理想。

遗传算法相似性评价交叉算子

0　引　言

图1　遗传算法模型

遗传算法GA(Geneticalgorithm)是一种借鉴生物界的进化规律(适者生存、优胜劣汰遗传机制)演化而来的随机化搜索方法。目前已被广泛应用于求解各类优化问题[1-5]。然而，这种基于种群搜索机制的优化方法在求解复杂计算问题时总是以计算时间为代价来换得最优解的产生，尽管现今硬件技术的快速发展，使得GA朝着最优解方向的搜索时间得到了缩短，但从算法自身的执行进制出发，缩短算法的搜索时间，提高算法的运行效率，是更值得研究人员思考的问题。

一般而言，传统的GA模型可分为三个部分[6]，见图1所示。

存储器用于存储每一代种群的优良个体，算法执行初始阶段，存储器中是一组随机生成的个体，每一个体代表着优化问题的一个候选解。进化器中包括两个主要算子：交叉和变异算子。进化器的作用是接收存储器传递过来的父代个体，对个体执行交叉和变异操作，得到子代个体。进化器产生的每一个子代个体都需要经过评价器的测试。在求解优化问题中，评价器往往是一个带有约束条件的待优化的单目标或多目标函数, 每个个体都有一个相应的目标函数值(标量或矢量形式)，根据预先设定的准则来比较个体间的优劣关系，以选择出优秀个体进入到下一代种群。

GA模型的执行时间在很大程度上集中在进化器和评价器上。就进化器组成部分而言，已经提出了不少改进策略[7-9]，这些改进策略在增强GA搜索性能的同时也带来了额外的时间成本。在个体评价过程中，执行时间主要取决于个体目标函数的计算次数。由此，我们可以初步设想通过减少目标函数的计算次数来达到缩短GA总的执行时间。

本文提出一种基于相似性评价策略的改进遗传算法IGA(Animprovedgeneticalgorithmbasedonsimilarstrategyofevaluation)。IGA与传统遗传算法TGA(Traditionalgeneticalgorithm)的执行流程基本一致[10]，不同之处主要表现在：(1)进化器中引入一种新的旋转交叉算子，达到增强种群个体多样性的目的。(2)在评价器中，本文借鉴了生物学物种相似性特点，通过分析个体性状的基因相似性规律，提出一种新的基因相似性计算方式。因此，在求解优化问题中，个体适应度的评价不再仅仅通过待优化的函数计算得到，通过对子个体与父个体进行相似性度量，根据度量的结果来指定子个体的适应度值f与可信度值r，r是一个反映个体适应度值f与真实适应度值接近的参数。通过在测试函数上的实验结果，我们验证了所提出算法的有效性和改进思想的先进性。

1　IGA描述

自然界中物种都各有其不同的特征性状，比如：世界上不存在两片完全一样的树叶，无论从大小、颜色、形状及重量，而决定这些特征性状的关键因素取决于物种自身内在的基因序列。通常，每一物种内在的不同基因对外表现出的特征状态是不一样的，物种内在的基因有其似性特点，但同时也存在着差异，但就基因相似概率来判断物种是否同属于一类末必可行。比如，老鼠和人类在基因、基因内容和DNA序列方面高度相似，仅从基因角度很难判断是鼠还是人。新的研究发现，人类基因有许多重复的内容，这些重复内容早期一直被称为“垃圾DNA＂，有学者认为正是重复的内容才分开了人与鼠。单就人类自身而言，做DNA鉴定，可以通过基因的相似特点来判定子女是否是父母所生，这源于子女的遗传物质各有一半分别来父亲和母亲。因此，子女在特征性状上和自己的父母存在相似的同时也存在着差异，这在生物学上的表现被称之为“基因”相似性和“基因”多样性。现实科技领域中，人们基于现有的基因学知识，通过模拟物种间的进化和遗传等演变过程，已经将GA很好地应用于许多实际复杂系统问题，但在求解复杂优化问题时，对个体间的相似性如何评价以及基因的多样性如何增强一直是众多学者研究的热点之处。在此，本文借鉴生物学知识，提出以下基因相似性评价策略和种群多样性的增强方法，从而更好地优化GA模型功能，提高解决实际问题的能力，同时也为模拟生物学某些特有现象以更好地为提高解决复杂系统问题的能力提供了一定可借鉴之处。

1.1相似性评价策略

从遗传学角度来说，物种的父代与子代之间，通常父代的基因特征决定着子代的对外特征表现，也即子代的特征在某种程度上依赖于父代的内在基因特征，父代的基因遗传物质即有完全遗传的可能，也有发生变异遗传的概率；同一染色体中，处于不同位置的基因在决定对外特征的表现功能也是不一样的。类似地，在GA求解复杂系统问题的每一代进化过程中，由于子个体与父个体存在着较高的相似特征，子个体的适应度值在一定程上依赖于父个体的适应度值；因此，子个体的适应度值可以基于父个体的适应度值为参照来评价其自身的适应度值，暂时不考虑个体真实适应度函数的计算方式，在某种程度上能够减少目标函数的计算次数，缩短算法的执行时间。显然，这对提高GA的执行效率，优化GA模型的功能起到了一定的实质效果。但仅仅采用这种策略来计算个体的适应度值是不完善的，当种群中个体适应度值严重与个体真实的适应度值失真时(即两者相差较大)，就会影响优良个体进入下一代种群；在此，给每个个体设定一个与之相应的评价其适应度值好坏的可信度参数r，当r小于预先设定的阈值T时，重新使用真实的适应度函数来计算个体的适应度值；否则，就使用预先设定的适应度评价策略来评价个体的适应度值。在此，称这两种情况下得到的适应度值分别为“真实性适应度值”TFV(Truefitnessvalue)和“评价性适应度值”EFV(Evaluationfitnessvalue)。

本文在相似性评价策略中，可信度r的设定方式考虑子个体与父个体两者间的适应度比值关系，使r能够更好地反映出个体EFV的可信程度。另外，在EFV的评价方式上，本文算法并不简单计算子个体与父个体同位互异基因的个数，通过给每一位基因位分别指定一个相应的效能系数λ，计算出子个体与父个体间的差分，由此确定出两者的相似性。实验中，使用本文算法给出的评价个体适应度的方式，可以缩短与EFV和TFV间的差距。此外，本文算法的可信度阈值T采用了固定和动态地两种方式。这样，算法执行时就能动态地调节具有EFV的个体比例，使得评价过程在确保优良个体进入下一代种群的同时，也更加接近真实状态下的选择过程。

本文算法生成下一代子个体的方式按以下步骤进行：

随机性生成一个初始种群。每个个体p均由三个元素组成：二进制编码字符串(染色体)、适应度值f、可信度r。初始种群中的每个个体使用真实的适应度函数计算f，并置r为1。

(1) 从种群中选择两个父个体p1和p2进行交叉与变异运算，并对生成的子个体c1与c2分别计算个体的f和r。

子个体与父个体相似性的度量，使用的是个体间的差分计算方式，由于处于不同位置的基因重要性是不相同的。在此，本文给出以下计算个体间差异的权值差分方法：

(1)

其中，函数D(c, p)计算出子个体c与父个体p间的差分值，个体的染色体编码形式为：c=(c0,c1,…,cn-1)、p=(p0,p1,…,pn-1)。参数用于调节不同基因位受重视的程度，称为效能系数；子个体c与父个体p间的差分是一个介于0与1之间的数字，两个体间的相似性由下式给出：

S = 1-D(c, p)

(2)

可以看出：个体间的差分D(c, p)越大，个体间的相似性就越小；反之越大。

在此，假定子个体c1与父个体p1、p2的相似性分别为S1、S2。如果S1= 1，表明子个体c1与父个体p1完全“相似”， 从遗传学角度来说，c1完全继承了父个体p1的全部基因；此时，c1的两个元素分别设置为：f = f1, r = r1；否则，如果S2= 1，则f = f2, r = r2。

如果上述两个条件都不满足，则个体c1的适应度f和可信度r分别按下述方式进行计算：

(3)

(4)

对于种群中的每个个体而言，个体的可信度r是一个介于0与1间的数值，反映了个体EFV和TFV间的近似程度。r越大，EFV越接近TFV。因此，在子个体可信度r的计算方式上融入对适应度的比值计算是可行的，仿真实验表明：这种改进在一定程度提高了个体适应度的可信度，降低了对目标函数的计算次数，提高了算法的运行效率。

(2) 从种群个体适应度是否真实性的角度出发，如果完全采用上述个体适应度的评价方式，则种群中个体的适应度值与真实的适应度值就会产生严重的“失真”，不利于选择过程的进行。为此，本文算法中预先设定一个阈值T，如果个体的r小于T，则f采用真实的适应度函数计算方式代替“评价性适应度值”，并重新置r = 1；否则，保留“评价性适度值f”，并维持目前的r。实验中T的设置分两种情况：一种是动态地进行设置。在每一代种群中统计出具有“评价性适应度值”个体占有的比率k，若k小于指定的W1，则T按照指定的方式动态变小；若k大于指定的阈值W2，则T以指定的方式动态变大；两种情况都不满足，则保持 T不变。另一种方式是在算法执行的整个过程中，T始终保持不变。比较这两种方式，T的动态设置更有利于调节种群中具有TFV的个体比率，提高选择过程的真实性。从式(3)和式(4)可以看出：子个体c1的适应度值总是介于两个父个体f1与f2之间，其可信度r

1.2旋转交叉算子

对于从种群中选定的两个个体p1与p2，先将每个个体首尾相连，构成一个圆环形状，再让两个圆环相交，并同时让两个圆环按预置的速度分别进行旋转，在设定的时刻到达后，互换圆环交叉部分，达到增强种群多样性的目的，具体过程见图2所示。

p1=1001101010110011

p2=1011011100110010

图2　旋转交叉过程

1.3变异算子

变异是在种群中按照变异概率pm任选若干基因位改变其位值，对于二进制编码来说，就是反转位值。本文所提出的算法中，使用与传统进化算法相同的变异方式[9]。

2　仿真结果

本文选用来自文献[10]的两个标准测试函数来验证所提出算法的有效性，每一个输入参数使用8位二进制编码方式，因此，每位基因的效能系数λi根据其二进制所在的权值做归一化处理，见表1所示。

表1　效能系数计算方式

测试函数描述如下：

-5.12

-200

其中,F1(x)和F2(x)两个函数的维数D=20。TGA和IGA用于求解上述两个函数的最大值。两种算法在两个测试函数中使用的参数设置相同，参数设置见表2所示。

表2　TGA和IGA在不同测试函数中的参数设置

比较TGA和IGA两种算法间的性能差异，我们考察整个行进过程中出现的三个重要时刻来评价各算法间的性能优劣。根据总的函数评价次数Niter，这三个位置时刻分别设定在1/3Niter、2/3Niter和Niter位置。针对每一个位置，都有一个对应的测试点， 例如，在E1=1/3 Niter时，其对应的测试点如图3所示。

图3　IGA和TGA性能差异的比较

图3中实线和虚线分别描述了TGA和IGA在每次评价中的最优适应度值变化曲线。在E1=1/3Niter时, 图2中的两个菱形和圆点被用于比较TGA和IGA的性能差异，其性能测试准则定义如下[4]：

在此，ΔE介于0和1之间，若E2为某一固定值，ΔE越大，则由IGA获得与TGA相同的适应度值所需要的评价次数越少。而ΔF越大，在相同的评价次数下，由IGA获得的适应度值越大。

图4显示出TGA和IGA在不同测试函数上的进化曲线过程，星号(“﹡”)线描述TGA求解函数最优适应度值的曲线变化过程；菱形(“◇”)线描述IGA在固定阈值T=0.4时的寻优路径；叉形 (“×”) 线描述IGA在动态阈值T初始为0.8，且阈值W=W1=W2=0.5的动态变化曲线。在图4(a)中，可以观察到这样一种现象，IGA在固定和动态阈值T的情况下，都能最终获得测试函数的最优适应度值，两者在进化过程中的路径变化较为相似，也即每次函数评价时，得到的最优适应度值较为相近，但IGA在动态阈值 T变化情况下获得最优适应度值略微更好。IGA和TGA两种算法最终都能求得F1函数的最优适应度值，在进过程中，IGA的两种阈值设置方式得到的最优适应度值都略高于TGA。在图4(b)中也出现了与图4(a)类似的情况，但两种算法获得的最优适应度值只能接近真实最优适应度值，并且IGA在动态情况下获得的最优适应度值最好。

图4　GA 和IGA在不同测试函数上的进化曲线

表3和表4分别描述了GA和IGA在两个函数寻优过程中，在三个测试点上表现出来的性能差异，可以看出：通过IGA获得与TGA相同的适应度值，IGA所需要的评价次数明显较少，而执行相同的评价次数时，IGA相对于GA能够获得更高的适应度值。例如，对函数F1而言：在测试点TP1上，若T=0.4，说明IGA需要的评价次数相对于TGA要少13.41%, 而在相同的评价次数下，IGA获得的EFV比通过TGA获得的TFV要高10.27%。 虽然ΔF在三个测试点上的性能都能计算出来，但在最终测试点TP3，由于TGA很难以实现与IGA相同的最优适应度值，故ΔE无法计算。表格中的数据显示出：IGA在两种阈值T的设置中，动态阈值T的效果较好。

表3　GA 和IGA在函数F1 上的性能比较

表4　GA和IGA在函数F2 上的性能比较

综上所述，本文在TGA中引入相似性评价策略并提出IGA。在IGA执行过程中，子个体能够较好地根据与父个体的相似性及可性度r计算个体的“评价性适应度值”，从而减少真实个体适应度的计算次数，有利于缩短总的寻优时间，测试准则上的数据也较好地说明本文提出的“评价策略”能够确保种群在接近真实适应度值的同时，缩短评价次数，最终获得理想的最优适应度值结果。

3　结　语

本文从遗传学角度，探讨了一种评价个体相似性的策略，在TGA中引入这种个体相似性评价策略，实验的效果显示出IGA能够以较少的评价次数得到与TGA的十分接近的结果。就两个测试准则而言，IGA在动态阈值T下取得的效果要比固定阈值T下取得的效果更好，但两种设置方式相对TGA，都能以相对较少的评价次数获得接近真状下的TFV，虽然在进化过程中，IGA中个体的适应度值都要略高于TGA，但IGA最终也能较好地求得全局最优解。

本文算法的后继工作将分析IGA的时间及复杂度性能，并借鉴生物学中的其他知识，通过真实的模拟其内在演变规律，达到更好的优化GA模型功能，从而为生物学知识转变为现实的解决复杂系统问题的方式提供一定的可借鉴之处。

[1] 李学峰. 遗传算法同步选择特征和支持向量机参数的网络入侵检测[J].计算机应用与软件，2014，31(3)：301-303,333.

[2] 张彬，邓红霞，李海芳．应用两阶段遗传算法优化求解动态因果模型[J]．计算机应用与软件，2014，31(4)：278-280,292．

[3] 朱夏, 李小平,王茜.基于总空闲时间增量的无等待流水调度混合遗传算法[J]. 计算机研究与发展, 2011,48(3):455-463.

[4]TangKZ,YuanXJ,SunTK,etal.Animprovedschemeforminimumcrossentropythresholdselectionbasedongeneticalgorithm[J].Knowledge-Basedsystems, 2011,24(8):1131-1138.

[5]TangKZ,SunTK,YangJY.Animprovedgeneticalgorithmbasedonanovelselectionstrategyfornonlinearprogrammingproblems[J].Computers&ChemcialEngineering, 2011, 35 (4): 615-621.

[6]SalamiM,HendtlassT.Afastevaluationstrategyforevolutionaryalgorithms[J].Appliedsoftcomputing, 2003,2(3):156-173.

[7]TangKZ,YangJY,ChenHY.Animprovedgeneticalgorithmfornonlinearprogrammingproblems[J].TheJournalofSystemsEngineeringandElectronic,2011,22(3):540-546.

[8] 刘全, 王晓燕, 傅启明.双精英协同进化遗传算法[J].软件学报, 2012,23(4):765-775.

[9]CasillasJ,Martlnez-LópezFJ.MiningUncertaindatawithmultiobjectivegeneticfuzzysystemstobeappliedinconsumerbehaviourmodelling[J].ExpertSystemsWithApplication, 2009,36(2):1645-1659.

[10] 李敏强, 寇纪凇. 遗传算法的基本理论与应用[M].北京：科学出版社，2002.

[11]KumarS,RaoCSP.Applicationofantcolony,geneticalgorithmanddatamining-basedtechniquesforscheduling[J].RoboticsandComputer-IntegratedManufacturing,2009,25(6):901-908.

[12]ZhanZH,ZhangJ,LiY,etal.AdaptiveParticleswarmoptimization[J].IEEETransactionsonSystems,Man,andCybernetics-PartB:Cybernetics,2009,39(6):1362-1381.

IMPROVEDGENETICALGORITHMBASEDONINDIVIDUALSIMILARITYEVALUATIONSTRATEGY

TangKezong1ZhangTong2LuoLimin1

1(School of Computer Science and Engineering, Southeast University, Nanjing 210094,Jiangsu,China)2(Institute of Information Engineering, Jingdezhen Ceramic Institute, Jingdezhen 333403,Jiangxi,China)

Geneticalgorithmisamethodofsearchingtheoptimalsolutionbysimulatingnaturalevolutionaryprocess.Butitalwaysrequireslongercomputationtimeforthebestsolutioninsolvingprocess.Thispaperpresentsanimprovedgeneticalgorithm,itisbasedonindividualsimilarityevaluationstrategy.Initanewrotationcrossoveroperatorisincorporated.Thefitnessvalueofeachindividualisassignedaccordingtoitssimilarityandreliabilitywithitsparents.Therealfitnessofindividualisonlyevaluatedwhenthereliabilityvalueisbelowathreshold.Experimentalresultsshowthatthefitnessvaluesofindividualderivedfromsimilarityevaluationstrategyareclosetotheactualones,andthenumberofevaluationsrequiredforseekingtheoptimalsolutionbytheimprovedgeneticalgorithmissignificantlylessthanthatoftraditionalgeneticalgorithm.Additionally,thedataontestcriterionshowthattheperformanceoftheproposedalgorithmandtheoptimalsolutionderivedfromitarerelativelybetterthanthetraditionalgeneticalgorithmaswell.

GeneticalgorithmSimilarityevaluationCrossoveroperator

2014-07-09。国家自然科学基金项目(61202313)；江西省教育厅科研项目(GJJ13637，2013BAB211020)。汤可宗，副教授，主研领域：多目标优化。张彤，本科。罗立民，教授。

TP301.6

ADOI:10.3969/j.issn.1000-386x.2016.03.055