Neighborhood search
Neighborhood search methods are iterative metaheuristics. With
appropriate settings, these methods can produce high-quality solutions
within a medium running time. Chose these
algorithms only if exact algorithms cannot be applied for the given
problem.
Using neighborhood search
We suppose that you are familiar with the basic concepts of
neighborhood search which can be found in almost each text book about
discrete optimization. You may choose
- the neighborhood:
- According to your choice, neighbors are
generated by swappping adjacent operations (API), shifting
operations or swap or shift blocks of operations. The influence
of the choosen neighborhood to the quality of the results is
different for each probem type.
- the search method:
- Implemented methods are simulated
anealing, threshold accepting, plain iterative improvement and
tabu search.
- creating a neighbor:
- Creating Neighbors randomly instead of
enumerating the whole neighborhood may work well with iterative
improvement and tabu search if the neighborhood large.
- Created Solutions:
- gives an upper bound for the numbers of
search vertices the algorithm will visit before terminating.
Options
For explanation of the capabilities of the neighborhood search modul
please refere to the neighborhood search manual.
Trouble shooting
- If the algorithm runs too long just stop it. It will output the
best solution encountered so far.
- If the quality of the obtained solution is poor you should try
other parameters or another search method. Numerical parameters
can be varied automatically.
Table of Contents
Date 9.02.2000, TAU