ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

4
Publication date:
09 September 2024

The quantum genetic algorithm in the problems of intelligent control modeling and supercomputing

Date of submission article: 02.12.2018
UDC: 512.6, 517.9, 519.6
The article was published in issue no. № 2, 2019 [ pp. 181-189 ]
Abstract:This paper considers the use of the quantum genetic algorithm for automatic selection of the optimum type and kind of correlation in the quantum structure of fuzzy inference. When solving intelligent and cognitive control tasks based on quantum soft computing and the principles of quantum deep machine learning, it is important to choose the type and kind of quantum correlation. It is an additional physical and informational computing resource in the formation of the laws of the time variation of the gains of traditional regulators located at the lower (performing) level of the intelligent control system structure. This approach is essential for the realization of adaptive and self-organizing processes of knowledge bases and guaranteed to achieve the control objectives under contingency control situations. Successful solution of the problem of choosing the type and kind of quantum correlations allows strengthening the successful search for solutions of algorithmically un-solvable problems at the classical control level. A genetic algorithm is a powerful computational intelligence toolkit for random searching of effec-tive solutions for poorly formalized tasks. However, it has a big disadvantage when used on a classic computer: low speed and dependence on the expert’s choice of a decision-making space. The paper describes the types of quantum genetic algorithms based on a combination of quantum and classical calculations, and an algorithm consisting only of quantum calculations. In such algorithm, a population can be composed of only one chromosome in a state of superposition. Immersion in the quantum structure of the fuzzy inference quantum genetic algorithm provides a synergistic effect and allows realizing quantum fuzzy inference on a classical processor. The new effect is based on the quantum genetic algorithm extracting information hidden in the clas-sical state laws change over time the gains of traditional regulators on a new unexpected situation con-trol. Such synergistic effect is possible only with end-to-end intellectual information technology of quantum computing and is absent at the classical level of application of the classical computing tech-nology.
Аннотация:В статье рассматривается применение квантового генетического алгоритма для автоматического выбора оптимального типа и вида корреляции в структуре квантового нечеткого логического вывода. В задачах интеллектуального и когнитивного управления с использованием квантовых мягких вычислений и принципов квантового глубокого машинного обучения важно правильно выбрать тип и вид квантовой корреляции. Она используется в качестве дополнительного физического и информационного вычислительного ресурса при формировании законов изменения во времени коэффициентов усиления традиционных регуляторов, находящихся на нижнем (исполнительском) уровне структуры интеллектуальной системы управления. Такой подход важен для реализации адаптивного или самоорганизующегося процесса баз знаний и гарантированного достижения цели управления в условиях непредвиденных ситуаций управления. Успешное решение задачи выбора типа и вида квантовых корреляций позволяет усилить успешный поиск решений алгоритмически неразрешимых проблем на классическом уровне управления. Генетический алгоритм – мощный инструментарий (computational intelligence toolkit) случайного поиска эффективных решений плохо формализованных задач. Однако он обладает большим недостатком при применении на классическом компьютере: низкая скорость работы и зависимость от выбора экспертом пространства поиска решений. В статье рассмотрены виды квантовых генетических алгоритмов, основанных на комбинации квантовых и классических вычислений, а также алгоритм, состоящий только из квантовых вычислений. В таком алгоритме популяция может быть составлена всего из одной хромосомы в состоянии суперпозиции. Погружение в структуру квантового нечеткого вывода квантового генетического алгоритма позволяет получить новый синергетический эффект и реализовать квантовый нечеткий вывод на классическом процессоре. Данный новый эффект основан на извлечении квантовым генетическим алгоритмом информации, скрытой в классических состояниях законов изменения во времени коэффициентов усиления традиционных регуляторов на новую непредвиденную ситуацию управления. Такой синергетический эффект возможен только за счет применения сквозной интеллектуальной информационной технологии квантовых вычислений и отсутствует на классическом уровне применения технологий классических вычислений.
Authors: Ulyanov, S.V. (ulyanovsv46_46@mail.ru) - Dubna State University – Institute of System Analysis and Control, Dubna, Joint Institute for Nuclear Research – Laboratory of Information Technology (Professor), Dubna, Russia, Ph.D, N.V. Ryabov (ryabov_nv95@mail.ru) - Dubna State University – Institute of System Analysis and Control, Dubna, Russia
Keywords: quantum computing, quantum genetic algorithm, quantum oracle, simulator, quantum fuzzy inference
Page views: 7036
PDF version article
Full issue in PDF (6.72Mb)

