Text

Runtime Analysis of Crowding Mechanisms for Multimodal Optimization

Many real-world optimization problems lead to multimodal domains and require the identification of multiple optima. Crowding methods have been developed to maintain population diversity, to investigate many peaks in parallel and to reduce genetic drift. We present the first rigorous runtime analyses of probabilistic crowding and generalized crowding, embedded in a (μ +1) EA. In probabilistic crowding the offspring compete with their parent in a fitness-proportional selection. Generalized crowding decreases the fitness of the inferior solution by a scaling factor during selection. We consider the bimodal function TwoMax and introduce a novel and natural notion for functions with bounded gradients. For a broad range of such functions we prove that probabilistic crowding needs exponential time with overwhelming probability to find solutions significantly closer to any global optimum than those found by random search. Even when the fitness function is scaled exponentially, probabilistic crowding still fails badly. Only if the exponential's base is linear in the problem size, probabilistic crowding becomes efficient on TwoMax. A similar threshold behavior holds for generalized crowding on TwoMax with respect to the scaling factor. Our theoretical results are accompanied by experiments for TwoMax showing that the threshold behaviors also apply to the best fitness found.

Ketersediaan

Informasi Detail

Judul Seri

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION; Vol.24 No.3 June 2020

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 581 - 592

Bahasa

English

ISBN/ISSN

-

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

THEORY
RUNTIME ANALYSIS
CROWDING METHODS
GENERALIZED CROWDING
PROBABILISTIC CROWDING

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Edgar Covantes Osuna, Dirk Sudholt

Versi lain/terkait

Lampiran Berkas

Komentar