A multi-objective ant colony approach for pareto-optimization using dynamic programming

ABSTRACT

This paper covers a multi-objective Ant Colony Optimization, which is applied to the NP-complete multi-objective shortest path problem in order to approximate Pareto-fronts. The efficient single-objective solvability of the problem is used to improve the results of the ant algorithm significantly. A dynamic program is developed which generates local heuristic values on the edges of the problem graph. These heuristic values are used by the artificial ants.

REFERENCES

• 1: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 2: G. Bol. Deskriptive Statistik. Oldenbourg Verlag, München, 1998.
• 3: C. Coello Coello, V. Veldhuizen, D. Allen, and G. Lamont. Evolutionary Algorithms for Solving Multi-Objective Problems, volume 5 of Genetic algorithms and evolutionary computation. Kluwer, Acad. Publ, New York, NY, 2002.
• 4: E. Dijkstra. A note on two problems in connexion with graphs. Number 1, pages 269--271. Mathematisch Centrum, Amsterdam, The Netherlands, 1959.
• 5: M. Dorigo and L. Gambardella. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1(1):53--66, 1997.
• 6: M. Dorigo, V. Maniezzo, and A. Colorni. The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1):1--13, 1996.
• 7: M. Fischer. Partnerauswahl in Netzwerken -- Ein mehrkriterieller Optimierungsansatz zur Bestimmung effizienter Netzkonfigurationen basierend auf Ant Colony Optimization. Verlag Dr. Kovac, Hamburg, 2008.
• 8: M. Fischer, S. Häckel, and J. Kaminski. Improving Ant Colony Optimization for solving Multiobjective Shortest Path Problems by Using the new Look-Ahead-Heuristic-Concept. In Proceedings of the 22th International Conference on CAD/CAM, Robotics and Factories of the Future (CARS & FOF 2006), Vellore (India), July 19.--22. 2006.
• 9: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 10: M. Guntsch. Ant algorithms in stochastic and multi-criteria environments. PhD thesis, Universität Karlsruhe (TH), 2004.
• 11: P. Hansen. Bicriterion Path Problems. In G. Fandel and T. Gal, editors, Multiple Criteria Decision Making Theory and Application, Lecture notes in economics and mathematical systems 177, pages 109--127, Berlin, Heidelberg, 1980. Springer.
• 12: Steffen Iredi , Daniel Merkle , Martin Middendorf, Bi-Criterion Optimization with Multi Colony Ant Algorithms, Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization, p.359-372, March 07-09, 2001
• 13: J. Jahn. Vector Optimization -- Theory, Applications, and Extensions. Springer, London, 2004.
• 14: K. Miettinen. Nonlinear Multiobjective Optimization, volume 12 of International series in operations research und management science. Kluwer, Acad. Publ, Boston, MA, 1999.
• 15: P. Sera¯ni. Some considerations about computational complexity for multi objective combinatorial problems. In J. Jahn and W. Krabs, editors, Recent Advances and Historical Develpment of Vector Optimization, Lecture notes in economics and mathematical systems 294, page 405, Berlin, 1987. Springer.
• 16: Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

General Terms:
Algorithms, Design, Measurement, Verification

Keywords:
ant colony optimization, dynamic programming, hybridization, multi-objective optimization, pareto-optimization, shortest-path problem