Meta-heuristic combining prior online and offline information for the quadratic assignment problem
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Article number | 6517261 |
Pages (from-to) | 429-444 |
Journal / Publication | IEEE Transactions on Cybernetics |
Volume | 44 |
Issue number | 3 |
Online published | 17 May 2013 |
Publication status | Published - Mar 2014 |
Link(s)
Abstract
The construction of promising solutions for N{script}P-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 meta-heuristic'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. © 2013 IEEE.
Research Area(s)
- Fitness landscape analysis, meta-heuristics, offline global information, online local information, quadratic assignment problem
Citation Format(s)
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, 6517261, 03.2014, p. 429-444.
In: IEEE Transactions on Cybernetics, Vol. 44, No. 3, 6517261, 03.2014, p. 429-444.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review