Адаптивний квантовий генетичний алгоритм для 0–1 задачі пакування рюкзака
Quantum Genetic Algorithm (QGA) has a number of advantages in comparison with its classical version: operating speed, small population size and auto-balance between the global search and the local search. It is based on the ideas of traditional evolutionary algorithms, applied to the quantum computa...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2018
|
| Теми: | |
| Онлайн доступ: | http://journal.iasa.kpi.ua/article/view/125371 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
Репозитарії
System research and information technologies| id |
journaliasakpiua-article-125371 |
|---|---|
| record_format |
ojs |
| spelling |
journaliasakpiua-article-1253712019-01-17T13:29:35Z An adaptive quantum evolution algorithm for 0–1 knapsack problem Адаптивный квантовый генетический алгоритм для 0–1 задачи упаковки рюкзака Адаптивний квантовий генетичний алгоритм для 0–1 задачі пакування рюкзака Tkachuk, Valerii M. quantum computing quantum bit quantum genetic algorithm quantum gate operator 0-1 knapsack problem квантовые вычисления квантовый бит квантовый генетический алгоритм оператор квантового гейта 0-1 задача упаковки рюкзак квантові обчислення квантовий біт квантовий генетичний алгоритм оператор квантового гейту 0-1 задача пакування рюкзака Quantum Genetic Algorithm (QGA) has a number of advantages in comparison with its classical version: operating speed, small population size and auto-balance between the global search and the local search. It is based on the ideas of traditional evolutionary algorithms, applied to the quantum computations technology, which operate with quantum bits, superposition of states and quantum measurements. This paper proposes a QGA with a new adaptive quantum gate operator and a restoring technology for the quantum chromosome during the process of solving combinatorial problems with constraints. Meta-optimization of the primary algorithm parameters is used for providing the algorithm efficiency. The productiveness of the suggested approach is proven by the model studies, carried out using a wide range of test 0–1 knapsack problems. Рассмотрен квантовый генетический алгоритм (QGA), который по сравнению с его классической реализацией обладает рядом преимуществ благодаря быстродействию, небольшому размеру популяции, автоматическому балансу между глобальным и локальным поисками решения. В основу QGA положены идеи традиционных эволюционных алгоритмов, положенные на технологию квантовых вычислений, которые оперируют квантовыми битами, суперпозицией состояний и квантовыми измерениями. Предложен новый QGA, для реализации которого использованы новый адаптивный оператор квантового гейта и технология восстановления квантовой хромосомы при решении комбинаторных задач с ограничениями. Для обеспечения эффективной работы алгоритма выполнена метаоптимизация основных параметров, положенных в основу его работы. Возможности предложенного подхода иллюстрируют модельные исследования с использованием широкого спектра тестовых 0–1 задач упаковки рюкзака. Розглянуто квантовий генетичний алгоритм (QGA), який порівняно з його класичною реалізацією має ряд переваг завдяки швидкодії, невеликому розміру популяції, автоматичному балансу між глобальним та локальним пошуком розв’язку. Основу QGA становлять ідеї традиційних еволюційних алгоритмів, покладені на технологію квантових обчислень, які оперують квантовими бітами, суперпозицією станів та квантовими вимірюваннями. Запропоновано новий QGA, для реалізації якого використано новий адаптивний оператор квантового гейту та технологію відновлення квантової хромосоми під час розв’язання комбінаторних задач з обмеженнями. Для забезпечення ефективності роботи алгоритму виконано метаоптимізацію основних параметрів, покладених в основу його роботи. Можливості запропонованого підходу ілюструють модельні дослідження з використанням широкого спектру тестових 0–1 задач пакування рюкзака. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018-06-20 Article Article application/pdf http://journal.iasa.kpi.ua/article/view/125371 10.20535/SRIT.2308-8893.2018.2.08 System research and information technologies; No. 2 (2018); 77-88 Системные исследования и информационные технологии; № 2 (2018); 77-88 Системні дослідження та інформаційні технології; № 2 (2018); 77-88 2308-8893 1681-6048 uk http://journal.iasa.kpi.ua/article/view/125371/136909 Copyright (c) 2021 System research and information technologies |
| institution |
System research and information technologies |
| collection |
OJS |
| language |
Ukrainian |
| topic |
quantum computing quantum bit quantum genetic algorithm quantum gate operator 0-1 knapsack problem квантовые вычисления квантовый бит квантовый генетический алгоритм оператор квантового гейта 0-1 задача упаковки рюкзак квантові обчислення квантовий біт квантовий генетичний алгоритм оператор квантового гейту 0-1 задача пакування рюкзака |
| spellingShingle |
quantum computing quantum bit quantum genetic algorithm quantum gate operator 0-1 knapsack problem квантовые вычисления квантовый бит квантовый генетический алгоритм оператор квантового гейта 0-1 задача упаковки рюкзак квантові обчислення квантовий біт квантовий генетичний алгоритм оператор квантового гейту 0-1 задача пакування рюкзака Tkachuk, Valerii M. Адаптивний квантовий генетичний алгоритм для 0–1 задачі пакування рюкзака |
| topic_facet |
quantum computing quantum bit quantum genetic algorithm quantum gate operator 0-1 knapsack problem квантовые вычисления квантовый бит квантовый генетический алгоритм оператор квантового гейта 0-1 задача упаковки рюкзак квантові обчислення квантовий біт квантовий генетичний алгоритм оператор квантового гейту 0-1 задача пакування рюкзака |
| format |
Article |
| author |
Tkachuk, Valerii M. |
| author_facet |
Tkachuk, Valerii 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 |
An adaptive quantum evolution algorithm for 0–1 knapsack problem Адаптивный квантовый генетический алгоритм для 0–1 задачи упаковки рюкзака |
| description |
Quantum Genetic Algorithm (QGA) has a number of advantages in comparison with its classical version: operating speed, small population size and auto-balance between the global search and the local search. It is based on the ideas of traditional evolutionary algorithms, applied to the quantum computations technology, which operate with quantum bits, superposition of states and quantum measurements. This paper proposes a QGA with a new adaptive quantum gate operator and a restoring technology for the quantum chromosome during the process of solving combinatorial problems with constraints. Meta-optimization of the primary algorithm parameters is used for providing the algorithm efficiency. The productiveness of the suggested approach is proven by the model studies, carried out using a wide range of test 0–1 knapsack problems. |
| publisher |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| publishDate |
2018 |
| url |
http://journal.iasa.kpi.ua/article/view/125371 |
| work_keys_str_mv |
AT tkachukvaleriim anadaptivequantumevolutionalgorithmfor01knapsackproblem AT tkachukvaleriim adaptivnyjkvantovyjgenetičeskijalgoritmdlâ01zadačiupakovkirûkzaka AT tkachukvaleriim adaptivnijkvantovijgenetičnijalgoritmdlâ01zadačípakuvannârûkzaka AT tkachukvaleriim adaptivequantumevolutionalgorithmfor01knapsackproblem |
| first_indexed |
2024-04-08T15:06:04Z |
| last_indexed |
2024-04-08T15:06:04Z |
| _version_ |
1795779475929038848 |