《1 引言》

1 引言

人类改造自然的方案规划与设计过程总体上反映了最大化效益、最小化成本这一基本优化原则。最大化效益、最小化成本实质上是一个多目标的优化问题 (MOP) 。效益可能包括多种效益, 如经济效益、政治效益与社会效益等;成本或损失也可能包括生产成本与非生产成本, 或与此相关联的其他目标如环境污染等方面损失。航天器总体设计中的有效载荷、射程、推力等指标参数的综合是一个典型的多目标的优化问题。控制工程中控制系统的稳、准、快等时域指标与稳定域度、系统带宽等频域特性的综合问题也是一个多目标工程优化设计问题。此外还有社会发展与国民经济的中长远发展计划的优化与决策问题等。一般说来, 科学与工程实践中的许多优化问题大都是多目标的优化与决策问题。

传统的多目标优化方法往往将其转化为各目标之加权和, 然后采用单目标的优化技术。但是, 这样做存在几大缺点:a.不同性质的目标之间单位不一致, 不易作比较;b.各目标加权值的分配带有较大的主观性;c.优化目标仅为各目标的加权和, 优化过程中各目标的优度进展不可操作;d.各目标之间通过决策变量相互制约, 往往存在相互矛盾的目标, 致使加权目标函数的拓扑结构十分复杂。基于传统数学规划原理的多目标优化方法在实际工程优化问题中往往表现出一定的脆弱性, 因此, 有必要研究高效实用的多目标优化与决策的算法及理论。

多目标优化/决策问题不存在唯一的全局最优解, 而是存在多个最优解的集合。多目标问题最优解集中的元素就全体目标而言是不可比较的, 一般称为Pareto最优解集[1]。所谓Pareto最优解集, 是对于一些解不可能进一步优化某一个或几个目标而其他目标不至于劣化, 因此也称为非劣最优解集。Pareto最优概念是建立在集合论基础上对多目标解的一种向量评估方式。而传统的数学规划法与模拟退火算法是以单点搜索为特征的串行算法, 不可能利用Pareto最优概念对解进行评估。因此, Pareto最优概念虽然提出来已百年有余, 但却仍无传统算法意义上的相关算法。基于种群操作的演化算法可以隐并行地搜索解空间的多个解, 并能利用不同解之间的相似性来提高其并发求解问题效率, 如果与Pareto最优概念相结合, 有可能产生真正基于Pareto最优概念的多目标优化的演化算法, 实现对非劣最优解集的搜索。

虽然Rosenberg曾提到可用基于遗传的搜索算法来求解多目标的优化问题[2], 但直到1985年才出现基于向量评估的遗传算法 (VEGA) [3], 这是第一个多目标演化算法 (MOEA) , 但仍然不是基于Pareto最优概念的演化算法。1990年后, 相继提出了不同的多目标演化算法[4]。1993年和1994年, 多目标遗传算法 (MOGA) [5]、非劣性分层遗传算法 (NSGA) [6]、小组决胜遗传算法 (NPGA) [7]已成为基于Pareto最优概念的多目标演化算法研究工作的奠基石。此外, 还存在一些不基于Pareto最优概念的多目标演化算法, 如多性别遗传算法[8]、目标向量方法[9]以及最大最小方法[10,11]等。多目标演化算法已用于燃气涡轮泵控制器设计[12]、航空器结构设计[13,14]以及汽车发动机优化设计[15]等等, 因此, 多目标演化算法研究直接受到实际工程问题的推动。尽管如此, 多目标优化与决策问题的演化计算技术中待研究的问题还很多, 如适应值赋值方法、选种配对机制、多目标演化种群动力学行为及其稳定性分析、非劣最优解域收敛性分析、种群更新终止条件以及实际多目标优化问题的演化求解等, 都是目前的研究热点。

实际的多目标问题不仅是一个优化问题, 而且最后往往归结为一个决策问题。运筹学研究领域曾采用数学规划的多目标优化技术对与设计领域紧密相关的多目标决策问题 (MODM) 作过一些研究[16,17], 这些设计问题的共同特征由三方面组成:一组定量的目标函数, 一组完整定义的设计约束, 以及一个可在诸目标之间作权衡的操作过程。

《2 多目标优化问题的数学描述》

2 多目标优化问题的数学描述

最小化与最大化问题可以相互转化, 因此, 仅以无约束最小化多目标问题为研究对象。

一个多目标问题可以表示如下, 其中决策向量x∈Rm, 目标向量y∈Rn:

