Keynote Speakers

ON PERFORMANCE OF NON-ELITIST EVOLUTIONARY ALGORITHMS WITH FITNESS PROPORTIONATE SELECTION

Duc-Cuong Dang 1, Anton Eremeev 2

1 University of Southampton, Southampton, United Kingdom

2 Sobolev Institute of Mathematics, Omsk, Russia

Abstract. In this survey, we rigorously analyse the use of the fitness proportionate selection in non-elitist evolutionary algorithms (EAs). This selection mechanism, also known as roulette-wheel selection, was the main selection used in the early development of genetic algorithms (GA) and their applications. Unlike the rank-based selections (tournament selection, (μ,λ)-selection, ranking selection etc.), this selection is sensitive to the absolute values of fitness function, and a non-linear scaling of the function may significantly change its properties. This is often seen as a weakness from the theoretical view point, but at the same time there exists a large body of literature reporting successful applications of the fitness proportionate selection.

The lower and upper bounds on the runtime, previously known for the OneMax function, recently have been extended to the linear fitness functions and the Royal Road functions. On the one hand, the lower bound for the EA runtime on linear functions is independent of variability of the weights in the linear function. On the other hand, the experimental evaluation and the theoretical upper bound on the runtime suggest that linear functions without a great difference in weights are easier to optimize.

This research is supported by the Russian Science Foundation grant 17-18-01536.

Global optimization techniques in geometrical problems

Abstract. We consider several geometrical problems like finding the diameter of a given compact convex set; approximating a measure of a convex body and as a particular case aprroximating the volume of a convex body; determining the gravity centers; construction of a mesh of points equidistantly representing a convex compact set an some other. The metodology used for solving these problems is based on inner and outer polyhedral approximation; branch and bound technique; cutting planes and linearization. All considered problems are illustrated by examples.