Автоматизированное формирование нечетких классификаторов самонастраивающимися коэволюционными алгоритмами

• Автор: Сергиенко, Роман Борисович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Красноярск
• Количество страниц: 192 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. Обзор современных алгоритмов и методов оптимизации, классификации и интеллектуального анализа данных
1Л. Общая постановка задачи и обзор алгоритмов глобальной оптимизации
1.2. Понятие о коэволюционных алгоритмах
1.3. Коэволюционный алгоритм для автоматической настройки параметров генетического алгоритма
1.4. Условная оптимизация в генетических алгоритмах
1.5. Многокритериальная оптимизация в генетических алгоритмах
1.6. Классификация: постановка задачи и обзор алгоритмов
1.7. Интеллектуальный анализ данных (Data Mining)
1.8. Нечеткий классификатор Выводы
ГЛАВА 2. Самонастраивающийся кооперативно-конкурирующий коэволюционный алгоритм решения сложных задач оптимизации
2.1. Общая схема проведения исследований эффективности коэволюционного алгоритма
2.2. Исследование эффективности коэволюционного алгоритма для решения задач безусловной однокритериальной оптимизации
2.3. Разработка и исследование эффективности коэволюционного алгоритма для решения задач условной однокритериальной оптимизации
2.4. Разработка и исследование эффективности коэволюционного алгоритма для задач многокритериальной оптимизации
Выводы
Г ЛАВА 3. Разработка и апробация схемы формирования нечеткого классификатора с использованием самонастраивающегося коэволюционного алгоритма
3.1. Разработка схемы работы нечеткого коэволюционного классификатора с комбинированием Мичиганского и Питтсбургского подходов
3.2. Описание тестовых задач классификации
3.3. Результаты исследования нечеткого коэволюционного
классификатора на тестовых задачах
Выводы
ГЛАВА 4. Практическая реализация разработанных алгоритмов
4.1. Программная система «Коэволюционный алгоритм условной 124 многокритериальной оптимизации»
4.2. Решение задачи составления расписания посадок самолетов
4.3. Программная система «Нечеткий коэволюционный 138 классификатор»
4.4. Решение задачи обработки данных дистанционного 143 зондирования Земли космическими аппаратами
Выводы
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
СПИСОК ПУБЛИКАЦИЙ АВТОРА
ПРИЛОЖЕНИЯ

ВВЕДЕНИЕ
Актуальность. На сегодняшний день интенсивно развивается направление, связанное с интеллектуализацией методов обработки и анализа данных. Интеллектуальные системы анализа данных (ИСАД) [107] призваны минимизировать усилия лица, принимающего решения (ЛГ1Р), в процессе анализа данных, а также в настройке алгоритмов анализа. Многие ИСАД позволяют не только решать классические задачи принятия решения, но и способны выявлять причинно-следственные связи, скрытые закономерности в системе, подвергаемой анализу.
Одна из наиболее распространенных задач анализа данных — классификация. К задачам классификации сводятся диагностирование заболеваний в медицине, принятие решения о выдаче кредита клиенту банка, распознавание изображений и звука и многие другие задачи. На сегодняшний день создано большое количество разнообразных алгоритмов классификации [76] (в частности, различные алгоритмы автоматической классификации разрабатываются в научной школе Дорофеюка A.A. в Институте проблем управления РАН [95]), разработаны формализованные теории конструирования высокоэффективных композиций из этих алгоритмов (например, метод алгоритмических композиций научной школы академика РАН Журавлёва Ю.И [102]). Однако недостатком большинства из существующих алгоритмов классификации является работа по принципу «чёрного ящика» - невозможность явной интерпретации закономерностей, приводящих к отнесению объекта классификации к тому или иному классу.
Такого недостатка лишены методы вербального анализа решений, разработкой которых, в частности, занимаются в Институте системного анализа РАН [111], а также нечеткий классификатор, являющийся разработкой японских специалистов в области нечетких систем во главе с X. Ишибучи [33]. Нечеткий классификатор представляет собой базу нечетких правил. Каждое нечеткое правило — выражение причинно-следственной

пригодности осуществляется не в смысле расстояния между индивидами, а на основе Парето доминирования.
Процедура метода БРЕА [74];
Вход: N (размер популяции), N (размер внешнего множества), Т (максимальное число поколений), рс (вероятность скрещивания), рт (вероятность мутации).
Выход: А (недоминируемое множество).
Шаг 1. Инициализация: создать начальную популяцию Р0, согласно 1 этапу схемы общего эволюционного алгоритма, и пустое внешнее множество Р0 = 0. Положить /=0.
Шаг 2. Модернизация внешнего множества: положить промежуточное внешнее множество Р' = Рг .
а) скопировать индивидов, чьи векторы решений недоминируемы относительно т(Р,) в Р': Р'=Р'+ {71 / еР, лт{г) е р(т(Р1))}.
б) удалить тех индивидов из Р', чьи соответствующие векторы решений слабо доминируемы относительно т{Р'), то есть, если существует пара (/,_/) с индивидами /, у е Р' и т(1)>-т(]), то Р'=Р' -{]}.
в) уменьшить посредством кластеризации (с параметрами Р' и И) число индивидов, хранящихся во внешнем множестве, и поместить результирующее уменьшенное множество В Рил .
Шаг 3. Назначение пригодности: вычислить значения пригодности индивидов в Р, и Р( .
Шаг 4. Селекция: положить Р'= 0 и для 5 = 1,77 выполнить:
а) случайным образом выбрать двух индивидов /, у е Р1 + Р,,
б) если Р(/)<Р(у')5 то Р'=Р' + {г}, иначе Р'=Р' + {]} (в случае задачи минимизации).
Шаг 5. Рекомбинация.