Skip to main content

Research Repository

See what's under the surface

Evolutionary squeaky wheel optimization: a new framework for analysis

Li, Jingpeng; Parkes, Andrew J.; Burke, Edmund K.

Authors

Jingpeng Li

Andrew J. Parkes

Edmund K. Burke



Abstract

Squeaky wheel optimization (SWO) is a relatively new metaheuristic that has been shown to be effective for many real-world problems. At each iteration SWO does a complete construction of a solution starting from the empty assignment. Although the construction uses information from previous iterations, the complete rebuilding does mean that SWO is generally effective at diversification but can suffer from a relatively weak intensification. Evolutionary SWO (ESWO) is a recent extension to SWO that is designed to improve the intensification by keeping the good components of solutions and only using SWO to reconstruct other poorer components of the solution. In such algorithms a standard challenge is to understand how the various parameters affect the search process. In order to support the future study of such issues, we propose a formal framework for the analysis of ESWO. The framework is based on Markov chains, and the main novelty arises because ESWO moves through the space of partial assignments. This makes it significantly different from the analyses used in local search (such as simulated annealing) which only move through complete assignments. Generally, the exact details of ESWO will depend on various heuristics; so we focus our approach on a case of ESWO that we call ESWO-II and that has probabilistic as opposed to heuristic selection and construction operators. For ESWO-II, we study a simple problem instance and explicitly compute the stationary distribution probability over the states of the search space. We find interesting properties of the distribution. In particular, we find that the probabilities of states generally, but not always, increase with their fitness. This nonmonotonocity is quite different from the monotonicity expected in algorithms such as simulated annealing.

Journal Article Type Article
Journal Evolutionary Computation
Print ISSN 1063-6560
Electronic ISSN 1530-9304
Publisher Massachusetts Institute of Technology Press
Peer Reviewed Peer Reviewed
Volume 19
Issue 3
APA6 Citation Li, J., Parkes, A. J., & Burke, E. K. (in press). Evolutionary squeaky wheel optimization: a new framework for analysis. Evolutionary Computation, 19(3), doi:10.1162/EVCO_a_00033
DOI https://doi.org/10.1162/EVCO_a_00033
Keywords Combinatorial optimization, metaheuristics, stochastic search, stochastic process, Markov chain.
Publisher URL https://www.mitpressjournals.org/doi/10.1162/EVCO_a_00033
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf

Files

Evolutionary Squeaky Wheel Optimization_ A New Framework for Analysis.pdf (248 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





Downloadable Citations