7.1.2　多目标优化问题

在实际的工程或者研究中,遇到的决策类问题往往不只包含一个目标,而是由多个或一组相互冲突的目标所组成的,具有多个目标的特点和性质,使这些目标在指定维度的空间内同时达到最优的问题为多目标优化问题。但是在实际情况下,其中一个解往往只能使多个目标中的一个达到较好的结果,对于其他的目标无法得出较好的结果,即无法使所有子目标同时达到最优。在解决多目标优化问题时一般采用折中处理的方法,使各子目标达到平衡,所以目标优化问题的解在一般情况下并不是唯一的,这种性质是多目标优化问题和单目标优化问题两者之间最本质的区别。而通过折中方法得到的解的集合称为Pareto最优解集,解集中的元素称为Pareto最优解[2]。

1.多目标优化问题的数学建模

多目标优化问题一般情况下是由以下内容组成的:目标函数、决策变量以及约束条件。其数学模型如式(7-1)所示。

其中,y为n个目标函数,f i(x)代表第i个目标函数,g i(x)≤0代表不等式约束条件,hj(x)=0表示等式约束条件,X为p维的决策向量,x dmin表示向量空间的下界,x dmax表示向量空间的上界[3]。

2.多目标优化问题的基本概念

定义7-1(可行解) 对于∀x∈X,若x满足式(7-1)中的约束条件g i(x)≤0(i=1,2,…,k)和h j(x)=0(j=1,2,…,l),称x为可行解。

定义7-2(可行解集) 可行解构成的集合称为可行解集,如式(7-2)所示。

X f在向量空间中对应的可行解表示为式(7-3)。

定义7-3(支配关系) 设u和v是R n中任意两个不同的向量,如果满足以下两个条件,则称u支配v:

①∀i∈{1,2,…,n},都满足u i≥v i;②∃i∈{1,2,…,n},使得u i≥v i。

在这种情况下,称u为非支配解,v为支配解,记作u≺v。

定义7-4(Pareto占优) 设x A,x B∈X f是式(7-1)中的两个解,对两者进行比较,若x A是Pareto占优,则需要满足式(7-4)所表示的条件。

定义7-5(Pareto最优解) Pareto最优解的条件如式(7-5)所示。

满足上述条件的解x*∈X f称为最优解。

定义7-6(Pareto最优解集) 满足多目标优化问题的解集中所有Pareto最优解的集合称为Pareto最优解集,其定义如式(7-6)所示。

定义7-7(Pareto前沿面) 由Pareto最优解集P*中所有Pareto最优解所对应的目标向量在目标空间内构成的曲面称为Pareto前沿面,记作:

3.多目标Pareto最优解集

在求解多目标优化算法的研究中,多目标进化算法逐渐为研究学者们所重视,其中最常见的方法是通过构造进化群体的非支配解集并在算法执行过程中不断进行补充,随着迭代过程逐渐接近真正的最优边界。因此,该方法相当于将构建多目标优化问题的最优解集转化为求解进化群体的非支配解集。影响这类进化算法效率的主要因素是构造非支配解集的过程,因为每一次迭代即进化过程都需要构建一次非支配集。高效的构建过程会对算法整体效率的提升起至关重要的作用。常用的构造非支配集的方法主要有庄家法、擂台赛法、递归法和快速排序法。这些方法都有自己的长处和不足,但都是常见的效率较高的方法,这里主要介绍一下庄家法和擂台赛法。

(1)庄家法构造Pareto最优解集

步骤1:初始集合为P,设构造集为Q,初始时Q=P,P的非支配解集为NDSet,算法开始时NDSet=∅。

步骤2:从Q中随机取出一个解x,使得Q=Q-{x},初始化偏序集D=∅。

步骤3:令D=D∪{y|x≻y,∀y∈Q}。

步骤4:令Q=Q-D,若∃/z∈Q,使得z≻x,则令NDSet=NDSet∪{x}。

步骤5:当Q≠∅时,跳到步骤2,否则输出NDSet。

(2)擂台赛法构造Pareto最优解集(https://www.daowen.com)

步骤1:初始集合为P,目标个数为r,设构造集为Q,初始时Q=P,P的非支配解集为NDSet,算法开始时NDSet=∅,从Q中随意选择一个个体x,并使用x作为比较对象。

步骤2:令Q=Q-x,PK=∅,R=∅。

步骤3:当Q≠∅时,跳到步骤4,否则跳到步骤5。

步骤4:从Q中按顺序取出个体,设为y,并将y与x进行比较,共有如下3种情况。

·如果x≻y,则令Q=Q-y,跳到步骤3。

·如果y≻x,则令x=y,Q=Q-y,PK=PK∪R,R=∅,跳到步骤3。

·如果x和y无关,则令R=R∪{y},Q=Q-y,跳到步骤3。

步骤5:令PK′=y∈PK|not(x≻y)

{

},NDSet=NDSet∪{x}。

步骤6:令Q=PK′∪R,如果|Q|＞1,则跳到步骤1,否则令NDSet∪Q,输出NDSet。

4.多目标群体分布性

多目标进化算法中一个重要的内容是解群体的多样性。当在进化的过程中由于进化算子的影响,收敛陷入单个解时,往往得到的解集会聚集到一个小的范围之内,无法得到最优的解集,因此如何保持进化群体的多样性是得到一个好的解集的关键问题。保持多目标进化群体分布性的方法主要有小生境技术、信息熵技术、聚集密度方法、网格和聚类方法[4],本书主要介绍前两种方法。

(1)小生境技术

小生境技术的核心是3种机制:预选择机制、排挤机制和共享机制。其实现思想是在群体周围设置一个共享半径,称为小生存半径,计算在小生存半径内群体个体的相似程度。

设个体i的适应度是fitness(i),mi为个体i的小生存计数,如式(7-8)所示。