基于最大熵进化算法的高维多目标优化

周雪松

doi:10.3969/j.issn.1673-3819.2025.05.009

指挥控制与仿真 >

2025 , Vol. 47 >Issue 5: 64 - 71

DOI: https://doi.org/10.3969/j.issn.1673-3819.2025.05.009

信息融合

基于最大熵进化算法的高维多目标优化

周雪松

展开

中船智能科技(上海)有限公司, 上海 201210

周雪松(1985—),男,硕士,高级工程师,研究方向为系统工程。

收稿日期: 2025-01-03

修回日期: 2025-01-16

网络出版日期: 2025-09-25

收起

Many-objective optimization based on maximum entropy evolutionary algorithm

ZHOU Xuesong

Expand

CSSC Intelligent Technology Shanghai CO., LTD, Shanghai 201210, China

Received date: 2025-01-03

Revised date: 2025-01-16

Online published: 2025-09-25

Fold

摘要

随着数据量、维度和优化目标数量的增加,目标之间的冲突也随之加剧,使得多目标优化问题的求解变得愈加复杂。尤其是高维异构的多目标优化问题,解决难度显著增加。因此,提出了一种基于最大熵的参考向量引导进化算法,旨在解决高维多目标优化问题。通过结合参考点策略与进化算法搜索机制,本方法实现了理想参考点和最差参考点的互补协同,从而提高了优化效率。该算法依赖一组自适应选择的参考向量,并通过贝叶斯最大熵进行优化,重点关注优化过程中的多样性与收敛性平衡。通过在一些基准问题上的对比实验可知,提出的K-RVEA算法表现出显著的优势,验证了该方法的可行性与有效性。

关键词： 多目标优化; 最大熵; 多样性; 收敛性

本文引用格式

周雪松 . 基于最大熵进化算法的高维多目标优化[J]. 指挥控制与仿真, 2025 , 47(5) : 64 -71 . DOI: 10.3969/j.issn.1673-3819.2025.05.009

Abstract

With the increase in data volume, dimensionality, and the number of optimization objectives, the conflicts between objectives intensify, making the solution of multi-objective optimization problems increasingly complex. This is especially true for high-dimensional heterogeneous multi-objective optimization problems, where the difficulty of solving them increases significantly. In this paper, we propose a maximum entropy-based reference vector-guided evolutionary algorithm aimed at solving many-objective optimization problems. By combining reference point strategies with evolutionary algorithm search mechanisms, the proposed method achieves complementary cooperation between the ideal and worst reference points, thereby improving the efficiency of optimization. The algorithm relies on a set of adaptively selected reference vectors and optimizes them using Bayesian maximum entropy, focusing on balancing diversity and convergence during the optimization process. Through comparative experiments on several benchmark problems, the proposed K-RVEA algorithm demonstrates significant advantages, verifying the feasibility and effectiveness of the method.

Key words： many-objective optimization; maximum entropy; diversity; convergence

在经济和工业领域,许多高维、异构的多目标优化问题日益凸显。这些问题通常表现为多个优化目标之间的冲突,即改善一个目标可能会导致其他目标的恶化,因此,需要在多个目标之间找到一种平衡。这类问题被称为“高维多目标优化问题”(many-objective optimization problems, MaOPs)。与传统的多目标优化问题相比,高维多目标优化问题一般涉及4个以上的目标函数。本文考虑以下形式的多目标优化问题:

(1)minimize{f₁(x),…,f_k(x)}subject to x∈S

其中,k大于2,目标函数值的向量表示为f(x)=(f₁(x),…,f_k(x))^T(非空)。可行空间S是决策空间R²的一个子集,并由决策向量x=(x₁,…,x_n)^T组成,此决策向量满足所有的约束条件。目标空间R²中的可行区域S称为用Z表示的可行目标集。Z的元素被称为可行目标向量,用z=(z₁,…,z_k)^T表示,其中,z_i=f_i(x)为目标函数值。由于这些目标是相互冲突的,通常不存在单一的最优解,而是存在多个帕累托最优解。在目标空间中,所有最优解的集合被称为帕累托前沿,在决策空间中被称为帕累托集。

现有研究提出了两大类优化算法:多准则决策(MCDM)^[1]和进化多目标优化(EMO)^[2]。MCDM方法通常通过两种方式求解:一是将多目标优化问题转化为单目标优化,找到代表性的帕累托最优解;二是根据决策者偏好选择最优解,决策者通常在获取一组帕累托最优解后进行选择。EMO方法主要处理大量候选解,目标是找到一组能够代表整个帕累托前沿的解^[3]。

