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

Сергиенко, Роман Борисович

Теоретические основы информатики

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

кандидата технических наук: Сергиенко, Роман Борисович
город: Красноярск
год: 2010
специальность ВАК РФ: 05.13.17
цена: 450 рублей

Диссертация по информатике, вычислительной технике и управлению на тему «Автоматизированное формирование нечетких классификаторов самонастраивающимися коэволюционными алгоритмами»

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

СЕРГИЕНКО РОМАН БОРИСОВИЧ

АВТОМАТИЗИРОВАННОЕ ФОРМИРОВАНИЕ НЕЧЕТКИХ КЛАССИФИКАТОРОВ САМОНАСТРАИВАЮЩИМИСЯ КОЭВОЛЮЦИОННЫМИ АЛГОРИТМАМИ

05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ

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

2 5 моя 7010

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

004614471

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

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

Семенкин Евгений Станиславович

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

Миркес Евгений Моисеевич

кандидат технических наук Цой Юрий Робертович

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

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

Защита состоится «10» декабря 2010 г. в 14 часов на заседании диссертационного совета Д 212.099.11 при Сибирском федеральном университете по адресу 660074, г. Красноярск, ул. Киренского, 26, ауд. УЖ 115.

С диссертацией можно ознакомиться в библиотеке Сибирского федерального университета по адресу: г. Красноярск, ул. Киренского, 26, ауд. Г 2-74.

Автореферат разослан «29» октября 2010 г.

Ученый секретарь диссертационного совета, кандидат технических наук, доцент

Покидышева Л.И.

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

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

Одна из наиболее распространенных задач анализа данных -классификация. К задачам классификации сводятся диагностирование заболеваний в медициие, принятие решения о выдаче кредита клиенту банка, распознавание изображений и звука и многие другие задачи. На сегодняшний день создано большое количество разнообразных алгоритмов классификации (в частности, различные алгоритмы автоматической классификации разрабатываются в научной школе Дорофеюка A.A. в Институте проблем управления РАН), разработаны формализованные теории конструирования высокоэффективных композиций из этих алгоритмов (например, метод алгоритмических композиций научной школы академика РАН Журавлёва Ю.И). Однако недостатком большинства из существующих алгоритмов классификации является работа по принципу «чёрного ящика» — невозможность явной интерпретации закономерностей, приводящих к отнесению объекта классификации к тому или иному классу.

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

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

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

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

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

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

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

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

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

4. Реализовать разработанные алгоритмы в виде программных систем и апробировать их на реальных практических задачах.

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

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

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

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

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

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

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

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

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

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

телекоммуникаций СибГАУ по направлению «Системный анализ и управление» при выполнении курсовых работ. Результаты решения программной системой «Нечеткий коэволюционный классификатор» задачи распознавания спутниковых изображений использовались в рамках проекта «Студенческий спутник СибГАУ» в сотрудничестве с Центром управления полетами СибГАУ.

Полученные результаты применялись в ходе выполнения работ по созданию систем управления сложными механическими системами (двойной перевернутый маятник) во время стажировки в Высшей технической школе г. Ульм (Hochschule Ulm), ФРГ, 2008 г.

Диссертационная работа поддержана Фондом содействия развитию малых форм предприятий в научно-технической сфере по программе «У.М.Н.И.К.» («Участник молодежного научно-инновационного конкурса») в рамках НИОКР «Разработка коэволюционного вероятностного алгоритма для автоматизированного проектирования интеллектуальных информационных технологий» на 2008-2011 гг. Работа финансировалась из средств госбюджета в рамках НИР Б1.01.05 «Разработка и исследование бионических методов идентификации и оптимизации сложных систем» ЕЗН СибГАУ, а также в рамках выполнения проекта «Система поддержки принятия решения при проектировании интегрированных систем безопасности», ставшего победителем конкурса инновационных проектов СибГАУ на 2007-2008 гг. Работа поддержана грантом в рамках конкурса научно-технического творчества молодежи города Красноярска «НТТМ-2010». Диссертационное исследование удостоено диплома 1 степени Российской ассоциации искусственного интеллекта.

Диссертационное исследование проводилось также в рамках НИР № 2.1.1./2710 «Математическое моделирование инвестиционного развития региональных экономических систем» АВЦП «Развитие научного потенциала высшей школы (2009-2010 годы)» и НИР НК-136П/3 "Автоматизированная система решения сложных задач глобальной оптимизации многоагентными стохастическими алгоритмами" ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009 - 2013 годы.

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

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

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

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

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

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

Апробация работы.

Результаты диссертационной работы были доложены и обсуждены на Всемирном конгрессе по вычислительному интеллекту (ШЕЕ 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 рисунков.

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

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

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

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

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

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

Все схемы коэволюционных алгоритмов объединяет два общих свойства:

1) в коэволюционном алгоритме обязательно представлено множество эволюционирующих в той или иной степени изолированно друг от друга подпопуляций;

2)подпопуляций коэволюционного алгоритма тем или иным способом взаимодействуют друг с другом.

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

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

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

Обобщенная схема «конкурентно-коопертивного» коэволюционного алгоритма для автоматизации выбора настроек ГА:

- выбор индивидуальных алгоритмов;

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

- независимая работа выбранных алгоритмов в течение интервала адаптации (обычно около 5 поколений);

- оценка алгоритмов;

- перераспределение ресурсов;

- миграция лучших индивидов во все подпопуляции.

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

Методы учета ограничений в ГА для решения задач условной оптимизации: метод «смертельных» штрафов, метод статических штрафов, метод динамических штрафов, метод адаптивных штрафов, «лечение» локальным поиском, метод поведенческой памяти, коэволюционный алгоритм поиска множителей Лагранжа и некоторые другие.

