A Hybrid Approach for Solving Dynamic Bi-level Optimization Problems

• Autores: Eduardo Samaniego Mena, Pavel Novoa Hernandez
• Localización: Computación y Sistemas (CyS), ISSN 1405-5546, ISSN-e 2007-9737, Vol. 22, Nº. 2, 2018, págs. 639-656
• Idioma: inglés
• DOI: 10.13053/cys-22-2-2557
• Enlaces
  • Texto completo
• Resumen

  • Abstract: Several real-life decision scenarios are hierarchical, which are commonly modeled as bi-level optimization problems (BOPs). As other decision scenarios, these problems can be dynamic, that is, some elements of their mathematical model can change over time. This kind of uncertainty imposes an extra level of complexity on the model, since the algorithm needs to find the best bi-level solution over time. Despite the importance of studying these problems, the literature reflects just a few works on dynamic bi-level optimization problems (DBOPs). In this context, this work addresses the solution of DBOPs from the viewpoint of metaheuristic methods. Our hypothesis is that, by hybridizing successful solving approaches from both bi-level and dynamic optimization fields, an effective method for DBOPs can be obtained. In this regard, we propose a hybrid method that combines a coevolutionary approach and a self-adaptive, multipopulation algorithm. Experimental results assert our hypothesis, specially for certain information exchange mechanisms.

• Referencias bibliográficas
  • Alba, E.,Nakib, A.,Siarry, P.. (2013). Metaheuristics for Dynamic Optimization. Springer Berlin Heidelberg.
  • Blackwell, T.,Branke, J.. (2006). Multiswarms, exclusion, and anti-convergence in dynamic environments. IEEE Transactions on Evolutionary...
  • Boussa¨ıd, I.,Lepagnot, J.,Siarry, P.. (2013). A survey on optimization metaheuristics. Information Sciences. 237. 82-117
  • Branke, J. (1999). Proceedings of the Congress on Evolutionary Computation. IEEE Press.
  • Camacho-Vallejo, J.-F.,González-Rodríguez, E.,Almaguer, F.-J.,González-Ramírez, R. G.. (2015). A bi-level optimization model for aid distribution...
  • Chen, Z.,Song, Z.. (2012). Dynamic portfolio optimization under multifactor model in stochastic markets. OR Spectrum. 34. 885-919
  • Colson, B.,Marcotte, P.,Savard, G.. (2005). Bilevel programming: A survey. 4OR. 3. 87-107
  • Cruz, C.,González, J. R.,Pelta, D.. (2011). Optimization in dynamic environments: a survey on problems, methods and measures. Soft Computing....
  • du Plessis, M. C.,Engelbrecht, A. P.. (2012). Using competitive population evaluation in a differential evolution algorithm for dynamic environments....
  • García, S.,Molina, D.,Lozano, M.,Herrera, F.. (2009). A study on the use of non-parametric tests for analyzing the evolutionary algorithms’...
  • Hansen, P.,Jaumard, B.,Savard, G.. (1992). New branch-and-bound rules for linear bilevel pro-gramming. SIAM Journal on Scientific and Statistical...
  • Jeroslow, R. (1985). The polynomial hierarchy and a simple model for competitive analysis. Mathematical Programming. 32. 146
  • Jin, Y.,Branke, J.. (2005). Evolutionary optimization in uncertain environments-a survey. Evolutionary Computation, IEEE Transactions on....
  • Kocvara, M.,Outrata, J.. (2006). Effective reformulations of the truss topology design problem. Optimization and Engineering. 7. 201
  • Legillon, F.,Liefooghe, A.,Talbi, E.-G.. (2013). Metaheuristics for Bi-level Optimization. Springer Berlin Heidelberg.
  • Li, C.,Nguyen, T. T.,Yang, M.,Yang, S.,Zeng, S.. (2015). Multi-population methods in unconstrained continuous dynamic environments: The challenges....
  • Li, C.,Yang, S.,Nguyen, T. T.,Yu, E. L.,Yao, X.,Jin, Y.,Beyer, H.-G.,Suganthan, P. N.. (2008). Benchmark generator for cec’2009 competition...
  • Linnala, M.,Madetoja, E.,Ruotsalainen, H.,Hämäläinen, J.. (2012). Bi-level optimization for a dynamic multiobjective problem. Engineering...
  • Marinakis, Y.,Marinaki, M.. (2013). Metaheuristics for Bi-level Optimization. Springer Berlin Heidelberg.
  • Meyer-Nieberg, S.,Beyer, H.-G.. (2007). Parameter Setting in Evolutionary Algorithms. Springer Berlin / Heidelberg.
  • Nguyen, T. T.,Yang, S.,Branke, J.. (2012). Evolutionary dynamic optimization: A survey of the state of the art. Swarm and Evolutionary Computation....
  • Novoa-Hernández, P.,Corona, C. C.,Pelta, D. A.. (2013). Self-adaptive, multipopulation differential evolution in dynamic environments. Soft...
  • Novoa-Hernández, P.,Corona, C. C.,Pelta, D. A.. (2015). A software tool for assisting experimentation in dynamic environments. Applied Computational...
  • Novoa-Hernández, P.,Corona, C. C.,Pelta, D. A.. (2016). Self-adaptation in dynamic environments - a survey and open issues. International...
  • Oduguwa, V.,Roy, R.. (2002). Bi-level optimisation using genetic algorithm. Artificial Intelligence Systems, 2002. (ICAIS 2002). 2002 IEEE...
  • Sinha, A.,Malo, P.,Deb, K.. (2014). Test problem construction for single objective bilevel optimization. Evolutionary Computation Journal.
  • Sinha, A.,Malo, P.,Frantsev, A.,Deb, K.. (2014). Finding optimal strategies in a multi-period multi-leader-follower stackelberg game using...
  • Storn, R.,Price, K.. (1997). Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces. Journal...
  • Sun, D.,Benekohal, R.,Waller, S.. (2006). Bi-level programming formulation and heuristic solution approach for dynamic traffic signal optimization....
  • Talbi, E.-G. (2013). Metaheuristics for Bi-level Optimization. Springer Berlin Heidelberg.