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 2-opt and 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}
}