Модификация квантово-инспирированного генетического алгоритма численной оптимизации с использованием кудита в условиях имитации квантовой декогеренции

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Генетический алгоритм численной оптимизации (GA) метаэвристического класса представляет собой метод поиска оптимальных решений, основанный на биологических принципах естественного отбора и изменчивости. GA характеризуется высокой скоростью работы, устойчивостью к шуму в данных, низкой вероятностью попадания в локальный экстремум мультимодальной целевой функции, а также одновременным применением вероятностных и детерминированных правил для порождения точек поискового пространства. Альтернативой классического GA является квантово-инспирированный генетический алгоритм численной оптимизации (QIGA), обладающий преимуществами, которые недостижимы для GA, за счет использования концепций и принципов квантовых вычислений. В статье предлагается новый подход к реализации квантово-инспирированного генетического алгоритма численной оптимизации для поиска глобального максимума целевой функции, основывающийся на моделировании функционирования GA имитацией выполнения квантовых вычислений на базе кудита в условиях существования квантовой декогеренции эпохи зашумленных квантовых алгоритмов среднего масштаба. С этой целью для осуществления квантовых операций вращения состояний многоуровневых квантовых систем в работе представлена матрица плотности на основе операторов Гейзенберга–Вейля как аналог сферы Блоха для кудитов. Имитация квантовой декогеренции интерпретируется с точки зрения влияния стороннего шума, исходящего от окружающей среды, на кудит и представляется как использование в квантовых вентилях нормальной случайной величины с нулевым математическим ожиданием и единичной дисперсией. Вместе с тем в работе представлены подробные псевдокоды функционирования как самого модифицированного квантово-инспирированного генетического алгоритма численной оптимизации, так и его отдельных операций. Тестирование осуществляется путем проведения вычислительных экспериментов с выполнением модифицированного алгоритма на двумерных и многомерных функциях тестовых задач оптимизации, а также при решении прикладной оптимизационной задачи планирования гибридного поточного производства в обрабатывающей промышленности на основе финансовых затрат и решении задачи повышения точности прогнозирования на основе компактных машин экстремального обучения. Результаты экспериментов демонстрируют превосходство нового алгоритма над QIGA и классическими оптимизационными алгоритмами в точности решения, скорости сходимости с целевым значением глобального максимума и временем выполнения алгоритма.

Об авторах

Владимир Владимирович Масленников

МИРЭА – Российский технологический университет

Автор, ответственный за переписку.
Email: vldmsn@yahoo.com
ORCID iD: 0000-0003-3201-2228

старший преподаватель, кафедра корпоративных информационных систем, Институт информационных технологий

Россия, г. Москва

Лилия Анатольевна Демидова

МИРЭА – Российский технологический университет

Email: liliya.demidova@rambler.ru
ORCID iD: 0000-0003-4516-3746

доктор технических наук, профессор, профессор, кафедра корпоративных информационных систем, Институт информационных технологий

Россия, г. Москва

Список литературы

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. Chen J., Zhang F., Chen M. et al. Classical simulation of intermediate-size quantum circuits. 2018. doi: 10.48550/arXiv.1805.01450.
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. Kaul D., Raju H., Tripathy B.K. Quantum-computing-inspired algorithms in machine learning. 2018. doi: 10.4018/978-1-5225-5219-2.ch001
  20. 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
  21. 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
  22. 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
  23. Nowotniak R., Kucharski J. Building Blocks propagation in quantum-inspired genetic algorithm // Scientific Bulletin of Academy of Science and Technology, Automatics. 2010. No. 14.
  24. Preskill J. Quantum computing in the NISQ era and beyond // Quantum. 2018. No. 2. doi: 10.22331/q-2018-08-06-79
  25. 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.
  26. Schlosshauer M. Decoherence, the measurement problem, and interpretations of quantum mechanics // Reviews of Modern Physics. 2003. No. 76. Pp. 1267–1305.
  27. Schlosshauer M. Quantum decoherence // Physics Reports. 2019. Vol. 831. Pp. 1–57. doi: 10.1016/j.physrep.2019.10.001. EDN PTXNOQ
  28. Sharma G., Ghosh S. Four-dimensional Bloch sphere representation of qutrits using Heisenberg–Weyl operators. 2021. URL: https://arxiv.org/abs/2101.06408
  29. 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
  30. 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.
  31. 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
  32. 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
  33. 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
  34. Żurek W. Decoherence, einselection, and the quantum origins of the classical // Reviews of Modern Physics. 2001. No. 75. doi: 10.1103/RevModPhys.75.715
  35. Демидова Л.А., Горчаков А.В. Применение биоинспирированных алгоритмов глобальной оптимизации для повышения точности прогнозов компактных машин экстремального обучения // Russian Technological Journal. 2022. Т. 10. № 2. С. 59–74. doi: 10.32362/2500-316X-2022-10-2-59-74. EDN: WCFZVD.
  36. Корж О.В., Чернявский А.Ю., Корж А.А. Моделирование квантового преобразования Фурье с шумами на суперкомпьютере Ломоносов // Научный сервис в сети Интернет: все грани параллелизма: труды Междунар. суперкомпьютерной конф., Новороссийск, 23–28 сентября 2013 г. Новороссийск: Изд-во Моск. гос. ун-та, 2013. С. 188–193. EDN: SXFHSD.
  37. Масленников В.В. Квантово-инспирированные оптимизационные алгоритмы в решении задач оперативного управления // Новые информационные технологии в научных исследованиях: матер. XХVIII Всерос. науч.-техн. конф. студентов, молодых ученых и специалистов, Рязань, 22–24 ноября 2023 г. Рязань: Рязанский гос. радиотехнический ун-т им. В.Ф. Уткина, 2023. С. 42–44. EDN: TTUMEJ.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать
2. Рис. 1. Представление элементарного кубита в виде сферы Блоха

Скачать (22KB)
Метаданные
3. Рис. 2. Графики сходимости для тестовых функций размерности n = 2: a – f1; b – f2; c – f3; d – f4

Скачать (57KB)
Метаданные
4. Рис. 3. Графики сходимости для тестовых функций размерности n = 2: a – f5; b – f6; c – f7; d – f8

Скачать (51KB)
Метаданные
5. Рис. 4. Графики сходимости для тестовых функций размерности n = 15: a – f1; b – f2; c – f3; d – f4

Скачать (63KB)
Метаданные
6. Рис. 5. Графики сходимости для тестовых функций размерности n = 15: a – f5; b – f6; c – f7; d – f8

Скачать (71KB)
Метаданные


Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».