IDEAS home Printed from https://ideas.repec.org/a/spr/metcap/v8y2006i1d10.1007_s11009-006-7291-4.html
   My bibliography  Save this article

On the Finite-Time Dynamics of Ant Colony Optimization

Author

Listed:
  • Walter J. Gutjahr

    (University of Vienna)

Abstract

An analytical framework for investigating the finite-time dynamics of ant colony optimization (ACO) under a fitness-proportional pheromone update rule on arbitrary construction graphs is developed. A limit theorem on the approximation of the stochastic ACO process by a deterministic process is demonstrated, and a system of ordinary differential equations governing the process dynamics is identified. As an example for the application of the presented theory, the behavior of ACO on three different construction graphs for subset selection problems is analyzed and compared for some basic test functions. The theory enables first rough theoretical predictions of the convergence speed of ACO.

Suggested Citation

  • Walter J. Gutjahr, 2006. "On the Finite-Time Dynamics of Ant Colony Optimization," Methodology and Computing in Applied Probability, Springer, vol. 8(1), pages 105-133, March.
    • Handle: RePEc:spr:metcap:v:8:y:2006:i:1:d:10.1007_s11009-006-7291-4
    DOI: 10.1007/s11009-006-7291-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11009-006-7291-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s11009-006-7291-4?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Karl Doerner & Walter Gutjahr & Richard Hartl & Christine Strauss & Christian Stummer, 2004. "Pareto Ant Colony Optimization: A Metaheuristic Approach to Multiobjective Portfolio Selection," Annals of Operations Research, Springer, vol. 131(1), pages 79-99, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Walter Gutjahr & Stefan Katzensteiner & Peter Reiter & Christian Stummer & Michaela Denk, 2008. "Competence-driven project portfolio selection, scheduling and staff assignment," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 16(3), pages 281-306, September.
    2. Karl F. Doerner & Vittorio Maniezzo, 2018. "Metaheuristic search techniques for multi-objective and stochastic problems: a history of the inventions of Walter J. Gutjahr in the past 22 years," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 26(2), pages 331-356, June.
    3. Walter J. Gutjahr & Giovanni Sebastiani, 2008. "Runtime Analysis of Ant Colony Optimization with Best-So-Far Reinforcement," Methodology and Computing in Applied Probability, Springer, vol. 10(3), pages 409-433, September.
    4. Gutjahr, Walter J. & Katzensteiner, Stefan & Reiter, Peter & Stummer, Christian & Denk, Michaela, 2010. "Multi-objective decision analysis for competence-oriented project portfolio selection," European Journal of Operational Research, Elsevier, vol. 205(3), pages 670-679, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Boxuan Zhao & Jianmin Gao & Kun Chen & Ke Guo, 2018. "Two-generation Pareto ant colony algorithm for multi-objective job shop scheduling problem with alternative process plans and unrelated parallel machines," Journal of Intelligent Manufacturing, Springer, vol. 29(1), pages 93-108, January.
    2. Jian Xiong & Rui Wang & Jiang Jiang, 2019. "Weapon Selection and Planning Problems Using MOEA/D with Distance-Based Divided Neighborhoods," Complexity, Hindawi, vol. 2019, pages 1-18, November.
    3. Gutjahr, Walter J. & Katzensteiner, Stefan & Reiter, Peter & Stummer, Christian & Denk, Michaela, 2010. "Multi-objective decision analysis for competence-oriented project portfolio selection," European Journal of Operational Research, Elsevier, vol. 205(3), pages 670-679, September.
    4. Pérez, Fátima & Gómez, Trinidad & Caballero, Rafael & Liern, Vicente, 2018. "Project portfolio selection and planning with fuzzy constraints," Technological Forecasting and Social Change, Elsevier, vol. 131(C), pages 117-129.
    5. Mohammad Asghari & Seyed Mohammad Javad Mirzapour Al-E-Hashem & Yacine Rekik, 2022. "Environmental and social implications of incorporating carpooling service on a customized bus system," Post-Print hal-03598768, HAL.
    6. Javier Panadero & Jana Doering & Renatas Kizys & Angel A. Juan & Angels Fito, 2020. "A variable neighborhood search simheuristic for project portfolio selection under uncertainty," Journal of Heuristics, Springer, vol. 26(3), pages 353-375, June.
    7. Luo, Hao & Du, Bing & Huang, George Q. & Chen, Huaping & Li, Xiaolin, 2013. "Hybrid flow shop scheduling considering machine electricity consumption cost," International Journal of Production Economics, Elsevier, vol. 146(2), pages 423-439.
    8. Doerner, K.F. & Gutjahr, W.J. & Hartl, R.F. & Strauss, C. & Stummer, C., 2008. "Nature-inspired metaheuristics for multiobjective activity crashing," Omega, Elsevier, vol. 36(6), pages 1019-1037, December.
    9. Doerner, Karl & Focke, Axel & Gutjahr, Walter J., 2007. "Multicriteria tour planning for mobile healthcare facilities in a developing country," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1078-1096, June.
    10. Shivam Gupta & Sachin Modgil & Samadrita Bhattacharyya & Indranil Bose, 2022. "Artificial intelligence for decision support systems in the field of operations research: review and future scope of research," Annals of Operations Research, Springer, vol. 308(1), pages 215-274, January.
    11. Farhad Hassanzadeh & Hamid Nemati & Minghe Sun, 2013. "Robust Optimization for Interactive Multiobjective Programming with Imprecise Information Applied to R&D Project Portfolio Selection," Working Papers 0194mss, College of Business, University of Texas at San Antonio.
    12. Paolo Giudici & Gloria Polinesi & Alessandro Spelta, 2022. "Network models to improve robot advisory portfolios," Annals of Operations Research, Springer, vol. 313(2), pages 965-989, June.
    13. Hassanzadeh, Farhad & Nemati, Hamid & Sun, Minghe, 2014. "Robust optimization for interactive multiobjective programming with imprecise information applied to R&D project portfolio selection," European Journal of Operational Research, Elsevier, vol. 238(1), pages 41-53.
    14. J. L. Redondo & J. Fernández & P. M. Ortigosa, 2017. "FEMOEA: a fast and efficient multi-objective evolutionary algorithm," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 85(1), pages 113-135, February.
    15. Zhang, Fan & Guo, Ping & Engel, Bernard A. & Guo, Shanshan & Zhang, Chenglong & Tang, Yikuan, 2019. "Planning seasonal irrigation water allocation based on an interval multiobjective multi-stage stochastic programming approach," Agricultural Water Management, Elsevier, vol. 223(C), pages 1-1.
    16. F. Perez & T. Gomez, 2016. "Multiobjective project portfolio selection with fuzzy constraints," Annals of Operations Research, Springer, vol. 245(1), pages 7-29, October.
    17. Masoud Rahiminezhad Galankashi & Farimah Mokhatab Rafiei & Maryam Ghezelbash, 2020. "Portfolio selection: a fuzzy-ANP approach," Financial Innovation, Springer;Southwestern University of Finance and Economics, vol. 6(1), pages 1-34, December.
    18. Fekri, Roxana & Amiri, Maghsoud & Sajjad, Rasoul & Golestaneh, Ramin, 2016. "Optimization of Bank Portfolio Investment Decision Considering Resistive Economy," Journal of Money and Economy, Monetary and Banking Research Institute, Central Bank of the Islamic Republic of Iran, vol. 11(4), pages 375-400, October.
    19. Marques, Adriana Cavalcante & Frej, Eduarda Asfora & de Almeida, Adiel Teixeira, 2022. "Multicriteria decision support for project portfolio selection with the FITradeoff method," Omega, Elsevier, vol. 111(C).
    20. Matthias Ehrgott & Xavier Gandibleux, 2004. "Approximative solution methods for multiobjective combinatorial optimization," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 12(1), pages 1-63, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:metcap:v:8:y:2006:i:1:d:10.1007_s11009-006-7291-4. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.