Авторефераты по всем темам  >>  Авторефераты по техническим специальностям  

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

Семенкина Мария Евгеньевна

САМОКОНФИГУРИРУЕМЫЕ ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ МОДЕЛИРОВАНИЯ И ОПТИМИЗАЦИИ

05.13.01 - Системный анализ, управление и обработка информации

(информационные и космические технологии)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

Красноярск - 2012

Работа выполнена в ФГБОУ ВПО Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева (СибГАУ), г. Красноярск

Научный руководитель: доктор физико-математических наук, профессор

Попов Евгений Александрович

Официальные оппоненты:  доктор технических наук, профессор

овчиков Анатолий Николаевич

ФГБОУ ВПО Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева, профессор кафедры систем автоматического управления

доктор технических наук, профессор

Спицын Владимир Григорьевич

ФГБОУ ВПО Научно-исследовательский Томский политехнический университет, профессор кафедры вычислительной техники

Ведущая организация:  Институт проблем управления РАН

имени В. А. Трапезникова (г. Москва)

Защита состоится л27 декабря 2012 г. в 14 часов на заседании диссертационного совета Д 212.249.02 при ФГБОУ ВПО Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева по адресу: 660014 г. Красноярск, проспект имени газеты Красноярский рабочий, 31

С диссертацией можно ознакомиться в библиотеке Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева

Автореферат разослан л 26 ноября 2012 г.

Ученый секретарь

диссертационного совета                        Александр Алексеевич Кузнецов

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

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

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

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

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

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

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

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

1. Разработать генетический алгоритм для эффективной оптимизации в дискретных пространствах;
2. Разработать алгоритм генетического программирования, решающий задачи символьной регрессии, для эффективного поиска на дискретных структурах;
3. Разработать алгоритм генетического программирования для автоматического генерирования нейронных сетей произвольной архитектуры;
4. Разработать подход для автоматического выбора настроек и параметров эволюционных алгоритмов в ходе решения задачи.
5. Разработать процедуру принятия решений коллективом ИИТ для повышения эффективности моделирования сложных систем и процессов;
6. Реализовать разработанные подходы в виде программных систем;
7. Проверить работоспособность предложенных подходов на тестовых и реальных практических задачах.

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

Научная новизна работы заключается в следующем:

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

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

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

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

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

Реализация результатов работы. Разработанные алгоритмы использованы при выполнении исследований в рамках российско-германских проектов 2011-1.9-519-005-042 Распределенные интеллектуальные информационные системы обработки и анализа информации в диалоговых информационно-коммуникационных системах ФЦП Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы (с участием научных и исследовательских организаций стран Европейского Союза) (ГК №11.519.11.4002) и 2011-1.2.1-113-025-002 Математическое и алгоритмическое обеспечение автоматизированного проектирования аппаратно-программных комплексов интеллектуальной обработки информации в распределенных высокопроизводительных системах космического назначения ФЦП Научные и научно-педагогические кадры инновационной России на 2009-2013 годы (с участием научно-исследовательских и научно-образовательных организаций Германии) (ГК № 16.740.11.0742). Кроме того, данная работа была поддержана молодежными инновационными грантами Сибирского федерального университета 2007-2009 гг. и Фондом содействия развитию малых форм предприятий в научно-технической сфере в рамках программы Участник молодежного научно-инновационного конкурса (У.М.Н.И.К.).

Две программные системы прошли государственную экспертизу и были зарегистрированы во ВНТИЦ, три программные системы зарегистрированы в Роспатенте.

Разработанные в диссертации программные системы используются в учебном процессе Института информатики и телекоммуникаций СибГАУ при выполнении лабораторных и курсовых работ и, кроме того, переданы для использования в две инновационные IT-компании.

Основные положения выносимые на защиту:

