Адаптивний квантовий генетичний алгоритм для 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...

Full description

Saved in:

Bibliographic Details
Date:	2018
Main Author:	Tkachuk, Valerii M.
Format:	Article
Language:	Ukrainian
Published:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018
Subjects:	квантові обчислення квантовий біт квантовий генетичний алгоритм оператор квантового гейту 0-1 задача пакування рюкзака
Online Access:	https://journal.iasa.kpi.ua/article/view/125371
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_	1867334329547358208
author	Tkachuk, Valerii M.
author_facet	Tkachuk, Valerii M.
author_institution_txt_mv	[ { "author": "Valerii M. Tkachuk", "institution": "Кафедра інформаційних технологій факультету математики та інформатики Прикарпатського національного університету імені Василя Стефаника, Івано-Франківськ" } ]
author_sort	Tkachuk, Valerii M.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2019-01-17T13:29:35Z
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.
doi_str_mv	10.20535/SRIT.2308-8893.2018.2.08
first_indexed	2025-07-17T10:23:26Z
format	Article
fulltext	 В.М. Ткачук, 2018 Системні дослідження та інформаційні технології, 2018, № 2 77 УДК 004.023, 539.18 DOI: 10.20535/SRIT.2308-8893.2018.2.08 АДАПТИВНИЙ КВАНТОВИЙ ГЕНЕТИЧНИЙ АЛГОРИТМ ДЛЯ 0–1 ЗАДАЧІ ПАКУВАННЯ РЮКЗАКА В.М. ТКАЧУК Анотація. Розглянуто квантовий генетичний алгоритм (QGA), який порівняно з його класичною реалізацією має ряд переваг завдяки швидкодії, невеликому розміру популяції, автоматичному балансу між глобальним та локальним по- шуком розв’язку. Основу QGA становлять ідеї традиційних еволюційних алго- ритмів, покладені на технологію квантових обчислень, які оперують кванто- вими бітами, суперпозицією станів та квантовими вимірюваннями. Запропоновано новий QGA, для реалізації якого використано новий адаптив- ний оператор квантового гейту та технологію відновлення квантової хромосо- ми під час розв’язання комбінаторних задач з обмеженнями. Для забезпечення ефективності роботи алгоритму виконано метаоптимізацію основних парамет- рів, покладених в основу його роботи. Можливості запропонованого підходу ілюструють модельні дослідження з використанням широкого спектру тесто- вих 0–1 задач пакування рюкзака. Ключові слова: квантові обчислення, квантовий біт, квантовий генетичний алгоритм, оператор квантового гейту, 0–1 задача пакування рюкзака. ВСТУП Генетичний алгоритм є евристичним алгоритмом, що використовується для наближеного розв’язку задач оптимізації та пошуку [1]. В основу його робо- ти покладено принципи еволюції природних біологічних систем, зокрема відбору, схрещування та мутації [2–4]. Алгоритм працює із множиною по- тенційних розв’язків, використовуючи найкращий для його відтворення та послідовного наближення до точного значення в ході еволюції. У класичній його реалізації мінімальною одиницею інформації є біт-структура із двома станами: 0 та 1. Квантовий генетичний алгоритм (QGA) є новим еволюційним алгоритмом, що ґрунтується на поєднанні іде- ології квантових обчислень і технології класичних генетичних алгорит- мів [5, 6]. Імовірнісний механізм квантових обчислень забезпечує глобальний пошук розв’язку за швидкої локальної збіжності та невеликого розміру по- пуляції. Хоча теоретичного обґрунтування роботи алгоритму поки що не існує, він показує задовільну ефективність у багатьох областях. Так, цей клас алгоритмів був успішно застосований до широкого спектру задач, як то комбінаторна та функціональна оптимізація, проблеми оптимізації в маши- нобудуванні, оброблення зображення та багатьох інших [7–11]. Основні ідеї QGA запропонували Narayanan і Moore [12], згідно з якими мінімальною одиницею інформації в квантових обчисленнях є кубіт – кван- това система, що може перебувати в двох основних станах: 0 та 1 . Кван- В.М. Ткачук ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 78 това природа кубіта полягає в принципі суперпозиції, відповідно до якого він може перебувати у довільному стані, що є лінійною комбінацією ба- зових: 10 10 q (1) з умовою нормування 12 1 2 0  . Наслідком принципу суперпозиції є те, що простір станів кубіта незрів- нянно більший від простору станів класичного біта. Інформація, що міс- титься в амплітудах 0 та 1 , є власне квантовою частиною інформації. Фактично 2 0 та 2 1 — імовірності перебування кубіта в стані 0 та 1 ві- дповідно. Як і класичний, квантовий біт можна виміряти. Результатом вимірю- вання буде кубіт в одному з основних станів. При цьому важливо, що ре- зультат вимірювання не детермінований, як у класичному обчисленні, а ймовірнісний. Для реалізації QGA використовується матричне подання основних ста- нів кубіта:        0 1 0 ,        1 0 1 . Стан суперпозиції (1) у такому поданні можна записати у вигляді          1 0q . Упорядкований набір з N кубітів формує квантову хромосому. Вектор стану такої хромосоми являє собою розклад по N2 базових станах Niii ,...,, 21 , }1,0{,...,, 21 Niii :    N k Niiii iii N 1 2,...,, ,...,, 21 . Оскільки заплутаність квантових станів у QGA не використовується, то хромосома може бути сформована як упорядкований набір незалежних кубі- тів. Так, якщо 16N кубітів, схематично її можна подати таким чином: Уся інформація про систему кубітів визначається вектором стану  . Єдине, що можна зробити з такою системою, — це перетворити вектор по- чаткового стану  до деякого нового  за допомогою оператора кван- тового гейту. Тобто QGA — це перехід системи з початкового в кінцевий стан відповідно до алгоритму, закладеного у роботу квантового гейту. Розв’язок задачі отримується як результат квантового вимірювання вектора кінцевого стану системи  та переходу до його класичного подання. q q q q q q q q q q q q q q q q Адаптивний квантовий генетичний алгоритм для 0–1 задачі пакування рюкзака Системні дослідження та інформаційні технології, 2018, № 2 79 КВАНТОВИЙ ГЕНЕТИЧНИЙ АЛГОРИТМ ТА ЙОГО ВИКОРИСТАННЯ В ЗАДАЧАХ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ У цілому структура QGA аналогічна звичайному генетичному алгоритму, а принципова відмінність полягає лише в особливостях реалізації квантових операторів з урахуванням подання хромосоми у вигляді системи кубітів та принципу суперпозиції. Загальна схема роботи алгоритму може бути реалізована у вигляді та- кого алгоритму: Алгоритм 1. Квантовий генетичний алгоритм 1 0t 2 ініціалізація )(tQ 3 вимірювання )(tQ та перехід до )(tP 4 оцінювання пристосованості )(tP 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 — класичне (бінарне) подання популяції, отримане в результаті квантового ви- мірювання. Операцію квантового вимірювання (етапи 3 та 11) детально розглянуто, наприклад у працях [6, 8], й окремого опису не потребує. Необхідність опе- рації відновлення (етапи 5, 6 і 13, 14) та алгоритм її роботи більш детально розглянуто далі. Для розширення області пошуку та виходу з локальних мінімумів QGA у разі потреби можна доповнити традиційними операторами, притаманними чисто класичному генетичному алгоритму, як то квантової мутації, схрещу- вання чи катастрофи [13]. Зважаючи на ймовірнісний механізм процесу квантового вимірювання у використанні оператора мутації у його класичному розумінні в розгляда- ному випадку потреби немає. Операція квантового гейту до певної міри ви- конує роль операції схрещування в її класичному розумінні. Для реалізації QGA використовується матричне подання квантових хромосом. Наприклад, якщо хромосома складається з N кубітів, кількість яких визначається розмірністю комбінаторної задачі, то вона може бути ре- алізована так: В.М. Ткачук ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 80 1 0 2 0 3 0 4 0 5 0 … … … N 0 1 1 2 1 3 1 4 1 5 1 … … … N 1 Тут },{ 10 ii  визначає стан i -го кубіта iq , а N кубітів формують од- ну особину популяції. Оскільки початковий стан не містить інформації про розв’язок задачі, то найпростішим способом ініціалізації популяції є рів- ність між собою всіх амплітуд імовірностей станів [12]. Тобто на етапі 2 ро- боти алгоритму кожен кубіт буде переведений у стан 1 2 1 0 2 1 q . Для пошуку розв’язку в ході еволюції відбувається зміна амплітуд імо- вірностей станів унаслідок послідовної дії квантових операторів (етапи ро- боти 9–15). Визначальним серед них є оператор квантового гейту, робота якого реалізована на етапі 10. МЕТА ДОСЛІДЖЕННЯ Метою дослідження була побудова нових квантових операторів у реалізації QGA для забезпечення, порівняно із традиційними підходами, більшої ефек- тивності роботи алгоритму як за часом роботи, так і за ефективністю пошу- ку оптимального значення. Усю інформація про задачу та алгоритм її розв’язку закладено у кван- товому гейті, тому його робота є визначальною для побудови будь-якого QGA. Він маніпулює амплітудами ймовірностей квантових станів, забезпе- чуючи виконання умови нормування. Під час реалізації обертання квантових станів для визначення кута по- вороту традиційним є використання таблиці пошуку, що обмежує універ- сальність роботи алгоритму. Крім того, фіксоване значення кута негативно впливає на швидкість збіжності, тому QGA інколи реалізують як адаптив- ний процес зміни його величини в ході еволюції. Більш ефективним, як по- казали виконані дослідження, є закладання адаптивного характеру у сам ал- горитм роботи оператора. Роботу пропонованого оператора можна поділити на два етапи. На першому етапі збільшується амплітуда ймовірності вибраного квантового стану b : )1(][)( 2 b k b k b k  , (2) де }1,0{k . Стан b визначається k -м значенням класичного подання найкращої особини популяції, отриманої на попередній ітерації еволюції в часі. Функ- ціональна залежність (2) забезпечує також той факт, що амплітуда ймовір- ності b k не може перевищувати 1. Значення параметра  лежить у межах ]1,0[ і підбирається за результатами попередніх досліджень. На другому етапі необхідно зменшити амплітуду ймовірності іншого стану кубіта для забезпечення виконання умови нормування. Загалом алго- Адаптивний квантовий генетичний алгоритм для 0–1 задачі пакування рюкзака Системні дослідження та інформаційні технології, 2018, № 2 81 ритм роботи оператора до квантової хромосоми, що складається з N кубі- тів, можна реалізувати таким чином: Алгоритм 2. Оператор квантового гейту 1 for i in N,,1 do 2 ibestamp  -е значення гена найкращої особини по- пуляції 3 if 0bestamp 4 )1(][ 0 2 00 iii  5 2 01 ][1 ii  6 end if 7 if 1bestamp 8 )1(][ 1 2 01 iii  9 2 00 ][1 ii  10 end if 11 end for На етапі 4 (8) алгоритму відбувається адаптивний поворот векто- ра квантового стану, що відповідає найкращій особині популяції, а на етапі 5 (9) — перерахунок амплітуди іншої імовірності для забезпечення вико- нання умови нормування. Таким чином, у кожному новому поколінні забезпечується збільшення ймовірності того, що в результаті спостереження генеруються класичні осо- бини, більш схожі на найкращу. За такого алгоритму роботи також можна обійтися без таблиці пошуку, що є одним із принципових недоліків QGA. Адаптивний механізм, покладений в основу роботи квантового гейту, як показали моделювання, дозволяє для розв’язання 0–1 задачі пакування рюкзака покласти 1 . ЗАДАЧА ПАКУВАННЯ РЮКЗАКА Проблема 0–1 пакування рюкзака є NP повною задачею дискретної комбі- наторної оптимізації, яка традиційно використовується для тестування пошукових алгоритмів. Вона зводиться до знаходження для скінченної множини N речей такого бінарного вектора заповнення рюкзака },...,,,{ 321 NxxxxX  , який забезпечує максимальне значення функції    N i ii xpXf 1 )( (3) з обмеженням    N i ii Cx 1 , (4) де ip — вартість i -го предмета; i — маса i -го предмета; C — максима- льно можлива маса рюкзака. У процесі ініціалізації популяції, чи в ході її еволюції завжди є ймовір- ність отримати ряд «поганих» особин (3), які не задовольняють умову (4). В.М. Ткачук ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 82 Для врахування цього використовується або метод штрафних функцій, або метод відновлення, який і буде використано в роботі. Процедура відновлен- ня зводиться до видалення випадковим чином елементів з рюкзака доти, до- ки не буде задоволено обмеження (4). Після відновлення функція пристосованості буде такою:      N i ii xpXf 1 , де },...,,,{ 321 NxxxxX  — відновлена версія бінарного вектора X . Дослідження показали, що жадібний алгоритм відновлення, коли всі речі, що пакуються, сортуються відповідно до вагових коефіцієнтів iip  та видаляються з рюкзака відповідно до їх росту, веде до зменшення різно- манітності популяції. Наслідком цього є зменшення ефективності глобаль- ного пошуку та погіршення кінцевих результатів. Процедура відновлення в QGA принципово інша, ніж в генетичному алгоритмі, бо потребує коригування і квантової хромосоми. Вона може бу- ти розбита на два етапи і потребувати значних обчислювальних ресурсів. Відсоток відновлених особин може змінюватися від 0 до 100% і є одним з параметрів роботи оператора. Надалі для простоти реалізації вважатимемо, що відновлюються всі хромосоми, що не задовольняють умову за масою (4). На першому традиційному етапі, якщо рюкзак надто важкий, елементи видаляються з нього доти, доки не буде задоволено обмеження (4). Якщо рюкзак занадто легкий, то процедура відновлення додає елементи в рюкзак доти, доки це дозволяє обмеження маси. Схематично перший етап можна подати у вигляді такого алгоритму. Алгоритм 3. Відновлення класичної хромосоми )(tP 1 переповнення_рюкзака=false 2 if         N i ii Cx 1 then переповнення_рюкзака=true 3 while(переповнення_рюкзака=true) 4 }1{ Nrandomi  — вибір випадковим чином пред- мета з рюкзака 5 0ix — видалення предмета із рюкзака 6 if         N i ii Cx 1 then переповнення_рюкзака=false 7 end while 8 for i in {1,2, … , N } 9 if         N i iii Cx 1 OR )0( ix then continue 10 1ix 11 end for Етапи 2–7 відповідають за видалення випадковим чином елементів із рюкзака, поки не виконається обмеження (4). На етапах 8–11, якщо це мож- ливо, у рюкзак послідовно додаються додаткові елементи. Адаптивний квантовий генетичний алгоритм для 0–1 задачі пакування рюкзака Системні дослідження та інформаційні технології, 2018, № 2 83 На другому етапі необхідно відкоригувати амплітуди ймовірності кван- тової хромосоми відповідно до відновленої хромосоми X  . Процес віднов- лення реалізовано у вигляді такого алгоритму: Алгоритм 4. Відновлення квантової хромосоми )(tQ 1 for i in {1,2, … , N } 2 if )1( ix 3 0 i 4 21 1 i 5 end if 6 if )0( ix 7 20 1 i 8 1 i 9 end if 10 end for Тут ]1,0[ — параметр роботи алгоритму. Проведені дослідження показали, що він не залежить від розміру системи N , а вплив його значення на ефективність роботи QGA ілюструє рис. 1. Рівень кореляції вхідних да- них не впливає на параметр  і оптимальним в подальших моделюваннях в даній роботі припускається 971,0 . РЕЗУЛЬТАТИ ЧИСЛОВОГО ЕКСПЕРИМЕНТУ QGA реалізовано мовою програмування С++, моделювання виконано на процесорі Intel Celeron CPU G1840 2,80 GHz, 4,0 Гбіт оперативної пам’яті. Для ілюстрації ефективності роботи алгоритму розглянуто ряд задач комбі- наторної оптимізації різної розмірності та ступеня кореляції вхідних даних. Рис. 1. Вплив  на середню за 100 запусками QGA пристосованість найкращої особини для 100N слабокорельованих вхідних даних f a vr  В.М. Ткачук ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 84 Потужність популяції s у QGA є важливим параметром роботи та кри- тичним особливо за великих значень N : чим більше його значення, тим бі- льшою має бути різноманітність потенційних розв’язків, що охоплюють всю область пошуку. Надалі для реалізації QGA взято 10s , що забезпечує 5000 звернень до функції пристосованості у процесі еволюції в часі 500t . Наведені нижче параметри, де це не оговорено окремо, оцінено як ре- зультат усереднення за 1000 запусками алгоритму. Ефективність роботи оцінено за середньою пристосованістю найкращої особини популяції avrf та середньоквадратичним відхиленням sdf . Їх типову поведінку в часі показа- но на рис. 2 і 3. Рис. 2. Усереднена за 100 запусками алгоритму еволюція середньої пристосова- ності найкращої особини avrf для 100N нескорельованих вхідних даних f a vr Номер ітерації за часом Рис. 3. Усереднена за 100 запусками алгоритму еволюція середньоквадратичного відхилення найкращої особини sdf для 100N нескорельованих вхідних даних F sd Номер ітерації за часом Адаптивний квантовий генетичний алгоритм для 0–1 задачі пакування рюкзака Системні дослідження та інформаційні технології, 2018, № 2 85 Ініціалізована на початку популяція ( 0t ) включає всі розв’язки з од- наковою ймовірністю (рис. 4). Це означає, що робота QGA починається з випадкового пошуку, а окремі піки на розподілі зумовлені дискретним хара- ктером оптимізації та роботою оператора відновлення квантової хромосоми. У міру еволюції в часі характер розподілу зазнає принципових змін (рис. 5). Зростає ймовірність знаходження особини в області точного розв’язку, який в розгляданому випадку дорівнює 9147 . Велика їх кількість тут веде до ефективного локального пошуку за рахунок квантового гейту. Оператор відновлення квантової хромосоми забезпечує різноманітність популяції. Рис. 4. Розподіл особин популяції по області пошуку на початкових етапах ево- люції f(x) t=0 t=20 n Рис. 5. Розподіл особин популяції по області пошуку на кінцевих етапах еволюції n f(x) t=200 t=100 В.М. Ткачук ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 86 Так, у разі його вилучення із QGA, як показують результати дослідження, різноманітність популяції набагато менша. У результаті зростає ймовірність потрапляння в локальні оптимуми та зменшується ефективність глобального пошуку. Підсумовуючи, можна відзначити, що QGA починає свою роботу з гло- бального пошуку та автоматично переходить до локального завдяки зміні структурних характеристик розподілу особин популяції. Статистичні результати, включаючи середнє значення найкращої осо- бини популяції avrf , його середньоквадратичне відхилення sdf , найкращий та найгірший результати, середній час роботи алгоритму avrt , отримані під час комбінаторної оптимізації тестових завдань різної розмірності, зведено в тaбл. 1 і 2. Т а б л и ц я 1 . Результати оптимізації тестових задач малої розмірності Розмірність N avrf avrt , с Точне значення 4 35 0,0015 35 10 52 0,0039 52 15 481 0,0061 481 20 1024 0,0078 1024 23 9767 0,0093 9767 Т а б л и ц я 2 . Результати оптимізації тестових задач великої розмірності Нескорельовані дані N avrf sdf avrt , с Найкраще значення Найгірше значення Точне значення 100 9084,1 98,2 0,049 9147 8628 9147 200 10763,0 331,9 0,111 11227 8861 200* 11178,0 68,28 0,591 11238 10814 11238 500 14668,0 942,2 0,284 18551 12012 500* 16963,0 908,3 1,454 20127 14539 28857 Слабоскорельовані дані 100 1462,5 51,7 0,050 1514 1208 1514 200 1476,7 31,28 0,114 1600 1387 200* 1530,5 25,11 0,602 1624 1449 1634 500 3283,8 84,49 0,276 3635 3044 500* 3448,2 77,80 1,434 3805 3161 4566 Сильноскорельовані дані 100 2338,4 48,74 0,050 2397 2292 2397 200 2552,5 72,68 0,110 2697 2297 200* 2628,4 58,10 0,599 2697 2397 2697 500 5065,7 156,0 0,271 5712 4715 500* 5394,7 151,98 1,447 5914 4917 7117 * Моделювання виконано за розміру популяції 50 особин. Як випливає з наведених результатів, середній час роботи avrt залежить лише від розміру області пошуку, яка визначається розміром квантової хро- мосоми N . Адаптивний квантовий генетичний алгоритм для 0–1 задачі пакування рюкзака Системні дослідження та інформаційні технології, 2018, № 2 87 Роль оператора відновлення ілюструють дані табл. 3. Така реалізація QGA потребує підбору параметра  та показує значно гірші результати. Використання операції відновлення квантової хромосоми веде до збільшен- ня часу роботи алгоритму майже в два рази. Т а б л и ц я 3 . Результати оптимізації тестових задач великої розмірності в разі реалізації QGA без оператора відновлення квантової хромосоми ( 10s ) Розмірність N avrf sdf avrt , с Нескорельовані дані 100 8253,9 486,6 0,027 200 8758,0 701,1 0,055 500 14425,0 1472,1 0,145 Слабоскорельовані дані 100 1271,9 93,3 0,027 200 1297,9 82,9 0,054 500 3004,4 145,3 0,135 Сильноскорельовані дані 100 2065,3 112,3 0,028 200 2147,0 123,6 0,055 500 4359,1 210,2 0,135 У цілому отримані результати порівняно з даними, доступними в літе- ратурі [6, 14], показують підвищення ефективності QGA за рахунок викори- стання запропонованих квантових операторів. ВИСНОВКИ У роботі побудовано новий QGA та проілюстровано ефективність його ро- боти з використанням набору тестових даних різної розмірності та рівня ко- реляції. Запропонований підхід ілюструє хорошу можливість глобального пошуку завдяки використанню процедури відновлення квантової хромосоми та оператора квантового вимірювання. Швидка локальна збіжність забезпе- чується адаптованим алгоритмом роботи оператора квантового гейту, який для своєї реалізації не потребує використання таблиці пошуку. Експериментальні результати 0–1 задачі пакування рюкзака ілюстру- ють можливості застосування QGA до задач різної розмірності. Результати, отримані за значних розмірів досліджуваних систем ( 500N ), указують на необхідність збільшення розміру популяції та пошуку додаткових методів поліпшення роботи алгоритму, що буде предметом наступних досліджень. ЛІТЕРАТУРА 1. Holland J.H. Adaptation in Natural and Arti_cial Systems: An Introductory Analysis with Applications to Biology, Control, and Arti_cial Intelligence / J.H. Holland. — Ann Arbor, MI: University of Michigan Press, 1975. 2. Whitley Darrell. A genetic algorithm tutorial / Darrell Whitley. — Statistics and computing. — 1994. —Vol. 4, N 2. — P. 65–85. В.М. Ткачук ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 88 3. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs / Z. Michalewicz // New York: Springer, 3rd (extended) edition, 1996. 4. Jantos P. Evolutionary algorithms for global parametric fault diagnosis in analogue integrated circuits / P. Jantos, D. Grzechca, J. Rutkowski // Bull. Pol. Ac.: Tech. — 2012. — Vol. 60, N 1. — P. 133–142. 5. Han K.-H. Genetic quantum algorithm and its application to combinatorial optimiza- tion problem / K.-H. Han, J.-H. Kim // Proceedings of IEEE Congress on Evolu- tionary Computation, USA. — 2000. — Vol. 2. — P. 1354–1360. 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. Jopek Ł. Zastosowanie kwantowych algorytmów genetycznych do selekcji cech / Ł. Jopek, R. Nowotniak, M. Postolski et al. // Automatyka, Akademia Górniczo- Hutnicza im. Stanisława Staszica w Krakowie. — 2009. — Vol.13, N 3. — P. 1219–1231. 8. Talbi H. A Quantum-Inspired Evolutionary Algorithm for Multiobjective Image Segmentation / H. Talbi, M. Batouche, A. Draa // International Journal of Mathematical, Physical and Engineering Sciences. — 2007. — Vol. 1, N 2. — P. 109–114. 9. Li B.B. A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling / B.B. Li, L. Wang // IEEE Trans. Systems, Man, and Cybernetics, Part B: Cybernetics. — 2007. — Vol. 37, N 3. — P. 576–591. 10. Lau T. Quantum-inspired evolutionary algorithm approach for unit commitment / T. Lau, C. Chung, K. Wong, T. Chung, S. Ho // IEEE Trans. on Power Systems. — 2009. — Vol. 24, N 3. — P. 1503–1512. 11. Su-Hua L. Application of quantum-inspired evolutionary algorithm in reactive power optimization / L. Su-Hua, W. Yao-Wu, P. Lei, X. Xin-Yin // Relay. — 2005. —Vol. 33. — P. 30–35. 12. Narayanan A. Quantum-inspired genetic algorithms / A. Narayanan, M. Moore // IEEE Evolutionary Computation. — 1996. — Vol.1. — P. 61–66. 13. 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. — Vol. 2013. — P. 1–10. 14. Kuk-Hyun Han. Quantum-Inspired Evolutionary Algorithm for a Class of Combina- torial Optimization / Kuk-Hyun Han, Jong-Hwan Kim // IEEE Transactions on Evolutionary Computation. — 2002. — Vol. 6, N 6. — P. 580–593. Надійшла 12.04.2018
id	journaliasakpiua-article-125371
institution	System research and information technologies
keywords_txt_mv	keywords
language	Ukrainian
last_indexed	2025-07-17T10:23:26Z
publishDate	2018
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/62/9bfc12025eca03fe4ecd9bd8f4eed762.pdf
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 https://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 https://journal.iasa.kpi.ua/article/view/125371/136909 Copyright (c) 2021 System research and information technologies
spellingShingle	квантові обчислення квантовий біт квантовий генетичний алгоритм оператор квантового гейту 0-1 задача пакування рюкзака Tkachuk, Valerii M. Адаптивний квантовий генетичний алгоритм для 0–1 задачі пакування рюкзака
title	Адаптивний квантовий генетичний алгоритм для 0–1 задачі пакування рюкзака
title_alt	An adaptive quantum evolution 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 computing quantum bit quantum genetic algorithm quantum gate operator 0-1 knapsack problem квантовые вычисления квантовый бит квантовый генетический алгоритм оператор квантового гейта 0-1 задача упаковки рюкзак квантові обчислення квантовий біт квантовий генетичний алгоритм оператор квантового гейту 0-1 задача пакування рюкзака
url	https://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

Адаптивний квантовий генетичний алгоритм для 0–1 задачі пакування рюкзака

Institution

Similar Items