research-article

Evolving an edge selection formula for ant colony optimization

Author:

Andrew RunkaAuthors Info & Claims

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Pages 1075 - 1082

https://doi.org/10.1145/1569901.1570046

Published: 08 July 2009 Publication History

Get Access

Abstract

This project utilizes the evolutionary process found in Genetic Programming to evolve an improved decision formula for the Ant System algorithm. Two such improved formulae are discovered, one which uses the typical roulette wheel selection found in all well-known Ant Colony Optimization algorithms, and one which uses a greedy-style selection mechanism. The evolution of each formula is trained using the Ant System algorithm to solve a small Travelling Salesman Problem (TSP) and tested using larger unseen TSP instances.

References

[1]

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, vol. 26, pp. 29--41, 1996.

Digital Library

Google Scholar

[2]

M. Dorigo, M. Birattari, and T. Stützle, "Ant colony optimization - artificial ants as a computational intelligence technique," IEEE Comput. Intell. Mag, vol. 1, pp. 28--39, 2006.

Digital Library

Google Scholar

[3]

M. Dorigo and L. M. Gambardella, "Ant colony system: a cooperative learning approach to the traveling salesman problem," Evolutionary Computation, IEEE Transactions on, vol. 1, no. 1, pp. 53--66, 1997. {Online}. Available: http://dx.doi.org/10.1109/4235.585892

Digital Library

Google Scholar

[4]

J. C. F. Pujol and R. Poli, "Optimization via parameter mapping with genetic programming," in Parallel Problem Solving from Nature - PPSN VIII, ser. LNCS, vol. 3242. Birmingham, UK: Springer-Verlag, 18-22 Sep. 2004, pp. 382--390.

Google Scholar

[5]

A. H. Wright, "Genetic algorithms for real parameter optimization," in Foundations of Genetic Algorithms. Morgan Kaufmann, 1991, pp. 205--218.

Google Scholar

[6]

A. I. Esparcia-Alcazar and K. C. Sharman, "Evolving recurrent neural network architectures by genetic programming," Faculty of Engineering, Glasgow G12 8QQ, Scotland, Technical Report CSC-96009, 1996.

Google Scholar

[7]

J. C. F. Pujol and R. Poli, "Evolving the architecture and weights of neural networks using a weight mapping approach," University of Birmingham, School of Computer Science, UK, Technical Report CSRP-99-05, 10 Feb. 1999. {Online}. Available: ftp://ftp.cs.bham.ac.uk/pub/tech-reports/1999/CSRP-99-05.ps.gz

Google Scholar

[8]

L. Dio»san and M. Oltean, "Evolving crossover operators for function optimization," in Proceedings of the 9th European Conference on Genetic Programming, ser. Lecture Notes in Computer Science, vol. 3905. Budapest, Hungary: Springer, 10-12 Apr. 2006, pp. 97--108.

Digital Library

Google Scholar

[9]

T. Stutzle and H. Hoos, "Improvements on the ant-system: Introducing the max-min ant system," Journal of Future Generation Computer Systems, vol. 16, pp. 889--914, 2000.

Digital Library

Google Scholar

[10]

J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection (Complex Adaptive Systems). The MIT Press, December 1992.

Digital Library

Google Scholar

[11]

"Genetic programming homepage," July 2008. {Online}. Available: http://www.genetic-programming.com

Google Scholar

[12]

M. O'Neill, R. Poli, W. B. Langdon, and N. F. McPhee, "A field guide to genetic programming," Genetic Programming and Evolvable Machines, march 2008. {Online}. Available: http://dx.doi.org/10.1007/s10710-008-9073-y

Digital Library

Google Scholar

[13]

B. L. Miller and D. E. Goldberg, "Genetic algorithms, tournament selection, and the effects of noise," Complex Systems, vol. 9, pp. 193--212, 1995.

Google Scholar

Cited By

View all

Biswas SNusrat STasnim N(2023)Grid-Based Pathfinding Using Ant Colony Optimization AlgorithmProceedings of Third International Conference on Advances in Computer Engineering and Communication Systems10.1007/978-981-19-9228-5_23(259-269)Online publication date: 18-Mar-2023
https://doi.org/10.1007/978-981-19-9228-5_23
Liu LShi L(2022)Automatic Design of Efficient Heuristics for Two-Stage Hybrid Flow Shop SchedulingSymmetry10.3390/sym1404063214:4(632)Online publication date: 22-Mar-2022
https://doi.org/10.3390/sym14040632
Jagadish TApte OPradeep K(2022)Task Scheduling Algorithms in Fog Computing: A Comparison and Analysis2022 International Conference on Automation, Computing and Renewable Systems (ICACRS)10.1109/ICACRS55517.2022.10029029(483-488)Online publication date: 13-Dec-2022
https://doi.org/10.1109/ICACRS55517.2022.10029029
Show More Cited By

Recommendations