进化算法(EAs)模拟自然界的进化过程,能够处理不同类型的决策变量,并且不依赖目标函数的凸性、可微性或约束条件^[4]。尽管EAs具备处理复杂问题的优势,但其收敛速度较慢,且通常需要大量的函数评估,尤其在计算代价高的领域,如气动优化中的CFD模拟时,评估代价巨大^[5]。传统的多目标进化算法(MOEAs)在面对许多目标优化问题(MaOPs)时,往往因为缺乏足够的收敛压力而失效。例如,依赖支配选择的算法,如NSGA-II和SPEA2,在大多数解是非支配解时,无法有效区分解空间中的解^[6]。此外,MOEAs在高维多目标空间中很难维持良好的种群多样性,因为大多数连续多目标问题的帕累托前沿是分段连续的,难以近似所有的帕累托最优解^[7]。

为了增强帕累托前沿的收敛压力,已有文献提出了3类方法:第1类通过修改支配规则(如ε支配和L最优方法)提升收敛压力,或者结合其他规则如替代距离来优化NSGA-II的性能^[8-10]。第2类为分解方法,通过将复杂的多目标问题分解为多个子问题后协同求解,其适用于目标较多的情况,尤其是在NSGA-III中将帕累托前沿划分为子域^[11]。第3类方法则不依赖支配解,而是基于性能指标进行优化,常见如基于指标的多目标进化算法和基于超体的进化算法^[12]。这三类方法在增强收敛压力上各有优势:第1类方法适合低维度情况,但可能丧失多样性;第2类方法在目标较多时效果较好,但计算开销较大,且子问题的划分影响优化效果;第3类方法避免了传统支配的局限,适用于复杂问题,但受限于性能指标的选择。

因此,本文提出了结合分解和基于指标的思想来解决多目标优化问题,即将多目标优化问题转化为多个单目标优化问题,分别求解并组合成理想解。随后,采用贝叶斯最大信息熵生成参考解,衡量每个解与理想解和最差解的距离,将其作为适应度函数,平衡种群的多样性与收敛性。

1 背景

1.1 参考向量进化算法(RVEA)

解决高维多目标优化问题的两个主要挑战是有效收敛到帕累托前沿以及在解集之间保持良好的多样性。为应对这些挑战,已有多种进化算法被提出。例如,某些方法通过使用修正的优势关系将许多目标优化问题分解为多个单目标优化问题,然后采用了基于指标的目标函数,或者使用参考点策略。有关这些算法及其在解决超过3个目标优化问题中的应用和挑战的更多细节,见文献[13]。

参考向量进化算法(RVEA)是一种专为高维多目标优化设计的算法。与MOEA/D^[14]和NSGA-III使用权重或参考点不同,RVEA采用参考向量,并基于角度惩罚距离(APD)来平衡收敛性和多样性。研究表明,APD在目标数目增加时,更有效地保持了两者之间的平衡。RVEA通过参考向量将目标空间划分为多个子空间,并在每个子空间独立选择个体^[15-16]。其主要特点体现在选择策略和参考向量自适应调整上。 RVEA的4个组成部分如下:

(1)参考向量生成:如图1所示,通过单纯格设计在单位超平面上均匀分布生成参考点,并将其投影到超球面上,得到参考向量。这样,目标空间被划分为多个子空间。

显示原图|下载原图ZIP|生成PPT

图1 一个双目标优化问题的参考向量的说明性例子

Fig.1 An illustrative example of a reference vector for a biobjective optimization problem

(2)个体分配给参考向量:根据目标值与参考向量之间的夹角,个体被分配给对应的参考向量。通过计算个体与参考向量的锐角,将个体分配到角度最小的参考向量。

(3)亚种群个体选择:从每个亚种群中选择个体,选择标准为个体收敛性(目标距离)和多样性(与参考向量的角度)。通过APD控制搜索过程中的收敛性与多样性。

(4)参考向量自适应:为了应对目标函数范围不同的问题,参考向量根据目标空间中个体的位置动态调整。自适应参考向量保证了即使在范围不同的优化问题中,也能获得均匀分布的非支配个体。

1.2 贝叶斯最大信息熵思想

