Published in Volume XVI, 2006, pages 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.

Bibtex

@article{sacscuza:pintea2006sopuaaa,
  title={Solving Optimization Problems using an ACS-based Approach.},
  author={Camelia M. Pintea and Gabriel Negara},
  journal={Scientific Annals of Computer Science},
  volume={16},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2006},
  pages={97--107},
  publisher={``A.I. Cuza'' University Press}
}