The Ant System Applied to the Quadratic Assignment Problem

Vittorio Maniezzo1, Alberto Colorni2

Abstract

In recent years there has been growing interest in algorithms inspired by the observation ofnatural phenomena to define computational procedures which can solve complex problems.In this article we describe a distributed heuristic algorithm which was inspired by theobservation of the behavior of ant colonies and we propose its use for the QuadraticAssignment Problem. The results obtained in solving several classical instances of theproblem are compared with those obtained from other evolutionary heuristics to evaluate thequality of the proposed system.

12

Scienze dell'Informazione, Università di Bologna, Via Sacchi 3, 47023, Cesena, Italy, maniezzo@csr.unibo.it

Dipartimento di Elettronica e Informazione, Politecnico di Milano, Via Ponzio 34/5, 20133, Milano, Italy,colorni@elet.polimi.it

1. Introduction

The Quadratic Assignment Problem (QAP) of order n consists in looking for the bestallocation of n activities to n locations, where the terms activity and location should beconsidered in their most general sense. It was first formulated in (Koopmans and Beckman,1957) and since then it has been recognized as a model of many different real situations;applications have been described concerning planning of buildings in university campuses,arrangement of departments in hospitals, minimization of the total wire length in electroniccircuits, ordering of correlated data in magnetic tapes and others (Burkard, 1984).Mathematically the problem is defined by three matrices of dimension n 󰀁 n:

D=[dih] = matrix of the distances (between location i and location h);F =[fjk] = matrix of the flows (between activity j and activity k);C =[cij] = matrix of the assignment costs (of activity j to location i).

Normally matrices D and F are integer-valued matrices, while the assignment cost cij ofactivity j to location i is usually ignored, as it does not make a significant contribution to thecomplexity of solving the problem.

Under these hypotheses, a permutation 󰀂: i 󰀃 󰀁(i) can be interpreted as a particularassignment of activity j = 󰀁(i) to location i (i = 1, ... , n).

The cost of transferring data (or materials etc., depending on the problem in question)between two activities can be expressed as the product of the distance between the locationsto which the activities are assigned by the flow between the two activities, dih·f󰀁(i)󰀁(h).

1

To solve the QAP one must thus find a permutation 󰀂 of the indices (1,2,...,n) whichminimizes the total assignment cost:

min z=

i,h=1

󰀄dih󰀅f󰀁(i)󰀁(h)

n

(1)

The problem can be reformulated to show the quadratic nature of the objective function:solving the problem means identifying a permutation matrix X of dimension n 󰀁 n (whoseelements xij are 1 if activity j is assigned to location i and 0 in the other cases) such that:

zQAP = min z =

subject to the following constraints

i,j󰀁1h,k󰀁1

󰀄󰀄

n

n

dih fjk xij xhk

(2)

i󰀁1nj󰀁1

󰀄xij󰀆1

n

(j = 1,...,n)(i = 1,...,n)(i,j = 1,...,n)

(3)(4)

(5)

󰀄xij󰀆1

xij 󰀇{0,1}

which identify the matrix X as belonging to set 󰀂 of the permutation matrices of order n.As the QAP is a generalization of the Traveling Salesman Problem (TSP), it is also an NP-complete problem (Sahni and Gonzales, 1976)

The techniques which can be used to find the optimal solution are limited to branch andbound and cutting planes methods: with current hardware, problems of order greater than 20cannot be solved in an acceptable time (Burkard et al., 1994).

For this reason, in recent years many heuristic algorithms have been proposed which, thoughnot ensuring that the solution found is the best one, give good results in an acceptablecomputation time (Maniezzo et al., 1994).

2

In this article we propose the use of a new heuristic procedure, improving over an algorithmoriginally developed for the TSP, which shows the emergence of global properties followingthe mutual interaction among many elementary agents (Colorni et al., 1991, 1992, Dorigo etal., 1996). In particular we are interested in the distribution of search activity among agentswhich can only perform very simple actions, so that we can easily parallelize thecomputational effort (see Li, Pardalos, 1992 for a discussion on the effectiveness ofparallelization for the QAP).

