Abstract
Complex bilevel programming problems (CBLP) involve hierarchical decision-making where both upper and lower levels feature high-dimensional variables. Traditional evolutionary algorithms often suffer from premature convergence and high computational costs in these scenarios. This paper proposes a Cooperative Coevolutionary Particle Swarm Optimization (CCPSO) algorithm. By decomposing the problem into interacting "species" and employing a stagnation detection strategy, the CCPSO enhances global convergence and efficiency. The algorithm's performance is validated through synthetic benchmarks and a practical watershed water trading case study, demonstrating significant improvements over existing methods.
Introduction
Bilevel programming (BLP) models hierarchical optimization where a "leader" at the upper level and a "follower" at the lower level interact. The leader's objective depends on the follower's optimal response. While standard BLPs are already NP-hard, Complex Bilevel Programming (CBLP) introduces high-dimensional decision variables, leading to the "curse of dimensionality." In such spaces, swarms often converge prematurely to local optima and become computationally prohibitive. The authors aim to bridge this gap by creating an algorithm that is both robust enough to find global optima and efficient enough for practical use.
Methodology
The proposed CCPSO addresses these challenges through three main mechanisms:
- Problem Decomposition: The $n$-dimensional decision vector is split into $n$ separate "species." Each species maintains its own population and evolves using standard PSO.
- Cooperative Evaluation: To assess an individual's fitness, it is combined with the best representatives from other species to form a complete solution vector. This "divide and conquer" strategy allows for more efficient exploration of high-dimensional landscapes.
- Stagnation Detection: If the best collaboration fails to improve significantly over a fixed window of generations, the stagnant species is reinitialized (retaining only the best member) to restore diversity and "kick" the swarm out of local optima.
Experimental Evaluation
The researchers evaluated their algorithm using two primary sources. First, a set of 12 scalable test problems (originally proposed by Sinha et al.) was used to test specific challenges like multi-modality and conflict between levels. Second, a practical case study involving a watershed water trading decision-making model was used to measure real-world utility.
Key Results and Insights
The CCPSO was compared against a state-of-the-art nested bilevel evolutionary algorithm, yielding several key findings:
- Efficiency Gains: In 5-dimensional tests, CCPSO required 2.7 to 5.01 times fewer upper-level function evaluations and 5.21 to 9.10 times fewer lower-level evaluations than the baseline.
- Scalability: As dimensions increased to 10, the baseline algorithm failed to solve several test problems entirely, whereas CCPSO maintained high accuracy and global convergence.
- Real-world Impact: In the watershed water trading application—optimizing water rights and emission volumes—CCPSO achieved a total profit of 59.0613, outperforming previous literature results (58.9783 and 54.4482).
Conclusion
The CCPSO framework effectively mitigates the curse of dimensionality in bilevel programming by maintaining evolutionary pressure and niche coverage. Future research will focus on improving constraint handling by utilizing near-feasible solutions and exploring parallel implementation to further reduce computational time for extremely high-dimensional problems.
Summary updated