An algorithm of ants’ colony for the multi-dimensional knapsack problem.

• Date: 2019
• Main Authors: Yukhymenko, B. I., Tkalenko, O. Yu.
• Format: Article
• Language: Ukrainian
• Published: Інститут проблем реєстрації інформації НАН України 2019
• Subjects: optimization methods; approximate probabilistic methods; ant colony algorithms; multi-dimensional knapsack problem; computational complexity
• Online Access: http://drsp.ipri.kiev.ua/article/view/180014
• Journal Title: Data Recording, Storage & Processing

A fairly new direction in the creation of methods and algorithms for solving optimization problems is described. The behavior of living beings in nature can be formalized using scientific ideas. Particular attention is attracted by the behavior of ants. Their colonies can be viewed as a multi-agent system, whose agents work separately, but pursue a common goal. They have the ability to transmit information that allows them to adapt and change their behavior.The principles of randomness, multiplicity, positive and negative feedback in the actions of those non-intelligent creatures in nature provide ideas for creating some original and quite effective optimization methods. The algorithms of the ant colony are successfully used in solving many problems of discrete optimization. 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.