Evolutionary squeaky wheel optimization: a new framework for analysis
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 iteration...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
MIT Press
2011
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/50212/ |
| _version_ | 1848798186801463296 |
|---|---|
| author | Li, Jingpeng Parkes, Andrew J. Burke, Edmund K. |
| author_facet | Li, Jingpeng Parkes, Andrew J. Burke, Edmund K. |
| author_sort | Li, Jingpeng |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T20:15:46Z |
| format | Article |
| id | nottingham-50212 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T20:15:46Z |
| publishDate | 2011 |
| publisher | MIT Press |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-502122020-05-04T16:31:04Z https://eprints.nottingham.ac.uk/50212/ Evolutionary squeaky wheel optimization: a new framework for analysis Li, Jingpeng Parkes, Andrew J. Burke, Edmund K. 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. MIT Press 2011-08-08 Article PeerReviewed Li, Jingpeng, Parkes, Andrew J. and Burke, Edmund K. (2011) Evolutionary squeaky wheel optimization: a new framework for analysis. Evolutionary Computation, 19 (3). pp. 405-428. ISSN 1530-9304 Combinatorial optimization metaheuristics stochastic search stochastic process Markov chain. https://www.mitpressjournals.org/doi/10.1162/EVCO_a_00033 doi:10.1162/EVCO_a_00033 doi:10.1162/EVCO_a_00033 |
| spellingShingle | Combinatorial optimization metaheuristics stochastic search stochastic process Markov chain. Li, Jingpeng Parkes, Andrew J. Burke, Edmund K. Evolutionary squeaky wheel optimization: a new framework for analysis |
| title | Evolutionary squeaky wheel optimization: a new framework for analysis |
| title_full | Evolutionary squeaky wheel optimization: a new framework for analysis |
| title_fullStr | Evolutionary squeaky wheel optimization: a new framework for analysis |
| title_full_unstemmed | Evolutionary squeaky wheel optimization: a new framework for analysis |
| title_short | Evolutionary squeaky wheel optimization: a new framework for analysis |
| title_sort | evolutionary squeaky wheel optimization: a new framework for analysis |
| topic | Combinatorial optimization metaheuristics stochastic search stochastic process Markov chain. |
| url | https://eprints.nottingham.ac.uk/50212/ https://eprints.nottingham.ac.uk/50212/ https://eprints.nottingham.ac.uk/50212/ |