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

Volume 10, Issue 4, pp 2115--2132 http://dx.doi.org/10.22436/jnsa.010.04.65

Publication Date: April 20, 2017 Submission Date: December 31, 2016

Download PDF

Download XML

• Export citations
  • CITATIONS & REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • ARTICLE CITATION
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)

• 1934 Downloads
• 3567 Views

Authors

Tao Zhang - School of Information and Mathematics, Yangtze University, Jingzhou 434023, China. Zhong Chen - School of Information and Mathematics, Yangtze University, Jingzhou 434023, China. Jiawei Chen - School of Mathematics and Statistics, Southwest University, Chongqing 400715, China.

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.

Share and Cite

Keywords

• Complex bilevel programming
• cooperative coevolutionary particle swarm optimization
• watershed water trading decision making problems
• elite strategy.

MSC

•  65K10
•  90C25

References

• [1] E. Aiyoshi, K. Shimuzu, A solution method for the static constrained Stackelberg problem via penalty method, IEEE Trans. Automat. Control, 29 (1984), 1112–1114.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [2] M. A. Amouzegar, A global optimization method for nonlinear bilevel programming problems, IEEE Trans. Systems Man Cybernet., 29 (1999), 771–777.
  • View Article
  • Google Scholar


• [3] J. F. Bard, An algorithm for solving the general bilevel programming problem, Math. Oper. Res., 8 (1983), 260–272.
  • View Article
  • MathSciNet
  • Google Scholar


• [4] J. F. Bard, Some properties of the bilevel programming problem, J. Optim. Theory Appl., 68 (1991), 371–378.
  • View Article
  • MathSciNet
  • Google Scholar


• [5] J. F. Bard, Practical bilevel optimization, Algorithms and applications, Nonconvex Optimization and its Applications, Kluwer Academic Publishers, Dordrecht (1998)
  • Google Scholar


• [6] J. F. Bard, J. E. Falk, An explicit solution to the multilevel programming problem, Mathematical programming with parameters and multilevel constraints, Comput. Oper. Res., 9 (1982), 77–100.
  • View Article
  • MathSciNet
  • Google Scholar


• [7] O. Ben-Ayed, C. E. Blair, Computational difficulties of bilevel linear programming, Oper. Res., 38 (1990), 556–560.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [8] H. I. Calvete, C. Gaté, P. M. Mateo, A new approach for solving linear bilevel problems using genetic algorithms, European J. Oper. Res., 188 (2008), 14–28.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [9] H. I. Calvete, C. Galé, M. J. Oliveros, Bilevel model for productiondistribution planning solved by using ant colony optimization, Comput. Oper. Res., 38 (2011), 320–327.
  • View Article
  • Google Scholar
  • MATH


• [10] J.-W. Chen, Q. H Ansari, Y.-C. Liou, J.-C. Yao, A proximal point algorithm based on decomposition method for cone constrained multiobjective optimization problems, Comput. Optim. Appl., 65 (2016), 289–308.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [11] B. Colson, P. Marcotte, G. Savard, Bilevel programming: a survey, 4OR, 3 (2005), 87–107.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [12] B. Colson, P. Marcotte, G. Savard, An overview of bilevel optimization, Ann. Oper. Res., 153 (2007), 235–256.
  • View Article
  • MathSciNet
  • Google Scholar


• [13] K. Deb, S. Agrawalan, A. Pratap, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6 (2002), 182–197.
  • View Article
  • Google Scholar


• [14] S. Dempe, Foundations of bilevel programming, Nonconvex Optimization and its Applications, Kluwer Academic Publishers, Dordrecht (2002)
  • MathSciNet
  • Google Scholar
  • MATH


• [15] S. Dempe, Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints, Optimization, 52 (2003), 333–359.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [16] T. A. Edmunds, J. F. Bard, Algorithms for nonlinear bilevel mathematical programs, IEEE Trans. Systems Man Cybernet., 21 (1991), 83–89.
  • View Article
  • MathSciNet
  • Google Scholar


