# A Nested Differential Evolution Based Algorithm for Solving Multi-objective Bilevel Optimization Problems

• Md Monjurul Islam
• Hemant Kumar Singh
• Tapabrata Ray
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 9592)

## Abstract

Bilevel optimization is a challenging class of problems, with applicability in several domains such as transportation, economics and engineering. In a bilevel problem, the aim is to identify the optimum solution(s) of an upper level (“leader”) problem, subject to optimality of a corresponding lower level (“follower”) problem. Most of the studies reported in the literature have focussed on single-objective bilevel problems, wherein both the levels contain only one objective. Several nested algorithms have been proposed in the literature to solve single objective problems, which have been subsequently enhanced through hybridization with local search in order to improve computational efficiency. The handful of algorithms used for multi-objective algorithms so far have used additional enhancements such as use of scalarization, sub-populations or hybridization. However, interestingly, unlike single-objective problems, the performance of a simple nested evolutionary algorithm has not been reported for multi-objective bilevel problems. In this paper, we attempt to address this gap by designing an algorithm which uses differential evolution at both levels. Numerical experiments show that on popular benchmarks, the proposed algorithm exhibits competitive performance with respect to existing state-of-the-art methods.

## Keywords

Bilevel optimization Multi objective Evolutionary algorithms

## Notes

### Acknowledgment

The third author acknowledges support from Australian Research Council Future Fellowship.

## References

