Модификация квантово-инспирированного генетического алгоритма численной оптимизации с использованием кудита в условиях имитации квантовой декогеренции
(Стр. 58-85)
Подробнее об авторах
Масленников Владимир Владимирович
старший преподаватель, кафедра корпоративных информационных систем, Институт информационных технологий
МИРЭА – Российский технологический университет
г. Москва, Российская Федерация Демидова Лилия Анатольевна доктор технических наук, профессор; профессор, кафедра корпоративных информационных систем, Институт информационных технологий; МИРЭА – Российский технологический университет; г. Москва, Российская Федерация
МИРЭА – Российский технологический университет
г. Москва, Российская Федерация Демидова Лилия Анатольевна доктор технических наук, профессор; профессор, кафедра корпоративных информационных систем, Институт информационных технологий; МИРЭА – Российский технологический университет; г. Москва, Российская Федерация
Нажимая на кнопку купить вы соглашаетесь с условиями договора оферты
Аннотация:
Генетический алгоритм численной оптимизации (GA) метаэвристического класса представляет собой метод поиска оптимальных решений, основанный на биологических принципах естественного отбора и изменчивости. GA характеризуется высокой скоростью работы, устойчивостью к шуму в данных, низкой вероятностью попадания в локальный экстремум мультимодальной целевой функции, а также одновременным применением вероятностных и детерминированных правил для порождения точек поискового пространства. Альтернативой классического GA является квантово-инспирированный генетический алгоритм численной оптимизации (QIGA), обладающий преимуществами, которые недостижимы для GA, за счет использования концепций и принципов квантовых вычислений. В статье предлагается новый подход к реализации квантово-инспирированного генетического алгоритма численной оптимизации для поиска глобального максимума целевой функции, основывающийся на моделировании функционирования GA имитацией выполнения квантовых вычислений на базе кудита в условиях существования квантовой декогеренции эпохи зашумленных квантовых алгоритмов среднего масштаба. С этой целью для осуществления квантовых операций вращения состояний многоуровневых квантовых систем в работе представлена матрица плотности на основе операторов Гейзенберга–Вейля как аналог сферы Блоха для кудитов. Имитация квантовой декогеренции интерпретируется с точки зрения влияния стороннего шума, исходящего от окружающей среды, на кудит и представляется как использование в квантовых вентилях нормальной случайной величины с нулевым математическим ожиданием и единичной дисперсией. Вместе с тем в работе представлены подробные псевдокоды функционирования как самого модифицированного квантово-инспирированного генетического алгоритма численной оптимизации, так и его отдельных операций. Тестирование осуществляется путем проведения вычислительных экспериментов с выполнением модифицированного алгоритма на двумерных и многомерных функциях тестовых задач оптимизации, а также при решении прикладной оптимизационной задачи планирования гибридного поточного производства в обрабатывающей промышленности на основе финансовых затрат и решении задачи повышения точности прогнозирования на основе компактных машин экстремального обучения. Результаты экспериментов демонстрируют превосходство нового алгоритма над QIGA и классическими оптимизационными алгоритмами в точности решения, скорости сходимости с целевым значением глобального максимума и временем выполнения алгоритма.
Образец цитирования:
ОБРАЗЕЦ ЦИТИРОВАНИЯ: Масленников В.В., Демидова Л.А. Модификация квантово-инспирированного генетического алгоритма численной оптимизации с использованием кудита в условиях имитации квантовой декогеренции // Computational Nanotechnology. 2024. Т. 11. № 2. С. 58-85. DOI: 10.33693/2313-223X-2024-11-2-58-85. EDN: MRWGYA
Список литературы:
Arute F., Arya K., Babbush R. et al. Quantum supremacy using a programmable superconducting processor // Nature. 2019. No. 574. Pp. 505–510. DOI: 10.1038/s41586-019-1666-5
Arrazola J., Delgado A., Bardhan B., Lloyd S. Quantum-inspired algorithms in practice // Quantum. 2020. No. 4. P. 307. DOI: 10.22331/q-2020-08-13-307
Abs da Cruz A.V., Vellasco M.M.B.R., Pacheco M.A.C. Quantum-inspired evolutionary algorithm for numerical optimization // IEEE International Conference on Evolutionary Computation. 2006. Pp. 2630–2637. DOI: 10.1109/CEC.2006.1688637
Asadian A., Erker P., Huber M., Klöckl C. Heisenberg–Weyl observables: Bloch vectors in phase space // Physical Review A. 2016. No. 94. DOI: 10.1103/PhysRevA.94.010301
Aksenov M., Zalivako I., Semerikov I. et al. Realizing quantum gates with optically addressable Yb + 171 ion qudits // Physical Review A. 2023. No. 107. DOI: 10.1103/PhysRevA.107.052612
Ab Rashid M.F.F., Mu’tasim M.A.N. Modeling and optimization of cost-based hybrid flow shop scheduling problem using metaheuristics // International Journal of Global Optimization and Its Application. 2023. No. 2. Pp. 244–254. DOI: 10.56225/ijgoia.v2i4.265
Beiranvand V., Hare W., Lucet Y. Best practices for comparing optimization algorithms // Optimization and Engineering. 2017. No. 18. DOI: 10.1007/s11081-017-9366-1
Chen J., Zhang F., Chen M. et al. Classical simulation of intermediate-size quantum circuits. 2018. DOI: 10.48550/arXiv.1805.01450.
Chabaud U., Ferrini G., Grosshans F., Markham D. Classical simulation of Gaussian quantum circuits with non-Gaussian input states // Physical Review Research. 2021. No. 3. DOI: 10.1103/PhysRevResearch.3.033018
Carlier J., Néron E. An exact method for solving the multi-processor flow-shop // RAIRO – Operations Research. 2000. No. 34. Pp. 1–25. DOI: 10.1051/ro:2000103
Demidova L., Gorchakov A. A study of chaotic maps producing symmetric distributions in the fish school search optimization algorithm with exponential step decay // Symmetry. 2020. No. 12. P. 784. DOI: 10.3390/sym12050784
Demidova L., Nikulchev E., Sokolova Y. The SVM classifier based on the modified particle swarm optimization // International Journal of Advanced Computer Science and Applications. 2016. No. 7. Pp. 16–24. DOI: 10.14569/IJACSA.2016.070203
Fay M., Proschan M. Wilcoxon–Mann–Whitney or t-test? On assumptions for hypothesis test and multiple interpretations of decision rules // Statistics Surveys. 2010. No. 4. Pp. 1–39. DOI: 10.1214/09-SS051
Huang Q., Mendl C. Classical simulation of quantum circuits using a multiqubit Bloch vector representation of density matrices // Physical Review A. 2022. No. 105. DOI: 10.1103/PhysRevA.105.022409
Hao T., Huang X., Jia C., Peng C. A quantum-inspired tensor network algorithm for constrained combinatorial optimization problems // Frontiers in Physics. 2022. No. 10. P. 906590. DOI: 10.3389/fphy.2022.906590
Han K., Kim J. Genetic quantum algorithm and its application to combinatorial optimization problem // Proceedings of the IEEE Conference on Evolutionary Computation, ICEC. 2000. Vol. 2. Pp. 1354–1360. DOI: 10.1109/CEC.2000.870809
Hakemi S., Houshmand M., KheirKhah E., Hosseini S. A review of recent advances in quantum-inspired metaheuristics // Evolutionary Intelligence. 2022. No. 1-16. DOI: 10.1007/s12065-022-00783-2
Harrison D., Rubinfeld D. Hedonic housing prices and the demand for clean air // Journal of Environmental Economics and Management. 1978. No. 5. Pp. 81–102. DOI: 10.1016/0095-0696(78)90006-2
Kaul D., Raju H., Tripathy B.K. Quantum-computing-inspired algorithms in machine learning. 2018. DOI: 10.4018/978-1-5225-5219-2.ch001
Krysenko D., Prudnikov O. Laser cooling of 171Yb+ ion in polychromatic light field // Journal of Experimental and Theoretical Physics. 2023. No. 137. Pp. 239–245. DOI: 10.1134/S1063776123080149
Kibler D., Aha D.W., Albert M.K. Instance-based prediction of real-valued attributes // Computational Intelligence. 1989. No. 5 (2). Pp. 51–57. DOI: 10.1111/j.1467-8640.1989.tb00315.x
Moretti V. Mathematical foundations of quantum mechanics: An advanced short course // International Journal of Geometric Methods in Modern Physics. 2015. No. 13. DOI: 10.1142/S0219887816300117
Nowotniak R., Kucharski J. Building Blocks propagation in quantum-inspired genetic algorithm // Scientific Bulletin of Academy of Science and Technology, Automatics. 2010. No. 14.
Preskill J. Quantum computing in the NISQ era and beyond // Quantum. 2018. No. 2. DOI: 10.22331/q-2018-08-06-79
Sabbar B.M., Rasool H.A. Quantum inspired genetic algorithm model based automatic modulation classification // Webology. 2021. Vol. 18. Special Issue. Pp. 1070–1085. DOI: 10.14704/WEB/V18SI04/WEB18182. EDN: BNCEZA.
Schlosshauer M. Decoherence, the measurement problem, and interpretations of quantum mechanics // Reviews of Modern Physics. 2003. No. 76. Pp. 1267–1305.
Schlosshauer M. Quantum decoherence // Physics Reports. 2019. Vol. 831. Pp. 1–57. DOI: 10.1016/j.physrep.2019.10.001. EDN PTXNOQ
Sharma G., Ghosh S. Four-dimensional Bloch sphere representation of qutrits using Heisenberg–Weyl operators. 2021. URL: https://arxiv.org/abs/2101.06408
Sofge D. Prospective algorithms for quantum evolutionary computation: Proceedings of the Second Quantum Interaction Symposium (QI-2008). College Publications, UK, 2008. URL: https://arxiv.org/pdf/0804.1133
Song S.J., Wang Y., Lin X., Huang Q. Study on GA-based training algorithm for extreme learning machine: 7th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC). Hangzhou, China, 2015. Pp. 132–135. DOI: 10.1109/IHMSC.2015.156.
Thieu N.V., Mirjalili S. MEALPY: An open-source library for latest meta-heuristic algorithms in Python // Journal of Systems Architecture. 2023. No. 139. DOI: 10.1016/j.sysarc.2023.102871
Wang Y., Hu Z., Sanders B., Kais S. Qudits and High-Dimensional Quantum Computing // Frontiers in Physics. 2020. No. 8. DOI: 10.3389/fphy.2020.589504
Zhang G. Quantum-inspired evolutionary algorithms: A survey and empirical study // J. Heuristics. 2011. No. 17. Pp. 303–351. DOI: 10.1007/s10732-010-9136-0
Żurek W. Decoherence, einselection, and the quantum origins of the classical // Reviews of Modern Physics. 2001. No. 75. DOI: 10.1103/RevModPhys.75.715
Демидова Л.А., Горчаков А.В. Применение биоинспирированных алгоритмов глобальной оптимизации для повышения точности прогнозов компактных машин экстремального обучения // Russian Technological Journal. 2022. Т. 10. № 2. С. 59–74. DOI: 10.32362/2500-316X-2022-10-2-59-74. EDN: WCFZVD.
Корж О.В., Чернявский А.Ю., Корж А.А. Моделирование квантового преобразования Фурье с шумами на суперкомпьютере Ломоносов // Научный сервис в сети Интернет: все грани параллелизма: труды Междунар. суперкомпьютерной конф., Новороссийск, 23–28 сентября 2013 г. Новороссийск: Изд-во Моск. гос. ун-та, 2013. С. 188–193. EDN: SXFHSD.
Масленников В.В. Квантово-инспирированные оптимизационные алгоритмы в решении задач оперативного управления // Новые информационные технологии в научных исследованиях: матер. XХVIII Всерос. науч.-техн. конф. студентов, молодых ученых и специалистов, Рязань, 22–24 ноября 2023 г. Рязань: Рязанский гос. радиотехнический ун-т им. В.Ф. Уткина, 2023. С. 42–44. EDN: TTUMEJ.
Arrazola J., Delgado A., Bardhan B., Lloyd S. Quantum-inspired algorithms in practice // Quantum. 2020. No. 4. P. 307. DOI: 10.22331/q-2020-08-13-307
Abs da Cruz A.V., Vellasco M.M.B.R., Pacheco M.A.C. Quantum-inspired evolutionary algorithm for numerical optimization // IEEE International Conference on Evolutionary Computation. 2006. Pp. 2630–2637. DOI: 10.1109/CEC.2006.1688637
Asadian A., Erker P., Huber M., Klöckl C. Heisenberg–Weyl observables: Bloch vectors in phase space // Physical Review A. 2016. No. 94. DOI: 10.1103/PhysRevA.94.010301
Aksenov M., Zalivako I., Semerikov I. et al. Realizing quantum gates with optically addressable Yb + 171 ion qudits // Physical Review A. 2023. No. 107. DOI: 10.1103/PhysRevA.107.052612
Ab Rashid M.F.F., Mu’tasim M.A.N. Modeling and optimization of cost-based hybrid flow shop scheduling problem using metaheuristics // International Journal of Global Optimization and Its Application. 2023. No. 2. Pp. 244–254. DOI: 10.56225/ijgoia.v2i4.265
Beiranvand V., Hare W., Lucet Y. Best practices for comparing optimization algorithms // Optimization and Engineering. 2017. No. 18. DOI: 10.1007/s11081-017-9366-1
Chen J., Zhang F., Chen M. et al. Classical simulation of intermediate-size quantum circuits. 2018. DOI: 10.48550/arXiv.1805.01450.
Chabaud U., Ferrini G., Grosshans F., Markham D. Classical simulation of Gaussian quantum circuits with non-Gaussian input states // Physical Review Research. 2021. No. 3. DOI: 10.1103/PhysRevResearch.3.033018
Carlier J., Néron E. An exact method for solving the multi-processor flow-shop // RAIRO – Operations Research. 2000. No. 34. Pp. 1–25. DOI: 10.1051/ro:2000103
Demidova L., Gorchakov A. A study of chaotic maps producing symmetric distributions in the fish school search optimization algorithm with exponential step decay // Symmetry. 2020. No. 12. P. 784. DOI: 10.3390/sym12050784
Demidova L., Nikulchev E., Sokolova Y. The SVM classifier based on the modified particle swarm optimization // International Journal of Advanced Computer Science and Applications. 2016. No. 7. Pp. 16–24. DOI: 10.14569/IJACSA.2016.070203
Fay M., Proschan M. Wilcoxon–Mann–Whitney or t-test? On assumptions for hypothesis test and multiple interpretations of decision rules // Statistics Surveys. 2010. No. 4. Pp. 1–39. DOI: 10.1214/09-SS051
Huang Q., Mendl C. Classical simulation of quantum circuits using a multiqubit Bloch vector representation of density matrices // Physical Review A. 2022. No. 105. DOI: 10.1103/PhysRevA.105.022409
Hao T., Huang X., Jia C., Peng C. A quantum-inspired tensor network algorithm for constrained combinatorial optimization problems // Frontiers in Physics. 2022. No. 10. P. 906590. DOI: 10.3389/fphy.2022.906590
Han K., Kim J. Genetic quantum algorithm and its application to combinatorial optimization problem // Proceedings of the IEEE Conference on Evolutionary Computation, ICEC. 2000. Vol. 2. Pp. 1354–1360. DOI: 10.1109/CEC.2000.870809
Hakemi S., Houshmand M., KheirKhah E., Hosseini S. A review of recent advances in quantum-inspired metaheuristics // Evolutionary Intelligence. 2022. No. 1-16. DOI: 10.1007/s12065-022-00783-2
Harrison D., Rubinfeld D. Hedonic housing prices and the demand for clean air // Journal of Environmental Economics and Management. 1978. No. 5. Pp. 81–102. DOI: 10.1016/0095-0696(78)90006-2
Kaul D., Raju H., Tripathy B.K. Quantum-computing-inspired algorithms in machine learning. 2018. DOI: 10.4018/978-1-5225-5219-2.ch001
Krysenko D., Prudnikov O. Laser cooling of 171Yb+ ion in polychromatic light field // Journal of Experimental and Theoretical Physics. 2023. No. 137. Pp. 239–245. DOI: 10.1134/S1063776123080149
Kibler D., Aha D.W., Albert M.K. Instance-based prediction of real-valued attributes // Computational Intelligence. 1989. No. 5 (2). Pp. 51–57. DOI: 10.1111/j.1467-8640.1989.tb00315.x
Moretti V. Mathematical foundations of quantum mechanics: An advanced short course // International Journal of Geometric Methods in Modern Physics. 2015. No. 13. DOI: 10.1142/S0219887816300117
Nowotniak R., Kucharski J. Building Blocks propagation in quantum-inspired genetic algorithm // Scientific Bulletin of Academy of Science and Technology, Automatics. 2010. No. 14.
Preskill J. Quantum computing in the NISQ era and beyond // Quantum. 2018. No. 2. DOI: 10.22331/q-2018-08-06-79
Sabbar B.M., Rasool H.A. Quantum inspired genetic algorithm model based automatic modulation classification // Webology. 2021. Vol. 18. Special Issue. Pp. 1070–1085. DOI: 10.14704/WEB/V18SI04/WEB18182. EDN: BNCEZA.
Schlosshauer M. Decoherence, the measurement problem, and interpretations of quantum mechanics // Reviews of Modern Physics. 2003. No. 76. Pp. 1267–1305.
Schlosshauer M. Quantum decoherence // Physics Reports. 2019. Vol. 831. Pp. 1–57. DOI: 10.1016/j.physrep.2019.10.001. EDN PTXNOQ
Sharma G., Ghosh S. Four-dimensional Bloch sphere representation of qutrits using Heisenberg–Weyl operators. 2021. URL: https://arxiv.org/abs/2101.06408
Sofge D. Prospective algorithms for quantum evolutionary computation: Proceedings of the Second Quantum Interaction Symposium (QI-2008). College Publications, UK, 2008. URL: https://arxiv.org/pdf/0804.1133
Song S.J., Wang Y., Lin X., Huang Q. Study on GA-based training algorithm for extreme learning machine: 7th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC). Hangzhou, China, 2015. Pp. 132–135. DOI: 10.1109/IHMSC.2015.156.
Thieu N.V., Mirjalili S. MEALPY: An open-source library for latest meta-heuristic algorithms in Python // Journal of Systems Architecture. 2023. No. 139. DOI: 10.1016/j.sysarc.2023.102871
Wang Y., Hu Z., Sanders B., Kais S. Qudits and High-Dimensional Quantum Computing // Frontiers in Physics. 2020. No. 8. DOI: 10.3389/fphy.2020.589504
Zhang G. Quantum-inspired evolutionary algorithms: A survey and empirical study // J. Heuristics. 2011. No. 17. Pp. 303–351. DOI: 10.1007/s10732-010-9136-0
Żurek W. Decoherence, einselection, and the quantum origins of the classical // Reviews of Modern Physics. 2001. No. 75. DOI: 10.1103/RevModPhys.75.715
Демидова Л.А., Горчаков А.В. Применение биоинспирированных алгоритмов глобальной оптимизации для повышения точности прогнозов компактных машин экстремального обучения // Russian Technological Journal. 2022. Т. 10. № 2. С. 59–74. DOI: 10.32362/2500-316X-2022-10-2-59-74. EDN: WCFZVD.
Корж О.В., Чернявский А.Ю., Корж А.А. Моделирование квантового преобразования Фурье с шумами на суперкомпьютере Ломоносов // Научный сервис в сети Интернет: все грани параллелизма: труды Междунар. суперкомпьютерной конф., Новороссийск, 23–28 сентября 2013 г. Новороссийск: Изд-во Моск. гос. ун-та, 2013. С. 188–193. EDN: SXFHSD.
Масленников В.В. Квантово-инспирированные оптимизационные алгоритмы в решении задач оперативного управления // Новые информационные технологии в научных исследованиях: матер. XХVIII Всерос. науч.-техн. конф. студентов, молодых ученых и специалистов, Рязань, 22–24 ноября 2023 г. Рязань: Рязанский гос. радиотехнический ун-т им. В.Ф. Уткина, 2023. С. 42–44. EDN: TTUMEJ.
Ключевые слова:
квантово-инспирированный алгоритм, генетический алгоритм, численная оптимизация, кудит, сфера Блоха, матрица плотности, квантовая суперпозиция состояний, квантовая декогеренция.
Статьи по теме
Автоматизация и управление технологическими процессами и производствами (специальность 2.3.3) Страницы: 16-25 DOI: 10.33693/2313-223X-2023-10-2-16-25 Выпуск №23034
Генетическое программирование и объектное моделирование манипуляционных роботов
манипуляционные роботы
обратная задача кинематики
объектное моделирование
генетический алгоритм
генетическое программирование
Подробнее
Квантовые структуры и квантовое моделирование Страницы: 13-18 DOI: 10.33693/2313-223X-2021-8-3-13-18 Выпуск №19706
О физическом представлении квантовых систем
связанные состояния
кубит
кутрит
кудит
tri-state+
Подробнее
Квантовые структуры и квантовое моделирование Страницы: 29-35 DOI: 10.33693/2313-223X-2021-8-3-29-35 Выпуск №19706
Коммуникационная симметрия Tri-State+ с использованием алгебраического подхода
квантовые межсоединения
межсоединения
связь
бит
кубит
Подробнее
Информатика и информационные процессы Страницы: 93-101 DOI: 10.33693/2313-223X-2024-11-2-93-101 Выпуск №119881
Использование генетического алгоритма в задаче кластеризации для взвешенного ориентированного графа
генетический алгоритм
кластеризация
оптимизация
пользователи
интернет
Подробнее
