research-article

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

Authors:

Sascha Häckel,

Tobias TeichAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 33 - 40

https://doi.org/10.1145/1389095.1389101

Published: 12 July 2008 Publication History

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]

R. Bellman. Dynamic programming. Princeton Univ. Press, Princeton, 1957.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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]

R. Floyd. Algorithm 97: Shortest Path. Communications of the ACM, 5(6):345, 1962.]]

Digital Library

[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]

S. Iredi, D. Merkle, and M. Middendorf. Bi-Criterion Optimization with Multi Colony Ant Algorithms. In E. Zitzler et al., editor, Proceedings of the First International Conference on Evolutionary Multi-Criterion-Optimization (EMO'01), Lecture Notes on Computer Science 1993, pages 359--372, Zürich, 2001. Springer.]]

Digital Library

[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]

S. Warshall. A Theorem on Boolean Matrices. Journal of the ACM, 9(1):11--12, 1962.]]

Digital Library

Cited By

Sun ZWei MZhang ZQu G(2019)Secure Routing Protocol based on Multi-objective Ant-colony-optimization for wireless sensor networksApplied Soft Computing10.1016/j.asoc.2019.01.03477:C(366-375)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1016/j.asoc.2019.01.034
Chebli SElakkary ASefiani N(2018)Ant Colony Optimization based on Pareto optimality: application to a congested router controlled by PID regulationSystems Science & Control Engineering10.1080/21642583.2018.15093956:1(360-369)Online publication date: 16-Aug-2018
https://doi.org/10.1080/21642583.2018.1509395
Devarajan JPaul Robert T(2018)Swarm Intelligent Approaches for Solving Shortest Path Problems with Multiple ObjectivesCognitive Computing and Information Processing10.1007/978-981-10-9059-2_14(143-156)Online publication date: 7-Apr-2018
https://doi.org/10.1007/978-981-10-9059-2_14
Show More Cited By

Index Terms

A multi-objective ant colony approach for pareto-optimization using dynamic programming
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

A Multi-objective Ant Colony Optimization Algorithm with Local Optimum Avoidance Strategy
Machine Learning for Cyber Security
Abstract
Ant colony optimization (ACO) algorithm has rapid convergence speed and competitive performance in multi-objective optimization. However, for complicated multi-objective problems (MOPs), it faces the issue of the local optimum trap, which hinders ...
Fuzzy goal programming-based ant colony optimization algorithm for multi-objective topology design of distributed local area networks
Abstract
Topology design of a distributed local area network (DLAN) is a complex optimization problem and has been generally modelled as a single-objective optimization problem. Traditionally, iterative techniques such as genetic algorithms and simulated ...
Bi-Objective Ant Colony Optimization approach to optimize production and maintenance scheduling

This paper presents an algorithm based on Ant Colony Optimization paradigm to solve the joint production and maintenance scheduling problem. This approach is developed to deal with the model previously proposed in [3] for the parallel machine case. This ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
626
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sun ZWei MZhang ZQu G(2019)Secure Routing Protocol based on Multi-objective Ant-colony-optimization for wireless sensor networksApplied Soft Computing10.1016/j.asoc.2019.01.03477:C(366-375)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1016/j.asoc.2019.01.034
Chebli SElakkary ASefiani N(2018)Ant Colony Optimization based on Pareto optimality: application to a congested router controlled by PID regulationSystems Science & Control Engineering10.1080/21642583.2018.15093956:1(360-369)Online publication date: 16-Aug-2018
https://doi.org/10.1080/21642583.2018.1509395
Devarajan JPaul Robert T(2018)Swarm Intelligent Approaches for Solving Shortest Path Problems with Multiple ObjectivesCognitive Computing and Information Processing10.1007/978-981-10-9059-2_14(143-156)Online publication date: 7-Apr-2018
https://doi.org/10.1007/978-981-10-9059-2_14
Moncayo–Martínez LZhang DRecio G(2016)Minimising Safety Stock and Lead Time in Production Systems Under Guaranteed-Service Time Models by Swarm IntelligenceMetaheuristics for Production Systems10.1007/978-3-319-23350-5_7(149-166)Online publication date: 2016
https://doi.org/10.1007/978-3-319-23350-5_7
Stefanov PSavic ADobric G(2014)Power system optimization using parallel scenario algorithm2014 IEEE International Energy Conference (ENERGYCON)10.1109/ENERGYCON.2014.6850445(310-317)Online publication date: May-2014
https://doi.org/10.1109/ENERGYCON.2014.6850445
Zaza TRichards A(2014)Ant Colony Optimization for routing and tasking problems for teams of UAVs2014 UKACC International Conference on Control (CONTROL)10.1109/CONTROL.2014.6915216(652-655)Online publication date: Jul-2014
https://doi.org/10.1109/CONTROL.2014.6915216
Corne DReynolds ABonabeau E(2012)Swarm IntelligenceHandbook of Natural Computing10.1007/978-3-540-92910-9_48(1599-1622)Online publication date: 2012
https://doi.org/10.1007/978-3-540-92910-9_48
Bezerra LGoldbarg EBuriol LGoldbarg M(2011)GRACEProceedings of the 6th international conference on Evolutionary multi-criterion optimization10.5555/1987637.1987677(535-549)Online publication date: 5-Apr-2011
https://dl.acm.org/doi/10.5555/1987637.1987677
Reynolds RLiu D(2011)Multi-objective cultural algorithms2011 IEEE Congress of Evolutionary Computation (CEC)10.1109/CEC.2011.5949757(1233-1241)Online publication date: Jun-2011
https://doi.org/10.1109/CEC.2011.5949757

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten