混合精英策略的元胞多目标遗传算法及其应用

王福才，周鲁苹

(鲁东大学信息与电气工程学院,山东烟台 264001)



混合精英策略的元胞多目标遗传算法及其应用

王福才，周鲁苹

(鲁东大学信息与电气工程学院,山东烟台 264001)

摘要：为了提高Pareto解集的收敛性,平衡多目标优化的全局搜索和局部寻优的能力，提出一种混合精英策略的元胞多目标遗传算法.该算法在分析元胞种群结构的特点基础上，融入一种混合精英策略，提高算法的收敛性能.为了更好的平衡算法的全局搜索和局部寻优的能力，加入一种差分进化交叉算子.通过与同类算法在21个基准函数上对比实验，结果表明，引入混合精英策略和差分进化策略能够提高算法的性能，与其他优秀算法进行比较的结果说明，新算法有更好的收敛性和多样性.工程实例求解结果表明了算法的工程可行性.

关键词:多目标；元胞遗传算法；混合精英；差分进化；函数优化；桁架结构

1引言

科学研究与工程领域中的优化问题大都是多目标优化问题(Multi-objective Optimization Problems,MOPs).为有效求解这类问题,人们提出了多目标进化算法(Multi-objective Evolutionary Algorithm,MOEA).过去的20年中，多目标进化算法在解决多目标优化问题上取得了长足发展，也涌现出了许多优秀算法，主要有NSGA-II[1]、PAES[2]、SPEA2[3]、MOEA/D[4]和MOCell[5]等.西班牙学者Enrique Alba[6]将进化算法按照种群结构的分布方式，可以分为两类，分别为单种群进化算法和结构化种群进化算法，而上述优秀算法中绝大多数属于单种群进化算法.

元胞遗传算法是一种结构化种群进化算法，且已经被证明在解决很多单目标优化问题时非常高效[7].Kirley M[8]提出了一种集合种群进化算法(Metapopulation Evolutionary Algorithm,MEA)，该算法是以在种群中偶尔发生灾变机制为特色的元胞模型，当灾变发生的时候，灾变区域的所有个体都会灭绝同时这个空的区域也会被其他个体占据.鲁宇明等人[9]将元胞自动机的演化规则融合到元胞遗传算法中，提出了一种具有演化规则的元胞遗传算法.Enrique Alba等人[10]在解决城市移动自组网广播策略问题的过程中，提出了一种新型的多目标元胞遗传算法cMOGA，该算法一般被认为是基于经典元胞遗传算法模型的第一个多目标元胞遗传算法.在cMOGA的基础上，为了更加适应多目标优化领域的要求，Antonio J.Nebro等[5]提出了MOCell算法，MOCell与cMOGA相比的一个主要改进就是引入了反馈机制，即在每次迭代完成后会将一定数量的解从外部文档返回到种群中，随机替换掉种群中相等数量的个体，测试对比表明MOCell算法性能远优于cMOGA算法，说明精英策略对算法性能影响较大.

根据相关研究，元胞多目标遗传算法在求解多目标优化问题时，算法的多样性较好.鉴于元胞多目标遗传算法的特点，如何提高算法的收敛性并更好的平衡全局搜索和局部寻优能力？这是个值得研究的问题.为了解决这两个问题，在MOCell基础上，提出一种混合精英策略的元胞多目标遗传算法(Cellular Multi-Objective Genetic Algorithm based Hybrid Elite Strategy,CMOGA-HES).该算法首先研究元胞邻居结构对算法性能的基础上，提出一种混合精英策略，从而更加有效的提高收敛性能.基于元胞种群结构的特点，每个个体只能与其邻居个体进行进化操作，在一定程度上有利于算法的局部寻优，为了增强算法的全局搜索能力，引入一种差分进化策略，从而更好的平衡算法的全局搜索和局部寻优性能.实验结果表明，CMOGA-HES算法与其他几种典型的算法相比，有一定的竞争力.

2元胞多目标遗传算法

Enrique Alba等人[6]根据种群的分布情况，将进化算法分为两类，一类是随机交配种群结构，如图1(a)所示；一类是结构化种群，而结构化种群又分为分布式式种群结构(图1(b)所示)和元胞种群结构.

