A VNS-based hyper-heuristic with adaptive computational budget of local search

Ping Che Hsiao, Tsung-Che Chiang, Li Chen Fu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Citations (Scopus)

Abstract

Hyper-heuristics solve problems by manipulating low-level domain-specific heuristics. The aim is to raise the level of generality of the algorithm to solve problems in different domains. In this paper we propose a hyper-heuristic based on Variable Neighborhood Search (VNS), which consists of two main steps: shaking and local search. Shaking disturbs solutions, and then local search seeks for the local optima. In our algorithm, we propose a mechanism to adjust the computational budget of local search periodically based on the search status. We also use a dynamically-sized population to store good solutions during the search process. Performance of the proposed algorithm is compared with four benchmark algorithms by four kinds of problems, Max-SAT, bin packing, flow shop scheduling, and personnel scheduling. Our algorithm finds the best solutions for around 90% of the tested instances.

Original languageEnglish
Title of host publication2012 IEEE Congress on Evolutionary Computation, CEC 2012
DOIs
Publication statusPublished - 2012 Oct 4
Event2012 IEEE Congress on Evolutionary Computation, CEC 2012 - Brisbane, QLD, Australia
Duration: 2012 Jun 102012 Jun 15

Publication series

Name2012 IEEE Congress on Evolutionary Computation, CEC 2012

Other

Other2012 IEEE Congress on Evolutionary Computation, CEC 2012
CountryAustralia
CityBrisbane, QLD
Period12/6/1012/6/15

    Fingerprint

Keywords

  • adaptive control
  • chesc
  • cross-domain heuristic search challenge
  • hyflex
  • hyper-heuristic
  • local search intensity
  • tabu search
  • variable neighborhood search

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Theoretical Computer Science

Cite this

Hsiao, P. C., Chiang, T-C., & Fu, L. C. (2012). A VNS-based hyper-heuristic with adaptive computational budget of local search. In 2012 IEEE Congress on Evolutionary Computation, CEC 2012 [6252969] (2012 IEEE Congress on Evolutionary Computation, CEC 2012). https://doi.org/10.1109/CEC.2012.6252969