Theoretical Study of Optimizing Rugged Landscapes with the cGA
Estimation of distribution algorithms (EDAs) provide a distribution - based approach for optimization which adapts its probability distribution during the run of the algorithm. We contribute to the theoretical understanding of EDAs and point out that their distribution approach makes them more suitable to deal with rugged fitness landscapes than classical local search algorithms. Concretely, we make the OneMax function rugged by adding noise to each fitness value. The cGA can nevertheless find solutions with n(1 - \epsilon) many 1s, even for high variance of noise. In contrast to this, RLS and the (1+1) EA, with high probability, only find solutions with n(1/2+o(1)) many 1s, even for noise with small variance.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Computational and Experimental Exploration of Protein Fitness Landscapes: Navigating Smooth and Rugged Terrains
Proteins evolve through complex sequence spaces, with fitness landscapes serving as a conceptual framework that links sequence to function. Fitness landscapes can be smooth, where multiple similarly accessible evolutiona…
Scale-invariance of ruggedness measures in fractal fitness landscapes
The paper deals with using chaos to direct trajectories to targets and analyzes ruggedness and fractality of the resulting fitness landscapes. The targeting problem is formulated as a dynamic fitness landscape and four d…
Getting higher on rugged landscapes: Inversion mutations open access to fitter adaptive peaks in NK fitness landscapes
Molecular evolution is often conceptualised as adaptive walks on rugged fitness landscapes, driven by mutations and constrained by incremental fitness selection. It is well known that epistasis shapes the ruggedness of t…
Tunably Rugged Landscapes with Known Maximum and Minimum
We propose NM landscapes as a new class of tunably rugged benchmark problems. NM landscapes are well-defined on alphabets of any arity, including both discrete and real-valued alphabets, include epistasis in a natural an…
Impact of population size on early adaptation in rugged fitness landscapes
Due to stochastic fluctuations arising from finite population size, known as genetic drift, the ability of a population to explore a rugged fitness landscape depends on its size. In the weak mutation regime, while the me…