多目标群体智能算法-相关概念与定理

2023-11-26 理论教育版权反馈

【摘要】：根据优化的对偶理论，只需考虑最小化问题。不失一般性，一个具有n个决策变量，m个目标函数，(p＋q)个约束的MOP问题可定义为:其中，x＝(x1，x2，…定义2假设x1，x2∈Xf是上述MOP问题的可行解，称x1 Pareto支配x2当且仅当i＝1，2，…，m)成立且至少有一个是严格不等式，则称x是(7.6)式的Pareto最优解。，Tmax，Tmax为MOEA算法最大进化代数，｜·｜为集合的基数。同理，对于y2，y3∈Pop，使得y3y2，即有y3y2y1成立。

根据优化的对偶理论，只需考虑最小化问题。不失一般性，一个具有n个决策变量，m个目标函数，(p＋q)个约束的MOP问题可定义为:

其中，x＝(x1，x2，…，xn)T∈X⊂Rn是n维决策向量，X为n维决策空间；y＝(y1，y2，…，ym)∈Y⊂Rm为m维目标空间；目标函数F(x)定义了由决策空间X向目标空间Y映射的函数，g(x)定义了p个不等式约束，h(x)定义了q个等式约束。约束函数g(x)和h(x)共同确定决策向量x的可行域。在此基础上给出几个重要的定义。

定义1(可行解集)可行解集Xf为满足式(7.6)中约束函数g(x)和h(x)的决策向量x的集合，即Xf＝{x∈X｜g(x)≥0且h(x)＝0}。

定义2(Pareto支配)假设x1，x2∈Xf是上述MOP问题的可行解，称x1 Pareto支配x2(记为x1≺x2)当且仅当∀i＝1，2，…，m:fi(x1)≤fi(x2)∧∃j＝1，2，…，m:fj(x1)<fj(x2)成立。

定义3(Pareto最优解)假设x∗∈Xf且不存在其他的解使得(i＝1，2，…，m)成立且至少有一个是严格不等式，则称x∗是(7.6)式的Pareto最优解。

定义4(Pareto最优解集)Pareto最优解集(Pareto Set，PS)是所有Pareto最优解的集合，即PS＝{x∗}＝{x∈Xf｜¬∃x′∈Xf:fi(x′)≤fi(x∗)，i＝1，2，…，m}。(www.chuimin.cn)

定义5(Pareto前沿)Pareto前沿(Pareto Front，PF)是Pareto最优解集在目标空间中的投影，即PF＝{F(x)｜x∈PS}。

定义6(当前种群的非劣解集NDS)假设Pop(t)为MOEA算法的第t代种群，个体x∗∈Pop(t)为群体的非劣解，当且仅当¬∃x′∈Pop(t):x′≺x∗。Pop(t)中所有非劣解x∗组成的集合称为当前群体Pop(t)的非劣解集NDS，即NDS＝{x∗}＝{x｜x∈Pop(t)且¬∃x′∈Pop(t)，使x′≺x}。

定义7(极端解和极端解集)对于非劣解集NDS，若个体x∈NDS且在NDS中的某一目标上不存在比x还小的解，则称x为NDS中的极端解，NDS中所有极端解个体组成的集合称为NDS的极端解集NDES(Non-dominated Extreme Set，NDES)，即NDES＝{x｜x∈NDS，∃k∈{1，2，…，m}且¬∃x′∈NDS，使fk(x，)<fk(x)}。

定理1　MOEA算法任一代种群Pop(t)的当前非劣解集NDS(t)的规模至少为1，即｜NDS(t)｜≥1。这里的t＝1，2，…，Tmax，Tmax为MOEA算法最大进化代数，｜·｜为集合的基数。

证明:(反正法)记种群的规模为N，假设｜NDS(t)｜＝0，则∀y1∈Pop，∃y2∈Pop，使得y2≺y1。同理，对于y2，∃y3∈Pop，使得y3≺y2，即有y3≺y2≺y1成立。重复这一过程可得y1，y2，y3，…，yN，yN＋1∈Pop且yN＋1≺yN≺yN-1≺…≺yn≺yn-1≺…≺ym≺ym-1≺…≺y3≺y2≺y1成立。由于种群的规模为N，而支配序列中有(N＋1)个个体，因此支配序列中一定存在重复的个体，不妨设重复的个体为yn和ym，则有yn＝ym(n>m)，而支配序列中有yn≺ym，导出矛盾，故假设不成立。

多目标群体智能算法-相关概念与定理

相关推荐