Our work was inspired by researches on the behavior of ant colonies (Denebourg et al.,1983), where one of the problems of interest is to understand how ants, which are almostblind animals with very simple individual capacities, can, when they act together in a colony,find the shortest route between two points, (e.g. the ant's nest and a source of food).

The explanation lies in how the ants transmit information on the path followed: each of themwhen it moves deposits a substance, called pheromone, which can be detected by the otherants. While an ant with no information moves essentially at random, an ant which follows apath already followed by others is tempted to follow the already marked path (and theprobability of this to occur depends on the intensity of the trace perceived), in turn leavingnew pheromone which is added to that already existing. The emerging collective effect is aform of autocatalytic or positive feedback behavior, in that the more ants follow a particularpath, the more attractive this path becomes for the next ants which should meet it. Theprocess is characterized by a positive feedback; in fact, the probability with which an antchooses a path increases with the number of ants which have already chosen the same path.The final result is that nearly all the ants will choose to follow the shortest path, even if eachant's decision always remains probabilistic (that is, they can also explore new paths).The algorithm which we will define in the next section is inspired by the observations madeon ant colonies and is thus called the Ant System. A description of the original version of this

3

method and of its experimental results when applied to the Traveling Salesman Problem canbe found in (Dorigo, et al., 1996).

2. The Ant System

In this section we introduce a new heuristic (below called the Ant System) for the QAP whichuses some characteristics of behavior shown in reality by ant colonies, defining a system ofartificial \"ants\". The Ant System presented in this paper represents an improvement of thealgorithm described in (Dorigo et al., 1996), from which it differs in several structuralelements.

In the Ant System each artificial \"ant\" is an agent with the following characteristics:i)

when it chooses to assign activity j to location i it leaves a substance, called trace (theequivalent of the pheromone) 󰀈ij on the coupling (i, j);

ii)it chooses the location to which a given activity is to be assigned with a probability

which is a function of the \"potential goodness\" 󰀉ij of the coupling (i,j) and of the quantityof trace present on the coupling itself;

iii)to construct a complete permutation, locations and activities already coupled are

inhibited until all activities have been assigned.

This heuristic uses a population of m agents which construct solutions step by step, assigningan activity to each location. When all the ants have constructed their permutations, the bestassignments are rewarded so as to encourage the identification of ever better solutions in thenext cycles.

To satisfy the requirement that the ants assign each activity to a different location, weassociate a data structure, called a tabu list, to each ant. This memorizes the locations alreadyused and stops the ant assigning them a new activity before a cycle is complete (which thusidentifies a permutation). Once the permutation is completed, the tabu list is emptied and the

4

ant is free to choose its own couplings again. Let us define tabuk a vector containing the tabulist for the k-th ant and tabuk(s) as the s-th element of the tabu list for the k-th ant (thelocation occupied by the s-th activity in the assignment made by the k-th ant).

We now see how to introduce a method to calculate the \"potential goodness\" 󰀉ij of anassignment and thus the initial assignment (when there is no trace); the initial situation willthen be modified by the experience acquired by the population via the trace.

The basic idea is to exploit the information given by an effective lower bound to thecompletion of the problem solution and use it as an indicator of the expected proficiency of aparticular pairing.

For the particular case of the QAP, several lower bounds have been proposed (Pardalos,Wolkowicz, 1994). The better known one, and among those we tested the one that had thebest effectiveness/computational cost ratio, is the Gilmore and Lawler bound (independentlypresented by Gilmore, 1962, and Lawler, 1963). The bound is obtained by computing a valuezGL as

zGL = min z =

i,j󰀁1

󰀄

n

( min

h,k󰀁1

󰀄

n

dih fjk xhk ) xij

(6)

where the minimum is computed subject to constraints (3), (4) and (5). Obviously zGL 󰀊zQAP. Using the same bounding strategy it is also possible to obtain a lower bound to thevalue of the completion of a partial assignment. In fact, suppose that the index set 󰀋 = {1, 2,... , n} is partitioned into two subsets 󰀋1 and 󰀋2, corresponding to the indices of the alreadyassigned facilities and to the indices of the still unassigned facilities, respectively.

Similarly, suppose that the index set 󰀌 = {1, 2, ... , n} is partitioned into two subsets 󰀌1 and󰀌2, corresponding to the indices of the already assigned locations and to the indices of thestill unassigned locations, respectively. Then, equation (2) can be rewritten as :

5

zQAP = min z =

i,h󰀂󰀃1j,k󰀂󰀄1

󰀄

i,h󰀂󰀃2j,k󰀂󰀄1

󰀄

󰀄

󰀄

dih fjk xij xhk +

i,h󰀂󰀃1j,k󰀂󰀄2

󰀄

dih fjk xij xhk +

i,h󰀂󰀃2j,k󰀂󰀄2

󰀄

󰀄

󰀄

dih fjk xij xhk +dih fjk xij xhk

(2󰀍)

Notice that the first term of the objective function is now a known constant, z1, and the fourthterm is a reduced QAP instance to which formula (6) can be applied to obtain a bound z4. Alower bound z23 to the value of the second and third terms can be obtained (Burkard, 1984)by solving an assignment problem defined over a cost matrix [󰀎lm], l󰀇󰀋2, m󰀇󰀌2, where

󰀎lm =

i󰀂󰀃1j󰀂󰀄1

󰀄󰀄

( dil fjm + dli fmj )

(7)

A lower bound to the completion cost of a partial assignment can be thus computed as

zLB = z1 + z23 + z4

(8)

On the basis of these results to compute the attractiveness of a coupling (i,j), i󰀇󰀋2, j󰀇󰀌2 wesimply compute formula (8) for a partial assignment where, apart from the already specifiedcouplings, we also tentatively locate facility i in location j. Therefore we tentatively set 󰀋1 =󰀋1 󰀏 {i}, 󰀌1 = 󰀌1 󰀏 {j}, 󰀋2󰀐= 󰀋2\\󰀋1, and 󰀌2󰀐= 󰀌2\\󰀌1, compute zLB accordingly and set 󰀉ij= zLB.

