An improved simulated annealing algorithm for bilevel multiobjective programming problems with application

Volume 9, Issue 6, pp 3672--3685 http://dx.doi.org/10.22436/jnsa.009.06.19

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)

• 1552 Downloads
• 2554 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. Yue Zheng - School of Management, Huaibei Normal University, Huaibei 235000, China. Jiawei Chen - School of Mathematics and Statistics, Southwest University, Chongqing 400715, China. - College of Computer Science, Chongqing University, Chongqing 400044, China.

Abstract

In this paper, an improved simulated annealing (SA) optimization algorithm is proposed for solving bilevel multiobjective programming problem (BLMPP). The improved SA algorithm uses a group of points in its operation instead of the classical point-by-point approach, and the rule for accepting a candidate solution that depends on a dominance based energy function is adopted in this algorithm. For BLMPP, the proposed method directly simulates the decision process of bilevel programming, which is different from most traditional algorithms designed for specific versions or based on specific assumptions. Finally, we present six different test problems to measure and evaluate the proposed algorithm, including low dimension and high dimension BLMPPs. The experimental results show that the proposed algorithm is a feasible and efficient method for solving BLMPPs.

Share and Cite

Keywords

• Bilevel multiobjective programming
• simulated annealing algorithm
• Pareto optimal solution
• elite strategy.

MSC

•  65K10
•  90C25

References

• [1] M. Abo-Sinna, I. Baky, Interactive balance spaces approach for solving multi-level multi-objective programming problems, Inform. Sci., 177 (2007), 3397-3410.


• [2] S. Bandyopadhyay, S. Saha, U. Maulik, K. Deb, A simulated annealing based multi-objective optimization algorithm: AMOSA, IEEE Trans. Evolutionary Comput., 12 (2008), 269-283.


• [3] J. F. Bard, Practical bilevel optimization: Algorithms and applications, Kluwer Academic, Dordrecht (1998)


• [4] J. 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. Opti. Appl., 2016 (2016), 20 pages.


• [5] J. Chen, Y. C. Liou, C. F. Wen, Bilevel vector pesudomonotone equilibrium problem: duality and existence, J. Nonlinear Convex Anal., 16 (2015), 1293-1303.


• [6] B. Colson, P. Marcotte, G. Savard , Bilevel programming: A survey, A Quarterly J. Oper. Res., 3 (2005), 87-107.


• [7] B. Colson, P. Marcotte, G. Savard, An overview of bilevel optimization, Ann. Oper. Res., 153 (2007), 235-256.


• [8] K. Deb, Multi-Objective Optimization using evolutionary algorithms, IEEE Trans. Evolutionary Comput., 6 (2002), 182-197.


• [9] K. Deb, S. Agrawalan, A. Pratap, T. Meyarivan, A fast and elitist multi-objective genetic algorithm: NSGA-II., IEEE Trans. Evolutionary Comput., 6 (2002), 182-197.


• [10] K. Deb, A. Sinha, Constructing test problems for bilevel evolutionary multi-objective optimization, IEEE Congr. Evolutionary Comput., (2009), 1153-1160.


• [11] K. Deb, A. Sinha, Solving bilevel multiobjective optimization problems using evolutionary algorithms, Lecture notes in computer science, 5467 (2009), 110-124.


• [12] K. Deb, A. Sinha, An evolutionary approach for bilevel multiobjective problems, Commun. Comput. Inform. Sci., 35 (2009), 17-24.


• [13] K. Deb, A. Sinha, An eficient and accurate solution methodology for bilevel multi-objective programming problems using a hybrid evolutionary local-search algorithm, Evolutionary Comput., 18 (2010), 403-449.


• [14] S. Dempe, Foundations of bilevel programming, Non-convex optimization and its applications series, Kluwer Academic, Dordrecht (2002)


• [15] S. Dempe, Annotated bibliography on bilevel programming and mathematical problems with equilibrium constraints, Optim, 52 (2003), 333-359.


• [16] G. Eichfelder , Solving nonlinear multi-objective bi-level optimization problems with coupled upper level constraints, Technical Report Preprint No. 320, Preprint-Series of the Institute of Applied Mathematics, Univ. Erlangen- Nrnberg, Germany (2007)


• [17] G. Eichfelder, Multiobjective bilevel optimization, Math. Program., 123 (2010), 419-449.


• [18] Y. Gao, G. Zhang, J. Lu, H. Wee, Particle swarm optimization for bilevel pricing problems in supply chains, J. Global Optim., 51 (2011), 245-254.


