Seminar of Algorithms of Saclay Plateau: Simon Wietheger on Friday 07 October 2022 at 11h30

===== Seminar "Algorithms of Saclay Plateau" =====

Dear all,

Reminder: Recall that next seminar will be on Monday 17 October 2022 at 14h00 by Max S. New: A type theory for formal category theory.

Notce that for another  seminar of the seminar "Algorithms of Saclay Plateau", we are happy to welcome Simon Wietheger.

***** Friday 07 October 2022 at 11h30, room Poincaré *****

Simon Wietheger -- Crossover for Cardinality-Constrained Optimization

"In order to understand better how and why crossover can benefit optimization, we consider pseudo-Boolean functions with an upper bound 𝐵 on the number of 1s allowed in the bit string (cardinality constraint). We consider the natural translation of the OneMax test function, a linear function where 𝐵 bits have a weight of 1 + 𝜀 and the remaining bits have a weight of 1. The literature gives a bound of Θ(𝑛^2) for the (1+1) EA on this function. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping both a 1 and a 0. The experimental literature proposes balanced operators, preserving the number of 1s, as a remedy. We show that a balanced mutation operator optimizes the problem in 𝑂 (𝑛 log 𝑛) if,𝑛 − 𝐵 = 𝑂 (1). However, if 𝑛 − 𝐵 = Θ(𝑛), we show a bound of Ω(𝑛^2), just as classic bit flip mutation. Crossover and a simple island model gives 𝑂 (𝑛^2/log 𝑛) (uniform crossover) and 𝑂 (𝑛√𝑛) (3-ary majority vote crossover). For balanced uniform crossover with Hamming distance maximization for diversity we show a bound of 𝑂 (𝑛 log 𝑛)."


Following seminars: TBA

The list of next seminars can be found at:
https://bournez.gitlabpages.inria.fr/seminar-algorithms-plateau-Saclay/seminar/

The calendar of seminars can be found at:
https://bournez.gitlabpages.inria.fr/seminar-algorithms-plateau-Saclay/seminar.ics