miny=f(x)=(f1(x),f2(x),⋯,fn(x))。

定义1 优劣性 (dominance / inferiority) 如果目标向量解u = (u1, u2, …, un) 部分小于目标向量解v = (v1, v2, …, vn) , 也就是∀i∈{1, 2, …, n}, ui ≤ vi ∧∃ j∈{1, 2, …, n}, uj <vj, 则称u优于v, 记为up<v。 反之, 如果目标向量解u = (u1, u2, …, un) 部分大于目标向量解v = (v1, v2, …, vn) , 也就是∀i∈{1, 2, …, n}, ui ≥ vj∧∃ j∈{1, 2, …, n}, uj>vj, 则称u劣于v, 记为up>v。

定义2 非劣最优解 (Pareto optimal) 只有不存在决策变量xv∈Rn, 使得相应的目标向量解v =f (xv∈Rn) = (v1, v2, …, vn) 优于目标向量解u =f (xu∈Rn) = (u1, u2, …, un) , 即vp<u , 则称决策变量xu∈Rn为多目标问题的非劣最优解。

由所有非劣最优解组成的集合称为多目标优化问题的最优解集, 也称为可接受解集或有效解集, 记为Ptrue;相应非劣最优解的目标向量称为非支配的目标向量 (non-dominated) , 由所有非支配的目标向量构成多目标问题的非劣最优目标域 (Pareto front) , 记为PFtrue。 Ptrue与PFtrue由具体的多目标优化问题中各目标函数所决定, 是一个确定的不变集合。由优化算法所发现的非劣最优解组成的集合记为Pknown与PFknown, 使用演化算法求解多目标优化问题时, 隐含下列假设之一在某些赋范空间 (如欧氏空间, RMS赋范空间等) 中成立:Pknown = Ptrue, Pknown ⊂Ptrue或PFknown∈[PFtrue, PFtrue+ε] 。

《3 多目标优化与决策问题的求解技术分类》

3 多目标优化与决策问题的求解技术分类

《3.1多目标演化算法任务组成》

3.1多目标演化算法任务组成

多目标演化算法的任务分解如图1所示, 由以下功能任务单元组成:1为种群初始化过程;2为适应值评估过程;2a为向量目标→标量适应值转换过程;3为杂交操作;4为变异操作;5为选择过程。可见其主要任务组成与单目标优化演化算法相同, 其中2a部分是单目标演化算法所没有的。2a任务是把多目标问题解的向量表示转化为标量化的适应值, 决策者对各目标的偏重程度、权衡优先次序与对各目标的期望值, 通过2a部分转化为决策过程中的效用值, 对多目标演化算法的研究主要集中在2a部分, 不同的转换机制决定了不同的多目标演化算法。

《图1》

图1 多目标演化算法任务分解图

图1 多目标演化算法任务分解图  

Fig.1 MOEA task decomposition

《3.2多目标问题优化与决策的关系》

3.2多目标问题优化与决策的关系

与单目标优化问题的本质区别在于多目标问题的解是一个非劣最优解的集合, 实际的多目标问题往往希望按某些可以定量或定性的领域约束、目标偏好或难以表述的专家经验, 从这一非劣最优解集中选择唯一现实可行的最优方案。图2表示多目标优化与决策系统的基本构成方式, 非劣最优解的搜索过程由优化器实现, 解的选择过程由决策器完成。优化器可由演化算法等多目标优化算法实现, 而决策器则由决策专家或具有领域决策知识的专家系统承担。决策器可以从优化器对非劣最优域的搜索过程中不断获得与精炼决策信息, 而不断变化与丰富的决策信息可以逐步引导优化器搜索最感兴趣的非劣最优域。决策信息决定了非劣最优域的性质以及对最终解的选择结果, 一般以决策者对目标的偏好关系与程度、目标期望值、权衡优先次序、效用函数、模糊逻辑等表示, 因此, 多目标优化问题最终表现为一个与问题相关的本质主观的决策过程。有关偏好信息处理参见文献[18]。

《图2》

图2 多目标优化与决策器的系统构成

图2 多目标优化与决策器的系统构成  

Fig.2 A general multiobjective evolutionary optimizer

《3.3多目标问题演化算法分类》

3.3多目标问题演化算法分类

多目标演化算法是在多目标数学规划技术的基础上发展起来的。根据决策者对各目标主观偏重程度与非劣最优解搜索过程之间的相互影响关系, 多目标优化技术可分为三大类:先验优先权技术, 优先权演化技术与后验优先权技术。

