An analysis of parameter adaptation in reactive tabu search. (15th August 2013)

• Record Type: Journal Article
• Authors: Mascia, Franco; Pellegrini, Paola; Birattari, Mauro; Stützle, Thomas
• Is Part Of: International transactions in operational research. Volume 21:Number 1(2014:Jan.)
• Page Start: 127
• Page End: 152
• Publication Date: 2013-08-15
• Subjects: Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12043
• Languages: English
• ISSNs: 0969-6016

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>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 (<alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3zknb2kf" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:media:itor12043:itor12043-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="sans-serif">RTS</mml:mi></mml:math></alternatives>) 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3zknb2jw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:media:itor12043:itor12043-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="sans-serif">RTS</mml:mi></mml:math></alternatives> algorithm for the quadratic assignment problem. Together, the results of the two algorithms shed some new light on the reasons behind the effectiveness of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3zknb2hb" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:media:itor12043:itor12043-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="sans-serif">RTS</mml:mi></mml:math></alternatives>.</p> </abstract>