2. 东北大学 流程工业综合自动化国家重点实验室，辽宁 沈阳 110819
2. State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, Shenyang 110819, China.
Corresponding author: WANG Hong-feng, E-mail: hfwang@mail.neu.edu.cn
多目标优化问题是科学和工程优化中普遍存在的优化问题，众多学者对多目标优化问题的优化技术进行了广泛而深入的研究.
进化算法通过交叉、变异等算子进行群体进化，已被广泛地用于求解多目标优化问题[1].Deb等[2]提出了一种非支配排序遗传算法，采用种群的非支配排序和拥挤距离评估提高算法搜索质量和收敛性能.Qu等[3]提出了规范目标值和分散选择的个体保留方法，有效地利用支配解信息以提高种群多样性.近年来，利用构造子种群的策略求解多目标优化问题已经引起了学者的广泛关注.Zhang等[4]考虑将多目标优化问题分解成一定数量的单目标子问题,将相似子问题的解构造子种群实施进化操作.Goh等[5]为每个决策变量构造子种群，提出了一种多种群协同和竞争机制的多目标进化算法.Zhang等[6]考虑为每个优化目标构造子种群，提出一种通过构造子种群实施单个目标搜索的多目标粒子群优化算法.Zhan等[7]采用为每个优化目标构造子种群的搜索方式，提出了多种群协同进化的多目标粒子群优化算法.
上述算法在迭代过程中使整个种群逐渐逼近于Pareto最优前沿，以获得一个近似最优且分布均匀的非支配解集.这就要求种群在决策空间内具有较好的分布，会影响算法对局部区域的开发能力.然而，在实际工程优化问题中，决策者往往只关注若干个非支配解，对解的质量和求解效率提出了更高的要求，这需要算法具有很好的搜索能力及同时获得多个非支配最优解的能力.为此，本文采用多种群策略实现了多个个体对一个非支配最优解的搜索，提出一种基于Species的多目标遗传算法(Species-based multiobjective genetic algorithm,SpeciesGA).该算法采用Tchebycheff方法将多目标优化问题分解为一定数量的单目标子问题，在每次迭代时基于Species机制为每个子问题分别构造子种群进行求解.这种基于多种群的搜索策略，可以提高对子问题的求解速度和精度.
1 本文提出的算法 1.1 算法基本思想传统多目标求解方法将多目标问题转化为单目标问题，加权求和方法和Tchebycheff方法是常用的转化方法，其中，Tchebycheff方法不依赖于问题特点，能够解决前沿面为凸或非凸形状的多目标优化问题.本文采用该方法将多目标优化问题进行转化，从而构建一定数量的单目标子问题.
令w=(w1,w2,…,wm)T表示权重向量，z*=(z*1,z2*,…,zm*)T表示理想点，对于最小化问题，zi*=min{fi(x)|x∈Ω}，i=1,2,…,m，其中，m为目标个数，Ω为解空间，则子问题为
对于给定的权重向量w，式(1)存在唯一的最优解，也是原多目标优化问题的非支配最优解.因此，可以通过设定不同的权重向量构建多个子问题，并采用基于Species机制的多种群方法为每个子问题构造子种群进行求解，以获得多个非支配解.由于权重向量与子问题为一一对应关系，在算法描述过程中将子问题称之为权重向量.
文献[8]提出基于Species机制的优化算法解决多峰优化问题，将Species(子种群)定义为种群中一组具有较高相似性的个体集合，一个Species由其Species种子及被种子支配的所有成员个体组成，该算法采用个体间Euclidean距离评价相似性.笔者之前的研究也提出了一种基于个体编号构造Species的方法[9].上述研究通过构造Species的方法实现了并行搜索多个最优解，这与本文解决多目标优化问题的求解思路类似.
1.2 算法基本流程本文提出的求解多目标优化问题的SpeciesGA的伪码如图 1所示.在完成算法参数和种群初始化后，算法将进入如下迭代过程：首先从当前种群中选择各子问题的最好解作为Species种子个体，针对各种子个体分别构造Species，并对Species进行独立的遗传进化操作；然后对Species种子个体执行局部搜索方法,并对理想点进行更新；最后选择各Species的优良个体作为下一代种群.
 | 图 1 SpeciesGA伪码图 Fig. 1 Pseudo-code for SpeciesGA |
本文所提出的算法在每次迭代时，首先在目标空间内为各个子问题分别选择最好解作为Species种子个体，然后在决策空间内基于各种子个体分别构造Species，这样就为每个子问题分别构造了Species.
采用Tchebycheff方法构建的子问题通常被认为同等重要，而极端点对应的子问题(即
=1，且
j∈[1,m] 满足wj=1)在选择Species种子时会优先选择极端目标上具有优势的个体，可能占用其他子问题的当前最好解.为解决该问题采用如下两种策略：①随机选择子问题并为其选择Species种子个体；②极端点的权重向量中分量为0的权重设为较小数，如10-4，以降低极端目标的选择压力.依据该方法，可以为每个子问题分别选择最好解，并将其作为Species的种子个体.Species的成员个体是由与种子个体相似性较高的个体组成，这里的相似性评价方法是计算个体与种子个体在决策空间的Euclidean距离.个体间的距离越小，表明它们的相似性越高.依据上述方法，将与种子个体相似性高的个体划分为一个Species，这样就可以为多个子问题分别构造了Species.这里规定各Species的成员个体不重合，即一个个体只能属于一个Species，Species的构造顺序与Species种子的选择顺序相同.
采用锦标赛选择机制从当前Species中选取优良个体进行遗传操作.该方法首先从Species中随机选择2个个体，将优良个体置于对应的配偶池(mating pool,MP)中；若2个个体目标值相等,则随机选择1个置于配偶池中.按此方法分别为各个Species选择参与交叉和变异的个体.
为保证各个Species能够独立进化，交叉和变异操作仅限于Species内进行.具体方法为：对各个Species对应的配偶池中的个体依次实施交叉和变异操作，将新生个体置于对应的Species，并在选择阶段依据精英保留策略选择各Species的优势个体遗传至下一代.这里采用文献[8]的方法执行交叉和变异操作.
1.5 局部搜索策略为了保证算法能够搜索到尽可能好的解，本文对各种子个体采用一种迭代的随机搜索策略[10]，以提高算法的开发能力.该方法产生一个随机向量作为个体移动方向，其方法如图 2所示.
 | 图 2 局域搜索算法流程图 Fig. 2 Pseudo-code for local searching method |
为验证本文所提出算法的性能，选取13个测试函数进行仿真实验，包括10个双目标测试函数，3个三目标测试函数.所有的测试函数可参见文献[11].
2.2 实验设置为验证算法在求解多目标问题的有效性，选取具有代表性的多目标算法MOEA/D[4],NSGA-II[2],COEA[5],AMOSA[12]作为对比算法.NSGA-II是被广泛应用的多目标算法，MOEA/D和COEA同样采用构造子种群的方法，而AMOSA是基于单点搜索的多目标模拟退火算法，5种算法均以50000次估值作为停止条件，设定子问题的数量为10.SpeciesGA的参数设置如下：种群大小为100，变异率为1/n，其中n为变量个数，实验分为两种方式.
方式一：在获得非支配解数量相同的情况下,评价算法的性能.算法参数设置如下：MOEA/D种群大小为10，每一子问题对应种群大小为2；NSGA-II种群大小为10；COEA和AMOSA外部档案大小为10；AMOSA的初始温度100，冷却系数0.95,结束温度2.5×10-6.
方式二：将对比算法获得的非支配解集中各子问题的最好解作为算法的评价解集.算法参数设置如下：MOEA/D种群大小为100，每一子问题对应种群大小为20；NSGA-II种群大小为100；COEA和AMOSA外部档案大小为100；AMOSA的其他参数设置同方式一.对比算法的其他参数设置均与原文献相同.
实验采用C指标评估算法性能，该指标用于评价两个非支配解集的覆盖率，如式(2)所示，其中X和Y分别表示两种算法获得的非支配解集.
若C(X,Y)=1，说明对于集中的任一非支配解，X集中总存在支配它的解；若C(X,Y)=0，说明对于集中的任一非支配解，X集中都不存在支配它的解.
2.3 实验结果与分析采用5种算法对每一测试函数分别求解30次,取性能指标的平均值作为评价依据.为有效地分析实验结果，采用自由度为58，显著性水平0.05的T检验方法,符号“+”、“-”、“~”分别表示SpeciesGA性能显著优于、显著劣于和基本等同于对比算法.
下面将检验所提出的SpeciesGA算法的C指标性能.表 1和表 2分别给出了方式一和方式二的实验结果，表中加粗的实验结果表示SpeciesGA的性能显著优于其对比算法.从表 1可以看出，SpeciesGA有10个算例显著优于MOEA/D,两种算法在ZDT1及LE1算例的优化性能上基本等同；有10个算例显著优于NSGA-II，另外有3个算例的优化效果基本等同；有10个算例显著优于COEA，且有4个算例优化效果基本等同；13个算例的优化效果均显著优于AMOSA.在该方式下，NSGA-II，COEA和AMOSA获得在目标空间中分布均匀的10个非支配解，而SpeciesGA和MOEA/D所生成的权重向量集在目标空间并不能达到均匀分布，所以得到的非支配解集可能与前者存在非支配关系.从表 2的实验结果可以看出，SpeciesGA中所有算例均显著优于MOEA/D；有11个算例显著优于NSGA-II，且有2个算例的实验结果基本等同；有11个算例显著优于COEA，另外有2个算例的实验结果基本等同；有14个算例显著优于AMOSA.在该方式下，5种算法所获得的非支配解集均为对应权重向量下的最好解的集合，更具有可比性.通过表 1和表 2的实验结果及统计分析可见，SpeciesGA具有较好的求解效果.为直观地展示算法性能，图 3和图 4分别给出了方式一和方式二下ZDT2的各个子问题最好解的分布图.从图中可以发现，在方式一下，由于对比算法的种群规模较小使其过快收敛，无法获得各子问题的近似最优解，而SpeciesGA表现出较好的效果；在方式二下，5种算法均可以获得各子问题的近似最优解，且SpeciesGA在一些子问题的求解效果要优于对比算法.
 | 表 1 方式一下算法的C指标性能比较 Table 1 Comparison of the performance via C-index in the first experimental way |