As an example we consider Nugent's problem of order 5 (Nugent et al., 1968), a problemarising in a hospital layout location context, with the distance D and flow F matrices shownbelow.

01123

10212

12012

21101

322 10

05241

50302

23000

40005

12050

D =F =

6

The following execution trace shows how a solution is constructed. Assume for simplicitythat solutions are constructed assigning facilities to locations of increasing indices, that is,first a facility to assign to location 1 is chosen, then the facility to assign to location 2, and soon. The construction goes on as follows. At the root node no facility is assigned, so there are5 possible assignments of facilities to location 1, whose costs are:

1) z1=0, z12=32, z4=222) z1=0, z12=24, z4=283) z1=0, z12=10, z4=434) z1=0, z12=18, z4=325) z1=0, z12=18, z4=33

The corresponding 5 lower bounds are therefore:

zLB= 54 52 53 50 51

The choice goes to assigning facility 4 to location 1.

At the second level one needs to define the assignment to location 2. Being one facilityassigned, only 4 possibilities remain, whose costs are:

1) z1= 8, z12=32, z4=102) z1= 0, z12=56, z4= 63) 3) z1= 0, z12=42, z4=185) z1=10, z12=16, z4=24

The corresponding 4 lower bounds are therefore:

zLB= 50 62 60 50

The choice goes to assigning facility 1 to location 2.

At the third level one needs to define the assignment to location 3. The 3 possibilities remain,have the following costs:

2) z1=28, z12=46, z4=03) z1=16, z12=50, z4=44) z1=22, z12=22, z4=6

The corresponding 3 lower bounds are therefore:

7

zLB= 74 70 50

Facility 5 is thus chosen for location 3. The two remaining assignments are then consideredexplicitly, i.e., without going through lower bound computations.

One can thus find the complete permutation: activity 4 is assigned to node 1; activity 1 tonode 2 and so on, obtaining the permutations (4,1,5,2,3) of cost equal to 50.

In the Ant System the permutation is constructed probabilistically, using the Monte Carlomethod, on the basis both of the 󰀉ij values and of the values of the 󰀈ij variables, representingthe trace levels. We define in fact 󰀈ij(t+1) as the trace intensity (pheromone in the case of realants) associated to the location i - activity j coupling.

The population has m ants, with k the generic ant (k = 1, ... , m). The probability that the k-thant assigns activity j to location i is given by

󰀖󰀅󰀈ij(t)󰀘(1󰀗󰀖)󰀅󰀉ij󰀔

if j󰀕tabuk󰀑󰀑󰀄󰀁󰀖󰀅󰀈ir(t)󰀘(1󰀗󰀖)󰀅󰀉ir󰀂k

pij(t)󰀆󰀓

󰀑r󰀅tabuk󰀑0otherwise󰀒

with 0 󰀊 󰀖 󰀊 1.

In constructing the permutation we start from the location of index 1 and we assign a facilityto it by choosing probabilistically from all the available facilities; at the second step weassign to the second location a facility by choosing probabilistically among those that werenot already assigned, and so on. The procedure is repeated for all n locations. The solutionconstruction is repeated m times, as many times as there are ants in the population.

The parameter 󰀖 allows the user to define the relative importance of the trace 󰀈ij(t) with

k

respect to the desirability 󰀉ij. Thus the probability pij(t) is a compromise between the

(9)

