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

MULTIOBJECTIVE OPTIMIZATION OF NEURAL NETWORK MODELS STRUCTURE WITH PARALLEL GENETIC ALGORITHMS

An evolutionary approach for neural network models construction is discussed. The problem statement of neural network structure multiobjective unconstrained optimization isformulated. The multiobjective parallel genetic algorithms are used to solve assigned task.

Е. С. Семенкин, М. Е. Семенкина1

ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА С МОДИФИЦИРОВАННЫМ ОПЕРАТОРОМ РАВНОМЕРНОЙ РЕКОМБИНАЦИИ ПРИ АВТОМАТИЗИРОВАННОМ ФОРМИРОВАНИИ ИНТЕЛЛЕКТУАЛЬНЫХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

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

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

При моделировании сложных систем и процессов часто используются так называемые интеллектуальные информационные технологии (ПИТ) - системы на нечеткой логике (НЛС) [1] - как метод формирования причинно-следственных связей, искусственные нейронные сети (ИНС) [2] как метод аппроксимации или классификации, генетическое программирование (ГП) [3] как метод автоматического генерирования математических выражений.

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

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

В данной работе при проведении экспериментов использовались программные системы автоматизации проектирования ПИТ, разработанные в Сибирском государственном аэрокосмическом университете имени академика М. Ф. Решетнева, а также программная система, реализующая модифицированный ГА, специально разработанные авторами.

Программные системы автоматизированного проектирования интеллектуальных информационных технологий. В работе использовалась программная система [5], позволяющая при помощи алгоритма генетического программирования строить по результатам наблюдений математические модели в явном аналитическом виде и производить настройку коэффициентов символьного выражения. Перед реализацией алгоритма задаются терминальное и функциональное множества. Функциональное множество F может состоять из функций, процедур. Терминальное множество Тсостоит из набора переменных и констант Алгоритм работает с множеством индивидов, представляющих собой деревья, в вершинах которых находятся элементы функционального и терминального множеств. Существует несколько методов генерирования деревьев: полный метод, метод выращивания, комбинированный; несколько видов скрещивания: одноточечное, многоточечное и другие; селекции: пропорциональная, ранговая, турнирная; и мутации: низкая, средняя, высокая. Их выбор определяет эффективность работы системы.

Использованная в работе программная система [6] позволяет автоматически строить нейронную сеть и оптимизировать ее структуру и параметры. ГА применяется на обеих стадиях, поэтому для эффективной работы системы необходимо его настраивать дважды, так как настройки эффективных ГА выбора структуры и настройки весовых коэффициентов не обязаны совпадать.

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

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

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

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

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

Генетический алгоритм - это стохастическая оптимизационная процедура, имитирующая естественный эволюционный процесс [4]. Схематично процесс решения задачи можно представить в виде этапов:

• 1)    генерирование начальной популяции индивидов (инициализация);

• 2)    выращивание (восстановление индивида (фенотипа) по известному генотипу, перевод из двоичной системы в десятичную систему исчисления);

• 3)    определение значений целевой функции для каждого индивида:

• -    цикл 1 . Пока не будет выполнено условие остановки (найдено решение, исчерпаны ресурсы);

• -    цикл 2. Пока не сформированы все индивиды новой популяции;

• -    операция селекции (выбираются особи из текущей популяции и заносятся в популяцию родителей, из которых в свою очередь отбирается пара индивидов);

• -    операция скрещивания (отобранных селекцией индивидов);

• - операция мутации (потомка, полученного при скрещивании);

• -    окончание цикла 2;

• 4)    вычисление целевой функции для потомков новой популяции;

• 5)    определение наилучшего индивида;

• 6)    окончание цикла 1 .

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

Каждый из перечисленных выше методов имеет свои преимущества и недостатки, поэтому необходимо сравнить их по эффективности и выбрать лучший для дальнейшей работы с ним. Поэтому прежде чем проводить эксперименты с проектированием ИИТ, было выполнено исследование эффективности ГА на тестовых задачах оптимизации с дискретными структурами на примере решения диофантовых уравнений [8]. Для этого была разработана соответствующая программная система и выбран репрезентативный набор тестовых задач. Результаты экспериментов приведены в табл. 1.

Показателем эффективности ГА была выбрана его надежность, т. е. доля запусков с успешным решением задачи при тысячи прогонах. Всего были проведены эксперименты с 10 задачами, среди которых были диофантовы уравнения различных типов, а также системы диофантовых уравнений. В результате исследований было установлено следующее [8]: ГА намного превосходит полный перебор по быстродействию, при этом не уступает ему по надежности при правильном выборе настроек; турнирная селекция, высокая вероятность мутации и равномерное скрещивание являются наиболее эффективными выборами настроек ГА; ГА слабо чувствителен к росту размерности поискового пространства, что делает его перспективным в практических задачах; выбор наиболее эффективного варианта ГА для решаемой задачи требует ее многократного решения, что очень неэффективно в практических задачах.

Далее было выполнено сравнение эффективности ГА с его естественным конкурентом - мультистартом локального поиска (МЛС). Сравнение проводилось по надежности при равных затратах на поиск. Фрагменты результатов приведен в табл. 2.

