A Novel Immune Algorithm for Multiparty Multiobjective Optimization

Kesheng Chen; Wenjian Luo; Qi Zhou; Yujiang liu; Peilan Xu; Yuhui Shi

cs.NEMar 29, 2026

A Novel Immune Algorithm for Multiparty Multiobjective Optimization

Authors: Kesheng Chen, Wenjian Luo, Qi Zhou, Yujiang liu, Peilan Xu, Yuhui Shi

Organizations: Guangdong Provincial Key Laboratory of Novel Security Intelligence Technologies, School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen 518055, China. · Peng Cheng Laboratory, Shenzhen 518000, China. · School of Artificial Intelligence, Nanjing University of Information Science and Technology, Nanjing 210044, China. · School of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China.

Abstract

Traditional multiobjective optimization problems (MOPs) are insufficiently equipped for scenarios involving multiple decision makers (DMs), which are prevalent in many practical applications. These scenarios are categorized as multiparty multiobjective optimization problems (MPMOPs). For MPMOPs, the goal is to find a solution set that is as close to the Pareto front of each DM as much as possible. This poses challenges for evolutionary algorithms in terms of searching and selecting. To better solve MPMOPs, this paper proposes a novel approach called the multiparty immune algorithm (MPIA). The MPIA incorporates an inter-party guided crossover strategy based on the individual's non-dominated sorting ranks from different DM perspectives and an adaptive activation strategy based on the proposed multiparty cover metric (MCM). These strategies enable MPIA to activate suitable individuals for the next operations, maintain population diversity from different DM perspectives, and enhance the algorithm's search capability. To evaluate the performance of MPIA, we compare it with ordinary multiobjective evolutionary algorithms (MOEAs) and state-of-the-art multiparty multiobjective optimization evolutionary algorithms (MPMOEAs) by solving synthetic multiparty multiobjective problems and real-world biparty multiobjective unmanned aerial vehicle path planning (BPUAV-PP) problems involving multiple DMs. Experimental results demonstrate that MPIA outperforms other algorithms.

Figures & tables

Fig. 1: An example of using inter-party guided crossover. The black circular entities are located on the PF of both DMs. The hexagonal entities are regarded as individuals being guided, while the black circular entities serve as guiding individuals, enabling crossover with the expectation of generating offspring that approach all PF of different DMs.

Solution	Layers *	PS for DM1	PS for DM2	PS for MOP	PS for MPMOP
$X_{1}$	(1,1)	✓	✓	✓	✓
$X_{2}$	(1,1)	✓	✓	✓	✓
$X_{3}$	(1,1)	✓	✓	✓	✓
$X_{4}$	(1,2)	✓	$\times$	✓	$\times$
$X_{5}$	(1,3)	✓	$\times$	✓	$\times$

TABLE I: The situation of the solutions from different perspectives

Fig. 2: Inappropriate activations cause the population to lose diversity in the DM1 perspective. The existing method will select $\{x_{1},x_{2},x_{3}\}$ as the activation set. However, adding $x_{4}$ enables the activation set to have higher population diversity for both DMs.

Fig. 3: The population distribution in solving Case 1 using existing multiparty immune algorithms (such as BPNNIA, BPHEIA and BPAIMA) is shown when the number of activations is set to 20. The Case 1 problem is given in Table VII .

Fig. 4: The population distribution in solving Case 1 using MPIA is shown when the number of activations is adaptive. The Case 1 problem is given in Table VII .

Fig. 5: Overall framework of the MPIA. Here, for better understanding, we assume that there are two parties and each party has two objectives.

Fig. 6: The relevant details of calculating the cover metric $cm_{k}$ of the $k$ -th DM for the given activation individual set $\mathcal{A}=\{x_{1},x_{2},x_{3}\}$ . The details about the population are provided in Table I . Where $\mathcal{B}_{k}$ is the set of frontier individuals for $k$ -th DM. $M_{k}$ denotes the set of objectives for the $k$ -th DM. $M_{1}=\{f_{1},f_{2}\},M_{2}=\{f_{3},f_{4}\},\mathcal{B}_{1}=\{x_{1},x_{2},x_{3},x_{4},x_{5}\},\mathcal{B}_{2}=\{x_{1},x_{2},x_{3}\}$ . The figure intuitively demonstrates why the cover metric $cm$ indicator can measure the cover metric of activation individual set $\mathcal{A}$ in different DM perspectives. The metric $cm_{2}$ is close to 1 and $cm_{1}$ is much smaller than $cm_{2}$ , indicating that the given activation individual set $\mathcal{A}$ has sufficient diversity for DM2, but lacks diversity for DM1.