Font size:       Font:

Известно, что интеллектуальные системы управления (ИСУ) основаны на применении мягких вычислений, нечеткой логики, эволюционных алгоритмов и нейронных сетей. Ба- зисом развития систем управления является пропорционально-интегрально-дифференцирующий (ПИД) регулятор, который применяется в 70 % промышленной автоматики, но зачастую не справляется с задачей управления и совсем плохо работает в непредвиденных ситуациях. Нечеткие регуляторы позволяют частично расширить сферу применения ПИД-регуляторов за счет добавления продукцион- ных логических правил функционирования и частично адаптировать систему. Совместное применение генетических алгоритмов (ГА) и нечеткой нейронной сети позволило полностью адаптировать систему, но для обучения такой системы требуется время, что в нештатных и непредвиденных ситуациях критично. Моделирование оптимального обучающего сигнала дает возможность создать частичную самоорганизацию в системе за счет формирования оптимальных траекторий коэффициентов усиления ПИД-регулятора. Применение квантовых вычислений и, как частный пример, квантового нечеткого вывода (КНВ) позволяет повысить робастность без затрат временного ресурса – в режиме реального времени.

На рисунке 1 показана ИСУ с объединением нескольких нечетких регуляторов и КНВ, способствующая созданию нового качества в управлении – самоорганизации баз знаний (БЗ) в режиме online.

Описание КНВ

Главная проблема разработки и проектирования ИСУ заключается в том, что очень трудно спроектировать глобально хорошую и робастную структуру управления на все возможные случаи, особенно, когда система работает в слабо предсказуемых ситуациях. Одно из лучших решений – формирование конечного числа БЗ нечеткого регулятора для множества фиксированных ситуаций управления. Цель квантового регулятора – объединить БЗ, полученные при помощи оптимизатора БЗ, в самоорганизующиеся квантовые нечеткие регуляторы. Модель КНВ использует частные индивидуальные БЗ нечеткого регулятора, каждая из которых получена с помощью инструментария оптимизатора БЗ (SCOptKBTM).

Процесс проектирования квантовой алгоритмической ячейки (КАЯ, англ.: quantum algorithmic gate – QAG) включает матричную форму трех квантовых операторов: суперпозиции, квантовой запутанности (или квантового оракула) и интерференции, которые являются частью структуры квантовых поисковых алгоритмов (КПА, англ.: quantum search algorithm –QSA). В общем виде структура КАЯ с применением квантового ГА (КГА, англ.: quantum genetic algorithm – QGA) может быть представлена следующей формулой:

                     (1)

где I – тождественный матричный оператор; Ä – тензорное произведение; S равен I или H в зависимости от описания проблемы. Согласно уравнению (1), первая часть в проектировании КАЯ – выбор типа оператора запутанного состояния UF, который физически описывает качественные свойства исследуемой функции.

Основным блоком такой ИСУ является квантовый генетический поисковый алгоритм (КГПА, англ.: quantum genetic search algorithm – QGSA) (рис. 2).

Ключевые элементы структуры КПА как главного блока глобальной оптимизации, основанной на квантовых мягких вычислениях, представлены на рисунке 3. Формально струк- туру КГПА в (1) описывается следующим множеством логических операторов:

,                            (2)

где С – алфавит для генетического кодирования индивидуума для конкретной задачи; Ev – функция пригодности; P0– начальная популяция; L – размер популяции; W – оператор от- бора (селекции); c – оператор скрещивания; m – оператор мутации; Sup – квантовый оператор линейной суперпозиции; Ent – квантовый оператор запутывания (смешанное состояние); Inf – оператор вывода; D – условие остановки, включающее такие критерии, как оптимум заданной функции пригодности и минимум энтропии Шеннона–фон Неймана.

Алгоритм КНВ для определения новых коэффициентов усиления ПИД-регулятора K (рис. 3) состоит из таких этапов, как нормализация, формирование квантового бита, после которого выполняется подбор оптимальной структуры КАЯ, выбирается состояние с максимальной амплитудой, осуществляется декодирование и на выходе получается новый параметр k [1, 2].

