Алгоритм муравьиной колонии для многомерной задачи о ранце
Приведена модификация муравьиного алгоритма решения многомерной задачи о ранце. Также приведен обзор применяемости муравьиных алгоритмов в различных предметных областях. Все алгоритмы этого типа являются приближенными вероятностными алгоритмами. Эффективность работы алгоритмов зависит от параметров...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2019
|
| Назва видання: | Реєстрація, зберігання і обробка даних |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/169098 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгоритм муравьиной колонии для многомерной задачи о ранце / Б.И. Юхименко, О.Ю. Ткаленко // Реєстрація, зберігання і обробка даних. — 2019. — Т. 21, № 2. — С. 3–11. — Бібліогр.: 10 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-169098 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1690982020-06-05T01:26:02Z Алгоритм муравьиной колонии для многомерной задачи о ранце Юхименко, Б.И. Ткаленко, О.Ю. Математичні методи обробки даних Приведена модификация муравьиного алгоритма решения многомерной задачи о ранце. Также приведен обзор применяемости муравьиных алгоритмов в различных предметных областях. Все алгоритмы этого типа являются приближенными вероятностными алгоритмами. Эффективность работы алгоритмов зависит от параметров α и β, предопределяющих количество феромонов при передвижении муравьев, а также их испарение соответственно. Приведены формулы расчета величины вероятности, согласно которой принимается решение о присвоении значения «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. 2019 Article Алгоритм муравьиной колонии для многомерной задачи о ранце / Б.И. Юхименко, О.Ю. Ткаленко // Реєстрація, зберігання і обробка даних. — 2019. — Т. 21, № 2. — С. 3–11. — Бібліогр.: 10 назв. — рос. 1560-9189 DOI: https://doi.org/10.35681/1560-9189.2019.21.2.180014 http://dspace.nbuv.gov.ua/handle/123456789/169098 519.854 ru Реєстрація, зберігання і обробка даних Інститут проблем реєстрації інформації НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Математичні методи обробки даних Математичні методи обробки даних |
| spellingShingle |
Математичні методи обробки даних Математичні методи обробки даних Юхименко, Б.И. Ткаленко, О.Ю. Алгоритм муравьиной колонии для многомерной задачи о ранце Реєстрація, зберігання і обробка даних |
| description |
Приведена модификация муравьиного алгоритма решения многомерной задачи о ранце. Также приведен обзор применяемости муравьиных алгоритмов в различных предметных областях. Все алгоритмы этого типа являются приближенными вероятностными алгоритмами. Эффективность работы алгоритмов зависит от параметров α и β, предопределяющих количество феромонов при передвижении муравьев, а также их испарение соответственно. Приведены формулы расчета величины вероятности, согласно которой принимается решение о присвоении значения «1» компоненте вектора решений. Приведены результаты компьютерного экспериментального исследования. Результаты сравнения точных решений с решением предложенным алгоритмом подчеркивают его эффективность. |
| format |
Article |
| author |
Юхименко, Б.И. Ткаленко, О.Ю. |
| author_facet |
Юхименко, Б.И. Ткаленко, О.Ю. |
| author_sort |
Юхименко, Б.И. |
| title |
Алгоритм муравьиной колонии для многомерной задачи о ранце |
| title_short |
Алгоритм муравьиной колонии для многомерной задачи о ранце |
| title_full |
Алгоритм муравьиной колонии для многомерной задачи о ранце |
| title_fullStr |
Алгоритм муравьиной колонии для многомерной задачи о ранце |
| title_full_unstemmed |
Алгоритм муравьиной колонии для многомерной задачи о ранце |
| title_sort |
алгоритм муравьиной колонии для многомерной задачи о ранце |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| publishDate |
2019 |
| topic_facet |
Математичні методи обробки даних |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/169098 |
| citation_txt |
Алгоритм муравьиной колонии для многомерной задачи о ранце / Б.И. Юхименко, О.Ю. Ткаленко // Реєстрація, зберігання і обробка даних. — 2019. — Т. 21, № 2. — С. 3–11. — Бібліогр.: 10 назв. — рос. |
| series |
Реєстрація, зберігання і обробка даних |
| work_keys_str_mv |
AT ûhimenkobi algoritmmuravʹinojkoloniidlâmnogomernojzadačiorance AT tkalenkooû algoritmmuravʹinojkoloniidlâmnogomernojzadačiorance |
| first_indexed |
2023-10-18T22:24:27Z |
| last_indexed |
2023-10-18T22:24:27Z |
| _version_ |
1796155434949672960 |