• [17] J. B. Etoa Etoa, Solving quadratic convex bilevel programming problems using a smoothing method, Appl. Math. Comput., 217 (2011), 6680–6690.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [18] J. E. Falk, J.-M. Liu, On bilevel programming, I, General nonlinear cases, Math. Programming, 70 (1995), 47–72.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [19] Y. Gao, G.-Q. Zhang, J. Lu, H.-M. Wee, Particle swarm optimization for bi-level pricing problems in supply chains, J. Global Optim., 51 (2011), 245–254.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [20] Y. Gao, G.-Q. Zhang, J. Ma, J. Lu, A \(\lambda\)-cut and goal-programming-based algorithm for fuzzy-linear multiple-objective bilevel optimization, IEEE Trans. Fuzzy Syst., 18 (2010), 1–13.
  • View Article
  • Google Scholar


• [21] M. Gendreau, P. Marcotte, G. Savard, A hybrid tabu-ascent algorithm for the linear bilevel programming problem, Hierarchical and bilevel programming, J. Global Optim., 8 (1996), 217–233.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [22] S. R. Hejazi, A. Memariani, G. Jahanshahloo, M. M. Sepehri, Linear bilevel programming solution by genetic algorithm, Comput. Oper. Res., 29 (2001), 1913–1925.
  • View Article
  • MathSciNet
  • Google Scholar


• [23] Y. Ishizuka, E. Aiyoshi, Double penalty method for bilevel optimization problems, Hierarchical optimization, Ann. Oper. Res., 34 (1992), 73–88.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [24] R. G. Jeroslow, The polynomial hierarchy and a simple model for competitive analysis, Math. Programming, 32 (1985), 146–164.
  • View Article
  • MathSciNet
  • Google Scholar


• [25] Y. Jiang, X.-Y. Li, C.-C. Hang, X.-N. Wu, Application of particle swarm optimization based on CHKS smoothing function for solving nonlinear bilevel programming problem, Appl. Math. Comput., 129 (2013), 4332–4339.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [26] J. Kennedy, R. C. Eberhart, Y.-H. Shi, Swarm intelligence, Morgan Kaufmann Publishers, San Francisco, CA (2001)
  • Google Scholar


• [27] R. J. Kuo, Y. S. Han, A hybrid of genetic algorithm and particle swarm optimization for solving bi-level linear programming problem—a case study on supply chain model, Appl. Math. Model., 35 (2011), 3905–3917.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [28] R. J. Kuo, C. C. Huang, Application of particle swarm optimization algorithm for solving bi-level linear programming problem, Comput. Math. Appl., 58 (2009), 678–685.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [29] K.-M. Lan, U.-P. Wen, H.-S. Shih, E. S. Lee, A hybrid neural network approach to bilevel programming problems, Appl. Math. Lett., 20 (2007), 880–884.
  • View Article
  • MathSciNet
  • Google Scholar


• [30] X.-Y. Li, P. Tian, X.-P. Min, A hierarchical particle swarm optimization for solving bilevel programming problems, Proceedings of the 8th International Conference on Artificial Intelligence and Soft Computing (ICAISC), Poland, Lecture Notes in Computer Science, 2016 (2006), 1169–1178.
  • View Article
  • Google Scholar


• [31] Y.-B. Lv, T.-S. Hu, G.-M. Wang, Z.-P. Wan, A penalty function method based on Kuhn-Tucker condition for solving linear bilevel programming, Appl. Math. Comput., 188 (2007), 808–813.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [32] Y.-B. Lv, T.-S. Hu, G.-M.Wang, Z.-P.Wan, A neural network approach for solving nonlinear bilevel programming problem, Comput. Math. Appl., 55 (2008), 2823–2829.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [33] R. Mathieu, L. Pittard, G. Anandalingam, Genetic algorithm based approach to bi-level linear programming, RAIRO Rech. Opér., 28 (1994), 1–21.
  • View Article
  • MathSciNet
  • Google Scholar