《3.3.1 先验优先权技术 (决策→搜索) 》

3.3.1 先验优先权技术 (决策→搜索)

决策器事先 (主观) 设置各目标的优先权值, 将全体目标按权值合成一个标量效用函数, 把多目标优化问题转化成单目标优化问题。优点是多目标问题的决策过程隐含在标量化的总效用函数中, 对总效用函数的优化过程也是相应多目标问题的决策过程;缺点是很难获得各目标精确的先验优先权值, 而且相应多目标问题的Pareto最优解搜索空间受到限制。先验优先权技术可分为排序聚合方法与标量化聚合方法两类。

1) 排序聚合方法[19]

按目标的先验优先顺序, 解的优劣比较从最高优先级的目标开始, 如上一级目标出现平局, 则开始下一优先级目标的比较直至平局结束;算法采用排序选择法。特点是简单易执行, 所得多目标问题的解皆为Pareto最优解, 但当目标数过多时, 因对目标空间搜索的不平衡特性, 算法易收敛于非劣最优域的局部区域。

2) 标量化聚合方法

将多目标优化问题转化为单目标优化问题的方法, 可分为线性聚合方法与非线性聚合方法。非线性聚合方法又可分为乘性聚合方法、目标向量方法与最大最小方法。线性聚合方法即常规的加权法, 根据各目标的重要性赋以相应权值, 采用标准化的权向量对各目标进行线性加权, 原多目标问题化为单目标优化问题。Fonseca与Fleming指出, 由任何正的加权向量形成的加权目标函数的全局最优解一定是非劣最优解。线性聚合方法的特点是简单易执行, 但在非凸搜索空间中找不到适当的Pareto最优解。非线性聚合方法将多目标以非线性形式转化为单目标, 如乘性聚合方法以各目标之乘积形式转化为单目标优化问题[7]。目标向量方法则将多目标转化为某种范式下距预定目标向量之间的距离优化问题[9]。最大最小方法则将多目标问题转化为最小化距预定目标值中之最大者[10,11]。

《3.3.2 优先权演化技术 (决策←→搜索) 》

3.3.2 优先权演化技术 (决策←→搜索)

优先权决策 (决策器) 与非劣最优解的搜索过程 (优化器) 交替进行 (参见图2) , 变化的优先权可产生变化的非劣最优解集, 决策器从优化器的搜索过程中提取有利于精炼优先权设置的信息, 而优先权的设置则有利于优化器搜索到更感兴趣的非劣最优域。优先权演化技术中一般可采用后验优先权技术中的多目标演化算法。可以认为优先权演化技术是先验优先权技术与后验优先权技术的一种有机结合。

《3.3.3 后验优先权技术 (搜索→决策) 》

3.3.3 后验优先权技术 (搜索→决策)

优化器进行非劣最优解的搜索, 决策器从搜索到的非劣最优解集中进行选择, 选择过程就是一个优先权的决策过程。包括独立采样法与合作搜索法, 而合作搜索法又分为目标选择法、聚合选择法与Pareto选择法, 其中Pareto选择法又可分为Pareto排序法、Pareto排序与小生境法、同类群法及Pareto最优保持法。独立采样法以各目标的多种聚合形式对解空间进行独立搜索, 算法每次运行即是以不同加权向量形成聚合目标函数独立采样问题的非劣最优域[20]。在合作搜索法中, 各目标相互合作, 协同参与对非劣最优解域的搜索, 其中目标选择法中各目标轮流参与下代种群个体的选择, 如Shaffer的VEGA算法;聚合选择法则用各目标的线性或非线性聚合值来选择下代种群[21,22]。Pareto选择法采用Pareto最优概念对解进行选择, 如Pareto排序法基于Pareto最优概念对解进行优劣比较与排序[23];排序与小生境法则以Pareto最优概念对解进行排序并赋适应值, 然后通过共享函数将Pareto最优解均匀分布于非劣最优域, 如MOGA算法[5]、NSGA算法[6]与NPGA算法[7]等;同类群法在岛屿模型中基于解的Pareto排序及在种群中的几何位置对解进行选择[24];最优保持法则以解的精华状态作为选择准则, 将Pareto排序居先的最优解直接保留至下代种群, 剩余部分则以另外方式产生[25]。

