基于帕累托前沿关系求解约束多目标优化问题

doi:10.16182/j.issn1004731x.joss.22-1430

摘要/Abstract

摘要：

为解决约束多目标优化问题中的平衡约束满足与目标函数优化以及可行域复杂等挑战，提出了基于不同帕累托前沿关系的分类搜索方法。提出一种双种群双阶段框架：进化一个辅助种群P_a和一个主种群P_m，并将进化过程分为学习阶段和搜索阶段。学习阶段，种群P_a向UPF(unconstrained Pareto front)进行搜索，而种群P_m向CPF(constrained Pareto front)进行搜索，旨在探索UPF与CPF之间的关系；完成学习后，对不同问题的UPF与CPF关系进行分类，以指导后续搜索策略；在搜索阶段，根据不同的分类关系，调整种群P_a的搜索策略，旨在使种群P_a为种群P_m提供更有效的辅助信息。基于此算法框架，对不同类型约束多目标优化问题的帕累托前沿关系进行了分类，实现了对CPF更有效的搜索。实验结果表明：所提算法与其他7种先进的约束多目标优化算法相比具有更显著的性能优势。通过学习与利用UPF与CPF的关系，能够选择更合适的搜索策略去应对具有不同特性的约束多目标优化问题，以获得更具优势的最终解集。

关键词: 约束多目标优化, 帕累托前沿关系, 双种群, 学习阶段, 搜索阶段

Abstract:

To address the challenges of balancing the constraint satisfaction and objective function optimization, and dealing with the complex feasible regions in constrained multi-objective optimization problems(CMOPs), a classification-based search approach is proposed based on different Pareto front relationships. A dual-population dual-phase framework is proposed in which an auxiliary population P_a and a main population P_m are evolved and the evolution process is divided into a learning phase and a search phase. During the learning phase, P_a explores unconstrained Pareto front (UPF) and P_m explores constrained Pareto front(CPF), through which the relationship between UPF and CPF is determined. After completing the learning phase, the different classified relationships guide the subsequent search strategies. In the search phase, the algorithm adaptively adjusts the search strategy of P_a to provide effective assistance for P_m according to the different classification relationships between UPF and CPF. Based on this framework, Pareto front relationships for different CMOPs are classified to achieve the more effective searching for CPF. Experimental results show that the proposed algorithm has a better performance compared with the seven state-of-the-art constrained multi-objective evolutionary algorithms (CMOEAs). Through learning and utilizing the relationship between UPF and CPF, the more appropriate search strategies can be selected to handle CMOPs with different characteristics and a more advantageous final solution set can be got.

Key words: constrained multi-objective optimization, relationship between Pareto fronts, two-population, learning phase, search phase

中图分类号:

TP18

王昱博,胡成玉,龚文引 . 基于帕累托前沿关系求解约束多目标优化问题[J]. 系统仿真学报, 2024, 36(4): 901-914.

Wang Yubo,Hu Chengyu,Gong Wenyin . Handling Constrained Multi-objective Optimization Problems Based on Relationship Between Pareto Fronts[J]. Journal of System Simulation, 2024, 36(4): 901-914.

图/表 13

图1

图2

图3

表1

不同算法在LIR-CMOP1-14上的IGD+结果

问题

BiCo

C-TAEA

CMOEA-MS

PPS

ToP

TiGE-2

URCMO

RBPF

LIRCMOP5

1.230 00

(0.004 24)-

1.200 00

(0.196 00)-

0.250 00

(0.053 40)-

0.006 88

(0.001 44)+

1.200 00

(0.022 30)-

1.010 00

(0.398 00)-

0.123 00

(0.290 00)=

0.142 00

(0.297 00)

LIRCMOP6

1.350 0

(0.000 184)-

1.220 0

(0.341 000)-

0.368 0

(0.271 000)-

0.050 3

(0.245 000)+

1.300 0

(0.185 000)-

1.060 0

(0.454 000)-

0.075 9

(0.106 000)=

0.260 0

(0.450 000)

LIRCMOP13

1.320 0

(0.002 01)-

0.047 1

(0.001 36)-

0.043 9

(0.001 27)=

0.077 9

(0.004 49)-

1.320 0

(0.009 00)-

1.100 0