Parameters	Value
Population size	105
Maximum number of function evaluations (MPUAV-PP)	1.4e5
Number of independent runs	30
Maximum number of function evaluations (MPMOPs)	$1000dM$ *
SBX crossover distribution index	20
SBX crossover probability	1.0

TABLE II: Parameters of Algorithms for Experiments

Fig. 7: Results of MPIA in solving MPMOP9

Problems	Algorithms
Problems	NSGA-II	NSGA-III	MPNDS	MPNDS2	BPHEIA	BPNNIA	BPAIMA	MPIA
MPMOP1	9.26E-03(3.7E-03)	\	1.59E-05(4.8E-06)	1.43E-05(4.6E-06)	4.15E-05(1.4E-05)	3.96E-05(1.5E-05)	6.19E-05(1.6E-05)	2.89E-05(5.8E-06)
MPMOP2	3.90E-02(4.1E-02)	3.75E-01(1.7E-01)	1.28E-02(3.6E-02)	1.52E-02(3.8E-02)	3.59E-02(5.5E-02)	3.28E-02(5.7E-02)	3.08E-05(1.4E-05)	2.37E-05(8.8E-06)
MPMOP3	2.25E-01(9.1E-02)	2.13E-01(4.7E-02)	2.27E-01(8.9E-02)	2.10E-01(9.6E-02)	1.82E-01(9.6E-02)	2.06E-01(1.3E-01)	7.86E-02(2.6E-02)	6.84E-02(2.3E-02)
MPMOP4	1.40E+00(8.0E-01)	1.17E+00(1.4E+00)	4.88E-02(6.7E-03)	5.18E-02(8.5E-03)	5.85E-02(1.6E-02)	5.96E-02(1.8E-02)	3.03E-02(3.4E-03)	3.25E-02(3.1E-03)
MPMOP5	3.56E-01(8.9E-02)	\	4.00E-02(3.8E-03)	4.03E-02(4.1E-03)	4.31E-02(5.5E-03)	4.34E-02(5.8E-03)	3.58E-02(5.7E-03)	3.49E-02(6.9E-03)

TABLE III: MPIGD metric of different algorithms in MPMOP 1 - MPMOP 12

Problems	Efficiency DM Objectives	Safety DM Objectives	Map Type
Case 1	$\textbf{F}_{\text{eff}}=(f_{\textup{length}},f_{\textup{distance}})$	$\textbf{F}_{\text{safe}}=(f_{\textup{fatal}},f_{\textup{eco}})$	MAP-A
Case 2	$\textbf{F}_{\text{eff}}=(f_{\textup{length}}+f_{\textup{height}},f_{\textup{distance}})$	$\textbf{F}_{\text{safe}}=(f_{\textup{fatal}},f_{\textup{eco}})$	MAP-A
Case 3	$\textbf{F}_{\text{eff}}=(f_{\textup{fuel}},f_{\textup{distance}})$	$\textbf{F}_{\text{safe}}=(f_{\textup{fatal}},f_{\textup{eco}})$	MAP-A
Case 4	$\textbf{F}_{\text{eff}}=(f_{\textup{length}},f_{\textup{distance}})$	$\textbf{F}_{\text{safe}}=(f_{\textup{fatal}},f_{\textup{noise}})$	MAP-A
Case 5	$\textbf{F}_{\text{eff}}=(f_{\textup{length}}+f_{\textup{height}},f_{\textup{distance}})$	$\textbf{F}_{\text{safe}}=(f_{\textup{fatal}},f_{\textup{noise}})$	MAP-A
Case 6	$\textbf{F}_{\text{eff}}=(f_{\textup{fuel}},f_{\textup{distance}})$	$\textbf{F}_{\text{safe}}=(f_{\textup{fatal}},f_{\textup{noise}})$	MAP-A

TABLE IV: Case design

Fig. 8: A part of MPIA’s solutions in solving BPUAV-PP Case 1

Fig. 9: Final population of NSGA-II in solving Case 1 problem