贝叶斯最大信息熵方法是一种基于S/TRF的空间或时空数据分析与预测方法。与传统空间分析方法相比,该方法的主要特点是能将硬数据、软数据及其他相关信息系统地整合进估计与分析过程中^[17-18]。本文基于这一方法,探讨其在空间随机场(spatial random field, SRF)中的应用机制,具体而言,该方法将自然过程抽象为空间尺度上不同点位随机变量组合的场。为方便表示,用Z(p)代表SRF(即某自然过程),其中,p=(S_m)表示空间位置,其包含了M维空间位置信息S_m。随机场Z(p)由一系列独立随机变量r(p)组合而成,其一次实现可以通过采样或模拟得到。具体来说,空间随机场SRF有具有m个空间点位p=[p₁,…,p_m]的随机变量r(p)=[r₁,…,r_m]经采样或模拟得到Z(p)=[Z₁,…,Z_m]。

该方法中,通用知识库包含与随机变量r(p)相关的统计特征,如平均值、期望值、协方差等。在预测随机变量的概率分布时,通过最大熵原理选择熵最大的分布作为先验概率密度函数(pdf),如公式(2)所示:

(2)f_G=

A 1 - 1

exp[

∑ a = 1 N C

u_ag_a(Z_all)]

其中,

A 1 - 1

为配分函数,用来将f_G(all)归一化;硬数据、软数据和预测点的关系通过知识库S组成。此方法通过拉格朗日乘子法在最大信息熵条件下计算先验概率密度函数,约束条件包括归一化约束、期望约束、方差约束等。信息熵H定义如下:

(3)H(f_G(Z_all))=-∫log[f_G(Z_all)]f_G(Z_all)dZ_all

软数据通常以区间型数据(interval data, ID)形式表现:

(4)Z_soft={[Z_h₊₁,…,Z_m]}^T;Z_i∈[l_i,u_i],i=(h+1),…,m

其中,l_i,u_i为区间的上下界。软数据的集成用于求取条件先验概率密度函数,其估计模型可表示为

(5)f_k(Z_K)=

A 2 - 1 ∫ l u

f_G(Z_all)dZ_soft

其中,

A 2 - 1 ∫ l u

f_G(Z_all)dZ_soft是归一化常量,f_G(Z_data)=∫f_G(Z_data)dZ_k是硬数据和软数据的联合先验概率密度函数,f_k(Z_K)为待求的先验概率密度函数,整合结果用后验概率的数学期望来表示:

(6)

Z - K

=∫Z_kf_k(Z_k)dZ_k

2 基于最大信息熵的多目标优化

2.1 确定整个种群空间的理想点

种群的理想点就是各个目标在解空间的最优值,假设所有目标都是最小形式,那么,种群的理想点可以根据以下公式获得:

(7)

Z -

Z 1 m i n

Z 2 m i n

,…,

Z o m i n

)

(8)

Z i m i n = s ∈ s t m i n

f_i(s)

其中,s_t为所有种群的集合,

Z i m i n

为第i个目标的函数最小值,

Z -

为整个种群空间的理想点。

在得到理想点

Z -

后,系统就可以对所有个体的目标函数值进行转化,转化时可以按下列公式进行:

(9)f_i'(s)=f_i(s)-

Z i m i n

, ∀ s∈s_t

通过极值点创建超平面,种群的极值点数目和优化目标的数目相同,其中,第d维的极值点就是在第d个目标函数上的取值很大,其他目标函数的取值很小。本文使用权重向量W得到极值点,当计算第d维的极值点时,需要将该方向的权重设定为1,其他方向的权重设定为10^-6,再使用ASF函数得到所有个体的ASF值,ASF值最小的个体即为该目标方向的极值点。其中ASF函数公式如下:

(10)ASF(X,W)=

m a x i ∈ [1, m]

f'_i(X)/w_i,∀x∈s_t

2.2 参考点设置

在随机选择的目标向量集合中,随着目标数量的增加,非支配解的比例呈指数级增大。在实现种群多样性时,采用如NSGA-II中的拥挤度或聚类算子等方法会带来较大的计算和存储开销(时间和空间复杂度)。此外,高维空间中的收敛性问题及前沿解集均匀分布的难度也使得优化过程变得更加复杂。参考点的引入旨在获取种群个体与参考点之间的映射关系(即垂直距离),从而引导种群向更接近参考点的方向演化,使参考点的分布更加均匀。在解空间中选择一定数量、均匀分布且能够覆盖整个目标空间的自适应调整参考点,相当于在解空间中打下了标记,指示后续的解搜索算法需要探索这些标记区域,以确保不会遗漏任何潜在的解空间区域。

下面是本文提出的K-RVEA算法整体流程。