元胞遗传算法[6]是将元胞自动机的拓扑特性同遗传算法的基本理论相结合而发展起来的一种优化算法，因此该算法不仅继承了遗传算法的优良品质，而且拥有元胞自动机的部分特性.其特点在于将种群中的每个个体分布于一个二维拓扑结构中(图1(c)所示)，每个个体拥有相同的邻居数，且每个个体只能与其规定的邻居个体进行遗传操作.遗传操作限制在邻域范围内进行，在一定程度上降低了选择压力.

元胞多目标遗传算法[5]MOCell(如图2所示)，是基于元胞遗传算法的大框架下，加入了多目标进化理论和策略.MOCell算法也是基于cMOGA算法的基础上加入外部存档精英保留策略，结果表明MOCell算法相对于cMOGA有较好的收敛性和多样性，也说明精英保留策略有利于提高算法的性能.

MOCell算法的基本思想如表1所示，首先生产一个空的外部存档，用于存储进化过程中的非支配(第2行).将初始种群分布于一个二维的网格结构中，每个个体都有对应的邻居(第4、5行).从邻居中选择父代个体进行交叉变异操作(第6～8行).对产生的子代个体进行评估，并进行替换策略(第9、10行).将种群中的非支配解存入外部存档(第11行).每一次迭代完成后，新产生的辅助种群被当作下一次循环的新种群(第13行)，并执行反馈策略(第14行)，如此循环直到满足循环终止条件为止(第3行).

表1　元胞多目标遗传算法的伪代码

3CMOGA-HES算法

大部分进化算法在求解优化问题时，总是力求在算法的多样性和收敛性方面寻求一种平衡,在全局搜索和局部寻优的过程中寻找一种平衡.本文在研究元胞多目标遗传算法的基础上，为了很好的平衡算法的全局搜索和局部寻优能力，分别引入一种混合精英策略和差分进化策略.使用混合精英策略，促使更多的精英个体参与到进化过程中，但为了避免算法陷入局部收敛，将种群中每个个体放置于二维元胞自动机模型中，使每个个体只能同规定的邻居个体进行遗传操作，从而有利于精英个体在算法中缓慢扩散，降低了算法的选择压力，提高全局搜索能力.利用差分进化策略具有搜索能力强，有利于保持算法的多样性的特点，加强算法的多样性和局部寻优能力.

3.1混合精英策略

在进化过程中，精英个体对算法的性能产生巨大的影响，尤其是对算法的收敛性，正确的引入精英个体有利加快算法的收敛速度，提高算法效率.现有基于精英策略的进化算法中，对精英个体的保存通常采用两种经典的方法：一种是外部存档法，利用外部存档保存当前所有的非支配解，并一定数目反馈至种群，实现精英个体参与种群进化，其中代表算法有SPEA2[3]等；另一种是NSGA-II[1]算法使用的辅助种群小生境法，将父代个体产生的子代个体保留至辅助种群中，一次进化后，将父代个体和子代个体融合，通过支配关系和拥挤距离进行排序，优先选择其中精英个体组成下一代的进化种群.

在MOCell算法中，使用外部存档来存储进化过程中得到的非支配解，作为一种精英机制可以使得MOCell具有较快的收敛速度.然而，精英个体仅仅只是存储在外部文档中，并没有有效地参与到种群的进化过程中.为了能充分发挥非劣解在进化过程中的作用，本文将两种上述的外部存档和辅助种群小生境法进行结合，形成一种混合精英策略(Hybrid Elite Strategy，HES)，其示意图如图3所示.具体操作：

UniPop=Union(Archiveg+AuxPopg)

(1)

(2)

Ranking()=Sorting(Distance(UniPopi,D),F(UniPopi,D))

(3)

OfferspringPop=Select(Ranking(UniPop))

(4)

其中：g为当前进化代数；Archiveg为外部存档；AuxPopg为辅助种群；UniPop为合并后的种群；OfferspringPop为子代种群；Distance()为拥挤距离评估函数；D为决策空间大小；F()为适应度函数；Sorting()为根据个体支配关系和拥挤距离进行排序函数；Ranking()为排序函数；Selcet()为选择函数.