Методы многокритериальной оптимизации в ГА: VEGA (Vector Evaluated Genetic Algorithm), FFGA (Fonseca and Fleming's Multiobjective Genetic Algorithm), NPGA (Niched Pareto Genetic Algorithm), группа методов NSGA (Non-Dominated Sorting Genetic Algorithm), метод SPEA (Strength Pareto Evolutionary Algorithm), а также его модификация SPEA 2. По результатам предыдущих исследований показано, что в большинстве случаев SPEA 2 превосходит по эффективности остальные методы.

Рассматриваются методы классификации: решающее Байесовское правило, различные статистические и детерминистские методы классификации, методы конструирования высокоэффективных композиций из алгоритмов распознавания. Выяснено, что большинство из них работают по принципу «чёрного ящика» с невозможностью явной интерпретации причинно-следственных связей отнесения объекта к тому или иному классу.

Такого недостатка лишены методы вербального анализа решений (в частности, методы ЦИКЛ, ИСКРА, ПАКС, разработанные в Институте системного анализа РАН А. А. Асановым, О. И. Ларичевым, Г. В. Ройзензоном), а также нечеткий классификатор, разработанный группой японских специалистов в области нечетких систем (X. Ишибучи, Т. Накашима, Т. Курода, Т. Мурата). Нечеткий классификатор — алгоритм классификации, основанный на извлечении нечетких правил из массивов данных. Каждое правило в нечетком классификаторе содержит значения лингвистических термов для всех информативных признаков (включая терм «игнорирования»), номер класса, которому соответствует данное правило, а также уровень значимости в интервале [0;1], показывающий степень достоверности правила. Нечеткий классификатор относится и к алгоритмам классификации, и к технологиям интеллектуального анализа данных (Data Mining) для обнаружения скрытых знаний и закономерностей.

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

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

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

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

При исследованиях используются три типа селекции (пропорциональная, турнирная с турниром 2, ранговая), три типа скрещивания (одноточечное, двухточечное, равномерное) и три типа метода учета ограничений для условной оптимизации (метод «смертельных» штрафов в комбинации с «лечением» локальным поиском, метод динамических штрафов, метод адаптивных штрафов). Используется адаптивная мутация, в многокритериальной оптимизации используется единственный метод ЙРЕА2. Таким образом, число различных алгоритмов равно 9 для безусловной оптимизации и 27 для условной

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

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

Адаптация коэволюционного алгоритма на класс задач многокритериальной оптимизации также была сопряжена с существенными изменениями. Алгоритм БРЕА 2 направлен на поиск наиболее репрезентативной аппроксимации множества Парето (т.е. является методом сужения множество Парето). Наличие изолированных друг от друга в течение интервала адаптации подпопуляций в стандартном коэволюционном алгоритме приводит, во-первых, к высокой вероятности появления повторяющихся или близких друг к другу индивидов и, во-вторых, к появлению значительного числа индивидов, доминируемых индивидами из других подпопуляций. Поэтому было принято решение о наличии единой популяции для всех индивидуальных алгоритмов. При этом «закрепленная» за каждым алгоритмом часть потомков генерируется согласно настройкам этого алгоритма. Формирование повой популяции (из родителей и потомков) в каждом поколении осуществляется на основе результатов работы всех алгоритмов.

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

На основании проведенных исследований эффективности коэволюционного алгоритма были сделаны следующие обобщающие выводы.

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

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

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

Таблица 1

Исследования на задачах безусловной одпокритериалыюй оптимизации

Задача- Наихудший ГА Средний ГА Наилучший ГА Коэволюция

Над. Пок. Над. Пок. Над. Пок. Над. Пок.

1 0,79 74,6 0,96 60,9 1,00 50,7 1,00 25,8

2 0,22 76,7 0,25 78,9 0,32 83,6 0,24 40,2

3 0,26 71,5 0,57 69,0 0,78 65,3 0,66 32,9

4 0,16 68,0 0,55 69,0 0,81 70,9 0,87 49,6

5 0.84 71,2 0,88 65,5 0,93 67,1 0.89 30,9

6 0,41 74,1 0,87 63,7 1,00 52,7 0,97 28,0

7 1,00 57,2 1,00 45,0 1,00 38,3 1,00 27,0

8 1,00 48,1 1,00 43,1 1,00 39,7 1,00 26,3

Таблица 2

Исследования на задачах условной однокритсриальной оптимизации

Задача Наихудший ГА Средний ГА Наилучший ГА Коэволюция

Над! Пок. Над. Пок. Над. Пок. Над. Пок.

1 0,016 69,8 0,249 64,1 0,736 70,8 0,990 57,8

2 0,014 41,3 0,661 63,5 1,000 55,2 1,000 23,0

3 0,012 15,0 0,679 62,1 1,000 60,6 1,000 31,4

4 0,190 56,0 0.735 59,6 1,000 62,6 1,000 27,0

5 _ 0,000 - 0,066 73,2 0,292 73,4 0,990 48,0

6 0,014 57,2 0,550 61,5 1,000 68,0 0,982 39,4

7 0,000 - 0,080 70,5 0,320 71,0 0,996 50,2

8 0,000 - 0,420 78,8 0,748 70,0 1,000 44,8

9 0,050 15,0 0,294 51,4 0,568 71,8 0,802 54,0

10 0,028 16,5 0,172 50,8 0,372 75,4 0,340 59,0

Таблица 3

Исследования на задачах многокритериальной оптимизации_

Алгоритм Зад. 1 Зад. 2 Зад. 3 Зад. 4 Зад. 5 Зад. 6 Зад. 7

(ДП) (ДП) (ДП) (ДП) (ДП) (Р) (ДП)

Наихудший ГА 0,217 0,569 0,788 0,566 0,960 3.28 0,818

Средний ГА 0.246 0,611 0,807 0,582 0,973 3,34 0,830

Наилучший ГА 0,284 0,644 0,823 0,613 0,980 3,43 0,854

Коэволюция 0,242 0,620 0,810 0,573 0,972 3,32 0,830

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

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

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

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

Формирование начальной популяции для Мичиганского этапа (отбор стартовых правил). Пусть п - число нечетких правил, необходимое для заполнения популяции для Мичиганского этапа, k - число классов, I - число информативных признаков в задаче классификации. Последовательность шагов:

1) вычислить т = int (n/k);

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

3) от (':=! до к

отJ:-l до т

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

выборки;

от f:=l до 1

определить ближайший центр нечеткого числа по признаку í;

назначить соответствующее нечеткое число в нечеткое правило;

изменить нечеткое число на терм «игнорирование» с вероятностью 0,33;

4) заполнить популяцию сгенерированными нечеткими правилами.

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

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

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

1. Credit (Australia-1) (задача о выдаче банковского кредита, австралийский вариант, 14 признаков, 2 класса);

2. Credit (Germany) (задача о выдаче банковского кредита, немецкий вариант, 24 признака, 2 класса);

3. Liver Disorder (диагностика заболеваний печени, 6 признаков, 2 класса);

4. Iris (классификация видов ириса, 4 признака, 3 класса);

5. Yeast (классификация типов белков в дрожках, 8 признаков, 10 классов);

6. Glass Identification (классификация сортов стекла по содержанию химических элементов, 9 признаков, 7 классов).

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

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

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

Таблица 4

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

на задачах из репозитория ЦС1

Параметр Задача

1 2 3 4 5 6

Начальное число правил 200 200 100 50 200 200

Средняя точность классификации начальной базы правил 0,854 0,782 0,595 0,945 0,417 0,640

Средняя точность классификации после Мичиганского этапа 0,870 0,791 0,653 . 0,979 0,495 0,687

Средняя точность классификации после Питтсбургского этапа (в скобках -ограничение на число используемых правил) 0,827(10) 0,861(20) 0,873(30) 0,762(50) 0,790(80) 0,666(10) 0,682(15) 0,692(30) 0,908(3) 0,951(4) 0,971(5) 0,975(6) 0,573(20) 0,586(30) 0,593(60) 0,737(20) 0,781(30)

Макисмальиая точность классификации после Питтсбургского этапа 0,870(10) 0,890(20) 0,891(30) 0,767(50) 0,794(80) 0,687(10) 0,710(15) 0,725(20) 0,947(3) 0,973(4) 0,987(5) 0,987(6) 0,598(20) 0,606(30) 0,626(60) 0,757(20) 0,827(30)

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

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

Таблица 5

Сравнение различных алгоритмов классификации на задачах из репозитория иС1 по _точности классификации__

Алгоритм Credit (Australia-l) Credit (Germany) Liver Disorder