На входе КНВ получает коэффициенты от сформированных заранее БЗ нечеткого регулятора на основе оптимизатора БЗ на мягких вычислениях [1].

Следующий шаг – нормализация полученных сигналов [0, 1] путем деления текущих значений сигналов управления на их максимальные значения (max k), которые заранее известны.

Формирование квантовых битов. Определяются функции плотности распределения вероятностей. Они интегрируются, и из них получаются функции распределения вероятностей, позволяющие определить виртуальные состояния сигналов управления для формирования суперпозиции с помощью преобразова- ния Адамара из текущего состояния введенных сигналов управления. Используется закон ве- роятности: p(|0ñ) + p(|1ñ)  = 1, где p(|0ñ) – вероятность текущего реального состояния; p(|1ñ) – вероятность текущего виртуального состоя- ния [3, 4]. По текущему реальному состоянию из закона сохранения вероятностей определяется виртуальное состояние.

Суперпозиция квантовой системы «реальное состояние–виртуальное состояние» имеет вид: .

На рисунке 4 показан процесс формирования квантовых битов для текущего реального состояния нормированного сигнала управления, описывающего коэффициенты усиления нечеткого ПИД-регулятора.

На следующем этапе осуществляется выбор вида и типа квантовой корреляции – построение запутанных состояний. Рассматриваются три типа квантовой корреляции: пространственная, временная и пространственно-временная и два вида корреляции – внутренняя и внешняя. Каждая из них содержит скрытую в спроектированных БЗ ценную квантовую информацию [2].

В ходе работы был проведен эксперимент на квантовом симуляторе системы «каретка–перевернутый маятник» с применением ПИД-регулятора, двух нечетких регуляторов и алгоритмов квантового нечеткого вывода с применением различных типов корреляции (рис. 5), где Q-S-T – пространственно-временная корреляция, Q-T – временная, Q-S – пространственная.

Виды и операторы КГА

Существует несколько различных видов КГА. Все они построены на комбинации квантовых и классических вычислений. Квантовые вычисления включают в себя квантово-генетические операторы, выполняющие генетические операции на квантовых хромосомах. Эти операторы называют interference gates (интерференционные ячейки).

Существует несколько операторов обновления, но наиболее востребованным является Q-gate интерференции (вращения) [5]. Оператор квантовой интерференции обозначается как gate U(t):

.

Применяя оператор U(t) к исходной хро- мосоме популяции, получим эволюцию по- пуляции как результат процесса унитарных преобразований, особенно вращения, приближающего состояние хромосом к состоянию оптимальной хромосомы в популяции.

Таким образом, ячейка усиливает или уменьшает амплитуду кубитов или генов в со ответствии с хромосомой с максимальной функцией пригодности: f(x1, x2, x3, …, xj)i, то есть эволюция квантового состояния определяется лучшими индивидуумами.

В работе рассматриваются КГА [6, 7], гибридный ГА (ГГА) и сокращенный КГА (СКГА). В КГА используются квантовый гейт вращений и квантовый гейт мутации, в ГГА между ними добавляется оператор кроссовера.

Примечание. В классическом ГА оператор выбора имитирует дарвиновский естественный отбор, улучшая популяции, продвигая особи с лучшей пригодностью и «наказывая» тех, кто имеет худшую производительность. В КГА выбор заменяется изменением всех особей на лучшую. Поэтому, когда популяция обновляется оператором вращения, она сходится, но обычно КГА попадает в локальные оптимумы, подвергающиеся преждевременной конвергенции (сходимости). Чтобы избежать этого, КГА часто включают в себя либо рулетку, либо элитный выбор. Например, КГА с шагом выбора используется в улучшенном алгоритме кластеризации К-средних. Существуют еще более экстремальные подходы, например, когда КГА включает в себя выбор и алгоритм имитации отжига, исключающий преждевременную конвергенцию. В других случаях шаг выбора включается без помощи операторов, обычно используемых в ГА. Это случай полуклассического ГА, где оператор селекции (выбора) стремится к максимальной пригодности посредством квантового подхода, например, используя алгоритм Гровера [8].

