A genetic algorithm using a finite search space for solving nonlinear/linear fractional bilevel programming problems

详细信息    查看全文

• 作者：Hecheng Li
• 关键词：Bilevel programming ; Genetic algorithm ; Optimal solutions ; Bases
• 刊名：Annals of Operations Research
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：235
• 期：1
• 页码：543-558
• 全文大小：576 KB
• 参考文献：Abdou-Kandil, H., & Bertrand, P. (1987). Government-private sector relations as a stackelberg game: A degenerate case. Journal of Economic Dynamics and Control, 11, 513-17.CrossRef
  Andreani, R., Castro, S. L. C., Chela, J. L., Friedlande, A., & Santos, S. A. (2009). An inexact-restoration method for nonlinear bilevel programming problems. Computational Optimization and Applications, 43, 307-28.CrossRef
  Arroyo, J. M., & Galiana, F. D. (2009). On the solution of the bilevel programming formulation of the terrorist threat problem. IEEE Transactions on Power Systems, 20(2), 789-97.CrossRef
  B?ck, T. (1996). Evolutionary algorithms in theory and practice. Oxford: Oxford University Press.
  Bard, J. F. (1998). Practical bilevel optimization: Algorithms and applications. Dordrecht: Kluwer Academic Publishers.CrossRef
  Bard, J. F., Plummer, J. C., & Sourie, J. C. (2000). A bilevel programming approach to determining tax credits for biofuel production. European Journal of Operational Research, 120, 30-3.CrossRef
  Ben-Ayed, O., Boyce, D., & Blair, C. (1988). A general bilevel linear programming formulation of the network design problem. Transportation Research, 22B, 311-18.CrossRef
  Calvete, H. I., & Gale, C. (1998). On the quasiconcave bilevel programming problem. Journal of Optimization Theory and Applications, 98, 613-22.CrossRef
  Calvete, H. I., Gale, C., & Mateo, P. M. (2008). A new approach for solving linear bilevel problems using genetic algorithms. European Journal of Operational Research, 188, 14-8.CrossRef
  Calvete, H. I., Gale, C., & Mateo, P. M. (2009). A genetic algorithm for solving linear fractional bilevel problems. Annals of Operations Research, 166, 39-6.CrossRef
  Calvete, H. I., Gale, C., & Oliveros, M. (2011). Bilevel model for production-distribution planning solved by using ant colony optimization. Computers and Operations Research, 38, 320-27.CrossRef
  Colson, B., Marcotte, P., & Savard, G. (2007). An overview of bilevel optimization. Annals of Operations Research, 153, 235-56.CrossRef
  Colson, B., Marcotte, P., & Savard, G. (2005). A trust-region method for nonlinear bilevel programming: Algorithm and computational experience. Computational Optimization and Applications, 30, 211-27.CrossRef
  Deb, K., & Sinha, A. (2009). An evolutionary approach for bilevel multi-objective problems. Communications in Computer and Information Science, 35, 17-4.CrossRef
  Dempe, S. (1987). A simple algorithm for the linear bilevel programming problem. Optimization, 18, 373-85.CrossRef
  Dempe, S. (2002). Foundations of bilevel programming. Dordrecht: Kluwer Academie Publishers.
  Dempe, S. (2003). Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization, 52(3), 333-59.CrossRef
  Dempe, S., & Zemkoho, A. B. (2012). Bilevel road pricing: Theoretical analysis and optimality conditions. Annals of Operations Research, 196, 223-40.CrossRef
  Etoa, J. B. E. (2010). Solving convex quadratic bilevel programming problems using an enumeration sequential quadratic programming. Journal of Global Optimization, 47, 615-37.CrossRef
  Etoa, J. B. E. (2011). Solving quadratic convex bilevel programming problems using a smoothing method. Applied Mathematics and Computation, 217, 6680-690.CrossRef
  Glackin, J., Ecker, J. G., & Kupferschmid, H. (2009). Solving bilevel linear programs using multiple objective linear programming. Journal of Optimization Theory and Applications, 140, 197-12.CrossRef
  Gümüs, Z. H., & Floudas, C. A. (2005). Global optimization of mixed-integer bilevel programming problems. Computational Management Science, 2, 181-12.CrossRef
  Lan, K. M., Wen, U. P., & Shih, H. S. (2007). A hybrid neural network approach to bilevel programming problems. Applied Mathematics Letters, 20, 880-84.CrossRef
  Li, H., & Wang, Y. (2008a). An interpolation-based genetic algorithm for solving nonlinear bilevel programming problems. Chinese Journal of Computers, 31(6), 910-18.CrossRef
  Li, H., & Wang, Y. (2008b). Exponential distribution-based genetic algorithm for solving mixed-integer bilevel programming problems. Journal of Systems Engineering and Electronics, 19(6), 1159-164.CrossRef
  Li, H., & Wang, Y. (2011). A real-binary coded genetic algorithm for solving nonlinear bilevel programming with nonconvex objective functions. In The proceedings of 2011 IEEE congress on evolutionary computation (CEC) (pp. 2496-500). New Orleans, USA.
  Mersha, A. G., & Dempe, S. (2011). Direct search algorithm for bilevel programming problems. Computational Optimization and Applications, 49, 1-5.CrossRef
  Migdalas, A. (1995). Bilevel programming in traffic planning: Models, methods and challenge. Journal of Global Optimization, 7, 381-05.CrossRef
  Muu, L. D., & Quy, N. V. (2003). A global optimization method for solving convex quadratic bilevel programming problems. Journal of Global Optimizat
• 作者单位：Hecheng Li (1)
  
  1. Department of Mathematics, Qinghai Normal University, Xining, 810008, China
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Combinatorics
  Theory of Computation
  
• 出版者：Springer Netherlands
• ISSN：1572-9338

文摘

The bilevel programming problem is strongly NP-hard and non-convex, which implies that the problem is very challenging for most canonical optimization approaches using single-point search techniques to find global optima. In the present paper, a class of nonlinear bilevel programming problems are considered where the follower is a linear fractional program. Based on a novel coding scheme, a genetic algorithm with global convergence was developed. First, potential bases of the follower’s problem were taken as individuals, and a genetic algorithm was used to explore these bases. In addition, in order to evaluate each individual, a fitness function was presented by making use of the optimality conditions of linear fractional programs. Also, the fitness evaluation, as a sub-procedure of optimization, can partly improve the leader’s objective. Finally, some computational examples were solved and the results show that the proposed algorithm is efficient and robust. Keywords Bilevel programming Genetic algorithm Optimal solutions Bases