Нечеткий классификатор 0,891 0,794 0,725

Байесовский подход. 0,847 0,679 0,629

Многослойный перссптрон 0,833 0,716 0,693

Бустинг 0,760 0,700 0,656

Бэттинг 0,847 0,684 0,630

Метод случайных подпространств 0,852 0,677 0,632

Коэволюционный метод обучения алгоритмических композиций 0,866 0,746 0,644

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

Первая программная система «Коэволюционный алгоритм условной многокритериальной оптимизации» (разработана в среде С++ Builder 6.0) представляет собой универсальный комплекс для решения задач оптимизации различных классов и различного уровня сложности. Вторая программная система «Нечеткий коэволюционный классификатор» (разработана в среде MS Visual Studio 2005, язык С++) представляет собой универсальный комплекс для решения задач классификации с одновременным выявлением лингвистических знаний в соответствующих проблемных областях.

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

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

В задаче распознавания спутниковых изображений рассматривается шесть различных классов: красноземные почвы (1), хлопковые посевы (2), сероземные почвы (3), влажные сероземные почвы (4), земли с овощными посевами (5), очень влажные сероземные почвы (6). Необходимо на снимке, полученном со спутника дистанционного зондирования Земли, отнести каждый квадрат-размером 3x3 к тому или иному классу по значениям интенсивности в четырёх спектрах (зеленый, красный и два инфракрасных). Ниже приведена полученная при использовании нечеткого классификатора компактная база нечетких правил (обозначения лингвистических термов: ОМ - «очень малая интенсивность», М -«малая интенсивность», С - «средняя интенсивность», Б - «большая интенсивность», ОБ - «очень большая интенсивность»).

Таблица 6

База нечетких правил для распознавания спутниковых изображений_

№ Зеленый Красный 1-й инфракрасный 2-й инфракрасный Класс Доверит.

спектр спектр спектр спектр уровень

1 ОМ С м 1 0,899171

2 ОБ 2 1

3 ОМ ОМ С С 2 0,921344

4 м Б 2 0,898492

5 ОБ ОБ 3 0,862182

6 Б С С 3 0,665 ¡46

7 Б ом 4 0,592109

8 ОМ ОМ 5 0,959055

9 М м м 5 0,757215

10 с ом 6 0,675657

Точность классификации по базе правил на обучающей выборке - 0,8490, на

тестовой - 0,8435.

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

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

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

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

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

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

1. Сергиенко, Р.Б. Коэволюционный генетический алгоритм решения сложных задач условной оптимизации / Р.Б. Сергиенко, Е.С. Семенкин // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнёва. -№2 (23). - 2009. - С. 17-21.

2. Сергиенко, Р.Б. Исследование эффективности коэволюционного генетического алгоритма условной оптимизации / Р.Б. Сергиенко // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнёва. - №3 (24). - 2009. - С. 31-36.

3. Сергиенко, Р.Б. Метод формирования нечеткого классификатора самонастраивающимися коэволюционными алгоритмами / Р.Б. Сергиенко // Искусственный интеллект и принятие решений. - №3. - 2010. - С. 98-106.

4. Сергиенко, Р.Б. Коэволюционный алгоритм для задач условной и многокритериальной оптимизации / Р.Б. Сергиенко, Е.С. Семенкин // Программные продукты и системы. - №4. - 2010. - С. 24-28.

Публикации в журналах и сборниках

5. Сергиенко, Р.Б. Системы поддержки принятия решений на основе коэволюционного вероятностного алгоритма / Р.Б. Сергиенко, Е.С. Семенкин // Ползуновский альманах. - № 4. - 2008. - С. 217-219.

6. Сергиенко, Р.Б. Коэволюционный алгоритм условной оптимизации «Conditional Coevolution» / Р.Б. Сергиенко // Компьютерные учебные программы и инновации. - № 2. - 2009. - С. 21.

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

7. Sergienko, R. Competitive Cooperation for Strategy Adaptation in Coevolutionary Genetic Algorithm for Constrained Optimization / R. Sergienko, E.Semenkin // IEEE World Congress on Computational Intelligence (WCCI'2010), Barcelona, Spain, 2010. - P. 1626-1631.

8. Сергиенко, Р.Б. Разработка и исследование гибридной схемы формирования нечеткого классификатора с использованием коэволюционного алгоритма / Р.Б. Сергиенко // Труды Национальной конференции по искусственному интеллекту КИИ-2010. - Т.2. - М.: Физматлит, 2010. - С. 353360.

9. Сергиенко, Р.Б. Гибридная схема генерирования нечеткого классификатора с использованием коэволюционного алгоритма / Р. Б. Сергиенко // Теория и практика системного анализа. Труды I Всероссийской научной конференции молодых ученых. - Т. 1. - Рыбинск: РГАТА, 2010. - С. 11-19.

10. Сергиенко, Р.Б. Нечеткий коэволюционный классификатор / Р.Б. Сергиенко // Технологии Microsoft в теории и практике программирования: сборник трудов VII Всероссийской научно-практической конференции. - Томск: Издательство Томского политехнического университета, 2010. - С. 94-95.

11. Сергиенко, Р.Б. Нечеткий генетический классификатор в задаче распознавания спутниковых изображений / Р.Б. Сергиенко // Информационные технологии и математическое моделирование. Материалы VIII Всероссийской научно-практической конференции в 2-х частях. - Томск: Издательство Томского университета, 2009. - Часть 2. - С. 272-276.

12. Сергиенко, Р.Б. Параллелизация коэволюционного алгоритма в многопроцессорных вычислительных системах / Р.Б. Сергиенко // Решетневские чтения. Материалы Х1П Международной научной конференции в 2-х частях. -Красноярск: СибГАУ, 2009. - Часть 2. - С. 453-454.

13. Сергиенко, Р.Б. Использование коэволюционного алгоритма при извлечении знаний в виде нечетких правил в задачах классификации / Р.Б. Сергиенко // Труды Конгресса по интеллектуальным системам и информационным технологиям "AIS-IT'09". Научное издание в 4-х томах. - М.: Физматлит, 2009. - Т.З. - С. 321-328.

14. Сергиенко, Р.Б. Составление расписания посадок самолетов коэволюционным алгоритмом условной оптимизации / Р.Б. Сергиенко // Решетневские чтения. Материалы XII Международной научной конференции. -Красноярск: СибГАУ,-2008. - С. 308-310.

15. Сергиенко, Р.Б. Коэволюционный алгоритм условной оптимизации: разработка и приложения / Р.Б. Сергиенко // Труды Международных научно-технических конференций "Интеллектуальные системы" (AIS'08) и "Интеллектуальные САПР" (CAD-2008). Научное издание в 4-х томах. - М.: Физматлит, 2008. -Т.1.-С. 33-40.

16. Сергиенко, Р.Б. Автоматизированное генерирование интеллектуальных информационных технологий на основе самонастраивающихся эволюционных алгоритмов / Р.Б. Сергиенко, В.В. Бухтояров // Технологии Microsoft в теории и практике программирования. - Новосибирск: НГУ, 2008. - С. 167-169.

