Бесплатный автореферат и диссертация по биологии на тему

Разработка и применение самоадаптирующихся генетических алгоритмов

ВАК РФ 03.00.02, Биофизика

Автореферат диссертации по теме "Разработка и применение самоадаптирующихся генетических алгоритмов"

0 Д На правах рукописи

УДК 681.518.2:007

I и*. ,

СКУРИХИН АЛЕКСЕЙ НИКОЛАЕВИЧ

РАЗРАБОТКА II ПРИМЕНЕНИЕ СД МОЛДАПТНРУТОПШХСЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

03.00.02- биофизика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Пущине - 1996

Работа выполнена в Государственном Научном Центре Российской Федерации "Физико-Энергетический Институт"

Научные руководители:

Официальные оппоненты:

кандидат физико-математических паук Борисюк P.M.

кандидат физико-математических наук Куприянов В.М.

доктор физико-математических наук Дмитриев A.C.

кандидат физико-математических наук Ежов A.A.

Ведущая организация:

Вычислительный Центр РАН, г. Москва.

Защита состоится "29 " ^4^^996 г. в^час. на заседании Диссертационного Совета Д 200.22.01 в Институте теоретической и экспериментальной биофизики РАН по адресу: 142292, г. Пухцино Московской обл., ИТЭБ РАН.

С диссертацией можно ознакомиться в библиотеке ИТЭБ РАН,

Автореферат разослан "2 У января 1996 г.

Ученый секретарь Диссертационного Совета /j кандидат биологических наук

~/"7"]/; /Л, П.А.Нелипович

/ / U'Miutk li

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

1. Исследование свойств мобильного генетического алгоритма.

2. Разработка самоадаптирующихся механизмов управления алгоритмом.

3. Создание адаптивной системы классификации на основе модифицированного мобильного генетического алгоритма.

4. Анализ эффективности разработанных алгоритмов и систем, сравнение с другими методами.

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

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

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

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

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

исследование эффективности мобильных

для решения задачи прогнозирования газопотребления на географически большой территории США.

В настоящее время результаты данной работы и, в частности, программная разработка генетического алгоритма и нейросетевых алгоритмов, используются в университете штата Небраска (США) и в университете Сингапура. Планируется применение результатов работы в Физико-энергетическом институте (г.Обнинск) при создании специализированного комплекса "советчик оператора", предназначенного для решения задач диагностики н управления объектами на атомных электростанциях.

Материалы диссертации докладывались на:

1) Международная конференция по генетическим алгоритмам и нейронным сетям, Алее, Франция, 1995;

2) Тихоокеанская конференция по информационным системам, Сингапур, 1995;

3) 10-ая международная конференция по математическому и компьютерному моделированию и научным расчетам, Бостон, США, 1995;

4) Всемирный конгресс по нейронным сетям, Сан-Диего, США, 1994;

5) 11-ая Еяропейская конференция по искусственному интеллекту, Амстердам, Голландия, 1994;

6) Международная конференция по АРЬ, Антверпен, Бельгия, 1994;

7) Международная конференция по АРЬ, Торонто, Канада, 1993;

8) Международная конференция но АРЬ, Санкт-Петербург, Россия, 1992;

9) научные семинары в ФЭИ, г.Обнинск, в 1992-95 гг..

Публикации.

Основные результат диссертации опубликованы в 9 статьях. 2 статьи приняты к публикации в международных научных журналах и 2 статьи находятся на этапе рецензирования.

Структура и обьем работы.

Диссертация состоит из введения, шести глав, заключения, приложения п списка литературы. Объем диссертации - 147 страниц, 48 рисунков, 4 таблицы, библнофафия из 78 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении (- первая глава) обоснована актуальность работы, сформулированы основные цели, определена научная новизна и практически

ценность.

з

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

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

Функционирование стандартного генетического алгоритма определяется следующим образом:

1) Задается функция оптимальности, определяющая эффективность каждого потенциального решения.