将种群分布于元胞拓扑结构中，可以提高算法的多样性，文献[5,9,11,12]表明元胞遗传算法有较好的多样性.本算法通过将外部存档和辅助种群融合，进行快速非支配排序后，外部存档中的个体能得到充分地利用，种群中的优良个体能更多地被保留下来，尤其在进化初期可以促使精英个体引导进化，从而加快收敛速度.由于将种群分布元胞结构中，也促使种群中优良个体缓慢的扩散，从而可以缓解算法陷于局部收敛的可能性，能够有效的平衡算法的收敛性和多样性.

3.2差分进化策略

差分进化策略(Differential Evolution，DE)利用了群体中个体之间的距离和方向信息，具有全局并行直接搜索的特点，适于求解高维、非线性的多目标问题，而且实施起来相对较容易[13].对于差分进化策略，存在多种进化模式，每种进化策略之间存在各自的特点，文献[14～16]对五种常见的进化模式进行了探讨，分析出不同的进化模式的优缺点.

本文为了平衡算法的全局搜索和局部寻优的能力，引入DE/rand-to-best/1/bin进化策略，该策略的具体方法为：

(5)

式中：Vi,D代表基准个体i，D代表决策空间大小，Xbest,D表示当前最优秀个体，Xr1,D、Xr2,D、和Xi,D代表随机选择的个体，K和F表示差分控制参数.结合元胞空间结构的特点和元胞遗传算法的特性，对于个体的选择为：Xi,D为元胞中心个体；Xr1,D和Xr2,D代表为从邻居个体中随机选择两个个体；对于Xbest,D个体，则从外部文档中随机的选择一个个体.

对于产生的个体Vi,D=[vi,1,…,vi,j,…,vi,D]中的每一分量vi,j，通过比较randj与交叉因子CR或j与K的大小关系，以判断是否使用Vi,j来替换Xi,j，从而得到新个体ui,D=[ui,1,…,ui,j,…,ui,D].其具体表达式为：

(6)

其中：K∈[0,D-1]之间的任意整数；randj∈[0,1]的任意随机数.

3.3CMOGA-HES算法流程

综合3.1节和3.2节在经典的元胞遗传算法上两方面改进，CMOGA-HES算法的算法流程如下所示：

Step1在决策变量空间D里随机生成初始化种群NP，将种群分布于一个二维的网格结构中，每个个体都有对应的邻居(本文选用Moore型，八邻居结构).

Step2根据DE进化策略，选择中心个体与2个邻居个体和1个外部存档个体，由4个父代个体进行差分交叉操作，最后执行多项式变异操作[1]，产生子代.对于新产生的子代个体与父代进行对比，如果优秀子代替换父代个体；否则，不替换.

Step3将外部存档中的个体和辅助种群进行融合，根据支配关系和拥挤距离信息进行排序，选择优秀个体组成下一代种群.

Step4判断是否满足终止条件，满足则输出非支配解集，否则转向Step2.

4实验与结果分析

为了对改进算法的性能做出全面评估，本文选用多目标优化领域经常采用的测试函数作为测试基准函数，包括ZDT[17]系列，WFG[18]系列和DTLZ[19]系列，其中ZDT系列和WFG系列是两目标测试函数，DTLZ系列是三目标测试函数.

4.1性能指标

为了评价算法求解测试问题的性能，两个关键指标必须要考虑到.一个是收敛性，即尽量使算法求出的Pareto前端与真实前端间的距离最小；另外一个是多样性，即尽量使得到的Pareto前端均匀宽广的沿着真实前端分布.为了对以上指标进行评价，一些研究人员提出了多种性能评价指标.本文选取HV[20]与IGD[21]两个评价指标对算法性能进行综合评价，另外还选取Epsilon[22]指标对收敛性进行评价.

(1)超体积(Hypervolume,HV)

超体积是用来计算获得的Pareto解集个体在目标域所覆盖的体积.这个指标可以对收敛性和多样性进行综合评价，其计算公式如式(7)

(7)

式中Q为所获得的Pareto前端的个数.对于这个Pareto前端中的每一个个体i，vi是由参考点W=(0，…，0)和成员i所形成的超体积，此指标越大表明所得的Pareto解集越能宽广地分布在其前端上.因此，其取值越大越好.

