Advances and Applications in Discrete Mathematics
Volume 17, Issue 2, Pages 125 - 149
(April 2016) http://dx.doi.org/10.17654/AADMApr2016_125_149 |
|
ENHANCED META-HEURISTICS WITH VARIABLE NEIGHBORHOOD SEARCH STRATEGY FOR COMBINATORIAL OPTIMIZATION PROBLEMS
Noureddine Bouhmala
|
Abstract: Variable neighborhood search (VNS) is a simple meta-heuristic that systematically changes the size and type of neighborhood during the search process in order to escape from local optima. In this paper, enhanced versions of tabu search and memetic algorithm with variable neighborhood search for combinatorial optimization problems are introduced. The set of constructed neighborhoods satisfies the property that each small neighborhood is a subset of a larger one. Most of the work published earlier on VNS starts from the first neighborhood and moves on to higher neighborhoods without controlling and adapting the ordering of neighborhood structures. The order in which the neighborhood structures have been selected in this paper during the search process offers a better mechanism for performing diversification and intensification. A set of industrial and random problems is used to test the effectiveness of the two enhanced meta-heuristics using the maximum satisfying problem as a test case. |
Keywords and phrases: maximum satisfiability problem, memetic algorithm, tabu search, variable neighborhood search. |
|
Number of Downloads: 343 | Number of Views: 1229 |
|