2) В соответствии с определенным« ограничениями инициализируется исходное множество решений • задачи (в терминологии генетических алгоритмов - популяция). Обычно каждое решение представляется в виде вектора XI, который называется хромосомой (возможны также такие названия как строка или индивидуум). Хромосома состоит из элементов, которые называются генами. Каждый ген внутри хромосомы соответствует одной переменной. Изменяющиеся значения внутри гена называются аллелями. Наиболее часто используется двоичное представление переменных (рйс.1).

3) Каждая хромосома дс/, ¡=1,:.М, в популяции декодируется в необходимую форму для последующей оценки и затем ей присваивается значение эффективности ДхО в -соответствии с функцией оптимальности.

4) Каждой хромосоме присваивается вероятность воспроизведения 1—1,.которая зависит от эффективности данной хромосомы.

5) В соответствии с вероятностями воспроизведения р1 создается новая ■ популяция хромосом, причем с большей вероятностью отбираются наиболее оптимальные. Отобранные хромосомы производят потомков, используя операции рекомбинации, такие как кроссинговер (хромосомы скрещиваются, обмениваясь частями строк, рис.2) и мутация (вероятностное изменение аллелей, рис.3).

аллели

Рис. 1. Структура хромосомы.

Точка кроссннгоаера

Родите пь 1:110

Родитель 2: 0 0 1

1 1 Потомок 1: 0 0 111

0 1 Потомок 2: 110 0 1

Рис. 2. Одноточечная схема кроссинговера.

Потомок 1 Потомок 2

До мутации: 0 0 1 1 1 1 1 0 0 1

После мутации: 10 10 1 110 0 0

Рис. 3. Мутация.

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

ГЛ=(Р°, /V, /, 5, А/, Е),

