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

15 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

Hyper-heuristics
Variable Neighborhood Search
Local Search
Scheduling
Bin Packing
Flow Shop Scheduling
Bins
Personnel
Heuristics
Benchmark

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

A VNS-based hyper-heuristic with adaptive computational budget of local search. / Hsiao, Ping Che; Chiang, Tsung-Che; Fu, Li Chen.

2012 IEEE Congress on Evolutionary Computation, CEC 2012. 2012. 6252969 (2012 IEEE Congress on Evolutionary Computation, CEC 2012).

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

Hsiao, PC, Chiang, T-C & Fu, LC 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, 2012 IEEE Congress on Evolutionary Computation, CEC 2012, Brisbane, QLD, Australia, 12/6/10. https://doi.org/10.1109/CEC.2012.6252969
Hsiao PC, Chiang T-C, Fu LC. A VNS-based hyper-heuristic with adaptive computational budget of local search. In 2012 IEEE Congress on Evolutionary Computation, CEC 2012. 2012. 6252969. (2012 IEEE Congress on Evolutionary Computation, CEC 2012). https://doi.org/10.1109/CEC.2012.6252969
Hsiao, Ping Che ; Chiang, Tsung-Che ; Fu, Li Chen. / A VNS-based hyper-heuristic with adaptive computational budget of local search. 2012 IEEE Congress on Evolutionary Computation, CEC 2012. 2012. (2012 IEEE Congress on Evolutionary Computation, CEC 2012).
@inproceedings{97c4787a440b4b13a94822f5b68ce825,
title = "A VNS-based hyper-heuristic with adaptive computational budget of local search",
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.",
keywords = "adaptive control, chesc, cross-domain heuristic search challenge, hyflex, hyper-heuristic, local search intensity, tabu search, variable neighborhood search",
author = "Hsiao, {Ping Che} and Tsung-Che Chiang and Fu, {Li Chen}",
year = "2012",
month = "10",
day = "4",
doi = "10.1109/CEC.2012.6252969",
language = "English",
isbn = "9781467315098",
series = "2012 IEEE Congress on Evolutionary Computation, CEC 2012",
booktitle = "2012 IEEE Congress on Evolutionary Computation, CEC 2012",

}

TY - GEN

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

AU - Hsiao, Ping Che

AU - Chiang, Tsung-Che

AU - Fu, Li Chen

PY - 2012/10/4

Y1 - 2012/10/4

N2 - 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.

AB - 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.

KW - adaptive control

KW - chesc

KW - cross-domain heuristic search challenge

KW - hyflex

KW - hyper-heuristic

KW - local search intensity

KW - tabu search

KW - variable neighborhood search

UR - http://www.scopus.com/inward/record.url?scp=84866862507&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84866862507&partnerID=8YFLogxK

U2 - 10.1109/CEC.2012.6252969

DO - 10.1109/CEC.2012.6252969

M3 - Conference contribution

SN - 9781467315098

T3 - 2012 IEEE Congress on Evolutionary Computation, CEC 2012

BT - 2012 IEEE Congress on Evolutionary Computation, CEC 2012

ER -