1313
A Method Using a Combination A Method Using a Combination
of Ant Colony Optimization of Ant Colony Optimization
Variants with Ant Set Variants with Ant Set
PartitioningPartitioning
Evelia Lizarraga, Oscar Castillo* and José Soria
ABSTRACT
In this paper, we propose an ant’s partition method for Ant Colony
Optimization (ACO), a meta-heuristic that is inspired in ant’s behavior
and how they collect their food. The proposed method equivalently
divides the total number of ants in three different subsets, and each
one is evaluated separately by the corresponding variation of ACO
(AS, EAS, MMAS) to solve different instances of the Traveling Salesman
Problem (TSP). This method is based in the common saying “divide
and conquer” to be applied in the repartition of the work, as the ants
are evaluated in different ways in the same iteration. This method also
includes a stagnation mechanism that stops a certain variation if it is
not working properly after several iterations. This allows us to save
time performing tests and have less overhead in comparison with
the conventional method, which uses just one variation of ACO in all
iterations.
Tijuana Institute of Technology, México.
E-mail: ocastillo@tectijuana.mx
* Corresponding author
A Method Using a Combination of ACOA Method Using a Combination of ACO 283
13.1 Introduction
Nowadays, there are open NP-complete problems where the complexity
to construct the right confi guration of a solution lies in fi nding a possible
solution within a great number of possible combinations. In the past it
was assumed that this kind of problems were impossible to solve since
the feasibility to fi nd the right answer was attached to the idea that an
exhaustive search was needed resulting in the impossibility to fi nd an
answer in a reasonable frame of time. In many cases even when a super
computer was used, the amount of time needed to fi nd a solution was
monumental causing overhead and great computational complexity.
Therefore, NP-hard problems are approached fi nding the solution in a
subset of the decision problem; this means fi nding an optimal solution
using approximate algorithms that can give us good solutions effi ciently;
sacrifi cing nding very good solutions in a polynomial time. One of the
most known examples of this kind of problems is TSP (Traveling Salesman
Problem), which is represented fi guratively as a salesman who wants to
travel from city to city starting in an original point (city) without passing
a city twice before returning home (original city). This is considering the
length between cities as the cost that needs to be minimized. This problem
can be represented as an undirected weight graph where the cities are
the vertices of the graph, paths are graph’s edges and the distance of the
path is the length of the edge. There are many approaches proposed to
solve this problem, one of the most used are meta-heuristics inspired in
biological behavior such as Ant Colony Optimization (ACO) (Dorigo and
Stützle 2004, Dorigo et al. 2006), Genetic Algorithms (GA), Particle Swarm
Optimization (PSO) (Eberhart and Kennedy 1995, Engelbrecht 2005), among
others. These techniques are known to be effi cient in the search for a space
solution providing optimal values. Given that ACO can be represented as
graph, this meta-heuristic is one of the most used to represent and solve
TSP. Dorigo and Stützle proposed the solution of TSP in (Dorigo and
Stützle 2004, Stützle and Hoos 1996, 1999, Stützle and Linke 2002) using
ACO according to the biological information that an ant provides when a
good path is found adding pheromone to the nodes of that specifi c path.
ACO uses the amount of pheromone and heuristic information to fi nd
the probability of the next node, where the heuristic information in this
case (TSP) is the distance between cities. Owing to the fact, that ACO has
many variations in how the pheromone is applied, the way to solve each
problem is narrowed to how a designer uses these variations and how
good is a specifi c variation in a specifi c problem. In this paper, we propose
a strategy to compare these variations, such as Elitist Ant System (EAS), Ant
System (AS), and Max Min Ant System (MMAS) within the same iteration;
hence minimizing the number of tests needed. For this paper, there were

Get High Performance Programming for Soft Computing now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.