Квантовий генетичний алгоритм вищих порядків для 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...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2018
|
| Теми: | |
| Онлайн доступ: | http://journal.iasa.kpi.ua/article/view/132427 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
Репозитарії
System research and information technologies| id |
journaliasakpiua-article-132427 |
|---|---|
| record_format |
ojs |
| 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 http://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 http://journal.iasa.kpi.ua/article/view/132427/149280 Copyright (c) 2021 System research and information technologies |
| institution |
System research and information technologies |
| collection |
OJS |
| language |
Ukrainian |
| topic |
quantum genetic algorithm 0-1 knapsack problem quantum gate operator quantum register entanglement of quantum states квантовый генетический алгоритм 0-1 задача о ранце оператор квантового гейта квантовый регистр запутанность квантовых состояний квантовий генетичний алгоритм 0-1 задача пакування рюкзака оператор квантового гейту квантовий регістр заплутаність квантових станів |
| spellingShingle |
quantum genetic algorithm 0-1 knapsack problem quantum gate operator quantum register entanglement of quantum states квантовый генетический алгоритм 0-1 задача о ранце оператор квантового гейта квантовый регистр запутанность квантовых состояний квантовий генетичний алгоритм 0-1 задача пакування рюкзака оператор квантового гейту квантовий регістр заплутаність квантових станів Tkachuk, Valerii M. Tkachuk, Orysya M. Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака |
| topic_facet |
quantum genetic algorithm 0-1 knapsack problem quantum gate operator quantum register entanglement of quantum states квантовый генетический алгоритм 0-1 задача о ранце оператор квантового гейта квантовый регистр запутанность квантовых состояний квантовий генетичний алгоритм 0-1 задача пакування рюкзака оператор квантового гейту квантовий регістр заплутаність квантових станів |
| format |
Article |
| author |
Tkachuk, Valerii M. Tkachuk, Orysya M. |
| author_facet |
Tkachuk, Valerii M. Tkachuk, Orysya M. |
| author_sort |
Tkachuk, Valerii M. |
| title |
Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака |
| title_short |
Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака |
| title_full |
Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака |
| title_fullStr |
Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака |
| title_full_unstemmed |
Квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака |
| title_sort |
квантовий генетичний алгоритм вищих порядків для 0–1 задачі пакування рюкзака |
| title_alt |
Higher-order quantum genetic algorithm for 0-1 knapsack problem Квантовый генетический алгоритм высших порядков для 0–1 задачи упаковки рюкзака |
| 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. |
| publisher |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| publishDate |
2018 |
| url |
http://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 |
| first_indexed |
2024-04-08T15:06:17Z |
| last_indexed |
2024-04-08T15:06:17Z |
| _version_ |
1795779490217984000 |