1. Разработанный генетический алгоритм оптимизации с модифицированным оператором множественной рекомбинации превосходит стандартный генетический алгоритм по надежности и быстродействию.
2. Новые операторы равномерного скрещивания в алгоритме генетического программирования по надежности сравнимы со стандартным и превосходят одноточечное скрещивание и предотвращают чрезмерное усложнение решений.
3. Эволюционный алгоритм автоматического генерирования нейронных сетей является эффективным средством построения нейросетевых моделей произвольной структуры.
4. Разработанный способ самоконфигурации эволюционных алгоритмов позволяет избегать затрат на их настройку, не снижая при этом эффективности моделирования и оптимизации.
5. Предложенная процедура принятия решения  коллективом  ИИТ является эффективным средством повышения точности моделирования сложных систем и процессов.

Апробация работы. Процесс разработки алгоритмов и результаты проведенных исследований докладывались в период 2006-2012 гг. на 24 конференциях различного уровня, среди которых 6 зарубежных, 6 международных, 4 всероссийских с международным участием и 8 молодежных научных конференций, в том числе: Biologically Inspired Optimization Methods and Applications (Bohinj, Slovenia, 2012), Advances in Swarm Intelligence (Shenzhen, China, 2012), Informatics in Control, Automation and Robotics (Rome, Italy, 2012), Congress on Evolutionary Computations of the IEEE World Congress on Computational Intelligence (Brisbane, Australia, 2012), Computational Intelligence in Security for Information Systems (Ostrava, Czech Republic, 2012), XII и XIII Национальные конференции по искусственному интеллекту с международным участием (г. Тверь, 2010, г. Белгород, 2012 гг.), XIII Международная научно-техническая конференция Кибернетика и высокие технологии XXI  века (г. Воронеж, 2012), I и II Всероссийские научные конференции с  международным участием  Теория и практика системного анализа (г. Рыбинск, 2010, 2012 гг.), VII Всероссийская научно-практическая конференция с международным участием "Информационные технологии и математическое моделирование" (Томск, 2008), и др. Кроме того, отдельные результаты работы были обсуждены на научном семинаре института информационных технологий университета г. Ульм (Германия, 2011), а диссертация в целом обсуждалась на научных семинарах института проблем управления РАН имени В.А.Трапезникова (Москва, 2012) и института системного анализа РАН (Москва, 2012), а также на научно-техническом семинаре кафедры системного анализа и исследования операций СибГАУ.

Публикации. По материалам данной работы опубликовано более 25 печатных работ, в том числе 5 статей в научных изданиях Перечня ВАК.

Структура работы. Работа состоит из введения, пяти глав, заключения, списка литературы и приложений.

Основное содержание работы

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

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

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

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

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

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

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

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

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

1. Создается дерево обобщенных структур;

2. Для каждого узла дерева обобщенных структур случайным образом выбирается номер претендента-родителя;

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

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

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

Описанный подход был реализован и протестирован для оценки эффективности разработанных операторов. Так как набор общепринятых тестовых задач для алгоритма генетического программирования все еще относится к "открытым вопросам", для предварительной оценки были использованы задачи символьной регрессии. Каждый алгоритм получал 100 индивидов и 300 поколений для поиска решения и был запущен по 100 раз на каждой тестовой функции.

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

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

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

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

Следуя определению, данному организаторами семинара по самонастраивающимся эволюционным алгоритмам (Self*EAs) Международной конференции PPSN XI (Krakov, 2010), выделим 3 основных пути к автоматической разработке алгоритмов. Первый путь - это (само)регулирование или (само)настройка управляющих параметров алгоритма. Второй путь - (само)конфигурирование алгоритмов, т.е. автоматизированный выбор и применение существующих алгоритмических компонент (вариантов операторов). И последний, третий, подход - это обобщение или создание новых эвристик из существующих подкомпонент, заимствованных из других адаптивных поисковых методов.

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

Таблица 1 ЦПсевдокод для SelfCEA

	Псевдокод для SelfCEA