Fig. 10: Final population of MPIA in solving Case 1 problem

Problems	Algorithms
Problems	NSGA-II	NSGA-III	MPNDS	MPNDS2	HEIA	NNIA	AIMA	MPIA
Case 1	0.136(0.094)	0.359(0.114)	0.440(0.053)	0.453(0.048)	0.395(0.072)	0.390(0.087)	0.496(0.055)	0.563(0.046)
Case 2	0.292(0.100)	0.427(0.129)	0.451(0.066)	0.461(0.061)	0.413(0.085)	0.396(0.092)	0.509(0.122)	0.565(0.072)
Case 3	0.292(0.106)	0.391(0.124)	0.443(0.060)	0.450(0.065)	0.380(0.082)	0.377(0.098)	0.495(0.085)	0.557(0.069)
Case 4	0.234(0.087)	0.401(0.112)	0.408(0.056)	0.447(0.065)	0.383(0.073)	0.358(0.088)	0.480(0.075)	0.540(0.064)
Case 5	0.229(0.093)	0.456(0.082)	0.421(0.076)	0.458(0.067)	0.361(0.089)	0.378(0.105)	0.507(0.094)	0.518(0.092)

TABLE V: sumHV metric of different algorithms in BPUAV-PP Problem Case 1 - Case 12

Problems	Decision Makers	Algorithms
Problems	Decision Makers	NSGA-II	NSGA-III	MPNDS	MPNDS2	HEIA	NNIA	AIMA	MPIA
Case 1	Effciency	0.081(0.023)	0.083(0.027)	0.108(0.020)	0.110(0.017)	0.097(0.015)	0.103(0.018)	0.122(0.016)	0.134(0.020)
Case 1	Safe	0.192(0.060)	0.275(0.082)	0.332(0.061)	0.343(0.054)	0.298(0.055)	0.287(0.043)	0.374(0.046)	0.428(0.048)
Case 2	Effciency	0.078(0.038)	0.105(0.048)	0.150(0.032)	0.152(0.036)	0.130(0.040)	0.135(0.028)	0.150(0.041)	0.172(0.036)
Case 2	Safe	0.214(0.082)	0.323(0.084)	0.301(0.068)	0.309(0.067)	0.283(0.068)	0.261(0.070)	0.359(0.074)	0.393(0.067)
Case 3	Effciency	0.076(0.024)	0.089(0.026)	0.118(0.016)	0.119(0.022)	0.104(0.024)	0.112(0.023)	0.126(0.024)	0.141(0.026)

TABLE VI: HV metric of different algorithms in Efficiency DM and Safety DM of BPUAV-PP Problem Case 1 - Case 12

Fig. 11: Results of MPIA in solving MPMOP1

Fig. 12: Results of MPIA in solving MPMOP2

Fig. 13: Results of MPIA in solving MPMOP3

Fig. 14: Results of MPIA in solving MPMOP4

Fig. 15: Results of MPIA in solving MPMOP5

Fig. 16: Results of MPIA in solving MPMOP6

Fig. 17: Results of MPIA in solving MPMOP7

Fig. 18: Results of MPIA in solving MPMOP8

Fig. 19: Results of MPIA in solving MPMOP9

Fig. 20: Results of MPIA in solving MPMOP10

Fig. 21: Results of MPIA in solving MPMOP11

Problems	Efficiency DM Objectives	Safety DM Objectives	Map Type
Case 1	$\textbf{F}_{\text{eff}}=(f_{\textup{length}},f_{\textup{distance}})$	$\textbf{F}_{\text{safe}}=(f_{\textup{fatal}},f_{\textup{eco}})$	MAP-A
Case 2	$\textbf{F}_{\text{eff}}=(f_{\textup{length}}+f_{\textup{height}},f_{\textup{distance}})$	$\textbf{F}_{\text{safe}}=(f_{\textup{fatal}},f_{\textup{eco}})$	MAP-A
Case 3	$\textbf{F}_{\text{eff}}=(f_{\textup{fuel}},f_{\textup{distance}})$	$\textbf{F}_{\text{safe}}=(f_{\textup{fatal}},f_{\textup{eco}})$	MAP-A
Case 4	$\textbf{F}_{\text{eff}}=(f_{\textup{length}},f_{\textup{distance}})$	$\textbf{F}_{\text{safe}}=(f_{\textup{fatal}},f_{\textup{noise}})$	MAP-A
Case 5	$\textbf{F}_{\text{eff}}=(f_{\textup{length}}+f_{\textup{height}},f_{\textup{distance}})$	$\textbf{F}_{\text{safe}}=(f_{\textup{fatal}},f_{\textup{noise}})$	MAP-A
Case 6	$\textbf{F}_{\text{eff}}=(f_{\textup{fuel}},f_{\textup{distance}})$	$\textbf{F}_{\text{safe}}=(f_{\textup{fatal}},f_{\textup{noise}})$	MAP-A

