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

Ping Che Hsiao; Tsung Che Chiang; Li Chen Fu

doi:10.1109/CEC.2012.6252969

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

Ping Che Hsiao^*, Tsung Che Chiang, Li Chen Fu

^*Corresponding author for this work

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

31 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 language	English
Title of host publication	2012 IEEE Congress on Evolutionary Computation, CEC 2012
DOIs	https://doi.org/10.1109/CEC.2012.6252969
Publication status	Published - 2012
Event	2012 IEEE Congress on Evolutionary Computation, CEC 2012 - Brisbane, QLD, Australia Duration: 2012 Jun 10 → 2012 Jun 15

Publication series

Name	2012 IEEE Congress on Evolutionary Computation, CEC 2012

Other

Other	2012 IEEE Congress on Evolutionary Computation, CEC 2012
Country/Territory	Australia
City	Brisbane, QLD
Period	2012/06/10 → 2012/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

Access to Document

10.1109/CEC.2012.6252969

Cite this

Hsiao, PC, Chiang, TC & 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, 2012/06/10. https://doi.org/10.1109/CEC.2012.6252969

@inproceedings{13454a47e92041e0b9a6de2b7d5dfd68,

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 Chiang, {Tsung Che} and Fu, {Li Chen}",

year = "2012",

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",

note = "2012 IEEE Congress on Evolutionary Computation, CEC 2012 ; Conference date: 10-06-2012 Through 15-06-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

Y1 - 2012

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

AN - SCOPUS:84866862507

SN - 9781467315098

T3 - 2012 IEEE Congress on Evolutionary Computation, CEC 2012

BT - 2012 IEEE Congress on Evolutionary Computation, CEC 2012

T2 - 2012 IEEE Congress on Evolutionary Computation, CEC 2012

Y2 - 10 June 2012 through 15 June 2012

ER -

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

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this