17. Сергиенко, Р.Б. Автоматическая настройка параметров генетического алгоритма коэволюционным методом в решении задач условной оптимизации / Р.Б. Сергиенко // Молодежь и современные информационные технологии. Сборник трудов VI Всероссийской научно-практической конференции. - Томск: Издательство ТПУ, 2008. - С. 277-278.

18. Сергиенко, Р.Б. Коэволюционный алгоритм решения задач условной оптимизации / Р.Б. Сергиенко // VIII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям. -Новосибирск: Институт вычислительных технологий СО РАН, 2007. - С.73.

19. Сергиенко, Р.Б. Разработка и исследование коэволюционного алгоритма для решения задач условной оптимизации / Р.Б. Сергиенко // Информационные технологии и математическое моделирование (ИТММ-2007): Материалы VI Международной научно-практической конференции. - Томск: Издательство Томского университета, 2007. - 4.2. - С.96-99.

20. Сергиенко, Р.Б. Исследование эффективности коэволюционного алгоритма на тестовых функциях одной переменной / Р.Б. Сергиенко // VII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям. - Красноярск: Институт вычислительного моделирования СО РАН, 2006. - С.68.

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

21. Сергиенко, Р.Б. Коэволюционный алгоритм условной оптимизации «Conditional Coevolution»: свидетельство об отраслевой регистрации разработки. - М.: ВНТИЦ, 2008. - № гос. per. 50200802249.

22. Сергиенко, Р.Б. Коэволюционный алгоритм условной многокритериальной оптимизации: свидетельство о государственной регистрации программы для ЭВМ / Р.Б. Сергиенко, Е.С. Семенкин. - М.: Реестр программ для ЭВМ, 2009. -№ гос. per. 2009616049.

23. Сергиенко, Р.Б. Нечеткий коэволюционный классификатор: свидетельство о государственной регистрации программы для ЭВМ / Р.Б. Сергиенко. -М.: Реестр программ для ЭВМ, 2010. -№ гос. per. 2010611766.

Сергиенко Роман Борисович Автоматизированное формирование нечетких классификаторов самонастраивающимися коэволюционными алгоритмами Автореферат Подписано к печати 28.10.2010. Формат 60x84/16 Уч. изд. л. 1.0 Тираж 100 экз. Заказ №

Отпечатано в отделе копировальной и множительной техники СибГАУ. 660014, г. Красноярск, пр. им. газ. «Красноярский рабочий», 31

Оглавление автор диссертации — кандидата технических наук Сергиенко, Роман Борисович

ВВЕДЕНИЕ

ГЛАВА 1. Обзор современных алгоритмов и методов оптимизации, 11 классификации и интеллектуального анализа данных

1.1. Общая постановка задачи и обзор алгоритмов глобальной 11 оптимизации

1.2. Понятие о коэволюционных алгоритмах

1.3. Коэволюционный алгоритм для автоматической настройки 21 параметров генетического алгоритма

1.4. Условная оптимизация в генетических алгоритмах

1.5. Многокритериальная оптимизация в генетических алгоритмах

1.6. Классификация: постановка задачи и обзор алгоритмов

1.7. Интеллектуальный анализ данных (Data Mining)

1.8. Нечеткий классификатор

Выводы

ГЛАВА 2. Самонастраивающийся кооперативно-конкурирующий 57 коэволюционный алгоритм решения сложных задач оптимизации

2.1. Общая схема проведения исследований эффективности коэволюционного алгоритма

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

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

2.4. Разработка и исследование эффективности коэволюционного 93 алгоритма для задач многокритериальной оптимизации

Выводы

ГЛАВА 3. Разработка и апробация схемы формирования нечеткого 105 классификатора с использованием самонастраивающегося коэволюционного алгоритма

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

3.2. Описание тестовых задач классификации

3.3. Результаты исследования нечеткого коэволюционного И классификатора на тестовых задачах

Выводы

ГЛАВА 4. Практическая реализация разработанных алгоритмов

4.1. Программная система «Коэволюционный алгоритм условной 124 многокритериальной оптимизации»

4.2. Решение задачи составления расписания посадок самолетов

4.3. Программная система «Нечеткий коэволюционный 138 классификатор»

4.4. Решение задачи обработки данных дистанционного 143 зондирования Земли космическими аппаратами

Выводы

Введение 2010 год, диссертация по информатике, вычислительной технике и управлению, Сергиенко, Роман Борисович

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

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

Такого недостатка лишены методы вербального анализа решений, разработкой которых, в частности, занимаются в Институте системного анализа РАН [111], а также нечеткий классификатор, являющийся разработкой японских специалистов в области нечетких систем во главе с X. Ишибучи [33]. Нечеткий классификатор представляет собой базу нечетких правил. Каждое нечеткое правило — выражение причинно-следственной закономерности отнесения объекта к какому-либо классу в лингвистической форме, доступное для прямого восприятия экспертом. Таким образом, нечеткий классификатор представляет собой одновременно алгоритм классификации и инструмент интеллектуального анализа данных (Data Mining) для обнаружения скрытых знаний и закономерностей.

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

Однако применение эволюционных алгоритмов оптимизации сопряжено с другой серьезной проблемой — высокой сложностью и трудоемкостью настройки алгоритмов на решаемую задачу в связи с большим числом возможных комбинаций их настроек (селекции, мутации, скрещивания и некоторых других). Эффективность одной и той же настройки на разных задачах и различных настроек на одной и той же задаче может изменяться в очень широком диапазоне. Поэтому выбор настроек наугад является неприемлемым, так как многие комбинации параметров алгоритма оказываются неработоспособными, а тщательная настройка под новую задачу является чрезмерно трудоемкой, особенно для таких вычислительно сложных задач, как формирование нечеткого классификатора. Для решения проблемы предлагается использование так называемого коэволюционного подхода для адаптации стратегии оптимизации [96], позволяющего отказаться от выбора настроек эволюционного алгоритма за счет 5 взаимодействия (конкуренции и кооперации) множества эволюционных алгоритмов с различными настройками.

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

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

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

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

Практическая ценность. Разработанные в ходе исследования алгоритмы и методы реализованы в виде двух программных систем: 7

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

Реализация результатов работы. Программные системы использовались в качестве лабораторных установок студентами Института информатики и телекоммуникаций СибГАУ по направлению «Системный анализ и управление» при выполнении курсовых работ. Результаты решения программной системой «Нечеткий коэволюционный классификатор» задачи распознавания спутниковых изображений использовались в рамках проекта «Студенческий спутник СибГАУ» в сотрудничестве с Центром управления полетами СибГАУ.

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

У.М.Н.И.К.» («Участник молодежного научно-инновационного конкурса») в рамках НИОКР «Разработка коэволюционного вероятностного алгоритма для автоматизированного проектирования интеллектуальных 8 информационных технологий» на 2008-2011 гг. Работа финансировалась из средств госбюджета в рамках НИР Б 1.01.05 «Разработка и исследование бионических методов идентификации и оптимизации сложных систем» ЕЗН СибГАУ, а также в рамках выполнения проекта «Система поддержки принятия решения при проектировании интегрированных систем безопасности», ставшего победителем конкурса инновационных проектов СибГАУ на 2007-2008 гг. Работа поддержана грантом в рамках конкурса научно-технического творчества молодежи города Красноярска «НТТМ-2010». Диссертационное исследование удостоено диплома 1 степени Российской ассоциации искусственного интеллекта.

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

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

