×

zbMATH — the first resource for mathematics

An analysis of parameter adaptation in reactive tabu search. (English) Zbl 1291.90326
Summary: On-line parameter adaptation schemes are widely used in metaheuristics. They are sometimes preferred to off-line tuning techniques for two main reasons. First, they promise to achieve good performance even on new instance families that have not been considered during the design or the tuning phase of the algorithm. Second, it is assumed that an on-line scheme could adapt the algorithm’s behaviour to local characteristics of the search space. This paper challenges the second hypothesis by analysing the contribution of the parameter adaptation to the performance of a state-of-the-art reactive tabu search (RTS) algorithm for the maximum clique problem. Our experimental analysis shows that this on-line parameter adaptation scheme converges to good instance-specific settings for the parameters, and that there is no evidence that it adapts to the local characteristics of the search space. The insights gained from the analysis are confirmed by further experiments with an RTS algorithm for the quadratic assignment problem. Together, the results of the two algorithms shed some new light on the reasons behind the effectiveness of RTS.

MSC:
90C59 Approximation methods and heuristics in mathematical programming
90C35 Programming involving graphs or networks
90B80 Discrete location and assignment
Software:
CFinder; coin; DIMACS; QAPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adamcsek, Cfinder: locating cliques and overlapping modules in biological networks, Bioinformatics 22 (8) pp 1021– (2006) · doi:10.1093/bioinformatics/btl039
[2] Balas, Finding a maximum clique in an arbitary graph, SIAM Journal of Computing 15 (4) pp 1054– (1986) · Zbl 0604.05024 · doi:10.1137/0215075
[3] Bastos, Essays and Surveys in Metaheuristics pp 39– (2001)
[4] Battiti, Greedy, prohibition, and reactive heuristics for graph partitioning, IEEE Transactions on Computers 48 (4) pp 361– (1999) · Zbl 05104430 · doi:10.1109/12.762522
[5] Battiti, Operations Research/Computer Science Interfaces (2008)
[6] Battiti, Reactive and dynamic local search for max-clique: engineering effective building blocks, Computers & Operations Research 37 (3) pp 534– (2010) · Zbl 1173.90586 · doi:10.1016/j.cor.2009.02.013
[7] Battiti, Reactive local search for the maximum clique problem, Algorithmica 29 (4) pp 610– (2001) · Zbl 0985.68016 · doi:10.1007/s004530010074
[8] Battiti, The reactive tabu search, ORSA Journal on Computing 6 pp 126– (1994) · Zbl 0807.90094 · doi:10.1287/ijoc.6.2.126
[9] Boginski, Mining market data: a network approach, Computers & Operations Research 33 (11) pp 3171– (2006) · Zbl 1113.90079 · doi:10.1016/j.cor.2005.01.027
[10] Bomze, The maximum clique problem, Handbook of Combinatorial Optimization, Supplement Vol. A 4 pp 1– (1999) · doi:10.1007/978-1-4757-3023-4_1
[11] Breiman, Bagging predictors, Machine Learning 24 pp 123– (1996) · Zbl 0858.68080 · doi:10.1007/BF00058655
[12] Brockington, Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge 26 (1996)
[13] Burkard, QAPLIB-a quadratic assignment problem library, Journal of Global Optimization 10 pp 391– (1997) · Zbl 0884.90116 · doi:10.1023/A:1008293323270
[14] Butenko, Clique-detection models in computational biochemistry and genomics, European Journal of Operational Research 173 pp 1– (2005) · Zbl 1125.92025 · doi:10.1016/j.ejor.2005.05.026
[15] Chiang, A reactive tabu search metaheuristic for the vehicle routing problem with time windows, INFORMS Journal on Computing 9 pp 417– (1997) · Zbl 0901.90088 · doi:10.1287/ijoc.9.4.417
[16] Dorigo, The ant system: an autocatalytic optimizing process (1991)
[17] Dorigo, Ant Colony Optimization (2004) · doi:10.1007/b99492
[18] Eiben, Parameter Setting in Evolutionary Algorithms pp 19– (2007) · doi:10.1007/978-3-540-69432-8_2
[19] Glover, Future paths for integer programming and links to artificial intelligence, Computers & Operations Research 13 (5) pp 533– (1986) · Zbl 0615.90083 · doi:10.1016/0305-0548(86)90048-1
[20] Grosso, Simple ingredients leading to very efficient heuristics for the maximum clique problem, Journal of Heuristics 14 (6) pp 587– (2007) · Zbl 1173.90565 · doi:10.1007/s10732-007-9055-x
[21] Hansen, Algorithms for the maximum satisfiability problem, Computing 44 pp 279– (1990) · Zbl 0716.68077 · doi:10.1007/BF02241270
[22] Hothorn, Implementing a class of permutation tests: the coin package, Journal of Statistical Software 28 (8) pp 1– (2008) · doi:10.18637/jss.v028.i08
[23] Ji, A graph theoretical approach to predict common RNA secondary structure motifs including pseudoknots in unaligned sequences, Bioinformatics 20 (10) pp 1591– (2004) · doi:10.1093/bioinformatics/bth131
[24] Joachims, Advances in Kernel Methods-Support Vector Learning pp 169– (1999)
[25] Johnson, Cliques, coloring, and satisfiability: second DIMACS implementation challenge (1996) · Zbl 0875.68678
[26] Lourenço, Handbook of Metaheuristics 146 pp 363– (2010) · doi:10.1007/978-1-4419-1665-5_12
[27] Mascia, Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010 pp 1274– (2010)
[28] Mascia, An analysis of parameter adaptation in reactive tabu search (2011)
[29] Moscato, Memetic Algorithms: A Short Introduction pp 219– (1999)
[30] Nanry, Solving the pickup and delivery problem with time windows using reactive tabu search, Transportation Research Part B 34 (2) pp 107– (2000) · doi:10.1016/S0191-2615(99)00016-8
[31] Osman, A reactive tabu search meta-heuristic for the vehicle routing problem with back-hauls, Journal of Scheduling 5 (4) pp 263– (2002) · Zbl 1009.90018 · doi:10.1002/jos.122
[32] Palla, Quantifying social group evolution, Nature 446 pp 664– (2007) · doi:10.1038/nature05670
[33] Pellegrini, On the sensitivity of reactive tabu search to its meta-parameters (2011)
[34] Pevzner, Combinatorial approaches to finding subtle signals in DNA sequences pp 269– (2000)
[35] Pla, Matching feature points in image sequences through a region-based method, Computer Vision and Image Understanding 66 (3) pp 271– (1997) · doi:10.1006/cviu.1996.0512
[36] Pullan, Phased local search for the maximum clique problem, Journal of Combinatorial Optimization 12 (3) pp 303– (2006) · Zbl 1255.90122 · doi:10.1007/s10878-006-9635-y
[37] Pullan, Dynamic local search for the maximum clique problem, Journal of Artificial Intelligence Research 25 (1) pp 159– (2006) · Zbl 1255.90122
[38] Pullan, Cooperating local search for the maximum clique problem, Journal of Heuristics 17 (2) pp 181– (2011) · Zbl 05886941 · doi:10.1007/s10732-010-9131-5
[39] Ryan, Reactive tabu search in unmanned aerial reconnaissance simulations pp 873– (1998)
[40] Stützle, Autonomous Search pp 191– (2012)
[41] Taillard, Robust taboo search for the quadratic assignment problem, Parallel Computing 17 (4-5) pp 443– (1991) · doi:10.1016/S0167-8191(05)80147-4
[42] Toune, Proceedings on IEEE World Congress on Computational Intelligence-Evolutionary Computation pp 763– (1998)
[43] Voy, Extracting gene networks for low-dose radiation using graph theoretical algorithms, PLoS Computational Biology 2 (7) pp e89– (2006) · doi:10.1371/journal.pcbi.0020089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.