Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Ant models are investigated with the purpose of providing a high-quality performing heuristic for solving the linear ordering problem. Extending the Ant Colony System (ACS) model, the proposed Step-Back Sensitive Ant Model (SBSAM) allows agents to take a 'step back' if it reaches a virtual state modulated by various sensitivity levels to the pheromone trails. An effective exploration of the search space is performed particularly by agents having low pheromone sensitivity while the exploitation of intermediary solutions is facilitated by highly-sensitive ants. Both ACS and SB-SAM techniques compete with existing heuristic methods for linear ordering in terms of solution quality.

REFERENCES

• 1: Camelia Chira , D. Dumitrescu , Camelia M. Pintea, Heterogeneous sensitive ant model for combinatorial optimization, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389120]
• 2: M. Dorigo, L.M. Gambardella, "Ant Colony System: A cooperative learning approach to the traveling salesman problem," IEEE Trans. on Systems, Man, and Cybernetics, 26, 29--41, 1996.
• 3: Carlos G. Garcia , Dionisio Pérez-Brito , Vicente Campos , Rafael Martí, Variable neighborhood search for the linear ordering problem, Computers and Operations Research, v.33 n.12, p.3549-3565, December 2006 [doi>10.1016/j.cor.2005.03.032]
• 4: Manuel Laguna , Rafael Marti , Vicente Campos, Intensification and diversification with elite tabu search solutions for the linear ordering problem, Computers and Operations Research, v.26 n.12, p.1217-1230, Oct. 1999 [doi>10.1016/S0305-0548(98)00104-X]
• 5: M.G.C. Resende, C.C. Ribeiro, "Greedy randomized adaptive search procedures: Advances and applications," Handbook of Metaheuristics, 2nd Edition, Springer, 2008.
• 6: Václav Snášel , Pavel Krömer , Jan Platoš, Evolutionary Approaches to Linear Ordering Problem, Proceedings of the 2008 19th International Conference on Database and Expert Systems Application, p.566-570, September 01-05, 2008 [doi>10.1109/DEXA.2008.94]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms

Keywords:
ant colony optimization, linear ordering