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

Abstract

Запит на ефективні розв’язки задач оптимізації з невизначеними та стохастичними даними зростає. Імовірнісна задача комівояжера (PTSP) — це клас стохастичних комбінаторних задач оптимізації (SCOP), які містять частково невідому інформацію про дані задачі з відомим розподілом ймовірностей. Вона полягає в мінімізації очікуваної тривалості туру, коли кожен клієнт вимагає відвідування лише з певною ймовірністю, за якої клієнти, яким тур не потрібен, просто ігноруються без подальшої оптимізації. Оскільки PTSP є NP-складною, для розв’язування цієї задачі необхідно використовувати метаевристичні методи. У цій статті подано алгоритм оптимізації мурашиної колонії (ACO) у поєднанні з механізмом польоту Леві (LFACO), який базується на розподілі Леві, щоб збалансувати простір пошуку та прискорити глобальну оптимізацію. Експериментальні результати на великій кількості прикладів показують, що запропонований алгоритм Леві ACO для імовірнісної задачі комівояжера дає кращі результати порівняно з класичним алгоритмом ACOThe 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.