Experimentation on Iterated Local Search Hyper-heuristics for Combinatorial Optimization Problems

Designing effective algorithms to solve cross-domain combinatorial optimization problems is an important goal for which manifold search methods have been extensively investigated. However, finding an optimal combination of perturbation operations for solving cross-domain optimization problems is hard because of the different characteristics of each problem and the discrepancies in the strengths of perturbation operations. The algorithm that works effectively for one problem domain may completely falter in the instances of other optimization problems. The objectives of this study are to describe three categories of a hyper-heuristic that combine low-level heuristics with an acceptance mechanism for solving cross-domain optimization problems, compare the three hyper-heuristic categories against the existing benchmark algorithms and experimentally determine the effects of low-level heuristic categorization on the standard optimization problems from the hyper-heuristic flexible framework. The hyper-heuristic categories are based on the methods of Thompson sampling and iterated local search to control the perturbation behavior of the iterated local search. The performances of the perturbation configurations in a hyper-heuristic were experimentally tested against the existing benchmark algorithms on standard optimization problems from the hyper-heuristic flexible framework. Study findings have suggested the most effective hyper-heuristic with improved performance when compared to the existing hyper-heuristics investigated for solving cross-domain optimization problems to be the one with a good balance between “single shaking” and “double shaking” strategies. The findings not only provide a foundation for establishing comparisons with other hyper-heuristics but also demonstrate a flexible alternative to investigate effective hyper-heuristics for solving complex combinatorial optimization problems.

@article{Adubi2023,
  title     = {Experimentation on Iterated Local Search Hyper-heuristics for Combinatorial Optimization Problems},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {14},
  number    = {5},
  year      = {2023},
  publisher = {The Science and Information Organization},
  author    = {Stephen A. Adubi and Olufunke O. Oladipupo and Oludayo O. Olugbara},
  doi       = {10.14569/IJACSA.2023.0140599},
  url       = {https://doi.org/10.14569/IJACSA.2023.0140599}
}