Particle swarm optimizer, ant colony strategy and harmony search scheme hybridized for optimization of truss structures

A heuristic particle swarm ant colony optimization (HPSACO) is presented for optimum design of trusses. The algorithm is based on the particle swarm optimizer with passive congregation (PSOPC), ant colony optimization and harmony search scheme. HPSACO ...
Evolving ant colony optimization based unit commitment

Ant colony optimization (ACO) was inspired by the observation of natural behavior of real ants' pheromone trail formation and foraging. Ant colony optimization is more suitable for combinatorial optimization problems. ACO is successfully applied to the ...
Ant colony optimization for image edge detection
ISPRA'10: Proceedings of the 9th WSEAS international conference on Signal processing, robotics and automation

Ant colony optimization is a population-based metaheuristic that mimics the foraging behavior of ants to find approximate solutions to difficult optimization problems. This paper presents an ACO-based technique for image edge detection. The proposed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

July 2009

2036 pages

ISBN:9781605583259

DOI:10.1145/1569901

General Chair:
Franz Rothlauf
University of Mainz, Germany

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO09

Sponsor:

GECCO09: Genetic and Evolutionary Computation Conference

July 8 - 12, 2009

Québec, Montreal, Canada

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
288
Total Downloads

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

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Biswas SNusrat STasnim N(2023)Grid-Based Pathfinding Using Ant Colony Optimization AlgorithmProceedings of Third International Conference on Advances in Computer Engineering and Communication Systems10.1007/978-981-19-9228-5_23(259-269)Online publication date: 18-Mar-2023
https://doi.org/10.1007/978-981-19-9228-5_23
Liu LShi L(2022)Automatic Design of Efficient Heuristics for Two-Stage Hybrid Flow Shop SchedulingSymmetry10.3390/sym1404063214:4(632)Online publication date: 22-Mar-2022
https://doi.org/10.3390/sym14040632
Jagadish TApte OPradeep K(2022)Task Scheduling Algorithms in Fog Computing: A Comparison and Analysis2022 International Conference on Automation, Computing and Renewable Systems (ICACRS)10.1109/ICACRS55517.2022.10029029(483-488)Online publication date: 13-Dec-2022
https://doi.org/10.1109/ICACRS55517.2022.10029029
Bartashevich PBakurov IMostaghim SVanneschi L(2018)PSO-Based Search Rules for Aerial Swarms Against Unexplored Vector Fields via Genetic ProgrammingParallel Problem Solving from Nature – PPSN XV10.1007/978-3-319-99253-2_4(41-53)Online publication date: 22-Aug-2018
https://doi.org/10.1007/978-3-319-99253-2_4
Swiercz A(2017)Hyper‐Heuristics and Metaheuristics for Selected Bio‐Inspired Combinatorial Optimization ProblemsHeuristics and Hyper-Heuristics - Principles and Applications10.5772/intechopen.69225Online publication date: 30-Aug-2017
https://doi.org/10.5772/intechopen.69225
Sourabh Joshi Sarabjit Kaur (2016)Ant Colony Optimization Meta-heuristic for Solving Real Travelling Salesman ProblemEmerging Research in Computing, Information, Communication and Applications10.1007/978-981-10-0287-8_5(55-63)Online publication date: 10-May-2016
https://doi.org/10.1007/978-981-10-0287-8_5
Lourenço NPereira FCosta E(2015)The Optimization Ability of Evolved StrategiesProgress in Artificial Intelligence10.1007/978-3-319-23485-4_23(226-237)Online publication date: 25-Aug-2015
https://doi.org/10.1007/978-3-319-23485-4_23
Aliehyaei RKhan S(2014)Ant Colony Optimization, Genetic Programming and a hybrid approach for credit scoring: A comparative studyThe 8th International Conference on Software, Knowledge, Information Management and Applications (SKIMA 2014)10.1109/SKIMA.2014.7083391(1-5)Online publication date: Dec-2014
https://doi.org/10.1109/SKIMA.2014.7083391
Ortiz-Bayliss JOzcan EParkes ATerashima-Marin H(2013)A genetic programming hyper-heuristic: Turning features into heuristics for constraint satisfaction2013 13th UK Workshop on Computational Intelligence (UKCI)10.1109/UKCI.2013.6651304(183-190)Online publication date: Sep-2013
https://doi.org/10.1109/UKCI.2013.6651304
Aliehyaei RSmith RVrbsky S(2012)Efficient and effective classification of creditworthiness using ant colony optimizationProceedings of the 50th annual ACM Southeast Conference10.1145/2184512.2184532(83-88)Online publication date: 29-Mar-2012
https://dl.acm.org/doi/10.1145/2184512.2184532
Show More Cited By

View Options

Get Access

Login options

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

Cited By

Recommendations

Particle swarm optimizer, ant colony strategy and harmony search scheme hybridized for optimization of truss structures

Evolving ant colony optimization based unit commitment

Ant colony optimization for image edge detection