Примеры применения генетических алгоритмов в задачах управления

Рассмотрим применение ГА в задачах интеллектуального управления.

Пример 1. Применение ГА для оптимального выбора нечетких правил.

Задача 1 – парковка движущегося объекта.

Рассмотрим следующую задачу управления движением тележки (рис.2.29): разработать нечеткий регулятор (НР), который переводит тележку (объект управления - ОУ) из заданных начального положения и начальной скорости в целевое положение (0,0) (центровка и останов) за минимальное время.

Начальное состояние ОУ: Примеры применения генетических алгоритмов в задачах управления - №1 - открытая онлайн библиотека ; Целевое (конечное) состояние ОУ: [0,0].

Примеры применения генетических алгоритмов в задачах управления - №2 - открытая онлайн библиотека

Рис. 2.29. Задача парковки движущегося объекта

Математическая модель для заданной задачи управления представляется следующими уравнениями движения:

Примеры применения генетических алгоритмов в задачах управления - №3 - открытая онлайн библиотека

Примеры применения генетических алгоритмов в задачах управления - №4 - открытая онлайн библиотека ,

где Примеры применения генетических алгоритмов в задачах управления - №5 - открытая онлайн библиотека – положение тележки на дороге, представленной одномерной осью Примеры применения генетических алгоритмов в задачах управления - №6 - открытая онлайн библиотека в модели объекта на рис.2.29; Примеры применения генетических алгоритмов в задачах управления - №7 - открытая онлайн библиотека – скорость движения тележки; Примеры применения генетических алгоритмов в задачах управления - №8 - открытая онлайн библиотека – сила управления, приложенная к тележке; Примеры применения генетических алгоритмов в задачах управления - №9 - открытая онлайн библиотека – шаг управления, m – масса тележки.

Прежде всего, вспомним, какие шаги должны быть сделаны при построении НР:

· описание входных и выходных переменных и их множеств значений (Таблица 2.5а);

· разбиение множеств значений на подмножества значений;

· описание этих подмножеств с помощью нечетких множеств с заданными функциями принадлежности (рис.2.30);

· построение множества нечетких правил (Таблица 2.5б).

Итак, на вход НР поступают значения следующих переменных:

· Примеры применения генетических алгоритмов в задачах управления - №5 - открытая онлайн библиотека – положение тележки;

· Примеры применения генетических алгоритмов в задачах управления - №7 - открытая онлайн библиотека – скорость движения тележки.

На выходе – значения силы управления Примеры применения генетических алгоритмов в задачах управления - №8 - открытая онлайн библиотека , приложенной к тележке.

Примеры применения генетических алгоритмов в задачах управления - №13 - открытая онлайн библиотека

Рис. 2.30. Функции принадлежности

Пространство изменения переменных Примеры применения генетических алгоритмов в задачах управления - №5 - открытая онлайн библиотека , Примеры применения генетических алгоритмов в задачах управления - №7 - открытая онлайн библиотека и Примеры применения генетических алгоритмов в задачах управления - №16 - открытая онлайн библиотека будем описывать с помощью следующих лингвистических переменных {NM, NS, ZE, PS, PM} = {«negative medium», «negative small», «Zero», «positive small», «positive medium»}.

Будем рассматривать следующие нечеткие правила:

ЕСЛИ Примеры применения генетических алгоритмов в задачах управления - №5 - открытая онлайн библиотека есть {NM,…, PM} И v есть {NM,…, PM}

ТО Примеры применения генетических алгоритмов в задачах управления - №16 - открытая онлайн библиотека есть {NM, NS, ZE, PS, PM}.

Приведенный тип правил соответствует модели нечеткого вывода Мамдани.

В общем виде правила в такой модели выглядят следующим образом:

Правило l: ЕСЛИ Примеры применения генетических алгоритмов в задачах управления - №19 - открытая онлайн библиотека ТО Примеры применения генетических алгоритмов в задачах управления - №20 - открытая онлайн библиотека ,

где Примеры применения генетических алгоритмов в задачах управления - №21 - открытая онлайн библиотека – входные лингвистические переменные, « Примеры применения генетических алгоритмов в задачах управления - №22 - открытая онлайн библиотека » операция нечеткой конъюнкции.

В общем виде выходное значение в модели Мамдани (с нечеткой конъюнкцией в виде умножения, синглетон-фаззификатором и дефаззификатором «средний максимум») вычисляется по следующей формуле:

Примеры применения генетических алгоритмов в задачах управления - №23 - открытая онлайн библиотека ,

где Примеры применения генетических алгоритмов в задачах управления - №24 - открытая онлайн библиотека - точка максимального значения (центра) функции Примеры применения генетических алгоритмов в задачах управления - №25 - открытая онлайн библиотека .

Различные НР имеют различные функции принадлежности и различные множества нечетких правил.

Нашей задачей является найти оптимальное множество нечетких правил так, чтобы НР осуществлял задачу управления за минимальное время.

Первый шаг в применении ГА – выбор способа кодирования потенциальных решений.

Что такое «потенциальные решения» для нашей задачи? Это множество нечетких правил (НП), которое может быть представлено в виде так называемой таблицы «look-up-table», показанной в Таблице 2.5 б.

Введем следующее кодирование для типа функций принадлежности (лингвистических переменных) внутри Таблицы 2.5:

1 - NM, 2 - NS, 3 - ZE, 4 - PS, 5 - PM.

Таблица 2.5 а Параметры модели Таблица 2.5 б Множество НП
  Примеры применения генетических алгоритмов в задачах управления - №26 - открытая онлайн библиотека   Примеры применения генетических алгоритмов в задачах управления - №27 - открытая онлайн библиотека

Выставив все значения строк таблицы в одну строку, получим строку из 25 позиций - {1432152432124514312211345}, которую легко перевести в бинарную строку, которая и будет служить хромосомой для данной задачи оптимизации с помощью ГА. Зададим также важные параметры ГА поиска: размер популяции = 100; максимальное число генераций = 100; вероятность скрещивания = 0.7; вероятность мутации = 0.03.

В качестве оператора селекции используется разновидность метода «tournament selection»: две или более хромосомы выбираются случайным образом и их значения пригодности сравниваются. Хромосомы с большими значениями пригодности копируются в следующую генерацию. Для лучшего поиска решения, ГА процесс разделяется на две стадии: стадия 1, называемая «эволюцией», и стадия 2, называемая «refinement stage». На первой стадии ГА ищет приемлемые решения по управлению такие, что ошибка управления минимальна (заданное значение). На второй стадии отбираются решения с минимальным временем, переводящим состояние ОУ из положения Примеры применения генетических алгоритмов в задачах управления - №1 - открытая онлайн библиотека в целевое положение [0,0]. Опишем стадию 1.

Стадия 1.

Число генераций равно 30. Функция пригодности (ФП) «награждает» каждое решение в зависимости от того, как близко данное решение к заданному пределу ошибки управления = Примеры применения генетических алгоритмов в задачах управления - №29 - открытая онлайн библиотека 0.5 по Примеры применения генетических алгоритмов в задачах управления - №5 - открытая онлайн библиотека и по Примеры применения генетических алгоритмов в задачах управления - №7 - открытая онлайн библиотека .

Введем функцию пригодности ГА для оценки пригодности текущей хромосомы, представляющей собой множество нечетких правил, т.е. некоторый НР. Для вычисления Примеры применения генетических алгоритмов в задачах управления - №5 - открытая онлайн библиотека и Примеры применения генетических алгоритмов в задачах управления - №7 - открытая онлайн библиотека используется математическая модель.

Функция пригодности для стадии 1 (эволюции):

(if ( Примеры применения генетических алгоритмов в задачах управления - №34 - открытая онлайн библиотека < 0.5 ) and ( Примеры применения генетических алгоритмов в задачах управления - №35 - открытая онлайн библиотека < 0.5) then fitness = Примеры применения генетических алгоритмов в задачах управления - №36 - открытая онлайн библиотека

%{ Примеры применения генетических алгоритмов в задачах управления - №5 - открытая онлайн библиотека и Примеры применения генетических алгоритмов в задачах управления - №7 - открытая онлайн библиотека в пределах значений ошибки управления}

else ( if ( Примеры применения генетических алгоритмов в задачах управления - №39 - открытая онлайн библиотека = 175 ) then

%{максимальное число шагов управления задачи}

(if ( Примеры применения генетических алгоритмов в задачах управления - №34 - открытая онлайн библиотека < 1.0 ) and ( Примеры применения генетических алгоритмов в задачах управления - №35 - открытая онлайн библиотека < 1.0) then fitness = Примеры применения генетических алгоритмов в задачах управления - №42 - открытая онлайн библиотека else fitness = Примеры применения генетических алгоритмов в задачах управления - №43 - открытая онлайн библиотека )

if ( ( Примеры применения генетических алгоритмов в задачах управления - №34 - открытая онлайн библиотека > 5.0 ) and ( Примеры применения генетических алгоритмов в задачах управления - №35 - открытая онлайн библиотека > 5.0 ) then fitness = Примеры применения генетических алгоритмов в задачах управления - №46 - открытая онлайн библиотека ).

Примечание: За символом «%» идет комментарий.

Обсудим данную функцию. Если хромосома успешна по критерию качества управления, то она оценивается в зависимости от времени, необходимого для выполнения задачи управления. Минимальное значение ФП в этом случае равно 8 (так как 175 – заданный лимит шагов управления).

Если хромосома выходит за рамки «175 шагов», то она или «поощряется» положительным значением ФП (если удовлетворительное качество управления ( Примеры применения генетических алгоритмов в задачах управления - №34 - открытая онлайн библиотека < 1.0 ) и ( Примеры применения генетических алгоритмов в задачах управления - №35 - открытая онлайн библиотека < 1.0) или «наказывается» отрицательным значением ФП, если плохое качество управления. Если хромосома неуспешна по критерию качества управления ( Примеры применения генетических алгоритмов в задачах управления - №34 - открытая онлайн библиотека > 5.0 ) и ( Примеры применения генетических алгоритмов в задачах управления - №35 - открытая онлайн библиотека > 5.0), то она наказывается большим отрицательным значением ФП.

Рисунки внизу 2.31 и 2.32 иллюстрируют структуру хромосомы и процесс вычисления функции пригодности.

Примеры применения генетических алгоритмов в задачах управления - №51 - открытая онлайн библиотека

Рис. 2.31. Иллюстрация процесса декодирования хромосомы

Примеры применения генетических алгоритмов в задачах управления - №52 - открытая онлайн библиотека

Рис. 2.32. Схема вычисления функции пригодности

Стадия 2.

Число генераций - от 31 -ой до 100-ой.

Функция пригодности для стадии 2 (отбора по критерию времени):

(if ( Примеры применения генетических алгоритмов в задачах управления - №34 - открытая онлайн библиотека < 0.5 ) and ( Примеры применения генетических алгоритмов в задачах управления - №35 - открытая онлайн библиотека < 0.5)

%{ Примеры применения генетических алгоритмов в задачах управления - №5 - открытая онлайн библиотека и Примеры применения генетических алгоритмов в задачах управления - №7 - открытая онлайн библиотека в пределах значений ошибки управления}

then fitness = Примеры применения генетических алгоритмов в задачах управления - №57 - открытая онлайн библиотека

else (if ( Примеры применения генетических алгоритмов в задачах управления - №39 - открытая онлайн библиотека = 175 ) % {максимальное число шагов управления задачи}

then fitness = Примеры применения генетических алгоритмов в задачах управления - №59 - открытая онлайн библиотека ))

if (( Примеры применения генетических алгоритмов в задачах управления - №34 - открытая онлайн библиотека > 5.0 ) and ( Примеры применения генетических алгоритмов в задачах управления - №35 - открытая онлайн библиотека > 5.0 ) then fitness = Примеры применения генетических алгоритмов в задачах управления - №62 - открытая онлайн библиотека ).

На рис. 2.33 показан результат ГА оптимизации для задачи 1.

Примеры применения генетических алгоритмов в задачах управления - №63 - открытая онлайн библиотека (a) Примеры применения генетических алгоритмов в задачах управления - №64 - открытая онлайн библиотека (b)

Рис. 2.33. НР с оптимально выбранным множеством НП

Множество НП Примеры применения генетических алгоритмов в задачах управления - №65 - открытая онлайн библиотека (c) Примеры применения генетических алгоритмов в задачах управления - №66 - открытая онлайн библиотека (d)

Рис. 2.33. НР с оптимально выбранным множеством НП

Примечание. На рис.2.33 значения (а), (b) и (d) фиксированы, значения (c) найдены с помощью ГА.

Пример 2. Рассмотрим следующую задачу: с помощью оптимизации, основанной на ГА, выбрать такие коэффициенты усиления ПИД регулятора Примеры применения генетических алгоритмов в задачах управления - №67 - открытая онлайн библиотека , чтобы ошибка управления была минимальной (основной критерий качества управления).

Общая схема оптимизации коэффициентов усиления ПИД регулятора с помощью ГА показана на рис. 2.34.

Примечание. В этом примере мы рассматриваем общие вопросы поставленной задачи без уточнения ОУ и цели управления.

Примеры применения генетических алгоритмов в задачах управления - №68 - открытая онлайн библиотека

Рис. 2.34. Схема оптимизации с помощью ГА коэффициентов усиления ПИД регулятора

Рассмотрим два варианта этой задачи: 1) поиск оптимальных постоянных коэффициентов усиления ПИД регулятора; и 2) поиск оптимальных переменных коэффициентов усиления ПИД регулятора, которые используются в нечетких регуляторах;

Поскольку целью управления (в общем виде) является минимизация ошибки управления, то в качестве функции пригодности можно выбрать, например, следующую функцию:

Примеры применения генетических алгоритмов в задачах управления - №69 - открытая онлайн библиотека , где Примеры применения генетических алгоритмов в задачах управления - №70 - открытая онлайн библиотека - ошибка управления.

Ошибка управления (по определению) вычисляется как

Примеры применения генетических алгоритмов в задачах управления - №71 - открытая онлайн библиотека ,

где Примеры применения генетических алгоритмов в задачах управления - №72 - открытая онлайн библиотека - задающий сигнал (цель управления), а Примеры применения генетических алгоритмов в задачах управления - №73 - открытая онлайн библиотека - состояние ОУ.

Тогда, отыскивая с помощью ГА максимум функции Примеры применения генетических алгоритмов в задачах управления - №74 - открытая онлайн библиотека , мы тем самым минимизируем ошибку управления Примеры применения генетических алгоритмов в задачах управления - №70 - открытая онлайн библиотека . В этом случае большие значения функции пригодности будут соответствовать малым значениям ошибки управления, а, следовательно, лучшему качеству управления ПИД регулятора.

Так как ГА работает с закодированными параметрами, обсудим способ кодирования для нашей задачи.

Вначале рассмотрим простейший случай – задача оптимизации постоянных коэффициентов усиления ПИД регулятора - Примеры применения генетических алгоритмов в задачах управления - №67 - открытая онлайн библиотека .

Задача 2: поиск оптимальных постоянных коэффициентов усиления ПИД регулятора. Без потери общности, предположим, что необходимо Примеры применения генетических алгоритмов в задачах управления - №77 - открытая онлайн библиотека бит для кодирования значений ПИД параметров( Примеры применения генетических алгоритмов в задачах управления - №67 - открытая онлайн библиотека ). В этом случае, размер хромосомы Примеры применения генетических алгоритмов в задачах управления - №79 - открытая онлайн библиотека , представляющей значения Примеры применения генетических алгоритмов в задачах управления - №67 - открытая онлайн библиотека , будет Примеры применения генетических алгоритмов в задачах управления - №81 - открытая онлайн библиотека бит. Представим Примеры применения генетических алгоритмов в задачах управления - №79 - открытая онлайн библиотека как S = Примеры применения генетических алгоритмов в задачах управления - №83 - открытая онлайн библиотека , где Примеры применения генетических алгоритмов в задачах управления - №84 - открытая онлайн библиотека - следующие строки:

Примеры применения генетических алгоритмов в задачах управления - №85 - открытая онлайн библиотека , Примеры применения генетических алгоритмов в задачах управления - №86 - открытая онлайн библиотека , и Примеры применения генетических алгоритмов в задачах управления - №87 - открытая онлайн библиотека .

Рассмотрим, как определить число Примеры применения генетических алгоритмов в задачах управления - №88 - открытая онлайн библиотека бит для кодирования ПИД параметров. Допустим, что

Примеры применения генетических алгоритмов в задачах управления - №89 - открытая онлайн библиотека , Примеры применения генетических алгоритмов в задачах управления - №90 - открытая онлайн библиотека , Примеры применения генетических алгоритмов в задачах управления - №91 - открытая онлайн библиотека ,

где R есть множество всех действительных чисел.

Для каждого интервала Примеры применения генетических алгоритмов в задачах управления - №92 - открытая онлайн библиотека построим соответствующую решетку значений следующим образом. Зададим расстояние Примеры применения генетических алгоритмов в задачах управления - №93 - открытая онлайн библиотека между соседними точками решетки. Это расстояние называется шагом дискретизации ГА (GA discretization step). Тогда общее число точек Примеры применения генетических алгоритмов в задачах управления - №94 - открытая онлайн библиотека в решетке будет вычисляться по формуле:

Примеры применения генетических алгоритмов в задачах управления - №95 - открытая онлайн библиотека .

Для выбора лучшего значения (с точки заданной функции пригодности), например, для Примеры применения генетических алгоритмов в задачах управления - №89 - открытая онлайн библиотека ГА исследует все точки в решетке:

Примеры применения генетических алгоритмов в задачах управления - №97 - открытая онлайн библиотека

Длина бинарной хромосомы Примеры применения генетических алгоритмов в задачах управления - №98 - открытая онлайн библиотека для кодирования десятичного числа из Примеры применения генетических алгоритмов в задачах управления - №99 - открытая онлайн библиотека определяется по формуле:

Примеры применения генетических алгоритмов в задачах управления - №88 - открытая онлайн библиотека = Примеры применения генетических алгоритмов в задачах управления - №101 - открытая онлайн библиотека .

Примечание. Для вычисления значений пригодности хромосомы, бинарные значения Примеры применения генетических алгоритмов в задачах управления - №102 - открытая онлайн библиотека преобразуются обратно в десятичные числа по следующей формуле:

Примеры применения генетических алгоритмов в задачах управления - №103 - открытая онлайн библиотека

где Примеры применения генетических алгоритмов в задачах управления - №104 - открытая онлайн библиотека ( Примеры применения генетических алгоритмов в задачах управления - №105 - открытая онлайн библиотека ).

Графическая иллюстрация этих вычислений приведена на рис. 2.34.

Примеры применения генетических алгоритмов в задачах управления - №106 - открытая онлайн библиотека

Рис. 2.34. Вычисление значений бинарных хромосом

После того, как кодирование ПИД параметров, функция пригодности и пространство поиска для коэффициентов усиления ПИД регулятора определены, можно применять стандартный ГА.

На рисунке 2.35 показана Матлаб–Симулинк структура системы моделирования оптимальных коэффициентов усиления ПИД- регулятора.

Задача 3: поиск оптимальных переменных коэффициентов усиления ПИД регулятора для нечеткого регулятора

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

Для реализации этой задачи разработана система, названная SSCQ - система моделирования качества управления (от англ. simulation system of control quality). Матлаб–Симулинк структура системы SSCQ показана на рис.2.36.

Примеры применения генетических алгоритмов в задачах управления - №108 - открытая онлайн библиотека

Рис. 2.35. Матлаб/Симулинк структура системы моделирования оптимальных коэффициентов усиления ПИД-регулятора.

Примеры применения генетических алгоритмов в задачах управления - №109 - открытая онлайн библиотека

Рис. 2.36. Матлаб/Симулинк структура системы оптимизации управления, основанной на ГА

Примеры применения генетических алгоритмов в задачах управления - №110 - открытая онлайн библиотека

Рис. 2.37. Пример обучающего сигнала

С помощью ГА находим оптимальные значения коэффициентов усиления ПИД Примеры применения генетических алгоритмов в задачах управления - №111 - открытая онлайн библиотека для моментов времени Примеры применения генетических алгоритмов в задачах управления - №112 - открытая онлайн библиотека . В дальнейшем эти значения будем называть законами управления. Объединяя законы управления с соответствующими значениями ошибки управления (control error), ее скорости (derivative of error) и интегральной части (integral error), получаем так называемый обучающий сигнал (ОС) (teaching signal (TS)). Пример ОС показан на рис. 2.37.

Данный обучающий сигнал используется на этапе обучения в нечеткой нейронной сети (ННС) (Fuzzy Neural Network (FNN)), реализующей модель нечеткого вывода Сугено нулевого порядка.

Теория ННС является одной из составляющих компонент технологии мягких вычислений. В следующем параграфе мы обсудим основные понятия ННС и алгоритмы их обучения.

2.4. Искусственные и нечеткие нейронные сети: основные понятия и применение

В данной главе мы обсудим основные понятия в теории искусственных нейронных сетей (Artificial neural networks), рассмотрим обобщение на нечеткие нейронные сети и их применение.

Искусственные нейронные сетипредставляют собой математические модели, а также их программные или аппаратные реализации, построенные по принципу организации и функционирования биологических нейронных сетей - сетей нервных клеток живого организма.

Широкое распространение ИНС связано с их следующими двумя ключевыми характеристиками:

1) адаптивными свойствами, позволяющими «обучаться на примерах» (подробнее смотри далее);

2) структура ИНС воплощает свойство параллелизма вычислений, что позволяет находить решения в реальном времени.

Эти свойства ИНС позволяют использовать их для решения следующих проблем:

· аппроксимация функций на основе ряда данных;

· распознавание образов;

· кластеризация и классификация данных;

· обучение в области статистической обработки данных;

· накопление знаний через обучение на примерах;

· предсказание и прогноз;

· оптимизация;

· ассоциативная память;

· нелинейное моделирование и управление.

Понятие искусственной нейронной сети (ИНС) возникло при изучении процессов, протекающих в коре головного мозга, и при попытке смоделировать эти процессы. Сети называются «нейронными» благодаря аналогии с нейрофизиологией, наукой о человеческом мозге и его нервной системе. Известно, что наш мозг содержит порядка 1011 нейронов и имеет порядка 1015 связей между нейронами. Это очень большие числа. Для сравнения, такое же количество звезд в нашей галактике «Млечный Путь». Наличие такого количества взаимосвязей определяет высокий уровень параллелизма в процессах обработки информации и высокую скорость реакции (нахождения решения) нашего мозга. Мозг человека – сложная вычислительная система, состоящая из нейронов различного типа (по форме и функциям). Одна из базовых особенностей нашего мозга является – способность к обучению. Моделирование этой способности является также одной из основных целей в исследованиях по разработке теории (моделей) ИНС.

История ИНС исследований восходит к работам McCuloch и Pitts (1943), Hebb (1949), Rosenblatt (1958,1961), Rochester (1956), Widrow (1960), и продолжена в работах Kohonen (1972), Hopfiled (1982), Cohen и Grossberg (1983) и др. Чтобы представить различные модели ИНС, рассмотрим вначале общую схему работы биологического нейрона.