1 2 3 4 5 6 7 8 9 10	Установить равные вероятности для всех вариантов настройки для каждого вида оператора (исключение - пустое скрещивание). For k=1 to N For l=1 to NInd Выбрать вариант селекции, рекомбинации и мутации; Выбрать родителей выбранным оператором селекции; Скрестить родителей выбранным оператором рекомбинации для создания потомка; Мутировать потомка с выбранной вероятностью мутации; Оценить потомка; Выбрать выживших с выбранным оператором замещения; Обновить вероятности для операторов, используя среднюю пригодность потомков, полученных при помощи данного оператора.
	Пояснение для шага 10 (пересчет вероятностей)
1	Для каждого оператора проверить превышают ли его вероятности - пороговую вероятность для данного типа оператора, где i - это номер типа оператора (скрещивание, селекция и другие), j - номер конкретного вида оператора для данного типа.
2	Если:
		и
	то вероятность оператора изменяется следующим образом:
3	Выбор оператора получившего самую большую среднюю пригодность сгенерированных с его участием потомков , при , где - число поколений, Fitki Цпригодность i-го индивида на k-м поколении;
4	К вероятности выигравшего варианта оператора прибавляем все, что было вычтено из вероятностей на шаге 2.

Самоконфигурируемый ГА (SelfCGA) был проверен на тех же обычных  тестовых задачах. Было проведено сравнение самоконфигурируемого ГА, основанного на общепринятых операторах скрещивания (одноточечное, двухточечное, равномерное) (SelfCGA-1) и самоконфигурируемого ГА основанного на 6 типах скрещивания (SelfCGA-2), т.е. включая и новые типы операторов.

По результатам тестирования можно сделать вывод, что:

• SelfCGA-1 работает лучше, чем три отдельных алгоритма, скомбинированные в нем. Это позволяет утверждать, что способ самоконфигурирования ГА сам по себе оказывает положительное влияние на эффективность алгоритма.
• SelfCGA-2 превосходит SelfCGA-1 по всем показателям, например имеет лучшею среднюю надежность и разброс надежностей. Из этого следует, что предложенные типы операторов равномерного скрещивания с селективным давлением оказывают положительное влияние на эффективность ГА при взаимодействии настроек и дают надежду на лучшие результаты при решении реальных практических задач.
• Различия между ними являются статистически значимыми, что было подтверждено с использованием ANOVA и пакета статистической обработки данных Statistica.
• Алгоритмы с самоконфигурированием обеспечивают меньший разброс надежностей, меньший разброс среднего числа поколений до нахождения оптимума, а также обладают сопоставимым временем работы в сравнении со стандартным генетическим алгоритмом.
• Лучшим выбором, по результатам данного исследования, является генетический алгоритм с самоконфигурированием с вновь введенными модифицированными операторами равномерного скрещивания, поскольку он уменьшает перебор настроек алгоритма более чем в 54 раза и обеспечивает высокую надежность работы при произвольном выборе остальных настроек (способ кодирования, управление популяцией и другие).

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

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

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

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

Худшая надежность по 100 прогонам равна 0.42, лучшая 1.00. Средняя надежность SelfCGP, усредненная по 17 задачам, выше, чем лучшая из усредненных надежностей стандартного ГП, и немного меньше, чем лучшая усредненная надежность МГП (определенная экспертом после многочисленных прогонов). Кроме того, SelfCGP тратит меньше ресурсов, чем альтернативные алгоритмы. Это позволяет рекомендовать SelfCGP для решения задач символьной регрессии как лучшую альтернативу стандартному ГП. Основным достоинством SelfCGP является отсутствие необходимости в настройке его параметров, что делает этот алгоритм весьма полезным в различных приложениях, где конечный пользователь, не будучи специалистом в области эволюционных алгоритмов, тем не менее применяет ГП для решения своих задач. Еще одним полезным для практики свойством SelfCGP является предотвращение чрезмерного разрастания деревьев за счет применения операторов равномерного скрещивания.

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

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

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

Так как при генерации нейросетей алгоритм ГП имеет дело не с числами, а с нейронами, то и допустимые операции из его функционального множества специфические:

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

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

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