Апробация работы.

Результаты диссертационной работы были доложены и обсуждены на Всемирном конгрессе по вычислительному интеллекту (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), а также на ряде молодежных и студенческих конференций.

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

Выводы

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

Библиография Сергиенко, Роман Борисович, диссертация по теме Теоретические основы информатики

1. Aarts, E.H.L. Simulated Annealing: Theory and Applications / E.H.L. Aarts, P.J.M. van Laarhoven. London: Kluwer, 1987.

2. Alba, P. Adaptive mutation in genetic algorithms / S. Marsili Libelli, P. Alba // Soft Computing. №4. - 2000. - pp. 76-80.

3. Beasley, J. E. Scheduling aircraft landings the static case / J. E. Beasley, M. Krishnamoorthy, Y. M. Sharaiha, D. Abramson // Transportation Science. -2000.-Vol. 34.-pp. 180-197.

4. Breiman, L. Arcing classifiers / L. Breiman // The Annals of Statistics. -vol. 26. Mar, 1998. - pp. 801-849.

5. Carr, G. C. Airline arrival prioritization in sequencing and scheduling / G. C. Carr , H. Erzberger, F. Neuman // Air Traffic Management R&D Seminar. -Orlando. 1998. - http://www.ctas.arc.nasa.gov/publications.

6. Cassilas, J. A. Cooperative Coevolutionary Algorithm for Jointly Learning Fuzzy Rules Base and Membership Functions / J. Cassilas, O. Cordon, F. Herrero. Granada, Spain, 2005.

7. Clerc, M. Particle Swarm Optimization / M. Clerc. London: Wiley-ISTE, 2006. - 243 pp.

8. Coit, D. Adaptive Penalty Methods for Genetic Optimization of Constrained Combinatorial Problems / David W. Coit, Alice E. Smith and David M. Tate // INFORMS Journal on Computing, 8(2): 173-182, Spring 1996.

9. Colorni, A. Distributed Optimization by Ant Colonies / A. Colorni, M. Dorigo et V. Maniezzo // Actes de la première conférence européenne sur la vie artificielle. Paris, France: Elsevier Publishing, 1991. - pp. 134-142.

10. Corcoran, A. An Overview of Parallelism in Genetic Algorithms. Technical Report / A. Corcoran. Tulsa: The University of Tulsa, 1993.

11. Corne, D.W. The Pareto Envelope-Based Selection Algorithm for Multiobjactive Optimization / D.W. Corne, J.D. Knowles, M.J. Oates // Parallel

12. Problem Solving form Nature. PPSN VI. - Berlin: Springier, 2000. - pp. 839848.

13. Deb, K. A fast and elitist multiobjective genetic algorithm: NSGA-II / K. Deb, A. Pratap, S. Agarwal, T. Meyarivan // IEEE Transactions on Evolutionary Computation. №6(2). - 2002. - pp. 182-197.

14. Deb, K. Controlled elitist non-dominated sorting genetic algorithms for better convergence / K. Deb, T. Goel // Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization. — Zurich, Switzerland, 2001.-pp. 67-81.

15. Diener, I. Trajectory Methods in Global Optimization / I. Diener, R. Horst, P.M. Pardalos (eds) // Handbook of Global Optimization. Dordrecht: Kluwer, 1995. - pp. 649-668.

16. Eiben, A. Parameter Control in Evolutionary Algorithms / A. Eiben, R. Hinterding, Z. Michalewicz // IEEE Transactions on Evolutionary Algorithms. -Vol. 3, №2. 1999. - pp. 124-141.

17. Ficici, S.G. Solution Concepts in Coevolutionary Algorithms. A Doctor of Philosophy Dissertation / S.G. Ficici. Brandeis University, 2004. - 276 pp.

18. Fogel, D.B. Evolutionary Computation / D.B. Fogel. IEEE Press, 1995.

19. Funes, P. Dynamic Properties of Minimal Algorithms for Coevolution / P. Funes, E. Pujals. Cambridge, MA: Icosystem Corporation, 2004. - 13 pp.

20. Goldberg, D.E. Genetic algorithms in search, optimization and machine learning / D.E. Goldberg. Reading, MA: Addison-Wesley, 1989.

21. Gomez, S. The Tunneling Method Applied to Global Optimization / S. Gomez, A.V. Levy // SIAM, Numerical Optimization (Boggs, P.T., ed.), 1985. -pp. 213-244.

22. Goodman, E. Evolutionary computation and its applications / E. Goodman et al (Eds) // Proc. of the Int. Conference. Moscow: IHPCS of RAS, 1996. - 350 pp.

23. Guo, Y. Revolutionary Optimization Algorithm with Dynamic Subpopulation Size / Y. Guo, X. Cao, H. Yin // International Journal of Innovative Computing, Information and Control. Vol.3, №2. - 2007. - pp. 435-448.

24. Hansen, E.R. Global Optimization Using Interval Analysis / E.R. Hansen. -New York: Marcel Dekker, 1992.

25. Herrero, F. Genetic Fuzzy Systems: A Tutorial / F. Herrero, L. Magdalena. Granada: University of Granada, 1999. 20 pp.

26. Ho, T. K. The random subspace method for constructing decision forests / T.K. Ho // IEEE Trans, on Pattern Analysis and Machine Intelligence. vol. 20. — Aug, 1998.-pp. 832-844.

27. Holland, J. H. Cognitive systems based on adaptive algorithms / J.H. Holland, J.S. Reitman. // Pattern-Directed Inference Systems (Eds D. A. Waterman and F. Hayes-Roth). New York: Academic Press, 1978.

28. Holland, J. H. Adaptation in Natural and Artificial Systems / J. H. Holland. Cambridge, MA: MIT Press, 1992 (2nd edition).

29. Homaifar, A. Constrained Optimization via Genetic Algorithms / A. Homaifar, S. H.-Y. Lai, X. Qi // Simulation. Vol.62, №4. - 1994. - pp. 242-254.

30. Horn, J. Multiobjective optimization using the niched Pareto genetic algorithm / J. Horn, N. Nafpliotis. IlliGAL Report No. 93005, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana-Champaign, IL, 1993.

31. Iorio, A. Parameter Control within a Cooperative Coevolutionary Genetic Algorithm / A. Iorio, X. Li // Parallel Problem Solving from Nature PPSN VII. -Springer Berlin, 2002. - pp. 247-256.

32. Iorio, A. A Cooperative Coevolutionary Multiobjective Algorithm Using Non-dominated Sorting / A. Iorio, X. Li. Australia, 2004. - 12 pp.

33. Ishibuchi, H. Performance Evaluation of Fuzzy Classifier Systems for Multidimensional Pattern Classification Problems / H. Ishibuchi, T. Nakashima, T. Murata // IEEE Transactions on Systems, Man, and Cybernetics. — Vol.29, №5. — 1999.-pp. 601-618.

