# Scientific Annals of Computer Science

## Solving Optimization Problems using an ACS-based Approach.

Published in Volume XVI, 2006, p. 97-107

Authors: Camelia M. Pintea and Gabriel Negara

#### Abstract

Ant-systems based techniques are using metaheuristics able to solve $\mathcal {NP}$-hard problems. We introduce a technique based on Ant Colony System. It uses an extra-exploration phase in order to improve the quality of the solutions. In our algorithm two ant colonies explore and exploit the searching space in order to find solutions. The first colony is called {\em exploring colony}. Its main goal is to generate partial solutions by imposing strategies for chosing the next steps when exploring the solutions space. The second colony, the {\em exploiting colony}, finds the best solution combining its own experience with information provided by the exploring colony. We apply our technique for solving the Travelling Salesman problem. The solutions are improved using {\em 2-opt} and {\em 3-opt} heuristics. The experiments on problems from {\em TSPLIB}, the Traveling Salesman Problem Library, show encouraging results. The technique could be applied for solving routing, scheduling and other types of optimization problems.

© 2006-2013 FII | Contact: annals at info.uaic.ro