| 表 2 方式二下算法的C指标性能比较 Table 2 Comparison of the performance via C-index in the second experimental way |
 | 图 3 方式一下ZDT2的各子问题最好解的分布图 Fig. 3 Illustration of best solutions of subproblems for ZDT2 in the first experimental way |
 | 图 4 方式二下ZDT2的各子问题最好解的分布图 Fig. 4 Illustration of best solutions of subproblems for ZDT2 in the second experimental way |
综上，对13个标准测试函数的仿真实验分析可以发现，基于Species机制的多目标遗传算法(SpeciesGA)可以获得多个较高质量的非支配解，是一种求解多目标优化问题的有效方法.
3 结论本文研究了一种基于Species机制求解多目标优化问题的遗传算法(SpeciesGA).该算法采用Tchebycheff方法构建多个子问题，在每次迭代时通过采用多种群方法实现了对多个子问题最优解的并行搜索.这种采用多个体对一个最优解的搜索方式提高了算法的探索能力和开发能力.对一组多目标测试函数进行仿真实验，结果表明SpeciesGA能够获得较高质量的非支配解，具有较好的求解效果.
| [1] | Zhou A,Qu B,Li H,et al.Multiobjective evolutionary algorithms:a survey of the state of the art[J].Swarm and Evolutionary Computation,2011,1(1):32-49.( 1) |
| [2] | 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) |
| [3] | Qu B Y,Suganthan P N.Multi-objective evolutionary algorithms based on the summation of normalized objectives and diversified selection[J].Information Sciences,2010,180(17):3170-3181.(1) |
| [4] | Zhang Q,Li H.MOEA/D:a multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation, 2007,11(6):712-731.(2) |
| [5] | Goh C K,Tan K C.A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization[J].IEEE Transactions on Evolutionary Computation, 2009,13(1):103-127.(2) |
| [6] | Zhang Y,Gong D,Ding Z.Handling multi-objective optimization problems with a multi-swarm cooperative particle swarm optimizer[J].Expert Systems with Applications,2011,38(11):13933-13941.(1) |
| [7] | Zhan Z H,Li J J,Cao J N,et al.Multiple populations for multiple objectives:a coevolutionary technique for solving multiobjective optimization problems [J].IEEE Transactions on Cybernetics,2013,43(2):445-463.(1) |
| [8] | Li J P,Balazs M E,Parks G T,et al.A species conserving genetic algorithm for multimodal function optimization[J].Evolutionary Computation,2002,10(3):207-234.(2) |
| [9] | Wang H,Moon I,Yang S,et al.A memetic particle swarm optimization algorithm for multimodal optimization problems[J].Information Sciences,2012,197:38-52.(1) |
| [10] | Petalas Y G,Parsopoulos K E,Vrahatis M N.Memetic particle swarm optimization[J].Annals of Operation Research,2007,156(1):99-127.(1) |
| [11] | Huband S,Hingston P,Barone L,et al.A review of multiobjective test problems and a scalable test problem toolkit[J]. IEEE Transactions on Evolutionary Computation, 2006,10(5):477-506.(1) |
| [12] | Bandyopadhyay S,Saha S,Maulik U,et al.A simulated annealing-based multiobjective optimization algorithm:AMOSA[J].IEEE Transactions on Evolutionary Computation, 2008,12(3):269-283.(1) |