A cooperative coevolution PSO technique for complex bilevel programming problems and application to watershed water trading decision making problems

Tao Zhang, Zhong Chen, Jiawei ChenThe Journal of Nonlinear Sciences and Applications 2017 · DOI

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.
The cooperative coevolutionary framework illustrating how different species interact with a shared domain model for fitness evaluation.

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.

A subset of the test problems and their mathematical properties used to benchmark the CCPSO algorithm.

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

Abstract

The complex bilevel programming problem (CBLP) in this paper mainly refers to the optimistic BLP in which the highdimensional decision variables at both levels. A cooperative coevolutionary particle swarm optimization (CCPSO) is proposed for solving the (CBLP), in which the evolutionary paradigm can efficiently prevent the premature convergence of the swarm. Furthermore, the stagnation detection strategy in our algorithm can further accelerate the convergence speed. Finally, we use the test problems from the reference and practical example about watershed water trading decision-making problem to measure and evaluate the proposed algorithm. The presented results indicate that the proposed algorithm can effectively solve the complex bilevel programming problems.
BibTeX
@article{zhang2017cooperative,
  author = {Tao Zhang and Zhong Chen and Jiawei Chen},
  title = {{A cooperative coevolution PSO technique for complex bilevel programming problems and application to watershed water trading decision making problems}},
  journal = {The Journal of Nonlinear Sciences and Applications},
  year = {2017},
  doi = {10.22436/jnsa.010.04.65},
}
Figure