Получен следующий вывод [9]: на двух простейших задачах 2, 3 (большое количество одинаковых локальных минимумов) МЛС незначительно превосходит ГА, на сложных задачах 4, 6 (большое количество различных локальных минимумов, слабо отличающихся от глобального) МЛС проигрывает даже худшему из ГА, на остальных задачах МЛС значительно проигрывает лучшему ГА, проигрывает среднему ГА и слегка превосходит худший ГА. Таким образом, при решении сложных задач лучше использовать ГА в расчете на то, что выбираемые (в худшем случае - наугад) его настройки не будут самыми плохими.

Таблица 1

Пример оценки надежности ГА при решении диофантовых уравнений

Т9п селекц99	Уровень мотац99	ГА с одноточечным скрещ9ван9ем				ГА с равномерным скрещ9ван9ем
		Кол9чество поколен9й -Кол9чество 9нд9в9дов				Кол9чество поколен9й -Кол9чество 9нд9в9дов
		20-50	50-20	10-100	100-10	20-50	50-20	10-100	100-10
Пропорц9о-нальная	Н9зкая	0,817	0,818	0,866	0,903	0,821	0,767	0,871	0,89
	Средняя	0,924	0,954	0,951	0,982	0,914	0,967	0,937	0,993
	Высокая	0,976	0,98	0,979	0,984	0,97	0,99	0,957	0,993
Торн9рная к = 3	Н9зкая	0,9	0,703	0,963	0,63	0,955	0,751	0,959	0,644
	Средняя	0,983	0,979	0,962	0,97	0,973	0,986	0,958	0,983
	Высокая	0,943	0,948	0,914	0,965	0,904	0,937	0,894	0,956
Торн9рная к = 5	Н9зкая	0,797	0,563	0,953	0,495	0,878	0,614	0,975	0,491
	Средняя	0,957	0,855	0,983	0,87	0,969	0,862	0,984	0,836
	Высокая	0,978	0,984	0,956	0,992	0,974	0,979	0,939	0,989
Торн9рная к = 8	Н9зкая	0,757	0,511	0,887	0,476	0,726	0,576	0,924	0,463
	Средняя	0,875	0,715	0,965	0,723	0,893	0,723	0,968	0,697
	Высокая	0,988	0,993	0,985	0,988	0,989	0,995	0,965	0,994
	Н9зкая	0,654	0,489	0,867	0,419	0,682	0,506	0,883	0,451
Торн9рная к= 10	Средняя	0,831	0,692	0,935	0,671	0,82	0,673	0,948	0,67
	Высокая	0,984	0,974	0,986	0,983	0,983	0,978	0,966	0,992

Перспективность ГА при решении сложных задач привела к идее усовершенствования его операторов.

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

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

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

Данная модификация ГА была реализована в виде программной системы, испытана на тестовых задачах и зарегистрирована во ВНТИЦ [10]. Фрагмент результатов сравнения эффективности различных модификаций оператора равномерного скрещивания приведен в табл. 3.

Основные результаты могут быть сформулированы следующим образом [11]: наибольшей эффективностью обладает алгоритм с семью родителями для одного потомка, вторым по эффективности (незначительно уступающим первому) является алгоритм с двумя родителями, остальные - значительно им уступают; наиболее эффективным оператором равномерного скрещивания является ранговое равномерное, вторым по эффективности является стандартное равновероятное, остальные значительно им уступают, хотя на ряде задач турнирное рав номерное скрещивание оказалось значительно лучше остальных вариантов (но значительно хуже на других задачах).

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

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

С помощью программной системы [7] генерировалась база знаний НЛС управления перевернутым маятником при фиксированной семантике лингвистических переменных. Устанавливались размер популяции в 100 индивидов, длительность работы - 100 поколений. Установки ГА выбирались в соответствии с полученными рекомендациями - ранговое равномерное скрещивание, турнирная селекция, высокая мутация.

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

После замены турнирной селекции на пропорциональную и скрещивания на одноточечное результат оказался (0,9; 62; 3,744 6), т. е. хуже по всем трем показателям эффективности. При других настройках также получаем ухудшение. Самый плохой результат - ранговая селекция, двухточечное скрещивание, слабая мутация -(0,1; 80; 2,288 4).

С помощью программной системы [6] генерировалась нейронная сеть, восстанавливающая зависимость у = sin(x) с добавленным шумом в 5 %. Установки ГА, оптимизирующего структуру ИНС, и ГА, настраивающего весовые коэффициенты ИНС, выбирались как прежде. Полученная после 30 поколений (50 мин счета) луч-

Таблица 2

Фрагмент таблицы результатов сравнения МЛС и ГА

Задача	Надежность МЛС	Надежность лучшего ГА	Надежность среднего ГА	Надежность ходшего ГА
1	0,093	0,999	0,628	0,07
2	1	0,995	0,864	0,419
3	1	0,994	0,865	0,421
4	0,606	0,997	0,770	0,550
5	0,188	0,998	0,740	0,212
6	0,789	0,996	0,820	0,610

