Evolutionary squeaky wheel optimization: a new framework for analysis.

Area of Science:

• Optimization algorithms
• Metaheuristics
• Computational intelligence

Background:

• Squeaky Wheel Optimization (SWO) is effective but can lack intensification.
• Evolutionary SWO (ESWO) improves intensification by retaining good solution components.
• Analyzing parameter effects in ESWO is crucial for understanding its search process.

Purpose of the Study:

• To propose a formal Markov chain framework for analyzing ESWO.
• To address the challenge of ESWO operating on partial assignments.
• To investigate the search space properties of a specific ESWO variant (ESWO-II).

Main Methods:

• Development of a novel Markov chain-based analytical framework for ESWO.
• Focusing on ESWO-II, which uses probabilistic operators.
• Explicit computation of stationary distribution probabilities for a simple problem instance.

Main Results:

• The proposed framework successfully analyzes ESWO, considering its movement through partial assignments.
• ESWO-II exhibits interesting properties in its stationary distribution.
• State probabilities generally increase with fitness but show non-monotonic behavior.

Conclusions:

• The Markov chain framework provides a novel approach to analyzing ESWO, differing from local search analyses.
• The observed non-monotonicity in state probabilities is a key finding, contrasting with algorithms like simulated annealing.
• This formal analysis supports future studies on ESWO parameter tuning and performance.