此外, 如果按适应值赋值方法分类, 多目标优化技术可分为基于Pareto最优概念与不基于Pareto最优概念的两大类技术。基于Pareto概念的优化技术采用Pareto最优概念对多目标解进行比较与排序, 并基于Pareto排序进行适应值赋值, 如MOGA算法[5]、NSGA算法[6]以及NPGA算法[7]。不基于Pareto最优概念的多目标优化技术包括直接与间接的目标加权和方法。间接的目标加权和方法如VEGA方法[3]、BenTal的有序比较法与随机比较法[19]、概率向量选择法[26]以及加权向量与目标解向量混合编码方法[21]等, 虽然能提高种群的多样度, 但本质上都与传统直接加权法一样。如果按种群更新选择方案, 间接加权和方法又可分为按目标适应值的比例选择方法 (Shaffer[3], Hajela & Lin[21]) 、锦标赛选择法 (Ben Tal[19], Kursawe[26]) 与排序选择法 (Goldberg[27]) 等。锦标赛法与排序法克服了目标值尺度 (量纲) 的影响, 但与各目标的优先顺序有关。

《4 典型多目标演化算法的比较与分析》

4 典型多目标演化算法的比较与分析

多目标与单目标优化问题的本质区别是, 前者一般是一组或多组连续解的集合, 而后者只是单个解或一组不连续的解。得到一个解集合的近似解集比得到单个解的近似解难得多。本节代表性地介绍文献中五种比较常见的多目标演化算法:多性别遗传算法[8], VEGA算法[3], MOGA算法[5], NSGA算法[6], 以及NPGA算法[7], 其中前2种是不基于Pareto最优概念的间接加权算法, 后3种则是基于Pareto最优概念的多目标演化算法。

《4.1多性别遗传算法》

4.1多性别遗传算法

Allenson在做直线管道路径规划时提出了一种有性别的二目标优化演化算法[28]。两目标分别定义为雄性和雌性。个体产生时性别随机决定, 只允许异性个体之间杂交。个体适应值由其相应性别的目标函数值决定。初始种群中雌雄个体数相等, 但随着种群的更迭, 种群个体性别可能失衡, 每代中的最差个体由随机选取同性别的个体取代。Allenson还采用演化策略来实现生物个体之间的性别吸引机制, 以减少杂交算子的随机性。Lis与Eiben把Allenson 的方法扩展至三个以上的多目标优化问题, 并称为多性别遗传算法[8], 其中每一个目标都有相应的性别。多性别遗传算法的杂交算子有别于传统演化算法中的两两杂交算子, 允许多个不同性别个体之间随机交配, 由参与杂交的不同性别个体各取相应性别的部分基因生成杂交后代。杂交后代的性别由贡献基因数最多的亲本个体的性别决定, 当有两个以上个体贡献最大基因数量相同时, 后代个体性别在这些亲本性别中采用抽签法决定。变异算子不允许改变个体的性别。个体适应值由相应性别所标示的目标函数值决定。非劣最优解随种群更迭过程逐步更新, 即去掉过时的非劣解, 加进新的非劣解, 直至找到多目标问题的Pareto 最优解。多性别遗传算法对不同的目标定义了相应的子种群, 但这种子种群定义不同于VEGA算法。多性别遗传算法中的杂交算子只允许受限的随机杂交, 只有性别不同的个体之间才能杂交。因为生成一个杂交后代个体需要所有不同性别的个体参与杂交, 因此, 随着目标个数的增加, 在计算代价上这种受限随机杂交算子的效率将降低。

《4.2向量评估遗传算法 (VEGA) 》

4.2向量评估遗传算法 (VEGA)

Shaffer与Grefenstette利用演化算法对不同尺度的多目标优化问题分别处理, 可在一次演化计算过程中并发地搜索多个非劣最优解[3]。VEGA算法的基本思想是:分别利用每一目标从种群中选择部分个体, 组成相应的下代子种群, 然后混合各子种群, 从中均匀随机地选择配对个体进行杂交与变异, 生成新一代种群, 如此往复进行。子种群的归并混合是一个对各目标的相应标准化适应值实行平均的过程, 每一亲本所生子代个体的期望数是该亲本根据各目标所生子代个体期望数之和。因为VEGA算法采用适应值比例分配方案, 因此, 向量解个体的总体适应值相当于各目标的加权和, 只是加权指数随每代种群的分布而变化。这一结论已被Richardson[29]等提出并得到了Shaffer本人的证实[30]。与非劣最优解定义不相称的是不同的非劣最优解在VEGA算法中将赋以不同的适应值。VEGA算法易于在种群中形成相对于各目标的子种群, Shaffer称为物种形成。虽然VEGA本质上如同传统加权法一样不适合求解折中目标具有凹面的多目标问题, 但VEGA算法中隐含的加权方案有待进一步研究。VEGA算法中对每一目标的加权值与该目标的子种群大小成正比, 而与种群中该目标的平均适应值成反比。假定各目标子种群大小固定, VEGA算法的子种群选择方案将对各目标的优化进展进行自适应权衡, 即如果某一目标优化的进展较快, 该目标的平均适应值增大, 相应地该目标的加权值减小。VEGA算法对各目标的自动平衡原理与平衡多解问题中所用的共享函数法[31]有类似之处。与普通固定加权和算法相比, VEGA 算法对不同物种能够维持比较多的种群代数, 因而提高了种群的多样度。