基于最大信息熵的多目标优化算法
输入:最大代数t_max;参考向量数N;单位参考向量集V₀={v₀₁,…,v₀_n};
输出:种群Pt_max中的非支配解集
1:创建一个含有N个随机个体的初始种群p₀,并设置迭代计数器t=0
2:生成理想解向量I
3:while t<t_max do
4:生成子代种群Q_t
5:结合父代种群和子代种群,L_t=P_tUQ_t
6:选择下一代种群(P_t₊₁)
7:基于贝叶斯最大信息熵产生新参考向量(V_t₊₁)
8:end while

3 数值实验

本文以高维多目标优化问题中常用的DTLZ测试问题集为例,验证所提算法的有效性。为减少随机因素的干扰,采用反向世代距离(IGD)^[15]和超体积(HV)^[16]作为评价指标,分别衡量算法的收敛性和解集分布性。为了公平,本文将所提算法与4种基于不同策略的MOEA算法进行比较,包括ParEGO^[17]、SMS-EGO^[18]、MOEA/D-EGO^[19]和RVEA^[20]。这些算法代表了不同的优化思路,如代理模型引导的进化优化和参考向量引导的分解优化。

DTLZ问题中的决策变量数目及参数设置参照文献[21-22]。为确保公平,所有算法的种群大小设为100,外部档案规模为30,最大代数为200。所有算法采用二进制交叉(Pc=0.9)和二项式变异(Pm=0.1),以保证全局搜索能力并避免早期收敛。ParEGO、SMS-EGO和MOEA/D-EGO采用高斯过程回归(GPR)作为代理模型;RVEA则通过参考向量指导解的均匀分布。所有实验在Matlab R2019a中完成,运行环境为Intel Core i7 16.00 GHz CPU和16.0 GB RAM。每个算法在每个问题上独立运行30次,最终结果取平均值。

3.1 参数设置

在初始化阶段,使用原始目标函数进行评估的个体为训练档案中的最大个体数,NI=11n-1。独立运行的数量为10。最大函数计算数为300。更新模型的个体数量, |u|=5。参考向量的数量N由单纯格设计^[11]的因素和目标的数量决定,并在补充材料中列出。更新模型时,参数δ=0.05N,在更新模型之前的代数W_max=20。

RVEA使用50的种群规模,其他算法采用文献中推荐的相同参数。通过倒代距离(IGD)评估算法性能,并设置Wilcoxon秩和检验在0.05显著性水平下比较K-RVEA与其他4种算法,结果见表1、2和3。符号“↑”表示K-RVEA优于其他算法,符号“↓”表示其他算法优于K-RVEA,符号“≈”表示差异不显著。随着目标数量增加,问题变得更易求解,因此,实验中添加了WFG套件。

表1 由K-RVEA、RVEA 和ParEGO 获得的IGD 值的统计结果

Tab.1 Statistical results of IGD values obtained by K-RVEA, RVEA and ParEGO