(0.481 00)-

0.063 4

(0.002 93)-

0.043 4(0.001 07)

LIRCMOP14

1.270 0

(0.002 110)-

0.048 6

(0.000 738)-

0.044 2

(0.000 829)+

0.062 6

(0.002 400)-

1.290 0

(0.078 000)-

1.030 0

(0.494 000)-

0.050 9

(0.001 860)-

0.045 4 (0.001 520)

LIRCMOP9

0.909

(0.134 0)-

0.317

(0.086 5)-

0.491

(0.142 0)-

0.221

(0.084 1)-

0.362

(0.143 0)-

0.509

(0.179 0)-

0.195

(0.088 7)=

0.158(0.028 4)

LIRCMOP10

0.933 0

(0.072 3)-

0.301 0

(0.042 2) -

0.409 0

(0.198 0) -

0.197 0

(0.097 9) -

0.332 0

(0.078 8) -

0.745 0

(0.159 0) -

0.115 0

(0.058 9)-

0.058 3(0.081 0)

LIRCMOP11

0.677

(0.214 0)-

0.175

(0.038 7)-

0.280

(0.148 0)-

0.230

(0.144 0)-

0.413

(0.119 0)-

0.713

(0.164 0)-

0.150

(0.139 0)-

0.112

(0.018 7)

LIRCMOP12

0.556

(0.207 0)-

0.235

(0.151 0)=

0.315

(0.115 0)-

0.151

(0.071 2) =

0.223

(0.056 2)-

0.371

(0.077 2)-

0.160

(0.043 8)=

0.144(0.029 9)

LIRCMOP1

0.188 0

(0.011 3)-

0.259 0

(0.049 5)-

0.268 0

(0.032 3)-

0.024 2

(0.033 6)+

0.266

(0.012 5)-

0.186

(0.016 0)-

0.112 0

(0.045 3)-

0.049 3 (0.030 5)

LIRCMOP2

0.110 0

(0.012 20)-

0.140 0

(0.056 00)-

0.180 0

(0.022 70)-

0.010 9

(0.007 31)+

0.185 0

(0.019 40)-

0.114 0

(0.009 56)-

0.024 1

(0.033 10)+

0.024 6 (0.012 90)

LIRCMOP3

0.187 0

(0.023 9)-

0.259 0

(0.062 7)-

0.252 0

(0.046 2)-

0.071 1

(0.061 7)=

0.282 0

(0.010 5)-

0.185 0

(0.015 2)-

0.064 7

(0.047 4)-

0.034 3

(0.021 1)

LIRCMOP4

0.130 0

(0.020 4)-

0.203 0

(0.085 5)-

0.197 0

(0.021 1)-

0.040 4

(0.037 2)=

0.202 0

(0.015 9)-

0.123 0

(0.013 8)-

0.072 9