1. 1.
Bard, J.F., Falk, J.E.: An explicit solution to the multi-level programming problem. Comput. Oper. Res. 9(1), 77–100 (1982)
2. 2.
Carrasqueira, P., Alves, M.J., Antunes, C.H.: A bi-level Multiobjective PSO algorithm. In: Gaspar-Cunha, A., Henggeler Antunes, C., Coello, C.C. (eds.) EMO 2015. LNCS, vol. 9018, pp. 263–276. Springer, Heidelberg (2015)Google Scholar
3. 3.
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm:NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)
4. 4.
Deb, K., Sinha, A.: Solving bilevel multi-objective optimization problems using evolutionary algorithms. In: Ehrgott, M., Fonseca, C.M., Gandibleux, X., Hao, J.-K., Sevaux, M. (eds.) EMO 2009. LNCS, vol. 5467, pp. 110–124. Springer, Heidelberg (2009)
5. 5.
Deb, K., Sinha, A.: An efficient and accurate solution methodology for bilevel multi-objective programming problems using a hybrid evolutionary-local-search algorithm. Evol. Comput. 18(3), 403–449 (2010)
6. 6.
Dempe, S.: A simple algorithm for the-linear bilevel programming problem. Optimization 18(3), 373–385 (1987)
7. 7.
Eichfelder, G.: Multiobjective bilevel optimization. Math. Program. 123(2), 419–449 (2010)
8. 8.
Gong, W., Cai, Z., Ling, C.X., Li, C.: Enhanced differential evolution with adaptive strategies for numerical optimization. IEEE Trans. Syst. Man Cybern. Part B: Cybernetics 41(2), 397–413 (2011)
9. 9.
Hejazi, S.R., Memariani, A., Jahanshahloo, G., Sepehri, M.M.: Linear bilevel programming solution by genetic algorithm. Comput. Operat. Res. 29(13), 1913–1925 (2002)
10. 10.
Herskovits, J., Leontiev, A., Dias, G., Santos, G.: Contact shape optimization: a bilevel programming approach. Struct. Multi. Optim. 20(3), 214–221 (2000)
11. 11.
Islam, M.M., Singh, H.K., Ray, T.: A memetic algorithm for the solution of single objective bilevel optimization problems. In: IEEE Congress on Evolutionary Computation (CEC) (2015) (In press)Google Scholar
12. 12.
Kirjner-Neto, C., Polak, E., Der Kiureghian, A.: An outer approximations approach to reliability-based optimal design of structures. J. Optim. Theor. Appl. 98(1), 1–16 (1998)
13. 13.
Koh, A.: A metaheuristic framework for bi-level programming problems with multi-disciplinary applications. In: Talbi, E.-G., Brotcorne, L. (eds.) Metaheuristics for bi-level Optimization. SCI, vol. 482, pp. 153–187. Springer, Heidelberg (2013)
14. 14.
Kuo, R., Huang, C.: Application of particle swarm optimization algorithm for solving bi-level linear programming problem. Comput. Mathtt. Appl. 58(4), 678–685 (2009)
15. 15.
Legillon, F., Liefooghe, A., Talbi, E.: Cobra: a cooperative coevolutionary algorithm for bi-level optimization. In: IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. IEEE (2012)Google Scholar
16. 16.
Mathieu, R., Pittard, L., Anandalingam, G.: Genetic algorithm based approach to bi-level linear programming. RAIRO Rech. Opérationnelle 28(1), 1–21 (1994)
17. 17.
Migdalas, A.: Bilevel programming in traffic planning: models, methods and challenge. J. Glob. Optim. 7(4), 381–405 (1995)
18. 18.
Nishizaki, I., Sakawa, M.: Stackelberg solutions to multiobjective two-level linear programming problems. J. Optim. Theor. Appl. 103(1), 161–182 (1999)
19. 19.
Önal, H.: A modified simplex approach for solving bilevel linear programming problems. Eur. J. Oper. Res. 67(1), 126–135 (1993)
20. 20.
Shi, X., Xia, H.: Interactive bilevel multi-objective decision making. J. Oper. Res. Soc. 48(9), 943–949 (1997)
21. 21.
Shi, X., Xia, H.S.: Model and interactive algorithm of bi-level multi-objective decision-making with multiple interconnected decision makers. J. Multi-Criteria Decis. Anal. 10(1), 27–34 (2001)
22. 22.
Sinha, A., Malo, P., Deb, K.: An improved bilevel evolutionary algorithm based on quadratic approximations. In: IEEE Congress on Evolutionary Computation (CEC), pp. 1870–1877, July 2014Google Scholar
23. 23.
Sinha, A., Malo, P., Deb, K.: Efficient evolutionary algorithm for single-objective bilevel optimization (2013). arXiv preprint arXiv:1303.3901
24. 24.
Sinha, A., Malo, P., Deb, K.: Test problem construction for single-objective bilevel optimization. Evol. Comput. 22(3), 439–477 (2014)
25. 25.
Sinha, A., Malo, P., Frantsev, A., Deb, K.: Multi-objective stackelberg game between a regulating authority and a mining company: a case study in environmental economics. In: IEEE Congress on Evolutionary Computation (CEC), pp. 478–485. IEEE (2013)Google Scholar
26. 26.
von Stackelberg, H.: Theory of the Market Economy. Oxford University Press, New York (1952)Google Scholar
27. 27.
Sun, H., Gao, Z., Wu, J.: A bi-level programming model and solution algorithm for the location of logistics distribution centers. Appl. Math. Model. 32(4), 610–616 (2008)
28. 28.
Takahama, T., Sakai, S.: Constrained optimization by the $$\epsilon$$ constrained differential evolution with gradient-based mutation and feasible elites. In: 2006 IEEE Congress on Evolutionary Computation. CEC 2006, pp. 1–8. IEEE (2006)Google Scholar
29. 29.
Vicente, L., Savard, G., Júdice, J.: Descent approaches for quadratic bilevel programming. J. Optim. Theory Appl. 81(2), 379–399 (1994)
30. 30.
Wang, G.M., Wang, X.J., Wan, Z.P., Jia, S.H.: An adaptive genetic algorithm for solving bilevel linear programming problem. Appl. Math. Mech. 28, 1605–1612 (2007)
31. 31.
White, D.J., Anandalingam, G.: A penalty function approach for solving bi-level linear programs. J. Glob. Optim. 3(4), 397–419 (1993)
32. 32.
Yin, Y.: Multiobjective bilevel optimization for transportation planning and management problems. J. Adv. Transp. 36(1), 93–105 (2002)
33. 33.
Zhang, T., Hu, T., Guo, X., Chen, Z., Zheng, Y.: Solving high dimensional bilevel multiobjective programming problem using a hybrid particle swarm optimization algorithm with crossover operator. Knowl.-Based Syst. 53, 13–19 (2013)
34. 34.
Zhu, X., Yu, Q., Wang, X.: A hybrid differential evolution algorithm for solving nonlinear bilevel programming with linear constraints. In: Proceedings of 5th IEEE International Conference on Cognitive Informatics (ICCI06), pp. 126–131 (2006)Google Scholar
35. 35.
Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms - a comparative case study. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 292–301. Springer, Heidelberg (1998)

© Springer International Publishing Switzerland 2016

## Authors and Affiliations

• Md Monjurul Islam
• 1
• Hemant Kumar Singh
• 1
Email author
• Tapabrata Ray
• 1
1. 1.School of Engineering and Information TechnologyUniversity of New South WalesCanberraAustralia
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.7954320311546326, "perplexity": 23130.613826787147}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2019-18/segments/1555578721441.77/warc/CC-MAIN-20190425114058-20190425140058-00336.warc.gz"}