close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Математика, механика, информатика
УДК 004.94:519.254:004.8.032.26:004.88
Л. В. Липинский, Е. С. Семенкин
ПРИМЕНЕНИЕ АЛГОРИТМА ГЕНЕТИЧЕСКОГО ПРОГРАММИРОВАНИЯ
В ЗАДАЧАХ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ
ИНТЕЛЛЕКТУАЛЬНЫХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
Описано применение метода генетического программирования в задачах автоматизированного проектирования нейросетевых моделей и нечетких котроллеров. Приведены примеры решения конкретных практических
задач из различных областей принятия решений.
Интеллектуальные информационные технологии широко и успешно используются для решения различных
практических задач. Однако их проектирование является
трудоемким процессом, требующим больших временных затрат и материальных вложений. Это сдерживает
массовое использование интеллектуальных информационных технологий специалистами конкретных прикладных областей, не являющихся экспертами в нейросетевом моделировании или разработке нечетких систем.
Исследователь, решивший использовать для решения той
или иной задачи технологии искусственных нейронных
сетей (НС), сталкивается с вопросом об архитектуре нейронной сети. В большинстве случаев основной метод
подбора структуры НС – метод проб и ошибок, который,
разумеется, не может гарантировать оптимального решения. Проектирование базы правил (БП), являющейся
основой экспертных систем и систем управления на нечеткой логике, является сложным творческим процессом,
требующим больших затрат на взаимное обучение специалистов предметной области и инженеров. В обоих
случаях интеллектуальные и временные ресурсы разработчиков используются непродуктивно.
Применение генетического программирования (ГП)
позволяет существенно упростить и ускорить процесс
разработки интеллектуальных технологий за счет его автоматизации. Генетическое программирование является
эффективным инструментом для поиска эффективных
решений в пространстве нелинейных иерархических
структур (например, деревьев или графов). Представив
интеллектуальные технологии в виде таких структур, мы
получим мощное средство по генерированию эффективных решений, что в свою очередь высвобождает интеллектуальные ресурсы разработчиков для решения подлинно творческих задач.
Выбор структуры нейронной сети методом генетического программирования. Для использования ГП необходимо решить две задачи: кодирование нейронной
сети в виде дерева (в общем случае дерево может быть
n-нарным, но обычно выбирают бинарное) и выбор функции пригодности, позволяющей отбирать более эффективные структуры.
Для кодирования НС при помощи дерева необходимо
определить терминальное T и функциональное F множества.
При выборе терминального и функционального множеств нужно помнить следующее:
– любое дерево, составленное из элементов этих множеств, должно представлять собой некоторое решение из
поискового пространства;
– набор терминального и функционального множеств
должен позволять кодировать любое решение из поискового пространства.
Кроме того, выбранный способ кодирования должен
позволять представлять сети с межслойными связями, а
также сети с произвольными связями между нейронами
различных слоев, а не только с послойной организацией
нейросети; создавать нейросети с нейронами с различными активационными функциями.
Эти требования направлены на обеспечение более
гибкого поиска структуры НС.
Допустим, что терминальное множество Т состоит из
частей (блоков), из которых (по предположению исследователя) должна состоять нейронная сеть. Это могут быть
нейроны различных видов (в том числе входные), нейроны, уже объединенные в некоторые блоки (являющиеся
частью слоя) и т. п. Функциональное множество состоит
из элементов, показывающих, каким образом соотносятся между собой элементы из множества T.
Поясним сказанное на примере. Пусть имеются терминальное и функциональное множества: T = {slIn12,
slIn34, sl2, sl3}, F = {+, >}, где sl12 – блок, состоящий из
первого и второго входных нейронов; slIn34 – блок, состоящий из третьего и четвертого входных нейронов;
sl2 – блок, состоящий из двух нейронов с некоторыми
активационными функциями S1 и S2; sl3 – блок, состоящий из трех нейронов с функциями активации S3, S4 и
S5; знак + означает соединение в один слой, знак > – установление связей между слоями. Тогда дерево (рис. 1), соответствует нейронной сети (рис. 2).
?
>
>
Sl3
+
SlIn12
+
SlIn34
Sl2
>
SlIn34
Sl2
Рис. 1. Пример дерева, кодирующего НС
Функции пригодности также могут быть различными. Например, функция пригодности может быть равна
обратной величине ошибке НС после некоторого наперед заданного количества итераций настройки весовых
коэффициентов. Это может быть также число итераций
22
Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева
настройки весовых коэффициентов, необходимых для
получения некоторого заданного уровня ошибки НС.
Могут быть и другие варианты оценки пригодности в зависимости от задачи, решаемой НС.
1
2
S3
S4
{x1, x2, x3}, {y1, y2, y3}
%X
S1
S2
S5
3
элемент (если количество элементов нечетное). Аналогично работает оператор %Y (рис. 3).
{x2, x3}, {y1, y2, y3}
{x1}, {y1, y2, y3}
u1
?
%Y
{x2, x3}, {y2, y3}
{x2, x3}, {y1}
S1
u2
4
S2
%Y
{x2, x3}, {y2}
u1
Рис. 2. НС, соответствующая бинарному дереву (см. рис. 1)
Построение базы правил нечеткой системы управления. База правил ставит в соответствие набору значений
входных параметров значение выходных параметров некоторой системы. Например, пусть существует некоторая система, описывающаяся двумя входными параметрами и одним выходным параметрами: X = {x1, x2, x3},
Y = {y1, y2, y3} – вход, U = {u1, u2, u3} – выход. Тогда БП
может иметь такой вид:
if (x1&y1) then u1 else if (x1&y2) then u1 else if (x1&y3)
then u1 else if (x2&y1) then u2 else if (x2&y2) then u1
else if (x2&y3) then u3 else if (x3&y1) then u2 else if
(x3&y2) then u1 else if (x3&y3) then u3.
Данная БП является полной, т. е. в ней перечислены
все возможные комбинации входных параметров, и им в
соответствие ставится значение выходного параметра.
Такие БП, как правило, очень объемны и представляют
собой по сути модель черного ящика. На практике чаще
встречаются упрощенные БП. Например, следующая БП
эквивалентна исходной, однако содержит меньше правил
и более понятна человеку (эксперту):
if (x1) then u1 else if (y2) then u1 else if (y1) then u2 else
if (y3) then u3.
Генетическое программирование производит не
только численную адаптацию (как генетический алгоритм), но и структурную, и позволяет создать упрощенные БП.
Для решения данной задачи методом ГП необходимо
решить следующие задачи: выбор функционального множества, выбор терминального множества, построение
функции пригодности.
Выбор терминального множества в данном случае
определяется однозначно – это значение выходных параметров и их комбинации. В нашем случае терминальное
множество будет T = {u1, u2, u3}.
Выбор функционального множества, напротив, может решаться различными способами. Функциональный
элемент делит по какому-либо правилу вектор входных
параметров на два вектора (если для кодирования используются бинарные деревья). Для кодирования приведенной выше (упрощенной) БП достаточно следующего
функционального множества: F = {%X, %Y}. Оператор
%X делит вектор значений параметра Х пополам (если
количество элементов четное) или с перевесом в один
{x2, x3}, {y3}
u3
Рис. 3. Представление упрощенной БП в виде дерева
Функция пригодности выражает количественно, насколько одно решение предпочтительнее другого. Выбор
конкретной функции пригодности зависит от задачи.
Рассмотрим собственно процедуру ГП.
Общая схема ГП. Данная схема не является исчерпывающей и приводится здесь, чтобы создать общее представление о генетическом программировании. Подробнее познакомиться с данным методом можно в [1; 2].
Шаг 1. Создание начальной популяции. Случайным
образом генерируем набор деревьев, представляющих
некоторые решения.
Шаг 2. Оценивание текущей популяции. В соответствии с выбранной функцией пригодности каждому решению в популяции ставим в соответствие число, количественно характеризующее данное решение.
Шаг 3. Селективный отбор. Отбираем пары родителей для скрещивания. Родитель выбирается случайно таким образом, чтобы индивиды с большей пригодностью
отбирались с большей вероятностью. Пример селективного отбора – пропорциональная селекция, в которой
отбор организован таким образом, чтобы вероятность
выбора индивида в качестве родителя была пропорциональна его пригодности [1].
Шаг 4. Скрещивание. Выбранные пары родителей
обмениваются своими поддеревьями. В итоге получается пара потомков. В традиционной схеме ГП только один
потомок переходит в следующую популяцию. Потомка
можно выбрать случайно либо по его пригодности.
Шаг 5. Мутация. Листья дерева выбираются с некоторой вероятностью (как правило, малой) и изменяются.
Шаг 6. Проверка условия останова. Если условие
выполняется, то выбираем лучшего индивида и представляем его как решение, если иначе, то переходим на
шаг 2.
Для тестирования предлагаемых подходов были реализованы программные системы PGPNN и библиотека
PGPKlass. Последняя вошла в программную систему,
описанную в [3]. Данная программа прошла государственную экспертизу и зарегистрирована в отраслевом
фонде алгоритмов и программ [4].
Рассмотрим применение данного подхода при решении практических задач.
23
Математика, механика, информатика
Прогнозирование технического состояния турбины по
показаниям вибрационных датчиков. Задача имеет
11 входов и 12 выходов. Необходимо построить нейросетевую модель, прогнозирующую состояние турбины. Из
основной выборки объемом 1 000 элементов случайным
образом взяли 10 % измерений и поместили в тестовую
выборку. Нейронная сеть создавалась по оставшейся
выборке (900 элементов) и проверялась на тестовой выборке. Ошибка НС вычислялась по формуле
взаимного положения КА, Земли и Луны и имеет принципиальное значение, так как некоторые выходные характеристики ФП, в частности сила тока короткого замыкания, зависят от освещенности БС.
Данным входам в соответствие ставятся напряжение
холостого хода Uх.х и сила тока Iк .з БС (вектор значений
или выходной).
Таким образом, нейросетевая модель строится на основании телеметрической информации (полетных данных).
В нейронной сети формируются внутренние закономерности, позволяющие предсказывать значения выходных параметров для пробного набора внешних воздействий. Далее
выполняется прогноз параметров БС на конец ресурса для
заданных в техническом задании характеристик ИИКП.
Для обучения нейронной сети из выборки объемом
220 записей случайным образом было удалено 9 % примеров (20 записей). На оставшейся выборке было получено четыре нейронных сети для прогнозирования: I_БС3
(силы тока БС3); I_БС4 (силы тока БС4); Uхх_БС3 (напряжения холостого хода БС3); Uхх_БС4 (напряжения холостого
хода БС4). Результаты тестирования приведены в таблице.
Ошибка нейронной сети рассчитывалась по формуле (1).
1 N
(1)
? ( xi ? xi* )2 ,
N i =1
где N – количество примеров в выборке; xi – i-й прогноз
нейронной сети; xi* – 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 МэВ);
– ресурс – параметр, который задан как количество
дней с момента контакта отделения КА, характеризует
повреждения от метеоритных тел и от ультрафиолетового излучения;
– коэффициент освещенности КА – величина, характеризующая степень освещенности аппарата, зависит от
E=
Результаты моделирования
Выход
I_БС3
I_БС4
Uхх_БС3
Uхх_БС4
Выборка
Обучающ ая
Тестовая
Обучающ ая
Тестовая
Обучающ ая
Тестовая
Обучающ ая
Тестовая
Ошибка
0,002 10
0,005 37
0,000 935
0,003 76
0,000 367
0,001 66
0,000 229
0,001 25
Полученные нейронные сети также имеют достаточно простой вид и могут анализироваться специалистами.
Автоматическое формирование базы правил нечеткого контроллера. Оценка подхода производилась на задаче
автоматического проектирования нечеткого контроллера
для управления системой «тележка – перевернутый маятник» (рис. 4). Состояние системы в каждый момент времени характеризуется значением четырех ее параметров:
– положения системы x(t);
– линейной скорости системы – x?(t);
– угла отклонения маятника – ?(t);
– угловой скорости маятника – ? ?(t).
Система может перемещаться вдоль одной оси в интервале [–100; 100]. Маятник может совершать колебания
в интервале [–90; 90]°. Если значения положения системы
или угла маятника превышают указанные интервалы, то
считается, что система управления потерпела неудачу.
Необходимо построить нечеткий логический контроллер, управляющий системой «тележка – перевернутый
маятник». Целью управления является приведение системы в состояние равновесия, которое характеризуется
нулевым значением отклонения маятника от вертикальной оси и нулевым значением позиции тележки, за счет
передвижения системы вдоль оси X, при любом начальном допустимом положении тележки и маятника.
Оценка эффективности работы БП для задачи «тележка – перевернутый маятник» производилась по следую24
Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева
щему критерию, который необходимо было минимизировать в процессе оптимизации:
f ( s ) = F + [ A] + [ B ] + [C ] ? min ,
БП
? 0,5 ? a ?
F =?
?,
? Sq ?
?
?
N
Pi Cur
A = ? Ki ?
,
Pi max
i =1
P1 – позиция системы, P3 – угол отклонения мятника от
вертикали).
Сам критерий f ( s ) не может быть пригодностью, так
как меньшее значение этого критерия соответствует лучшему индивиду, а функция пригодности должна максимизироваться. Поэтому, чтобы получить функцию пригодности, необходимо преобразовать данный критерий
следующим образом:
1
fitness =
.
1 + f (s)
Результат применения ГП для построения БП. Четыре входных параметра и управляющее воздействие были
представлены в виде нечетких множеств триангулярного
типа. Использовался вывод в логике Мамдани.
В результате работы программы была получена следующая база, состоящая из 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, которое останавливает тележку рывком.
??200, if S q < a,
B=?
??0, otherwise
Sq
Sq
?
1?
0,3
K
P
K
?
?
+
?
??
1 ? 1i
3 ? P3i ?
?,
a?
i =1
i =1
?
где a – максимально допустимое число шагов (тактов)
работы системы при тестировании; Sq – число шагов,
сделанных системой до момента прекращения тестирования; Ki – уровень значимости i-го параметра системы;
P iCur – текущее значение i-го параметра системы;
Pi max – максимальное реально достигаемое значение
i-го параметра системы; N – количество параметров системы (в нашем случае N = 4).
Функции, указанные в квадратных скобках, могут быть
включены в общий критерий по желанию пользователя
(включение / исключение соответствующей функции
производится в настройках алгоритма оптимизации).
Данная функция качества позволяет на первых этапах
работы ГА производить отбор решений, которые достаточно продолжительное время пытаются привести систему в равновесное состояние (доминирование слагаемого ошибки F). Включение же дополнительных критериев дает следующие преимущества:
– [A] – когда почти все индивиды начнут более или
менее хорошо «ловить» маятник, их пригодность будет
уже определяться тем, насколько хорошо они «ловят»
(F устремится к 0,5, а [A] начнет доминировать над F, определяя качество);
– [B] – если индивид не смог продержаться заданное
число тактов при тестировании, т. е. потерял управление
над системой за число шагов, меньшее чем a, то он считается не способным решить данную тестовую задачу, за
что и получает штрафные баллы;
– [C] – данный критерий обеспечивает быстроту и
плавность управления системой, элиминируя индивидов,
совершающих большие колебательные движения и находящихся далеко от нулевого положения (в нашей системе
C=
Рис. 4. Система «тележка – перевернутый маятник»
25
Математика, механика, информатика
Правило 2 похоже на правило 1, только благодаря малой угловой скорости система управления прилагает большую положительную силу, что быстрее приводит систему к правилу 3.
Правила 4 и 5 говорят о том, что ничего делать не нужно, если система находится в этих состояниях. В правиле 4
маятник либо движется в желаемое состояние, либо покоится, поэтому можно ничего не предпринимать. В правиле 5, казалось бы, необходимо приложить положительную
силу, однако это правило призывает не прикладывать силу.
Дело в том, что в ситуации, когда у тележки скорость положительная, а угол отрицательный, вряд ли угловая скорость
может быть равна нулю, поэтому данное правило либо
срабатывает редко, либо не срабатывает вовсе.
Правило 6 напоминает правило 5, только угловая скорость положительна, и в такой ситуации система управления принимает правильное решение: приложить большую положительную силу.
Правила 7 и 8 заставляют маятник рывком двигаться к
нулевому положению.
Построенная база правил не может быть признана
совершенной, однако управление системой она выполняет эффективно. Кроме того, база может быть подвергнута анализу и корректировке специалистами.
ляющим легко получать конкурентоспособный результат, сравнимый с результатом специалистов, не заменяя
последних, а освобождая их для более продуктивной творческой работы. Применение этого подхода позволит существенно сократить затраты на разработку интеллектуальных технологий.
Работа выполнена при поддержке ФЦНТП по проектам № 2006-РИ- 16.0/001 и 2006-РИ-19.0/001/377.
Библиографический список
1. Koza, J. R. Genetic programming tutorial [Электронный ресурс] / R. J. Koza. Электрон. дан. Режим доступа:
http://www.genetic-programming.com/gpanimatedtutorial.html. Загл. с экрана.
2. Koza, J. R. Hierarchical genetic algorithms operating
on populations of computer programs / R. J. Koza // Proc. of
the 11th Intern. Joint Conf. on Artificial Intelligence. San
Mateo : Morgan Kaufman, 1989.
3. Липинский Л. В. Подходы к формированию базы
правил для нечетких систем управления / Л. В. Липинский,
В. А. Малько // Вестн. Сиб. гос. аэрокосмич. ун-та им. акад.
М. Ф. Решетнева / под ред. проф. Г. П. Белякова ; Сиб. гос.
аэрокосмич. ун-т. Вып. 5. Красноярск, 2004. С. 83–90.
4. Интеллектуальные технологии автоматизации проектирования системы управления на нечеткой логике:
прогр. для ЭВМ / Л. В. Липинский, В. А. Малько,
Е. С. Семенкин. М., 2006. Зарег. в ВНТИЦ, № 50200600369.
Предложенный в данной статье подход является эффективным средством автоматического проектирования
интеллектуальных информационных технологий, позво-
L. V. Lipinsky, E. S. Semenkin
APPLICATION OF GENETIC PROGRAMMING ALGORITHM IN AUTOMATED
DESIGN OF INTELLECTUAL INFORMATION TECHNOLOGIES
Application of genetic programming approach in automated design of artificial neural networks and fuzzy logic
controllers is described. Examples of real world problems solving from wide area of decision support are given.
УДК 539.3
А. В. Лопатин, И. В. Макаров, М. А. Рутковская
ОПРЕДЕЛЕНИЕ МАССОВОЙ ЭНЕРГОЕМКОСТИ МАХОВИКА
ГИПЕРБОЛИЧЕСКОГО ПРОФИЛЯ
Рассмотрена задача определения величины массовой энергоемкости маховика, профиль которого имеет
форму гиперболы. Получено аналитическое решение уравнений, описывающих напряженное состояние маховика
при вращении. Выполнен анализ влияния на коэффициент формы маховика геометрических параметров диска.
Приведено сравнение аналитических решений с решениями, полученными методом конечных элементов.
Маховики принадлежат к числу древнейших механизмов, способных накапливать энергию. В настоящее время существует множество маховичных систем аккумулирования энергии, используемых в различных областях
техники [1]. В частности, маховики нашли применение на
космических аппаратах в качестве накопителей энергии и
устройств стабилизации.
Качество накопителя энергии оценивают величиной
массовой энергоемкости, которая находится как отношение энергии, запасаемой на режиме предельно возможной угловой скорости, к массе маховика. Определение
максимальной угловой скорости связано с решением задачи о распределении напряжений, возникающих во вращающемся маховике, от центробежных сил. Наибольшее
26
1/--страниц
Пожаловаться на содержимое документа