Для настройки весовых коэффициентов полученной нейронной сети применялся SelfCGA с последующим локальным спуском.

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

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

Всевозможные интеллектуальные информационные технологии можно гибридизировать в единый подход. Обычно для этого применяются различные методы создания ансамблей - усреднение, взвешенное усреднение, голосование и т.д. У. Йоханссон и др. (2006) впервые применили алгоритм генетического программирования для создания ансамбля из определенного количества искусственных нейронных сетей (ИНС), где функциональный набор состоял из операций усреднения и умножения, а терминальное множество включало в себя  константы. В работе В. Бухтоярова (2010), был предложен аналогичный подход, где сначала генерировалось определенное число нейронных сетей, а потом алгоритм генетического программирования применялся для получения ансамбля, создавая символьные выражения, использующие в качестве входов отдельные нейронные сети. Известно, что разнообразие членов ансамбля играет важную роль при их создании. В данной работе для формирования общего метода принятия решений коллективом различных ИИТ применяется самоконфигурируемый алгоритм генетического программирования (SelfCGP), как наиболее подходящий инструмент для автоматизированного проектирования ИИТ, который не требует затрат времени и ресурсов на свою настройку и позволяет формировать как членов ансамбля ИИТ, так и способ принятия решений этим коллективом. Алгоритм включает в себя различные арифметические операции и математические функции и использует ИИТ разных видов для обеспечения разнообразия среди участников ансамбля. Далее в численных экспериментах в качестве членов ансамбля используются символьные выражения и нейронные сети, автоматически сгенерированные при помощи SelfCGP. Алгоритм автоматически выбирает конкретные ИИТ, которые вносят существенный вклад в эффективность решения, и не использует другие. Интеллектуальные информационные технологии отбирались в ансамбль из предварительного пула ИИТ, который включает в себя 20 ИНС и 20 символьных формул (СФ), заранее порожденные SelfCGP. Для настройки численных параметров в СФ и ИНС применяется SelfCGA с локальным спуском.

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

При помощи самоконфигурируемого генетического алгоритма SelfCGA решена задача выбора эффективного варианта структуры аппаратно-программного комплекса систем управления космическими аппаратами (КА).

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

Задача оптимизации для выбора эффективного варианта технологического контура управления имеет 11 дискретных переменных. Соответствующее пространство оптимизации содержит около 1.761013 точек и не может быть просмотрено при помощи полного перебора, в частности потому, что рассмотрение одной точки включает численное решение системы линейных уравнений с 40 переменными. Лучшие и худшие допустимые значения показателей не известны, поэтому  далее используются самые лучшие известные решения. Для оценки эффективности алгоритмов используются 40 индивидов на одно поколение и 80 поколений за один прогон, то есть алгоритм просматривает около 1.8210-7 % точек поискового пространства. Таблица 2 содержит результаты оценки надежности различных вариантов алгоритмов при решении задачи максимизации коэффициента готовности технологического контура системы управления космическим аппаратом. В первом столбце приведены названия операторов селекции, используемых соответствующим ГА (UE - равномерное равновероятное, UR - ранговое, UP - пропорциональное, UT - турнирное), результаты усреднены по выбору остальных настроек. Во втором столбце приведена доля прогонов, в которых был найден известный оптимума, среди общего числа прогонов (100). В двух следующих столбцах приведены среднее отклонение и относительное среднее отклонение найденных решений от известного оптимума. В последнем столбце приведен средний номер поколения, на котором был найден известный оптимум (оценка затрат на оптимизацию).

Таблица 2 - Сравнение надежностей алгоритмов для технологического контура

Алгоритмы	Надежности	MD (%)	RMD (%)	Поколение
UE	0.79	0.0115	0.2178	56
UR	0.86	0.0099	0.1875	48
UP	0.73	0.0121	0.2292	59
UT	0.87	0.0095	0.1799	49
SelfCGA	0.90	0.0092	0.1742	33

