A parallel algorithm combines genetic algorithm and ant colony algorithm for the minimum latency problem

ABSTRACT

The Minimum Latency Problem is a class of combinatorial optimization problems which has many practical applications. Recently, several meta-heuristic algorithms were proposed. These algorithms were developed in either a trajectory-based meta-heuristic or sequential approach, which start with a single initial solution and, at each step of the search, the current solution is replaced by another (often the best) solution found in its neighborhood. Since the search space of the problem is combinatorial explosion, these algorithms often explore a subset of the search space, therefore, they can fall into local optima in some cases. In order to overcome the drawbacks of the current algorithms, we propose a population-based algorithm that combines the genetic algorithm (GA) and the ant colony algorithm (ACO) according to island parallel model. In our parallel approach, subpopulations are developed in different ways and individual's migration helps to maintain the diversity. In each subpopulation, ACO is used to generate ant populations while the genetic information from GA drives ants to create better populations in the next iterations. The most important feature of our ACO is that three kinds of ants coexist to improve the efficiency of search. In addition, our population-based approach can simultaneously search from multiple solutions in populations, thus, its exploring search space is extended to escape from local optima. Extensive numerical experiments and comparisons with the state of the art meta-heuristic algorithms in the literature show that the proposed algorithm is highly competitive, providing the new best solutions for several instances.

References

1. A. Archer, A. Levin, and D. Williamson, "A Faster, Better Approximation Algorithm for the Minimum Latency Problem", J. SIAM, Vol. 37, No. 1, 2007, pp. 1472--1498.
2. S. Arora, and G. Karakostas, "Approximation schemes for minimum latency problems", Proc. STOC, 1999, pp. 688--693.
3. H. B. Ban, and D. N. Nguyen, "Improved genetic algorithm for minimum latency problem", Proc. SOICT, 2010, pp. 9--15.
4. H. B. Ban, K. Nguyen, M. C. Ngo, and D. N. Nguyen, "An efficient exact algorithm for Minimum Latency Problem", J. PI, No. 10, 2013, pp. 1--8.
5. A. Blum, P. Chalasani, D. Coppersmith, W. Pulleyblank, P. Raghavan, and M. Sudan, "The minimum latency problem", Proc. STOC, 1994, pp. 163--171.
6. K. Chaudhuri, B. Goldfrey, S. Rao, and K. Talwar, "Path, Tree and minimum latency tour", Proc. FOCS, 2003, pp. 36--45.
7. J. J. Dongarra, "Performance of Various Computers Using Standard Linear Equations Software", Linpack Benchmark Report, University of Tennessee Computer Science Technical Report, CS-89-85, 2013.
8. M. Dorigo and T. Stutzle, "Ant Colony Optimization", Bradford Books, 2004.
9. M. Goemans, and J. Kleinberg, "An improved approximation ratio for the minimum latency problem", Proc. SIAM SODA, 1996, pp. 152--158.
10. H. Hasegawa, "Optimization of GROUP Behavior", Japan Ethological Society Newsletter, No. 43, 2004, pp. 22--23.
11. L. Homaifar, C. Guan, and G. Liepins, "A New Approach to the Traveling Salesman Problem by Genetic Algorithms", Proc. ICGA, pp. 460--466, 1993.
12. N. Mladenovic, P. Hansen, "Variable neighborhood search", J. Operations Research, vol. 24, No. 11 24, 1997, pp. 1097--1100.
13. A. Salehipour, K. Sorensen, P. Goos, and O. Braysy, "Efficient GRASP+VND and GRASP+VNS meta-heuristics for the traveling repairman problem", J. Operations Research, Vol. 9, No. 2, 2011, pp. 189--209.
14. M. Sabry Abdel-Moetty, O. Asmaa Heakil, "Enhanced Traveling Salesman Problem Solving using Genetic Algorithm Technique with modified Sequential Constructive Crossover Operator", J. IJCSNS, Vol. 12, No. 6, 2012, pp. 134--138.
15. M. Silva, A. Subramanian, T. Vidal, and L. Ochi, "A simple and effective meta-heuristic for the Minimum Latency Problem", J. Operations Research, Vol 221, No. 3, 2012, pp. 513--520.
16. S. Shimomuray, M. Sugimotoy, T. Haraguchiy, H. Matsushitaz and Y. Nishioy, "Ant Colony Optimization with Intelligent and Dull Ants", Proc. NOLTA, 2010, pp. 504--507.
17. D. S. Johnson, and L. A. McGeoch, "The traveling salesman problem: A case study in local optimization in Local Search in Combinatorial Optimization", E. Aarts and J. K. Lenstra, eds., pp. 215--310.
18. R. Sivaraj, T. Ravichandran, "A review of selection methods in genetic algorithm", J. IJEST, Vol. 3, No. 5, 2011, pp. 3792--3797.
19. R. Sivaraj, T. Ravichandran, "Genetic Algorithm for the Traveling Salesman Problem using Sequential Constructive Crossover Operator", J. IJBB, Vol. 3, No. 6, 2010, pp. 96--105.
20. L. Wang, A. MaciejewskiS, H. J. Siegel, and V. P. Roychowdhury, "A comparative study of five parallel genetic algorithms using the traveling salesman problem", Proc. IPPS/SPDP, 2005, pp. 217--234.
21. B. Y. Wu, Z.-N. Huang and F.-J. Zhan, "Exact algorithms for the minimum latency problem", Inform. Proc. Letters, Vol. 92, No. 6, 2004, pp. 303--309.
22. http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

      • Combinatorial algorithms

  • Mathematical software