Skip to main content

Research Repository

Advanced Search

Evolutionary squeaky wheel optimization: a new framework for analysis

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

Evolutionary squeaky wheel optimization: a new framework for analysis Thumbnail


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.

Citation

Li, J., Parkes, A. J., & Burke, E. K. (in press). Evolutionary squeaky wheel optimization: a new framework for analysis. Evolutionary Computation, 19(3), https://doi.org/10.1162/EVCO_a_00033

Journal Article Type Article
Acceptance Date Jan 1, 2011
Online Publication Date Aug 8, 2011
Deposit Date Mar 8, 2018
Publicly Available Date Mar 8, 2018
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
DOI https://doi.org/10.1162/EVCO_a_00033
Keywords Combinatorial optimization, metaheuristics, stochastic search, stochastic process, Markov chain.
Public URL https://nottingham-repository.worktribe.com/output/708111
Publisher URL https://www.mitpressjournals.org/doi/10.1162/EVCO_a_00033
Contract Date Mar 8, 2018

Files





You might also like



Downloadable Citations