Оператор квантовой мутации (инверсия). В имитации ГА существует также квантовая версия классического оператора мутации. КГА выполняет межкубитную мутацию j-го кубита, заменяя амплитуды вероятности с помощью квантового оператора (ячейки) Паули.

Оператор квантовой мутации (ввод). Этот гейт напоминает биологический механизм введения хромосом. Вставка хромосомы означает, что сегмент хромосомы был вставлен в необычную позицию на той же или другой хромосоме. Квантовая версия этого генетического механизма включает перестановку или обмен между двумя случайно выбранными кубитами (левый, правый). Например, предположим, что, учитывая следующую хромосому, выбираются случайным образом первый и третий кубиты.

Оператор квантового перехода (классический). Квантовый кроссовер моделируется по аналогии с классическим алгоритмом реком- бинации, используемым в ГА, но работает с амплитудами вероятности. Хотя квантовая версия мутации может быть реализована на квантовом компьютере, есть теоретические причины, препятствующие выполнению кроссовера. Тем не менее, несмотря на теоретические ограничения, квантовая версия классического оператора кроссовера применяется во многих практических задачах оптимизации. В таких случаях поиск решения осуществляется с использованием квантового эволюционного вдохновляющего подхода. Вслед за этим оператор иллюстрируется для случая одноточечного кроссовера. В данном примере, если точка разреза выбирается произвольно, например, между первым и вторым положениями, происходит обмен хромосомными сегментами.

Оператор квантового перехода (интерференция). Настоящий квантовый оператор выполняет кроссовер путем рекомбинации в соответствии с критерием, основанным на рисовании диагоналей. В результате все особи смешиваются друг с другом, приводя к потомству. Оба квантовых алгоритма (КГА и ГГА) были протестированы на примере применения их в задаче нахождения корней уравнения .

Результат выполнения КГА показан на рисунке 6. Видно, что примерно после 30-й попу- ляции значение функции пригодности перестает меняться.

ГГА показывает результаты, изображенные на рисунке 7.

КГА и ГГА можно рассматривать как классические методы оптимизации, основанные на принципах квантовых вычислений. Про- граммы, реализующие такие методы, могут выполняться на цифровом классическом компьютере, что подразумевает практические или теоретические трудности.

Примечание. Одна из интересных идей была предложена в 2004 году, это были первые шаги в реализации ГА на квантовом компьютере [2]. Автором предложен настоящий квантовый эволюционный алгоритм, который можно назвать СКГА.

Алгоритм состоит из следующих этапов:

-     инициализация суперпозиции всех возможных хромосом;

-     оценка пригодности оператором F;

-     применение алгоритма Гровера;

-     квантовый оракул;

-     применение диффузионного оператора Гровера G;

-     оценка решения.

Поиск решений в СКГА выполняется за одну операцию. Однако сейчас его можно при- менять только на простых задачах, например, поиска решения уравнений. Результатом вы- полнения СКГА в таком случае будет следующая матрица:

[[0.078125]

[0.078125]

[0.078125]

[0.078125]

[0.078125]

[0.078125]

[0.078125]

[0.078125]

[0.078125]

[0.078125]

[0.078125]

[0.953125]

[0.078125]

[0.078125]

[0.078125]

[0.078125]]

В КГА и ГГА эволюция является результатом унитарных преобразований, особенно вращений, приближающих состояние хромосом к состоянию оптимальной хромосомы с максимальной пригодностью. Поскольку эта процедура повторяется из поколения в поколение, результатом является быстрая сходимость к локальным оптимумам, имеющим место локальной ловушки.

Общая стратегия улучшения качества КГА заключается в использовании небольших усовершенствований алгоритма, например, вклю- чая новые операторы: квантовое бедствие, возмущение или другие настроенные алгоритмы [9]. Но во многих случаях эти операторы полезны только в высокоспецифичных приложениях [5, 10].