34. Ishibuchi, H. A Hybrid Fuzzy GBML Algorithm for Designing Compact Fuzzy Rule-Based Classification System / H. Ishibuchi, T. Nakashima, T. Kuroda // Proc. of 9th IEEE International Conference on Fuzzy Systems. 2000. - pp. 706711.

35. Ishibuchi, H. Multiobjective Optimization in Linguistic Rule Extraction from Numerical Data / H. Ishibuchi, T. Nakashima, T. Murata // Evolutionary Multi-Criterion Optimization. Springier-Verlag Berlin Heidelberg, 2001. - pp. 588-602.

36. Jiao, L. An Organizational Coevolutionary Algorithm for Classification / L. Jiao, J. Liu, W. Zhong. Xidian University, China, 2006. - 39 pp.

37. Joines, J.A. On the Use of Non-Stationary Penalty Functions to Solve Nonlinear Constrained Optimization Problem With Gas / J.A. Joines, C.R. Houck // Proceedings of the IEEE ICEC, 1994. pp. 579-584.

38. Juille, H. Coevolutionary learning: A case study. In J. Shavlik, editor / H. Juille, J.B. Pollack // Proceedings of the Fifteenth International Conference on Machine Learning. Morgan Kaufmann, 1998. - pp. 251-259.

39. Kilani, Y. Treating Some Constraints as Hard Speeds up the ESG Local Search Algorithm / Y. Kilani and A. MohdZin // Adaptive and Natural Computing Algorithms. Springer, Coimbra, Portugal, March 2005. - pp. 257-250.

40. Koza, J. Genetic Programming / J. Koza. MIT Press, 1992.

41. Leung, K. Data mining using grammar based genetic programming and applications / K. Leung, M. Wong. New York: Kluwer Academic Publisher, 2002.-213 pp.

42. Lin, W.-K. The Co-Evolvability of Games in Coevolutionary Genetic Algorithms / W.-K. Lin, T.-L. Yu. // Proceedings of the 11th Annual conference on genetic and evolutionary computation, 2009. pp. 1869-1870.

43. Maneeratana, K. Multi-objective Optimization by Co-operative Co-evolution/ K. Maneeratana, K. Boonlong, N. Chaiyaratana. Thailand, 2004. - 10 pp.

44. Michalewicz, Z. Handling Constraints in Genetic Algorithm / Z. Michalewicz, C. Janikow // Proceedings of the Fourth ICG A. Morgan Kaufmann, 1991.-pp. 151-157.

45. Michalewicz, Z. Evolutionary Optimization for Constrained Problems / Z. Michalewicz, N. Attia // Proceedings of the 3rd Annual Conference on EP, World Scientific, 1994.-pp. 98-108.

46. Michalewicz, Z. Genocop III: A Coevolutionary Algorithm for Numerical Optimization Problems with Nonlinear Constraints / Z. Michalewicz, G. Nazhiyath // Evolutionary Computation. Vol.2, №11. - 1995 - pp. 647 - 651.

47. Michalewicz, Z. Genetic Algorithms + Data Structures = Evolution Programs (3rd Edn.) / Z. Michalewicz. New York: Springer-Verlag, 1996.

48. Michalewicz, Z. Evolutionary algorithms for constrained optimization parameter optimization problems / Z. Michalewicz, M. Schoenauer // Evolutionary Computation, 4:1, 1996. pp. 1-32.

49. Mühlenbein, H. Strategy Adaptation by Competing Subpopulations / D. Schlierkamp-Voosen, H. Mühlenbein // Parallel Problem Solving from Nature III. Lecture Notes in Computer Science 866. - Springer-Verlag, 1994.

50. Panait, L. A Comparative Study of Two Competitive Fitness Functions / L. Panait, S. Luke // Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), 2002.

51. Panait, L. A Sensitivity Analysis of a Cooperative Coevolutionary Algorithm Biased for Optimization / L. Panait, P.R. Wiegand, S. Luke // Genetic and Evolutionary Computation Conference GECCO 2004. - Springer Berlin, 2004.-pp. 573-584.

52. Pham, D. T. Outline of a New Evolutionary Algorithm for Fuzzy Systems Learning / D.T. Pham, M. Castellani // Proc. Instn. Mech. Engrs. Vol. 216. Part C: Mechanical Engineering Science. 2002. - pp. 557-570.

53. Pham, D.T. The Bees Algorithm A Novel Tool for Complex Optimization Problems / D.T. Pham, A. Ghanbarzadeh, E. K05, S. Otri, S. Rahim, and M. Zaidi // Proceedings of IPROMS 2006 Conference, pp. 454-461.

54. Potter, M.A. Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents / M.A. Potter, K.A. De Jong // Evolutionary Computation. Vol. 8, №1. - 2000. - pp. 1-29.

55. Powell, D. Using Genetic Algorithms in Engineering Design Optimization with Non-Linear Constraints / D. Powell, M.M. Skolnick // Proceedings of the Fifth ICG A. Morgan Kaufmann, 1993. - pp. 424-430.

56. Ray, T. A Cooperative Coevolutionary Algorithm with Correlation Based Adaptive Variable Partitioning / T.Ray, X. Yao // 2009 IEEE Congress on Evolutionary Computation (CEC 2009), 2009. pp. 983-989.

57. Rosin, C. New Methods for Competitive Coevolution / C. Rosin, R. Belew // Evolutionary Computation. — №5. — 1997. pp. 1-29.

58. Schapire, R. The boosting approach to machine learning: An overview / R. Schapire // MSRI Workshop on Nonlinear Estimation and Classification. -Berkeley, CA, 2001.

59. Schoenauer, M. Constrained GA Optimization / M. Schoenauer, S. Xanthakis // Proceedings of the Fifth ICGA. Morgan Kaufmann, 1993. - pp. 573-580.

60. Schwefel, H.-P. Evolution and Optimum Seeking / H.-P. Schwefel. — Wiley & Sons, 1995.

61. Senge, R. Learning Pattern Tree Classifiers Using a Coevolutionary Algorithm / R. Senge, E. Hullermeier // Lernen Wissen Adaptivitat, Darmstadt, 2009.

62. Seredynski, F. Competitive Coevolutionary Multi-Agent Systems: The Application to Mapping and Scheduling Problems / F. Seredynski // Journal of Parallel and Distributed Computing. Vol. 47. - 1997. - pp. 39-57.

63. Smith, S. F. A learning system based on genetic adaptive algorithms. PhD thesis / S.F. Smith. Department of Computer Science, University of Pittsburgh, Pennsylvania, 1980.

64. Srinivas, M. Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms / M. Srinivas, L. M. Patnaik // IEEE Transactions on Systems, Man and Cybernetics. Vol. 24, No.4. - 1994. - pp. 656-667.

65. Srinivas, N. Multi-objective function optimization using nondominated sorting genetic algorithms / N. Srinivas, K. Deb // Evolutionary Computation. — №2(3). 1994. - pp. 221-248.

66. Tan, K. A Distributed Cooperative Coevolutionary Algorithm for Multiobjective Optimization / K. Tan, Y. Yang, T. Lee // Evolutionary Computation. Vol.10, №10. - 2006. - pp. 527-549.

