An algorithm of ants’ colony for the multi-dimensional knapsack problem.
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...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2019
|
| Теми: | |
| Онлайн доступ: | http://drsp.ipri.kiev.ua/article/view/180014 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Data Recording, Storage & Processing |
Репозитарії
Data Recording, Storage & Processing| id |
drspiprikievua-article-180014 |
|---|---|
| record_format |
ojs |
| institution |
Data Recording, Storage & Processing |
| collection |
OJS |
| language |
Ukrainian |
| topic |
методи оптимізації наближені ймовірнісні алгоритми алгоритми мурашиної колонії багатовимірна задача про ранець складність обчислень optimization methods approximate probabilistic methods ant colony algorithms multi-dimensional knapsack problem computational complexity |
| spellingShingle |
методи оптимізації наближені ймовірнісні алгоритми алгоритми мурашиної колонії багатовимірна задача про ранець складність обчислень optimization methods approximate probabilistic methods ant colony algorithms multi-dimensional knapsack problem computational complexity Yukhymenko, B. I. Tkalenko, O. Yu. An algorithm of ants’ colony for the multi-dimensional knapsack problem. |
| topic_facet |
методи оптимізації наближені ймовірнісні алгоритми алгоритми мурашиної колонії багатовимірна задача про ранець складність обчислень optimization methods approximate probabilistic methods ant colony algorithms multi-dimensional knapsack problem computational complexity |
| format |
Article |
| author |
Yukhymenko, B. I. Tkalenko, O. Yu. |
| author_facet |
Yukhymenko, B. I. Tkalenko, O. Yu. |
| author_sort |
Yukhymenko, B. I. |
| title |
An algorithm of ants’ colony for the multi-dimensional knapsack problem. |
| title_short |
An algorithm of ants’ colony for the multi-dimensional knapsack problem. |
| title_full |
An algorithm of ants’ colony for the multi-dimensional knapsack problem. |
| title_fullStr |
An algorithm of ants’ colony for the multi-dimensional knapsack problem. |
| title_full_unstemmed |
An algorithm of ants’ colony for the multi-dimensional knapsack problem. |
| title_sort |
algorithm of ants’ colony for the multi-dimensional knapsack problem. |
| title_alt |
Алгоритм мурашиної колонії для багатовимірної задачі про ранець |
| description |
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. |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| publishDate |
2019 |
| url |
http://drsp.ipri.kiev.ua/article/view/180014 |
| work_keys_str_mv |
AT yukhymenkobi analgorithmofantscolonyforthemultidimensionalknapsackproblem AT tkalenkooyu analgorithmofantscolonyforthemultidimensionalknapsackproblem AT yukhymenkobi algoritmmurašinoíkoloníídlâbagatovimírnoízadačíproranecʹ AT tkalenkooyu algoritmmurašinoíkoloníídlâbagatovimírnoízadačíproranecʹ AT yukhymenkobi algorithmofantscolonyforthemultidimensionalknapsackproblem AT tkalenkooyu algorithmofantscolonyforthemultidimensionalknapsackproblem |
| first_indexed |
2024-04-21T19:34:05Z |
| last_indexed |
2024-04-21T19:34:05Z |
| _version_ |
1796974099079102464 |
| spelling |
drspiprikievua-article-1800142019-12-10T11:17:11Z An algorithm of ants’ colony for the multi-dimensional knapsack problem. Алгоритм мурашиної колонії для багатовимірної задачі про ранець Yukhymenko, B. I. Tkalenko, O. Yu. методи оптимізації наближені ймовірнісні алгоритми алгоритми мурашиної колонії багатовимірна задача про ранець складність обчислень optimization methods approximate probabilistic methods ant colony algorithms multi-dimensional knapsack problem computational complexity 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. Надано опис досить нового напряму в створенні методів і алгоритмів розв’язання оптимізаційних задач. Поведінку живих істот у природі вдається формалізувати, використовуючи наукові ідеї. Особливу увагу привертає поведінка мурах. Їхні колонії можна розглядати як багатоагентну систему, чиї агенти працюють окремо, але переслідують спільну мету. Вони мають можливість передавати інформацію, що дозволяє їм адаптуватись і змінювати свою поведінку. Принципи випадковості, багатократності, позитивний і негативний зворотній зв’язок у діях цих не інтелектуальних істот у живій природі подають ідеї створення своєрідних і досить ефективних методів оптимізації. Алгоритми мурашиної колонії вдало застосовуються при вирішенні багатьох завдань дискретної оптимізації. У статті наведено огляд вживаності мурашиних алгоритмів у різних предметних областях. Усі алгоритми цього типу є наближеними — ймовірнісними алгоритмами. Величина ймовірності прийняття певного рішення при формуванні варіанта залежить від параметрів a і b, які визначають наявність і випаровування феромонів. Значення цих параметрів у принципі і зумовлюють ефективність роботи алгоритму. Основний розробкою в статті є новий імовірнісний наближений алгоритм рішення багатовимірної задачі про ранець. В основі його розробки лежать ідеї алгоритмів мурашиної колонії, які вже застосовуються на практиці. Наведено результати комп’ютерного експериментального дослідження.Результати порівняння точних рішень з рішеннями запропонованим алгоритмом, дають надію отримати способи вирішення завдань дискретної оптимізації для практичного використання, обчислювальна складність яких значно менше.Надалі, якщо ці алгоритми вдасться привести до точних, то вони виведуть методи дискретної оптимізації з класу NP-складності. Інститут проблем реєстрації інформації НАН України 2019-11-21 Article Article application/pdf http://drsp.ipri.kiev.ua/article/view/180014 10.35681/1560-9189.2019.21.2.180014 Data Recording, Storage & Processing; Vol. 21 No. 2 (2019); 3-11 Регистрация, хранение и обработка данных; Том 21 № 2 (2019); 3-11 Реєстрація, зберігання і обробка даних; Том 21 № 2 (2019); 3-11 1560-9189 uk http://drsp.ipri.kiev.ua/article/view/180014/184142 Авторське право (c) 2021 Реєстрація, зберігання і обробка даних |