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

20 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
Period2012/06/102012/06/15

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

Fingerprint Dive into the research topics of 'A VNS-based hyper-heuristic with adaptive computational budget of local search'. Together they form a unique fingerprint.

Cite this