An ACO-RFD hybrid method to solve NP-complete problems

Abstract

In this paper we hybridize ant colony optimization (ACO) and river formation dynamics (RFD), two related swarm intelligence methods. In ACO, ants form paths (problem solutions) by following each other’s pheromone trails and reinforcing trails at best paths until eventually a single path is followed. On the other hand, RFD is based on copying how drops form rivers by eroding the ground and depositing sediments. In a rough sense, RFD can be seen as a gradient-oriented version of ACO. Several previous experiments have shown that the gradient orientation of RFD makes this method solve problems in a different way as ACO. In particular, RFD typically performs deepersearches, which in turn makes it find worse solutions than ACO in the first execution steps in general, though RFD solutions surpass ACO solutions after some more time passes. In this paper we try to get the best features of both worlds by hybridizing RFD and ACO. We use a kind of ant-drophybrid and consider both pheromone trails and altitudes in the environment. We apply the hybrid method, as well as ACO and RFD, to solve two NP-hard problems where ACO and RFD fit in a different manner: the traveling salesman problem (TSP) and the problem of the minimum distances tree in a variable-cost graph (MDV). We compare the results of each method and we analyze the advantages of using the hybrid approach in each case.

Keywords

river formation dynamics / ant colony optimization / heuristic algorithms / NP-hard problems

References

[1] Beni G, Wang J. Swarm intelligence in cellular robotic systems. In: NATO Advanced Workshop on Robotics and Biological Systems. 1989

[2] Kennedy J, Eberhart R. Swarm intelligence. TheMorgan Kaufmann series in evolutionary computation. Morgan Kaufmann Publishers, 2001

[3] Eiben A, Smith J. Introduction to evolutionary computing. Springer, 2003

[4] Kennedy J. Swarm intelligence. In: Zomaya A, ed. Handbook of nature-inspired and innovative computing, 187−219. Springer US, 2006

[5] Jong D K. Evolutionary computation: a unified approach. In: Genetic and Evolutionary Computation Conference, GECCO 2008. 2008, 2245−2258

[6] Chiong R, ed. . Nature-inspired algorithms for optimisation, Volume 193 of Studies in Computational Intelligence. Springer, 2009

[7] Luke S. Essentials of metaheuristics. Lulu, 2010

[8] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics, Part B, 1996, 26(1): 29−41

[9] Dorigo M, Gambardella L. Ant colonies for the traveling salesman problem. BioSystems, 1997, 43(2): 73−81

[10] Dorigo M, Stützle T. Ant colony optimization. Bradford Company, 2004

[11] Dorigo M, Birattari M, Stützle T. Ant colony optimization–artificial ants as a computational intelligence technique. IEEE Computational Intelligence Magazine, 2006, 1: 28−39

[12] Reimann M, Doerner K, Hartl R F. D-ants: savings based ants divide and conquer the vehicle routing problem. Computers & Operations Research, 2004, 31(4): 563−591

[13] Merkle D, Middendorf M, Schmeck H. Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation, 2002, 6(4): 333−346

[14] Blum C. Beam-ACO-hybridizing ant colony optimization with beam search: an application to open shop scheduling. Computers & Operations Research, 2005, 32(6): 1565−1591

[15] Lessing L, Dumitrescu I, Stützle T. A comparison between ACO algorithms for the set covering problem. In: Proceedings of the 4th International workshop on Ant Colony Optimization and Swarm Intelligence (ANTS 2004), LNCS, Volume 3172, 1−12

[16] Fenet S, Solnon C. Searching for maximum cliques with ant colony optimization. In: Proceedings of EvoWorkshops 2003, LNCS, Volume 2611, 236−245

[17] Maniezzo V. Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. INFORMS Journal on Computing, 1999, 11(4): 358−369

[18] Rabanal P, Rodríguez I, Rubio F. Using river formation dynamics to design heuristic algorithms. In: Unconventional Computation, UC’07, LNCS 4618. 2007, 163−177

[19] Rabanal P, Rodríguez I, Rubio F. Finding minimum spanning/distances trees by using river formation dynamics. In: Ant Colony Optimization and Swarm Intelligence, ANTS’08, LNCS 5217. 2008, 60−71

[20] Rabanal P, Rodríguez I, Rubio F. Studying the application of ant colony optimization and river formation dynamics to the steiner tree problem. Evolutionary Intelligence, 2011, 4(1): 51−65