• [34] A. Migdalas (Ed.), P. M. Pardalos (Ed.), P. Värbrand (Ed.), Multilevel optimization: algorithms and applications, Nonconvex Optimization and its Applications, Kluwer Academic Publishers, Dordrecht (1998)
  • View Article
  • MathSciNet
  • Google Scholar


• [35] J. Rajesh, K. Gupta, H. S. Kusumakar, V. K. Jayaraman, B. D. Kulkarni, A tabu search based approach for solving a class of bilevel programming problems in chemical engineering, J. Heuristics, 9 (2003), 307–319.
  • View Article
  • Google Scholar


• [36] K. H. Sahin, A. R. Ciric, A dual temperature simulated annealing approach for solving bilevel programming problems, Comput. Chem. Eng., 23 (1998), 11–25.
  • View Article
  • Google Scholar


• [37] G. Savard, J. Gauvin, The steepest descent direction for the nonlinear bilevel programming problem, Oper. Res. Lett., 15 (1994), 265–272.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [38] K. Shimizu, E. Aiyoshi, A new computational method for Stackelberg and min-max problems by use of a penalty method, IEEE Trans. Automat. Control, 26 (1981), 460–466.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [39] K. Shimizu, Y. Ishizuka, J. F. Bard, Nondifferentiable and two-level mathematical programming, Kluwer Academic Publishers, Boston, MA (1997)
  • View Article
  • MathSciNet
  • MATH


• [40] A. Sinha, P. Malo, K. Deb, Test problem construction for single-objective bilevel optimization, Evol. Comput., 22 (2014), 439–477.
  • View Article
  • Google Scholar


• [41] L. N. Vicente, P. H. Calamai, Bilevel and multilevel programming: a bibliography review, J. Global Optim., 5 (1994), 291–306.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [42] L. Vicente, G. Savard, J. Júdice, Descent approaches for quadratic bilevel programming, J. Optim. Theory Appl., 81 (1994), 379–399.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [43] Z.-P. Wan, G.-M. Wang, B. Sun, A hybrid intelligent algorithm by combining particle swarm optimization with chaos searching technique for solving nonlinear bilevel programming problems, Swarm Evol. Comput., 8 (2013), 26–32.
  • View Article
  • Google Scholar


• [44] Y.-P. Wang, Y.-C. Jiao, H. Li, An evolutionary algorithm for solving nonlinear bilevel programming based on a new constraint-handling scheme, IEEE Trans. Systems Man Cybernet., 35 (2005), 221–232.
  • View Article
  • Google Scholar


• [45] G.-M. Wang, X.-J. Wang, Z.-P. Wan, S.-H. Jia, An adaptive genetic algorithm for solving bilevel linear programming problem, Appl. Math. Mech. (English Ed.), 28 (2007), 1605–1612.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [46] U. P. Wen, A. D. Huang, A simple tabu search method to solve the mixed-integer linear bilevel programming problem, European J. Oper. Res., 88 (1996), 563–571.
  • View Article
  • Google Scholar
  • MATH


• [47] C.-Y. Wu, Y.-Z. Zhao, Watershed water trading decision-making model based on bi-level programming, Oper. Res. Manag. Sci., 20 (2011), 30–37.
  • Google Scholar


• [48] S. B. Yaakob, J. Watada, A hybrid intelligent algorithm for solving the bilevel programming models, Knowledge-Based Intell. Inf. Eng. Syst., 6277 (2010), 485–494.
  • View Article
  • Google Scholar


• [49] S. B. Yaakob, J. Watada, Double-layered hybrid neural network approach for solving mixed integer quadratic bilevel problems, Integr. Uncertain. Manag. Appl., 68 (2010), 221–230.
  • View Article
  • Google Scholar
  • MATH


• [50] G.-Q. Zhang, G.-L. Zhang, Y. Gao, J. Lu, Competitive strategic bidding optimization in electricity markets using bilevel programming and swarm technique, IEEE Trans. Ind. Electron., 58 (2011), 2138–2146.
  • View Article
  • Google Scholar