Co-evolutionary Hybrid Bi-level Optimization

Created by W.Langdon from gp-bibliography.bib Revision:1.8576

@PhdThesis{Kieffer:thesis,

• author = "Emmanuel Kieffer",
• title = "Co-evolutionary Hybrid Bi-level Optimization",
• school = "Interdisciplinary Centre for Security, Reliability and Trust (SNT), The Faculty of Sciences, Technology and Communication, Universite du Luxembourg",
• year = "2019",
• address = "Esch-sur-Alzette, Luxembourg",
• month = "18 " # jan,
• keywords = "genetic algorithms, genetic programming, Computer science, Bi-level Optimization, co-evolution, learning to optimize",
• language = "English",
• URL = "https://hdl.handle.net/10993/38566",
• URL = "https://orbilu.uni.lu/handle/10993/38566",
• URL = "https://orbilu.uni.lu/bitstream/10993/38566/1/main.pdf",
• size = "214 pages",
• abstract = "Multi-level optimization stems from the need to tackle complex problems involving multiple decision makers. Two-level optimization, referred as ``Bi-level optimization'', occurs when two decision makers only control part of the decision variables but impact each other (e.g., objective value, feasibility). Bi-level problems are sequential by nature and can be represented as nested optimization problems in which one problem (the ``upper-level'') is constrained by another one (the ``lower-level''). The nested structure is a real obstacle that can be highly time consuming when the lower-level is \$\textbackslashmathcal\{NP\}-hard\$. Consequently, classical nested optimization should be avoided. Some surrogate-based approaches have been proposed to approximate the lower-level objective value function (or variables) to reduce the number of times the lower-level is globally optimized. Unfortunately, such a methodology is not applicable for large-scale and combinatorial bi-level problems. After a deep study of theoretical properties and a survey of the existing applications being bi-level by nature, problems which can benefit from a bi-level reformulation are investigated. A first contribution of this work has been to propose a novel bi-level clustering approach. Extending the well-know ``uncapacitated k-median problem'', it has been shown that clustering can be easily modeled as a two-level optimization problem using decomposition techniques. The resulting two-level problem is then turned into a bi-level problem offering the possibility to combine distance metrics in a hierarchical manner. The novel bi-level clustering problem has a very interesting property that enable us to tackle it with classical nested approaches. Indeed, its lower-level problem can be solved in polynomial time. In cooperation with the Luxembourg Centre for Systems Biomedicine (LCSB), this new clustering model has been applied on real datasets such as disease maps (e.g. Parkinson, Alzheimer). Using a novel hybrid and parallel genetic algorithm as optimization approach, the results obtained after a campaign of experiments have the ability to produce new knowledge compared to classical clustering techniques combining distance metrics in a classical manner.

  The previous bi-level clustering model has the advantage that the lower-level can be solved in polynomial time although the global problem is by definition \$\textbackslashmathcal\{NP\}\$-hard. Therefore, next investigations have been undertaken to tackle more general bi-level problems in which the lower-level problem does not present any specific advantageous properties. Since the lower-level problem can be very expensive to solve, the focus has been turned to surrogate-based approaches and hyper-parameter optimization techniques with the aim of approximating the lower-level problem and reduce the number of global lower-level optimizations. Adapting the well-know Bayesian optimization algorithm to solve general bi-level problems, the expensive lower-level optimizations have been dramatically reduced while obtaining very accurate solutions. The resulting solutions and the number of spared lower-level optimizations have been compared to the bi-level evolutionary algorithm based on quadratic approximations (BLEAQ) results after a campaign of experiments on official bi-level benchmarks. Although both approaches are very accurate, the bi-level bayesian version required less lower-level objective function calls. Surrogate-based approaches are restricted to small-scale and continuous bi-level problems although many real applications are combinatorial by nature. As for continuous problems, a study has been performed to apply some machine learning strategies. Instead of approximating the lower-level solution value, new approximation algorithms for the discrete/combinatorial case have been designed. Using the principle employed in GP hyper-heuristics, heuristics are trained in order to tackle efficiently the \$\textbackslashmathcal\{NP\}-hard\$ lower-level of bi-level problems. This automatic generation of heuristics permits to break the nested structure into two separated phases: \textbackslashemph\{training lower-level heuristics\} and \textbackslashemph\{solving the upper-level problem with the new heuristics\}. At this occasion, a second modeling contribution has been introduced through a novel large-scale and mixed-integer bi-level problem dealing with pricing in the cloud, i.e., the Bi-level Cloud Pricing Optimization Problem (BCPOP). After a series of experiments that consisted in training heuristics on various lower-level instances of the BCPOP and using them to tackle the bi-level problem itself, the obtained results are compared to the ``cooperative coevolutionary algorithm for bi-level optimization'' (COBRA).

  Although training heuristics enables to \textbackslashemph\{break the nested structure\}, a two phase optimization is still required. Therefore, the emphasis has been put on training heuristics while optimizing the upper-level problem using competitive co-evolution. Instead of adopting the classical decomposition scheme as done by COBRA which suffers from the strong epistatic links between lower-level and upper-level variables, co-evolving the solution and the mean to get to it can cope with these epistatic link issues. The ``CARBON'' algorithm developed in this thesis is a competitive and hybrid co-evolutionary algorithm designed for this purpose. In order to validate the potential of CARBON, numerical experiments have been designed and results have been compared to state-of-the-art algorithms. These results demonstrate that ``CARBON'' makes possible to address nested optimization efficiently.",

• notes = "also known as \cite{ORBi-9bbcc942-a1ce-4d3e-8fff-b8984ba8b57c}

  PhD-FSTC-2019-06

  FNR - Fonds National de la Recherche FNR9984150 - Coevolutionary Hybrid Bi-level Optimization, 2015 (01/03/2015-31/01/2019)

  Supervisor: Pascal Bouvry",

}

Genetic Programming entries for Emmanuel Kieffer

Citations