On Misleading Solutions in Evolutionary Bilevel Optimization

Misleading solutions or pseudo-feasible solutions in Bilevel Optimization are infeasible solutions that have the same objective function values (considering both level) than the optimum one. Those misleading solutions affect the performance of bilevel evolutionary methods and the reporting of unfair results.

This post is based on the paper:

Mejía-de-Dios, J. A., Mezura-Montes, E., & Toledo-Hernández, P. (2022). Pseudo-feasible solutions in evolutionary bilevel optimization: Test problems and performance assessment. Applied Mathematics and Computation, 412, 126577.

The following figures and contents were presented in the 3rd Workshop on New Trends in Computational Intelligence and Applications (CIAPP 2021).

The presentation can be downloaded as a PDF:

Solution approaches: Classical vs Evolutionary

Many bilevel evolutionary algorithms approximate solutions using the nested scheme, i.e., for a given upper-level decision vector, a lower-level optimizer (another evolutionary algorithm) solves the lower-level problems for the given decision vector.

On the other hand, most classical techniques reformulate the bilevel problem before apply or propose an algorithm to solve the bilevel problem.

Note: When a lower-level evolutionary algorithm solves the lower-level, different issues emerge due to the inaccurate nature of such a lower-level optimizer. In general, a lower-level evolutionary method provides infeasible solutions to the upper level.

What is a pseudo-feasible solution?

As mentioned before, misleading solutions or pseudo-feasible solutions in bilevel optimization are infeasible solutions, i.e, solutions which are not optimizing the lower-level problem; however they have upper- and lower-level objective function values than the optimum one (see figure below).

Are Evolutionary Algorithms affected by misleading solutions?

Due to the inaccurate nature of evolutionary algorithms, those can report misleading report as studied in the paper:

Mejía-de-Dios, J. A., Mezura-Montes, E., & Toledo-Hernández, P. (2022). Pseudo-feasible solutions in evolutionary bilevel optimization: Test problems and performance assessment. Applied Mathematics and Computation, 412, 126577.

The main contributions given in the above paper were:

• Theoretical study on existence of misleading solutions.
• Conditions to mitigate misleading solutions.
• Test problem construction.
• Performance assessment.

Important Remarks

• Misleading solutions is a serious issue in evolutionary computation.
• EAs are not robust under presence of pseudo-feasible solutions.
• Unfair comparisons of solutions can be carried out if misleading solutions are not considered as a source of difficulty.