(2)反转世代距离(Inverted Generational Distance,IGD)

IGD是收敛性评价方法GD的反转，它计算Pareto面上均匀点到非支配解集上最小距离的平均值，其表达式如式(8)

(8)

其中，P*是覆盖整个Pareto最优面的均匀点，d(v,D)表示点v到非支配解集NDS中个体的最小欧氏距离，IGD能综合评价解集的收敛性和多样性.

(3)Epsilon(ε)

(9)

4.2同类算法对比分析

首先将改进算法CMOGA-HES与未使用混合精英策略的CMOGA-non-HES、MOCell以及 CellDE[19]进行比较，以便确定引入混合精英策略和差分进化策略可以提高算法的性能.选用的测试函数由ZDT系列、DTLZ 系列和WFG系列组成，这些问题的特征已经足够支持其得到的结论.算法的参数配置如表2所示.

表2　算法参数配置

表3　HV的平均值和标准差

按照表2中的参数配置好算法后，开始执行算法.由于进化算法在执行后得到的结果有一定的概率性(多次运行得到的结果可能不一样)，因此，所有算法都独立运行50次，并对得到的结果进行统计学分析.

实验结果如表3～表5所示，为了方便查看，表中每个问题的平均值和方差表示为：平均值/方差，其中最优值都用深灰色背景标出，次优值都用浅灰色背景标出.

表3是HV指标的平均值和标准差，这个指标是对算法的多样性和收敛性进行综合评判，其取值越大越好.由表3可知，在21个测试问题中，CMOGA-HES得到了11个问题的最优值，9个次优值，未加混合精英策略的CMOGA-non-HES获得了2个最优值，7个次优值，MOCell 得到了7个问题的最优值和4个次优值，而CellDE 只得到了1个问题的最优值和1个次优值，在这个指标中，CMOGA-HES具有明显的优势.对表4进一步分析，在2目标测试问题ZDT系列和WFG系列求解中，CMOGA-HES获得了8个最优值，6个次优值，MOCell表现次之，获得5个最优值，3个次优值，CMOGA-non-HES获得了1个最优值，5个次优值.由此可知，CMOGA-HES在14个2目标测试函数上面，均获得次优值以上的解，表明该算法在解决2目标问题上有较明显的优势.对于3目标DTLZ系列测试问题，CMOGA-HES获得了3个最优值，3个次优值，MOCell算法获得2个最优值，CellDE和CMOGA-non-HES各获得1个最优值，说明在解决 DTLZ 系列问题时，CMOGA-HES算法具有一定的优势.

表4中Epsilon性能指标可知，CMOGA-HES获得最优值比例为11/21，次优值为8/21，相对应的CMOGA-non-HES获得3个最优值，7个次优值，CellDE获得3最优值，2个次优值，NSGA-II最优值和次优值各获得4个.由统计，对于是否添加HES策略对比表明，HES策略有利于提高算法的收敛性，而对于CellDE、MOCell和CMOGA-non-HES算法都采用外部存档，三种算法的性能接近，MOCell算法稍微占优.对表4的结果做更细致的分析，对于ZDT系列测试问题，CMOGA-HES占有绝对优势，全部获得最优值，改进算法的优势较为明显；对于WFG系列问题，CMOGA-HES获得4个最优值和4个次优值，CMOGA-non-HES得到1个最优值和3个次优值，CellDE算法获得1个最优值和一个次优值，MOCell获得了3个最优值与1个次优值，这说明在 WFG 系列问题上，改进的算法有一定的优势.在3目标测试问题 DTLZ 系列上，CMOGA-HES、CMOGA-non-HES和CellDE算法各获得2个最优值，MOCell算法获得1个最优值，但是CMOGA-HES获得了4个次优值，再次表明改进算法相对于另外3种存在一定优势.

(续)表4

从表5 IGD 指标，可以直观的看出，在 21 个测试问题中，CMOGA-HES得到了9个问题的最优值和8个次优值，CMOGA-non-HES、MOCell和CellDE 各得到了4个问题的最优值.整体而言，CMOGA-HES还是占有较明显的优势.在对于2目标测试问题求解上，改进的算法相对另外3种算法占有较为明显的优势；对于3目标问题，改进的算法和CellDE算法的性能相当.

