TL;DR
This paper introduces MPIA, a novel immune algorithm designed to tackle multiparty multiobjective optimization problems (MPMOPs), where multiple decision-makers have conflicting objectives. MPIA improves search efficiency with an "inter-party guided crossover" and enhances population diversity using an "adaptive activation strategy" based on a new "multiparty cover metric," outperforming existing methods on synthetic and real-world UAV path planning problems.
What Problem Does This Paper Address?
Many real-world optimization problems involve multiple stakeholders, each with their own set of objectives that might conflict with others. These are known as multiparty multiobjective optimization problems (MPMOPs). Traditional multiobjective optimization algorithms (MOEAs) struggle with MPMOPs because they are designed for a single decision-maker and cannot effectively balance the diverse needs of multiple parties. Existing MPMOP algorithms, while an improvement, often fail to adequately leverage the information available from different decision-makers' perspectives to guide the search process or maintain sufficient diversity across all objectives. This can lead to suboptimal solutions that don't satisfy all stakeholders. The paper specifically highlights challenges in efficiently searching for solutions that satisfy all parties and maintaining population diversity across these diverse objectives.
Methods
The proposed algorithm, MPIA (Multiparty Immune Algorithm), introduces two key novel strategies:
- Inter-Party Guided Crossover: Inspired by transfer learning in dynamic optimization, this strategy uses the non-dominated sorting ranks from different decision-makers' perspectives to intelligently select individuals for crossover. This helps guide the search towards regions that are promising for multiple parties simultaneously.
- Adaptive Activation Strategy with Multiparty Cover Metric (MCM): Traditional immune algorithms use a fixed number of "activated" individuals for cloning. MPIA introduces the MCM, a new metric that quantifies the diversity of a selected set of individuals across all decision-makers' objective spaces. An adaptive activation strategy then uses MCM to dynamically determine the optimal number of individuals to activate, ensuring better population diversity and preventing the loss of valuable individuals that might not be part of the common Pareto front but are important for individual decision-makers.
MPIA also incorporates standard immune algorithm components like cloning and uses differential evolution (DE) operators and a simulated binary crossover (SBX) operator, with a novel adaptive operator selection mechanism.
Datasets
The paper evaluates MPIA on two types of datasets:
- Synthetic Multiparty Multiobjective Benchmarks: Specifically, MPMOP1-MPMOP11, derived from the CEC'2018 Competition on Dynamic Multiobjective Optimization.
- Biparty Multiobjective UAV Path Planning (BPUAV-PP) Problems: These are real-world problems that involve two decision-makers (efficiency and safety) with multiple conflicting objectives. The paper uses two maps, MAP-A and MAP-B, and extends existing BPUAV-PP problem formulations to create 12 distinct cases for testing.
Key Insights and Ideas
- Leveraging Inter-DM Information is Crucial: The success of MPIA hinges on its ability to use information from one decision-maker's objectives to guide the search for solutions that benefit others, a concept often overlooked by simpler MOEAs.
- Diversity is Not One-Size-Fits-All: Simply focusing on the common Pareto front for all DMs can lead to a loss of diversity from individual DM perspectives. The MCM metric and adaptive activation strategy are key to addressing this.
- Immune Algorithms are Well-Suited for MPMOPs: By adapting immune algorithm principles with novel strategies, MPIA demonstrates strong performance, suggesting this framework can be highly effective for complex multi-stakeholder optimization.
- Adaptive Strategies Outperform Fixed Ones: The adaptive activation strategy, driven by the MCM, shows a clear advantage over fixed-size activation in maintaining population diversity and improving overall performance.
Key Results
- MPIA consistently outperformed or was competitive with state-of-the-art MPMOEAs (including NSGA-II, NSGA-III, MPNDS, MPNDS2, BPNNIA, BPHEIA, BPAIMA) on both synthetic MPMOPs and the complex BPUAV-PP problems.
- On synthetic MPMOPs, MPIA achieved the smallest MPIGD metric in five out of eleven problems and was competitive in others.
- For BPUAV-PP problems, MPIA achieved the best sumHV metric in most cases, indicating superior fairness and convergence.
- Ablation studies showed that both the inter-party guided crossover and the adaptive activation strategy individually contributed to performance improvements over a baseline algorithm.
Limitations and Future Work
- Average Performance on Simpler Problems: MPIA showed only average performance on some simpler MPMOPs with fewer decision variables, suggesting that for less complex problems, existing MPMOEAs might suffice.
- Potential for Convergence Hindrance: While adaptive strategies are beneficial, excessively large activation sets could potentially hinder convergence. The paper addresses this by setting a threshold for MCM.
- Future Work: The authors plan to further investigate the theoretical aspects of their algorithm and explore its application to more real-world scenarios.
Summary updated