High Performance Programming for Soft Computing

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: [e-mail]

* 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 fi 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