1. MMC
  2. All Volumes and Issues
  3. Volume 10, Number 4, 2023
  4. Investigation of ant colony optimization with Levy flight technique for a class of stochastic combinatorial optimization problem

Investigation of ant colony optimization with Levy flight technique for a class of stochastic combinatorial optimization problem

MMC.
2023;
Volume 10, Number 4
: pp. 1132–1142
https://doi.org/10.23939/mmc2023.04.1132
Received: August 20, 2023
Revised: October 31, 2023
Accepted: November 02, 2023

Mathematical Modeling and Computing, Vol. 10, No. 4, pp. 1132–1142 (2023)

Authors:
  1. F. El Asri
  2. C. Tajani
  3. H. Fakhouri
1
SMAD Team, Polydisciplinary Faculty of Larache, Abdelmalek Essaadi University
2
SMAD Team, Polydisciplinary faculty of Larache, Abdelmalek Essaadi University
3
SMAD Team, Polydisciplinary Faculty of Larache, Abdelmalek Essaadi University

The demand for efficient solutions to optimization problems with uncertain and stochastic data is increasing.  Probabilistic traveling salesman problem (PTSP) is a class of Stochastic Combinatorial Optimization Problems (SCOPs) involving partially unknown information about problem data with a known probability distribution.  It consists to minimize the expected length of the tour where each customer requires a visit only with a given probability, at which customers who do not need a tour are just ignored without further optimization.  Since the PTSP is NP-hard, the usage of metaheuristic methods is necessary to solve the problem.  In this paper, we present the Ant Colony Optimization (ACO) algorithm combined with the Levy Flight mechanism (LFACO), which is based on Levy distribution to balance searching space and speed global optimization.  Experimental results on a large number of instances show that the proposed Levy ACO algorithm on the probabilistic traveling salesman problem allows to obtain better results compared with the classical ACO algorithm.

stochastic combinatorial optimization
probabilistic traveling salesman problem
metaheuristics
ant colony optimization
Levy flight
  1. Jaillet P.  Probabilistic Traveling Salesman Problems.  PhD Thesis, Massachusetts Institute of Technology (1985).
  2. Bertsimas D., Howell L. H.  Further results on the probabilistic traveling salesman problem.  European Journal of Operational Research.  65 (1), 68–95 (1993).
  3. Laporte G., Louveaux F. V., Mercure H.  A Priori Optimization of the Probabilistic Traveling Salesman Problem.  Operations Research.  42 (3), 543–549 (1994).
  4. Amar M. A., Khaznaji W.  An application and Parallel Tabu Search Algorithm for Solving the PTSP Under the OpenMP-MPI Environment.  (2020).
  5. Amar M. A., Khaznaji W., Bellalouna M.  A Parallel Branch and Bound Algorithm for the Probabilistic TSP.  International Conference on Algorithms and Architectures for Parallel Processing.  ICA3PP 2018: Algorithms and Architectures for Parallel Processing. 437–448 (2018).
  6. Balaprakash P., Birattari M., Stützle T., Yuan Z., Dorigo M.  Estimation-based ant colony optimization and local search for the probabilistic traveling salesman problem.  Swarm Intelligence.  3, 223–242 (2009).
  7. Bianchi L., Gambardella L. M., Dorigo M.  An Ant Colony Optimization Approach to the Probabilistic Traveling Salesman Problem.  International Conference on Parallel Problem Solving from Nature.  PPSN 2002: Parallel Problem Solving from Nature – PPSN VII.  883–892 (2002).
  8. Branke J., Guntsch M.  New Ideas for Applying Ant Colony Optimization to the Probabilistic TSP.  Workshops on Applications of Evolutionary Computation.  EvoWorkshops 2003: Applications of Evolutionary Computing.  165–175 (2003).
  9. Gutjahr W. J.  S-ACO: An Ant-Based Approach to Combinatorial Optimization Under Uncertainty.  International Workshop on Ant Colony Optimization and Swarm Intelligence.  ANTS 2004: Ant Colony Optimization and Swarm Intelligence.  238–249 (2004).
  10. Marinaki M., Marinakis Y., Zopounidis C.  Honey Bees Mating Optimization algorithm for financial classification problems.  Applied Soft Computing.  10 (3), 806–812 (2010).
  11. Marinakis Y., Marinaki M.  A hybrid Honey Bees Mating Optimization algorithm for the Probabilistic Traveling Salesman Problem.  2009 IEEE Congress on Evolutionary Computation. 1762–1769 (2009).
  12. Greenenko A. A., Chechkin A. V., Shul'ga N. F.  Anomalous diffusion and Lévy flights in channeling.  Physics Letters A.  324 (1), 82–85 (2004).
  13. Hanert E.  Front dynamics in a two-species competition model driven by Lévy flights.  Journal of Theoretical Biology.  300, 134–142 (2012).
  14. Liu F., Sun Y., Wang G.-g., Wu T.  An Artificial Bee Colony Algorithm Based on Dynamic Penalty and Lévy  Flight for Constrained Optimization Problems.  Arabian Journal for Science and Engineering.  43, 7189–7208 (2018).
  15. Liu Y., Cao B.  A Novel Ant Colony Optimization Algorithm With Levy Flight.  IEEE Access.  8, 67205–67213 (2020).
  16. Pavlyukevich I.  Lévy flights, non-local search and simulated annealing.  Journal of Computational Physics.  226 (2), 1830–1844 (2007).
  17. Qin J., Shen X., Mei F., Fang Z.  An Otsu multi-thresholds segmentation algorithm based on improved ACO.  The Journal of Supercomputing.  75, 955–967 (2019).
  18. Wang Q., Guo X.  Particle swarm optimization algorithm based on Levy flight.  Application Research of Computers.  33 (9), 2588–2591 (2016).
  19. Viswanathan G. M., Afanasyev V., Buldyrev S. V., Murphy E. J., Prince P. A., Stanley H. E.  Lévy flight search patterns of wandering albatrosses.  Nature.  381, 413–415 (1996).
  20. Bellalouna M.  Problémes d'optimisation combinatoires probabilistes.  PhD thesis, Ecole Nationale des Ponts et Chaussées (1993).
  21. Henchiri A., Bellalouna M., Khaznaji W.  A probabilistic traveling salesman problem: a survey.  Federated Conference on Computer Science and Information Systems (FedCSIS). 55–60 (2014).
  22. Campbell A. M., Thomas B. W.  Probabilistic Traveling Salesman Problem with Deadlines.  Transportation Science.  42 (1), 1–21 (2008).
  23. Colorni A., Dorigo M., Maniezzo V. et al.  Distributed optimization by ant colonies.  Proceedings of the first European conference on artificial life.  142, 134–142 (1991).
  24. Dorigo M., Gambardella L. M.  Ant colony system: a cooperative learning approach to the traveling salesman problem.  IEEE Transactions on Evolutionary Computation.  1 (1), 53–66 (1997).
  25. Dréo J.  Adaptation de la méthode des colonies de fourmis pour optimisation en variables continues.  Application en génie biomédical.  PhD thesis, Paris (2004).
  26. Saji Y., Barkatou M.  A discrete bat algorithm based on Lévy flights for Euclidean traveling salesman problem.  Expert Systems with Applications.  172, 114639 (2021).
  27. Liu Y., Cao B., Li H.  Improving ant colony optimization algorithm with epsilon greedy and Levy flight.  Complex & Intelligent Systems.  7, 1711–1722 (2021).