Можно сделать вывод, что эволюция (оптимизация) квантовых эволюционных алгоритмов является результатом вращения квантового гейта, который вводит явление интерференции. Таким образом, особи корректируются или модифицируются, чтобы быть более похожими на лучшую особь в популяции. В результате популяция подвергается более низкому дарвиновскому давлению отбора. Однако в ГА после оценки особей алгоритм, имитирующий выбор (например, оператор выбора родителей), заме- нит старую популяцию P(t) на новую популяцию P(t + 1) особей. Поскольку особи выбираются в соответствии с их значением пригодности, популяция решений развивается через дарвиновскую эволюцию, но с большим давлением отбора, чем КГА и ГГА. Следовательно, ГА заменяет устаревшие стратегии инновационными стратегиями, представленными потомством. Аналогично, когда кроссовер включен как шаг в алгоритм ГГА, его производительность обычно становится ближе к ГА.

Преимущество КГА в том, что они требуют меньше хромосом, чем ГА. В теории в истинном КГА (СКГА) можно считать, что популяция составлена из одной хромосомы в состоянии суперпозиции [2]. Этот факт не является неожиданным с точки зрения квантовой механики. Более того, алгоритм СКГА демонстрирует, что с использованием квантовых вычислений стратегия генетического поиска становится тавтологией. Эволюция происходит в одном поколении и является следствием квантового эффекта.

В ходе исследования с различными типами взаимосвязей было определено, что наилучший результат показывает пространственно-временная корреляция [1].

Запустив написанный КГА на несколько тысяч поколений (рис. 8), можно увидеть, что около 70 % лучших показателей у пространственно-временной корреляции. Временная и пространственная имеют примерно одинаковый процент. Стоит отметить, что после 5 000 поколений изменение вероятностей уже не происходит.

После 200 запусков КГА можно заметить, что вероятность выбора пространственно-временной корреляции снизилась до 60 % (рис. 9).

Заключение

Полноценная разработка и инженерное прикладное применение квантовых алгоритмов при текущих исследованиях и практических результатах в области квантовых компьютеров затруднены. Необходимо проводить исследования с учетом доступных возможностей разработки и моделировать квантовые алгоритмы на классическом компьютере, ожидая возможности создания промышленных версий квантовых компьютеров. Применение квантового программирования и суперкомпьютинга на основе GRID-технологий  является одним из эффективных решений в данном направлении.

Одной из востребованных задач является интеллектуальное робастное управление физическими объектами в непредвиденных ситуациях. Современные решения этой проблемы уже позволяют достичь хороших результатов, но такие системы не могут обучаться в режиме реального времени, поэтому набор способов реакций на события крайне ограничен. С помощью квантовых вычислений и, в частности, алгоритма КНВ можно решить подобные проблемы за счет повышения скорости глубокого машинного обучения.

Выбор вида и типа квантовой корреляции в КНВ – важная часть в ИСУ. Определение оптимальных параметров квантовой корреляции способствует улучшению показателей системы в нештатных и непредвиденных ситуациях. В статье рассмотрено использование КГА для автоматизации этапа определения квантовой корреляции. Существует несколько подходов к реализации КГА. В работе рассмотрены три типа: КГА, ГГА и СКГА. Применение первых двух алгоритмов возможно на классическом компьютере, что позволяет решить поставлен- ную в работе задачу, но полноценно не решает проблему скорости работы ГА. СКГА пока можно применять только на простых задачах, но при возможности его полноценной реализации на GRID-технологиях суперкомпьютеров типа ГОВОРУН ЛИТ ОИЯИ или квантовом компьютере он покажет существенное увеличение скорости работы за счет того, что целая популяция составлена из одной хромосомы в состоянии суперпозиции.

Литература

1.    Ульянов С.В. и др. Интеллектуальные системы управления: в 5 т. Т. 4. Оптимизатор баз знаний на квантовых вычислениях: в 2 ч. Ч. 2. Самоорганизующиеся интеллектуальные системы управления. Дубна: Изд-во Гос. ун-та «Дубна», 2014. 182 с.

2.    Ulyanov S.V. Self-organizing quantum robust control methods and systems for situations with uncertainty and risk. Patent US 8788450 B2, 2014, 31 p.

3.    Pintu Chandra Shill, Faijul Amin, Kazuyuki Murase. Parameter optimization based on quantum genetic algorithms for fuzzy logic controller. Proc. 27th Fuzzy System Sympos. Japan, 2011, pp. 1065–1068.