TABLE VII: Case design

Fig. 22: Population Density and Traffic Density of MAP-A

Fig. 24: Building height distribution of MAP-A

Fig. 25: Population Density and Traffic Density of MAP-B

Fig. 27: Building height distribution of MAP-B

Fig. 28: The population distribution (pre-stage) in solving Case 1 using existing multiparty immune algorithms (such as BPNNIA, BPHEIA and BPAIMA) is shown when the number of activations is set to 20. The Case 1 problem is given in Table VII .

Fig. 29: The population distribution (pre-stage) in solving Case 1 using existing multiparty immune algorithms is shown when the number of activations is set to 50. The Case 1 problem is given in Table VII .

Fig. 30: The population distribution (pre-stage) in solving Case 1 using existing multiparty immune algorithms is shown when the number of activations is set to 90. The Case 1 problem is given in Table VII .

Fig. 31: The population distribution (mid-stage) in solving Case 1 using existing multiparty immune algorithms is shown when the number of activations is set to 20. The Case 1 problem is given in Table VII .

Fig. 32: Visualization of the results of solving Cases 1-6

Fig. 33: Visualization of the results of solving Cases 7-12

Problems	Algorithms
Problems	NSGA-II	NSGA-III	MPNDS	MPNDS2	BPAIMA	MPIA-BASE	MPIA-A	MPIA-B	MPIA
Case 1	2.98E-01	3.87E-01	4.65E-01	4.78E-01	5.24E-01	5.41E-01	5.86E-01(+)	5.71E-01(+)	5.91E-01(+)
Case 2	3.03E-01	4.39E-01	4.66E-01	4.73E-01	5.26E-01	5.44E-01	5.85E-01(+)	5.89E-01(+)	5.85E-01(+)
Case 3	3.25E-01	4.24E-01	4.74E-01	4.82E-01	5.32E-01	5.68E-01	5.92E-01(+)	5.60E-01(+)	5.90E-01(+)
Case 4	2.41E-01	4.19E-01	4.30E-01	4.64E-01	5.04E-01	5.14E-01	5.74E-01(+)	5.24E-01(+)	5.57E-01(+)
Case 5	2.33E-01	4.60E-01	4.27E-01	4.68E-01	5.16E-01	4.80E-01	5.35E-01(+)	5.14E-01(+)	5.36E-01(+)

TABLE VIII:

sumHV

Metric of Different Algorithms in BPUAV-PP Problem Case 1 - Case 12

Problems	Algorithms
Problems	NSGA-II	NSGA-III	MPNDS	MPNDS2	BPHEIA	BPNNIA	BPAIMA	MPIA-BASE	MPIA-A	MPIA-B	MPIA
MPMOP1	9.26E-03	Inf	1.59E-05	1.43E-05	4.15E-05	3.96E-05	6.19E-05	5.43E-05	3.07E-05(+)	5.49E-05(-)	2.89E-05(+)
MPMOP2	3.90E-02	3.75E-01	1.28E-02	1.52E-02	3.59E-02	3.28E-02	3.08E-05	2.65E-05	2.32E-05(+)	2.33E-05(+)	2.37E-05(+)
MPMOP3	2.25E-01	2.13E-01	2.27E-01	2.10E-01	1.82E-01	2.06E-01	7.86E-02	7.26E-02	7.28E-02(-)	7.01E-02(+)	6.84E-02(+)
MPMOP4	1.40E+00	1.17E+00	4.88E-02	5.18E-02	5.85E-02	5.96E-02	3.03E-02	3.25E-02	3.18E-02(+)	3.19E-02(+)	3.25E-02(+)
MPMOP5	3.56E-01	Inf	4.00E-02	4.03E-02	4.31E-02	4.34E-02	3.58E-02	3.93E-02	3.73E-02(+)	3.74E-02(+)	3.49E-02(+)