问题	k	K-RVEA			RVEA				ParEGO
DTLZ1	3 4 6 8 10	min 82.03 48.23 8.031 0.699 0.198	mean 106.9 73.21 28.83 6.991 0.347	max 125.2 101.4 35.22 13.29 0.655	≈ ≈ ≈ ≈ ≈	min 42.65 39.65 12.24 1.250 0.193	mean 82.87 59.18 22.94 7.406 0.339	max 115.1 97.71 36.85 15.66 1.105	↓ ↓	min 13.42 18.63	mean 52.47 45.45	max 112.7 87.76
DTLZ2	3 4 6 8 10	0.092 0.191 0.316 0.360 0.419	0.155 0.276 0.342 0.395 0.446	0.262 0.376 0.362 0.522 0.470	↑ ↑ ↑ ↑ ↑	0.227 0.280 0.375 0.466 0.539	0.288 0.332 0.404 0.541 0.608	0.335 0.383 0.440 0.704 0.733	↑ ↑	0.151 0.289 — — —	0.191 0.337 — — —	0.243 0.408 — — —
DTLZ3	3 4 6 8 10	181.5 85.56 61.61 12.36 0.781	280.1 210.9 105.0 26.49 1.299	353.1 314.5 156.4 43.51 2.303	≈ ≈ ≈ ≈ ≈	133.7 89.95 43.54 8.569 0.761	256.1 198.6 95.97 25.27 1.228	347.9 306.3 157.7 42.17 1.836	↓ ↓	81.15 66.93 — — —	145.5 138.1 — — —	261.6 209.4 — — —
DTLZ4	3 4 6 8 10	0.190 0.268 0.422 0.547 0.553	0.448 0.458 0.585 0.635 0.608	0.737 0.648 0.754 0.728 0.672	≈ ≈ ≈ ≈ ↑	0.205 0.320 0.503 0.554 0.599	0.399 0.514 0.615 0.628 0.667	0.959 0.737 0.800 0.731 0.761	↑ ↑	0.387 0.505 — — —	0.646 0.725 — — —	0.947 0.960 — — —
DTLZ5	3 4 6 8 10	0.050 0.046 0.032 0.023 0.009	0.112 0.123 0.102 0.048 0.017	0.211 0.242 0.153 0.107 0.022	↑ ↑ ↑ ↑ ↑	0.201 0.149 0.159 0.104 0.224	0.247 0.294 0.280 0.260 0.488	0.316 0.393 0.431 0.748 0.746	↓ ↑	0.039 0.090 — — —	0.055 0.288 — — —	0.072 0.428 — — —
DTLZ6	3 4 6 8 10	2.121 1.306 1.133 0.377 0.054	2.727 2.446 1.597 0.660 0.153	3.343 3.060 2.174 1.049 0.373	↑ ↑ ↑ ↑ ↑	3.651 3.027 1.025 0.247 0.140	4.960 4.044 2.524 1.004 0.297	5.613 5.208 3.600 1.870 0.751	↑ ↑	5.030 5.652 — — —	6.378 5.916 — — —	6.867 6.034 — — —
DTLZ7	3 4 6 8 10	0.088 0.188 0.391 0.745 0.917	0.111 0.243 0.500 0.886 1.030	0.150 0.298 0.627 1.030 1.134	↑ ↑ ↑ ↑ ↑	0.400 0.532 0.889 1.162 1.343	0.515 0.691 1.088 1.359 1.900	0.637 0.926 1.808 1.634 3.327	↑ ↑	0.621 0.719 — — —	0.829 0.892 — — —	1.201 1.149 — — —

表2 通过K-RVEA、RVEA、ParEGO、SMS-EGO和MOEA/D-EGO对3个和4个目标获得的IGD值的统计结果,分别进行了120和115个功能评估

Tab.2 Statistical results of IGD values obtained by K-RVEA, RVEA, ParEGO, SMS-EGO and MOEA/D-EGO for 3 and 4 targets were used for 120 and 115 functional evaluations, respectively

问题	目标数	K-RVEA				RVEA				ParEGO				SMS-EGO				MOEA/D-EGO
DTLZ1		Min	Mean	Max		Min	Mean	Max		Min	Mean	Max	↑	Min	Mean	Max		Min	Mean	Max
	3	82.01	130.2	171.0	≈	66.20	128.8	171.4	≈	100.6	124.1	148.9	↑	85.48	114.3	148.9	↑	173.0	266.9	388.2
	4	61.91	90.29	115.6	≈	81.54	102.4	133.5	≈	75.21	99.82	128.6	↑	93.35	130.1	173.9		—	—	—
DTLZ2	3	0.306	0.360	0.408	↑	0.402	0.438	0.487	≈	0.272	0.356	0.397	↑	0.365	0.445	0.523	↑	0.325	0.385	0.456
	4	0.375	0.427	0.464	↑	0.423	0.465	0.511	≈	0.385	0.422	0.476	≈	0.447	0.489	0.533		—	—	—
DTLZ3	3	217.4	324.3	383.7	≈	237.6	366.8	494.2	≈	232.5	368.3	460.7	≈	220.8	325.3	459.2	≈	189.6	339.8	523.40
	4	173.9	302.1	370.2	≈	179.3	284.1	358.6	≈	172.6	291.8	357.1	≈	209.1	314.2	403.8		—	—	—
DTLZ4	3	0.453	0.710	0.977	≈	0.539	0.677	0.966	≈	0.588	0.768	0.911	≈	0.647	0.691	0.723	↓	0.395	0.435	0.479
	4	0.586	0.749	0.914	≈	0.671	0.802	0.927	≈	0.717	0.818	0.993	↑	0.681	0.746	0.816		—	—	—
DTLZ5	3	0.174	0.281	0.361	≈	0.273	0.327	0.396	↑	0.598	0.614	0.638	↑	0.447	0.498	0.547	↓	0.170	0.215	0.309
	4	0.227	0.255	0.302	↑	0.249	0.289	0.315	↑	0.443	0.456	0.485	↓	0.361	0.413	0.466		—	—	—