67. Tan, T. Competitive Coevolution with K-Random Opponents for Pareto Multiobjective Optimization / T. Tan, J. Teo, H. Leo // Third International Conference on Natural Computation (ICNC 2007), 2007.

68. Torn, A. Topographical Global Optimization Using Pre-Sampled Points / A. Torn, S. Viitanen // Journal of Global Optimization. Vol. 5. - No 3. - 1994. -pp. 267-276.

69. UCI Machine Learning Repository http://kdd.ics.uci.edu/.

70. Wiegand, P.R. An Analysis of Cooperative Coevolutionary Algorithms. A Doctor Philosophy Dissertation / P.R. Wiegand. Fairfax, Virginia: George Mason University, 2003. - 127 pp.

71. Zadeh, L. A. Fuzzy sets / L.A. Zadeh // Inf. and Control. №8. - 1965. -pp. 338-353.

72. Zitzler, E. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach / E. Zitzler, L. Thiele // IEEE Transactions on Evolutionary Computation. Vol. 3, No. 4. - 1999. - pp. 257-271.

73. Zitzler, E. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. ПК Report №103 / E. Zitzler, M. Laumanns, L. Thiele. — Zurich, Switzerland: Swiss Federal Institute of Technology, 2001. 21 pp.

74. Айвазян, C.A. Прикладная статистика. Классификация и снижение размерности / С.А. Айвазян и др. -М.: Финансы и статистика, 1989 607 с.

75. Антамошкин, А.Н. Оптимизация функционалов с булевыми переменными / А.Н. Антамошкин. Томск: Изд-во Том. ун-та, 1987. — 104 с.

76. Архангельский, А.Я. Язык С++ в С++ Builder: справочное и методическое пособие / А.Я. Архангельский. М.: Бином, 2008. — 944 с.

77. Асанов, А.А. Метод многокритериальной классификации ЦИКЛ и его применение для анализа кредитного риска / А. А. Асанов, О. И. Ларичев, Г. В. Ройзензон и др. // Экономика и математические методы. — 2001. Т. 37. — № 2. — С. 14-21.

78. Банди, Б. Методы оптимизации. Вводный курс / Б. Банди. М.: Радио и связь, 1988. - 128 с.

79. Барсегян, А.А. Методы и модели анализа данных: OLAP и Data Mining / А.А. Барсегян, М.С. Куприянов, В.В. Степаненко, И.И. Холод. -СПб.: «БХВ-Петербург», 2004. 336 с.

80. Барский, А.Б. Нейронные сети: распознавание, управление, принятие решений / А.Б. Барский. М.: Финансы и статистика, 2004. — 176 с.

81. Бежитский, С.С. Гибридный эволюционный алгоритм для задач выбора эффективных вариантов систем управления / С.С. Бежитский, Е.С. Семенкин, О.Э. Семенкина // Автоматизация и современные технологии. № 11.-2005.-С. 24-31.

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

83. С.С. Бежитский // Теория и практика системного анализа: Труды I160

84. Всероссийской научной конференции. Т. П. - Рыбинск: РГАТА, 2010. - С. 39-46.

85. Болыпев, Л.Н. Таблицы математической статистики / Л.Н. Большее, Смирнов Н.В. М.: Наука, 1983. - 416 с.

86. Ворожейкин, А. Ю. Адаптивные эволюционные алгоритмы решения сложных задач оптимизации: дисс. . канд. техн. наук / А.Ю. Ворожейкин. — Красноярск: СибГАУ, 2008. 177 с.

87. Воронцов, К.В. О методах оптимизации и монотонной коррекции в алгебраическом подходе к проблеме распознавания / К.В. Воронцов, К.В. Рудаков // Докл. РАН. Т.367. - № 3. - 1999. - С. 314-317.

88. Воронцов, К.В. Коэволюционный метод обучения алгоритмических композиций / К.В. Воронцов, Д.Ю. Каневский // Таврический вестник информатики и математики. №2. - 2005. — С.51-66.

89. Гладков, Л.А. Биоинспирированные методы в оптимизации / Л.А. Гладков В.В. Курейчик, В.М. Курейчик, П.В. Сорокалетов. -М.: Физматлит, 2009.-384 с.

90. Горелик, А.Л. Методы распознавания / А.Л. Горелик, В.А. Скрипкин. — М.: Высшая школа, 1977.

91. Гуменникова A.B. Гибридный алгоритм адаптивного поиска для решения задач условной многокритериальной оптимизации / A.B. Гуменникова, Т.Р. Ильина // Вестник Сибирского государственного аэрокосмического университета. №5. - 2004. - С. 70-76.

92. Джонс, М.Т. Программирование искусственного интеллекта в приложениях / М. Т. Джонс. М.: ДМК Пресс, 2006. - 312 с.

93. Дорофеюк, A.A. Алгоритмы автоматической классификации / A.A. Дорофеюк // Автоматика и телемеханика. №12. - 1971. — С. 78-113.

94. Емельянова, М.Н. Исследование эффективности коэволюционного алгоритма / М.Н. Емельянова, Е.С. Семенкин // Вестник Сибирского государственного аэрокосмического университета. — № 6. — 2004. — С. 28-34.

95. Жукова, М. Н. Коэволюционный алгоритм решения сложных задач оптимизации: дисс. . канд. техн. наук / М. Н. Жукова Красноярск: СибГАУ, 2004. - 126 с.

96. Журавлёв, Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть I. / Ю.И. Журавлёв // Кибернетика. 1977. - №4. - С.5-17.

97. Журавлёв, Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть II. / Ю.И. Журавлёв // Кибернетика. 1977. - №6. - С.21-27.

98. Журавлёв, Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть П1. / Ю.И. Журавлёв // Кибернетика. 1978. - №2. - С.35-43.

99. Журавлёв, Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации / Ю.И. Журавлёв // Проблемы кибернетики. 1978. - Т.ЗЗ. - С.5-68.

100. Каневский, Д.Ю. Обучение алгоритмических композиций на основе кооперативной коэволюции / Д.Ю. Каневский // Труды 49-й научной конференции МФТИ. Часть VII: управление и прикладная математика. — М.: МФТИ, 2006. С. 282-283.

101. Клешков, В.М. Модели и алгоритмы распределения общих ресурсов при управлении инновациями реструктурированного машиностроительного предприятия / В.М. Клешков, Е.С. Семенкин // Проблемы машиностроения и автоматизации. № 3. — 2006. - С. 24-31.

102. Липинский, JI.B. О коэволюционном генетическом алгоритме автоматизированного проектирования системы управления на нечеткой логике / JI.B. Липинский, В.А. Малько, Е.С. Семенкин // Автоматизация и современные технологии. -№11. -2006. С. 17-24.

103. Макленнен, Дж. Microsoft SQL Server 2008: Data Mining -интеллектуальный анализ данных / Дж. Макленнен, Ч. Танг, Б. Криват. — СПб.: «БХВ-Петербург», 2009. 720 с.

104. Матвеев, М.Г. Модели и методы искусственного интеллекта. Применение в экономике / М.Г. Матвеев, A.C. Свиридов, H.A. Алейникова. — М.: Финансы и статистика, 2008. 448 с.

105. Медведев, A.B. Непараметрические системы адаптации / A.B. Медведев. Новосибирск: Наука, 1983. - 174 с.

