Unbiased black-box complexities of jump functions: how to cross large plateaus - Sorbonne Université
Communication Dans Un Congrès Année : 2014

Unbiased black-box complexities of jump functions: how to cross large plateaus

Résumé

We analyze the unbiased black-box complexity of jump functions with large jump sizes. Among other results, we show that when the jump size is (1/2 - epsilon)n, that is, only a small constant fraction of the fitness values is visible, then the unbiased black-box complexities for arities 3 and higher are of the same order as those for the simple OneMax function. Even for the extreme jump function, in which all but the two fitness values n/2 and n are blanked out, polynomial-time mutation-based (i.e., unary unbiased) black-box optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a Theta(n-1/2) fraction) is a plateau of constant fitness.To prove these results, we introduce new tools for the analysis of unbiased black-box complexities, for example, selecting the new parent individual not by comparing the fitnesses of the competing search points, but also by taking into account the (empirical) expected fitnesses of their offspring.

Dates et versions

hal-01086528 , version 1 (24-11-2014)

Identifiants

Citer

Benjamin Doerr, Carola Doerr, Timo Koetzing. Unbiased black-box complexities of jump functions: how to cross large plateaus. GECCO '14 - Conference on Genetic and Evolutionary Computation, ACM, Jul 2014, Vancouver, Canada. pp.769-776, ⟨10.1145/2576768.2598341⟩. ⟨hal-01086528⟩
241 Consultations
0 Téléchargements

Altmetric

Partager

More