DTLZ6	3	3.111	3.972	4.630	↑	5.739	6.111	6.464	↑	6.506	6.709	6.826	↑	1.602	1.756	2.008	↑	4.075	5.079	6.625
	4	2.956	3.911	4.588	↑	4.407	5.038	5.630	↑	5.722	5.869	6.026	↓	5.843	5.884	6.011		—	—	—
DTLZ7	3	0.121	0.166	0.218	↑	0.634	0.761	1.271	↑	3.137	5.575	7.418	↓	0.241	0.261	0.277	↑	0.618	1.750	3.840
	4	0.295	0.400	0.649	↑	0.779	1.019	1.219	↑	5.306	7.377	8.922	↑	0.578	0.645	0.706		—	—	—

表3 通过K-RVEA和MOEA/D-EGO对3个目标进行300次功能评价后获得的IGD值的统计结果

Tab.3 Statistical results of IGD values obtained after 300 functional evaluations of the three targets by K-RVEA and MOEA/D-EGO

问题	K-RVEA			MOEA/D-EGO
	min	mean	max	↑	min	mean	max
DTLZ1	82.03	106.5	125.2	≈	145.9	177.9	224.5
DTLZ2	0.092	0.155	0.262	≈	0.081	0.103	0.212
DTLZ3	181.5	280.1	353.1	≈	161.5	205.9	281.8
DTLZ4	0.190	0.448	0.737	≈	0.357	0.436	0.574
DTLZ5	0.050	0.115	0.211	↓	0.035	0.046	0.071
DTLZ6	2.121	2.764	3.343	≈	0.491	2.551	4.126
DTLZ7	0.088	0.112	0.150	↑	0.154	0.646	1.254

3.2 DTLZ问题的性能

表1展示了4种算法在25次独立运行中的比较结果。ParEGO的实现仅支持4个目标,因此,超出4个目标的结果用“NA”表示。结果包括IGD的最小、平均和最大值,最佳值突出显示。多目标进化算法的性能通常通过IGD和HV评价,但这些结果受参数设置影响较大,特别是当目标数量较多时。例如,IGD值对参考集大小敏感,不同文献使用不同大小的参考集。本研究对目标数量使用了适当大小的参考集,并使用最差目标函数值加小阈值作为计算超体积的参考点。

表1中,K-RVEA在大部分算法中表现最好,除了DTLZ1和DTLZ3。原因是这两个问题有多个局部帕累托最优解,因此,RVEA和K-RVEA的收敛速度较慢。与SMS-EGO的比较中,选择不同的停止标准,允许SMS-EGO进行10次并行运行并在24小时内存储所有解决方案,作为停止准则。

3个目标和4个目标分别得到了120个和115个功能评价的结果,如表2所示。这些结果是用少量的函数评价表明,K-RVEA的性能优于比较的算法。其中,没有比较K-RVEA和SMS-EGO在4个目标以上范围内的问题,因为SMS-EGO需要更多的时间来处理此类问题。

在经过300次原始函数评估后,表3展示了K-RVEA与MOEA/D-EGO在3个目标函数问题上的比较。需要指出的是, MOEA/D-EGO提供的实现仅适用于2个和3个目标问题。从表3可以看出,除DTLZ5外,K-RVEA在所有测试问题上的表现均优于或至少与MOEA/D-EGO相当。对于DTLZ5问题,其帕累托前沿呈现出一条覆盖目标空间某子空间的曲线,导致K-RVEA和RVEA算法中大部分参考向量为空,意味着没有解决方案被分配给这些参考向量。值得注意的是,对于K-RVEA和RVEA,大约70%的参考向量未被分配任何解,这一现象导致解过程较为缓慢,且收敛到帕累托前沿的速度较慢。针对这类问题,本文在使用K-RVEA时,增加更多的参考向量可能会改善算法的表现。增加参考向量的数量有助于其更好地覆盖目标空间,避免部分参考向量长时间为空,从而加快收敛速度并提高求解精度。因此,针对具有特殊帕累托前沿特征的问题,适当调整参考向量的数量和分布,可能是优化K-RVEA算法的一个有效途径。

图2展示了DTLZ7问题中,非支配解集与通过比较算法得到的最佳IGD值的对比。从图2可以看出,与K-RVEA和MOEA/D-EGO相比,K-RVEA和RVEA得到的非支配解更接近帕累托前沿。对于DTLZ7问题,RVEA和K-RVEA由于参考向量的适应性,展现出较好的潜力,能够获得接近帕累托前沿的解。由于运行时间限制,未对超过4个目标的优化问题运行SMS-EGO。