где Р" = (*!,...,ДСлг) - популяция, Р" = Г(/У ') ,

I - номер поколения популяции, Г - правило, определяющее преобразование (набор операторов отбора и рекомбинации) поколения Р в поколение Р' .

XI - пробное решение задачи, представленное в виде хромосомы;

N - целое число, - размер популяции;

/ - целое число, - длина хромосомы (индивидуума) популяции;

5 - оператор отбора;

р - отображение, определяющее рекомбинацию (кроссинговер, мутация);

/ - функция оптимальности;

Е - критерий останова.

Теорема Холланда гарантирует глобальное улучшение свойств популяции, получаемой описанной выше последовательностью действий, гарантируя достижение оптимального решения.

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

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

Основываясь на перечисленных фактах молекулярной генетики был разработан новый тип генетического алгоритма - мобильный генетический алгоритм. Его основные особенности следующие: (1) отсутствует

фиксированное позиционирование генов внутри хромосомы, допускается наличие нескольких копий гена внутри хромосомы;(2) хромосомы имеют разные размеры, которые изменяются в процессе эволюции; (3) стандартный кроссинговер заменен двумя новыми операторами - CUT (разрезание) в SPLICE (сплайсинг) (рис.4);. (4) использование механизма экспрессии, который применяет правило чтения хромосомы "слева-направо". В результате, для активного проявления некоторого блока хромосомы необходимо не только, чтобы он сохранил свою целостность после разрезания хромосомы, но и чтобы он был экспрессирован после сплайсинга. Для любого гена активизируется только одна копия, которая находится ближе всего к левому концу хромосомы, все остальные копии данного гена не будут активизированы. Анализ показал, что совместное действие разрезания и сплайсинга носит примерно такой же характер, как и одноточечный кроссинговер,- при малых длинах хромосомы эффекты разрушения малы, при больших- нарастают, вероятность выживания и экспрессии уменьшается.

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

Важными параметрами, управляющими алгоритмом н влияющими на его эффективность, являются вероятность осуществления сплайсинга и вероятность мутации аллелей внутри гена.

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

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

р,=р0[ыр(-с/м)г,

гае С - количество общих генов между двумя хромосомами,

Перед I J

выполнением '-1-

3 , 4

"CUT" l^-^jy^jgWi

1 4

выполнения "SPLICE"

Рнс.4. Функционирование операторов СиТ(разрезанне) и БРЫСЕСснлансинг).

М — максимально возможное количество общих генов между этими же хромосомами;

к - некоторая положительная константа, задаваемая предварительно, например, 2 или 4;

•0<а,<1.

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

рс = 1рк, (ще 0<рк<1),

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

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

После .

Представление вероятностей мутаций

I bits к bits

4-► И-H

*1 Х2 *п J Рг рп

Рис.5. Представление мутаций.

Механизм управления мутацией реализован следующим образом:

• вероятность мутации кодируется вместе с хромосомой в одной строке;

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

• инициализация массива вероятностей мутации случайная.

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

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

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

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

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

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

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

АСК содержит следующие три главные компоненты:

• система правил (множество классификаторов) и сообщений;

• система распределения кредита(вознаграждения);

• метод оптимизации - генетический алгоритм.

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

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

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

IU

РВ - распрслелопк вознатравления

РК - разрешение консЬликтов между правшхаАти

мод.ГА - модифицированный мобильный генетический алгоритм

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

Сообщение внутри системы классификации - битовая строка конечного размера на некотором ограниченном алфавите. В случае использования двоичного алфавита:

<сообщенне> = {0,1}' ,

те / - длина бинарной строки. Сообщения используются для сравнения с условиями, закодированными в правилах (классификаторах). Классификатор представляется в следующем виде:

<классификатор> = <условие>:<сообщение>,

где условие - простое устройство распознавания образов с дополнительным символом алфавита (#): <условие> = {0,1, #}' .

Условие сравнивается с сообщением, если в одной и той же позиции строки условия и сообщения находятся одинаковые значення (0 или 1). Если какая-либо позиция условия содержит то данная позиция сравнивается с любым значением. Например, ##10 будет сраниваться с 0010 и с 1010, но не будет с 0011. Как только условие классификатора сравнилось с сообщением, он становится кандидатом послать свое сообщение в список сообщений в следующий момент времени. Победитель среди кандидатов определяется по итогам "конкуренции с шумом", то есть победителем, посылающим сообщение становится классификатор с максимальным значением величины, Е>,

£; = с51 + Ы(а),

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

= -св-к) + Я, О)

где Б' - эффективность /-ого классификатора на итерации V, в - фактор, отражающий специфичность классификатора,

п п°-1

и = , где «о,1 - количество позиций, отличных от #; 1С1 - длина условия классификатора;

Т-кБ (где 0<к<1. Налог позволяет уменьшить в системе количество низкоэффективных правил); 0<с<1, /?>0.

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

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

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

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

В качестве тестовой задачи использовалась задача имитации мультиплексора, которая традиционно применяется для исследования эффективности генетических алгоритмов. Мультиплексор с б-ыо входными линиями схематически изображен на рис.7. Сигналы на первых двух линиях кодируют адрес одной из остальных 4-х линий данных, значение сигнала с которой будет передано на выход мультиплексора. Размерность проблемы можно увеличить, добавляя новые входные линии. В обшам случае, мультиплексор с к линиями адреса имеет к + 2* линий еходз.

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

Изменение эффективности классификатора в результате конкуренции описывается уравнением (1).

Параметры системы классификации определяются следующим образом:

• система содержала 100 классификаторов для "б-" мультиплексора и 400 классификаторов для "11-" мультиплексора задач;

