Runtime Analysis of Restricted Tournament Selection for Bimodal Optimisation.

Area of Science:

• Evolutionary Computation
• Algorithm Analysis
• Optimization

Background:

• Niching methods are crucial for maintaining population diversity and preventing genetic drift in evolutionary algorithms.
• Investigating multiple peaks in parallel requires effective selection mechanisms that balance exploration and exploitation.

Purpose of the Study:

• To provide the first rigorous runtime analysis of restricted tournament selection (RTS) within a (μ+1) evolutionary algorithm.
• To evaluate the effectiveness of RTS in finding both optima of the bimodal TwoMax function.

Main Methods:

• Restricted Tournament Selection (RTS): An offspring competes against the closest individual within a randomly selected window of population members.
• Theoretical analysis of RTS runtime complexity on the TwoMax problem.
• Experimental studies to complement theoretical findings and explore parameter spaces.

Main Results:

• RTS efficiently finds both optima on the TwoMax function when the window size (w) is sufficiently large.
• With a small window size, RTS fails to find both optima, even with exponential time, with high probability.
• A variant of RTS using selection without replacement enhances diversity but slows convergence when niches collapse.

Conclusions:

• The effectiveness of RTS is highly dependent on the window size parameter for maintaining population diversity and achieving convergence.
• Theoretical results demonstrate a critical threshold for window size, beyond which efficient optimization is guaranteed.
• Experimental validation supports theoretical findings and suggests further research directions for RTS parameter tuning.