为了在统计意义上更加全面的比较分析多个算法的性能和稳定性，采用Friedman检验对结果进行分析，图4～图6给出了4种算法的在不同指标上的排序，图中数字1～4依次表示算法CMOGA-HES、CMOGA-non-HES、CellDE和MOCell.对于分布性指标HV，数值越大说明分布性越好，Epsilon和IGD指标，数值越小说明性能更好.对于HV指标，CMOGA-HES算法的数值最大，且是CellDE算法的两倍多.由1和2算法对比，可再次证实HES策略有利于提高算法的性能.对于IGD指标，CMOGA-HES算法性能最优，2和4算法性能相当.对于收敛性指标Epsilon，CMOGA-HES算法获得数值最小，且远远小于其他算法，说明改进的算法收敛性能优异.

综合以上分析，我们可以得出结论，从总体上来看，改进算法CMOGA-HES较CMOGA-non-HES、CellDE和MOCell性能有明显提高.一者说明，HES策略有利于提高算法的收敛性能，而元胞种群结构有助于算法的多样性，HES策略与元胞种群结构相互配合，较好的平衡了算法的多样性和收敛性；二者，引入的差分进化策略，有助于平衡种群的全局搜索和局部寻优能力.

4.3CMOGA-HES与其他算法对比分析

为了清楚改进算法与其他算法相比的竞争性，将改进算法与多目标优化领域的两个经典算法进行比较，即NSGA-II和SPEA2算法，且两种算法采用两种不同的精英保存机制，更便于对比.本文中，SPEA2算法的参数配置，其种群大小和外部文档的大小都设置为100，其他参数与NSGA-II算法的参数相同.每种算法独立运行50次，实验结果如表6和表7所示，表格中每个问题的最优解都用深灰色背景标出.

表6　Epsilon的平均值/标准差

从表6可以看出，在Epsilon指标上改进算法CMOGA-HES得到了12个问题中的10个最优值，SPEA2和NSGA-II都仅得到了1个最优值.所以，就Epsilon指标而言，与其他两个算法相比CMOGA-HES具有明显优势，表明该算法的收敛性较好，也说明HES策略相对于单个的精英保留策略有较好的收敛性.在2目标问题求解上，CMOGA-HES依旧保持绝对的优势，且在ZDT4和ZDT6问题上有一个数量级上的优势.对于求解3目标DTLZ系列问题，CMOGA-HES得到了7个问题中的5个最优值，SPEA2和NSGA-II各得到了1个问题中的最优值，由此表明，改进的算法在求解3目标问题是占有较明显的优势.

表7　IGD的平均值/标准差

从表7可以看出，在IGD指标上CMOGA-HES得到了12个问题中的9个最优值，NSGA-II得到了12个问题中的2个最优值，SPEA2获得1个最优值.因此，CMOGA-HES在IGD指标上比其他两个算法具有显著优势.

综合以上分析我们可以得出结论，CMOGA-HES与NSGA-II、SPEA2相比，还是有较强的竞争力.为了直观的显示出CMOGA-HES算法的性能，从50次运行结果中挑出每个算法得到的较好结果，将其与问题的真实Pareto前端画在一个图形中.由于数据量较大，这里只作出差异最为显著的DTLZ6问题的图形如图7～9所示.

5工程实例

为了进一步验证CMOGA-HES的性能，将其应用于含有约束条件的桁架结构优化设计问题.本文以10杆桁架结构作为对象，如图10所示.10桁架属于悬臂術架结构,各杆件材料相同，密度为ρ=2768kg/m3，弹性模量E=68950MPa，许用应力δ=172.3MPa，载荷P=444.5KN，L=914.4mm.设计变量上限为0.0258m2，下限为64.5×10-5m2.本文取优化目标分别为桁架结构总质量和节点1、2、3、4的最大位移.

为了进一步验证CMOGA-HES的性能，将其应用于含有约束条件的桁架结构优化设计问题，并与SPEA2算法对比分析.两算法相同的参数如下：种群规模大小NP=100，变异概率pm=1/len，其中len为决策变量的个数，最大进化代数为300代，其中CMOGA-HES的CR=0.1,F=0.5,K=0.5；SPEA2的交叉概率pc=0.9.