TABLE IX: MPIGD Metric of Different Algorithms in MPMOP 1 - MPMOP 12

Multi-Party Multi-Objective Optimization

See all 11 papers

Multi-Party Multi-Objective Optimization as Consensus Search: Runtime Analysis of Cross-Party Recombination
May 17, 2026Xiaolei Fang, Peilan Xu, Wenjian LuoMulti-Party Multi-Objective Optimization Evolutionary Optimization
School of Artificial Intelligence, Nanjing University of Information Science and Technology, Nanjing 210044, China · Guangdong Provincial Key Laboratory of Novel Security Intelligence Technologies, Institute of Cyberspace Security, School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen 518055, China.
Evolutionary Biparty Multiobjective UAV Path Planning: Problems and Empirical Comparisons
Mar 23, 2026Kesheng Chen, Wenjian Luo, Xin Lin +2UAV Trajectory Optimization Multi-Objective Motion Planning
Guangdong Provincial Key Laboratory of Novel Security Intelligence Technologies, School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen 518055, China · Peng Cheng Laboratory, Shenzhen 518055, China · School of Artificial Intelligence/School of Future Technology, Nanjing University of Information Science and Technology, Nanjing 210044, China
Fairness-Aware Performance Evaluation for Multi-Party Multi-Objective Optimization
Jan 30, 2026Zifan Zhao, Peilan Xu, Wenjian LuoMulti-Party Multi-Objective Optimization Cooperative Game Theory
School of Artificial Intelligence, Nanjing University of Information Science and Technology, Nanjing 210044, China · Guangdong Provincial Key Laboratory of Novel Security Intelligence Technologies, Institute of Cyberspace Security, School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen 518055, China

May 17, 2026J/K move · Enter open · S save

Multi-Party Multi-Objective Optimization as Consensus Search: Runtime Analysis of Cross-Party Recombination

Xiaolei Fang, Peilan Xu, Wenjian Luo

School of Artificial Intelligence, Nanjing University of Information Science and Technology, Nanjing 210044, China · Guangdong Provincial Key Laboratory of Novel Security Intelligence Technologies, Institute of Cyberspace Security, School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen 518055, China.

Multi-Party Multi-Objective Optimization Evolutionary Optimization Multi-Objective Evolutionary Optimization Runtime Analysis of Evolutionary Algorithms Multi-Objective Optimization

Open paper AskPDF arXiv

Multi-party multi-objective optimization problems (MPMOPs) require consensus among autonomous decision makers and therefore differ from flattened many-objective formulations. Existing runtime theory for multi-objective evolutionary algorithms is largely tailored to single-party Pareto-front approximation and does not directly explain common-solution search in MPMOPs. We investigate cross-party recombination in two representative settings. On MP-JCG, a pseudo-Boolean benchmark with an explicit gap region, we prove that a payoff-guided mutation baseline faces a gap-crossing bottleneck requiring

Θ(n^2)

expected fitness evaluations. In contrast, an analytical CPR-NSGA-II variant discovers both common Pareto-optimal solutions in

O(n\log n)

expected evaluations by directly assembling complementary prefix and suffix templates distributed across party populations. Comparing this with the flattened four-objective formulation F-JCG, our full-front coverage analysis illustrates the additional coverage burden introduced by flattening. For BPBOMST, the bi-party, two-objective-per-party specialization of the multi-party multi-objective minimum spanning tree problem, we develop a layered support-cover analysis. For each common Pareto objective vector, the symmetric average projection induces an auxiliary bi-objective MST instance, and suitable support representatives yield a

2λ

-common approximation cover with

λ\in[1,2]

. We further derive an instance-parameterized expected runtime bound for a representative-pool CPR-NSGA-II variant using edge-union recombination and uniform repair. This bound separates the effects of local auxiliary-front filling, cross-party recombination shortcuts, and edge-union repair ambiguity.

Abstract

Multi-Party Multi-Objective Optimization

Explore similar work

Multi-Party Multi-Objective Optimization as Consensus Search: Runtime Analysis of Cross-Party Recombination

Evolutionary Biparty Multiobjective UAV Path Planning: Problems and Empirical Comparisons

Fairness-Aware Performance Evaluation for Multi-Party Multi-Objective Optimization