Computer Science – Artificial Intelligence
Scientific paper
2011-05-27
Journal Of Artificial Intelligence Research, Volume 10, pages 353-373, 1999
Computer Science
Artificial Intelligence
Scientific paper
10.1613/jair.561
We describe a general approach to optimization which we term `Squeaky Wheel' Optimization (SWO). In SWO, a greedy algorithm is used to construct a solution which is then analyzed to find the trouble spots, i.e., those elements, that, if improved, are likely to improve the objective function score. The results of the analysis are used to generate new priorities that determine the order in which the greedy algorithm constructs the next solution. This Construct/Analyze/Prioritize cycle continues until some limit is reached, or an acceptable solution is found. SWO can be viewed as operating on two search spaces: solutions and prioritizations. Successive solutions are only indirectly related, via the re-prioritization that results from analyzing the prior solution. Similarly, successive prioritizations are generated by constructing and analyzing solutions. This `coupled search' has some interesting properties, which we discuss. We report encouraging experimental results on two domains, scheduling problems that arise in fiber-optic cable manufacturing, and graph coloring problems. The fact that these domains are very different supports our claim that SWO is a general technique for optimization.
Clements David Peregrine
Joslin D. E.
No associations
LandOfFree
Squeaky Wheel Optimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Squeaky Wheel Optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Squeaky Wheel Optimization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-664459