Drift and scaling in estimation of distribution algorithms.

Area of Science:

• Artificial Intelligence
• Computational Biology
• Optimization Algorithms

Background:

• Estimation of Distribution Algorithms (EDAs) are population-based metaheuristics.
• These algorithms can exhibit phenomena analogous to genetic drift.
• Finite population sampling in selection can reinforce model fluctuations.

Purpose of the Study:

• To analyze a phenomenon in EDAs similar to drift in population genetics.
• To identify conditions leading to attractive fixed points in EDA probability models.
• To propose strategies for avoiding premature convergence in EDAs.

Main Methods:

• Theoretical analysis of EDAs using Markov chain properties.
• Investigation of ergodicity and irreducibility of the probability model state space.
• Empirical validation using specific EDA instances like UMDA.

Main Results:

• A general EDA phenomenon is identified where probability models can converge to a single outcome.
• This convergence is linked to the lack of ergodicity and irreducibility.
• For UMDA, sufficient population size is crucial for finding the global optimum.

Conclusions:

• EDA parameter scaling must be problem-dependent or algorithms need modification to prevent model collapse.
• Population size must scale with search space size for 'needle-in-a-haystack' problems (sqrt(N)).
• Population size must scale with problem size for 'one-max' problems (sqrt(n)).