• длина вектора, представляющего условие классификатора, с которым сравнивается входной вектор, равна б или 11 в зависимости от типа имитируемого мультиплексора, длина двоичного вектора, представляющего отклик классификатора, равна 1. Элементы вектора, представляющего условие, принимают значения из множества {0,1,#);

• использовалась модель "стимул-отклик", то есть отсутствовало задержанное вознаграждение и классификаторы не обменивались сообщениями. Классификатор, победивший в конкуренции с другими классификаторами, посылает свое однобитовое сообщение (либо 0, либо 1), которое является итоговым ответом всей системы классификации на данный входной вектор.

Рис.7. Мультиплексор с 6-ью входными линиями.

• значения с, к, R, а устанавливаются следующим образом: с-0.1, R-1.0, к=0.0, а=0.075.

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

• контроль сплайсинга и мутации аллелей осуществлялся новыми механизмами, предложенными в предыдущих разделах;

• вероятность CUT, р = I рк, вде I - длина хромосомы, рк =0.02. Генетический процессинг применялся каждые 5000 итераций, обновлению

подвергалось 20% популяции классификаторов. Как показали эксперименты, снижение периода применения генетического процессинга с 5000 до 2000 или увеличение пропорции до 40% вызывает полную потерю системой эффективности. 20% заменяемых классификаторов выбиралось из числа наименее эффективных.

Результаты сравнивались с эффективностью системы на основе стандартного генетического алгоритма. Для "6-" мультиплексора корректность откликов системы классификации оказалась примерно одинаковой и достаточно высокой - 94-97%. Для "11-" мультиплексора разработанная система классификации обеспечила 85% уровень корректности работы, в то время как. стандартная система достигла точности 82%. • Разработанная система использовалась для решения практической задачи -классификация поступающих в американский университет. Необходимо было

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

Использовались реальные данные, предоставленные американской компанией занимающейся подобными исследованиями. Данные представляли агрегированные оценки предыдущей успеваемости учащихся, например "high school grade point average" и результаты психологического тестирования. Все данные были преобразованы в бинарную форму, то есть представлялись значениями из множества [0,1]. В данном исследовании выборка содержала 700 двопчных вехторов по 39 оценок каждый с известным результатом для каждого вектора (прошел студент курс обучения или нет). Целью системы классификации было научиться как можно лучше классифицировать поступающего, используя имеющуюся базу из 700 векторов. В качестве обучающей выборки использовалось 600 векторов, в качестве тестирующей -100. Система должпа была выдавать на выход 0 или 1 в зависимости от способностей конкурсанта пройти полный курс обучения.

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

• система содержит 400 классификаторов;

• длина вектора, представляющего условие классификатора, с которым сравнивается входной вектор, равна 39;

. к=0.05.

• вероятность мутации отклика классификатора была установлена равной 0.004.

Достигнутая точность разработанной системы на обучающем наборе данных составила 83.4%, па тестовом - 74%. Для сравнения применялись следующие методы: стандартный генетический алгоритм и нейронные сети типа метода обратного распространения ошибки, метод ускоренного обратного распространения ошибки, метод каскадной корелляшш, алопекс, то есть методы, использующие как градиентные процедуры, так и случайный поиск. Лучшая точность, достигнутая альтернативными методами, составила 66% hi тестовом наборе.

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

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

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

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

Прогнозирование энергопотребления, - потребления газа, - является актуальной задачей. Проблему представляет не только долговременный прогноз, например, на несколько месяцев вперед, но и кратковременный прогноз на один день. Поставленной целью была разработка алгоритма, предсказывающего газопотребление на один день вперед. Для решения использовались реальные данные ежедневного газопотреблепия на некоторой географически большой территории США за период с 1981 по 1991 год, предоставленные американской энергетической компанией.

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

Выборка данных была разделена на две части: 1) данные за 1981-1990 гг. использовались для обучения нейронной сети, 2) данные за январь-март 1991 года использовались для тестирования нейросети (95 дней).

Критерием точности служит средняя ошибка прогноза по тестовому периоду, вычисляемая по формуле:

гае Г - прогнозируемый период,

)'1 - фактические значения временного ряда,

1Г>

)'<* - прогнозируемые значения временного ряда.

Средняя ошибка прогноза по тестовой выборке, полученная самоадаптирующимся генетическим алгоритмом составила 4.4% (для алопекс -4.1%, остальные четыре нейросетевых метода - 5.4-7.8%).

