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

Valerii M. Tkachuk

Анотація


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

Ключові слова


квантові обчислення; квантовий біт; квантовий генетичний алгоритм; оператор квантового гейту; 0-1 задача пакування рюкзака

Повний текст:

PDF

Посилання


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.

Whitley Darrell. A genetic algorithm tutorial / Darrell Whitley. — Statistics and computing. — 1994. —Vol. 4, N 2. — P. 65–85.

Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs / Z. Michalewicz // New York: Springer, 3rd (extended) edition, 1996.

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.

Han K.-H. Genetic quantum algorithm and its application to combinatorial optimization problem / K.-H. Han, J.-H. Kim // Proceedings of IEEE Congress on Evolutionary Computation, USA. — 2000. — Vol. 2. — P. 1354–1360.

Nowotniak R. Higher-Order Quantum-Inspired Genetic Algorithms / R. Nowotniak, J. Kucharski // Federated Conference on Annals of Computer Science and Information Systems. — 2014. — P. 465–470.

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.

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.

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.

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.

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.

Narayanan A. Quantum-inspired genetic algorithms / A. Narayanan, M. Moore // IEEE Evolutionary Computation. — 1996. — Vol.1. — P. 61–66.

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.

Kuk-Hyun Han. Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization / Kuk-Hyun Han, Jong-Hwan Kim // IEEE Transactions on Evolutionary Computation. — 2002. — Vol. 6, N 6. — P. 580–593.


Пристатейна бібліографія ГОСТ


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.

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 optimization problem / K.-H. Han, J.-H. Kim // Proceedings of IEEE Congress on Evolutionary 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 Information 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 Combinatorial Optimization / Kuk-Hyun Han, Jong-Hwan Kim // IEEE Transactions on Evolutionary Computation. — 2002. — Vol. 6, N 6. — P. 580–593.





DOI: https://doi.org/10.20535/SRIT.2308-8893.2018.2.08

Посилання

  • Поки немає зовнішніх посилань.