The week's pick
Random Articles
Reseach Article
A Hybrid Ant Colony Optimization Algorithm using MapReduce for Arc Routing Problem
| 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
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
- 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.
- 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.
- C. Blum, "Ant colony optimization: Introduction and recent trends," Phys. Life Rev. , vol. 2, no. 4, pp. 353–373, Dec. 2005.
- M. Dorigo and C. Blum, "Ant colony optimization theory: A survey," Theor. Comput. Sci. , vol. 344, no. 2/3, pp. 243–278, Nov. 2005.
- 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.
- T. Stutzle and H. H. Hoos, "Max-min ant system," Future Gener. Comput. Syst. , vol. 16, no. 8, pp. 889–914, 2000.
- 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.
- 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.
- 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.
- 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.
- 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.
- J. Demsar, "Statistical comparisons of classifiers over multiple data sets," J. Mach. Learn. Res. , vol. 7, pp. 1–30, 2006.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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
Keywords