显示原图|下载原图ZIP|生成PPT

图2 由K-RVEA、RVEA、ParEGO和MOEA/D-EGO得到的非支配解用圆表示,3个目标DTLZ7的IGD值最好,其中点代表帕累托前沿

Fig.2 The non-dominated solutions obtained by K-RVEA, RVEA, ParEGO and MOEA/D-EGO are represented by circles, and the IGD values of the three targets DTLZ7 are the best, where the points represent the Pareto frontier

此外,图3给出了具有10个目标的DTLZ2问题的平行坐标图。从图3中可以看出,K-RVEA得到的解集覆盖范围大于RVEA得到的解集,换句话说,K-RVEA生成的解分布更均匀。RVEA解集密度较低的原因在于种群规模较小。由于最大函数评估数目相对较少,并且RVEA的性能依赖于最大代数,本文将RVEA的种群规模减少至50个。为了更令人信服地证明K-RVEA的性能,本文测试和比较了WFG问题的算法。

显示原图|下载原图ZIP|生成PPT

图3 由K-RVEA和RVEA在10个目标上以最佳IGD值运行得到的非支配解的平行坐标图

Fig.3 Parallel coordinate plot of the non-dominated solution obtained by K-RVEA and RVEA running at the optimal IGD values on 10 targets

4 结束语

本文提出了一种贝叶斯信息熵辅助参考向量引导进化算法,称为K-RVEA,用于求解具有3个以上目标的高维多目标优化问题。该算法采用贝叶斯信息熵模型来逼近每个目标函数。在使用原始、昂贵目标函数进行重新评估时,本文考虑了收敛性和多样性的问题。为此,在RVEA中,除了引入自适应参考向量外,还加入了一组固定的、均匀分布的参考向量。贝叶斯信息熵模型更新时,根据训练样本与参考向量的关系选择训练样本,限制了训练代理的计算时间,并减少了参与训练数据的数量。

本文研究了K-RVEA在具有3、4、6、8和10个目标的基准问题上的表现,并将其与3种最先进的进化算法进行比较。实验结果表明,K-RVEA在给定相同数量的函数评估下,相较于比较的算法,具有更优的整体性能。在本文的实验中,决策变量的数量设置为10个,这与其他文献中使用贝叶斯信息熵作为替代模型的做法一致。然而,如何使进化算法能够处理更多决策变量的优化问题,将是未来研究的一个重要方向。

未来的另一个研究方向是探索所提出的K-RVEA在处理约束计算昂贵优化问题时的表现。此外,本文中固定了更新代理的代数,尽管实证结果表明,K-RVEA在不同频率更新代理时对基准问题的性能相对不敏感,但我们认为,适应性地调整代理更新的频率可能会进一步提升算法性能。因此,开发自适应的代理更新方法,将是我们未来研究的关键任务。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序

[1]	MIETTINEN K. Nonlinear multiobjective optimization[M]. Boston, MA: Springer US, 1998.

[2]	孙良旭, 李林林, 刘国莉. 基于非欧几何权向量产生策略的分解多目标优化算法[J]. 计算机科学, 2024, 51(11): 280-291. DOI SUN L X, LI L L, LIU G L. Decomposition multi-objective optimization algorithm with weight vector generation strategy based on non-euclidean geometry[J]. Computer Science, 2024, 51(11): 280-291.

[3]	赵昳. 代理模型辅助的高维多目标进化优化方法研究[D]. 太原: 太原科技大学, 2022. ZHAO Y. Research on high-dimensional multi-objective evolutionary optimization method aided by agent model[D]. Taiyuan: Taiyuan University of Science and Technology, 2022.

[4]	蔡昕烨, 马中雨, 张峰, 等. 基于自适应分解的多任务协作型昂贵多目标优化算法[J]. 计算机学报, 2021, 44(9): 1 934-1 948. CAI X Y, MA Z Y, ZHANG F, et al. Adaptive multitask with multipopulation-based cooperative search for expensive multiobjective optimization problems[J]. Chinese Journal of Computers, 2021, 44(9): 1 934-1 948.

[5]	LOSHCHILOV I, SCHOENAUER M, SEBAG M. Dominance-based Pareto-surrogate for multi-objective optimization[M]//Simulated Evolution and Learning. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010: 230-239.

[6]	赵孟杰. 基于多目标协同计算的油藏生产优化理论[D]. 青岛: 中国石油大学(华东), 2021. ZHAO M J. Oil reservoir production optimization theory based on multi-objective collaborative computing[D]. Qingdao: China University of Petroleum (East China), 2021.

