CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

A Hybrid Ant Colony Optimization Algorithm using MapReduce for Arc Routing Problem

by Gajanan Aochar, Roshni Ade
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 112 - Number 11
Year of Publication: 2015
Authors: Gajanan Aochar, Roshni Ade
10.5120/19709-1467

Gajanan Aochar, Roshni Ade . A Hybrid Ant Colony Optimization Algorithm using MapReduce for Arc Routing Problem. International Journal of Computer Applications. 112, 11 ( February 2015), 8-12. DOI=10.5120/19709-1467

@article{ 10.5120/19709-1467,
author = { Gajanan Aochar, Roshni Ade },
title = { A Hybrid Ant Colony Optimization Algorithm using MapReduce for Arc Routing Problem },
journal = { International Journal of Computer Applications },
issue_date = { February 2015 },
volume = { 112 },
number = { 11 },
month = { February },
year = { 2015 },
issn = { 0975-8887 },
pages = { 8-12 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume112/number11/19709-1467/ },
doi = { 10.5120/19709-1467 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:49:11.522026+05:30
%A Gajanan Aochar
%A Roshni Ade
%T A Hybrid Ant Colony Optimization Algorithm using MapReduce for Arc Routing Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 112
%N 11
%P 8-12
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Ant colony optimisation (ACO) could be a comparatively new random heuristic approach for determination optimisation issues. Furthermore, This paper extend these implementations with two local search methods and we compare two heuristics that guide the HACO algorithms. However, relatively few results on the runtime analysis of the ACO on the TSP are available. Moreover, we experiment with two different pheromone update strategies. In order to demonstrate this we present an ACO implementation for the travelling salesman problem it requires a larger number of ants and iterations which consume more time. The influence of the parameters controlling the relative importance of pheromone trail versus visibility is also analyzed, and their choice is shown to have an impact on the expected runtime. The main application of the ACO algorithm lies in the field of combinatorial optimization, and the traveling salesman problem (TSP) is the first benchmark problem to which the HACO algorithm has been applied.

References
  1. M. Dorigo and L. M. Gambardella, "Ant colony system: A cooperative learning approach to the traveling salesman problem," IEEE Trans. Evol. Comput. , vol. 1, no. 1, pp. 53–66, Apr. 1997.
  2. M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: Optimization by a colony of cooperating agents," IEEE Trans. Syst. , Man, Cybern. B, Cybern. , vol. 26, no. 1, pp. 29–41, Feb. 1996.
  3. C. Blum, "Ant colony optimization: Introduction and recent trends," Phys. Life Rev. , vol. 2, no. 4, pp. 353–373, Dec. 2005.
  4. M. Dorigo and C. Blum, "Ant colony optimization theory: A survey," Theor. Comput. Sci. , vol. 344, no. 2/3, pp. 243–278, Nov. 2005.
  5. B. Bullnheimer, R. Hartl, and C. Strauss, "A new rank-based version of the Ant System: A computational study," Central Eur. J. Opera. Res. Econ. , vol. 7, no. 1, pp. 25–38, 1999.
  6. T. Stutzle and H. H. Hoos, "Max-min ant system," Future Gener. Comput. Syst. , vol. 16, no. 8, pp. 889–914, 2000.
  7. C. Blum and M. Dorigo, "The hyper-cube framework for ant colony optimization," IEEE Trans. Syst. , Man, Cybern. B, Cybern. , vol. 34, no. 2, pp. 1161–1172, Apr. 2004.
  8. Y. W. Leung and F. Wang, "An orthogonal genetic algorithm with quantization for global numerical optimisation," IEEE Trans. Evol. Comput. , vol. 5, no. 1, pp. 41–53, Feb. 2001.
  9. S. Lin and B. W. Kemighan, "An effective heuristic algorithm for the traveling salesman problem," Oper. Res. , vol. 21, no. 2, pp. 498–516, Mar. /Apr. 1973.
  10. M. Kiuchi, Y. Shinano, R. Hirabayashi, and Y. Saruwatari, "An exact algorithm for the capacitated arc routing problem using parallel branch and bound method," in Proc. Abstr. Spring Nat. Conf. Oper. Res. Soc. Jpn. , 1995, pp. 28–29.
  11. J. M. Belenguer and E. Benavent, "A cutting plane algorithm for the capacitated arc routing problem," Comput. Oper. Res. , vol. 30, no. 5, pp. 705–728, Apr. 2003.
  12. J. Demsar, "Statistical comparisons of classifiers over multiple data sets," J. Mach. Learn. Res. , vol. 7, pp. 1–30, 2006.
  13. J. He, X. Yao, and J. Li, "A comparative study of three evolutionary algorithms incorporating different amount of domain knowledge for node covering problems," IEEE Trans. System.
  14. H. G. Beyer, H. P. Schwefel, and I. Wegener, "How to analyze evolutionary algorithms," Theor. Comput. Sci. , vol. 287, no. 1, pp. 101–130,2002.
  15. C. Witt, "Worst-case and average-case approximations by simple randomized search heuristic," in Proc. 22nd Annu. Symp. Theor. Aspects Comput. Sci. (STACS), LNCS vol. 3404. Stuttgart, Germany, Feb. 2005, pp. 44–56.
  16. D. Sudholt, "Crossover is provably essential for the Ising model on trees," in Proc. Genetic Evol. Comput. Conf. (GECCO '05), Washington D. C. , Jun. 2005, pp. 1161–1167.
  17. J. He, X. Yao, and J. Li, "A comparative study of three evolutionary algorithms incorporating different amount of domain knowledge for node covering problems," IEEE Trans. Syst. , Man Cybern. , Part C, vol. 35, no. 2, pp. 266–271, 2005.
  18. T. Friedrich, J. He, N. Hebbinghaus, F. Neumann, and C. Witt, "On improving approximate solutions by evolutionary algorithms," in Proc. Congr. Evol. Comput. , Piscataway, NJ: IEEE Press, 2007, pp. 2614–2621.
  19. T. Friedrich, J. He, N. Hebbinghaus, F. Neumann, and C. Witt, "Approximating covering problems by randomized search heuristics using multiobjective models," in Proc. Genetic Evol. Comput. Conf. (GECCO), London, U. K. , Jul. 2007, pp. 797–804.
  20. F. Neumann and C. Witt, "Runtime analysis of a simple ant colony optimization algorithm," in Proc. 17th Int. Symp. Algorithms Comput. (ISAAC), LNCS vol. 4288. Kolkata, India, Berlin, Germany: Springer- Verlag, Dec. 2006, pp. 618–627.
  21. W. J. Gutjahr, "First steps to the runtime complexity analysis of ant colony optimization," Comput. Oper. Res. , vol. 35, no. 9, pp. 2711–2727, 2008.
  22. B. Doerr and D. Johannsen, "Refined runtime analysis of a basic ant colony optimization algorithm," in Proc. IEEE Congr. Evol. Comput, Piscataway, NJ: IEEE Press, 2007, pp. 501–507.
  23. B. Doerr, F. Neumann, D. Sudholt, and C. Witt, "On the runtime analysis of the 1-ANT ACO algorithm," in Proc. Genetic Evol. Comput. Conf. (GECCO), London, U. K. : ACM, 2007, pp. 33–40.
  24. W. J. Gutjahr and G. Sebastiani, "Runtime analysis of ant colony optimization with best-so-far reinforcement," Methodology Comput. Appl. Probab. , vol. 10, no. 3, pp. 409–433, 2008.
  25. F. Neumann, D. Sudholt, and C. Witt, "Analysis of different MMAS ACO algorithms on unimodal functions and plateaus," Swarm Intell. , vol. 3, no. 1, pp. 35–68, 2009.
Index Terms

Computer Science
Information Sciences

Keywords

Hybrid Ant colony optimization (HACO) Ant colony optimization(ACO) Capacitated vehicle routing problem (CVRP) Multi-depot vehicle routing problem (MDVRP) combinatorial optimization mimetic algorithms

Powered by PhDFocusTM