Fourman提出了与VEGA 类似的算法。Fourman算法[20]中物种的选择采用锦标赛方案, 即基于某一固定或随机选择的目标来比较一对向量解之间的优劣, 如果前一次比较产生平局, 则按预定目标优先顺序或随机地选择下一个目标作为比较基准。这种基于锦标赛的选择方案本质上也是一种加权和方法, 各目标的权重与该目标被选为锦标赛准则的概率成比例。Fourman算法中采用逐对比较法对向量解进行排序, 锦标赛个体排序是对整个种群全排序的一种随机逼近, 克服了VEGA算法对目标尺度的依赖性。Kursawe提出一种基于预定目标选择概率向量的多目标演化策略[26], 选种过程包括k步 (k为目标个数) , 每一步根据预定目标选择概率随机选择一个目标, 以此目标从当前种群中选出一部分予以删除, 经过k步有选择的删除以后, 当前种群中剩下的个体即为下一代亲本。虽然Kursawe方法与VEGA算法和Fourman方法 (随机目标选择) 有许多相似之处, 但由于目标选择的随机性, 每代中不同的目标选择方案会产生不同的适应值图景, 因此Kursawe方法会产生不稳定的动态演化环境, 降低了算法的收敛性。最后, Hajela与Lin提出了加权指数与向量解混合编码的改进型加权和方法[21], 并采用共享函数提高种群多样度, 使得具有不同加权指数的向量解可以在一个种群中并发地得到优化。

《4.3多目标遗传算法 (MOGA) 》

4.3多目标遗传算法 (MOGA)

Fonseca与Fleming提出的多目标遗传算法 (MOGA) [5]是基于Pareto最优概念的演化算法, 包括:按目标的优先顺序与期望目标值进行向量解的优劣比较, 基于排序的适应值赋值策略, 共享函数与小生境技术, 杂交约束技术。MOGA算法中先给出了基于期望目标值及其优先顺序的优先性定义, 向量目标等价性定义以及优先性与优劣性之间关系。如果完全缺乏各目标之间的优先关系信息, 算法将不可能在各目标之间做折中处理。通过以期望目标向量形式给出目标之间部分优先关系信息, MOGA算法基于Pareto最优概念对给定折中区域进行搜索。假定各目标的优先顺序与期望目标值已给定, 两目标向量的优劣性比较从优先级最高的子目标向量开始, 每一级子目标向量的优劣性比较是从目标未满足的子目标元素部分开始。除最后一级子目标向量中的各目标分量要全部参与比较外, 其余子目标向量仅须对目标未满足的子目标元素进行比较, 而期望目标已满足的目标则不影响向量之间的优劣性。如果给定一个不可实现的期望目标向量, 则所有目标元素都必须参与比较, 此时, 向量比较退化至原始的Pareto排序。算法运行过程中不断改变期望目标值可相应改变适应值图景, 决策者即可将种群引导并集中至某一特定折中区域。种群中每一个向量解的排序是由当前种群中 (基于Pareto最优概念) 优于该解的其他解的个数来决定, 因此, 种群个体排序是不连续的, 而当前种群中所有非劣最优解都置为同一排序1 (或0 ) 。向量解的排序除以种群规模得到该向量的标准化序数, 如果种群规模足够大, 该标准化序数反映了解空间中优于相应向量解的空间比例。适应值赋值策略是根据排序先后按线性或非线性插值方法给不同的排序个体赋以不同的适应值, 具有同一排序号的向量解共享适应值。为了实现种群个体对多目标问题非劣最优域的均匀采样, 算法采用共享函数与小生境技术来提高种群多样度。通过非劣最优域PFtrue的大小与种群规模来确定共享半径或小生境的大小σshare, 目标向量之间距离小于σshare的解向量集合 (即小生境) 将共享适应值。此外, 由于多目标问题非劣最优域的复杂性, 距离较远的向量解之间的杂交后代, 其适应值往往低于亲本。而且, 随机杂交过程一般导致种群多样度降低。因此, 算法采用杂交约束方式, 即只有目标空间距离小于杂交半径σmate的亲本才允许杂交。如果在杂交半径内找不到杂交对象, 则随机任取种群中其他亲本进行杂交。σmate的确定方法如同σshare。 MOGA算法的选择过程借用Baker的随机均匀采样算法 (SUS) [32]。MOGA算法的主要优点是算法的执行相对容易且效率高, 缺点是算法易受小生境大小的影响, 但Fonseca 与Fleming已经从理论上解决了小生境大小σshare的计算问题。