Модель командно-программного контура управления, содержащая 96 состояний и более 300 переходов, имеет 13 переменных и содержит 4.51015 точек в пространстве оптимизации. Для нахождения решения алгоритмам разрешалось просмотреть около 2.210-10 % поискового пространства (100 индивидов на 100 поколений). Для этой модели были получены аналогичные результаты.

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

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

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

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

Таблица 3 - Числовые характеристики решеных задач анализа данных

Задача	Число входов	Число выходов	Число классов	Размер выборки
Ирисы	3	1	3	150
Рак	10	1	2	699
Диабет	8	1	2	768
Кредит в Австралии	14	1	2	690
Кредит в Германии	20	1	2	1000
Выявление PROBE атак	8	1	2	4,900,000
Обнаружение спама	57	1	2	4600
ISOLET	617	1	26	7797
Прогнозирование деградации солнечных батарей	7	4	Аппроксимация	197

Задачи классификации решены как путем построения разделяющих поверхностей, представленных символьными выражениями, т.е. с применением алгоритма SelfCGP для символьной регрессии (SelfCGP+SRF), так и при помощи нейронных сетей, автоматически генерируемых самоконфигурируемым алгоритмом генетического программирования (SelfCGP+ANN). Во время экспериментов использовались 100 индивидов и максимум 500 поколений на каждом из 20 запусков. Все результаты были усреднены. Для разработки коллективов ИИТ каждый набор данных случайным образом разделили на три части, т.е. обучающую выборку (60%), проверочную выборку (20%) и тестовую выборку (20%). Статистическая достоверность полученных результатов была подтверждена при помощи ANOVA.

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

Сформированный ансамбль нейронных сетей имеет вид (на примере задачи о диагностике диабета): sin(0.5(N2+N8+N9)), а ансамбль символьных выражений: . Здесь Ni и Fi являются выходными значениями, соответственно, нейронных сетей и аналитических выражений, входящих в предварительный пул из 10 моделей. Нетрудно видеть, что в оптимальный ансамбль включаются далеко не все кандидаты.

Результаты второго эксперимента на двух задачах классификации из области банковского скоринга (см. таблицу 4, где последняя буква Е в названии классификатора означает использование ансамбля соответствующих ИИТ) показали, что ансамбли, автоматически сгенерированные SelfCGP, превосходят другие ансамбли (бустинг, багинг, CCEL) и одиночные классификаторы, в том числе и специально реализованные для решения задач банковского скоринга (нечеткий классификатор, 2SGP).

Таблица 4 - Сравнение методов классификации

Классификатор	Кредит Австралия	Кредит Германия	Классификатор	Кредит Австралия	Кредит Германия
SelfCGP ANN+SRFE	0.9094	0.8126	GP+SRF	0.8889	0.7834
SelfCGP ANNE	0.9046	0.8075	CART	0.8744	0.7565
SelfCGP SRFE	0.9046	0.8050	LR	0.8696	0.7837
2SGP	0.9027	0.8015	CCEL	0.8660	0.7460
SelfCGP+ANN	0.9022	0.7954	RSM	0,8520	0,6770
SelfCGP+SRF	0.9021	0.7950	Bagging	0.8470	0.6840
GP+ANN	0.8969	0.7863	Bayesian	0.8470	0.6790
C4.5	0.8986	0.7773	Boosting	0.7600	0.7000
Fuzzy	0.8910	0.7940	k-NN	0.7150	0.7151

Ансамбли нейронных сетей имеют вид: cosN0+0.5N8N9 (для задачи Кредит Австралия) и 1Ц(1ЦN0)(1ЦN1) (для задачи Кредит Германия). И в этом случае в ансамбль включены по 2-3 нейросети из 10 доступных алгоритму.

Если не учитывать коллективные подходы, первое место занял 2SGP, который был специально разработан для решения задачи банковского скоринга. Вторым на обеих задачах стал предложенный в данной работе SelfCGP+ANN, третьим стал SelfCGP+SRF.

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

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