图11为两种算法获得Pareto前端比较图，可以明显看出CMOGA-HES获得极端值点更加宽广，分布更加均匀，能够为决策者提供更多的选择方案，说明了算法的工程有效性.

6结论

本文提出一种混合精英策略的元胞多目标遗传算法，CMOGA-HES.首先，在分析元胞多目标遗传算法的基础上，可知含有元胞种群结构的算法其多样性较好，为了进一步提高算法的收敛性，将一种混合精英策略用于处理种群与外部存档之间的关系.其次，为了更好的平衡算法的全局搜索和局部寻优的能力，分析不同的进化模式的优缺，将一种差分进化交叉算子引入算法中.最后，通过21个测试函数，进行同类算法比较分析，表明混合精英策略能够进一步提高算法的收敛性，且CMOGA-HES较对比算法整体性能更优；将其与NSGA-II和SPEA2两种典型的精英保存策略的算法进行对比分析，CMOGA-HES在Epsilon和IGD指标上都有较明显的优势，说明从收敛性和均匀性上综合考察，改进算法具有一定的竞争力.为了验证算法在求解约束问题和解决实际工程问题的性能，将其用于10杆桁架多目标优化问题中，求解结果表明了本文算法的实用性及可行性.

参考文献

[1]Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[2]Knowles J,Corne D.The pareto archived evolution strategy:A new baseline algorithm for pareto multiobjective optimisation[A].Evolutionary Computation,1999 .CEC 99.Proceedings of the 1999 Congress on[C].Washington,DC:IEEE,1999.98-105.

[3]Bleuler S,Brack M,Thiele L,et al.Multiobjective genetic programming:Reducing bloat using SPEA2[A].Evolutionary Computation，2001.Proceedings of the 2001 Congress on[C].Seoul：IEEE,2001.536-543.

[4]Zhang Q,Li H.MOEA/D:A multiobjective evolutionary algorithm based on decomposition[J].Evolutionary Computation,IEEE Transactions on,2007,11(6):712-731.

[5]Nebro A J,Durillo J J,Luna F,et al.MOCell:A cellular genetic algorithm for multiobjective optimization[J].International Journal of Intelligent Systems,2009,24(7):726-746.

[6]Enrique Alba,Bernabé Dorronsoro.Cellular Genetic Algorithms[M].New York:Springer-Verlag New York Inc,2008.3-47.

[7]Alba E,Dorronsoro B.The exploration/exploitation tradeoff in dynamic cellular genetic algorithms[J].IEEE Transactions on Evolutionary Computation,2005,9(2):126-142.

[8]Kirley M.MEA:A metapopulation evolutionary algorithm for multi-objective optimisation problems[A].Evolutionary Computation,2001,Proceedings of the 2001 Congress on[C].Seoul :IEEE,2001.949-956.

[9]鲁宇明,黎明,李凌.一种具有演化规则的元胞遗传算法[J].电子学报,2010,38(7):1603-1607.

Lu Yu-ming,Li Ming,Li Ling.The cellular genetic algorithm with evolutionary rule[J].Acta Electronica Sinica,2010,38(7):1603-1607.(in Chinese)

[10]Alba E,Dorronsoro B,Luna F,et al.A cellular multi-objective genetic algorithm for optimal broadcasting strategy in metropolitan MANETs[J].Computer Communications,2007,30(4):685-697.

[11]Durillo J J,Nebro A J,Luna F,et al.Solving three-objective optimization problems using a new hybrid cellular genetic algorithm[A].Parallel Problem Solving from Nature-PPSN X[C].Berlin：Springer Berlin Heidelberg,2008.661-670.

[12]詹腾,张屹,朱大林,刘铮,等.基于多策略差分进化的元胞多目标遗传算法[J].计算机集成制造系统,2014,20(6):1342-1351.

Zhan Teng,Zhang Yi,Zhu Dalin,Liu Zheng,et al.Cellular multi-objective genetic algorithm based on multi-strategy differential evolution[J].Computer Integrated Manufacturing Systems,2014,20(6):1342-1351.(in Chinese)

