As the experimental results below show, SWO is a general approach to optimization. In this section, we explore a few insights into what makes SWO effective.
It is useful to think of SWO as searching two coupled spaces, as illustrated in Figure 4. One search space is the familiar solution space, and the other is priority space. Moves in the solution space are made indirectly, via the re-prioritization that results from analyzing the prior solution. Similarly, successive prioritizations are generated by constructing and analyzing a solution, and then using the blame that results from that analysis to modify the previous prioritization.
A point in the solution space represents a potential solution to the problem, and a corresponding point in priority space, derived by analyzing the solution, is an attempt to capture information about the structure of the search space in the vicinity of the solution. As SWO constructs a new solution from scratch, the priorities can be thought of as providing information about pitfalls common to the current region of the solution space. If some elements of the solution have tended to be sources of difficulty over some number of iterations, increasing their priority makes it more likely that the constructor will handle those elements in a good way.
One consequence of the coupled search spaces is that a small change in the sequence of elements generated by the prioritizer may correspond to a large change in the corresponding solution generated by the constructor, compared to the solution from the previous iteration. Moving an element forward in the sequence can significantly change its state in the resulting solution. In addition, any elements that now occur after it in the sequence must accommodate that element's state. For example, in the scheduling domain, moving a task earlier in the priority sequence may allow it to be placed on a different manufacturing line, thus possibly changing the mix of jobs that can run on that line, and on the line it was scheduled on in the previous iteration. One small change can have consequences for any element that follows it, with lower-priority tasks having to ``fill in the gaps'' that are left after higher-priority tasks have been scheduled.
The result is a large move that is ``coherent'' in the sense that it is similar to what we might expect from moving the higher priority task, then propagating the effects of that change by moving lower priority tasks as needed. This single move may correspond to a large number of moves for a search algorithm that only looks at local changes to the solution, and it may thus be difficult for such an algorithm to find.
The fact that SWO makes large moves in both search spaces is one obvious difference between SWO and traditional local search techniques, such as WSAT [Selman, Kautz, CohenSelman et al.1993]. Another difference is that with SWO, moves are never selected based on their effect on the objective function. Instead, unlike hillclimbing techniques, each move is made in response to ``trouble spots'' found in the current solution. The resulting move may be uphill, but the move is always motivated by those trouble spots.
In priority space the only ``local optima'' are those in which all elements of a solution are assigned equal blame. SWO tends to avoid getting trapped in local optima, because analysis and prioritization will always (in practice) suggest changes in the sequence, thus changing the solution generated on the next iteration. This does not guarantee that SWO will not become trapped in a small cycle, however. In our implementations we have introduced small amounts of randomness in the basic cycle. We also restart SWO periodically with a new initial sequence.
Another aspect of local search is that typically each point in the solution space is associated with a single value, the objective function score for that solution. When we talk about hillclimbing, we generally refer to the ``terrain'' described by this objective function score, over the space of solutions. The process of analysis in SWO can be thought of as synthesizing a more complex description of that terrain, by breaking a solution down into its component elements and assigning a score to each. Prioritization then translates the analysis into a ``strategy'' that the constructor can use to generate the next solution.
Assigning scores to the individual elements of a solution allows SWO to take advantage of the fact that real problems often combine some elements that are difficult to get right, plus others that are easy. In the scheduling problems presented below, some tasks can be assigned to just a few production lines, while others allow for much more flexibility. Some have due dates close to their release time, while others have a lot of leeway. It is sometimes possible to identify ``difficult'' elements of a problem with static analysis, but interactions can be complex, and elements that are causing difficulty in one part of the search space may be no trouble at all in another. Rather than trying to identify elements that are globally difficult by analyzing the entire problem, SWO analyzes individual solutions in order to find elements that are locally difficult. Globally difficult elements tend to be identified over time, as they are difficult across large parts of the search space.
By assigning blame and adjusting priorities based on identified problems in actual solutions, SWO avoids dependence on complex, domain dependent heuristics. It is our belief that this independence is particularly important in complex domains where even the best heuristics will miss some key interactions and therefore inhibit the search from exploring good areas that the heuristic incorrectly labels as unpromising. SWO uses actual solutions to discover which areas of the search space are promising and which are not.