Автоматическое проектирование ансамблей гетерогенных ИИТ, основанное на SelfCGP, позволяет повысить надежность и эффективность обработки информации, что подтверждается решением ряда задач анализа данных.

В заключении диссертации приведены основные результаты и выводы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

Публикации по теме диссертации:

Статьи в ведущих рецензируемых научных журналах и изданиях

1. Попов Е.А., Семенкина М.Е., Липинский Л.В. Принятие решений коллективом интеллектуальных информационных технологий // Вестник СибГАУ. - № 4 (44). - 2012.

2. Popov E.A., Semenkina M.E., Lipinski L.V. Evolutionary algorithm for automatic generation of neural network based noise suppression systems // Vestnik. Scientific Journal of Siberian State Aerospace University named after academician M. F. Reshetnev. - № 4 (44). - 2012.

3. Semenkin E.S., Semenkina M.E. Integration of Intelligent Information Technologies Ensembles with Self-Configuring Genetic Programming Algorithm // Vestnik. Scientific Journal of Siberian State Aerospace University named after academician M. F. Reshetnev. - № 4 (44).Ц2012.

4. Семенкин Е.С., Семенкина М.Е. Программный комплекс адаптивных эволюционных алгоритмов моделирования и оптимизации сложных систем // Программные продукты и системы. - № 4 (100). - 2012. - С. 54-58.

5. Семенкин Е.С., Семенкина М.Е. Применение генетического алгоритма с модифицированным оператором равномерной рекомбинации при автоматизированном формировании интеллектуальных информационных технологий // Вестник СибГАУ. - № 3 (16). - 2007. - С. 27-33.

Статьи в сборниках трудов коференций

6. Semenkin E.S., Semenkina M.E. Self-configuring Genetic Algorithm with Modified Uniform Crossover Operator // Y. Tan, Y. Shi, and Z. Ji (Eds.): Advances in Swarm Intelligence. - Lecture Notes in Computer Science 7331. - Springer-Verlag, Berlin Heidelberg, 2012. - P. 414-421.

7. Semenkin E.S., Semenkina M.E., Panfilov I.A. Neural Network Ensembles Design with Self-Configuring Genetic Programming Algorithm for Solving Computer Security Problems // Herrero A., et al (Eds.): Computational Intelligence in Security for Information Systems. - Advances in Intelligent Systems and Computing 189. - Springer-Verlag, Berlin Heidelberg, 2012. - P. 25-32.

8. Semenkin E.S., Semenkina M.E. Self-Configuring Genetic Programming Algorithm with Modified Uniform Crossover // Proceedings of the Congress on Evolutionary Computations of the IEEE World Congress on Computational Intelligence (CEC WCCI 2012), Brisbane, Australia, 2012. - P. 1918-1923.

9. Semenkin E.S., Semenkina M.E. The Choice of Spacecrafts' Control Systems Effective Variants with Self-Configuring Genetic Algorithm // Ferrier, J.L. et al (Eds.): Informatics in Control, Automation and Robotics: Proceedings of the 9th International Conference ICINCOТ2012. - Vol. 1. - Rome: Italy, 2012. - P. 84-93.

10. Semenkin E.S., Semenkina M.E. Artificial neural networks design with self-configuring genetic programming algorithm // Filipic B., Silc J. (Eds.): Bioinspired Optimization Methods and their Applications: Proceedings of the Fifth International conference BIOMA 2012. - Ljubljana: Jozef Stefan Institute, 2012. - P. 291Ц300.

11. Семенкина М.Е. Самоконфигурируемый генетический алгоритм с модифицированными операторами равномерного скрещивания // Кибернетика и высокие технологии XXI века. Сб. тр. 13-й международной научно-технической конференции - Т. 1. - Воронеж: ИСА РАН, 2012. - С. 32-41.

12. Семенкина М.Е. Самоконфигурируемый алгоритм генетического программирования для создания ансамблей интеллектуальных технологий // XIII национальная конференция по искусственному интеллекту с международным участием КИИ-2012: Труды конференции. - Т.2. - Белгород: Изд-во БГТУ, 2012. - С. 284-291.

13. Семенкина М.Е. Самоконфигурируемые эволюционные алгоритмы моделирования и оптимизации // Теория и практика системного анализа. - Рыбинск: ИСА РАН, РГАТА имени П.А. Соловьева, 2012. - С. 24-30.

14. Семенкина М.Е. Об алгоритме генетического программирования для автоматизации проектирования интеллектуальных информационных технологий // Информационные технологии, системный анализ и управление: Сб. тр. IX Всероссийской конференции. - Т.1. - Таганрог: ТТИ ЮФУ, 2011. - С. 190-192.

15. Семенкина М.Е. Алгоритм генетического программирования с равномерным скрещиванием для проектирования интеллектуальных информационных технологий // Труды XV Международной научной конференции Решетневские чтения. - Ч. 2. - Красноярск: СибГАУ, 2011. - С. 499-500.

16. Липинский Л.В., Лыткин И.С., Семенкина М.Е. Об автоматизации проектирования нейросетевых систем подавления шума с помощью алгоритма генетического программирования // Теория и практика системного анализа. - Рыбинск: ИСА РАН. РГАТА имени П.А. Соловьева, 2010. - с.33-39.

17. Липинский Л.В., Лыткин И.С., Семенкина М.Е. Об эволюционном алгоритме формирования нейросетевой системы подавления // XII национальная конференция по искусственному интеллекту с международным участием КИИ-2010: Труды конференции. - Т. 4. - М.: Физматлит, 2010. - С. 116-121.

18. Семенкина М.Е. Алгоритм генетического программирования с множественной рекомбинацией // Информационные технологии и математическое моделирование (ИТММ-2008): Материалы VII Всероссийской научно-практической конференции с международным участием. - Томск: Изд-во Том. ун-та, 2008. - Ч. 1. - С.110-112.

19. Семенкина М.Е. Об автоматизации проектирования интеллектуальных информационных технологий алгоритмами генетического программирования // Перспективы развития фундаментальных наук: материалы Международной конференции молодых ученых. - Томск: Изд-во ТПУ, 2008. - С. 288-290.

20. Семенкина М.Е. Разработка и исследование оператора множественной рекомбинации в алгоритмах генетического программирования // Труды XI Международной научной конференции Решетневские чтения. - Красноярск: СибГАУ, 2007. - С. 251-252.

Зарегистрированные программные системы

21. Семенкина М.Е., Семенкин Е.С. Программа для решения задач нейросетевого моделирования самоконфигурируемым алгоритмом генетического программирования. - М.: Роспатент, 2012. № гос. рег. 2012619346.

22. Семенкина М.Е., Семенкин Е.С. Программа для решения задач символьной регрессии самоконфигурируемым алгоритмом генетического программирования. - М.: Роспатент, 2012. № гос. рег. 2012619347.

23. Семенкина М.Е., Семенкин Е.С. Самоконфигурируемый генетический алгоритм для решения задач безусловной оптимизации. - М.: Роспатент, 2012. № гос. рег. 2012618746.

24. Семенкин Е.С., Семенкина М.Е. Алгоритм генетического программирования с обобщенным оператором множественной рекомбинации. - М.: ВНТИЦ, 2008. № гос. рег. 50200802149.а

25. Семенкин Е.С., Семенкина М.Е. Генетический алгоритм с модифицированным оператором множественной рекомбинации. - М.: ВНТИЦ, 2006. № гос. рег. 50200600370.

Семенкина Мария Евгеньевна

Самоконфигурируемые эволюционные алгоритмы моделирования и оптимизации

Автореферат

Подписано к печати                                         Формат 60х84/16

Уч. изд. л. 1.0                Тираж 100 экз.                Заказ № ________

Отпечатано в отделе копировальной и множительной техники СибГАУ.

660014, г. Красноярск, пр. им. газ. Красноярский рабочий, 31

Авторефераты по всем темам  >>  Авторефераты по техническим специальностям