ABSTRACT
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
performed 30 experiments using the proposed method (P-ACO) compared to 30 experiments for each ACO variation (AS, EAS, MMAS) resulting in a good performance and reduction of time. The main contribution in this work is the proposed P-ACO approach that combines the use of EAS, AS and MAS in a single method that is more effi cient in fi nding solutions for complex problems, such as the TSP.
