Parallel noising methods embedded in an adaptive memory
Maxence Laurent, Éric D. Taillard, Michel Toulouse, T eo Crainic · ArODES (HES-SO (https://www.hes-so.ch/)) · 2007
Memory: The memory (or data warehouse) is constituted of solutions. Each solution is classed into 3 categories : elite, intermediate and bad solutions. Each solution contains several components (for the TSP, a component is an edge: a route from one city to the next one). So, each component can be classified into 0, 1 or several of the 3 classes (no solution of the memory contains a given component, a component belongs to solutions of a single class or a component belongs to solutions of several classes). Memory initialization: The memory is initialized with solutions created with the the Quick-Boruvka procedure, as implemented in the Concorde software. These solutions are improved with the Chained Lin-Kernighan (CLK) procedure implemented in the Concorde software. Noising: Before launching CLK, the length of each edge is perturbed by a value that depends on av alue 1 >r> 0. This value r linearly decreases with the iteration number. For perturbing the length of the edges, we first multiply this length by a factor uniformly distributed between 1 � r and 1 + r. If the edge only belongs to elite solutions, the perturbed length is then diminished by a factor 1 � r. If the edge only belongs to bad solutions, the perturbed length is then increased by a factor 1 +r. Building a new solution: The quickest way to build a new solution is to start from a solution already in memory. So, we took the best solution stored in memory. Since the length of