• [19] H. S. Kemal, A. R. Ciric, A dual temperature simulated annealing approach for solving bilevel programming problems , Comput. Chem. Eng., 23 (1998), 11-25.


• [20] S. Kirkpatrick, C. Gelatt, M. Vecchi , Optimization by simulated annealing, Science, 220 (1983), 671-680.


• [21] R. J. Kuo, C. C. Huang , Application of particle swarm optimization algorithm for solving bilevel linear programming problem, Comput. Math. Appl., 58 (2009), 678-685.


• [22] Z. Q. Luo, J. S. Pang, D. Ralph, Mathematical programs with equilibrium constraints, Cambridge University Press, Cambridge (1996)


• [23] F. Maöli, Randomized heuristic for NP-hard problem, Advanced School on Stochastic in Combinatorial Optimization, World Sci. publishing, Singapore, (1987), 76-93.


• [24] I. Nishizaki, M. Sakawa, Stackelberg solutions to multiobjective two-level linear programming problems, J. Optim. Theory Appl., 103 (1999), 161-182.


• [25] V. Oduguwa, R. Roy , Bilevel optimization using genetic algorithm, Proc. 2002 IEEE International Conference on Artificial Intelligence Systems, (2002), 322-327.


• [26] X. Shi, H. Xia, Interactive bilevel multi-objective decision making, J. Oper. Res. Soc., 48 (1997), 943-949.


• [27] X. Shi, H. Xia, Model and interactive algorithm of bi-level multi-objective decision-making with multiple interconnected decision makers, J. Multi-criteria Decision Anal., 10 (2001), 27-34.


• [28] K. Shimizu, Y. Ishizuka, J. F. Bard, Non-differentiable and two-level mathematical programming, Kluwer Academic, Dordrecht (1997)


• [29] A. Sinha, Bilevel multi-objective optimization problem solving using progressively interactive EMO, Proceeding of the Sixth International Conference on Evolutionary Multi-criterion Optimization, (2011)


• [30] A. Sinha, K. Deb, Towards understanding evolutionary bilevel multiobjective optimization algorithm, Technical Report Kangal Report No. 2008006, Department of Mechanical Engineering, Indian Institute of Technology Kanpur, India (2008)


• [31] K. Smith, R. Everson, J. Fieldsend, Dominance measures for multi-objective simulated annealing, Proc. 2004 IEEE Congr. Evolutionary Comput. (CEC'04), (2004), 23-30.


• [32] B. Suman, P. Kumar, A survey of simulated annealing as a tool for single and multiobjective optimization, J. Oper. Res. Soc., 57 (2006), 1143-1160.


• [33] L. N. Vicente, P. H. Calamai , Bilevel and multilevel programming: A bibliography review, J. Global Optim., 5 (1994), 1-23.


• [34] L. N. Vicente, P. H. Calamai, Bilevel and multilevel programming: A bibliography review, J. Global Optim., 5 (2004), 291-306.


• [35] Y. Wang, Y. C. Jiao, H. Li , An evolutionary algorithm for solving nonlinear bilevel programming based on a new constraint-handling scheme, IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 35 (2005), 221-232.


• [36] G. Wang, Z. Wan, X. Wang, Bibliography on bilevel programming, Adv. Math. (in Chinese), 36 (2007), 513-529.


• [37] U. P. Wen, S. T. Hsu, Linear bilevel programming problems-A review, J. Oper. Res. Soc., 42 (1991), 125-133.


• [38] C. Y. Wu, Y. Z. Zhao , Watershed water trading decision-making model based on bilevel programming, Oper. Res. Management Sci. (in Chinese), 20 (2011), 30-37.


• [39] R. Xiang, G. Y. Lu, D. He, Simulated annealing algorithm for solving a bi-level optimization model on high-speed railway station location, 2010 Third International Conference on Inform. Comput., (2010), 159-162.


• [40] R. L. Yang, J. F. Gu, An eficient simulated annealing algorithm for global optimization, Syst. Eng.-Theory Practice (in Chinese), 17 (1997), 30-36.


• [41] Y. Yin , Genetic algorithm based approach for bilevel programming models, J. Trans. Eng., 126 (2000), 115-120.


• [42] T. Zhang, T. S. Hu, X. N. Guo, Z. Cheng, Y. Zheng, Solving high dimensional bilevel multiobjective programming problem using a hybrid particle swarm optimization algorithm with crossover operator, Knowledge-Based Sys., 53 (2013), 13-19.


• [43] G. Zhang, J. Lu, Fuzzy bilevel programming with multiple objectives and cooperative multiple followers, J. Global Optim., 47 (2010), 403-419.