Алгоритм муравьиной колонии для многомерной задачи о ранце

Abstract

Приведена модификация муравьиного алгоритма решения многомерной задачи о ранце. Также приведен обзор применяемости муравьиных алгоритмов в различных предметных областях. Все алгоритмы этого типа являются приближенными вероятностными алгоритмами. Эффективность работы алгоритмов зависит от параметров α и β, предопределяющих количество феромонов при передвижении муравьев, а также их испарение соответственно. Приведены формулы расчета величины вероятности, согласно которой принимается решение о присвоении значения «1» компоненте вектора решений. Приведены результаты компьютерного экспериментального исследования. Результаты сравнения точных решений с решением предложенным алгоритмом подчеркивают его эффективность.

У статті наведено огляд вживаності мурашиних алгоритмів у різних предметних областях. Усі алгоритми цього типу є наближеними — ймовірнісними алгоритмами. Величина ймовірності прийняття певного рішення при формуванні варіанта залежить від параметрів a і b, які визначають наявність і випаровування феромонів. Значення цих параметрів у принципі і зумовлюють ефективність роботи алгоритму. Основний розробкою в статті є новий імовірнісний наближений алгоритм рішення багатовимірної задачі про ранець. В основі його розробки лежать ідеї алгоритмів мурашиної колонії, які вже застосовуються на практиці. Наведено результати комп’ютерного експериментального дослідження. Результати порівняння точних рішень з рішеннями запропонованим алгоритмом, дають надію отримати способи вирішення завдань дискретної оптимізації для практичного використання, обчислювальна складність яких значно менше. Надалі, якщо ці алгоритми вдасться привести до точних, то вони виведуть методи дискретної оптимізації з класу NP-складності.

The article provides an overview of the applicability of ant algorithms in various subject areas. All algorithms of this type are approximate — probabilistic methods. The magnitude of the probability of making a certain decision when forming a variant depends on the parameters a and b, which determine the presence and evaporation of pheromones. The values of these parameters, in principle, and determine the efficiency of the algorithm. The main development in the article is a new probabilistic approximate algorithm for solving the multidimensional knapsack problem. At the core of its development are the ideas of ant colony algorithms, which are already being used in practice. The results of computer experimental research are given. The results of the comparison of exact solutions with the solutions of the proposed algorithm gives hope to get ways to solve discrete optimization problems for practical use, the computational complexity of which is much less. In the future, if these algorithms can be brought to exact ones, then they will derive discrete optimization methods from the NP class of complexity.