(0.056 0-

0.029 6(0.021 4)

LIRCMOP7

0.479 0

(0.675 0)-

0.338 0

(0.544 0)-

0.108 0

(0.020 3)-

0.108 0

(0.031 3)-

1.310 0

(0.652 0)-

0.251 0

(0.091 2)-

0.021 7

(0.031 7)-

0.015 4 (0.023 9)

LIRCMOP8

1.240 0

(0.690 0)-

0.712 0

(0.662 0)-

0.180 0

(0.044 3)-

0.157 0

(0.051 7)-

1.540 0

(0.454 0)-

0.391 0

(0.273 0)-

0.011 6

(0.018 4)+

0.033 3 (0.072 3)

+/-/=

0/14/0

0/13/1

1/12/1

4/7/3

0/14/0

2/8/4

表1

表2

不同算法在LIR-CMOP1-14上的HV结果

问题

BiCo

C-TAEA

CMOEA-MS

PPS

ToP

TiGE-2

URCMO

RBPF

LIRCMOP5

(0)-

0.006 14

(0.033 6)-

0.145 00

(0.022 1)-

0.290 00

(0.001 3)+

(0)-

0.029 00

(0.054 5)-

0.252 00

(0.074 5) =

0.245 00

(0.078 9)

LIRCMOP6

(0)-

0.009 96

(0.026 0)-

0.092 50

(0.026 7)-

0.190 00

(0.035 9)+

0.001 90

(0.010 4)-

0.024 00

(0.037 5)-

0.169 00

(0.034 5) =

0.138 00

(0.074 3)

LIRCMOP13

0.000 115

(0.000 137)-

0.546 000

(0.001 880)-

0.556 000

(0.001 290)=

0.510 000

(0.006 180)-

0.003 310

(0.012 500)-

0.072 100

(0.138 000)-

0.535 000

(0.002 910)-

0.556 000

(0.001 050)

LIRCMOP14

0.000 37 (0.000 334)-

0.546 00

(0.000 833)-

0.556 00

(0.000 965)+

0.530 00

(0.003 720)-

0.003 68

(0.018 600)-

0.089 60

(0.153 000)-

0.549 00

(0.002 010)-

0.555 00

(0.001 240)

LIRCMOP9

0.137

(0.057 8)-

0.349

(0.056 5)-

0.279

(0.064 3)-

0.437

(0.048 3)-

0.331

(0.074 7)-

0.242

(0.083 3)-

0.442

(0.065 4) =

0.449

(0.026 3)

LIRCMOP10

0.064 7

(0.017 9)-

0.504 0

(0.034 6)-

0.413 0

(0.155 0)-

0.579 0

(0.071 9)-

0.472 0

(0.075 0)-

0.151 0 (0.048 8)-

0.639 0

(0.038 2)-

0.672 0

(0.055 7)

LIRCMOP11

0.270

(0.102 0)-

0.606

(0.250 0)-

0.490

(0.108 0)-

0.512

(0.110 0)-

0.376

(0.079 6)-

0.191

(0.072 2)-

0.577

(0.109 0)-

0.607

(0.016 8)

LIRCMOP12

0.362

(0.097 7)-

0.506

(0.054 1) =

0.440

(0.050 8)-

0.525

(0.050 2) =

0.475

(0.043 6)-

0.370

(0.052 7)-

0.521

(0.030 9) =

0.530

(0.019 3)

LIRCMOP1

0.136

(0.005 18)-

0.114

(0.021 10)-

0.108

(0.012 90)-

0.225

(0.020 50)+

0.107

(0.008 56)-

0.137

(0.008 17)-

0.176

(0.024 90)-

0.206 (0.016 50)

LIRCMOP2

0.262

(0.009 11)-

0.260

(0.030 30)-

0.221

(0.017 00)-

0.355

(0.007 64)+

0.217

(0.016 10)-

0.262

(0.008 36)-

0.338

(0.033 10)-

0.341

(0.013 20)

LIRCMOP3

0.126 0

(0.010 30)-

0.096 5

(0.027 60)-

0.102 0

(0.016 80)-

0.173 0

(0.027 20) =

0.090 5

(0.006 14)-

0.124

(0.008 65)-

0.176

(0.024 10)-

0.188

(0.008 00)

LIRCMOP4

0.224

(0.012 50)-

0.191

(0.038 20)-

0.188

(0.013 60)-

0.288

(0.276 00) =

0.185

(0.108 00)-

0.230

(0.009 14)-

0.265

(0.039 00)-

0.294

(0.016 40)

LIRCMOP7

0.187 0

(0.105 00)-

0.208 0

(0.085 70)-

0.245 0

(0.008 76)-

0.246 0

(0.013 20)-

0.052 8

(0.098 80)-

0.196 0

(0.023 00)-

0.287 0

(0.014 80)-

0.289 00

(0.011 50)

LIRCMOP8

0.066 2

(0.103 00)-

0.135 0

(0.099 10)-

0.230 0

(0.010 40)-

0.235 0

(0.016 30)-

0.021 50

(0.066 00)-

0.174

(0.039 10)-

0.291

(0.008 90)+

0.284

(0.024 00)

+/-/=

0/14/0

0/13/1

1/12/1

4/7/3

0/14/0

1/9/4

表2

表3

表4

表5

表6

表7

表8

表9

表10

参考文献 23

1	Jozefowiez Nicolas, Semet Frédéric, El-Ghazali Talbi. Multi-objective Vehicle Routing Problems[J]. European Journal of Operational Research, 2008, 189(2): 293-309.
2	Saravanan R, Ramabalan S, Godwin Raja Ebenezer N, et al. Evolutionary Multi Criteria Design Optimization of Robot Grippers[J]. Applied Soft Computing, 2009, 9(1): 159-172.
3	Mala-Jetmarova H, Sultanova Nargiz, Savic D. Lost in Optimisation of Water Distribution Systems?A Literature Review of System Operation[J]. Environmental Modelling & Software, 2017, 93: 209-254.
4	Liu Zhizhong, Wang Yong. Handling Constrained Multiobjective Optimization Problems with Constraints in Both the Decision and Objective Spaces[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(5): 870-884.
5	Fan Zhun, Li Wenji, Cai Xinye, et al. Push and Pull Search for Solving Constrained Multi-objective Optimization Problems[J]. Swarm and Evolutionary Computation(S2210-6502), 2019, 44:665-679.
6	Li Ke, Chen Renzhi, Fu Guangtao, et al. Two-archive Evolutionary Algorithm for Constrained Multiobjective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(2): 303-315.
7	Ma Zhongwei, Wang Yong, Song Wu. A New Fitness Function with Two Rankings for Evolutionary Constrained Multiobjective Optimization[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 51(8): 5005-5016.
8	Zhou Yalan, Zhu Min, Wang Jiahai, et al. Tri-goal Evolution Framework for Constrained Many-objective Optimization[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2020, 50(8): 3086-3099.
9	Hernández Sosa, Adrián Víctor, Oliver Schütze, et al. The Set-based Hypervolume Newton Method for Bi-objective Optimization[J]. IEEE Transactions on Cybernetics, 2020, 50(5): 2186-2196.
10	Tian Ye, Zhang Tao, Xiao Jianhua, et al. A Coevolutionary Framework for Constrained Multiobjective Optimization Problems[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(1): 102-116.
11	Liang Jing, Qiao Kangjia, Yu Kunjie, et al. Utilizing the Relationship Between Unconstrained and Constrained Pareto Fronts for Constrained Multiobjective Optimization[J]. IEEE Transactions on Cybernetics, 2023, 53(6): 3873-3886.
12	Zitzler Eckart, Laumanns Marco, Thiele Lothar. SPEA2: Improving the Strength Pareto Evolutionary Algorithm: TIK-report 103[R]. Zurich: ETH Zurich, 2001,103.
13	Tian Ye, Zhang Yajie, Su Yansen, et al. Balancing Objective Optimization and Constraint Satisfaction in Constrained Evolutionary Multiobjective Optimization[J]. IEEE Transactions on Cybernetics, 2022, 52(9): 9559-9572.
14	Liu Zhizhong, Wang Bingchuan, Tang Ke. Handling Constrained Multiobjective Optimization Problems via Bidirectional Coevolution[J]. IEEE Transactions on Cybernetics, 2022, 52(10): 10163-10176.
15	Tian Ye, Cheng Ran, Zhang Xingyi, et al. PlatEMO: A MATLAB Platform for Evolutionary Multi-objective Optimization[J]. IEEE Computational Intelligence Magazine, 2017, 12(4): 73-87.
16	Kalyanmoy Deb, Himanshu Jain. An Evolutionary Many-objective Optimization Algorithm Using Reference-point-based Nondominated Sorting Approach, Part I: Solving Problems with Box Constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4):577-601.
17	Fan Zhun, Li Wenji, Cai Xinye, et al. Difficulty Adjustable and Scalable Constrained Multiobjective Test Problem Toolkit[J]. Evolutionary Computation, 2020, 28(3): 339-378.
18	Fan Zhun, Li Wenji, Cai Xinye, et al. An Improved Epsilon Constraint-handling Method in MOEA/D for CMOPs with Large Infeasible Regions[J]. Soft Computing, 2019, 23(23): 12491-12510.
19	Parsons M G, Scott R L. Formulation of Multicriterion Design Optimization Problems for Solution with Scalar Numerical Optimization Methods[J]. Journal of Ship Research, 2004, 48(1): 61-76.
20	Floudas C A. Nonlinear and Mixed-integer Optimization: Fundamentals and Applications[M]. Oxford: Oxford University Press, 1995.
21	Kocis G R, Grossmann I E. A Modelling and Decomposition Strategy for the Minlp Optimization of Process Flowsheets[J]. Computers & Chemical Engineering, 1989, 13(7): 797-819.
22	张进峰, 杨涛宁, 马伟皓. 基于多目标粒子群算法的船舶航速优化[J]. 系统仿真学报, 2019, 31(4): 787-794.
	Zhang Jinfeng, Yang Taoning, Ma Weihao. Ship Speed Optimization Based on Multi-objective Particle Swarm Algorithm[J]. Journal of System Simulation, 2019, 31(4): 787-794.
23	闫秀英, 党苗苗. 基于改进多目标粒子群算法的家庭用电时段优化[J]. 系统仿真学报, 2022, 34(1): 70-78.
	Yan Xiuying, Dang Miaomiao. Optimization of Household Electricity Consumption Period Based on Improved Multi-objective Particle Swarm Optimization[J]. Journal of System Simulation, 2022, 34(1): 70-78.

问题	BiCo	C-TAEA	CMOEA-MS	PPS	ToP	TiGE-2	URCMO	RBPF
+/-/=	0/8/1	0/8/1	1/5/3	0/9/0	0/4/0	0/9/0	0/7/2
DASCMOP1	0.729 00 (0.024 800)-	0.166 00 (0.003 170)-	0.728 00 (0.053 900)-	0.059 70 (0.104 000)-	0.782 00 (0.041 500)-	0.608 00 (0.143 000)-	0.017 80 (0.085 500) =	0.002 23 (0.000 102)
DASCMOP2	0.151 00 (0.007 590)-	0.056 30 (0.018 800)-	0.151 00 (0.009 150)-	0.004 03 (0.000 180)-	0.671 00 (0.231 000)-	0.130 00 (0.040 500)-	0.006 44 (0.014 300) =	0.003 86 (0.000 180)
DASCMOP3	0.187 00 (0.014 100)-	0.122 00 (0.031 000)-	0.197 00 (0.015 300)-	0.129 00 (0.082 0000)-	0.685 00 (0.161 000)-	0.190 00 (0.024 000)-	0.139 00 (0.073 500)-	0.005 54 (0.000 142)
DASCMOP4	0.063 20 (0.113 00)-	0.007 59 (0.001 50)-	0.044 10 (0.086 40) =	0.243 00 (0.145 00)-	NaN (NaN)	0.018 10 (0.007 27)-	0.112 00 (0.143 00)-	0.007 27 (0.035 80)
DASCMOP5	0.075 80 (0.155 000)-	0.005 72 (0.000 833)-	0.071 00 (0.160 000) =	0.167 00 (0.253 000)-	NaN (NaN)	0.018 70 (0.004 000)-	0.037 60 (0.099 900)-	0.001 83 (0.000 081)
DASCMOP6	0.145 0 (0.179 00)-	0.015 4 (0.008 06) =	0.216 0 (0.221 00)-	0.247 0 (0.303 00)-	NaN (NaN)	0.075 2 (0.139 00)-	0.361 0 (0.175 00)-	0.039 7 (0.092 20)
DASCMOP7	0.025 8 (0.001 710)-	0.027 2 (0.001 010)-	0.023 0(0.000 633) =	0.187 0 (0.164 000)-	NaN (NaN)	0.099 2 (0.017 6000)-	0.030 8 (0.011 000)-	0.023 4 (0.001 010)
DASCMOP8	0.019 4 (0.002 570) =	0.022 4 (0.002 570)-	0.018 4(0.000 588)+	0.165 0 (0.208 000)-	NaN (NaN)	0.059 0 (0.015 800)-	0.022 9 (0.004 160)-	0.018 8 (0.000 753)
DASCMOP9	0.251 0 (0.027 10)-	0.186 0 (0.031 90)-	0.232 0 (0.003 00)-	0.166 0 (0.128 00)-	0.458 0 (0.094 30)-	0.211 0 (0.026 10)-	0.023 6 (0.001 02)-	0.021 2 (0.001 12)

问题	BiCo	C-TAEA	CMOEA-MS	PPS	ToP	TiGE-2	URCMO	RBPF
+/-/=	0/7/3	3/6/1	2/6/2	0/10/0	0/7/0	0/9/1	0/10/0
C1_DTLZ1	0.014 6 (0.000 221)-	0.016 3 (0.000 128)-	0.014 7 (0.000 275)-	0.019 0 (0.000 838)-	NaN (NaN)	0.249 0 (0.088 100)-	0.018 0 (0.001 410)-	0.014 2 (0.000 172)
C1_DTLZ3	1.120 0 (2.750 0)-	0.128 0 (0.461 0)-	0.230 0 (1.460 0) =	2.970 0 (3.910 0)-	0.492 0 (1.470 0)-	5.210 0 (3.460 0)-	2.900 0 (3.730 0)-	0.024 2 (0.001 4)
C2_DTLZ2	0.019 2 (0.000 610) =	0.023 5 (0.000 438)-	0.019 5 (0.000 907)-	0.024 8 (0.000 716)-	0.036 4 (0.007 100)-	0.037 4 (0.002 860)-	0.022 2 (0.002 090)-	0.018 5 (0.000 654)
C3_DTLZ4	0.059 3 (0.002 16)-	0.061 0 (0.002 38)-	0.321 0 (0.041 70)-	0.097 2 (0.034 60)-	0.106 0 (0.007 05)-	0.086 7 (0.003 83)-	0.069 4 (0.003 33)-	0.056 1 (0.002 29)
DC1_DTLZ1	0.008 67 (0.000 599) =	0.010 60 (0.000 126)-	0.010 60 (0.003 260)-	0.029 50 (0.045 600)-	0.018 90 (0.004 020)-	0.455 00 (0.306 000)-	0.009 86 (0.000 668)-	0.008 44 (0.000 417)
DC1_DTLZ3	0.014 4 (0.001 160) =	0.016 1 (0.000 708)-	0.076 1 (0.089 700) =	0.469 0 (0.726 000)-	1.600 0 (2.300 000)-	1.820 0 (0.668 000)-	0.027 9 (0.028 900)-	0.014 4 (0.001 210)
DC2_DTLZ1	0.131 0 (0.075 900)-	0.016 4 (0.000 175)+	0.015 1 (0.000 520)+	0.031 5 (0.038 200)-	NaN (NaN)	0.255 0 (0.069 600)-	0.028 9 (0.028 400)-	0.024 5 (0.037 900)
DC2_DTLZ3	0.565 (0.003 07)-	0.374 (0.258 00)=	0.455 (0.218 00)-	0.375 (0.264 00)-	NaN (NaN)	0.989 (0)=	0.579 (0.016 10)-	0.152(0.206 00)
DC3_DTLZ1	0.083 90 (0.082 600)-	0.006 51 (0.000 165)+	0.025 80 (0.006 820)-	0.561 00 (0.956 000)-	2.070 00 (2.960 000)-	1.450 00 (0.777 000)-	0.018 00 (0.067 200)-	0.010 60 (0.030 000)
DC3_DTLZ3	1.200 00 (0.491 000)-	0.009 81 (0.000 503)+	0.299 00 (0.424 000)+	1.940 00 (1.770 000)-	7.880 00 (3.980 000)-	3.580 00 (0.724 000)-	0.722 00 (0.496 000)-	0.573 00 (0.320 000)

算法	IGD+ 排序值	p-值	HV 排序值	p-值
BiCo	5.333 0	0	5.560 6	0
C-TAEA	3.909 1	0.000 072	3.697 0	0.000 036
CMOEA-MS	4.484 8	0.000 001	4.424 2	0.000 002
PPS	4.242 4	0.000 006	4.121 2	0.000 019
ToP	7.212 1	0	7.242 4	0
TiGE-2	5.818 2	0	5.924 2	0
URCMO	3.484 8	0.001 089	3.484 8	0.001 299
RBPF	1.515 2		1.545 5

变体	IGD+(+/-/=)	HV(+/-/=)
RBPF1	5/17/11	4/19/10
RBPF2	2/17/14	3/17/13
RBPF3	2/22/9	1/23/9
RBPF4	0/1/32	0/1/32
RBPF5	0/2/31	0/1/32

问题	目标数量	决策变量数量	约束数量
Bulk Carrier Design^[19]	3	6	9
Process Flow Sheeting^[20]	2	3	3
Process Synthesis^[21]	2	2	2