[13]史彦军.复杂布局的协同差异演化方法与应用研究[D].大连：大连理工大学，2005.

SHI Yan-Jun.Thecooperative co-evolutionary differential evolution and its applications for complex layout optimization[D].Dalian:Dalian University of Technology,2005.(in Chinese)

[14]Qin A K,HUANG V L,SUSANTHAN P.Differential evolution algorithm with strategy adaptation for global numerical optimization[J].IEEE Transactions on Evolutionary Computation,2009,13(2):398-417.

[15]贺毅朝,王熙照,刘坤起,王彦祺.差分演化的收敛性分析与算法改进[J].软件学报，2010,21(5):875-885.

He Yichao,Wang Xizhao,Liu Kunqi et al.Convergent analysis and algorithmic improvement of differential evolution[J].Journal of Software,2010,21(5):875-885.(in Chinese)

[16]彭虎,吴志健,周新宇,邓长寿.基于精英区域学习的动态差分进化算法[J].电子学报,2014,42(8):1522-1530.

Peng Hu,Wu Zhijian,Zhou Xinyu,Deng Changshou.Dynamic differential evolution algorithm based on elite local learning[J].Acta Electronica Sinica,2014,42(8):1522-1530.(in Chinese)

[17]Zitzler E,Deb K,Thiele L.Comparison of multi-objective evolutionary algorithms:Empirical results[J].Evolutionary Computation,2000,8(2):173-195.

[18]Huband S,Barone L,While L,et al.A scalable multi-objective test problem toolkit[A].Proceedings of the Evolutionary Multi-criterion Optimization’05[C].Berlin,Germany:Springer,2005.280-295.

[19]Deb K,Thiele L,Laumanns M,et al.Scalable multi-objective optimization test problems[A].Proceedings of the 2002 Congress on Evolutionary Computation[C].Honolulu,USA：IEEE,2002.825-830.

[20]Zitzler E,Thiele L.Multi-objective evolutionary algorithms:a comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.

[21]Bosman T,Thierens D.The balance between proximity and diversity in multi-objective evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation,2003,7(2):174-188.

[22]Zitzler E,Thiele L,Laumanns M,Fonseca C M,Fonseca V G .Performance assessment of multi-objective optimizers:an analysis and review[J].IEEE Transactions on Evolutionary Computation,2003,7(2):117-132.

王福才男，1966年1月出生于山东烟台，现为鲁东大学信息与电气工程学院副教授，研究方向为信息与自动化，主持国家及省部级科研项目10余项，在国内外期刊发表论文10余篇.

E-mail:fucaiwang2002@aliyun.com

周鲁苹女，1970年4月出生于山东烟台，现为鲁东大学信息与电气工程学院讲师，研究方向为信息与自动化，主持参与省部级科研项目6项，在国内外期刊发表论文10余篇.

Cellular Multi-objective Genetic Algorithm Based on Hybrid Elite and Application

WANG Fu-cai,ZHOU Lu-ping

(DepartmentofInformationandElectricalEngineering,LudongUniversity,Yantai，Shandong264025,China)

Abstract:In order to maintain better convergence of Pareto sets and to balance the global search and local optimization ability,the cellular multi-objective genetic algorithm based hybrid elite strategy (CMOGA-HES) was introduced.The algorithm is integrated into a hybrid elitist strategy to improve the convergence performance，which is based on analyzing the cellular population structure characteristics.For better balance between exploitation and exploration,a differential evolution crossover operator is proposed.Comparing with the similar cellular genetic algorithm by testing 21 benchmark functions,CMOGA-HES can improve the algorithm performance and outperform several state-of-the-art multi-objective metaheuristics in terms of convergence and diversity.The results of engineering example showed the feasibility of the proposed algorithm.

Key words:multi-objective;cellular genetic algorithm;hybrid elite strategy;differential evolution;function optimization;truss structure

作者简介

DOI:电子学报URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.032

中图分类号:TP301

文献标识码：A

文章编号：0372-2112 (2016)03-0709-09

基金项目:山东省自然科学基金(No.ZR2010FL013)

收稿日期:2014-07-28;修回日期:2014-09-15；责任编辑：梅志强