Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака
In order to enhance the effectiveness of the quantum genetic algorithm (QGA), it is proposed to switch to higher-order quantum registers in the quantum chromosome representation. Such representation makes it possible to apply a powerful quantum computations mechanism – quantum state entanglement. In...
Saved in:
| Date: | 2018 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2018
|
| Subjects: | |
| Online Access: | https://journal.iasa.kpi.ua/article/view/132427 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1866302231203020800 |
|---|---|
| author | Tkachuk, Valerii M. Tkachuk, Orysya M. |
| author_facet | Tkachuk, Valerii M. Tkachuk, Orysya M. |
| author_sort | Tkachuk, Valerii M. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-01-17T13:31:43Z |
| description | In order to enhance the effectiveness of the quantum genetic algorithm (QGA), it is proposed to switch to higher-order quantum registers in the quantum chromosome representation. Such representation makes it possible to apply a powerful quantum computations mechanism – quantum state entanglement. In the algorithm implementation, we also use an adaptive quantum gate operator and propose a quantum chromosome recovery technology for solving constrained combinatorial optimization problems. The influence of the quantum register size on the algorithm efficiency has been investigated. The advantages of the suggested approach in comparison with the QGA traditional implementation are demonstrated on the example of multidimensional 0–1 knapsack problem and different levels of input data correlation. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2018.3.05 |
| first_indexed | 2025-07-17T10:23:59Z |
| format | Article |
| fulltext |
В.М. Ткачук, О.М. Ткачук, 2018
52 ISSN 1681–6048 System Research & Information Technologies, 2018, № 3
УДК 004.023, 539.18
DOI: 10.20535/SRIT.2308-8893.2018.3.05
КВАНТОВИЙ ГЕНЕТИЧНИЙ АЛГОРИТМ ВИЩИХ ПОРЯДКІВ
ДЛЯ 0–1 ЗАДАЧІ ПАКУВАННЯ РЮКЗАКА
В.М. ТКАЧУК, О.М. ТКАЧУК
Анотація. Для підвищення ефективності роботи квантового генетичного алго-
ритму (QGA) запропоновано в поданні квантової хромосоми перейти до кван-
тових регістрів вищих порядків. Таке подання дозволяє використати такий по-
тужний механізм квантових обчислень, як заплутаність квантових станів. Для
реалізації алгоритму використано адаптивний оператор квантового гейту та
запропоновано технологію відновлення квантової хромосоми для розв’язання
комбінаторних задач з обмеженнями. Досліджено вплив розміру квантового
регістра на ефективність роботи алгоритму. Переваги запропонованого підхо-
ду порівняно із традиційною реалізацією QGA проілюстровано на прикладі
0–1 задачі пакування рюкзака великої розмірності та різного рівня кореляції
вхідних даних.
Ключові слова: квантовий генетичний алгоритм, 0–1 задача пакування рюк-
зака, оператор квантового гейту, кубіт, квантовий регістр, заплутаність кван-
тових станів.
ВСТУП
Класичний генетичний алгоритм є стохастичним алгоритмом оптимізації,
робота якого ґрунтується на принципах еволюції біологічних систем [1]. Для
пошуку оптимального значення використовується випадковим чином згене-
рована множина можливих розв’язків – популяція, за допомогою якої дослі-
джується область пошуку. Алгоритм використовує кращі з них для їх від-
творення та поступового ітераційного наближення до оптимуму в ході
еволюції популяції в часі [2].
Квантовий генетичний алгоритм (QGA) є відносно новим еволюційним
алгоритмом, який ґрунтується на поєднанні принципів квантових обчислень,
таких як квантові біти, квантові гейти, суперпозиція станів і технології кла-
сичних генетичних алгоритмів [3,4]. Він проілюстрував свою ефективність
для широкого класу задач оптимізації та пошуку, які потребують наближе-
них, по можливості максимально близьких до оптимуму, розв’язків [4–8].
Порівняно з класичним підходом QGA забезпечує кращий баланс між гло-
бальним пошуком і технологією локальної збіжності [4, 5].
Алгоритм QGA працює також із множиною потенційних розв’язків, але
ймовірнісний механізм роботи квантових генетичних операторів забезпечує
глобальний пошук за швидкої локальної збіжності та невеликого розміру
популяції. Замість бінарного подання популяції QGA використовує її кван-
тово-механічне, імовірнісне подання, що також забезпечує збереження різ-
номанітності популяції в ході еволюції.
Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака
Системні дослідження та інформаційні технології, 2018, № 3 53
Згідно із працею [3] мінімальною одиницею інформації у квантових
обчисленнях є кубіт q — квантова система, що може перебувати в двох
основних станах: 0 та 1 . Відповідно до принципу суперпозиції він може
перебувати у довільному стані, що є лінійною комбінацією базових:
10 21 q . (1)
Інформація, що міститься в амплітудах 1 та 2 , власне є квантовою
частиною інформації. Фактично 2
1 та 2
2 — імовірності знаходження кубіта
у станах 0 та 1 відповідно, тому вони повинні задовольняти умову нор-
мування:
12
2
2
1 .
Якщо скористатися матричним поданням квантових станів
0
1
0 ,
1
0
1 ,
то стан кубіта (1) можна задати як
2
1
q .
Для реалізації QGA [4, 5] зазвичай заплутаність квантових станів не
використовується, тому хромосома являє собою впорядкований набір не-
залежних кубітів. Так, якщо довжина 16N кубітів, її можна подати у ви-
гляді
Для задачі 0–1 пакування рюкзака довжина хромосоми N визначається
загальною кількістю предметів, які можна помістити в нього.
ЗАСТОСУВАННЯ QGA ДО ЗАДАЧ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ
Загальна схема роботи QGA аналогічна класичному генетичному алгоритму.
Принципова відмінність виявляється у способі подання потенційних
розв’язків, використовуваних квантових генетичних операторах, особливос-
тях їх реалізації з урахуванням подання хромосоми як системи кубітів,
принципу суперпозиції та заплутаності квантових станів.
Алгоритм QGA можна реалізувати у такому вигляді:
Квантовий генетичний алгоритм
1 0t
2 ініціалізація )(tQ
3 квантове вимірювання )(tQ та перехід до )(tP
4 оцінка пристосованості )(tP
q q q q q q q q q q q q q q q q
В.М. Ткачук, О.М. Ткачук
ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 54
5 відновлення )(tP
6 відновлення )(tQ
7 знаходження b — найкращого розв’язку в )(tP
8 while(умова завершення еволюції)
9 1 tt
10 оновлення )(tQ за допомогою квантового гейту
11 квантове вимірювання )(tQ та перехід до )(tP
12 оцінка пристосованості )(tP
13 відновлення )(tP
14 відновлення )(tQ
15 знаходження b — найкращого розв’язку в )(tP
16 end while
Тут )(tQ — квантова популяція розв’язків на момент часу t; )(tP —
класичне (бінарне) подання популяції, отримане в результаті квантового ви-
мірювання.
МЕТА ДОСЛІДЖЕННЯ
Мета дослідження — включення в роботу QGA такого потужного механізму
квантових обчислень, яким є заплутаність квантових станів. Можливості
реалізації цього алгоритму частково проаналізовано у праці [6], де проілюс-
тровано ефективність такого підходу до задач комбінаторної оптимізації.
Загальну ідею його реалізації в задачах функціональної оптимізації детально
розглянуто у праці [7].
Принципова відмінність у реалізації QGA вищих порядків полягає у
потребі під час реалізації квантових операторів ураховувати заплутаність
станів квантових регістрів. Якщо кожні два кубіти хромосоми попарно пе-
ребувають у заплутаному стані, то її можна подати у такому вигляді:
Тут iR — квантовий регістр, що складається із двох кубітів ( 2r ), які пе-
ребувають у заплутаному стані. Кількість можливих станів такого регістра
422 2 rn .
У результаті квантового вимірювання він може перейти в один із чоти-
рьох можливих основних станів:
00 , 01 , 10 , 11 .
У загальному випадку така система перебуває в стані, що є лінійною
комбінацією базових:
11100100 4321 q .
Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака
Системні дослідження та інформаційні технології, 2018, № 3 55
Тут 2
1 , 2
2 , 2
3 та 2
4 — імовірності перебування квантового
регістра у відповідному стані. У разі переходу до 2r розмір матриці M,
потрібний для подання квантової хромосоми, залишається незмінним. Так,
для подання одного кубіта засобами класичного комп’ютера потрібні два
елементи матриці, тому
324
2
2
2
2
NN
NM r .
У разі переходу до квантових регістрів вищих порядків, тобто, якщо
2r ,
N
r
N
M r 22 .
Це означає, що в цьому випадку для подання квантової хромосоми не-
обхідно додатково збільшити розмір матриці, потрібний для подання як од-
нієї особини, так і популяції в цілому. Так, якщо 4r , квантова хромосома
складатиметься із чотирьох регістрів ),,,( 4321 RRRR :
Кількість основних станів регістра дорівнює 1624 :
0000 , 0001 , 0010 , … , 1111 .
Згідно з принципом суперпозиції (1) стан одного регістра можна подати як
1111....001000010000 16321 q .
Розмір матриці, потрібний для подання однієї такої квантової хромосо-
ми,
322642
4
16
2 4 N
r
N
M r .
Для реалізації QGA вищого порядку для подання особини популяції
зручно використати структуру, що складається з rNk квантових регіст-
рів відповідно до такої схеми:
1R 2R 3R iR kR
1
1 2
1 3
1 i
1 k
1
1
2 2
2 3
2 i
2 k
2
1
2r 2
2r 3
2r
i
r2
k
r2
Тут },...,,,{
2321
iiii
r визначає стан одного квантового регістра iR , а
множина },...,,,{ 321 kRRRR формує одну особину популяції.
В.М. Ткачук, О.М. Ткачук
ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 56
ІНІЦІАЛІЗАЦІЯ ПОЧАТКОВОЇ КВАНТОВОЇ ПОПУЛЯЦІЇ
Початковий стан як кубіта, так і квантового регістра в цілому не містить ін-
формації про задачу та алгоритм її розв’язання, тому найпростішим спосо-
бом його ініціалізації є рівність усіх амплітуд між собою [3,4]. Це означає,
що на початку еволюції кожен квантовий регістр розміру r перебуває в стані:
11...11
2
1
10...11
2
1
...01...00
2
1
00...00
2
1
rrrr
q .
УМОВА ЗАВЕРШЕННЯ ЕВОЛЮЦІЇ
Як умовою завершення еволюційного процесу можна скористатися одним із
таких критеріїв:
кількість звернень до функції пристосованості. Це 5000 звернень до
функції пристосованості [4–7]. Ця умова використовується для порівняння
ефективності різного типу еволюційних алгоритмів;
загальний час роботи. Дозволяє порівняти ефективність однотипних
алгоритмів, що відрізняються тими чи іншими особливостями реалізації;
усереднене значення ймовірностей квантових станів популяції [9].
Для подання хромосоми з використанням квантових регістрів критерій мо-
жна задати у такий спосіб:
k
i
b
i
i
avr k
c
1
2
21
1
;
s
i
i
avravr c
s
C
1
1
,
де стан b визначається класичним значенням відповідного квантового регіс-
тра, отриманого в результаті квантового вимірювання; s — потужність по-
пуляції. Так, якщо 99.0 , у середньому 99% імовірностей квантових ста-
нів майже збігаються до значення одного з основних станів регістра.
Операція вимірювання (етапи 3 та 11 роботи QGA) стану квантового
регістра реалізовано згідно із запропонованим у праці [6, 7] підходом і додат-
кового пояснення не потребує. Схематично процес вимірювання стану регіст-
ра iR та перехід до класичного його подання можна зобразити таким чином:
i
0
i
1
i
r2
Вимірювання
Усього r вінарних знаків
Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака
Системні дослідження та інформаційні технології, 2018, № 3 57
ОПЕРАТОР КВАНТОВОГО ГЕЙТУ
Для реалізації обертання квантових станів для визначення кута та напрямку
повороту традиційно використовується таблиця пошуку [4,5], що принципо-
во обмежує універсальність роботи QGA. Фіксоване значення кута, яке ви-
користовується при цьому, також негативно впливає на швидкість збіжнос-
ті, тому QGA інколи реалізують як адаптивний процес зміни його величини
у процесі еволюції [5]. Більш ефективним, як показали проведені моделю-
вання, може бути адаптивний характер роботи самого оператора квантового
гейту.
Роботу оператора можна поділити на два етапи. На першому етапі збі-
льшується амплітуда ймовірності вибраного стану квантового регістра iR :
)][1(][)( 22 b
i
b
i
b
i , (2)
де стан b визначається класичним поданням квантового регістра iR най-
кращої особини популяції, що була отримана на попередній ітерації за ча-
сом. Функціональна залежність (2) забезпечує також той факт, що b
i не мо-
же перевищувати 1. Параметр визначає кут повороту квантових станів,
підбирається за результатами модельних досліджень і перебуває в межах ]1,0[ .
На другому етапі необхідно зменшити амплітуди ймовірностей інших
станів квантового регістра iR для виконання умови нормування. Таким чи-
ном, у кожному новому поколінні забезпечується збільшення ймовірності
того, що в результаті спостереження генеруються класичні особини, більш
схожі на найкращу.
У цілому алгоритм роботи оператора до квантової хромосоми, що
складається із rNk регістрів, можна реалізувати таким чином:
Оператор квантового гейту
1 for },...,1{ r
Ni do
2 0s
3 for }12,...,0{ rj do
4 j
ji rs 2bs
2
5 end for
6 2][1 s
iM
7 )][1(][ 22 s
i
s
i
s
i
8 MM
s
i )][1( 2
9 for }12,...,0{ rj do
10 if sj then
11 j
i
j
i M
12 end if
В.М. Ткачук, О.М. Ткачук
ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 58
13 end for
14 end for
Динаміку поведінки пристосованості найкращої особини популяції за-
лежно від величини ілюструє рис. 1. З огляду на ймовірнісний характер
роботи алгоритму надалі всі значення наведено як результат усереднення за
100 запусками QGA. Як випливає із наведених даних, розмір квантового ре-
гістра не впливає на величину оптимального значення параметра . Під час
проведення експерименту за оптимальне значення можна взяти 09,0 .
ЗАДАЧА ПАКУВАННЯ РЮКЗАКА
Проблема 0–1 пакування рюкзака є NP — повною задачею дискретної
комбінаторної оптимізації, яка традиційно використовується для тесту-
вання пошукових алгоритмів. Вона зводиться до знаходження для скін-
ченної множини N речей такого бінарного вектора заповнення
},...,,,{ 321 NxxxxX , який забезпечує максимальне значення функції
N
i
ii xpXf
1
)(
і задовольняє обмеження
N
i
ii Cx
1
, (3)
де ip — вартість i-го предмета; i — маса i-го предмета; C — максималь-
но можлива маса рюкзака.
Рис. 1. Вплив параметра на середню пристосованість найкращої особини avrf
за різних розмірів квантового регістра для 500N некорельованих вхідних даних
r = 1
r = 4
Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака
Системні дослідження та інформаційні технології, 2018, № 3 59
У процесі ініціалізації популяції чи її еволюції завжди є ймовірність
отримати ряд «поганих» особин, для яких не виконується обмеження (3) і
які необхідно «відремонтувати». Процедура «ремонту» може бути зведена
до видалення випадковим чином елементів з рюкзака доти, доки не викона-
ється обмеження (3). Після відновлення функція пристосованості набуде
вигляду
N
i
ii xpXf
1
)( ,
де },...,,,{ 321 NxxxxX — відновлена версія бінарного вектора X.
Процедура відновлення в QGA принципово інша, ніж в класичному ге-
нетичному алгоритмі, оскільки потребує коригування і ймовірностей кван-
тових станів. На першому, традиційному етапі, якщо рюкзак надто важкий,
елементи видаляються з нього доти, доки не буде задоволено обмеження (3).
Якщо рюкзак надто легкий, то в рюкзак випадковим чином додаються речі,
поки це дозволяє обмеження маси.
Перший етап роботи оператора можна подати у вигляді такого алго-
ритму:
«Ремонт» класичної хромосоми )(tP
// видалення випадковим чином речей з рюкзака
1 переповнення_рюкзака false
2 if
N
i
ii Cx
1
then
3 переповнення_рюкзака true
4 end if
5 while(переповнення_рюкзака true )
6 }...1{ Nrandomk — вибір випадковим чи-
ном предмета з рюкзака
7 0kx — видалення предмета з рюкзака
8 if
N
i
ii Cx
1
then
9 переповнення_рюкзака false
10 end if
11 end while
// додавання випадковим чином речей до рюкзака
12 for },...,1{ Di
13 }...1{ Nrandomk — вибір випадковим чи-
ном предмета для рюкзака
14 if
N
i
kii Cx
1
or )1( kx then
15 continue
16 end if
17 1kx
18 end for
В.М. Ткачук, О.М. Ткачук
ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 60
Тут NdD 02,0 — параметр роботи оператора відновлення. Його ве-
личина визначає кількість спроб випадковим чином додавання предметів до
рюкзака. Згідно з проведеними дослідженнями за оптимальне можна взяти
значення 64d ; воно забезпечує ефективність процесу відновлення за
незначного, у межах 15%, зростання часу роботи алгоритму в цілому
(рис. 2). Такий алгоритм «ремонту» забезпечує різноманітність популяції та
ефективний глобальний пошук за множиною всіх допустимих розв’язків.
На другому етапі необхідно відкоригувати амплітуди ймовірностей
квантової хромосоми відповідно до нової, відновленої класичної хромосо-
ми X . Процес відновлення реалізовано як оператор квантового гейту, на-
прямок кута повороту, у якому визначається значенням відновленої класич-
ної хромосоми. Такий алгоритм забезпечує збереження генетичної інформації,
яку нагромадила особина в процесі всієї своєї попередньої еволюції:
Відновлення квантової хромосоми
1 for },...,1{ r
Ni do
2 0s
3 for }12,...,0{ rj do
4 j
ji rxss 2
2
5 end for
6 2][1 s
iM
7 )][1(][ 22 s
i
s
i
s
i
8 MM
s
i )][1( 2
9 for }12,...,0{ rj do
Рис. 2. Вплив параметра відновлення d на ефективність роботи алгоритму, якщо
500N , сильнокорельованих вхідних даних 2)( r
Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака
Системні дослідження та інформаційні технології, 2018, № 3 61
10 if sj then
11 j
i
j
i M
12 end if
13 end for
14 end for
Тут ]1,0[ — параметр відновлення. Його вплив на ефективність ро-
боти QGA ілюструє рис. 3. Така поведінка є типовою, не залежить від рівня
кореляції вхідних даних та розміру квантового регістра. Як випливає
з рис. 3, оптимальним для подальших досліджень можна вважати 15.0 .
РЕЗУЛЬТАТИ ЧИСЛОВОГО ЕКСПЕРИМЕНТУ
Квантовий генетичний алгоритм вищого порядку реалізовано на С++, а мо-
делювання виконано на процесорі Intel Celeron CPU G1840 2,80 GHz, 4,0 Гб
оперативної пам’яті. Для ілюстрації ефективності роботи алгоритму розгля-
нуто ряд задач комбінаторної оптимізації великої розмірності та різного
рівня кореляції вхідних даних (рис. 4). Задачі малої розмірності не розгля-
даються, оскільки за умови 100N отримуються майже точні результати,
що не дозволяє оцінити вплив розміру квантового регістра на ефективність
запропонованого алгоритму. Розмір популяції 10s , що забезпечує 5000
звернень до функції пристосованості за часу еволюції 500t .
Вплив розміру квантового регістра на середній час роботи QGA пока-
зано на рис. 5. Якщо 1r , маємо випадок класичного квантового генетич-
ного алгоритму і власне відносно нього виконано порівняння ефективності
переходу до QGA вищого порядку. Середній час роботи avrt залежить тіль-
Рис. 3. Вплив на середню пристосованість найкращої особини avrf та середньо-
квадратичне відхилення sdf для 500N некорельованих вхідних даних, якщо
3r
В.М. Ткачук, О.М. Ткачук
ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 62
ки від розмірів області пошуку, яка для задачі пакування рюкзака ви-
значається лише довжиною квантової хромосоми N (множиною речей).
Рис. 4. Розподіл вартості предметів як функція їх маси p для різного рівня
кореляції вхідних даних: А — некорельовані дані; B — слабокорельовані дані;
C — сильнокорельовані дані
A B
C
3
3
3
Рис. 5. Середній час роботи avrt як функція розміру квантового регістра r для
500N некорельованих вхідних даних
r
t a
vr
cc
Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака
Системні дослідження та інформаційні технології, 2018, № 3 63
Як видно з рис. 6, якщо як критерій зупинки використати середній час
роботи QGA першого порядку ( 1r ), то найефективнішими можна вважати
розміри квантового регістра 3 та 6 кубітів.
Згенерована на початку роботи QGA популяція ( 0t ) включає широ-
кий спектр усіх можливих розв’язків (рис. 7), які однак достатньо далекі від
оптимального значення. Це означає, що робота QGA починається з випадко-
вого пошуку. На початкових етапах еволюції в межах часу до 150100t
основним механізмом пошуку є глобальний пошук, зумовлений імовірніс-
ним характером роботи оператора квантового вимірювання. Розподіл
розв’язків поступово зсувається до оптимального значення за майже не-
змінної величини середньоквадратичного відхилення (різноманітності
розв’язків).
Рис. 6. Вплив розміру квантового регістра r на величину avrf для 500N
некорельованих вхідних даних
Рис. 7. Усереднений розподіл розв’язків по області пошуку залежно від часу
еволюції популяції t
t=0
t=100
t=500
f(x)
В.М. Ткачук, О.М. Ткачук
ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 64
На кінцевих етапах еволюції ( 500t ) характер розподілу зазнає прин-
ципових змін, що означає включення механізму локального пошуку за раху-
нок оператора квантового гейту. Детальніше механізм роботи QGA на різ-
них етапах еволюції проаналізовано у праці [7].
Статистичні результати моделювання — середнє значення найкращої
особини популяції avrf , середньоквадратичне відхилення sdf , найкращий
та найгірший результати, середній час роботи avrt при розв’язанні тестових
задач великої розмірності — наведено в тaбл. 1–9. Розрахунки виконано за
розмірів квантового регістра в межах 1–7 кубітів, бо власне за таких значень
час роботи не перевищує час роботи традиційного QGA.
Т а б л и ц я 1 . Результати оптимізації, якщо 200N некорельованих
даних (точне значення — 11238)
r avrt , с avrf sdf Найкраще
значення
Найгірше
значення
1 0,066 10903 651,9 11238 8872
2 0,042 10848 708,7 11238 9020
3 0,036 11137 131,4 11238 10630
4 0,034 10861 674,7 11238 8767
5 0,035 10825 708,7 11238 8989
6 0,040 11135 133,2 11238 10693
7 0,048 11119 157,3 11238 10509
Т а б л и ц я 2 . Результати оптимізації, якщо 500N некорельованих
даних (точне значення — 28857)
r avrt , с avrf sdf Найкраще
значення
Найгірше
значення
1 0,175 27984 730,4 28623 25207
2 0,116 27987 741,3 28703 22020
3 0,098 28048 396,1 28834 27244
4 0,095 27974 735,4 28834 22926
5 0,097 27936 747,9 28834 22751
6 0,109 28041 416,3 28801 26746
7 0,136 28023 398,1 28790 26988
Т а б л и ц я 3 . Результати оптимізації, якщо 1000N некорельованих
даних (точне значення — 54503)
r avrt , с avrf sdf Найкраще
значення
Найгірше
значення
1 0,372 49802 1243.3 52610 46101
2 0,233 49785 1224,3 52511 46127
3 0,203 50330 971,9 53482 47600
4 0,197 49882 1270,6 52598 46414
5 0,202 49780 1310,0 52338 46737
6 0,233 50311 982,6 52203 47434
7 0,281 50319 922,1 52348 47871
Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака
Системні дослідження та інформаційні технології, 2018, № 3 65
Т а б л и ц я 4 . Результати оптимізації, якщо 200N слабокорельованих
даних (точне значення — 1634)
r avrt , с avrf sdf Найкраще
значення
Найгірше
значення
1 0,068 1542,1 31,3 1634 1486
2 0,044 1544,0 33,5 1627 1478
3 0,039 1608,3 16,6 1624 1544
4 0,036 1542,3 33,0 1633 1497
5 0,038 1543,5 32,5 1634 1495
6 0,044 1608,0 17,2 1634 1567
7 0,054 1608,1 17,6 1634 1541
Т а б л и ц я 5 . Результати оптимізації,якщо 1000N слабокорельованих
даних (точне значення — 4566)
r avrt , с avrf sdf Найкраще
значення
Найгірше
значення
1 0,194 4309,6 152,5 4493 3899
2 0,127 4313,5 128,3 4517 3933
3 0,101 4373,0 61,9 4506 4179
4 0,098 4302,1 157,4 4514 3953
5 0,100 4301,6 155,0 4489 3950
6 0,114 4371,8 62,9 4508 4176
7 0,141 4376,6 63,2 4512 4130
Т а б л и ц я 6 . Результати оптимізації, якщо 1000N слабокорельованих
даних (точне значення — 9052)
r avrt , с avrf sdf Найкраще
значення
Найгірше
значення
1 0,368 8260,6 139,8 8582 7918
2 0,239 8267,9 139,0 8621 7830
3 0,203 8309,1 129,2 8697 7945
4 0,197 8261,3 142,9 8604 7917
5 0,202 8253,1 146,8 8579 7973
6 0,227 8311,7 129,5 8679 7991
7 0,300 8309,7 138,4 8668 7818
Т а б л и ц я 7 . Результати оптимізації, якщо 200N сильнокорельованих
даних (точне значення — 2697)
r avrt , с avrf sdf Найкраще
значення
Найгірше
значення
1 0,066 2580,3 86,5 2697 2397
2 0,043 2579,7 84,0 2697 2494
3 0,037 2661,6 47,1 2697 2594
4 0,035 2578,5 85,4 2697 2493
5 0,035 2574,1 84,2 2697 2491
6 0,041 2659,9 48,5 2697 2593
7 0,050 2663,4 46,7 2697 2594
В.М. Ткачук, О.М. Ткачук
ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 66
Т а б л и ц я 8 . Результати оптимізації, якщо 500N сильнокорельованих
даних (точне значення — 7117)
r avrt , с avrf sdf Найкраще
значення
Найгірше
значення
1 0,184 6791,2 175,2 7017 6409
2 0,115 6784,3 177,9 7017 6315
3 0,099 6898,9 76,3 7017 6716
4 0,097 6788,9 178,2 7017 6317
5 0,098 6787,6 172,8 7017 6417
6 0,112 6896,5 73,4 7017 6717
7 0,142 6891,2 75,3 7017 6714
Т а б л и ц я 9 . Результати оптимізації, якщо 1000N сильнокорельованих
даних (точне значення — 14390)
r avrt , с avrf sdf Найкраще
значення
Найгірше
значення
1 0,361 13532,0 157,0 13887 13074
2 0,234 13528,2 157,2 13884 13089
3 0,203 13577,8 155,3 13890 13186
4 0,197 13534,2 156,6 13883 13088
5 0,204 13529,7 161,2 13874 13162
6 0,228 13567,0 156,2 13890 13190
7 0,287 13564,0 155,7 13889 13190
ВИСНОВКИ
У роботі запропоновано новий квантовий генетичний алгоритм вищого по-
рядку та проілюстровано ефективність його роботи на прикладі задач 0–1
пакування рюкзака великої розмірності та з різним рівнем кореляції даних.
Для подання квантової хромосоми застосовано квантові регістри вищих по-
рядків ( 1r ), використання яких дозволяє включити в роботу такий меха-
нізм інтенсифікації квантових обчислень, як заплутаність квантових станів.
Такий перехід зменшує час роботи алгоритму майже в два рази, точність
пошуку розв’язку залишається незмінною, а за деяких розмірів регістра на-
віть зростає.
Використання адаптивного оператора квантового гейту та оператора
відновлення квантової хромосоми забезпечує ефективне поєднання глоба-
льного та локального пошуку алгоритму. Запропонований оператор віднов-
лення квантової хромосоми, робота якого реалізована аналогічно до прин-
ципів роботи квантового гейту, забезпечує збереження генетичної
інформації, що набула особина в ході всієї своєї попередньої еволюції.
Ефективність роботи запропонованого QGA вищого порядку оцінено
порівняно із традиційним QGA ( 1r ). Порівняння з іншими алгоритмами
розв’язку задач оптимізації не виконувалося, бо, як випливає з багатьох пу-
блікацій [6,10,11], його можна вважати одним з найефективніших.
Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака
Системні дослідження та інформаційні технології, 2018, № 3 67
Експериментальні результати 0–1 задачі пакування рюкзака ілюстру-
ють можливості застосування QGA до задач великої розмірності за розмірів
популяції, що не перевищують 10 особин. За співвідношенням швидко-
дія/ефективність оптимальним можна вважати розмір квантового регістра
3r і 6r .
ЛІТЕРАТУРА
1. Holland J.H. Adaptation in natural and artificial systems. An introductory analysis
with application to biology, control, and artificial intelligence / J.H. Holland. —
London: Bradford book edition, 1994. — 211 p.
2. Simon D. Evolutionary Optimization Algorithms: Biologically Inspired and Popula-
tion-Based Approaches to Computer Intelligence / D. Simon. — John Wiley &
Sons, 2013. — 742 p.
3. Narayanan A. Quantum-inspired genetic algorithms / A. Narayanan, M. Moore //
Proceedings of the IEEE International Conference on Evolutionary Computation
(ICEC’96), Nagoya, Japan, 1996. — P.61–66.
4. Han K.–H. Genetic quantum algorithm and its application to combinatorial optimiza-
tion problem / K.–H. Han, J.–H. Kim // Proc.Congress on Evolutionary Compu-
tation. — Vol. 2. — La Jolla, CA, July 2000. — P. 1354–1360.
5. Wang H. The improvement of quantum genetic algorithm and its application on
function optimization / H. Wang, J. Liu, J. Zhi, C. Fu // Math. Probl. Eng. —
2013. — P.1–10.
6. Nowotniak R. Higher-Order Quantum-Inspired Genetic Algorithms / R. Nowotniak,
J. Kucharski // Federated Conference on Annals of Computer Science and Infor-
mation Systems, 2014. — P. 465–470.
7. Tkachuk V. Quantum Genetic Algorithm Based on Qutrits and Its Application /
V. Tkachuk // Mathematical Problems in Engineering. — Vol. 2018, Article ID
8614073, 8 p.
8. Zhang G. Quantum-inspired evolutionary algorithms: a survey and empirical study /
G. Zhang // Journal of Heuristics. — 2010. — P. 1–49.
9. Han K. Quantum-inspired evolutionary algorithms with a new termination criterion,
h-epsilon gate, and two-phase scheme / K. Han, J. Kim // IEEE Trans. Evol.
Comput. — 2014. — 8 (2). — P. 156–169.
10. Iimura I. Integer-Type Gene-Coding Method Based on Quantum Bit Representation
in Quantum-Inspired Evolutionary Algorithm: Application to Integer Knapsack
Problem / I. Iimura // Journal of Signal Processing. — 2012. — Vol. 16, N 6. — P.
495–502.
11. Takata T. Performance Analysis of Quantum-Inspired Evolutionary Algorithm /
T. Takata, T. Isokawa, A. Saitoh et al // SCIS & ISIS 2010, Dec. 8-12, Okayama
Convention Center, Okayama, Japan.
Надійшла 10.07.2018
|
| id | journaliasakpiua-article-132427 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:23:59Z |
| publishDate | 2018 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/4a/50498010eb1e14a2d51fc41717400e4a.pdf |
| spelling | journaliasakpiua-article-1324272019-01-17T13:31:43Z Higher-order quantum genetic algorithm for 0-1 knapsack problem Квантовый генетический алгоритм высших порядков для 0–1 задачи упаковки рюкзака Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака Tkachuk, Valerii M. Tkachuk, Orysya M. quantum genetic algorithm 0-1 knapsack problem quantum gate operator quantum register entanglement of quantum states квантовый генетический алгоритм 0-1 задача о ранце оператор квантового гейта квантовый регистр запутанность квантовых состояний квантовий генетичний алгоритм 0-1 задача пакування рюкзака оператор квантового гейту квантовий регістр заплутаність квантових станів In order to enhance the effectiveness of the quantum genetic algorithm (QGA), it is proposed to switch to higher-order quantum registers in the quantum chromosome representation. Such representation makes it possible to apply a powerful quantum computations mechanism – quantum state entanglement. In the algorithm implementation, we also use an adaptive quantum gate operator and propose a quantum chromosome recovery technology for solving constrained combinatorial optimization problems. The influence of the quantum register size on the algorithm efficiency has been investigated. The advantages of the suggested approach in comparison with the QGA traditional implementation are demonstrated on the example of multidimensional 0–1 knapsack problem and different levels of input data correlation. Для повышения эффективности работы квантового генетического алгоритма (QGA) предложено в представлении квантовой хромосомы перейти к квантовым регистрам высших порядков. Такое представление позволяет использовать такой мощной механизм квантовых вычислений, как запутанность квантовых состояний. Для реализации алгоритма использован адаптивный оператор квантового гейта и предложена технология восстановления квантовой хромосомы для решения комбинаторных задач с ограничениями. Исследовано влияние размера квантового регистра на эффективность работы алгоритма. Преимущество предложенного подхода по сравнению с традиционной реализацией QGA проиллюстрировано на примере 0–1 задачи упаковки рюкзака большой размерности и разного уровня корреляции входных данных. Для підвищення ефективності роботи квантового генетичного алгоритму (QGA) запропоновано в поданні квантової хромосоми перейти до квантових регістрів вищих порядків. Таке подання дозволяє використати такий потужний механізм квантових обчислень, як заплутаність квантових станів. Для реалізації алгоритму використано адаптивний оператор квантового гейту та запропоновано технологію відновлення квантової хромосоми для розв’язання комбінаторних задач з обмеженнями. Досліджено вплив розміру квантового регістра на ефективність роботи алгоритму. Переваги запропонованого підходу порівняно із традиційною реалізацією QGA проілюстровано на прикладі 0–1 задачі пакування рюкзака великої розмірності та різного рівня кореляції вхідних даних. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018-10-16 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/132427 10.20535/SRIT.2308-8893.2018.3.05 System research and information technologies; No. 3 (2018); 52-67 Системные исследования и информационные технологии; № 3 (2018); 52-67 Системні дослідження та інформаційні технології; № 3 (2018); 52-67 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/132427/149280 Copyright (c) 2021 System research and information technologies |
| spellingShingle | квантовий генетичний алгоритм 0-1 задача пакування рюкзака оператор квантового гейту квантовий регістр заплутаність квантових станів Tkachuk, Valerii M. Tkachuk, Orysya M. Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака |
| title | Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака |
| title_alt | Higher-order quantum genetic algorithm for 0-1 knapsack problem Квантовый генетический алгоритм высших порядков для 0–1 задачи упаковки рюкзака |
| title_full | Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака |
| title_fullStr | Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака |
| title_full_unstemmed | Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака |
| title_short | Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака |
| title_sort | квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака |
| topic | квантовий генетичний алгоритм 0-1 задача пакування рюкзака оператор квантового гейту квантовий регістр заплутаність квантових станів |
| topic_facet | quantum genetic algorithm 0-1 knapsack problem quantum gate operator quantum register entanglement of quantum states квантовый генетический алгоритм 0-1 задача о ранце оператор квантового гейта квантовый регистр запутанность квантовых состояний квантовий генетичний алгоритм 0-1 задача пакування рюкзака оператор квантового гейту квантовий регістр заплутаність квантових станів |
| url | https://journal.iasa.kpi.ua/article/view/132427 |
| work_keys_str_mv | AT tkachukvaleriim higherorderquantumgeneticalgorithmfor01knapsackproblem AT tkachukorysyam higherorderquantumgeneticalgorithmfor01knapsackproblem AT tkachukvaleriim kvantovyjgenetičeskijalgoritmvysšihporâdkovdlâ01zadačiupakovkirûkzaka AT tkachukorysyam kvantovyjgenetičeskijalgoritmvysšihporâdkovdlâ01zadačiupakovkirûkzaka AT tkachukvaleriim kvantovijgenetičnijalgoritmviŝihporâdkívdlâ01zadačípakuvannârûkzaka AT tkachukorysyam kvantovijgenetičnijalgoritmviŝihporâdkívdlâ01zadačípakuvannârûkzaka |