Глава 8(заключение'1 содержит формулировку основных результатов работы.

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

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

3. Разработана адаптивная система классификации на . основе самоадаптирующегося мобильного генетического алгоритма.

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

5. Система использовалась для решешгя практической задачи -классификация поступающих в университет. Достигнутые результаты (74% точности) показали реальную возможность применения модифицированной системы в приложениях.

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

1Т

7. Модифицированный генетический алгоритм использовался для решения практической задачи прогнозирования ежедневного потребления газа на географически большой территории на один день вперед. Результаты применения и сравнения с альтернативными методами продемонстрировали реальную возможность применения модифицированного алгоритма в приложениях. Средняя ошибка прогноза для тестового периода (95 дней), полученная с использованием модифицированного генетического алгоритма, составила 4.4% (для алопекс - 4.1%, остальные четыре нейросетевых метода -5.4-7.8%).

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

Основной материал диссертации изложен в следующих работах:

[1] Скурнхин, А.Н., "Нейронные сети: определения, концепции, применение", ФЭИ-0246, М:ЦНИИатоминформ, 53с., 1991.

[2] Skurikhin, A.N., "Neural networks in J", Proc. of the Intern. Conf. on APL, APL Quote Quad, Vol.23, No.l, pp.216-220, StPetersburg, Russia, July 1992.

[3] Skurikhin, A.N., Surkan, A.J., 'identification of parallelism in neural networks by simulation with language J", Proc. of the Intern. Conf. on APL, APL Quote Quad, Vol.24, No.l, pp.230-237, Toronto, Canada, August 1993.

[4] Скурихии, A.H., Замиусский, B.H., Богомолов, B.H., "Нейросети: применение в диагностике", ФЭИ-0266, М:ЦНИИатоминформ, 23с„ 1994.

[5] Surkan, A.J., Skurikhin, A.N., "Memory neural networks applied to the prediction of daily energy usage", Proc. of the World Congress on Neural Networks, San Diego, USA, Vol.2, pp.254-259, Publisher: Lawrence Erlbaum Associates, Hillsdale. 1994.

[6] Skurikhin, A.N., Surkan, A.J., "Alopex network algorithm applied to predict gas usage", Proc. of the 11th European Conference on Artificial Intelligence, ECAI-94, pp.241-245, Amsterdam, The Netherlands, Publisher: John Wiley & Sons. 1994.

[7] Skurikhin, A.N., Surkan, A.J., "A parallel correlation-based algorithm in J learns neural network connections", Proc. of the Intern. Conf. on APL, APL Quote Quad, Vol.25, No.l, pp.194-199, Antwerpen, Belgium, September 1994.

[8] Skurikhin, A.N., Surkan, A.J., "Neural network training compared for backprop, quickprop and cascor in energy control problems", Proc. of the Intern. Conf. on Genetic Algorithms and Neural Networks, France, pp. 444447, April 1995.

[9] Surkan, A.J., Skurikhin, A.N., "Evolving pattern detectors for predicting retention in managing student retention", Proc. of the Pan Pacific Conf. on Information Systems, Singapore, June 1995.

[10] Skurikhin, A.N., Surkan, A.J., "Messy genetic algorithm evaluate college student applicants", (статья будет опубликована в первом квартале 1996г. в журнале Mathematical Modelling and Scientific Computing).

[11] Skurikhin, A.N., "Messy genetic processing", (статья будет опубликована в первом квартале 1996г. в журнале Vector).

Статьи, находящиеся на стадии рецензирования:

[1] Skurikhin, A.N., Surkan, A.J., "Messy genetic algorithm learns classifier for multiplexer design", (статья заявлена на the IEEE Intern. Confer, on Evolutionary Computation, Japan, May 1996r.).

[2] Surkan, A.J., Skurikhin, A.N., "Prediction by neural network methods compared for energy control problems", (статья заказана, invited paper, для American Power Conference, USA, April 1996).