《4.4非劣性分层遗传算法 (NSGA) 》

4.4非劣性分层遗传算法 (NSGA)

非劣性分层遗传算法 (NSGA) [6], 基于非劣最优性定义对多目标解种群进行逐层分类, 每代选种配对之前先按个体的非劣性进行排序。首先, 找出当代种群中的非劣最优解并分配最高序号 (如零级) , 赋给该层非劣最优解集与当前种群规模成比例的总体适应值。为了保持解的多样性, 所有该层非劣最优解基于决策向量空间距离共享此总体适应值。此后, 该层非劣最优解集将不予考虑。然后, 开始下一层非劣最优解集搜索, 在该层得到的非劣最优解集称为第二层, 分配排列序号 (如一级) , 并赋给与该层种群规模 (除去以上各层被分解出来的非劣最优解) 成比例的总体适应值, 同样, 必须在各层非劣最优解集中实行适应值共享。如此重复直到当前种群中最后一个被分解完。杂交配对个体采用适应值比例选择。因为最高层非劣最优解集具有最大的总体适应值, 因此, 该算法易于使整个种群收敛并均匀分布到多目标问题的非劣最优域。算法性能取决于如何利用非劣最优性定义进行逐层排序, 并把多目标问题转化为各层总体适应值的函数赋值方式。

NSGA算法的种群排序不同于MOGA算法, 前者排序序号是连续的, 后者可以是断续的;NSGA算法的适应值赋值方式不同于MOGA算法, 前者与非劣最优解的比较范围有关, 后者仅与序号有关;NSGA算法的适应值共享方式也不同于MOGA算法, 前者是基于决策向量空间距离共享适应值, 后者是基于目标向量空间距离共享适应值。NSGA算法的优点是优化目标个数任选, 非劣最优解分布均匀, 允许存在多个不同的等价解;缺点是算法效率 (包括计算复杂度与最终解Pknown的优度) 较低, 且对共享参数σshare的依赖性较大。

《4.5小组决胜遗传算法 (NPGA) 》

4.5小组决胜遗传算法 (NPGA)

小组决胜遗传算法 (NPGA) [7]采用基于非劣最优性定义的锦标赛选择机制。与直接比较两个个体不同的是, 算法还从种群中随机选取一定数量 (一般为10个) 的其他个体组成参赛组tdom, 参与非劣最优解的竞选。如果参与竞赛的两个个体中的一个劣于参赛组tdom中的所有个体, 而另一个体至少优于参赛组tdom中的一个个体, 则后一个体在竞赛中得胜。如果两个竟赛的个体都优于或劣于参赛组tdom中的所有个体, 即认为此次竞赛成为平局, 而其输赢由彼此的共享值来决定。在每一个体的目标空间邻域σshare内, 共享个体数较少的竞赛个体取胜, 即获得繁殖后代的机会。因为该算法的非劣最优解选择是基于种群的部分而非全体, 因此其优点是能很快找到一些好的非劣最优解域, 并能维持一个较长的种群更新期, 缺点是除了设置共享参数外还需要选择一个适当的锦标赛规模, 限制了该算法的实际应用效果。

