|
|
|
|
|
|
|
|
Neural Network Training |
|
Multi-Objective Routing Problem |
|
OptQuest: A Commercial Implementation |
|
A Context-Independent Method for Permutation
Problems |
|
Classical and Periodic Vehicle Routing |
|
Matrix Bandwidth Minimization |
|
Arc Crossing Minimization |
|
Project Scheduling under Uncertainty |
|
P-Median Problems |
|
Software Testing |
|
DNA Sequencing |
|
Network Design Problems in Telecommunications |
|
Variable Selection Problems |
|
Bus Routing |
|
|
|
|
|
Seminal ideas originated in the late 60s and
first description appeared in … |
|
Glover, F. (1977) “Heuristics for Integer
Programming Using Surrogate Constraints,” Decision Sciences, vol. 8, pp.
156-166. |
|
|
|
Modern version of the method is described in … |
|
Laguna, M. and R. Martí (2003) Scatter Search:
Methodology and Implementations in C, Kluwer Academic Publishers: Boston,
ISBN 1-4020-7376-3, 312 pp. |
|
|
|
|
|
|
Subset Type 1: all 2-element subsets. |
|
Subset Type 2: 3-element subsets derived from
the 2-element subsets by augmenting each 2-element subset to include the
best solution not in this subset. |
|
Subset Type 3: 4-element subsets derived from
the 3-element subsets by augmenting each 3-element subset to include the
best solutions not in this subset. |
|
Subset Type 4: the subsets consisting of the
best i elements, for i = 5 to b. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
An empirical investigation on parallelization
strategies for Scatter Search |
|
B. Adenso-Díaz, S. García-Carvajal, S. Lozano |
|
|
|
Solving feature subset selection problem by a
parallel scatter search |
|
F. G. López, M. G. Torres, B. Melián, J. A.
Moreno and J. M. Moreno-Vega |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Solution Quality |
|
Static updating is better than dynamic |
|
No interaction effects between phases |
|
Phase I |
|
MW outperforms SW |
|
Cooperation not significantly better |
|
Phase II |
|
Cooperative variants are superior |
|
Execution Time |
|
Static updating is faster than dynamic |
|
Phase I |
|
Cooperative MW |
|
Single walk |
|
Independent MW |
|
Phase II |
|
Independent MW |
|
Single walk |
|
Cooperative MW |
|
|
|
|
|
|
Seminal ideas originated in connection with tabu
search … |
|
Glover, F. and M. Laguna (1993) “Tabu Search,”
in Modern Heuristic Techniques for Combinatorial Problems, C. Reeves (ed.) Blackwell
Scientific Publications, pp. 70-150. |
|
|
|
Modern versions have been applied as a
combination method within scatter search and in the improvement phase of
GRASP |
|
|
|
|
|
|
|
|
|
Multi-start and local search procedure
introduced by Feo and Resende (1989) |
|
|
|
do |
|
{ |
|
x ß RandomizedGreedyConstruction(a) |
|
x ß LocalSearch(x) |
|
x* ß UpdateBest(x) |
|
} while (termination criterion not met) |
|
|
|
|
|
Originally suggested in the context of Graph
Drawing by Laguna and Marti (1999) |
|
A guiding solution is selected from a small set
(size 3) of elite solutions |
|
Initiating solutions are the result of GRASP
iterations |
|
The number of relinking steps is the number of
vertices in the graph |
|
Local search is applied every b ~ |E| steps |
|
|
|
Extensions and comprehensive review are due to
Resende and Riberio (2003) “GRASP with Path Relinking: Recent Advances and
Applications” http://www.research.att.com/~mgcr/doc/sgrasppr.pdf |
|
|
|
|
three index assignment problem [1, 3] |
|
job-shop scheduling problem [1, 2] |
|
prize-collecting Steiner tree problem [9] |
|
MAX-CUT problem [17] |
|
quadratic assignment problem [31] |
|
routing private circuits in telecommunication
networks [40] |
|
p-median problem [43] |
|
2-path network design problem [47] |
|
Steiner problem in graphs [49] |
|
capacitated minimum spanning tree problem [53] |
|
|
|
|
Periodical relinking ¾ not systematically applied to all
solutions |
|
|
|
Forward relinking ¾ worst solution is the initiating
solution |
|
|
|
Backward relinking ¾ best solution is the initiating
solution |
|
|
|
Backward and forward relinking ¾ both directions are
explored |
|
|
|
Mixed relinking ¾ relinking starts at both ends |
|
|
|
Randomized relinking ¾ stochastic selection of moves |
|
|
|
Truncated relinking ¾ the guiding solution is not reached |
|
|
|
|
Selection of initiating and guiding solutions |
|
|
|
Application of local search to intermediate
solutions |
|
|
|
Testing of standalone PR procedures |
|
|