Parallel shared memory strategies for ant-based optimization algorithms

ABSTRACT

This paper describes a general scheme to convert sequential ant-based algorithms into parallel shared memory algorithms. The scheme is applied to an ant-based algorithm for the maximum clique problem. Extensive experimental results indicate that the parallel version provides noticeable improvements to the running time while maintaining comparable solution quality to that of the sequential version.

REFERENCES

• 1: S. Alonso, O. Cordon, I. Fernandez de Viana, F. Herrera, "Integrating Evolutionary Computation Components in Ant Colony Optimization," Recent Developments in Biologically Inspired Computing, L.Nunes de Castro, F.J. Von Zuben (Eds.), Idea Group Publishing, 2004, pp. 48--180.
• 2: P. Berman and A. Pelc, "Distributed Fault Diagnosis For Multiprocessor Systems," Proc. of the 20th Annual International Symposium on Fault-Tolerant Computing, Newcastle, UK, 1990, pp. 340--346.
• 3: E. Bonabeau, M. Dorigo, and G. Theraulaz, "Inspiration for Optimization from Social Insect Behavior," Nature, Vol. 406, July 6, 2000, pp. 39--42.
• 4: T. Bui and J. Rizzo, "Finding Maximum Cliques with Distributed Ants," Proc. of the Genetic and Evolutionary Computation Conf., 2004, pp. 24--35.
• 5: T. Bui and G. Sundarraj, "Ant System for the k-Cardinality Tree Problem," Proc. of the Genetic and Evolutionary Computation Conf., 2004, pp. 36--47.
• 6: Thang Nguyen Bui , Lisa C. Strite, An Ant System Algorithm For Graph Bisection, Proceedings of the Genetic and Evolutionary Computation Conference, p.43-51, July 09-13, 2002
• 7: Thang N. Bui , Catherine M. Zrncic, An ant-based algorithm for finding degree-constrained minimum spanning tree, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144000]
• 8: B. Bullnheimer, G, Kotsis, and C. Strauss, "Parallelization Strategies for the Ant System," High Performance Algorithms and Software in Nonlinear Optimization, Kluwer, Dordrecht, 1998, pp. 87--100.
• 9: P. Delisle, M. Krajecki, M. Gravel, and C. Gagne, "Parallel Implementation of An Ant colony Optimization Metaheuristic With OpenMP," Proc. of the 3rd European Workshop on OpenMP (EWOMP'01), Barcelona, Spain, 2001.
• 10: M. Dorigo, "Optimization, Learning and Natural Algorithms," Ph.D. Thesis, Politecnico di Milano, Italy, {in Italian}, 1992.
• 11: Marco Dorigo , Gianni Di Caro, The ant colony optimization meta-heuristic, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
• 12: M. Dorigo and L. Gambardella, "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem," IEEE Trans. on Evol. Computation, 1(1), 1997, pp. 53--66.
• 13: M. Dorigo, L. Gambardella, and E. Taillard, "Ant Colonies for the Quadratic Assignment Problem," Journal of the Operational Research Society, Vol. 50, 1999, pp. 167--176.
• 14: Issmail Ellabib , Paul Calamai , Otman Basir, Exchange strategies for multiple Ant Colony System, Information Sciences: an International Journal, v.177 n.5, p.1248-1264, March, 2007 [doi>10.1016/j.ins.2006.09.016]
• 15: David Geer, Industry Trends: Chip Makers Turn to Multicore Processors, Computer, v.38 n.5, p.11-13, May 2005 [doi>10.1109/MC.2005.160]
• 16: J. Hastad, "Clique Is Hard to Approximate within n1-ë," Acta Mathematica, 182, 1999, pp. 105--142.
• 17: J. Lagarias and P. Shor, "Keller's Cube-Tiling Conjecture Is False In High Dimensions," Bulletin of the American Mathematical Society, 27(2), 1992, pp. 279--283.
• 18: M. Manfrin, M. Birattari, Thomas Stutzle, and M. Dorigo, "Parallel Ant Colony Optimization for the Traveling Salesman Problem," M. Dorigo et al. (Eds.): ANTS 2006, Lecture Notes in Computer Science, 4150, 2006, pp. 224--234.
• 19: V. Maniezzo and A. Carbonaro, "Ant Colony Optimization: An Overview," Essays and Surveys in Metaheuristics, C. Ribeiro editor, Kluwer Academic Publishers, 2001, pp. 21--44.
• 20: René Michel , Martin Middendorf, An ACO algorithm for the shortest common supersequence problem, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
• 21: Martin Middendorf , Frank Reischle , Hartmut Schmeck, Multi Colony Ant Algorithms, Journal of Heuristics, v.8 n.3, p.305-320, May 2002 [doi>10.1023/A:1015057701750]
• 22: Jeff Parkhurst , John Darringer , Bill Grundmann, From single core to multi-core: preparing for a new exponential, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233516]
• 23: David A. Patterson , John L. Hennessy, Computer organization and design (2nd ed.): the hardware/software interface, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 24: Marcus Randall , Andrew Lewis, A parallel implementation of ant colony optimization, Journal of Parallel and Distributed Computing, v.62 n.9, p.1421-1432, September 2002 [doi>10.1006/jpdc.2002.1854]
• 25: John E. Savage , Mohammad Zubair, A unified model for multicore architectures, Proceedings of the 1st international forum on Next-generation multicore/manycore technologies, November 24-25, 2008, Cairo, Egypt [doi>10.1145/1463768.1463780]
• 26: N. Sloane, "Unsolved Problems in Graph Theory Arising from the Study of Codes," Graph Theory Notes of New York, XVIII, 1989, pp. 11--20.
• 27: N. Sloane and F. MacWilliams, "The Theory of Correcting Codes," North Holland, Amsterdam, 1979.
• 28: Thomas Stützle, Parallelization Strategies for Ant Colony Optimization, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.722-731, September 27-30, 1998
• 29: El-Ghazali Talbi , Olivier Roux , Cyril Fonlupt , Denis Robillard, Parallel Ant Colonies for Combinatorial Optimization Problems, Proceedings of the 11 IPPS/SPDP'99 Workshops Held in Conjunction with the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, p.239-247, April 12-16, 1999
• 30: The Beowulf Project. http://www.beowulf.org. Last accessed March 2009.
• 31: MPI - The Message Passing Interface Standard. http://www-unix.mcs.anl.gov/mpi/. Last accessed March 2009.
• 32: OpenMP Architecture Review Board. http://www.openmp.org/specs/. Last accessed March 2009.
• 33: Clique Benchmark Instances. http://www.cs.hbg.psu.edu/benchmarks/. Last accessed March 2009.
• 34: BHOSLIB: Benchmarks with Hidden Optimum Solutions for Graph Problems. http://www.nlsde.buaa.edu.cn/ kexu/benchmarks/graphbenchmarks.htm. Last accessed March 2009.
• 35: Supplemental results. http://www.cs.unm.edu/~tnguyen/Files/Papers/mcsup.pdf. Last accessed March 2009.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

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

General Terms:
Algorithms, Design

Keywords:
MPI, Max Clique, OpenMP, ant-based algorithms, distributed memory, shared memory