[21] Rabanal P, Rodríguez I, Rubio F. Applying river formation dynamics to solve NP-complete problems. In: Chiong R, ed. Nature-inspired algorithms for optimisation, Volume 193 of Studies in Computational Intelligence, 333−368. Springer, 2009

[22] Rabanal P, Rodríguez I, Rubio F. Testing restorable systems: formal definition and heuristic solution based on river formation dynamics. Formal Aspects of Computing, 2012, In press

[23] Rabanal P, Rodríguez I. Hybridizing river formation dynamics and ant colony optimization. In: Proceedings of the 10th European Conference on Advances in Artificial Life. 2009, 424−431

[24] Tech G. The traveling salesman problem, 2012. Available at http://www.tsp.gatech.edu

[25] Hoffman K. The traveling salesman problem, 2011.

[26] Hanen C. Study of a np-hard cyclic scheduling problem: the recurrent job-shop. European Journal of Operational Research, 1994, 72(1): 82−101

[27] Meguerdichian S, Koushanfar F, Potkonjak M, Srivastava M. Coverage problems in wireless ad-hoc sensor networks. In: Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies. 2001

[28] Lee Z J, Lee C Y. A hybrid search algorithm with heuristics for resource allocation problem. Information Science-Informatics and Computer Science, 2005, 173: 155−167

[29] Gonzalez T. Handbook of approximation algorithms and metaheuristics. Chapman & Hall/CRC, 2007

[30] Lawler E L, Lenstram J K, Rinnooy A H G, Shmoys D B. The traveling salesman problem: a guide tour of combinatorial optimization. John Wiley and Sons, 1986

[31] Reinelt G. The traveling salesman (computational solutions for TSP applications). Springer, 1994

[32] Golden B, Skiscim C. Using simulated annealing to solve routing and location problems. Naval Research Logistics Quarterly, 1986, 33(2): 261−279

[33] Martin O, Otto S. Combining simulated annealing with local search heuristics. Technical Report, 1993

[34] Braun H. On solving travelling salesman problems by genetic algorithms. In: Proceedings of the 1stWorkshop on Parallel Problem Solving from Nature, PPSN I. 1991, 129−133

[35] Larrañaga P, Kuijpers C, Inza R M I, Dizdarevic S. Genetic algorithms for the travelling salesman problem: a review of representations and operators. Artificial Intelligence Review, 1999, 13: 129−170

[36] García-Martínez C, Cordón O, Herrera F. A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP. European Journal of Operational Research, 2007, 180(1): 116−148

[37] Perlman R. An algorithm for distributed computation of a spanningtree in an extended lan. In: ACM SIGCOMM Computer Communication Review. 1985, 44−53

[38] Peterson L, Davie B. Computer networks: a systems approach. 3rd ed. Morgan Kaufmann, 2007

[39] Rabanal P, Rodríguez I. Testing restorable systems by using RFD. In: Int.Work Conference on Artificial Neural Networks, IWANN’09. 2009

[40] Rabanal P, Rodríguez I, Rubio F. Applying RFD to construct optimal quality-investment trees. J. UCS, 2010, 16(14): 1882−1901

[41] Zhou Y. Runtime analysis of an ant colony optimization algorithm for TSP instances. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 1083−1092

[42] Reinelt G. TSPLIB 95. Technical Report, Research Report, Institut für Angewandte Mathematik, Universität Heidelberg, Heidelberg, Germany, 1995.

[43] Parejo-Maestre J, García-Gutiérrez J, Ruiz-Cortés A, Riquelme-Santos J. STATService.

[44] Derrac J, García S, Molina D, Herrera F. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation, 2011, 1(1): 3−18

[45] Friedman M. The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical Association, 1937, 32: 674−701

[46] Friedman M. A comparison of alternative tests of significance for the problem of m rankings. Annals of Mathematical Statistics, 1940, 11: 86−92

[47] Hodges J, Lehmann E. Ranks methods for combination of independent experiments in analysis of variance. Annals of Mathematical Statistics, 1962, 33: 482−497

[48] Holm S. A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 1979, 6: 65−70

RIGHTS & PERMISSIONS

2013 Higher Education Press and Springer-Verlag Berlin Heidelberg