REPOSITORY > RESULTS

Abstract

This thesis investigates two distinct but related optimization problems: bilevel and minmax
problems, in the context of evolutionary algorithms (EAs). Bilevel optimization
involves hierarchical decision-making, where decisions at the upper level are subject to
constraints defined by the solutions of an optimization problem at the lower level. These
problems are particularly challenging due to their nested structure, the need to solve multiple
optimization problems simultaneously and hierarchically, and the ill-posedness that
arises when the lower level admits multiple optimal solutions. To address this ill-posedness,
bilevel problems can be analyzed through two approaches: optimistic and pessimistic. The
optimistic approach assumes that the lower-level decision-maker (follower) will select a
solution that is most favorable to the upper-level decision-maker (leader). In contrast,
the pessimistic approach assumes the follower selects the least favorable solution for the
leader, requiring the leader to optimize for the best achievable outcome under worst-case
conditions. This thesis introduces a δ-perturbed formulation to tackle this ill-posedness,
ensuring a unique approximate solution in the lower level. The method is applied to a
differential evolution (DE), a type of EA. EAs, including DE, are particularly suited for
solving bilevel optimization problems due to their ability to efficiently explore complex,
high-dimensional, and non-convex spaces. Theoretical properties of the δ-perturbed formulation,
including error bounds and proofs, are validated through computational studies.
Extensive experiments on benchmark test functions demonstrate the approach’s ability to
find both optimistic and pessimistic solutions. The methodology is then extended to multiobjective
bilevel problems, where the upper level involves multiple objectives, and the
lower level retains a single objective. In these problems, the ill-posedness of the lower level
leads to two distinct Pareto fronts in the upper level. The optimistic Pareto front arises
when the follower selects solutions that maximize the leader’s benefit, while the pessimistic
Pareto front represents the best achievable trade-offs under the follower’s worst-case behavior.
These distinct Pareto fronts highlight the impact of lower-level ambiguities on
upper-level objectives. The method is employed in the m-BLEAQ algorithm, an evolutionary
multiobjective bilevel algorithm, and computational experiments on test problems
validate its ability to accurately approximate both fronts. Min-max optimization is a special
case of bilevel optimization, where the leader seeks solutions against the worst-case
responses of the follower. These problems model robust optimization scenarios, where the
objective is to find solutions that perform reliably under the most unfavorable conditions
imposed by uncertainty. A differential evolution with estimation of distribution algorithm
(MMNDE-EDA) is proposed to solve min-max problems. This algorithm combines global
search capabilities with probabilistic modeling to efficiently estimate best worst-case solutions.
Experiments on standard min-max test functions and an engineering application
demonstrate the algorithm’s comparable performance to a state-of-the-art method. These
contributions advance theoretical understanding and provide novel methods for solving
hierarchical optimization problems, validated through computational experiments.