An External Partial Permutations Memory for Ant Colony Optimization | SpringerLink
Skip to main content
Springer Nature Link
Log in

An External Partial Permutations Memory for Ant Colony Optimization

  • Conference paper
Evolutionary Computation in Combinatorial Optimization (EvoCOP 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3448))

Abstract

A novel external memory implementation based on the use of partially complete sequences of solution components from above-average quality individuals over a number of previous iterations is introduced. Elements of such variable-size partial permutation sequences are taken from randomly selected positions of parental individuals and stored in an external memory called the partial permutation memory. Partial permutation sequences are associated with lifetimes together with their parent solutions’ fitness values that are used in retrieving and updating the contents of the memory. When a solution is to be constructed, a partial permutation sequence is retrieved from the memory based on its age and associated fitness value, and the remaining components of the partial solution is completed with an ant colony optimization algorithm. Resulting solutions are also used to update some elements within the memory. The implemented algorithm is used for the solution of a difficult combinatorial optimization problem, namely the quadratic assignment problem, for which significant performance achievements are provided in terms of convergence speed and solution quality.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Dorigo, M., Caro, G.D., Gambardella, L.M.: Ant algorithms for distributed discrete optimization. Artificial Life 5, 137–172 (1999)

    Article  Google Scholar 

  2. Dorigo, M., Caro, G.D.: The ant colony optimization metaheuristic. In: Corne, D., Dorigo, M., Glover, F. (eds.) New ideas in optimization, pp. 11–32. McGraw-Hill, London (1999)

    Google Scholar 

  3. Eggermont, J., Lenaerts, T.: Non-stationary function optimization using evolutionary algorithms with a case-based memory, Technical report, Leiden University Advanced Computer Science (LIACS) Technical Report 2001-11

    Google Scholar 

  4. Ramsey, C.L., Grefenstette, J.J.: Case-based initialization of GAs. In: Forest, S. (ed.) Proceedings of the Fifth International Conference on Genetic Algorithms, San Mateo, CA, pp. 84–91 (1993)

    Google Scholar 

  5. Louis, S., Li, G.: Augmenting genetic algorithms with memory to solve traveling salesman problem. In: Proceedings of the Joint Conference on Information Sciences, Duke University, pp. 108–111 (1997)

    Google Scholar 

  6. Simoes, A., Costa, E.: Using genetic algorithms to deal with dynamic environments: comparative study of several approaches based on promoting diversity. In: Langton, W.B., et al. (eds.) Proceedings of the genetic and evolutionary computation conference GECCO 2002, p. 698. Morgan Kaufmann, New York (2002)

    Google Scholar 

  7. Simoes, A., Costa, E.: Using biological inspiration to deal with dynamic environments. In: Proceedings of the seventh international conference on soft computing MENDEL 2001, Czech Republic (2001)

    Google Scholar 

  8. Acan, A., Tekol, Y.: Chromosome reuse in genetic algorithms. In: Cantú-Paz, E., Foster, J.A., Deb, K., Davis, L., Roy, R., O’Reilly, U.-M., Beyer, H.-G., Kendall, G., Wilson, S.W., Harman, M., Wegener, J., Dasgupta, D., Potter, M.A., Schultz, A., Dowsland, K.A., Jonoska, N., Miller, J., Standish, R.K. (eds.) GECCO 2003. LNCS, vol. 2723, pp. 695–705. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  9. Lewis, J., Hart, E., Ritchie, G.: A comparison of dominance mechanisms and simple mutation on non-stationary problems. In: Eiben, A.E., Back, T., Schoenauer, M., Schwefel, H. (eds.) Parallel Problem Solving from Nature- PPSN V, Berlin, pp. 139–148 (1998)

    Google Scholar 

  10. Montgomery, J., Randall, M.: The accumulated experience ant colony for the traveling salesman problem. International Journal of Computational Intelligence and Applications 3(2), 189–198 (2003)

    Article  Google Scholar 

  11. Guntsch, M., Middendorf, M.: A population based approach for ACO. In: Cagnoni, S., Gottlieb, J., Hart, E., Middendorf, M., Raidl, G.R. (eds.) EvoIASP 2002, EvoWorkshops 2002, EvoSTIM 2002, EvoCOP 2002, and EvoPlan 2002. LNCS, vol. 2279, pp. 72–81. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  12. Guntsch, M., Middendorf, M.: Applying population based ACO for dynamic optimization problems. In: Dorigo, M., Di Caro, G.A., Sampels, M. (eds.) Ant Algorithms 2002. LNCS, vol. 2463, pp. 111–122. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  13. Acan, A.: An External Memory Implementation in Ant Colony Optimization. In: Dorigo, M., Birattari, M., Blum, C., Gambardella, L.M., Mondada, F., Stützle, T. (eds.) ANTS 2004. LNCS, vol. 3172, pp. 73–82. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  14. Stützle, T., Fernandes, S.: New benchmark instances for the QAP and the experimental analysis of algorithms. In: Gottlieb, J., Raidl, G.R. (eds.) EvoCOP 2004. LNCS, vol. 3004, pp. 199–209. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  15. Stützle, T., Dorigo, M.: ACO Algorithms for the Quadratic Assignment Problem. In: Corne, D., Dorigo, M., Glover, F. (eds.) New Ideas in Optimization, pp. 33–50. McGraw-Hill, New York (1999)

    Google Scholar 

  16. Stützle, T.: MAX-MIN ant system for the quadratic assignment problem. Technical Report AIDA-97-04, Darmstadt University of Technology, Computer Science Dept., Intellectics Group (1997)

    Google Scholar 

  17. Stützle, T.: Iterated local search for the quadratic assignment problem. Technical Report AIDA-99-03, Darmstadt University of Technology, Computer Science Dept., Intellectics Group (1999)

    Google Scholar 

  18. Maniezzo, V.: Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. INFORMS Journal on Computing 11(4), 358–369 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  19. Maniezzo, V., Colorni, A., Dorigo, M.: The ant system applied to the quadratic assignment problem. Technical Report IRIDIA/94-28, Universite Libre de Bruxelles (1994)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Engineering Department Gazimagusa, T.R.N.C., Eastern Mediterranean University, Via Mersin 10, Turkey

    Adnan Acan

Authors
  1. Adnan Acan
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institute of Computer Graphics and Algorithms, Vienna University of Technology, Favoritenstraße 9–11/1861, 1040, Vienna, Austria

    Günther R. Raidl

  2. SAP AG, Neurottstr. 16, P.O. Box, Walldorf, Germany

    Jens Gottlieb

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Acan, A. (2005). An External Partial Permutations Memory for Ant Colony Optimization. In: Raidl, G.R., Gottlieb, J. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2005. Lecture Notes in Computer Science, vol 3448. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31996-2_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-31996-2_1

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-25337-2

  • Online ISBN: 978-3-540-31996-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation