Содержание к диссертации
Введение
ГЛАВА 1. Обзор современных алгоритмов и методов оптимизации, классификации и интеллектуального анализа данных 11
1.1. Общая постановка задачи и обзор алгоритмов глобальной оптимизации 11
1.2. Понятие о коэволюционных алгоритмах 15
1.3. Коэволюционный алгоритм для автоматической настройки параметров генетического алгоритма 21
1.4. Условная оптимизация в генетических алгоритмах 26
1.5. Многокритериальная оптимизация в генетических алгоритмах 32
1.6. Классификация: постановка задачи и обзор алгоритмов 40
1.7. Интеллектуальный анализ данных (Data Mining) 45
1.8. Нечеткий классификатор 48
Выводы 55
ГЛАВА 2. Самонастраивающийся кооперативно-конкурирующий коэволюционный алгоритм решения сложных задач оптимизации 57
2.1. Общая схема проведения исследований эффективности коэволюционного алгоритма 57
2.2. Исследование эффективности коэволюционного алгоритма для решения задач безусловной однокритериальной оптимизации 63
2.3. Разработка и исследование эффективности коэволюционного алгоритма для решения задач условной однокритериальной оптимизации 70
2.4. Разработка и исследование эффективности коэволюционного алгоритма для задач многокритериальной оптимизации 93
Выводы 102
ГЛАВА 3. Разработка и апробация схемы формирования нечеткого классификатора с использованием самонастраивающегося коэволюционного алгоритма 105
3.1. Разработка схемы работы нечеткого коэволюционного классификатора с комбинированием Мичиганского и Питтсбургского подходов 105
3.2. Описание тестовых задач классификации 111
3.3. Результаты исследования нечеткого коэволюционного классификатора на тестовых задачах 115
Выводы 121
ГЛАВА 4. Практическая реализация разработанных алгоритмов 124
4.1. Программная система «Коэволюционный алгоритм условной многокритериальной оптимизации» 124
4.2. Решение задачи составления расписания посадок самолетов 130
4.3. Программная система «Нечеткий коэволюционный классификатор» 138
4.4. Решение задачи обработки данных дистанционного зондирования Земли космическими аппаратами 143
Выводы 149
Заключение 151
Список литературы 153
Список публикаций автора 166
Приложения 170
Введение
- Коэволюционный алгоритм для автоматической настройки параметров генетического алгоритма
- Исследование эффективности коэволюционного алгоритма для решения задач безусловной однокритериальной оптимизации
- Результаты исследования нечеткого коэволюционного классификатора на тестовых задачах
- Программная система «Нечеткий коэволюционный классификатор»
Введение к работе
Актуальность. На сегодняшний день интенсивно развивается направление, связанное с интеллектуализацией методов обработки и анализа данных. Интеллектуальные системы анализа данных (ИСАД) [107] призваны минимизировать усилия лица, принимающего решения (ЛПР), в процессе анализа данных, а также в настройке алгоритмов анализа. Многие ИСАД позволяют не только решать классические задачи принятия решения, но и способны выявлять причинно-следственные связи, скрытые закономерности в системе, подвергаемой анализу.
Одна из наиболее распространенных задач анализа данных - классификация. К задачам классификации сводятся диагностирование заболеваний в медицине, принятие решения о выдаче кредита клиенту банка, распознавание изображений и звука и многие другие задачи. На сегодняшний день создано большое количество разнообразных алгоритмов классификации [76] (в частности, различные алгоритмы автоматической классификации разрабатываются в научной школе Дорофеюка A.A. в Институте проблем управления РАН [95]), разработаны формализованные теории конструирования высокоэффективных композиций из этих алгоритмов (например, метод алгоритмических композиций научной школы академика РАН Журавлёва Ю.И [102]). Однако недостатком большинства из существующих алгоритмов классификации является работа по принципу «чёрного ящика» - невозможность явной интерпретации закономерностей, приводящих к отнесению объекта классификации к тому или иному классу.
Такого недостатка лишены методы вербального анализа решений, разработкой которых, в частности, занимаются в Институте системного анализа РАН [111], а также нечеткий классификатор, являющийся разработкой японских специалистов в области нечетких систем во главе с X. Ишибучи [33]. Нечеткий классификатор представляет собой базу нечетких правил. Каждое нечеткое правило — выражение причинно-следственной закономерности отнесения объекта к какому-либо классу в лингвистической форме, доступное для прямого восприятия экспертом. Таким образом, нечеткий классификатор представляет собой одновременно алгоритм классификации и инструмент интеллектуального анализа данных (Data Mining) для обнаружения скрытых знаний и закономерностей.
Формирование нечеткого классификатора сводится к задаче оптимизации - выбору наилучшей базы нечетких правил из множества существующих. Данная задача оптимизации отличается существенной вычислительной и алгоритмической сложностью, обусловленной высокой размерностью решаемой задачи оптимизации, процедурно заданной целевой функцией (вычисление которой, как правило, трудоёмко), наличием дискретных переменных и др. В такой ситуации использование классических методов оптимизации неприемлемо. Для задачи формирования нечеткого классификатора целесообразно использовать эволюционные алгоритмы [47], которые хорошо зарекомендовали себя при решении именно такого рода задач оптимизации.
Однако применение эволюционных алгоритмов оптимизации сопряжено с другой серьезной проблемой — высокой сложностью и трудоемкостью настройки алгоритмов на решаемую задачу в связи с большим числом возможных комбинаций их настроек (селекции, мутации, скрещивания и некоторых других). Эффективность одной и той же настройки на разных задачах и различных настроек на одной и той же задаче может изменяться в очень широком диапазоне. Поэтому выбор настроек наугад является неприемлемым, так как многие комбинации параметров алгоритма оказываются неработоспособными, а тщательная настройка под новую задачу является чрезмерно трудоемкой, особенно для таких вычислительно сложных задач, как формирование нечеткого классификатора. Для решения проблемы предлагается использование так называемого коэволюционного подхода для адаптации стратегии оптимизации [96], позволяющего
отказаться от выбора настроек эволюционного алгоритма за счет
взаимодействия (конкуренции и кооперации) множества эволюционных алгоритмов с различными настройками.
Таким образом, разработка и исследование самонастраивающихся коэволюционных алгоритмов и дальнейшее их использование в системах формирования нечетких классификаторов для одновременного решения задач классификации и интеллектуального анализа данных с выявлением скрытых знаний, является актуальной научно-технической задачей.
Целью диссертационной работы является повышение эффективности, быстродействия и адаптивности эволюционного метода формирования нечеткого классификатора с использованием самонастраивающихся коэволюционных алгоритмов.
Сформулированная цель предопределила следующую совокупность решаемых задач:
Выполнить аналитический обзор существующих методов классификации и оптимизации с целью установления целесообразности использования нечеткого классификатора, эволюционных алгоритмов как метода формирования нечетких систем, коэволюционных алгоритмов как инструмента автоматизации выбора настроек эволюционного алгоритма.
Провести комплексные исследования эффективности коэволюционного подхода как инструмента автоматизации выбора настроек эволюционного алгоритма на различных классах задач.
Разработать метод формирования нечетких классификаторов с использованием коэволюционных алгоритмов, обладающий преимуществами перед существующими методами.
Реализовать разработанные алгоритмы в виде программных систем и апробировать их на реальных практических задачах.
Методы исследования. При выполнении диссертационной работы
использовались методы теории оптимизации, теории вероятностей и
математической статистики, анализа данных, методы снижения размерности,
теории эволюционных алгоритмов, теории нечетких систем; методики
разработки и исследования моделей и алгоритмов анализа данных, выявления закономерностей в данных и их извлечения, применения бионических принципов и моделей в информационных технологиях.
Научная новизна результатов диссертационной работы состоит в следующем:
Разработан новый самонастраивающийся коэволюционный алгоритм условной оптимизации, отличающийся от известных самонастройкой метода учёта ограничений и пропорционально-групповым способом реализации модифицированного оператора миграции.
Разработан новый самонастраивающийся коэволюционный алгоритм многокритериальной оптимизации, отличающийся от известных отсутствием независимой работы индивидуальных алгоритмов в коэволюционной комбинации и способом оценивания эффективности индивидуальных алгоритмов.
Разработан новый метод формирования нечеткого классификатора, отличающийся от известных схемой комбинирования Мичиганского и Питтсбургского подходов, наличием формализованной процедуры отбора стартовых нечетких правил и использованием самонастраивающихся коэволюционных алгоритмов.
Самонастраивающийся коэволюционный алгоритм безусловной однокритериальной оптимизации обеспечивает эффективность, не уступающую стандартному генетическому алгоритму с настройками, обеспечивающими среднюю эффективность.
Эффективность самонастраивающегося коэволюционного алгоритма условной однокритериальной оптимизации с использованием разработанной пропорционально-групповой схемы миграции превосходит эффективность стандартного генетического алгоритма с наилучшими настройками.
Разработанный новый метод формирования нечетких классификаторов самонастраивающимися коэволюционными алгоритмами позволяьг получать эффективную базу знаний с небольшим числом правил.
Теоретическая значимость результатов диссертационного исследования состоит в том, что разработаны, исследованы и апробированы новые коэволюционные алгоритмы для автоматизации выбора настроек генетических алгоритмов и новый метод формирования нечеткого классификатора самонастраивающимися коэволюционными алгоритмами для решения задач классификации и интеллектуального анализа данных, что является существенным вкладом в теорию и практику исследования методов преобразования информации в данные и знания, методов машинного обучения и обнаружения новых знаний.
Практическая ценность. Разработанные в ходе исследования
алгоритмы и методы реализованы в виде двух программных систем:
«Коэволюционный алгоритм условной многокритериальной оптимизации» и «Нечеткий коэволюционный классификатор». Первая программная система предназначена для решения различных задач оптимизации. Программная система использовалась для решения следующих практических задач: формирование оптимального инвестиционного портфеля предприятия, формирование оптимального кредитного портфеля банка, планирование расписания посадок самолётов.
Вторая программная система предназначена для решения задач классификации с одновременным выявлением лингвистических знаний в соответствующих проблемных областях. Программная система апробировалась при решении практических задач диагностики заболевания печени, выдачи банковского кредита физическим лицам, классификации видов ириса, распознавания спутниковых изображений и некоторых других.
Реализация результатов работы. Программные системы использовались в качестве лабораторных установок студентами Института информатики и телекоммуникаций СибГАУ по направлению «Системный анализ и управление» при выполнении курсовых работ. Результаты решения программной системой «Нечеткий коэволюционный классификатор» задачи распознавания спутниковых изображений использовались в рамках проекта «Студенческий спутник СибГАУ» в сотрудничестве с Центром управления полетами СибГАУ.
Полученные результаты применялись в ходе выполнения работ по созданию систем управления сложными механическими системами (двойной перевернутый маятник) во время стажировки в Высшей технической школе г. Ульм (Hochschule Ulm), ФРГ, 2008 г.
Диссертационная работа поддержана Фондом содействия развитию
малых форм предприятий в научно-технической сфере по программе
«У.М.Н.И.К.» («Участник молодежного научно-инновационного конкурса»)
в рамках НИОКР «Разработка коэволюционного вероятностного алгоритма
для автоматизированного проектирования интеллектуальных
информационных технологий» на 2008-2011 гг. Работа финансировалась из средств госбюджета в рамках НИР Б 1.01.05 «Разработка и исследование бионических методов идентификации и оптимизации сложных систем» ЕЗН СибГАУ, а также в рамках выполнения проекта «Система поддержки принятия решения при проектировании интегрированных систем безопасности», ставшего победителем конкурса инновационных проектов СибГАУ на 2007-2008 гг. Работа поддержана грантом в рамках конкурса научно-технического творчества молодежи города Красноярска «НТТМ- 2010». Диссертационное исследование удостоено диплома 1 степени Российской ассоциации искусственного интеллекта.
Диссертационное исследование проводилось также в рамках НИР № 2.1.1./2710 «Математическое моделирование инвестиционного развития региональных экономических систем» АВЦП «Развитие научного потенциала высшей школы (2009-2010 годы)» и НИР НК-136П/3 "Автоматизированная система решения сложных задач глобальной оптимизации многоагентными стохастическими алгоритмами" ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009 - 2013 годы.
Основные защищаемые положения:
4. Нечеткий классификатор, формируемый разработанным методом, превосходит по точности классификации другие известные подходы.
Публикации. По теме диссертации опубликовано двадцать три работы, в том числе четыре в изданиях из перечня ВАК, а также зарегистрированы три программные системы.
Апробация работы.
Результаты диссертационной работы были доложены и обсуждены на Всемирном конгрессе по вычислительному интеллекту (IEEE World Congress on Computational Intelligence (WCCI'2010), Barcelona, Spain, 2010); Национальной конференции по искусственному интеллекту с международным участием КИИ-2010 (Тверь, 2010); Всероссийской научной конференции «Теория и практика системного анализа» (Рыбинск, Институт системного анализа РАН и РГАТА, 2010); Международных научно- технических конференциях «Интеллектуальные системы» AIS'08 и AIS'09 (Дивноморское, 2008, 2009), на Всероссийских научно-практических конференциях с международным участием «Информационные технологии и математическое моделирование» (Томский университет, 2007, 2009), Конференции-конкурсе «Технологии Microsoft в теории и практике программирования» (Томск, ТПУ, 2010), Всероссийских конференциях молодых ученых по математическому моделированию и информационным технологиям (Красноярск, ИВМ СО РАН, 2006, и Новосибирск, ИВТ СО РАН, 2007), на Международных научно-практических конференциях «Решетневские чтения» (Красноярск, СибГАУ, 2006-2009), на научном семинаре в Институте проблем управления РАН (Москва, 2010), а также на ряде молодежных и студенческих конференций.
Структура работы. Диссертация содержит 152 страницы основного текста и состоит из введения, четырёх глав, заключения, списка литературы на 157 источников и 8 приложений, содержащих 23 страницы, основной текст диссертации включает 47 таблиц, 26 рисунков.
Коэволюционный алгоритм для автоматической настройки параметров генетического алгоритма
Наиболее распространенным подходом в кооперативной коэволюции является разбиение исходного множества параметров задачи на непересекающиеся подмножества. Таким образом, каждый индивидуальный алгоритм в коэволюции работает со своим набором параметров. Особенностью такого подхода является то, что пригодность индивида в отдельной подпопуляции вычисляется только с использованием информации об индивидах в других подпопуляциях, т.к. исходная целевая функция зависит от всего множества параметров. Разработчики кооперативной коэволюции дают следующее определение данного алгоритма: «кооперативная коэволюция — эволюционный алгоритм (или группа алгоритмов), в котором пригодность индивида зависит от других индивидов» [72]. Существуют различные архитектуры взаимодействия алгоритмов в кооперативной коэволюции, которые определяют правило вычисления пригодности индивидов [55].
Следует отметить, что кооперативная коэволюция не всегда подразумевает разбиение множества параметров на подмножества. Иногда осуществляется декомпозиция целевого функционала (в тех случаях, когда это возможно), а иногда декомпозиция множества параметров и целевого функционала одновременно.
Главные проблемы в кооперативной коэволюции — сложность задачи разбиения множества параметров на подмножества, противоречивые эффекты от взаимодействия подпопуляций [72], преобладание в стратегии эволюции только одной популяции и некоторые другие.
В последние годы появилось ряд работ, направленных на повышение эффективности кооперативной коэволюции. Это такие работы, как настройка кооперативного коэволюционного алгоритма с помощью анализа чувствительности с целью балансировки подпопуляций для приближения к идеальной схеме «сотрудничества» (collaboration) [51], кооперативный коэволюционный алгоритм с самонастройкой параметров алгоритма методом кодирования параметров в хромосому [31], кооперативный коэволюционный алгоритм с адаптивным разбиением параметров на подмножества на основе корреляционного анализа [57].
Принципиально иным является конкурирующий подход в коэволюции. В ходе конкурирующей коэволюции осуществляется борьба индивидуальных алгоритмов в той или иной форме. Возможны различные графы взаимодействия алгоритмов. Наиболее распространенным является схема в виде полносвязного графа, т.е. происходит конкуренция каждого алгоритма с каждым. Хотя возможны и другие схемы, например, гиперкуб, решетка или даже схема в виде дерева. В последнем случае речь идет об иерархической структуре коэволюционного алгоритма [92].
Подход в использовании конкурирующей коэволюции, предложенный в [49] под названием Breeder Genetic Algorithm, заключается в том, что индивидуальные генетические алгоритмы в коэволюционной комбинации обладают различными стратегиями функционирования (различны операторы генетического алгоритма: тип селекции, скрещивания, мутации, схемы формирования нового поколения). В этом случае идея конкурирующей коэволюции состоит в том, что алгоритм, обладающей наилучшей стратегией для оптимизации конкретной задачи, получает наибольший ресурс для своей работы. Критерий оценки индивидуальных алгоритмов — эффективность решения задачи оптимизации. Выигрыш победившего алгоритма — ресурс (часть размера популяций), отнимаемый у проигравших алгоритмов. Таким образом, автоматизируется очень актуальная для эволюционных методов принятия решения задача выбора алгоритма с наилучшими настройками для оптимизации выбранной задачи. Т.е. конкурирующий коэволюционный алгоритм для адаптации стратегии оптимизации — это самонастраивающаяся (самоадаптирующаяся) оптимизационная процедура.
В настоящее время в научных публикациях термином «конкурирующая коэволюция» называют несколько совершенно различных подходов, что вносит некоторую путаницу в понимание этого метода. Так, в [58] конкурирующим коэволюционным алгоритмом называется схема взаимодействия двух субпопуляций по схеме «хозяин-паразит». В алгоритме не происходит перераспределения ресурсов, но пригодность каждого индивида определяется его сравнением с индивидами из противоположной субпопу яции. В [50] описывается аналогичный подход, но только с использованием одной популяции — для каждого индивида при определении пригодности выбирается К случайных оппонентов из той же популяции. В [64] под конкурирующей коэволюцией понимается, по сути, схема кооперативного коэволюционного алгоритма - происходит декомпозиция множества переменных и целевого функционала. Каждой переменной соответствует отдельная подпопуляция, а также отдельная локальная целевая функция. Композиция локальных целевых функций образует исходную ЦФ. Алгоритм называется «конкурирующим», т.к. взаимодействие подпопуляций происходит в виде игры - каждая подпопуляция стремится оптимизировать свою целевую функцию, а конечное решение получается достижением точки равновесия Нэша, согласно теории игр. Однако с методологической точки зрения данный подход всё же правильнее относить к классу кооперативных коэволюционных алгоритмов.
Существует подход использования конкурирующей коэволюции с перераспределением ресурсов, в котором индивидуальные алгоритмы отличаются не стратегией оптимизации, а областями поискового пространства [23]. В этом методе исходное поисковое пространство разбивается на подмножества, причем частично пересекающиеся, каждому из которых соответствует отдельный алгоритм. Динамическое перераспределение ресурсов обеспечивает преимущество того алгоритма, чье поисковое пространство соответствует глобальному оптимуму.
Исходная идея конкурирующей коэволюции, использующей индивидуальные генетические алгоритмы с различными стратегиями оптимизации, получила дальнейшее развитие в работах Е.С. Семёнкина [123]. Помимо оператора перераспределения ресурсов в коэволюцию был введен оператор миграции, обеспечивающий обмен наилучшими индивидами между алгоритмами. В такой форме коэволюционный алгоритм обеспечивает не только ресурсное преимущество алгоритма с наилучшими настройками, но позволяет также использовать эффект от взаимодействия алгоритмов с различными свойствами между собой. Например, положительный эффект может иметь взаимодействие алгоритма с глобальными поисковыми свойствами с алгоритмом со свойством локальной сходимости. Таким образом, введение оператора миграции теоретически должно существенно повысить эффективность традиционной схемы конкурирующего коэволюционного алгоритма. Проведенные исследования [96], в т.ч. и в данной работе, подтверждают целесообразность использования такого «кооперативно-конкурирующего» подхода в коэволюции при решении разнообразных задач оптимизации.
Практически во всех исследованиях, посвященных конкурирующему коэволюционному алгоритму, отмечается одна и та же особенность — эффективность включения незначительного числа индивидуальных алгоритмов в коэволюционную комбинацию (от 4 до 20). При увеличении числа алгоритмов наблюдается существенное падение эффективности.
В настоящее время публикуются работы, связанные с теоретическим обоснованием различных схем коэволюционного алгоритма с использованием математического аппарата теории игр: [16, 42, 19].
Козволюционные алгоритмы используются не только как инструмент оптимизации, но также как и инструмент моделирования различных процессов, связанных с эффектом коллективного поведения [16]. Это биологические, экономические и социальные процессы. Разработаны алгоритм коэволюционного обучения, используемый в различных задачах анализа данных [38], алгоритм коэволюционного генетического программирования [97] для решения задач символьной регрессии.
Исследование эффективности коэволюционного алгоритма для решения задач безусловной однокритериальной оптимизации
Подобная процедура обеспечивает более репрезентативное распределение недоминируемых решений по сравнению с кластеризацией в SPEA.
5) В селекции принимают участие только индивиды из внешнего множества. Это позволяет использовать в алгоритме не только турнирную селекцию, но и другие ее типы — пропорциональную, ранговую. Кроме того, при совпадении значений N и N множества Р и Р, по сути, становятся идентичными. Это позволяет работать только с одной популяцией (именно такая схема используется в настоящей диссертации).
В работе [75] приводятся результаты экспериментального сравнения эффективности SPEA2 по сравнению с SPEA, а также со «свежими» алгоритмами многокритериальной оптимизации в ГА NSGA-II и PESA (Pareto Envelope-Based Selection Algorithm, 2000 г.) [11] на тестовых задачах вещественной и комбинаторной многокритериальной оптимизации. Преимущество SPEA над VEGA, FFGA, NPGA и NSGA было показано в более ранних исследованиях. По результатам исследований было выяснено преимущество SPEA2 над SPEA и PESA на всех тестовых задачах. SPEA2 в некоторых случаях уступал NSGA-II на задачах малой размерности, однако при увеличении размерности превосходство SPEA2 росло.
Алгоритмы многокритериальной оптимизации в ГА в некоторых работах реализованы в варианте кооперативной коэволюции. Так, в [43] кооперативный коэволюционный алгоритм по отдельности применяется к реализации FFGA (MOGA), NPGA, NSGA и CNSGA. NSGA-II в виде кооперативной коэволюции представлен в [32]. Распределенный кооперативный коэволюционный алгоритм многокритериальной оптимизации рассматривается в [68].
В работе [69] используется конкурирующий коэволюционный алгоритм по схеме выбора К случайных оппонентов [50] для определения пригодности индивидов при реализации многокритериальной оптимизации по схеме SPEA2.
Отдельной проблемой в многокритериальной оптимизации является сужение найденного множества Парето [109].
Распознавание (классификация) - это отнесение конкретного объекта (реализации), представленного значениями его свойств (признаков), к одному из фиксированного перечня образов (классов) по определённому решающему правилу в соответствии с поставленной целью [91]. Классификация относится к классу задач так называемого машинного обучения (Machine Learning).
Перечень образов может задаваться распознающей системе извне (учителем). Например, если система предназначена для автоматического стенографирования, то распознаваемыми образами являются фонемы — элементы устной речи.
Во многих случаях распознающая система сама формирует перечень распознаваемых образов. В литературе этот процесс называют обучением без учителя, самообучением, кластерным анализом (таксономией). Эта функция реализуется чаще всего в исследовательском процессе: естественнонаучная классификация, анализ данных, выявление закономерностей и т.п.
Далее речь будет идти о первом случае - распознавании при наличии обучающей выборки. В этом случае необходимым является наличие экзаменующей выборки, не используемой при конструировании алгоритма классификации, но необходимой для проверки эффективности алгоритма. Обучающая выборка может использоваться как экзаменующая при использовании метода скользящего экзамена (исключение экзаменуемой точки из обучающей выборки и соответствующая перестройка алгоритма классификации) [121]. Важным качеством алгоритма классификации является обобщающая способность (способность эффективно работать на тестовой выборке, существенно отличной от обучающей).
Отбор информативных признаков для распознавания — отдельная сложная задача, которую принято называть факторным анализом, или снижением размерности [76].
При известных плотностях распределения информативных признаков для каждого класса существует оптимальное в смысле критерия минимизации ошибки классификации решающее правило — решающее Байесовское правило [121].
Однако получение достаточно точных плотностей распределения информативных признаков - задача также непростая, поэтому прямое использование решающего Байесовского правила не всегда возможно.
К детерминистским методам классификации относятся следующие [91]: - метод построения эталонов: для каждого класса по обучающей выборке строится эталон, имеющий в качестве значений параметров оценки их математических ожиданий для данного класса; классифицируемый объект относится к классу, расстояние до эталона которого минимально. - метод дробящихся эталонов: в области пересечения классов формируются дополнительные уточняющие эталоны по специальному правилу. - линейные решающие правила: строится разделяющая классы поверхность в пространстве информативных признаков в виде гиперплоскости; - метод ближайших соседей: для отнесения объекта к конкретному классу определяется класс ближайшего к нему элемента из обучающей выборки; - метод потенциальных функций: решающее правило строится в виде специальной потенциальной функции; - структурные (лингвистические) решения: решающие правила в виде деревьев решений. К статистическим методам классификации принято относить методы, предназначенные для получения оценок плотности распределения информативных признаков для последующего применения Байесовской теории принятия решений. Различают параметрическое оценивание распределений (метод максимума правдоподобий) и непараметрическое (метод К блиэюайших соседей [121], непараметрическая оценка Розенблатта-Парзена [108]/ Выделяют последовательные процедуры распознавания, в которых происходит последовательное получение и использование измерений.
Для решений задач классификации используют технологии интеллектуального анализа данных. В первую очередь, это нейронные сети [82], основная идея которых исходит из персептрона, предложенного Э. Розенблаттом в 1957 г. Нейронные сети на сегодняшний день исключительно успешно зарекомендовали себя при решении разнообразных задач распознавания. В первую очередь, это распознавание изображений и аудиосигнала.
Результаты исследования нечеткого коэволюционного классификатора на тестовых задачах
Обоснование коэволюционного алгоритма как инструмента автоматизации выбора настроек генетического алгоритма заключается в сравнительном исследовании эффективности коэволюционного алгоритма и стандартных генетических алгоритмов с различными настройками на множестве тестовых задач. Отдельно рассматриваются следующие классы задач оптимизации: -задачи безусловной однокритериальной оптимизации (п. 2.2); - задачи условной однокритериальной оптимизации (п. 2.3); -задачи безусловной и условной многокритериальной оптимизации (п. 2.4). Для всех классов задач оптимизации исследования проводятся по следующей общей схеме: - формирование множества комбинаций настроек стандартного генетического алгоритма; - мь огократный запуск генетического алгоритма для каждой комбинации настроек алгоритма на всех тестовых задачах; - определение наихудшего, наилучшего и среднего стандартного генетического алгоритма в смысле выбранных показателей эффективности работы алгоритма для каждой тестовой задачи; -многократный запуск коэволюционного алгоритма, включающего в качестве подпопуляций все различные индивидуальные генетические алгоритмы, на всех тестовых задачах (возможно тестирование промежуточных коэволюционных комбинаций, включающих не все различные индивидуальные ГА); - сравнение эффективности коэволюционного алгоритма и эффективности наихудшего, среднего и наилучшего стандартного генетического алгоритма. Рассмотрим показатели эффективности работы алгоритма на задачах однокритериальной оптимизации. Показатели эффективности при решении многокритериальных задач оптимизации рассматриваются в п. 2.4.1 настоящей диссертации.
Основным критерием эффективности работы алгоритма оптимизации при известном истинном оптимуме будем полагать надежность — отношение числа запусков алгоритма, в которых с заданной точностью был найден истинный оптимум, к общему числу запусков. Заданная точность нахождения оптимума определяется максимальным шагом дискретизации вещественных переменных (максимальный шаг дискретизации, задаваемый исследователем, может быть несколько больше реально используемого в алгоритме ввиду специфики бинаризации переменных в ГА — п. 1.4). Истинный оптимум считается найденным с заданной точностью, если модуль разности между значением каждой переменной найденного алгоритмом решения и истинного оптимума не превышает максимального шага дискретизации переменной, помноженного на 10: х - д:, 10 йг, / = \,п, где / номер переменной, п — общее число переменных в задаче оптимизации, лг( — значение переменной истинного оптимума, дг,- — значение переменной наилучшего найденного алгоритмом решения, с11 - максимальный шаг дискретизации /-й переменной. В данной работе значение (1, используется неизменным для всех В случае наличия в задаче оптимизации бинарных переменных истинный оптимум следует считать найденным только при строгом совпадении значений бинарных переменных. Очевидно, что алгоритм с более высоким значением надежности является более эффективным.
В случае неизвестности значения истинного оптимума основным показателем эффективности работы алгоритма считается наилучшее значение голевой функции найденного алгоритмом решения, усредненное по нескольким многократным запускам. Также вычисляется среднее значение голевой функции, вычисляемое по всем найденным решениям в многократном запуске.
При равенстве или статистической неразличимости значений основных показателей эффективности работы алгоритма для сравнительного анализа используется средний номер поколения, на котором впервые алгоритмом получено итоговое решение. Данный показатель характеризует скорость сходимости алгоритма.
Для каждого алгоритма осуществляется 5 или 10 стократных запусков на каждой тестовой задаче. В каждом стократном запуске вычисляются показатели эффективности работы алгоритма. Наличие выборок из 5 или 10 значений показателей эффективности позволяет производить анализ выборок на существенную статистическую различимость между собой с использованием специальных методов, например, рангового критерия Вилкоксона [85]. Подобные статистические исследования обеспечивают более достоверный вывод, чем простое сравнение двух случайных величин.
Средний стандартный генетический алгоритм либо определяется вычислением средних значений показателей эффективности работы всех различных стандартных ГА на данной задаче оптимизации, либо определяется как средний по медиане, т.е. как средний по номеру алгоритм после упорядочиванию по основному показателю эффективности. Необходимым условием проведения исследований является равенство (или минимально возможная разница) ресурса стандартных генетических алгоритмов и коэволюционного алгоритма. Ресурс стандартного ГА равен произведению размера популяции на число поколений, ресурс коэволюционного алгоритма равен произведению начального размера подпопуляций на число подпопуляций (индивидуальных алгоритмов в коэволюционной комбинации) и на число поколений. Естественным является также требование равенства числа поколений в обоих случаях. Общими для всех классов задач оптимизации являются следующие параметры генетического алгоритма: тип селекции, тип скрещивания, вероятность мутации. В данной работе вероятность мутации не является настраиваемым параметром, т.к. используется адаптивная мутация, предложенная в [86] и основанная на идее поддержания разнообразия популяции. На каждом шаге работы алгоритма вероятность мутации рассчитывается автоматически по следующей формуле: где п - длина хромосомы; — разброс (дисперсия) точек в пространстве решений (бинаризованном) на (к-1)-м поколении; Хк - разброс точек, в пространстве решений на к-м поколении; функция определяет силу мутации. Начальное значение = 1. Ограничение сверху для вероятности мутации составляет 0,5, т.к. при увеличении этого значения мутация начинает, по сути, превращаться в оператор инверсии битов и теряет свой первоначальный смысл. Таким образом, вероятность мутации увеличивается, если решения-индивиды начинают группироваться около какого-либо локального оптимума, и уменьшается, когда решения распределяются в пространстве более широко.
Программная система «Нечеткий коэволюционный классификатор»
Значения показателей эффективности худших алгоритмов приведены для иллюстрации степени разброса этих значений. Видно, что для задач условной оптимизации разброс в эффективности стандартных ГА значительнее, чем для задач безусловной оптимизации (таблица 2.6.). К тому же существенно больше общее число различных комбинаций настроек ГА.
На всех тестовых задачах условной оптимизации с ограничениями- неравенствами и на практических задачах, которые также являются задачами с ограничениями-неравенствами, видно существенное повышение средних показателей эффективности на каждом этапе «коэволюционной свертки», а на большинстве задач и наилучших показателей. При этом на каждом этапе происходит существенное сокращение разброса значений показателей эффективности.
Итоговый коэволюционный алгоритм (этап 4) работает эффективнее самого лучшего индивидуального алгоритма на семи из восьми тестовых задачах с ограничениями-неравенствами, а также на обеих практических задачах. Наиболее ярко это выражено на задачах 5 и 7: надежность наилучших индивидуальных алгоритмов составляет 29,2% и 32,0%, а итогового коэволюционного алгоритма 99,0% и 99,6% соответственно при одинаковом ресурсе. Таким образом, на задачах условной оптимизации с ограничениями-неравенствами имеет место значительный положительный эффект взаимодействия алгоритмов между собой, что не наблюдается в такой степени на задачах безусловной оптимизации - по результатам исследований [6] был сделан общий вывод, что коэволюционный алгоритм на задачах безусловной оптимизации работает лучше алгоритма со средними настройками, но все-таки может уступать алгоритму с наилучшими настройками.
В некоторых случаях на промежуточных этапах свертки алгоритмов (для задачи 6 — на этапе индивидуальных алгоритмов) встречаются коэволюционные комбинации, которые несколько превосходят итоговый коэволюционный алгоритм. Так, на задачах 3 и 8 итоговая коэволюция обеспечивает максимальную надежность, однако на предыдущих этапах встречаются комбинации алгоритмов, которые дают улучшение по скорости сходимсоти в среднем на 1 и 3 поколения соответственно. В задаче 6 есть промежуточная «неполная» комбинация алгоритмов и индивидуальный алгоритм, которые дают выигрыш по надежности на 2% по сравнению с итоговым коэволюционным алгоритмом. Для инвестиционной задачи «неполная» комбинация на этапе 2 дает выигрыш в 2% по надежности и в 5 поколений по скорости сходимости. Для банковской задачи на этапе 4 существует комбинация, дающая выигрыш в прибыли по сравнению со средним максимальным решением на этапе 4 в 1 267,2 р. (0,00063% от значения целевой функции). Однако, эти отличия можно считать малозначительными, т.к. выигрыш до 5 поколений по скорости сходимости или до 2% по надежности не сопоставим с затратами на поиск подходящей комбинации алгоритмов.
Схожие результаты получены на задачах с ограничениями-равенствами. Итоговый коэволюционный алгоритм значительно лучше среднего индивидуального на обеих задачах и значительного эффективнее лучшего индивидуального на задаче 9 (рост надежности с 56,8% до 80,2%), на второй задаче наблюдается снижение надежности на 3 процента с 37,2% до 34%. Однако при этом на обеих задачах встречаются «неполные» коэволюционные комбинации, которые дают выигрыш в надежности по сравнению с итоговой коэволюцией в среднем на 13% и 11% соответственно, что не может быть признано малозначительным.
Если же проводить сравнение итогового коэволюционного алгоритма только со стандартными генетическими алгоритмами, то коэволюционный алгоритм превосходит стандартный ГА с наилучшими настройками на всех тестовых и практических задачах условной оптимизации, за исключением задач 6 и 10 с незначительным падением надежности на 2-3%. При этом коэволюционный алгоритм существенно превосходит стандартный ГА с наилучшими настройками по скорости сходимости на всех тестовых задачах. На инвестиционной задаче наблюдается незначительное уменьшение скорости сходимости, существенное уменьшение средней скорости сходимости на банковской задаче связано с большим разбросом в значениях номера поколения для нахождения решения на первых этапах.
Интересной особенностью коэволюционного алгоритма условной оптимизации является динамика перераспределения ресурсов между алгоритмами. Ниже приведены графики этого процесса на тестовых и практических задачах при усреднении по 100 запускам. По оси абсцисс отложен номер интервала адаптации, по оси ординат размер популяции для каждого алгоритма.
