Choosing Internal Heuristics and Fine Tuning of Parameters"

authored by M. Josep Blesa, Lluís Hernàndez and Fatos Xhafa |

submitted to YOR 12 Workshop |

## Experimental Results

We have tested the Tabu Search Implementation for this problem with standard instances from the literature. For small and medium size instances [Freville, Plateau, 1990] the results are as follows:

We note that for instances of small and medium size we have always found the optimum solution, except for KNAP50. Interestingly, we have found the optimum solution in almost all the executions except for instance SENTO2 for which the optimum was find in 46% of executions.

For big size instances from OR-Library [Beasley, 1990] our fitness is very close to the best known fitness obtained by other ad hoc implementations (see [CB97]). These are the results:

## The configuration used

## The executions were done in computers from the BA-Cluster, an heterogeneous cluster of PCs that we are installing in our Department (Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya). The cluster is currently composed by a set of 9 computers:

Hardware configurationba1.lsi.upc.es

ba2.lsi.upc.es

ba3.lsi.upc.es

ba4.lsi.upc.es

guernika.lsi.upc.es

tarkus.lsi.upc.es

kruja.lsi.upc.es

alberti.lsi.upc.es

algenib.lsi.upc.esBy now, all these computers share the same configuration:

Processor: AMD K6-2 450 MHz

Main memory: 256 Mb

Hard Disk: 6 Gb

Main board: chipset VIA/ALI

Network adpater: 10/100 MbpsComputers named ba* only cointain their "box" (no keyboard, no mouse, no screen and no graphic adapter). Computers not named ba* are complete workstations including keyboard, mouse, michrophon, speakers, screen and graphic adapter.

Computers named ba* are interconnected by a dedicated network using a 10/100 switch. guernika, tarkus and kruja could also be connected to this switch but currently are not (we can do that if necessary).

We expect to increase the size of our cluster in the following years with ba*-like computers (the switch can connect 20 more computers!).

## The experiments have been done with different configurations mainly depending on the size of the problem. A configuration consist of a set of values for the setup parameters (see below). The concrete values used for each instance can be obtained by retrieving the complete input file (2nd column of the tables). These input files contain the problem and the setup parameters (see below).

Execution configuration

## Fine Tuning of Parameters

Here we refer only to two important internal heuristics for Tabu Search method, namely the intensification and diversification. A detailed explanation will be given in the full version of the paper.

## Initially, the search is instensified if the same solution is reached at least

Intensification & Equality of solutionsmax_repetitionstimes. We found that if the equality of solutions is defined strictly the intensification is never activated (due to the heuristic used for the neighborhood exploration). So the equality has been relaxed.We introduce the concept of

distance between solutionsthat measures the number of items whose values are different in a solution compared with another solution. Since a solution is implemented as a binary array of sizen(the number of items) it is clear that this distance is the Hamming distance. So we have redefined the "equality" between two solutions in terms of Hamming distance and consider two solutions "equal" if they difer in a very small number of items.For the number of differences between two given solutions (i.e. the Hamming distance) we have observed this behavior:

- For at most
kn(0<k <=1) differences:Good results are obtained for values of

knear 0.05 for small instances, but for big instances (n>250) the results obtained are bad, e.g. forn=500 25 differences are allowed (solutions are then quite different).- For at most
kn/lnn(0 <k<= 1) differences:This expression grows slower than the first one, so the number of differences allowed for two solutions to be equal does not increase rapidly wrt the number of items.

The figure below compares the growth of both expressions fork=0.05 (in the first one) andk=0.1 (in the second one).

Our diversification strategy includes two forms: soft diversification (explained below) and strong diversification (this is essentially an escape mecanism that permits exploring in a new region of the solution space).

## The parameter

Soft diversification &history_rephistory_repis a percentage used to decide if an item has been incorporated many times to the solution in process during the search. This parameter has an important influence when diversifying softly.We initially used a constant value (not a percentage) for the

history_repand compared it with all the elements of the arrayHISTORY(as [NF96] do) but drawbacks were found, so we considered it as a percentage. This parameters has become adaptable since it gets a proportional value (wrt the elements of the arrayHISTORY)each iteration of the diversification stage.rep = (

history_rep/ 100) * max {HISTORY[j], j=1..n }As we can see in the figure below, the best results are obtained when the value of

history_repis large (that means "more softness" in the soft diversification).