Алгоритм муравьиной колонии для многомерной задачи о ранце
Приведена модификация муравьиного алгоритма решения многомерной задачи о ранце. Также приведен обзор применяемости муравьиных алгоритмов в различных предметных областях. Все алгоритмы этого типа являются приближенными вероятностными алгоритмами. Эффективность работы алгоритмов зависит от параметров...
Збережено в:
| Опубліковано в: : | Реєстрація, зберігання і обробка даних |
|---|---|
| Дата: | 2019 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2019
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.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 |
nasplib_isofts_kiev_ua-123456789-169098 |
|---|---|
| record_format |
dspace |
| spelling |
Юхименко, Б.И. Ткаленко, О.Ю. 2020-06-04T14:19:02Z 2020-06-04T14:19:02Z 2019 Алгоритм муравьиной колонии для многомерной задачи о ранце / Б.И. Юхименко, О.Ю. Ткаленко // Реєстрація, зберігання і обробка даних. — 2019. — Т. 21, № 2. — С. 3–11. — Бібліогр.: 10 назв. — рос. 1560-9189 DOI: https://doi.org/10.35681/1560-9189.2019.21.2.180014 https://nasplib.isofts.kiev.ua/handle/123456789/169098 519.854 Приведена модификация муравьиного алгоритма решения многомерной задачи о ранце. Также приведен обзор применяемости муравьиных алгоритмов в различных предметных областях. Все алгоритмы этого типа являются приближенными вероятностными алгоритмами. Эффективность работы алгоритмов зависит от параметров α и β, предопределяющих количество феромонов при передвижении муравьев, а также их испарение соответственно. Приведены формулы расчета величины вероятности, согласно которой принимается решение о присвоении значения «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. ru Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Математичні методи обробки даних Алгоритм муравьиной колонии для многомерной задачи о ранце Алгоритм мурашиної колонії для багатовимірної задачі про ранець An algorithm of ants’ colony for the multi-dimensional knapsack problem Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Алгоритм муравьиной колонии для многомерной задачи о ранце |
| spellingShingle |
Алгоритм муравьиной колонии для многомерной задачи о ранце Юхименко, Б.И. Ткаленко, О.Ю. Математичні методи обробки даних |
| title_short |
Алгоритм муравьиной колонии для многомерной задачи о ранце |
| title_full |
Алгоритм муравьиной колонии для многомерной задачи о ранце |
| title_fullStr |
Алгоритм муравьиной колонии для многомерной задачи о ранце |
| title_full_unstemmed |
Алгоритм муравьиной колонии для многомерной задачи о ранце |
| title_sort |
алгоритм муравьиной колонии для многомерной задачи о ранце |
| author |
Юхименко, Б.И. Ткаленко, О.Ю. |
| author_facet |
Юхименко, Б.И. Ткаленко, О.Ю. |
| topic |
Математичні методи обробки даних |
| topic_facet |
Математичні методи обробки даних |
| publishDate |
2019 |
| language |
Russian |
| container_title |
Реєстрація, зберігання і обробка даних |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| format |
Article |
| title_alt |
Алгоритм мурашиної колонії для багатовимірної задачі про ранець An algorithm of ants’ colony for the multi-dimensional knapsack problem |
| description |
Приведена модификация муравьиного алгоритма решения многомерной задачи о ранце. Также приведен обзор применяемости муравьиных алгоритмов в различных предметных областях. Все алгоритмы этого типа являются приближенными вероятностными алгоритмами. Эффективность работы алгоритмов зависит от параметров α и β, предопределяющих количество феромонов при передвижении муравьев, а также их испарение соответственно. Приведены формулы расчета величины вероятности, согласно которой принимается решение о присвоении значения «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.
|
| issn |
1560-9189 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/169098 |
| citation_txt |
Алгоритм муравьиной колонии для многомерной задачи о ранце / Б.И. Юхименко, О.Ю. Ткаленко // Реєстрація, зберігання і обробка даних. — 2019. — Т. 21, № 2. — С. 3–11. — Бібліогр.: 10 назв. — рос. |
| work_keys_str_mv |
AT ûhimenkobi algoritmmuravʹinoikoloniidlâmnogomernoizadačiorance AT tkalenkooû algoritmmuravʹinoikoloniidlâmnogomernoizadačiorance AT ûhimenkobi algoritmmurašinoíkoloníídlâbagatovimírnoízadačíproranecʹ AT tkalenkooû algoritmmurašinoíkoloníídlâbagatovimírnoízadačíproranecʹ AT ûhimenkobi analgorithmofantscolonyforthemultidimensionalknapsackproblem AT tkalenkooû analgorithmofantscolonyforthemultidimensionalknapsackproblem |
| first_indexed |
2025-11-25T14:43:52Z |
| last_indexed |
2025-11-25T14:43:52Z |
| _version_ |
1850517814040854528 |
| fulltext |
ISSN 1560-9189 , , 2019, . 21, 2 3
519.854
. . , . .
, 1, 65044 ,
-
.
.
. -
,
-
, .
, -
«1» . -
-
. -
.
: , -
, , -
.
, ,
.
. -
NP-
. -
- .
, -
.
-
, .
.
, -
. -
© . . , . .
. . , . .
4
, , . -
, , , -
.
,
. , -
.
-
-
.
-
XXI- , -
, ,
.
-
. , -
. NP-
. -
, ,
, ,
.
, -
, , -
. ( )
. . -
— ,
. [1].
. ,
, ,
— . « , -
» [2]. [2] -
. .
, . -
.
, . , -
. .
. -
. -
, , -
.
, , -
, -
. , -
ISSN 1560-9189 , , 2019, . 21, 2 5
— -
, .
( ) , . , [4]
« » -
. , ,
,
. -
.
. -
- ( . [2] [3]),
« » -
.
— ( ) -
, « »
.
. -
. .
— .
-
. -
. — -
, , -
. -
.
. -
[5]. -
- . , -
— .
, ( )
[6]. -
[4]. [7, 8]
. -
. -
. ,
, -
. -
. . , . .
6
, -
( . . [9]).
, -
. . -
, . [3]
,
.
-
.
:
1
max
n
j j
j
z c x ,
1
, 1,
n
ij j i
j
a x b i m ,
0,1 , 1,jx j n .
— .
:
n — ( 1, )j n ;
m — ),1( mi ;
r — ),1( rk ,
;
mina — , ;
— , ;
T — ),1( Tt ;
j — , j- -
«1» ;
k
jV — j k- , jx
«1» -
;
k
jp — jx - k- -
;
kI — k- .
-
k- :
ISSN 1560-9189 , , 2019, . 21, 2 7
min min( )j
j
j
a a a
na . (1)
k
jV
:
= 0, = 1, , = 1, .
k
k k
j i ij
j I
V j b a i m k r
jx -
- :
rkVj
cca
cca
p k
j
Vj
jj
jjk
j
k
j
,1,,
)(
)(
min
min , (2)
min min 1
k
j
j
j V
.
(2) -
. , .
. -
(0,1). -
.
,
0, ( 1, )k
jV k r . r
1 2( , ,..., )k k k k
nX x x x j :
1
, 1, .
r
k
j j
k
x j n
t ( 2)t ja , -
(1). ja ,
0 0 ( (0,1))q q .
1. , mina , r1, T.
2. 00, , 1, , 1.jZM a q j n t
3. 1 2= ( , ,..., ), = 1, , , = 1.k k k k k
nX x x x k r I r r
4. , 1, .k
jV k r
. . , . .
8
5. 0 0,k
jV .12.
6. , 1, , 1, .k
jp j n k r
7. k
jp k
jV
0
,k
jx
«1», 1, .k r
8.
0
1, 1,k
jx k r ,
0
, 1, .k k k
jI I x k r
9. , 1, .j j n
10. , 1, .ja j n
11. . 4.
12. ;1rr
0kz .
13. r = 0, . 15.
14. . 4.
15. 0
0 1, = 1, = max , = k
k kk rr r z Z X X .
16.
0
,kz ZM . 18.
17. 0
0
, ;k
kZM z XM X .
18. .
19. t = t + 1.
20. t < T, . 3.
21. .
-
-
. 30×70, 40×90, 50×110 -
250×510, 500×1010. j ija
, (1:10) (1:10)
. ija -
:
1 , 1, .
3
n
ij
j
i
a
b i m
, -
0,1, 0,3. m×n 10 .
( ).
. , -
. , , -
[4].
( ) ,
ISSN 1560-9189 , , 2019, . 21, 2 9
-
.
.
1.
, -
.
.
2.
10 .
3. , 1 % 2 %,
. . 1 .
.
1.
1 % 2 %%
= 0,1 = 0,3 = 0,1 = 0,3
10 3 6 5 9
20 7 6 9 9
30 9 9 10 10
40 9 8 10 10
50 9 9 10 10
60 10 7 10 10
70 9 8 10 10
.
.
4. 10 , -
10, , -
( 10). «1»
, .
. . , . .
10
, , -
, 20–40 .
5. . -
( )
- . . 2 .
2.
6. , ,
( [2]).
7. , -
, -
.
8. -
.
. -
. ,
, ,
, ,
. , -
. . -
-
. , ,
, .
, -
,
. , -
.
—
.
1. . . , , . : . 2000. 132 .
= 0,1 = 0,3
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 8 9 10
10 1 0 0 0 0 13 0 0 0 13 0 13 13 0 8 0 0 0
20 15 2 0 15 6 0 0 0 0 0 9 0 0 0 0 0 0 0
30 14 4 4 2 0 0 14 0 0 3 0 0 0 3 0 0 11 14
40 3 3 0 0 3 1 0 1 0 1 0 3 3 3 0 0 0 4
50 0 2 1 0 1 0 1 7 0 0 0 0 5 0 0 1 0 0
60 1 0 4 0 2 0 14 1 2 0 0 0 2 3 0 0 0 0
70 3 0 0 0 4 0 0 1 0 1 0 1 1 0 0 12 1 2
ISSN 1560-9189 , , 2019, . 21, 2 11
2. . . : . . 2005.
4. . 1–16.
3. . ., . . -
p- . . 2004. 3. . 80–88.
4. . ., . . . -
: , 2007. 303 .
5. . . . I, II.
. 1965. 1, 2.
6. . ., . . : .
. 1999. . 2. 2(4). . 68–93.
7. . .
. -
«Project, Program, Portfolio, Management». 2016. . 1. . 143–146.
8. . . -
.
. 2015. . 5. 4. . 389–395.
9. . ., . .
. . -
. - . 2005. . 2. . 199–204.
10. . ., . .
. . 2017. . 22. . 2(30). . 104–113.
27.05.2019
|