![](https://csdnimg.cn/release/download_crawler_static/1232603/bg12.jpg)
Scatter Search and Path Relinking
5
RefSet, the new solution replaces the worst and RefSet is reordered in step 6. The
NewSolutions flag is switched to TRUE and the subset s that was just combined is
deleted from NewSubsets in steps 7 and 8, respectively.
This basic design can be expanded and improved in different ways. The SS method-
ology is very flexible, since each of its elements can be implemented in a variety of ways
and degrees of sophistication. Different improvements and designs from this basic SS
algorithm are given in Glover (1998), Glover et al. (1999, 2000), Laguna (2000) and
Laguna and Armentano (2001).
3 PATH RELINKING
One of the main goals in any search method is to create a balance between search inten-
sification and search diversification. Path relinking has been suggested as an approach
to integrate intensification and diversification strategies (Glover and Laguna, 1997).
Features that have been added to Scatter Search, by extension of its basic philosophy,
are also captured in the Path Relinking framework. This approach generates new solu-
tions by exploring trajectories that connect high-quality solutions—by starting from
one of these solutions, called an initiating solution
,
and generating a path in the neigh-
borhood space that leads toward the other solutions, called guiding solutions. This
is accomplished by selecting moves that introduce attributes contained in the guiding
solutions.
The approach may be viewed as an extreme (highly focused) instance of a strategy
that seeks to incorporate attributes of high quality solutions, by creating inducements to
favor these attributes in the moves selected. However, instead of using an inducement
that merely encourages the inclusion of such attributes, the path relinking approach
subordinates other considerations to the goal of choosing moves that introduce the
attributes of the guiding solutions, in order to create a “good attribute composition” in
the current solution. The composition at each step is determined by choosing the best
move, using customary choice criteria, from a restricted set—the set of those moves
currently available that incorporate a maximum number (or a maximum weighted value)
of the attributes of the guiding solutions.
The approach is called path relinking either by virtue of generating a new path
between solutions previously linked by a series of moves executed during a search, or
by generating a path between solutions previously linked to other solutions but not to
each other. Figure 1.2 shows two hypothetical paths (i.e., a sequence of moves) that link
solution A to solution B, to illustrate relinking of the first type. The solid line indicates
an original path produced by the “normal” operation of a procedure that produced a
series of moves leading from A to B, while the dashed line depicts the relinking path.
The paths are different because the move selection during the normal operation does not
“know” where solution B lies until it is finally reached, but simply follows a trajectory
whose intermediate steps are determined by some form of evaluation function. For
example, a commonly used approach is to select a move that minimizes (or maximizes)
the objective function value in the local sense. During path relinking, however, the main
goal is to incorporate attributes of the guiding solution (or solutions) while at the same
time recording the objective function values.
The effort to represent the process in a simple diagram such as the one preceding
creates some misleading impressions, however. First, the original (solid line) path,