desirability of a coupling (as indicated by the lower bound to the cost of a solution containing

8

that assignment) and the trace intensity (if there was already a high \"passage\" of ants oncoupling (i,j) then this coupling is probably very desirable).

Trail levels are updated after all the ants have constructed their solutions. The update is madeaccording to the following equation

󰀂ij(t+1) = 󰀃󰀂ij(t)+󰀄󰀂ij

(10)

where 󰀙 is a coefficient which represents the trace's persistence (1-󰀙 represents theevaporation) and

󰀄󰀂ij=

k󰀁1

󰀄

m

󰀄󰀂ij

k

(11)

󰀚󰀈ijk being the quantity of trace left on the coupling (i,j) by the k-th ant at the end of theconstruction of its permutation. The trace's initial intensity, 󰀈ij(0), can be set to a small andpositive arbitrary value.

The coefficient 󰀙 must be fixed to a value < 1 to avoid an unlimited accumulation of trace.Concerning the quantity of trace left by the ants, different choices for the calculation of 󰀚󰀈ijkdetermine the realization of slightly different algorithms. In the current version of the AntSystem 󰀚󰀈ijk is given by the value Q/Lk if the k-th ant has chosen coupling (i,j), and by thevalue 0 otherwise: Q is the current upper bound, i.e., the best solution found at the currentiteration, while Lk is the value of the objective function obtained by the k-th ant.

In this way the best solutions (with a corresponding low Lk value) must be characterized bymore trace on the couplings which determine low values of the objective function.

The basic algorithm, which uses the calculation of the bounds and which we will indicate byAS, is the following.

9

1.t:=0

Initialize the trace matrix

Calculate the upper and lower bounds for the whole problem and thedesirabilities 󰀆ijPut m ants on node 12.For k:=1 to m

Repeat {for each location}

Choose, with probability given by equation (9), the facility toassign from those not yet assigned.

Put the chosen facility in the tabu list of the k-th ant

Until the tabu list is full End-forFor k:=1 to m

Carry the solution to its local optimum and compute Lk

{the local search procedure is described at the end of this Section}Update the best permutation foundEnd-for

3.For each coupling (i,j) calculate 󰀇tij according to equation (11)

Update the trace matrix according to equation (10)4.If not (END_TEST)

Empty the tabu lists of all the antsgoto 2Else

Print the best permutation and STOP

{this cycle is repeated n times}

The END_TEST is usually made either on a maximum number of iterations (steps from 2 to5) or on a maximum CPU time allowed.

The algorithm's performance depends on the values of parameters 󰀙 (trace persistencecoefficient), 󰀖 (importance of the trace), and m (number of ants). An experimental analysisfor parameters setting will be presented in Section 3.

10

One can calculate an estimate of the complexity of the Ant System algorithm. After theinitializations, of complexity O(n3) as it implies the solution of a linear assignment problem,one must choose which facility will be assigned to the currently considered location:probabilities are calculated according to equation (9) and the choice in probability is madebetween the facilities not yet assigned; the whole has complexity O(n2). To construct anentire permutation one must thus perform O(n3) operations. Each complete iteration (m ants)thus requires a number of operations O(m·n3). When all the ants have constructed theirsolution the trace matrix must be updated: O(n2) operations are required for this updating.The total complexity of an iteration of the algorithm is thus O(m·n3).

As it is the case for most constructive heuristics (see for example GRASP, Li et al., 1994)also for the Ant System efficiency improvements can be achieved by using a local searchprocedure as a standard element of the overall algorithm. We thus designed a two-phasealgorithm. The first phase constructs solutions one element after the other, following the antpath. When an ant has constructed its basic permutation, a second phase of local search (seestep 2) is activated and the trace is then added to the common data structure.

The local search procedure we implemented is a simple deterministic procedure. The cost ofall the possible exchanges is evaluated starting from the permutation obtained by the ant andchoosing the exchange which most improves the objective function (see (Taillard, 1990) foran efficient implementation of the variation due to an exchange).The local search procedure is then the following.

Change:=true

While (change=true) do

Explore the neighborhood of solution s(k) constructed by ant kand save the best adjacent solution s'(k)

If f(s'(k))11

else change:=false

End-while

The complete exploration of the neighborhood of a solution requires a number of operationsO(n2): in fact the neighborhood consists of n(n-1)/2 permutations which can be obtained withexchanges of pairs of elements and evaluating the cost variation, once initialized the relevantdata structures, requires a constant operation time (Taillard, 1990); the local search step, formedium-large problems, could become rather onerous in terms of computation time.

3. Experimental results

The algorithm presented in this paper was coded in Fortran 77 and tested on a Pentium 166MHz machine, running under DOS. The computational testing of the new algorithm wascarried out applying the code to standard test problems from the literature, and comparing theresults to those of an established heuristic, running under identical experimental conditions.Before comparing our code, we had to identify a good parameter setting. As a completeanalysis of the model which suggests the optimum values of the parameters in each situationhas not been developed, we performed several simulations, testing the algorithm on 5different problems with various values of the control parameters 󰀖 (importance of the trace)and 󰀙 (trace persistence coefficient). We also studied how the number m of ants can influencethe overall performance.

The problems chosen for the purpose of setting the algorithm parameters were: the Nugentproblems (Nugent et al., 1968) of dimension from 15 to 30, the Elshafei problem (Elshafei,1977) of dimension 19, and a Krarup problem of dimension 30 (Krarup and Pruzan, 1978).The optimal solution is known for all the problems up to dimension 20, while for the largerones (Nugent 30 and Krarup 30) the best solutions found in the literature, as reported byBurkard et al. (1994), were considered for the comparison.

12

We tested various values for each parameter (in a cœteris paribus framework) on 5 differentsimulations for each choice.

The values tested were: 󰀖={0.3, 0.5, 0.9} and 󰀙={0.7, 0.9, 0.95, 0.99}. We kept 󰀖 = 0.5, 󰀙 =0.9 as default values.

As well as solving the problems, we were also interested in studying the behavior of the antpopulation with regard to a possible \"stagnationhe same solution: this situation indicates that the system has stopped exploring newpossibilities and that the best solution found up to that point will probably not be improvedany further. With some parameter values it was observed that, after many cycles, all the antsmade the same couplings despite the algorithm's stochastic nature: this behavior is due to amuch greater trace level on some couplings than on others. From this high trace level itfollows that the probability that an ant chooses a new coupling is very low and thusstagnation is produced.

The value 0.9 for 󰀖 (independent of the other parameters) quickly led the ant population tostagnation around the sub-optimum solutions. With parameter 󰀖 at value 0.5 good solutionswere found for all the problems (about 0% to 3% away from the best solution known),without observing stagnation of the population: this means that at each cycle new solutionsbelonging to a promising subset were tried.

Low values of parameter 󰀙 reduce the algorithm's efficiency: it takes longer to find goodsolutions; the best results were obtained for 󰀙 = 0.95.

The number of ants used does not seem to have a decisive influence on the overallperformance, on condition that a quantity at least the same as the dimension (n) of theproblem is used. This agrees with results obtained by a previous version of the Ant Systemapplied to the TSP (Dorigo et al., 1996).

13

With the most effective parameters (󰀖 = 0.5, 󰀙 = 0.95, m = n) the basic algorithm AS foundthe optimal or best known solutions of all problems.

Table 1 gives the best known results, the Gilmore-Lawler lower bound, the average of theobjective function of 500 randomly generated solutions, and the best results given by the AntSystem in 10 minutes runs.

TABLE 1.Best known results (Best), Gilmore-Lawler lower bound (GL bound), random

average value (Random), and results obtained by the Ant System (AS) for theproblems examined

Nugent(15)Best1150GL bound963Random1588AS1150Nugent(20)2570205734032570Nugent(30)6124453981206124Elshafei(19)17212548119719005899304017212548Krarup(30a)889006836013464188900To evaluate the performance of the algorithm proposed, we compared it with one of the bestperforming metaheuristics so far proposed for the QAP, namely GRASP, in the versionpresented by Li et al. (1994). Both the Ant System and GRASP were run for 10 minutes oneach problem instance.

The comparative computational experiments were carried out on problem instances takenfrom the QAPLIB library (Burkard et al., 1994), plus one instance (UFFICI), which will beintroduced in Section 4. In order to have a significant test suite, we used all instances of theQAPLIB database (by the time of writing of this paper) containing problem of dimension 20to 40: lower dimensions imply too easy problems, bigger dimensions lead to the need ofaugmenting the time limit of 10 minutes in order to have meaningful results.

For GRASP, the parameters used were the same as those that were used in Li et al. (1994),that is 󰀖 = 0.5 and 󰀛󰀐= 0.1, except for MaxIter, which was set to 2048 as in Li et al. (1994).

14

All experiments were run on the same Pentium PC 166 MHz machine mentioned at thebeginning of this Section. The results are presented in Table 2, which shows the followingcolumns:󰀜 PROBL:󰀜 GL:

problem identifier.Gilmore and Lawler bound.

󰀜 OPT/BK:optimal or best known solution.

󰀜 GRASP-best: best result obtained by GRASP over 5 runs of 10 minutes each.󰀜 GRASP-%error: percentage error of the best solution obtained by GRASP.

󰀜 GRASP-t.best: average, over 5 runs, of the CPU time (in seconds) needed by GRASP to

produce its best solutions.

󰀜 ANT-best:best result obtained by the Ant System over 5 runs of 10 minutes each.󰀜 ANT-%error: percentage error of the best solution obtained by the Ant System.

󰀜 ANT-t.best: average, over 5 runs, of the CPU time (in seconds) needed by the Ant System

to produce its best solutions.

The last two rows of Table 2 present:AVG

average percentage distance from the optimum (or best known) solutioncomputed over all 45 problems;

MAX

maximal percentage distance from the optimum (or best known) solutioncomputed over all 45 problems.

15

TABLE 2. Comparison of results obtained by GRASP and by the Ant System.

PROBLGLOPT/BKbestGRASP%errort.bestbestANT%errort.bestBUR26ABUR26BBUR26CBUR26DBUR26EBUR26FBUR26GBUR26HCHR20ACHR20BCHR20CCHR22ACHR22BCHR25AESC32AESC32BESC32CESC32DESC32EESC32FESC32GESC32HHAD20LIPA20ALIPA20BLIPA30ALIPA30BLIPA40ALIPA40BKRA30AKRA30BNUG20NUG30ROU20SCR20STE36ASTE36BSTE36CTAI20ATAI25ATAI30ATAI35ATAI40ATHO30THO40UFFICIAVGMAX

51894305426670542667036269503817852381785251655505426795542679536094703821225382122551558205386879538687936012903782044378204493689901011717210117172654790070986587098658215021922232219622982434860114142141425924615662985936619463542765379638843513013296168168350642642106200200022022066257438438616669226922366736833683270762707627076131471317813178151426151426151426314973153831893476581476581476581683608890088900690659142091710205725702570453961246150599948725522725522867661100301100307124952696988653158521599863936308239110831275258067470348270348296241711672561182914150469018181461846888195121024220022467946249285031393703208452905781499361499361438042405162433202098213394163394160,000,000,000,000,000,000,000,001,825,920,002,312,582,321,540,000,000,000,000,000,000,000,000,000,000,000,001,130,000,000,320,000,420,000,001,810,920,890,001,341,581,902,200,001,170,000,665,92

11,38542667059,4538178525,16542679515,12382122517,6353868795,053782044222,581011717237,587098658509,452192195,0023629,2314142200,666156213,416254114,9537967,031302,801680,006421,922000,0020,0020,0063,414382,8069220,9936830,662707646,43131787,31151426306,38318596,21476581292,0388900267,80914202,532570522,976124164,55725522157,47110030275,779598179,6215892141,878265934483,80703482354,511173672264,621844676531,322461764324,843203836215,88149936184,39242108249,393394160,000,000,000,000,000,000,000,000,002,790,000,000,970,000,000,000,000,000,000,000,000,000,000,000,000,000,001,020,000,000,000,000,000,000,000,760,250,330,000,551,461,642,050,000,660,000,272,79

21,0735,0319,0919,4020,5311,2318,675,67331,20374,5729,49314,68161,75236,29226,4740,590,082,130,050,080,072,64158,71107,320,0054,850,00281,000,00199,06140,02119,28180,75244,5446,09295,23212,81321,16160,07206,17331,72231,59252,83287,50312,46379,6516

Table 2 shows that, under the mentioned experimental conditions, the Ant System has abetter performance, in terms of quality of the best solution found, than GRASP on theproblem tested: it finds a greater number of best known solutions, it has a smaller averagepercentage error and a smaller maximum error. On no problem, GRASP found a bettersolution which improved over that found by the Ant System. Moreover, the time needed tofind its best solution is on the average slightly smaller for the Ant System (138.99 sec.) thanfor GRASP (143.83 sec.), even though on individual problems GRASP could be moreefficient than the Ant System.

4. A real-world testcase

In this section we propose a real assignment problem, which can be modeled as QAP of order33. The problem is the optimum allocation of services in the offices of a Milan multinationalcompany, originally described in (Maniezzo, et al., 1994)

The offices available are clustered into units, which are the elements of the three followingbuildings:I.

TOWER: a building on six identical floors, each divided into three units, numbered from1 to 18 (three per floor).

II.BUILDING A: a three-floor construction near to the TOWER building, with direct

pedestrian connections at the level of the first two floors (as well as the outside passage)and with three units per floor, numbered from 19 to 27.

III.BUILDING B: a construction with several floors, of which the first three are available

for the company in question, detached from the previous buildings and connected to themby footpaths. Two units are available on each usable floor, numbered from 28 to 33. Thewhole is shown in Figure 1.

17

161310741

171411852

181512963

252219

262320

272421

323028

333129

TOWERBUILDINGABUILDINGB

Figure 1. Position of the units in the three buildings available

The distance matrix is made of the times (in seconds) spent by an employee to move fromlocation i to location h (i, h = 1,...,33).

For simplicity, the distances between the units on the various floors of each building areconsidered as identical, even though sometimes there are mandatory paths which may causesmall differences. The distances are estimated on the basis of the conditions of normalactivity of the offices themselves (waiting times for the service lifts and/or any use ofalternative routes, walkways or stairs).

As \"flow between activities\" we decided to use the number of personal contacts necessary onaverage in a week by the employees of various offices, weighted according to thequalification of the person involved (the employees were assigned weight 1 and the managersweight 2), thus trying to correlate the movements to the effective burden in terms of workingcosts. The matrix of the flows between the various activities was obtained by quali-quantitative indications obtained from all the managers of the various services. The distanceand flow matrices are reported in the Appendix.

The objective function of the permutation (3, 4, 5, 14, 16, 17, 25, 26, 15, 24, 8, 9, 10, 2, 11,1, 6, 7, 29, 31, 30, 18, 22, 23, 20, 21, 19, 27, 28, 32, 33, 12, 13) corresponding to the current

18

location of the offices in the units was initially calculated: it produces a value of 438114man-sec per week (󰀝 121.7 man-hours).

If this datum is compared with the average value of a random arrangement (565541 man-sec,calculated as the average between 100 permutations generated at random), one can concludethat the actual logistic situation allows a \"saving\" of about 22.5% as compared to a randomallocation.

The best permutation found with the Ant System algorithm, as reported in the last row ofTable 2, has a value of 339416 man-sec (󰀝 94.3 man-hours). This solution is 22.5% betterthan the current logistic situation (obviously this datum must be taken with due care, as thecurrent assignment derives not only from cost considerations, but also from other lessquantifiable objectives such as personal preferences, prestige of a location, … ).

5. Conclusions

In this work we presented a distributed heuristic algorithm, the Ant System, applied to theQuadratic Assignment Problem.

The main point in each distributed system is the definition of the communication procedureamong agents. In our algorithm a set of ants communicates by modifying the problem'srepresentation, as at each step of the processing each ant leaves a sign of its activity whichchanges the probability with which the decisions will be made in future. The idea is that if anant in a given state must choose between different options and, having made a choice, thatchoice results to be particularly good, then in the future that choice must appear moredesirable whenever the state and the options are the same.

The ants are given a heuristic to guide the initial steps of the computation process, when theinformation on the problem structure given by the trace has not yet accumulated. This initial

19

heuristic then automatically loses importance (by means of trace accumulation) when theexperience acquired by the ants, saved in the trace matrix, grows.

The result presented in this work is the use of an autocatalytic process as a method foroptimization and learning. The autocatalytic process of an individual ant would almostalways converge very quickly to a sub-optimum solution; the interaction of manyautocatalytic processes can instead lead to convergence towards a region of the spacecontaining good solutions, so that a very good solution can be found (without however beingstuck on it). In other words, the ant population does not converge on a single solution, but ona set of (good) solutions; the ants continue their search to further improve the best solutionfound.

The results obtained showed the Ant System's competitive performance on all test problems.

REFERENCES

R.E.Burkard. Quadratic Assignment Problems, European Journal of Operational Research,

15, 1984, 283–289.

R.E.Burkard, S.E.Karisch, F.Rendl. QAPLIB - A Quadratic Assignment Problem Library,

Technical Report n.287, Technische Universität Graz, 1994.

A.Colorni, M.Dorigo and V. Maniezzo. Distributed Optimization by Ant Colonies,

Proceedings of ECAL91 - European Conference on Artificial Life, Paris, France,Elsevier Publishing, 1991, 134–142.

A.Colorni, M.Dorigo and V. Maniezzo. An Investigation of some Properties of an Ant

Algorithm, Proceedings of the Parallel Problem Solving from Nature Conference(PPSN 92), Brussels, Belgium, Elsevier Publishing, 1992, 509–520.

J.L.Denebourg, J.M.Pasteels and J.C.Verhaeghe. Probabilistic Behavior in Ants: a Strategy

of Errors?, Journal of Theoretical Biology, 105, 1983, 259–271.

20

M. Dorigo, V. Maniezzo, A. Colorni, Ant System: optimization by a colony of cooperating

agents. IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics,26(1), 1996, 29-41.

A.E.Elshafei. Hospital Layout as a Quadratic Assignment Problem, Operations Research

Quarterly, 28, 1977, 167–179.

P.Gilmore. Optimal and suboptimal algorithms for the quadratic assignment problem, Journal

of SIAM, 10, 1962, 305-313.

T.C.Koopmans and M.J.Beckmann. Assignment Problems and the Location of Economic

Activities, Econometrica, 25, 1957, 53–76.

J.Krarup and P.M.Pruzan. Computer Aided Layout Design, Mathematical Programming

Study, 9, 1978, 85–94.

E.Lawler. The quadratic assignment problem, Management Science, 9, 1963, 586-599.Y.Li and P.M.Pardalos. Parallel algorithms for the quadratic assignment problems. In

P.M.Pardalos (ed.) Advances in optimization and parallel computing, Elsevier, 1992,177-189.

Y.Li, P.M.Pardalos, and M.G.C.Resende. A greedy randomized adaptive search procedure for

the quadratic assignment problem. In P.M.Pardalos and H.Wolkowicz (eds), Quadraticassignment and related problems, DIMACS Series in Discrete Mathematics andTheoretical Computer Science, 16, 1994, 237-261.

V.Maniezzo, L.Muzio, A.Colorni, M.Dorigo. Il sistema formiche applicato al problema

dell’assegnamento quadratico. Technical Report No. 94-058, Politecnico di Milano,Italy, 1994, in Italian.

V.Maniezzo, A.Colorni and M.Dorigo. Algodesk: an Experimental Comparison of Eight

Evolutionary Heuristics Applied to the Quadratic Assignment Problem, EuropeanJournal of Operational Research, 81, 1995, 188-205.

21

C.E.Nugent, T.E.Vollman and J.Ruml. An Experimental Comparison of Techniques for the

Assignment of Techniques to Locations, Operations Research, 16, 1968, 150–173.P.M.Pardalos, H.Wolkowicz (eds.). Quadratic Assignment and Related Problems, DIMACS

series, American Mathematical Society, vol. 16, 1994, 555-565.

S.Sahni and T. Gonzales. P-complete approximation problems, Journal of ACM, , 197623,

555–565.

E.Taillard. Robust Taboo Search for the Quadratic Assignment Problem, Report ORPW

90/10, DMA Swiss Federal Institute of Technology of Lousanne, 1990.

22

Appendix: distance and flow matrices for the Italian company problem

Distance matrix

0 9 12 54 56 60 66 68 72 78 80 84 90 92 96 102 104 108 40 40 43 82 82 85 104 104 107 234 236 246 248 258 260 0 15 56 58 62 68 70 74 80 82 86 92 94 98 104 106 110 42 42 45 84 84 87 106 106 109 236 238 248 250 260 262 0 60 62 66 72 74 78 84 86 90 96 98 102 108 110 114 46 46 49 88 88 91 110 110 113 240 242 252 254 264 266 0 9 12 54 56 60 66 68 72 78 80 84 90 92 96 82 82 85 40 40 43 92 92 95 246 248 258 260 270 272 0 15 56 58 62 68 70 74 80 82 86 92 94 98 84 84 87 42 42 45 94 94 97 248 250 260 262 272 274 0 60 62 66 72 74 78 84 86 90 94 98 102 88 88 91 46 46 49 98 98 101 252 254 264 266 276 278 0 9 12 54 56 60 66 68 72 78 80 84 94 94 97 82 82 85 134 134 137 258 260 270 272 282 284 0 15 56 58 62 68 70 74 80 82 86 96 96 99 84 84 87 136 136 139 260 262 272 274 284 286 0 60 62 66 72 74 78 84 86 90 100 100 103 88 88 91 140 140 143 264 266 276 278 288 290 0 9 12 54 56 60 66 68 72 106 106 109 94 94 97 146 146 149 270 272 282 284 294 296 0 15 56 58 62 68 70 74 108 108 111 96 96 99 148 148 151 272 274 284 286 296 298 0 60 62 66 72 74 78 112 112 115 100 100 103 152 152 155 276 278 288 290 300 302 0 9 12 54 56 60 118 118 121 106 106 109 158 158 161 282 284 294 296 306 308 0 15 56 58 62 120 120 123 108 108 111 160 160 163 284 286 296 298 308 310 0 60 62 66 124 124 127 112 112 115 164 164 167 288 290 300 302 312 314 0 9 12 130 130 133 118 118 121 170 170 173 294 296 306 308 318 320 0 15 132 132 135 120 120 123 172 172 175 296 298 308 310 320 322 0 136 136 139 124 124 127 176 176 179 300 302 312 314 324 326 0 6 8 60 60 63 72 72 75 192 194 204 206 216 218 0 6 60 60 63 72 72 75 192 194 204 206 216 218 0 63 63 66 75 75 78 195 197 207 209 219 221 0 6 8 60 60 63 204 206 216 218 228 230 0 6 60 60 63 204 206 216 218 228 230 0 63 63 66 207 209 219 221 231 233 0 6 8 216 218 228 230 240 242 0 6 216 218 228 230 240 242 0 219 221 231 239 243 245 0 8 70 72 82 84 0 72 74 84 86 0 8 70 72 0 72 74 0 8 0

23

Flow matrix

0 10 20 4 7 24 30 6 8 2 4 6 5 10 4 10 0 14 6 6 0 10 0 4 12 4 4 1 10 0 0 0 0 0 2 1 1 4 8 2 2 0 4 0 0 4 2 2 0 6 2 2 0 2 0 0 0 0 2 1 10 0 4 0 0 0 13 7 20 24 10 10 0 2 4 0 10 0 4 1 10 2 4 1 4 1 2 2 7 0 0 36 2 0 0 0 0 8 7 2 2 2 0 0 1 0 4 0 0 0 4 0 0 0 0 0 0 5 3 0 0 5 2 1 0 0 0 2 1 1 1 0 0 0 1 2 0 0 0 3 0 0 0 0 0 0 2 1 0 0 3 0 0 0 0 0 20 10 10 4 16 14 9 20 8 12 0 24 8 8 0 10 0 4 6 7 0 0 10 2 0 0 0 0 4 4 0 0 4 3 12 0 0 0 16 0 0 0 0 0 20 24 20 10 7 36 13 20 7 10 0 0 1 0 4 0 8 0 0 0 0 0 0 0 0 0 0 4 0 0 0 4 0 0 0 0 0 1 0 4 0 0 0 0 0 12 0 0 0 0 0 0 4 0 0 0 4 0 0 0 0 0 0 0 0 6 0 10 3 8 0 8 2 8 3 0 0 2 0 1 4 1 0 1 0 0 8 5 4 4 4 0 4 4 2 0 2 0 0 4 0 0 0 2 0 0 0 0 0 3 10 20 4 0 0 4 0 0 0 0 0 4 0 0 0 4 0 2 1 0 0 0 4 0 0 10 24 4 0 6 0 0 4 0 0 0 4 0 2 1 0 0 30 40 20 6 4 4 0 4 0 4 4 5 4 3 10 4 4 1 5 0 10 0 0 4 0 0 0 0 0 4 4 2 0 4 1 4 3 0 0 27 0 0 4 0 4 0 4 4 3 0 0 4 3 2 0 3 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 5 0 30 30 11 30 11 6 6 7 4 4 10 4 4 1 7 0 10 0 10 0 0 4 4 2 0 4 1 4 3 0 0 27 10 0 4 4 2 0 0 4 3 2 0 3 0 0 0 0 0 0 0 0 2 0 0 0 5 0 27 4 4 3 0 0 4 3 2 0 3 0 0 0 0 0 0 1 0 0 0 5 0 10 13 4 3 10 7 4 1 1 0 20 4 1 4 0 0 0 0 0 3 2 13 5 7 3 3 0 0 6 7 10 7 0 0 3 5 7 5 0 0 13 24 11 7 0 20 8 6 0 13 13 0 0 0

24