шая структура ИНС была дообучена и дала результат со среднеквадратичной погрешностью 0,007 429 59. При замене настроек ГА получаемые результаты ухудшились (например, при одноточечном скрещивании ошибка составляла 0,009 742 даже на 83 поколении через 2,5 ч работы программы). Аналогичные результаты были получены и при восстановлении других зависимостей с шумом или без шума. Исчерпывающие исследования эффективности ГА при всех настройках не были проведены в связи со значительными временными затратами на эксперименты.

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

Параметры алгоритма генетического программирования: 100 индивидов, турнирная селекция, высокая вероятность мутации, полный метод выращивания, начальная глубина дерева 4, размерность турнира 4. Параметры генетического алгоритма: 50 индивидов,100 поколений, точность параметров 0,01, [-10; 10], размер турнира 4.

Была восстановлена функцияу= С + 2х + 3 на отрезке [-2; 2], выборка случайная, объем 100. Функциональное множество {+, -, *, /}. Точное решение было найдено на 4-ом поколении 41-ом дереве.

Восстанавливалась зависимость^ = sin(c) на отрезке [-1,5л; 1,5п], выборка случайная, объем 100. Функциональное множество {+, -, *, /}. Решение х x(0,075 413x2 -2,508 5)(x-3,15)(x + 3,15)

f (x) = —--------------5------------------ x2 + 25

было найдено на 27 поколении. Среднеквадратическая ошибка составила 0,007 452 135 535 545 14.

При расширенном функциональном множестве, включающем тригонометрические функции, точное символьное выражение восстанавливается не позже 5-го поколения.

Восстанавливался закон всемирного тяготения, выборка случайная, объем 1 000. Функциональное множество {+, -, *, /}. Точное символьное выражение находится всегда и не позже 4-5-го поколения.

2 x -

Восстанавливалась зависимость Ф( с ) = ^2— J e ² dt . Функциональное множество {+, -, *, /, sin, cos, exp}. Выборка случайная, объем 200, функция восстанавливается на отрезке [-5; 5].

На 214-ом поколении получено следующее решение: 0,500 3 + 0,141331058 • x +

+ 0,218 711887 • sin x + 0,032 064 685 • sin 1,77 x + +      sin(sin x )

• 68,    857 896 96 e ^{1,1 x 2 ,} среднеквадратическая ошибка составила 0,000 976 912 053 703 936.

^x sin( t )

Восстанавливалась зависимость/(+) =          dt .

0 t

Выборка случайная, объем 100, функция восстанавливается на промежутке [1; 7]. Функциональное множество {+, -, *, /, sin, cos}. На 40-ом поколении было найдено решение с точностью 0,002 573 587 789 442 59, а на 157-ом поколении получено выражение

, _Л        ( 0,4693 x - 0,2 x ² + 2 x ³)

( x - 9,2 ) + cos I------—--

V 2,71 x J

,     (6,57 - x ) <0,049 824) . (x - 1,52)

f (x) = ^-l —------ 4 —------- • sin I----

V x J V x J V x J

1 4,38 ( 0,870 x )( x - 3,01 ) )

x

[ V 2,96 JJ

• < 0,103 + x2 ) x-

• V     10,3 x J

среднеквадратичная ошибка 0,001 272 900 2.

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

Решались различные дифференциальные уравнения с переменным успехом. Так, решения дифференциальных уравнений

''                                     '

y + ln( x) y + x2

- e4

- e 4 (x2

- x ln x -

'

cos x

-

'' ^y

+ y + y =---

x cos xsin x

-Г+т+Т +

2sin x x ³

x ²

^^^^^в ^^^^^^^^^^^.

были получены достаточно легко y = e sin x

, y =---- ^при

правильном выборе штрафа за размеры дерева. В то же время, решения внешне более простых уравнений x2

- y" + (y1)2 = e 4

-

1 - xe ⁴

,

''

ln x _'

y ⁺-- y = x

x cos x + sin ( ln x - 1 )

x ²

никак не удавалось получить в простом виде. Лучший результат для первого уравнения -f (x) = sin(0,45sin(0,85x) + 0,41 x), среднеквадратичная ошибка составила 0,001 4. При анализе ситуации выяснилось, что для нахождения искомых решений надо «попут-x2 ^^^^^в ^^^^^^^^^^^.

но» решить дифференциальные уравнения y = e 2 , sinx y =----, т. е. «взять» неберущиеся интегралы. Этим и x объясняются возникавшие проблемы. Если решение дифференциального уравнения не требует сложного интег рирования, то решение в явном аналитическом виде получается практически всегда, в том числе получаются и истинные решения, найденные предварительно аналитическими методами.

Описанные результаты были изложены и обсуждены на ряде конференций молодых ученых [12-14].

Итак, в данной работе получены следующие результаты:

• -    разработаны модификации равномерного скрещивания, повысившие эффективность применения эволюционных алгоритмов в задачах математического моделирования интеллектуальными информационными технологиями;

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

• -    разработана и зарегистрирована программная система, позволяющая проводить исследования эффективности генетического алгоритма с модифицированным оператором обобщенной рекомбинации;

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

Результаты работы позволяют сформулировать следующие выводы.

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

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

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