Evolutionary Bilevel Optimization

Genetic and Evolutionary Computation Conference (GECCO) 2014

July 12-16 2014, Vancouver, BC, Canada

Many practical problem solving tasks involve multiple hierarchical search processes, requiring one search and optimization task to solve another lower-level search and optimization problem in a nested manner. In their simplicity, these problems are known as "Bilevel optimization" problems, in which there are two levels of optimization tasks. A solution at the upper level is feasible if the corresponding lower level variable vector is optimal for the lower level optimization problem. Problems in economics and business involving company CEOs and department heads or governmental decision makers and NGOs are standard bilevel optimization problems. In engineering, optimal control problems, structural design problems, transportation problems and other hierarchical problems fall into this category. Consider, for example, an inverted pendulum problem for which the motion of the platform relates to the upper-level optimization problem of performing the balancing task in a time-optimal manner. For a given motion of the platform, whether the pendulum can be balanced at all becomes a lower-level optimization problem of maximizing stability margin. Heirarchical games having multi-level controls are better posoed as bilevel problems. These problems are also known as Stackelberg games in the operations research and computer science community.

Bilevel problems are too complex to be solved using a classical optimization method simply due to the "nestedness" of one optimization task into another. Recent studies have shown that evolutionary optimization methodologies provide a distinct niche in solving such problems due to their flexibility, parallel processing, population approach and their ability to handle constrained search spaces efficiently. In the recent past, there has been a surge in research activities towards solving bilevel optimization problems using EAs and it is an appropriate time to have more EC researchers aware of "what bilevel problems are?" and "how efficient EAs can be developed for solving such problems?". GECCO-2014 provides a great platform to share the research challenges and current state-of-the-art in evoltionary bilevel optimization with EC researchers, so that more resarchers are aware and get interested in this emerging and important area.

In the tutorial, we shall introduce principles of bilevel optimization for single and multiple objectives and discuss the difficulties in solving such problems in general. With a brief survey of the existing literature, we shall present a few viable efficient evolutionary algorithms for both single and multi-objective EAs for bilevel optimization. Our recent studies on bilevel test problems and some application studies will be discussed. Finally, a number of immediate and future research ideas on evolutionary bilevel optimization (EBO) will be highlighted. Movies demonstrating the working principles of EBOs will be shown to make the understanding of the tutorial clear.

Organizers

Dr. Kalyanmoy Deb
Michigan State University, East Lansing, MI, USA

Dr. Ankur Sinha
Aalto University School of Business, Helsinki, Finland

Keywords

Bilevel Optimization, Bilevel Multi-objective Optimization, Evolutionary Algorithms, Multi-Criteria Decision Making, Theory on Bilevel Programming, Hierarchical Decision Making, Bilevel Applications, Hybrid Algorithms.