An Evolutionary Algorithm Based on a New Decomposition Scheme for Nonlinear Bilevel Programming Problems

Hecheng LI, Yuping WANG

.

DOI: 10.4236/ijcns.2010.31013                

Abstract

In this paper, we focus on a class of nonlinear bilevel programming problems where the follower’s objective is a function of the linear expression of all variables, and the follower’s constraint functions are convex with respect to the follower’s variables. First, based on the features of the follower’s problem, we give a new decomposition scheme by which the follower’s optimal solution can be obtained easily. Then, to solve efficiently this class of problems by using evolutionary algorithm, novel evolutionary operators are designed by considering the best individuals and the diversity of individuals in the populations. Finally, based on these techniques, a new evolutionary algorithm is proposed. The numerical results on 20 test problems illustrate that the proposed algorithm is efficient and stable.

Keywords

Nonlinear Bilevel Programming, Decomposition Scheme, Evolutionary Algorithm, Optimal Solutions

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	B. Colson, P. Marcotte, and G. Savard, “Bilevel programming: A survey,” A Quarterly Journal of Operations Research (4OR), Vol. 3, pp. 87–107, 2005.
[2]	J. F. Bard, “Practical bilevel optimization,” The Netherlands: Kluwer Academic Publishers, 1998.
[3]	U. P. Wen and S. T. Hsu, “Linear bi-level programming problems-A review,” The Journal of the Operational Research Society, Vol. 42, pp. 125–133, 1991.
[4]	K.-M. Lan, U.-P. Wen, H.-S. Shih, et al., “A hybrid neural network approach to bilevel programming problems,” Applied Mathematics Letters, Vol. 20, pp. 880–884, 2007.
[5]	H. I. Calvete, C. Gale, and P. M. Mateo, “A new approach for solving linear bilevel problems using genetic algorithms,” European Journal of Operational Research, Vol. 188, pp. 14–28, 2008.
[6]	L. D. Muu and N. V. Quy, “A global optimization method for solving convex quadratic bilevel programming problems,” Journal of Global Optimization, Vol. 26, pp. 199–219, 2003.
[7]	D. L. Zhu, Q. Xua, and Z. H. Lin, “A homotopy methodfor solving bilevel programming problem,” Nonlinear Analysis, Vol. 57, pp. 917–928, 2004.
[8]	H. Tuy, A. Migdalas, and N. T. Hoai-Phuong, “A novel approach to bilevel nonlinear programming,” Journal of Global Optimization, Vol. 38, pp. 527–554, 2007.
[9]	H. I. Calvete and C. Gale, “On the quasiconcave bilevel programming problem,” Journal of Optimization Theory and Applications, Vol. 98, pp. 613–622, 1998.
[10]	Y. P. Wang, Y. C. Jiao, and H. Li, “An evolutionary algorithm for solving nonlinear bilevel programming based on a new constraint - handling scheme,” IEEE Trans. on Systems, Man, and Cybernetics-Part C, Vol. 35, pp. 221– 232, 2005.
[11]	H. C. Li and Y. P. Wang, “A hybrid genetic algorithm for solving a class of nonlinear bilevel programming problems,” Proceedings of Simulated Evolution and Learning- 6th International Conference, SEAL, pp. 408–415, 2006.
[12]	K. Shimizu and E. Aiyoshi, “A new computational method for Stackelberg and minmax problems by use of a penalty method,” IEEE Transactions on Automatic Control, Vol. 26, pp. 460–466, 1998.
[13]	E. Aiyoshi and K. Shimizu, “A solution method for the static constrained Stackelberg problem via penalty method,” IEEE Transactions on Automatic Control, Vol. AC-29 (12), pp. 1111–1114, 1984.
[14]	B. Colson, P. Marcotte, and G. Savard, “A trust-region method for nonlinear bilevel programming: algorithm & computational experience,” Computational Optimization and Applications, Vol. 30, pp. 211–227, 2005.
[15]	V. Oduguwa and R. Roy, “Bilevel optimization using genetic algorithm,” Proceedings of IEEE International Conference on Artificial Intelligence Systems, pp. 123– 128, 2002.
[16]	B. D. Liu, “Stackelberg-Nash equilibrium for mutilevel programming with multiple followers using genetic algorithms,” Computer mathematics Application, Vol. 36, No. 7, pp. 79–89, 1998.
[17]	X. B. Zhu, Q. Yu, and X. J. Wang, “A hybrid differential evolution algorithm for solving nonlinear bilevel programming with linear constraints,” Proceedings of 5th IEEE International Conference on Cognitive Informatics (ICCI’06), pp. 126–131, 2006.
[18]	J. Rajesh, K. Gupta, and H. Shankar, et al., “A tabu search based approach for solving a class of bilevel programming problems in chemical engineering,” Journal of Heuristics, Vol. 9, pp. 307–319, 2003.
[19]	B. V. Sheela and P. Ramamoorthy, “SWIFT-S new constraines optimization technique,” Computer Methods in Applied Mechanics and Engineering, Vol. 6, pp. 309–318, 1975.