Investigation of ant colony optimization with Levy flight technique for a class of stochastic combinatorial optimization problem
| dc.citation.epage | 1142 | |
| dc.citation.issue | 4 | |
| dc.citation.journalTitle | Математичне моделювання та комп'ютинг | |
| dc.citation.spage | 1132 | |
| dc.contributor.affiliation | Університет Абдельмалека Ессааді | |
| dc.contributor.affiliation | Abdelmalek Essaadi University | |
| dc.contributor.author | Ель Асрі, Ф. | |
| dc.contributor.author | Таяні, К. | |
| dc.contributor.author | Фахурі, Х. | |
| dc.contributor.author | El Asri, F. | |
| dc.contributor.author | Tajani, C. | |
| dc.contributor.author | Fakhouri, H. | |
| dc.coverage.placename | Львів | |
| dc.date.accessioned | 2025-03-10T09:21:53Z | |
| dc.date.created | 2023-02-28 | |
| dc.date.issued | 2023-02-28 | |
| dc.description.abstract | Запит на ефективні розв’язки задач оптимізації з невизначеними та стохастичними даними зростає. Імовірнісна задача комівояжера (PTSP) — це клас стохастичних комбінаторних задач оптимізації (SCOP), які містять частково невідому інформацію про дані задачі з відомим розподілом ймовірностей. Вона полягає в мінімізації очікуваної тривалості туру, коли кожен клієнт вимагає відвідування лише з певною ймовірністю, за якої клієнти, яким тур не потрібен, просто ігноруються без подальшої оптимізації. Оскільки PTSP є NP-складною, для розв’язування цієї задачі необхідно використовувати метаевристичні методи. У цій статті подано алгоритм оптимізації мурашиної колонії (ACO) у поєднанні з механізмом польоту Леві (LFACO), який базується на розподілі Леві, щоб збалансувати простір пошуку та прискорити глобальну оптимізацію. Експериментальні результати на великій кількості прикладів показують, що запропонований алгоритм Леві ACO для імовірнісної задачі комівояжера дає кращі результати порівняно з класичним алгоритмом ACO | |
| dc.description.abstract | 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. | |
| dc.format.extent | 1132-1142 | |
| dc.format.pages | 11 | |
| dc.identifier.citation | El Asri F. Investigation of ant colony optimization with Levy flight technique for a class of stochastic combinatorial optimization problem / F. El Asri, C. Tajani, H. Fakhouri // Mathematical Modeling and Computing. — Lviv Politechnic Publishing House, 2023. — Vol 10. — No 4. — P. 1132–1142. | |
| dc.identifier.citationen | El Asri F. Investigation of ant colony optimization with Levy flight technique for a class of stochastic combinatorial optimization problem / F. El Asri, C. Tajani, H. Fakhouri // Mathematical Modeling and Computing. — Lviv Politechnic Publishing House, 2023. — Vol 10. — No 4. — P. 1132–1142. | |
| dc.identifier.doi | doi.org/10.23939/mmc2023.04.1132 | |
| dc.identifier.uri | https://ena.lpnu.ua/handle/ntb/64065 | |
| dc.language.iso | en | |
| dc.publisher | Видавництво Львівської політехніки | |
| dc.publisher | Lviv Politechnic Publishing House | |
| dc.relation.ispartof | Математичне моделювання та комп'ютинг, 4 (10), 2023 | |
| dc.relation.ispartof | Mathematical Modeling and Computing, 4 (10), 2023 | |
| dc.relation.references | [1] Jaillet P. Probabilistic Traveling Salesman Problems. PhD Thesis, Massachusetts Institute of Technology (1985). | |
| dc.relation.references | [2] Bertsimas D., Howell L. H. Further results on the probabilistic traveling salesman problem. European Journal of Operational Research. 65 (1), 68–95 (1993). | |
| dc.relation.references | [3] Laporte G., Louveaux F. V., Mercure H. A Priori Optimization of the Probabilistic Traveling Salesman Problem. Operations Research. 42 (3), 543–549 (1994). | |
| dc.relation.references | [4] Amar M. A., Khaznaji W. An application and Parallel Tabu Search Algorithm for Solving the PTSP Under the OpenMP-MPI Environment. (2020). | |
| dc.relation.references | [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). | |
| dc.relation.references | [6] Balaprakash P., Birattari M., St¨utzle 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). | |
| dc.relation.references | [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). | |
| dc.relation.references | [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). | |
| dc.relation.references | [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). | |
| dc.relation.references | [10] Marinaki M., Marinakis Y., Zopounidis C. Honey Bees Mating Optimization algorithm for financial classification problems. Applied Soft Computing. 10 (3), 806–812 (2010). | |
| dc.relation.references | [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). | |
| dc.relation.references | [12] Greenenko A. A., Chechkin A. V., Shul’ga N. F. Anomalous diffusion and L´evy flights in channeling. Physics Letters A. 324 (1), 82–85 (2004). | |
| dc.relation.references | [13] Hanert E. Front dynamics in a two-species competition model driven by L´evy flights. Journal of Theoretical Biology. 300, 134–142 (2012). | |
| dc.relation.references | [14] Liu F., Sun Y., Wang G.-g., Wu T. An Artificial Bee Colony Algorithm Based on Dynamic Penalty and L´evy Flight for Constrained Optimization Problems. Arabian Journal for Science and Engineering. 43, 7189–7208 (2018). | |
| dc.relation.references | [15] Liu Y., Cao B. A Novel Ant Colony Optimization Algorithm With Levy Flight. IEEE Access. 8, 67205–67213 (2020). | |
| dc.relation.references | [16] Pavlyukevich I. L´evy flights, non-local search and simulated annealing. Journal of Computational Physics. 226 (2), 1830–1844 (2007). | |
| dc.relation.references | [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). | |
| dc.relation.references | [18] Wang Q., Guo X. Particle swarm optimization algorithm based on Levy flight. Application Research of Computers. 33 (9), 2588–2591 (2016). | |
| dc.relation.references | [19] Viswanathan G. M., Afanasyev V., Buldyrev S. V., Murphy E. J., Prince P. A., Stanley H. E. L´evy flight search patterns of wandering albatrosses. Nature. 381, 413–415 (1996). | |
| dc.relation.references | [20] Bellalouna M. Probl´emes d’optimisation combinatoires probabilistes. PhD thesis, Ecole Nationale des Ponts et Chauss´ees (1993). | |
| dc.relation.references | [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). | |
| dc.relation.references | [22] Campbell A. M., Thomas B. W. Probabilistic Traveling Salesman Problem with Deadlines. Transportation Science. 42 (1), 1–21 (2008). | |
| dc.relation.references | [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). | |
| dc.relation.references | [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). | |
| dc.relation.references | [25] Dr´eo J. Adaptation de la m´ethode des colonies de fourmis pour optimisation en variables continues. Application en g´enie biom´edical. PhD thesis, Paris (2004). | |
| dc.relation.references | [26] Saji Y., Barkatou M. A discrete bat algorithm based on L´evy flights for Euclidean traveling salesman problem. Expert Systems with Applications. 172, 114639 (2021). | |
| dc.relation.references | [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). | |
| dc.relation.referencesen | [1] Jaillet P. Probabilistic Traveling Salesman Problems. PhD Thesis, Massachusetts Institute of Technology (1985). | |
| dc.relation.referencesen | [2] Bertsimas D., Howell L. H. Further results on the probabilistic traveling salesman problem. European Journal of Operational Research. 65 (1), 68–95 (1993). | |
| dc.relation.referencesen | [3] Laporte G., Louveaux F. V., Mercure H. A Priori Optimization of the Probabilistic Traveling Salesman Problem. Operations Research. 42 (3), 543–549 (1994). | |
| dc.relation.referencesen | [4] Amar M. A., Khaznaji W. An application and Parallel Tabu Search Algorithm for Solving the PTSP Under the OpenMP-MPI Environment. (2020). | |
| dc.relation.referencesen | [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). | |
| dc.relation.referencesen | [6] Balaprakash P., Birattari M., St¨utzle 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). | |
| dc.relation.referencesen | [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). | |
| dc.relation.referencesen | [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). | |
| dc.relation.referencesen | [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). | |
| dc.relation.referencesen | [10] Marinaki M., Marinakis Y., Zopounidis C. Honey Bees Mating Optimization algorithm for financial classification problems. Applied Soft Computing. 10 (3), 806–812 (2010). | |
| dc.relation.referencesen | [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). | |
| dc.relation.referencesen | [12] Greenenko A. A., Chechkin A. V., Shul’ga N. F. Anomalous diffusion and L´evy flights in channeling. Physics Letters A. 324 (1), 82–85 (2004). | |
| dc.relation.referencesen | [13] Hanert E. Front dynamics in a two-species competition model driven by L´evy flights. Journal of Theoretical Biology. 300, 134–142 (2012). | |
| dc.relation.referencesen | [14] Liu F., Sun Y., Wang G.-g., Wu T. An Artificial Bee Colony Algorithm Based on Dynamic Penalty and L´evy Flight for Constrained Optimization Problems. Arabian Journal for Science and Engineering. 43, 7189–7208 (2018). | |
| dc.relation.referencesen | [15] Liu Y., Cao B. A Novel Ant Colony Optimization Algorithm With Levy Flight. IEEE Access. 8, 67205–67213 (2020). | |
| dc.relation.referencesen | [16] Pavlyukevich I. L´evy flights, non-local search and simulated annealing. Journal of Computational Physics. 226 (2), 1830–1844 (2007). | |
| dc.relation.referencesen | [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). | |
| dc.relation.referencesen | [18] Wang Q., Guo X. Particle swarm optimization algorithm based on Levy flight. Application Research of Computers. 33 (9), 2588–2591 (2016). | |
| dc.relation.referencesen | [19] Viswanathan G. M., Afanasyev V., Buldyrev S. V., Murphy E. J., Prince P. A., Stanley H. E. L´evy flight search patterns of wandering albatrosses. Nature. 381, 413–415 (1996). | |
| dc.relation.referencesen | [20] Bellalouna M. Probl´emes d’optimisation combinatoires probabilistes. PhD thesis, Ecole Nationale des Ponts et Chauss´ees (1993). | |
| dc.relation.referencesen | [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). | |
| dc.relation.referencesen | [22] Campbell A. M., Thomas B. W. Probabilistic Traveling Salesman Problem with Deadlines. Transportation Science. 42 (1), 1–21 (2008). | |
| dc.relation.referencesen | [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). | |
| dc.relation.referencesen | [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). | |
| dc.relation.referencesen | [25] Dr´eo J. Adaptation de la m´ethode des colonies de fourmis pour optimisation en variables continues. Application en g´enie biom´edical. PhD thesis, Paris (2004). | |
| dc.relation.referencesen | [26] Saji Y., Barkatou M. A discrete bat algorithm based on L´evy flights for Euclidean traveling salesman problem. Expert Systems with Applications. 172, 114639 (2021). | |
| dc.relation.referencesen | [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). | |
| dc.rights.holder | © Національний університет “Львівська політехніка”, 2023 | |
| dc.subject | стохастична комбінаторна оптимізація | |
| dc.subject | імовірнісна задача комівояжера | |
| dc.subject | метаевристика | |
| dc.subject | оптимізація мурашиної колонії | |
| dc.subject | політ Леві | |
| dc.subject | stochastic combinatorial optimization | |
| dc.subject | probabilistic traveling salesman problem | |
| dc.subject | metaheuristics | |
| dc.subject | ant colony optimization | |
| dc.subject | Levy flight | |
| dc.title | Investigation of ant colony optimization with Levy flight technique for a class of stochastic combinatorial optimization problem | |
| dc.title.alternative | Дослідження оптимізації мурашиної колонії за допомогою техніки польоту Леві для класу задач стохастичної комбінаторної оптимізації | |
| dc.type | Article |
Files
License bundle
1 - 1 of 1