对多目标演化算法的系统比较研究还不足以说明上述算法的优劣。Zitzler与Thiele等[33]对上述三种算法 (NSGA, NPGA, VEGA) 与Hajela和Lin的加权向量算法以及纯随机搜索算法, 作了系统的定量实验比较, 采用多背包问题扩展形式的九种不同规模设置作为数值型多目标测试问题, 通过全面的比较分析, NSGA算法的性能最优, 其次是VEGA算法。但NPGA算法与Hajela和Lin的加权向量算法的全部实验结果仍不分上下。由于测试问题的单一性, 这种比较结果不能无限制地外推。NFL理论[34]认为, 不可能存在一种对所有问题的求解效率都高于其他算法的超级算法, 因此, 任何算法的优点总是针对特有的问题。在多目标问题求解的三大类技术中, 先验优先权技术虽然最简单, 但先验优先权知识很难获取, 而缺乏优先权知识的多目标搜索无异于瞎子摸象, 其求解能力最弱;即使各目标的优先权值能精确定义, 此类算法也具有其固有的弱点, 即其非劣最优解搜索空间受限。然而, 先验优先权技术所表现出来的明显弱点并不意味着优先权演化技术与后验优先权技术就是我们的最佳选择。从已发表的相关文献而言, 以算法理论的完备性作为选择多目标演化算法的基本准则是明智的。因此, 本节3种基于Pareto最优概念的演化算法是值得推广的。

《5 多目标演化算法研究中的相关问题》

5 多目标演化算法研究中的相关问题

《5.1多目标问题非劣最优域的性质》

5.1多目标问题非劣最优域的性质

无论问题规模 (维数) 的大小, 任何非劣最优解域PFtrue都应有理论上的极限。例如, PFtrue一定是单调的, 并且PFtrue应该具有渐近边界[6,35]。最近, David 与Gary证明了以下定理:具有二个目标的多目标优化/决策问题 (k=2) 的非劣最优解域PFtrue至多只是一根曲线, 而具有三个目标以上的多目标优化问题 (k≥3) 的非劣最优解域PFtrue至多只是一个曲面[36], 而不是如Horn所说的一定是一个 (k-1) 维曲面[7]。

《5.2测试函数设计》

5.2测试函数设计

为了提高算法研究与比较的效率, 必须设计一些能反映实际多目标优化问题基本特征的标准测试函数集, 它包含多目标问题领域的基本知识。Whitley等曾提出多目标优化/决策问题的测试函数设计准则[9]:a.测试问题必须是简单搜索策略所不易解决的;b.测试函数中应包括非线性耦合以及非对称问题;c.测试问题中应包括问题规模可伸缩的问题;d.一些测试问题的评估代价应具有可伸缩性;e.测试问题应有规范的表达形式。

演化计算曾经使用过不同的测试函数, 如五个单目标优化函数 (F1～F5) [37], 五个单目标约束优化测试函数 (G1～G5) [38], Whitley[9]与Goldberg[39]也设计了一些有关的测试函数以及GA 欺骗问题。此外, 组合优化中的测试问题有旅行商 (TSP) 问题与背包 (Knapsack) 问题等。这些函数为研究演化计算提供了有应用背景价值且问题规模可伸缩的基准测试问题。文献[4]列出了比较详尽的多目标优化问题测试函数表, 并最终归纳成三类数值测试问题, 即MOP1[3,36], MOP2, MOP3。Rudolph给出了MOP1非劣最优解集的完整表示[40]。MOP2 [41] 多目标数值优化问题不会因增加决策变量的个数而改变其PFtrue结构, 而且其非劣最优解集Ptrue具有完整的表示形式。MOP3是三目标数值优化问题[22], 其PFtrue是目标空间中相当复杂的三维曲线。此测试问题具有非线性与不对称特性, 可用来测试多目标优化算法发现并保持整个PFtrue的能力。此外, 多目标演化算法的测试函数集中还必须包括等式或/和不等式的约束条件。

《5.3算法性能的评估技术》

5.3算法性能的评估技术

对各种多目标演化算法的性能比较研究必须建立在某种度量标准上。已有的性能比较方法有绝对评估方法[36]、统计分布方法[6]与非劣最优区域占有率方法等[42]。 对于任何一个多目标优化问题, 都不易得到类似MOP1完整的非劣最优解的集合表达形式, 因此, 很难对MOEA的有效性作绝对评估。对于比较简单的多目标数值优化问题, 可以在一定精度内对决策变量进行离散化处理, 转化为一个有穷离散空间的多目标优化问题, 通过穷尽枚举法计算所有可能的决策变量组合, 得到问题的近似Ptrue和PFtrue, 作为对MOEA进行绝对评估的依据。统计分布方法以已知的PFknown在PFtrue中统计分布的均匀性来评估算法对Pareto最优解的搜索能力, 区域占有率方法采用PFknown在PFtrue中所占的区域比例来反映算法的搜索广度, 或以一种算法与另一种算法所得到的PFknown之间的交集来反映其相对性能。

《5.4算法收敛性分析》

5.4算法收敛性分析