4.    Chandra Shill P., Sarker B., Chowdhury Urmi M., Murase K.. Quantum fuzzy controller for inverted pendulum system based on quantum genetic optimization. IJARCS, 2012, vol. 3, no. 7, pp. 1–8.

5.    Lahoz-Beltra R. Quantum genetic algorithms for computer scientists. Computers. 2016, vol. 5, iss. 4, 24 p. DOI: https://doi.org/10.3390/computers5040024.

6.    Cheng-Wen Lee, Bing-Yi Lin. Applications of the chaotic quantum genetic algorithm with support vector regression in load forecasting. Energies. 2017, vol. 10, iss. 11, pp. 18–32. DOI: https://doi.org /10.3390/en10111832.

7.    Arjmandzadeh A., Yarahmadi M. Quantum genetic learning control of quantum ensembles with Hamiltonian uncertainties, 2017, no. 19, vol. 8, art. 376. DOI: 10.3390/e19080376.

8.    Grover L.K. A fast quantum mechanical algorithm for database search. Proceedings, 28th Annual ACM Symposium on the Theory of Computing, 1996, pp. 212–219.

9.    Huaixiao Wang, Jianyong Liu, Jun Zhi. The improvement of quantum genetic algorithm and its application on function optimization. Mathematical Problems in Engineering, 2013, vol. 2013, art. 730749, 10 p. DOI: 10.1155/2013/730749.

10. Malossini A., Blanzieri E., Calarco T. QGA: A quantum genetic algorithm. Tech. Report, Univ. of Toronto, 2004, pp. 1–19. URL: http://eprints.biblio.unitn.it/711/1/qga_techrep.pdf/ (дата обращения: 01.12.2018).

References

  1. Ulyanov S.V. Intelligent Control Systems. Vol. 4. Knowledge Optimizer on Quantum Computing. Part 2. Self-Organizing Intelligent Control Systems. Dubna, Dubna State Univ., 2014, 182 p.
  2. Ulyanov S.V. Self-Organizing Quantum Robust Control Methods and Systems for Situations with Uncertainty and Risk. Patent US 8788450 B2, 2014, 31 p.
  3. Chandra Shill P., Amin F., Murase K. Parameter optimization based on quantum genetic algorithms for fuzzy logic controller. Proc. 27th Fuzzy System Symp. Japan, 2011. pp. 1065–1068.
  4. Chandra Shill P., Sarker B., Chowdhury Urmi M., Murase K. Quantum fuzzy controller for inverted pendulum system based on quantum genetic optimization. IJARCS. 2012, vol. 3, no. 7, pp. 1–8.
  5. Lahoz-Beltra R. Quantum genetic algorithms for computer scientists. Computers. 2016, vol. 5, 24 p. DOI: https://doi.org/10.3390/computers5040024.
  6. Lee Ch.-W., Lin Bing-Yi. Applications of the chaotic quantum genetic algorithm with support vector regression in load forecasting. Energies. 2017, vol. 10, iss. 11, pp. 1832. DOI: https://doi.org/10.3390/
    en10111832.
  7. Arjmandzadeh A., Yarahmadi M. Quantum Genetic Learning Control of Quantum Ensembles with Hamiltonian Uncertainties. Switzerland, 2017, no. 19, vol. 8, art. 376. DOI: 10.3390/e19080376.
  8. Grover L.K. A fast quantum mechanical algorithm for database search. Proc. 28th Annual ACM Symp. on the Theory of Computing. 1996, pp. 212–219.
  9. Wang H., Liu J., Zhi J. The improvement of quantum genetic algorithm and its application on function optimization. Mathematical Problems in Engineering. China, 2013, vol. 2013, art. 730749, 10 p. DOI: 10.1155/2013/730749.
  10. Malossini A., Blanzieri E., Calarco T. QGA: A Quantum Genetic Algorithm. Technical Report. Univ. of Toronto, 2004, pp. 1–19. Available at: http://eprints.biblio.unitn.it/711/1/qga_techrep.pdf/ (accessed December 01, 2018).

Permanent link:
http://swsys.ru/index.php?page=article&id=4580&lang=&lang=en&like=1
Print version
Full issue in PDF (6.72Mb)
The article was published in issue no. № 2, 2019 [ pp. 181-189 ]

Perhaps, you might be interested in the following articles of similar topics: