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

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

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

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

Цля кодирования НС при помощи дерева необходимо определить терминальное Т и функциональное F множества.

При выборе терминального и функционального множеств нужно помнить следующее:

-любое дерево, составленное из элементов этих множеств, должно представлять собой некоторое решение из поискового пространства;

- набор терминального и функционального множеств должен позволять кодировать любое решение из поискового пространства.

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

Эти требования направлены на обеспечение более гибкого поиска структуры НС.

Цопустим, что терминальное множество Т состоит из частей (блоков), из которых (по предположению исследователя) должна состоять нейронная сеть. Это могут быть нейроны различных видов (в том числе входные), нейроны, уже объединенные в некоторые блоки (являющиеся частью слоя) и т. п. Функциональное множество состоит из элементов, показывающих, каким образом соотносятся между собой элементы из множества Т.

Поясним сказанное на примере. Пусть имеются терминальное и функциональное множества: Т= {$/Ти12, $Пи34, s!2, sZ3}, F= {+, >}, где sU2 - блок, состоящий из первого и второго входных нейронов; $Ии34 - блок, состоящий из третьего и четвертого входных нейронов; sl2 - блок, состоящий из двух нейронов с некоторыми активационными функциями 51 и 52; $13 - блок, состоящий из трех нейронов с функциями активации 53, 54 и 55; знак + означает соединение в один слой, знак > -установление связей между слоями. Тогда дерево (рис. 1), соответствует нейронной сети (рис. 2).

Рис. 1. Пример дерева, кодирующего НС

Функции пригодности также могут быть различными. Например, функция пригодности может быть равна обратной величине ошибке НС после некоторого наперед заданного количества итераций настройки весовых коэффициентов. Это может быть также число итераций настройки весовых коэффициентов, необходимых для получения некоторого заданного уровня ошибки НС. Могут быть и другие варианты оценки пригодности в зависимости от задачи, решаемой НС.

Рис. 2. НС, соответствующая бинарному дереву (см. рис. 1)

Построение базы правил нечеткой системы управления. База правил ставит в соответствие набору значений входных параметров значение выходных параметров некоторой системы. Например, пусть существует некоторая система, описывающаяся двумя входными параметрами и одним выходным параметрами:А~ {х1, х2, хЗ}, 7= {у1,у2,уЗ} - вход, U= {и1, и2, иЗ} - выход. Тогда БП может иметь такой вид:

if (х1&у1) then и 1 else if (х1&у2) then и1 else if (х1&уЗ) then и1 else if (х2&у1) then и2 else if (х2&у2) then и1 else if (х2&уЗ) then иЗ else if (хЗ&у1) then и2 else if (хЗ&у2) then и 1 else if (хЗ&уЗ) then иЗ.

Данная БП является полной, т. е. в ней перечислены все возможные комбинации входных параметров, и им в соответствие ставится значение выходного параметра. Такие БП, как правило, очень объемны и представляют собой по сути модель черного ящика. На практике чаще встречаются упрощенные БП. Например, следующая БП эквивалентна исходной, однако содержит меньше правил и более понятна человеку (эксперту):

if (х1) then и1 else if (у 2) then и1 else if (у1) then и2 else if (уЗ) then иЗ.

Генетическое программирование производит не только численную адаптацию (как генетический алгоритм), но и структурную, и позволяет создать упрощенные БП.

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

Выбор терминального множества в данном случае определяется однозначно - это значение выходных параметров и их комбинации. В нашем случае терминальное множество будет Т= {и1, и2, иЗ}.

Выбор функционального множества, напротив, может решаться различными способами. Функциональный элемент делит по какому-либо правилу вектор входных параметров на два вектора (если для кодирования используются бинарные деревья). Для кодирования приведенной выше (упрощенной) БП достаточно следующего функционального множества: F = {%А, % Г). Оператор %Х делит вектор значений параметра X пополам (если количество элементов четное) или с перевесом в один элемент (если количество элементов нечетное). Аналогично работает оператор %Г(рис. З).

Функция пригодности выражает количественно, насколько одно решение предпочтительнее другого. Выбор конкретной функции пригодности зависит от задачи.

Рассмотрим собственно процедуру ГП.

Общая схема ГП. Данная схема не является исчерпывающей и приводится здесь, чтобы создать общее представление о генетическом программировании. Подробнее познакомиться с данным методом можно в [1; 2].

Шаг 1. Создание начальной популяции. Случайным образом генерируем набор деревьев, представляющих некоторые решения.

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

Шаг 3. Селективный отбор. Отбираем пары родителей для скрещивания. Родитель выбирается случайно таким образом, чтобы индивиды с большей пригодностью отбирались с большей вероятностью. Пример селективного отбора - пропорциональная селекция, в которой отбор организован таким образом, чтобы вероятность выбора индивида в качестве родителя была пропорциональна его пригодности [1].

Шаг 4. Скрещивание. Выбранные пары родителей обмениваются своими поддеревьями. В итоге получается пара потомков. В традиционной схеме ГП только один потомок переходит в следующую популяцию. Потомка можно выбрать случайно либо по его пригодности.

Шаг 5. Мутация. Листья дерева выбираются с некоторой вероятностью (как правило, малой) и изменяются.

Шаг 6. Проверка условия останова. Если условие выполняется, то выбираем лучшего индивида и представляем его как решение, если иначе, то переходим на шаг 2.

Для тестирования предлагаемых подходов были реализованы программные системы PGPNN и библиотека PGPKlass. Последняя вошла в программную систему, описанную в [З]. Данная программа прошла государственную экспертизу и зарегистрирована в отраслевом фонде алгоритмов и программ [4].

Рассмотрим применение данного подхода при решении практических задач.

Прогнозирование технического состояния турбины по показаниям вибрационных датчиков. Задача имеет 11 входов и 12 выходов. Необходимо построить нейросетевую модель, прогнозирующую состояние турбины. Из основной выборки объемом 1 000 элементов случайным образом взяли 10 % измерений и поместили в тестовую выборку. Нейронная сеть создавалась по оставшейся выборке (900 элементов) и проверялась на тестовой выборке. Ошибка НС вычислялась по формуле

N

E = 17 а Е ( X i - X i )² , (1) N = 1

где N- количество примеров в выборке; х - i-й прогноз нейронной сети; х * - i-е реальное значение.

Получены следующие результаты моделирования. У автоматически сгенерированных нейронных сетей наибольшая, средняя и наименьшая ошибки по всем выходам на обучающей выборке составили 0,035,0,09 и 0,001 соответственно. Ошибки на контрольной выборке составили 0,084,0,027 и 0,005 соответственно. Нейронные сети имеют простой вид и могут быть визуально проанализированы специалистами.

Прогнозирования состояния пациентов после инфаркта. Задача состоит в том, что по имеющимся данным пациента определить, проживет ли данный больной, перенесший инфаркт миокарда, по крайней мере год или нет. Задача имеет 9 входов и 1 выход. База, по которой обучается нейронная сеть, состоит из 132 примеров. Из общей выборки также было удалено 10 % примеров для создания контрольной выборки. Автоматически полученная нейронная сеть безошибочно распознала все примеры из тестовой и обучающей выборки. Такой результат, скорее всего, может быть объяснен тем, что исходная выборка была заранее адаптирована для нейросетевого моделирования.

Прогнозирование деградации электрических характеристик солнечных батарей космических аппаратов. Необходимо по имеющимся результатам измерения параметров солнечных батарей (БС) в полете космического аппарата (КА): параметров секций БС3 и БС4 на КА «Эк-спресс-А» № 2 - и результатам измерения параметров БС с КА «Экспресс-А» и «Goes» в годы активного Солнца (25 событий за период с 4 апреля 2000 г. по 22 ноября 2001 г., от экстремально мощных 14 июля 2000 г и 22 ноября 2001 г. до обычных 16 октября 2000 г.) построить нейросетевую модель, прогнозирующую деградацию электрических характеристик БС.

Нейросетевая модель настраивается на определение электрических характеристик солнечных батарей в зависимости от следующих факторов (входной вектор):

• -    интегральный флюенс протонов с различными энергиями (от 1 до 100 МэВ);

• -    интегральный флюенс электронов с различными энергиями (от 0,6 до 2 МэВ);

• -    ресурс - параметр, который задан как количество дней с момента контакта отделения КА, характеризует повреждения от метеоритных тел и от ультрафиолетового излучения;

• -    коэффициент освещенности КА - величина, характеризующая степень освещенности аппарата, зависит от

взаимного положения КА, Земли и Луны и имеет принципиальное значение, так как некоторые выходные характеристики ФП, в частности сила тока короткого замыкания, зависят от освещенности БС.

Данным входам в соответствие ставятся напряжение холостого хода U и сила тока I БС (вектор значений х.х                          к .з или выходной).

Таким образом, нейросетевая модель строится на основании телеметрической информации (полетных данных). В нейронной сети формируются внутренние закономерности, позволяющие предсказывать значения выходных параметров для пробного набора внешних воздействий. Далее выполняется прогноз параметров БС на конец ресурса для заданных в техническом задании характеристик ИИКП.

Для обучения нейронной сети из выборки объемом 220 записей случайным образом было удалено 9 % примеров (20 записей). На оставшейся выборке было получено четыре нейронных сети для прогнозирования: 1_БС3 (силы тока БС3);1_БС4 (силы тока БС4); ихх_БС3 (напряжения холостого хода БС3); ихх_БС4 (напряжения холостого хода БС4). Результаты тестирования приведены в таблице. Ошибка нейронной сети рассчитывалась по формуле (1).

Результаты моделирования

Вых^д	Выборка	Ошибка
/_ БС3	Обучают ая	0,002 10
	Тесте рая	0,005 37
/_ БС4	Обучают ая	0,000 935
	Тестерая	0,003 76
Г хх БСЗ	Обучают ая	0,000 3 67
	ТестеРая	0,001 66
№х_БС4	Обучают ая	0,000 229
	ТестеРая	0,001 25

Полученные нейронные сети также имеют достаточно простой вид и могут анализироваться специалистами.

Автоматическое формирование базы правил нечеткого контроллера. Оценка подхода производилась на задаче автоматического проектирования нечеткого контроллера для управления системой «тележка - перевернутый маятник» (рис. 4). Состояние системы в каждый момент времени характеризуется значением четырех ее параметров:

• -    положения системы хЦ);

• -    линейной скорости системы - x'(t);

• -    угла отклонения маятника - О (/);

• -    угловой скорости маятника - (-)'(/).

Система может перемещаться вдоль одной оси в интервале [-100; 100]. Маятник может совершать колебания в интервале [-90; 90] ° . Если значения положения системы или угла маятника превышают указанные интервалы, то считается, что система управления потерпела неудачу.

Необходимо построить нечеткий логический контроллер, управляющий системой «тележка - перевернутый маятник». Целью управления является приведение системы в состояние равновесия, которое характеризуется нулевым значением отклонения маятника от вертикальной оси и нулевым значением позиции тележки, за счет передвижения системы вдоль оси А, при любом начальном допустимом положении тележки и маятника.

Оценка эффективности работы БП для задачи «тележка - перевернутый маятник» производилась по следую- щему критерию, который необходимо было минимизи ровать в процессе оптимизации:

f ( 5 ) = F + [ A ] + [ B ] + [ C ] ^ min ,

F =

0,5 • a

. S ,

,

N

A = £ Ki • i=1

P i Cur

P ’ i max

• 200,    if S_q <  a , 0, otherwise

• 1    (             S q               ^s q A

c = - 0,3 • K 1 • £ p i + K 3 • £ P 3 i , a                  i = 1                 i = 1

v                           / где а - максимально допустимое число шагов (тактов) работы системы при тестировании; Sq - число шагов, сделанных системой до момента прекращения тестиро вания; К - уровень значимости i-го параметра системы; РС - текущее значение i-го параметра системы; Р. шах - максимальное реально достигаемое значение i-го параметра системы; N- количество параметров системы (в нашем случае N= 4).

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

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

• -    [А] - когда почти все индивиды начнут более или менее хорошо «ловить» маятник, их пригодность будет уже определяться тем, насколько хорошо они «ловят» (Fустремится к 0,5, а [А] начнет доминировать над F, определяя качество);

• -    [5] - если индивид не смог продержаться заданное

число тактов при тестировании, т. е. потерял управление над системой за число шагов, меньшее чем а, то он считается не способным решить данную тестовую задачу за что и получает штрафные баллы;

• -    [С] - данный критерий обеспечивает быстроту и плавность управления системой, элиминируя индивидов, совершающих большие колебательные движения и находящихся далеко от нулевого положения (в нашей системе

Р1 - позиция системы, Р3 - угол отклонения мятника от вертикали).

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

1 fitness = 1— f ( ).

Результат применения ГП для построения БП. Четыре входных параметра и управляющее воздействие были представлены в виде нечетких множеств триангулярного типа. Использовался вывод в логике Мамдани.

В результате работы программы была получена следующая база, состоящая из 8 правил:

• 1)    IF (позиция отрицательная) и (угловая скорость отрицательная большая) THEN сила положительная малая;

• 2)    ELSE IF (позиция отрицательная) и (угловая скорость отрицательная малая) THEN сила положительная большая;

• 3)    ELSE IF (позиция неотрицательная) и (угловая скорость отрицательная) THEN сила отрицательная большая;

• 4)    ELSE IF (угол отрицательный) и (угловая скорость неотрицательная) THEN сила нулевая;

• 5)    ELSE IF (скорость отрицательная) и (угол положительный) и (угловая скорость нулевая) THEN сила нулевая;

• 6)    ELSE IF (скорость отрицательная) и угол (положительный) и (угловая скорость положительна) THEN сила положительная большая;

• 7)    ELSE IF (позиция отрицательная) и (скорость неотрицательная) и (угол неотрицательный) и (угловая скорость неотрицательная) THEN сила положительная большая;

• 8)    ELSE IF (позиция положительная) и (скорость неотрицательная) и (угол неотрицательный) и (угловая скорость неотрицательная) THEN сила положительная большая.

Здесь приняты следующие обозначения: позиция -позиция тележки; скорость - скорость тележки; угол -угол отклонения маятника; угловая скорость - угловая скорость маятника.

Рассмотрим данную БП.

Правило 1 говорит о том, что если позиция отрицательная и угловая скорость отрицательная большая, то сила положительная малая. На первый взгляд, данное воздействие помогает упасть маятнику. Однако как только позиция тележки станет положительной, то в силу вступает правило 3, которое останавливает тележку рывком.

Правило 2 похоже на правило 1, только благодаря малой угловой скорости система управления прилагает большую положительную силу, что быстрее приводит систему к правилу 3.

Правила 4 и 5 говорят о том, что ничего делать не нужно, если система находится в этих состояниях. В правиле 4 маятник либо движется в желаемое состояние, либо покоится, поэтому можно ничего не предпринимать. В правиле 5, казалось бы, необходимо приложить положительную силу, однако это правило призывает не прикладывать силу. Дело в том, что в ситуации, когда у тележки скорость положительная, а угол отрицательный, вряд ли угловая скорость может быть равна нулю, поэтому данное правило либо срабатывает редко, либо не срабатывает вовсе.

Правило 6 напоминает правило 5, только угловая скорость положительна, и в такой ситуации система управления принимает правильное решение: приложить большую положительную силу.

Правила 7 и 8 заставляют маятник рывком двигаться к нулевому положению.

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

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

Работа выполнена при поддержке ФЦНТП по проек-там№2006-РИ-16.0/001 и2006-РИ-19.0/001/377.