106. Ногин, В.Д. Сужение множества Парето на основе информации о предпочтениях ЛПР точечно-множественного типа / В.Д. Ногин // Искусственный интеллект и принятие решений. — 2009. № 1. — С. 5-16.

107. Орлянская, И. В. Современные подходы к построению глобальной оптимизации / И. В. Орлянская // Электронный журнал «Исследовано в России», 2002 С. 2097-2108. http://zhurnal.ape.relarn.ru/articles/2002/189.pdf

108. Петровский, А. Б. Интерактивная процедура снижения размерности признакового пространства в задачах многокритериальной классификации / А.Б. Петровский, Г.В. Ройзензон // Поддержка принятия решений: Труды

109. Института системного анализа Российской академии наук / Под ред. А. Б. Петровского. — М.: Издательство ЛЕСИ, 2008. — Т. 35. С. 43-53.

110. Пиявский, С.А. Один алгоритм отыскания абсолютного экстремума функции / С. А. Пиявский // Журнал вычислительной математики и математической физики. — № 12. — 1972.

111. Пуртиков, В.А. Оптимизация управления формированием кредитного портфеля банка: дисс. . канд. техн. наук / В.А. Пуртиков. — Красноярск: CAA, 2001. 148 с.

112. Растригин, JI.A. Случайный поиск / JT.A. Растригин. М.: Знание, 1979.

113. Растригин, JI.A. Коллективные правила распознавания /Л.А. Растригин, Р.Х. Эренштейн. М.: Энергия, 1981. - 244 с.

114. Ройзензон, Г.В. Интерактивные методы снижения размерности признакового пространства в задачах многокритериального принятия решения: автореферат дисс. . канд. техн. наук / Г. В. Ройзензон М: Институт системного анализа РАН, 2008. - 23 с.

115. Рубан, А.И. Методы оптимизации: учеб. пособие / А. И. Рубан. -Красноярск: НИИ ИПУ, 2001. 528 с.

116. Рубан, А.И. Глобальная оптимизация методом усреднения координат: Монография / А. И. Рубан. Красноярск: ИПЦ КГТУ, 2004. - 302 с.

117. Рубан, А.И. Методы анализа данных: учеб. пособие / А.И. Рубан. — Красноярск: ИПЦКГТУ, 2004. 319 с.

118. Семенкин, Е.С. Оптимизация технических систем. Учебное пособие / Е.С. Семенкин, О.Э. Семенкина, С.П. Коробейников. Красноярск: СИБУП, 1996.-284 с.

119. Семенкин, Е.С. Метод обобщенного адаптивного поиска для синтеза систем управления сложными объектами / Е.С. Семенкин, В.А. Лебедев. -М.: МАКС Пресс, 2002. 320 с.

120. Семенкин, Е.С. Вероятностные эволюционные алгоритмы оптимизации сложных систем / Е.С. Семёнкин, Е.А. Сопов // Труды Международных научно-практических конференций AIS'05/CAD-2005. M.: Физматлит, 2005. - С. 77-78.

121. Сопов, Е.А. Эволюционные алгоритмы моделирования и оптимизации сложных систем: автореф. дисс. на соиск. учен. степ, к.т.н. / Е.А. Сопов. Красноярск: СибГАУ, 2004. - 16 с.

122. Тестирование многослойного персептрона http://poligon. machinelearning.ru/Testing/Report.aspx?ReportID=4.

123. Тэрано, Т. Прикладные нечёткие системы / Т. Тэрано, К. Асаи, М. Сугэно. -М.: Мир, 1993.-368 с.

124. Фаулер, M. UML. Основы. Краткое руководство по унифицированному языку моделирования / М. Фаулер, К. Скотт. СПб.: Символ-Плюс, 2002. - 192 с.

125. Шеферд, Дж. Программирование на Microsoft Visual C++.NET / Дж. Шеферд. М.: Русская редакция, 2003. - 928 с.

126. Шилдт Г. Теория и практика С++ / Г. Шилдт. СПб.: BHV-Санкт1651. Петербург, 1996. 312 с.

127. Ярушкина, Н.Г. Основы теории нечетких и гибридных систем / Н.Г. Ярушкина-М.: Финансы и статистика, 2004.1. СПИСОК ПУБЛИКАЦИЙ АВТОРА

128. Сергиенко, Р.Б. Разработка турнирного метода перераспределения ресурсов между подпопуляциями в коэволюционном алгоритме / Р.Б. Сергиенко // Инновационные недра Кузбасса. IT-технологии: сборник научных трудов. Кемерово: ИНТ, 2007. - С. 401-404.

129. Сергиенко, Р.Б. Системы поддержки принятия решений на основе коэволюционного вероятностного алгоритма / Р.Б. Сергиенко, Е.С. Семенкин // Ползуновский альманах. № 4. - 2008. - С. 217-219.

130. Сергиенко, Р.Б. Составление расписания посадок самолетов коэволюционным алгоритмом условной оптимизации / Р.Б. Сергиенко // Решетневские чтения. Материалы XII Международной научной конференции. Красноярск: СибГАУ, 2008. - С. 308-310.

131. Сергиенко, Р.Б. Коэволюционный алгоритм условной оптимизации «Conditional Coevolution» / Р.Б. Сергиенко // Компьютерные учебные программы и инновации. — № 2. — 2009. — С. 21.

132. Сергиенко, Р.Б. Исследование эффективности коэволюционного генетического алгоритма условной оптимизации / Р.Б. Сергиенко // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнёва. №3 (24). - 2009. - С. 31-36.

133. Sergienko, R.B. Image identification from a satellite with fuzzy genetic algorithm / R.B. Sergienko // The 12th International Scientific and Practical Conference "Modern Technique and Technologies" MTT'2009. Tomsk: TPU Press, 2009. - 137-139 pp.

134. Сергиенко, Р.Б. Метод формирования нечеткого классификатора самонастраивающимися коэволюционными алгоритмами / Р.Б. Сергиенко // Искусственный интеллект и принятие решений. №3. - 2010. - С. 98-106.

135. Сергиенко, Р.Б. Коэволюциоииый алгоритм для задач условной и многокритериальной оптимизации / Р.Б. Сергиенко, Е.С. Семенкин // Программные продукты и системы. №4. - 2010. - С. 24-28.

136. Регистрации программных систем

137. Сергиенко, Р.Б. Коэволюционный алгоритм условной оптимизации «Conditional Coevolution»: свидетельство об отраслевой регистрации разработки. М.: ВНТИЦ, 2008. - № гос. per. 50200802249.

138. Сергиенко, Р.Б. Коэволюционный алгоритм условной многокритериальной оптимизации: свидетельство о государственной регистрации программы для ЭВМ / Р.Б. Сергиенко, Е.С. Семенкин. М.: Реестр программ для ЭВМ, 2009. - № гос. per. 2009616049.

139. Сергиенко, Р.Б. Нечеткий коэволюционный классификатор: свидетельство о государственной регистрации программы для ЭВМ / Р.Б. Сергиенко. -М.: Реестр программ для ЭВМ, 2010. № гос. per. 2010611766.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00