The Ant System Applied to the Quadratic Assignment Problem.
AbstractIn recent years, there has been growing interest in algorithms inspired by the observation of natural phenomena to define computational procedures that can solve complex problems. In this article, we describe a distributed heuristic algorithm that was inspired by the observation of the behavior of ant colonies, and we propose its use for the Quadratic Assignment Problem. The results obtained in solving several classical instances of the problem are compared with those obtained from other evolutionary heuristics to evaluate the quality of the proposed system.
Introduction
The Quadratic Assignment Problem (QAP) of order n consists in looking for the best
allocation of n activities to n locations, where the terms activity and location should be
considered 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 electronic
circuits, ordering of correlated data in magnetic tapes and others (Burkard, 1984).
Mathematically the problem is defined by three matrices of dimension n # n:
of the distances (between location i and location h);
of the flows (between activity j and activity k);
of the assignment costs (of activity j to location i).
Normally matrices D and F are integer-valued matrices, while the assignment cost c ij of
activity j to location i is usually ignored, as it does not make a significant contribution to the
complexity of solving the problem.
Under these hypotheses, a permutation #: i #(i) can be interpreted as a particular
assignment of activity location
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 locations
to which the activities are assigned by the flow between the two activities, d ih -f #(i)#(h) .
To solve the QAP one must thus find a permutation # of the indices (1,2,.,n) which
minimizes the total assignment cost:
d
z
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 (whose
is assigned to location i and 0 in the other cases) such that:
z
subject to the following constraints
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 and
bound and cutting planes methods: with current hardware, problems of order greater than 20
cannot be solved in an acceptable time (Burkard et al., 1994).
For this reason, in recent years many heuristic algorithms have been proposed which, though
not ensuring that the solution found is the best one, give good results in an acceptable
computation time (Maniezzo et al., 1994).
In this article we propose the use of a new heuristic procedure, improving over an algorithm
originally developed for the TSP, which shows the emergence of global properties following
the mutual interaction among many elementary agents (Colorni et al., 1991, 1992, Dorigo et
al., 1996). In particular we are interested in the distribution of search activity among agents
which can only perform very simple actions, so that we can easily parallelize the
computational effort (see Li, Pardalos, 1992 for a discussion on the effectiveness of
parallelization 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 almost
blind 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 them
when it moves deposits a substance, called pheromone, which can be detected by the other
ants. While an ant with no information moves essentially at random, an ant which follows a
path already followed by others is tempted to follow the already marked path (and the
probability of this to occur depends on the intensity of the trace perceived), in turn leaving
new pheromone which is added to that already existing. The emerging collective effect is a
form of autocatalytic or positive feedback behavior, in that the more ants follow a particular
path, the more attractive this path becomes for the next ants which should meet it. The
process is characterized by a positive feedback; in fact, the probability with which an ant
chooses 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 each
ant'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 made
on ant colonies and is thus called the Ant System. A description of the original version of this
method and of its experimental results when applied to the Traveling Salesman Problem can
be 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 which
uses some characteristics of behavior shown in reality by ant colonies, defining a system of
artificial "ants". The Ant System presented in this paper represents an improvement of the
algorithm described in (Dorigo et al., 1996), from which it differs in several structural
elements.
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 (the
equivalent 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 quantity
of 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, assigning
an activity to each location. When all the ants have constructed their permutations, the best
assignments are rewarded so as to encourage the identification of ever better solutions in the
next cycles.
To satisfy the requirement that the ants assign each activity to a different location, we
associate a data structure, called a tabu list, to each ant. This memorizes the locations already
used and stops the ant assigning them a new activity before a cycle is complete (which thus
identifies a permutation). Once the permutation is completed, the tabu list is emptied and the
ant is free to choose its own couplings again. Let us define tabu k a vector containing the tabu
list for the k-th ant and tabu k (s) as the s-th element of the tabu list for the k-th ant (the
location 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 an
assignment and thus the initial assignment (when there is no trace); the initial situation will
then 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 the
completion of the problem solution and use it as an indicator of the expected proficiency of a
particular 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 the
best effectiveness/computational cost ratio, is the Gilmore and Lawler bound (independently
presented by Gilmore, 1962, and Lawler, 1963). The bound is obtained by computing a value
z GL as
z
#( min
#d ih f jk x hk
where the minimum is computed subject to constraints (3), (4) and (5). Obviously z
GL#
z QAP . Using the same bounding strategy it is also possible to obtain a lower bound to the
value of the completion of a partial assignment. In fact, suppose that the index set
. , n} is partitioned into two subsets # 1 and # 2 , corresponding to the indices of the already
assigned facilities and to the indices of the still unassigned facilities, respectively.
Similarly, suppose that the index set partitioned into two subsets # 1 and
corresponding to the indices of the already assigned locations and to the indices of the
still unassigned locations, respectively. Then, equation (2) can be rewritten as :
z
Notice that the first term of the objective function is now a known constant, z 1 , and the fourth
term is a reduced QAP instance to which formula (6) can be applied to obtain a bound z 4 . A
lower bound z 23 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
li f mj ) (7)
A lower bound to the completion cost of a partial assignment can be thus computed as
z
On the basis of these results to compute the attractiveness of a coupling (i,j), i# 2 , j# 2 we
simply compute formula (8) for a partial assignment where, apart from the already specified
couplings, we also tentatively locate facility i in location j. Therefore we tentatively set #
accordingly and set # ij
z LB .
As an example we consider Nugent's problem of order 5 (Nugent et al., 1968), a problem
arising in a hospital layout location context, with the distance D and flow F matrices shown
below.
The following execution trace shows how a solution is constructed. Assume for simplicity
that 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 so
on. The construction goes on as follows. At the root node no facility is assigned, so there are
5 possible assignments of facilities to location 1, whose costs are:
The corresponding 5 lower bounds are therefore:
z
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 facility
assigned, only 4 possibilities remain, whose costs are:
The corresponding 4 lower bounds are therefore:
z
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:
The corresponding 3 lower bounds are therefore:
z
Facility 5 is thus chosen for location 3. The two remaining assignments are then considered
explicitly, i.e., without going through lower bound computations.
One can thus find the complete permutation: activity 4 is assigned to node 1; activity 1 to
node 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 Carlo
method, on the basis both of the # ij values and of the values of the # ij variables, representing
the trace levels. We define in fact as the trace intensity (pheromone in the case of real
ants) associated to the location i - activity j coupling.
The population has m ants, with k the generic ant m). The probability that the k-th
ant assigns activity j to location i is given by
if
tabu
r
ir
ir
with
0# 1.
In constructing the permutation we start from the location of index 1 and we assign a facility
to it by choosing probabilistically from all the available facilities; at the second step we
assign to the second location a facility by choosing probabilistically among those that were
not already assigned, and so on. The procedure is repeated for all n locations. The solution
construction 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
respect to the desirability # ij . Thus the probability p t
between the
desirability of a coupling (as indicated by the lower bound to the cost of a solution containing
that assignment) and the trace intensity (if there was already a high "passage" of ants on
coupling (i,j) then this coupling is probably very desirable).
Trail levels are updated after all the ants have constructed their solutions. The update is made
according to the following equation
where # is a coefficient which represents the trace's persistence (1-# represents the
evaporation) and
being the quantity of trace left on the coupling (i,j) by the k-th ant at the end of the
construction of its permutation. The trace's initial intensity, # ij (0), can be set to a small and
positive 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 # ij k
determine the realization of slightly different algorithms. In the current version of the Ant
is given by the value Q/L k if the k-th ant has chosen coupling (i,j), and by the
value 0 otherwise: Q is the current upper bound, i.e., the best solution found at the current
iteration, while L k is the value of the objective function obtained by the k-th ant.
In this way the best solutions (with a corresponding low L k value) must be characterized by
more 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 by
AS, is the following.
1. t:=0
Initialize the trace matrix
Calculate the upper and lower bounds for the whole problem and the
desirabilities
ants on node 1
2. For k:=1 to m
Repeat {for each location}
Choose, with probability given by equation (9), the facility to
assign from those not yet assigned.
Put the chosen facility in the tabu list of the k-th ant
Until the tabu list is full {this cycle is repeated n times}
End-for
For k:=1 to m
Carry the solution to its local optimum and compute L k
{the local search procedure is described at the end of this Section}
Update the best permutation found
End-for
3. For each coupling (i,j) calculate #t ij according to equation (11)
Update the trace matrix according to equation (10)
4. If not (END_TEST)
Empty the tabu lists of all the ants
Else
Print the best permutation and STOP
The END_TEST is usually made either on a maximum number of iterations (steps from 2 to
5) or on a maximum CPU time allowed.
The algorithm's performance depends on the values of parameters # (trace persistence
(importance of the trace), and m (number of ants). An experimental analysis
for parameters setting will be presented in Section 3.
One can calculate an estimate of the complexity of the Ant System algorithm. After the
initializations, of complexity O(n 3 ) 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 made
between the facilities not yet assigned; the whole has complexity O(n 2 ). To construct an
entire permutation one must thus perform O(n 3 ) operations. Each complete iteration (m ants)
thus requires a number of operations O(m-n 3 ). When all the ants have constructed their
solution the trace matrix must be updated: O(n 2 ) operations are required for this updating.
The total complexity of an iteration of the algorithm is thus O(m-n 3 ).
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 search
procedure as a standard element of the overall algorithm. We thus designed a two-phase
algorithm. The first phase constructs solutions one element after the other, following the ant
path. When an ant has constructed its basic permutation, a second phase of local search (see
step 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 of
all the possible exchanges is evaluated starting from the permutation obtained by the ant and
choosing the exchange which most improves the objective function (see (Taillard, 1990) for
an 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 k
and save the best adjacent solution s'(k)
If f(s'(k))<f(s(k))
then s(k):= s'(k)
else change:=false
End-while
The complete exploration of the neighborhood of a solution requires a number of operations
in fact the neighborhood consists of n(n-1)/2 permutations which can be obtained with
exchanges of pairs of elements and evaluating the cost variation, once initialized the relevant
data structures, requires a constant operation time (Taillard, 1990); the local search step, for
medium-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 166
MHz machine, running under DOS. The computational testing of the new algorithm was
carried out applying the code to standard test problems from the literature, and comparing the
results 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 complete
analysis of the model which suggests the optimum values of the parameters in each situation
has not been developed, we performed several simulations, testing the algorithm on 5
different 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 influence
the overall performance.
The problems chosen for the purpose of setting the algorithm parameters were: the Nugent
problems (Nugent et al., 1968) of dimension from 15 to 30, the Elshafei problem (Elshafei,
1977) of dimension 19, and a Krarup problem of dimension
The optimal solution is known for all the problems up to dimension 20, while for the larger
ones (Nugent 30 and Krarup 30) the best solutions found in the literature, as reported by
Burkard et al. (1994), were considered for the comparison.
We tested various values for each parameter (in a coeteris paribus framework) on 5 different
simulations for each choice.
The values tested were: #={0.3, 0.5, 0.9} and #={0.7, 0.9, 0.95, 0.99}. We
0.9 as default values.
As well as solving the problems, we were also interested in studying the behavior of the ant
population with regard to a possible "stagnation", a situation in which all the ants reconstruct
the same solution: this situation indicates that the system has stopped exploring new
possibilities and that the best solution found up to that point will probably not be improved
any further. With some parameter values it was observed that, after many cycles, all the ants
made the same couplings despite the algorithm's stochastic nature: this behavior is due to a
much greater trace level on some couplings than on others. From this high trace level it
follows that the probability that an ant chooses a new coupling is very low and thus
stagnation is produced.
The value 0.9 for # (independent of the other parameters) quickly led the ant population to
stagnation around the sub-optimum solutions. With parameter # at value 0.5 good solutions
were 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 solutions
belonging to a promising subset were tried.
Low values of parameter # reduce the algorithm's efficiency: it takes longer to find good
solutions; the best results were obtained for
The number of ants used does not seem to have a decisive influence on the overall
performance, on condition that a quantity at least the same as the dimension (n) of the
problem is used. This agrees with results obtained by a previous version of the Ant System
applied to the TSP (Dorigo et al., 1996).
With the most effective parameters n) the basic algorithm AS found
the optimal or best known solutions of all problems.

Table

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


1. Best known results (Best), Gilmore-Lawler lower bound (GL bound), random
average value (Random), and results obtained by the Ant System (AS) for the
problems examined
Nugent
Nugent
Nugent
Krarup
(30a)
GL bound 963 2057 4539 11971900 68360
Random 1588 3403 8120 58993040 134641
AS 1150 2570 6124 17212548 88900
To evaluate the performance of the algorithm proposed, we compared it with one of the best
performing metaheuristics so far proposed for the QAP, namely GRASP, in the version
presented by Li et al. (1994). Both the Ant System and GRASP were run for 10 minutes on
each problem instance.
The comparative computational experiments were carried out on problem instances taken
from the QAPLIB library (Burkard et al., 1994), plus one instance (UFFICI), which will be
introduced in Section 4. In order to have a significant test suite, we used all instances of the
QAPLIB database (by the time of writing of this paper) containing problem of dimension 20
to 40: lower dimensions imply too easy problems, bigger dimensions lead to the need of
augmenting 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 for MaxIter, which was set to 2048 as in Li et al. (1994).
All experiments were run on the same Pentium PC 166 MHz machine mentioned at the
beginning of this Section. The results are presented in Table 2, which shows the following
columns:
# PROBL: problem identifier.
# GL: 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) solution
computed over all 45 problems;
MAX maximal percentage distance from the optimum (or best known) solution
computed over all 45 problems.


2. Comparison of results obtained by GRASP and by the Ant System.
GRASP ANT
PROBL GL OPT/BK best %error t.best best %error t.best
CHR22A 5924 6156 6298 2,31 200,66 6156 0,00 314,68
ESC32D 106 200 200 0,00 1,92 200 0,00 2,13
KRA30A 68360 88900 88900 0,00 292,03 88900 0,00 199,06
ROU20 599948 725522 725522 0,00 164,55 725522 0,00 244,54
STE36A 7124 9526 9698 1,81 275,77 9598 0,76 295,23
AVG 0,66 0,27

Table

2 shows that, under the mentioned experimental conditions, the Ant System has a
better performance, in terms of quality of the best solution found, than GRASP on the
problem tested: it finds a greater number of best known solutions, it has a smaller average
percentage error and a smaller maximum error. On no problem, GRASP found a better
solution which improved over that found by the Ant System. Moreover, the time needed to
find its best solution is on the average slightly smaller for the Ant System (138.99 sec.) than
for GRASP (143.83 sec.), even though on individual problems GRASP could be more
efficient 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 order
33. The problem is the optimum allocation of services in the offices of a Milan multinational
company, originally described in (Maniezzo, et al., 1994)
The offices available are clustered into units, which are the elements of the three following
buildings:
I. TOWER: a building on six identical floors, each divided into three units, numbered from
1 to
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 them
by footpaths. Two units are available on each usable floor, numbered from 28 to 33. The
whole is shown in Figure 1.

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 from
location i to location h (i,
For simplicity, the distances between the units on the various floors of each building are
considered as identical, even though sometimes there are mandatory paths which may cause
small differences. The distances are estimated on the basis of the conditions of normal
activity of the offices themselves (waiting times for the service lifts and/or any use of
alternative routes, walkways or stairs).
As "flow between activities" we decided to use the number of personal contacts necessary on
average in a week by the employees of various offices, weighted according to the
qualification of the person involved (the employees were assigned weight 1 and the managers
weight 2), thus trying to correlate the movements to the effective burden in terms of working
costs. 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 distance
and 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,
corresponding to the current
location of the offices in the units was initially calculated: it produces a value of 438114
man-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 conclude
that the actual logistic situation allows a "saving" of about 22.5% as compared to a random
allocation.
The best permutation found with the Ant System algorithm, as reported in the last row of

Table

2, has a value of 339416 man-sec (# 94.3 man-hours). This solution is 22.5% better
than the current logistic situation (obviously this datum must be taken with due care, as the
current assignment derives not only from cost considerations, but also from other less
quantifiable 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 the
Quadratic Assignment Problem.
The main point in each distributed system is the definition of the communication procedure
among agents. In our algorithm a set of ants communicates by modifying the problem's
representation, as at each step of the processing each ant leaves a sign of its activity which
changes the probability with which the decisions will be made in future. The idea is that if an
ant in a given state must choose between different options and, having made a choice, that
choice results to be particularly good, then in the future that choice must appear more
desirable 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 the
information on the problem structure given by the trace has not yet accumulated. This initial
heuristic then automatically loses importance (by means of trace accumulation) when the
experience 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 for
optimization and learning. The autocatalytic process of an individual ant would almost
always converge very quickly to a sub-optimum solution; the interaction of many
autocatalytic processes can instead lead to convergence towards a region of the space
containing good solutions, so that a very good solution can be found (without however being
stuck on it). In other words, the ant population does not converge on a single solution, but on
a set of (good) solutions; the ants continue their search to further improve the best solution
found.
The results obtained showed the Ant System's competitive performance on all test problems.



--R

Quadratic Assignment Problems

Distributed Optimization by Ant Colonies
An Investigation of some Properties of an Ant Algorithm
Probabilistic Behavior in Ants: a Strategy of

Hospital Layout as a Quadratic Assignment Problem
Optimal and suboptimal algorithms for the quadratic assignment problem
Assignment Problems and the Location of Economic Activities
Computer Aided Layout Design
The quadratic assignment problem


Il sistema formiche applicato al problema dell'assegnamento quadratico.
Algodesk: an Experimental Comparison of Eight Evolutionary Heuristics Applied to the Quadratic Assignment Problem



Robust Taboo Search for the Quadratic Assignment Problem
Appendix: distance and flow matrices for the Italian company problem Distance matrix
--TR

--CTR
Habibeh Abbasi , Abbas Afshar , Saeed Alimohammadi, Optimum design of water conveyance system by ant colony optimization algorithms, Proceedings of the 5th WSEAS/IASME International Conference on Systems Theory and Scientific Computation, p.232-237, September 15-17, 2005, Malta
Shu-Chuan Chu , John F. Roddick , Jeng-Shyang Pan, Ant colony system with communication strategies, Information SciencesInformatics and Computer Science: An International Journal, v.167 n.1-4, p.63-76, 2 December 2004
Yan Yang , Mohamed S. Kamel, An aggregated clustering approach using multi-ant colonies algorithms, Pattern Recognition, v.39 n.7, p.1278-1289, July, 2006
Shiyan Hu, Key-dependant decomposition based image watermarking, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA
Daniel Merkle , Martin Middendorf, Fast Ant Colony Optimization on Runtime Reconfigurable Processor Arrays, Genetic Programming and Evolvable Machines, v.3 n.4, p.345-361, December 2002
Carlos M. Fernandes , Agostinho C. Rosa , Vitorino Ramos, Binary ant algorithm, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England
Wenbing Tao , Hai Jin , Liman Liu, Object segmentation using ant colony optimization algorithm and fuzzy entropy, Pattern Recognition Letters, v.28 n.7, p.788-796, May, 2007
Stefan Janson , Daniel Merkle , Martin Middendorf , Hossam Elgindy , Hartmut Schmeck, On Enforced Convergence of ACO and its Implementation on the Reconfigurable Mesh Architecture Using Size Reduction Tasks, The Journal of Supercomputing, v.26 n.3, p.221-238, November
Martin Middendorf , Frank Reischle , Hartmut Schmeck, Multi Colony Ant Algorithms, Journal of Heuristics, v.8 n.3, p.305-320, May 2002
Stephen Gilmour , Mark Dras, A two-pronged attack on the dragon of intractability, Proceedings of the Twenty-eighth Australasian conference on Computer Science, p.183-192, January 01, 2005, Newcastle, Australia
Matteo Golfarelli , Vittorio Maniezzo , Stefano Rizzi, Materialization of fragmented views in multidimensional databases, Data & Knowledge Engineering, v.49 n.3, p.325-351, June 2004
Shxyong Jian Shyu , B. M. T. Lin , Tsung-Shen Hsiao, Ant colony optimization for the cell assignment problem in PCS networks, Computers and Operations Research, v.33 n.6, p.1713-1740, June 2006
Zne-Jung Lee , Chou-Yuan Lee, A hybrid search algorithm with heuristics for resource allocation problem, Information SciencesInformatics and Computer Science: An International Journal, v.173 n.1-3, p.155-167,
Anne Wade , Said Salhi, An ant system algorithm for the mixed vehicle routing problem with backhauls, Metaheuristics: computer decision-making, Kluwer Academic Publishers, Norwell, MA, 2004
Alan R. McKendall, Jr. , Jin Shang, Hybrid ant systems for the dynamic facility layout problem, Computers and Operations Research, v.33 n.3, p.790-803, March 2006
M. Solimanpur , Prem Vrat , Ravi Shankar, An ant algorithm for the single row layout problem in flexible manufacturing systems, Computers and Operations Research, v.32 n.3, p.583-598, March 2005
Yi-Liang Xu , Meng-Hiot Lim , Yew-Soon Ong , Jing Tang, A GA-ACO-local search hybrid algorithm for solving quadratic assignment problem, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA
Nicolas Meuleau , Marco Dorigo, Ant colony optimization and stochastic gradient descent, Artificial Life, v.8 n.2, p.103-121, July 2002
Christine Solnon , Serge Fenet, A study of ACO capabilities for solving the maximum clique problem, Journal of Heuristics, v.12 n.3, p.155-180, May       2006
Tseng , Shyi-Ching Liang, A Hybrid Metaheuristic for the Quadratic Assignment Problem, Computational Optimization and Applications, v.34 n.1, p.85-113, May       2006
Kuo-Ching Ying , Ching-Jong Liao, An ant colony system for permutation flow-shop sequencing, Computers and Operations Research, v.31 n.5, p.791-801, April 2004
Subrata , Albert Y. Zomaya, A Comparison of Three Artificial Life Techniques for Reporting Cell Planning in Mobile Computing, IEEE Transactions on Parallel and Distributed Systems, v.14 n.2, p.142-153, February
Antonella Carbonaro , Vittorio Maniezzo, The Ant Colony Optimization paradigm for combinatorial optimization, Advances in evolutionary computing: theory and applications, Springer-Verlag New York, Inc., New York, NY,
Marco Dorigo , Christian Blum, Ant colony optimization theory: a survey, Theoretical Computer Science, v.344 n.2-3, p.243-278, 17 November 2005
Urszula Boryczka , Mariusz Boryczka, Multi-cast ant colony system for the bus routing problem, Metaheuristics: computer decision-making, Kluwer Academic Publishers, Norwell, MA, 2004
Marco Dorigo , Gianni Di Caro , Luca M. Gambardella, Ant algorithms for discrete optimization, Artificial Life, v.5 n.2, p.137-172, April 1999
Geoff Nitschke, Emergence of Cooperation: State of the Art, Artificial Life, v.11 n.3, p.367-396, September 2005
evolutionary computation;combinatorial optimization;knowledge pooling;distributed algorithms;ant system;heuristic algorithms;quadratic assignment problem