对一般多目标优化问题收敛行为的理论分析有助于改进现有算法的收敛性。Rudolph[40]对由两个目标组成的简单多目标优化问题的演化算法的收敛行为进行了分析, 以集合之间的距离定义解的收敛性, 说明具有比例步长均匀变异算子的 (1+1) -EA (演化策略) 能以概率1收敛到问题的非劣最优域。但是, Rudolph的分析过程比较复杂, 而且中间过程不太清晰, 似有疑问, 且这种收敛性向一般多目标问题的推广上具有局限性。理论上, 多目标优化问题的演化算法缺乏与单目标优化问题演化算法相类似的收敛性理论, 因此, 目前还未出现描述多目标问题演化算法中代与代之间的动态行为的理论分析结果。

《5.5并行实现与终止条件》

5.5并行实现与终止条件

多目标优化演化算法中的并行实现方式也是值得研究的问题。向量目标评估与相应解的适应值赋值是算法并行性开发中可以首先考虑的两个任务。因为各目标函数可以彼此独立地并行计算, 因此, 开发各目标计算的并行性可以大大提高算法的并行效率。种群中个体的Pareto排序、共享函数与小生境规模计算可以独立执行, 将此两项任务并行实现可提高算法效率。此外, 种群初始化、杂交与变异、选择等必须顺序执行的任务可集中在主机上执行, 同时主机可控制向量目标评估与适应值赋值并行执行。

多目标演化算法终止条件的确定也是一个值得研究的问题。现有的终止条件是, 或采用固定的种群代数, 或每隔一定代数对所得Pknown所对应的PFknown的几何图形进行分析, 以确定算法是否已取得足够完整且均匀的非劣最优解集, 但这些方法仅适应三个目标以下的优化问题。

《5.6实际多目标问题处理》

5.6实际多目标问题处理

多目标优化与约束条件满足是同一问题的两个方面, 都是对一组函数进行优化, 因此二者可相互转化。多目标优化过程中约束不等式的满足问题可转化为最小化相应约束函数直至约束条件满足, 相反, 如果仅把多目标优化问题中的一个目标看成优化对象, 而其余目标均视为约束条件, 则多目标优化问题也可以转化为带约束条件的单目标优化问题。多目标优化技术可以通过对所有设计目标同时进行优化, 来寻找各种满足设计目标与约束条件的设计方案。设计过程中的主观因素来源于设计者已有设计知识与对问题领域认识的局限性, 设计专家对各设计目标的偏重程度往往只能定性地说明, 这些对各设计目标的定性偏重程度可用于对种群的排序, 如果设计目标过多, 也可用来计算其相应的加权值[43]。另外, 设计过程中的主观因素也表现在设计者对设计变量与各设计目标之间的某些约束关系上。如果把这些设计者的主观设计自由度作为决策者 (DM) 加入多目标优化的演化设计算法中, 就构成了具有反馈的工程演化设计系统。对各设计约束项的满足程度将对设计方案适应值作相应修改, 只要设计适当的人机交互界面, 设计专家的设计知识与思想就能与演化算法的强大搜索功能有机结合, 大大提高设计效率, 并降低设计风险!

《5.7算法的逆向应用》

5.7算法的逆向应用

从直接与间接多目标加权和的优化方法联想到, 把一个复杂目标函数的优化转化成一个多目标的优化问题, 也就是把一个高维复杂函数分解成一些比较简单的函数之间的协同优化, 以子函数的协同演化提供原目标函数的种群多样度, 预防过早收敛。因为解群的收敛方向是由适应值函数的拓扑结构或图景所决定的演化压力所驱动, 将复杂的适应值图景拆成比较简单的图景, 也许是提高种群多样度防止过早收敛的一种有效措施, 同时也是提高演化算法控制参数与初始种群设置的鲁棒性的一种有效措施[44,45]。

《6 结语》

6 结语

按适应值赋值方式, 多目标演化算法可分为基于Pareto最优概念与不基于Pareto最优概念的两大类算法。多性别遗传算法与向量评估算法本质上仍然是加权和方法, 只有建立在Pareto最优概念上进行个体排序的多目标遗传算法、非劣性分层遗传算法以及小组决胜遗传算法, 才有可能搜索到多目标优化问题的非劣最优解集。

多目标优化与决策的演化算法有待更深更广的研究工作。多目标演化算法的性能比较必须建立在测试函数的基础上, 并采用统一的性能度量标准进行定量比较, 严密的算法比较还有待研究。对基于Pareto最优概念的多目标演化算法的动态行为理论分析尤其是收敛性分析亦有待探索。