Meta-heuristic combining prior online and offline information for the quadratic assignment problem

Jianyong Sun, Qingfu Zhang, Xin Yao

Research output: Contribution to journalArticle

16 Citations (Scopus)
49 Downloads (Pure)

Abstract

The construction of promising solutions for NP-hard combinatorial optimization problems (COPs) in meta-heuristics is usually based on three types of information, namely a priori information, a posteriori information learned from visited solutions during the search procedure, and online information collected in the solution construction process. Prior information reflects our domain knowledge about the COPs. Extensive domain knowledge can surely make the search effective, yet it is not always available. Posterior information could guide the meta-heuristics to globally explore promising search areas, but it lacks local guidance capability. On the contrary, online information can capture local structures, and its application can help exploit the search space. In this paper, we studied the effects of using this information on metaheuristic's algorithmic performances for the COPs. The study was illustrated by a set of heuristic algorithms developed for the quadratic assignment problem. We first proposed an improved scheme to extract online local information, then developed a unified framework under which all types of information can be combined readily. Finally, we studied the benefits of the three types of information to meta-heuristics. Conclusions were drawn from the comprehensive study, which can be used as principles to guide the design of effective meta-heuristic in the future.
Original languageEnglish
Pages (from-to)429 - 444
Number of pages16
JournalIEEE Transactions on Cybernetics
Volume44
Issue number3
DOIs
Publication statusPublished - Mar 2014

Fingerprint

Combinatorial optimization
Heuristic algorithms

Cite this

Sun, Jianyong ; Zhang, Qingfu ; Yao, Xin. / Meta-heuristic combining prior online and offline information for the quadratic assignment problem. In: IEEE Transactions on Cybernetics. 2014 ; Vol. 44, No. 3. pp. 429 - 444.
@article{bf1bb70a95a5447a81fceb5c74206aaf,
title = "Meta-heuristic combining prior online and offline information for the quadratic assignment problem",
abstract = "The construction of promising solutions for NP-hard combinatorial optimization problems (COPs) in meta-heuristics is usually based on three types of information, namely a priori information, a posteriori information learned from visited solutions during the search procedure, and online information collected in the solution construction process. Prior information reflects our domain knowledge about the COPs. Extensive domain knowledge can surely make the search effective, yet it is not always available. Posterior information could guide the meta-heuristics to globally explore promising search areas, but it lacks local guidance capability. On the contrary, online information can capture local structures, and its application can help exploit the search space. In this paper, we studied the effects of using this information on metaheuristic's algorithmic performances for the COPs. The study was illustrated by a set of heuristic algorithms developed for the quadratic assignment problem. We first proposed an improved scheme to extract online local information, then developed a unified framework under which all types of information can be combined readily. Finally, we studied the benefits of the three types of information to meta-heuristics. Conclusions were drawn from the comprehensive study, which can be used as principles to guide the design of effective meta-heuristic in the future.",
author = "Jianyong Sun and Qingfu Zhang and Xin Yao",
year = "2014",
month = "3",
doi = "10.1109/TCYB.2013.2256892",
language = "English",
volume = "44",
pages = "429 -- 444",
journal = "IEEE Transactions on Cybernetics",
issn = "2168-2267",
publisher = "IEEE Advancing Technology for Humanity",
number = "3",

}

Meta-heuristic combining prior online and offline information for the quadratic assignment problem. / Sun, Jianyong; Zhang, Qingfu; Yao, Xin.

In: IEEE Transactions on Cybernetics, Vol. 44, No. 3, 03.2014, p. 429 - 444.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Meta-heuristic combining prior online and offline information for the quadratic assignment problem

AU - Sun, Jianyong

AU - Zhang, Qingfu

AU - Yao, Xin

PY - 2014/3

Y1 - 2014/3

N2 - The construction of promising solutions for NP-hard combinatorial optimization problems (COPs) in meta-heuristics is usually based on three types of information, namely a priori information, a posteriori information learned from visited solutions during the search procedure, and online information collected in the solution construction process. Prior information reflects our domain knowledge about the COPs. Extensive domain knowledge can surely make the search effective, yet it is not always available. Posterior information could guide the meta-heuristics to globally explore promising search areas, but it lacks local guidance capability. On the contrary, online information can capture local structures, and its application can help exploit the search space. In this paper, we studied the effects of using this information on metaheuristic's algorithmic performances for the COPs. The study was illustrated by a set of heuristic algorithms developed for the quadratic assignment problem. We first proposed an improved scheme to extract online local information, then developed a unified framework under which all types of information can be combined readily. Finally, we studied the benefits of the three types of information to meta-heuristics. Conclusions were drawn from the comprehensive study, which can be used as principles to guide the design of effective meta-heuristic in the future.

AB - The construction of promising solutions for NP-hard combinatorial optimization problems (COPs) in meta-heuristics is usually based on three types of information, namely a priori information, a posteriori information learned from visited solutions during the search procedure, and online information collected in the solution construction process. Prior information reflects our domain knowledge about the COPs. Extensive domain knowledge can surely make the search effective, yet it is not always available. Posterior information could guide the meta-heuristics to globally explore promising search areas, but it lacks local guidance capability. On the contrary, online information can capture local structures, and its application can help exploit the search space. In this paper, we studied the effects of using this information on metaheuristic's algorithmic performances for the COPs. The study was illustrated by a set of heuristic algorithms developed for the quadratic assignment problem. We first proposed an improved scheme to extract online local information, then developed a unified framework under which all types of information can be combined readily. Finally, we studied the benefits of the three types of information to meta-heuristics. Conclusions were drawn from the comprehensive study, which can be used as principles to guide the design of effective meta-heuristic in the future.

U2 - 10.1109/TCYB.2013.2256892

DO - 10.1109/TCYB.2013.2256892

M3 - Article

VL - 44

SP - 429

EP - 444

JO - IEEE Transactions on Cybernetics

JF - IEEE Transactions on Cybernetics

SN - 2168-2267

IS - 3

ER -