[7]	JIN Y C. Surrogate-assisted evolutionary computation: recent advances and future challenges[J]. Swarm and Evolutionary Computation, 2011, 1(2): 61-70.

[8]	李飞, 吴紫恒, 刘阚蓉, 等. 基于R2指标和目标空间分解的高维多目标粒子群优化算法[J]. 控制与决策, 2021, 36(9): 2 085-2 094. LI F, WU Z H, LIU K R, et al. R2 indicator and objective space partition based many-objective particle swarm optimizer[J]. Control and Decision, 2021, 36(9): 2 085-2 094.

[9]	孙超利, 李贞, 金耀初. 模型辅助的计算费时进化高维多目标优化[J]. 自动化学报, 2022, 48(4): 1 119-1 128. SUN C L, LI Z, JIN Y C. Surrogate-assisted expensive evolutionary many-objective optimization[J]. Acta Automatica Sinica, 2022, 48(4): 1 119-1 128.

[10]	DI NUOVO A G, ASCIA G, CATANIA V. A study on evolutionary multi-objective optimization with fuzzy approximation for computational expensive problems[M]. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012: 102-111.

[11]	LUO C, SHIMOYAMA K, OBAYASHI S. Kriging model based many-objective optimization with efficient calculation of expected hypervolume improvement[C]// 2014 IEEE Congress on Evolutionary Computation (CEC),Beijing, 2014: 1 187-1 194.

[12]	PILAT M, NERUDA R. ASM-MOMA: Multiobjective memetic algorithm with aggregate surrogate model[C]// 2011 IEEE Congress of Evolutionary Computation (CEC), New Orleans, 2011: 1 202-1 208.

[13]	CHENG R, JIN Y C, OLHOFER M, et al. A reference vector guided evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(5): 773-791.

[14]	COELLO C A, CHRISTIANSEN A D. Multiobjective optimization of trusses using genetic algorithms[J]. Computers & Structures, 2000, 75(6): 647-660.

[15]	ISHIBUCHI H, MASUDA H, TANIGAKI Y, et al. Modified distance calculation in generational distance and inverted generational distance[M]. Cham: Springer International Publishing, 2015: 110-125.

[16]	WHILE L, HINGSTON P, BARONE L, et al. A faster algorithm for calculating hypervolume[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(1): 29-38.

[17]	KNOWLES J. ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(1): 50-66.

[18]	ZHANG Q F, LIU W D, TSANG E, et al. Expensive multiobjective optimization by MOEA/D with Gaussian process model[J]. IEEE Transactions on Evolutionary Computation, 2010, 14(3): 456-474.

[19]	CHENG R, JIN Y C, OLHOFER M, et al. A reference vector guided evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(5): 773-791.

[20]	ZHANG Q, CHEN X. A fuzzy-related entropy based genetic algorithm for multi-objective optimization[J]. Computational Intelligence and Neuroscience, 2013(5): 867 521.

[21]	PANAGANT N, PHOLDEE N, BUREERAT S, et al. A comparative study of recent multi-objective metaheuristics for solving constrained truss optimisation problems[J]. Archives of Computational Methods in Engineering, 2021, 28(5): 4 031-4 047.

[22]	HAMDY N, HASSAN M R, HUSSEIN M E. A genetic algorithm to solve the robust design problem for a flow network with node failure[J]. Transactions on Networks and Communications, 2020, 8(4): 1-10.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

1 背景

1.1 参考向量进化算法(RVEA)

图1 一个双目标优化问题的参考向量的说明性例子

1.2 贝叶斯最大信息熵思想

2 基于最大信息熵的多目标优化

2.1 确定整个种群空间的理想点

2.2 参考点设置

3 数值实验

3.1 参数设置

表1 由K-RVEA、RVEA 和ParEGO 获得的IGD 值的统计结果

表2 通过K-RVEA、RVEA、ParEGO、SMS-EGO和MOEA/D-EGO对3个和4个目标获得的IGD值的统计结果,分别进行了120和115个功能评估

表3 通过K-RVEA和MOEA/D-EGO对3个目标进行300次功能评价后获得的IGD值的统计结果

3.2 DTLZ问题的性能

图2 由K-RVEA、RVEA、ParEGO和MOEA/D-EGO得到的非支配解用圆表示,3个目标DTLZ7的IGD值最好,其中点代表帕累托前沿

图3 由K-RVEA和RVEA在10个目标上以最佳IGD值运行得到的非支配解的平行坐标图

4 结束语

参考文献