АДАПТИВНИЙ КВАНТОВИЙ ГЕНЕТИЧНИЙ АЛГОРИТМ ДЛЯ 0–1 ЗАДАЧІ ПАКУВАННЯ РЮКЗАКА

Abstract

Розглянуто квантовий генетичний алгоритм (QGA), який порівняно з його класичною реалізацією має ряд переваг завдяки швидкодії, невеликому розміру популяції, автоматичному балансу між глобальним та локальним по- шуком розв’язку. Основу QGA становлять ідеї традиційних еволюційних алго- ритмів, покладені на технологію квантових обчислень, які оперують кванто- вими бітами, суперпозицією станів та квантовими вимірюваннями. Запропоновано новий QGA, для реалізації якого використано новий адаптив- ний оператор квантового гейту та технологію відновлення квантової хромосо- ми під час розв’язання комбінаторних задач з обмеженнями. Для забезпечення ефективності роботи алгоритму виконано метаоптимізацію основних парамет- рів, покладених в основу його роботи. Можливості запропонованого підходу ілюструють модельні дослідження з використанням широкого спектру тесто- вих 0–1 задач пакування рюкзака.