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

Я04Ы 6301

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

4

/I Шашкин Леонид Олегович

Приближенные средства установления сходств для ДСМ-метода автоматического порождения гипотез

Специальность 05.13.17 - Теоретические основы информатики

Автореферат

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

- 2 ДЕН 2010

Москва-2010

004616301

Работа выполнена в Российском государственном гуманитарном университете

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

Финн Виктор Константинович

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

Еремеев Александр Павлович

кандидат физико-математических наук, доцент Забежайло Михаил Иванович

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

Защита состоится 15 декабря 2010 г. в 1330 на заседании диссертационного совета Д 002.026.01 во Всероссийском институте научной и технической информации РАН по адресу: 125190, Москва, ул. Усиевича, д. 20.

■к

С диссертацией можно ознакомиться в библиотеке Всероссийского института научной и технической информации РАН.

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

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

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

Цветкова Валентина Алексеевна

Общая характеристика работы

Актуальность темы исследования

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

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

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

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

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

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

Целью работы является разработка алгоритма, реализующего приближенные средства выбора оптимального множества ДСМ-гипотез.

Для реализации указанной цели в диссертационной работе решались следующие задачи:

• изучение особенностей работы ДСМ-системы и проблем, связанных с большим объемом перебора и необходимостью его сокращения;

• анализ различных методов решения комбинаторных задач;

• исследование работы классического генетического алгоритма и выявление условий его успешного применения;

• обоснование необходимости модификации классического генетического алгоритма для решения задачи оптимизации множества ДСМ-гипотез;

• разработка алгоритма поиска, основанного на эволюционной модели.

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

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

Основные результаты работы:

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

• разработан эволюционный алгоритм поиска, учитывающий структуру ДСМ-гипотез;

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

• проанализированы результаты тестирования алгоритма обработки множества ДСМ-гипотез.

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

множества ДСМ-гипотез и ее решении с использованием эволюционных

моделей. В ходе исследования:

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

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

• предложен метод поиска оптимального подмножества множества ДСМ-гипотез;

• впервые разработана версия приближенного ДСМ-метода автоматического порождения гипотез, допускающая работу с большими массивами данных.

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

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

• выбор оптимального множества гипотез позволяет сократить перебор при применении ДСМ-системой правил второго рода (вывода по аналогии);

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

Апробация работы. Основные положения диссертационной работы были изложены на Двенадцатой национальной конференции по искусственному интеллекту с международным участием КИИ-2010 (20-24 сентября 2010г., г. Тверь, Россия).

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

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

Краткое содержание работы

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

В первой главе «Задача оптимизации множества ДСМ-гипотез и возможные пути ее решения» рассмотрены основные понятия ДСМ-метода, проанализирована работа простого генетического алгоритма как представителя семейства эволюционных методов, и выявлены условия его успешного применения.

ДСМ-метод автоматического порождения гипотез является теорией автоматизированных рассуждений и способом представления знаний для решения задач прогнозирования в условиях неполноты информации. Описание метода берется из работ [Аншаков, 1999] и [Финн, 1999].

ДСМ-метод рассматривает множество объектов О. Объекты можно отождествить с их описаниями, поскольку способ описания в рамках одного вычислительного эксперимента фиксирован. Р - множество свойств объектов, С- множество характеристик объектов, претендующих на роль возможных причин их свойств, V = {+1, —1, 0, т} - множество типов истинностных значений, предназначенных для описания фактов.

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

Функция F:OxP->V представляет начальную ситуацию (базу фактов).

Объект о называется положительным примером для свойства р, если F(p,p) = +\.

Характеристика (фрагмент представления) с может быть извлечена из описания объекта о. Характеристика, которая извлекается из описания каждого объекта некоторого множества, называется сходством, с удовлетворяет (+)-условию для р (соответствующий предикат обозначается ht{F, с, р)), если является сходством для достаточно большого множества (+)-примеров.

Аналогично определяются отрицательные и противоречивые примеры, а также вводятся предикаты, которые обозначаются M~(F, с, р) и M°(F, с, р).

Задача ДСМ-системы состоит в том, чтобы доопределить функцию F, то есть избавиться от значений т.

ДСМ-система строит все возможные гипотезы, опираясь на правила первого рода

+1, если М+(F, с, р) & -iM~(F, с, р) & -,М° (F, с, р); . -1 ,ewuM-(F,c,p)&^M+(F,c,p)&^M\F,c,p);

О, если (М+ (F,с,р) & М'(F,с,р)) v М°(F,с,р); г, если -М+(F, с, р) & -лМ' (F, с, р) & -М0 (F, с, р).

Эти правила соответствуют индуктивному рассуждению. Доопределение (т)-примеров происходит при помощи аналогии, которая представляется формально в виде правил второго рода.

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

Преобразование данных в ДСМ-системе представлено на схеме (Рис. 1).

Рис. 1 Преобразование данных в ДСМ-системе.

Итак, множество порожденных правилами первого рода гипотез используется самой системой для доопределения примеров. Количество гипотез зависит от особенностей конкретной ситуации (количества и вида примеров, а также настроек алгоритма ДСМ-метода) и в некоторых случаях оказывается чрезмерно большим, что может затруднить работу системы [Кузнецов, 1991]. Средства выдвижения гипотез в ДСМ-методе представляют собой совокупность переборных алгоритмов исчерпывающего анализа всевозможных вариантов и характеризуются традиционным набором проблем, специфичных для компьютерных алгоритмов такого типа: построение оценок вычислительной сложности, сокращение перебора, поиск эффективных алгоритмов и т.п. [Забежайло, 1988].

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

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

множества должна быть близка к минимально возможной. Если такое подмножество существует, то множество ДСМ-гипотез оказывается в рассмотренном смысле избыточным и возможно его сокращение.

Задача выбора обладающего перечисленными свойствами подмножества гипотез из множества, порожденного ДСМ-системой, относится к комбинаторным. Задачи, связанные с поиском решения в конечном, но большом множестве возможных вариантов, встречаются во многих областях. Методы их решения в случае, когда полный перебор затруднен или невозможен, можно разделить на детерминированные и стохастические. У каждой из двух групп имеются как сильные, так и слабые стороны.

В качестве одного из способов объединения свойства универсальности вероятностных методов с возможностями целенаправленного поиска, которыми обладают детерминированные методы, рассматриваются генетические алгоритмы [Holland, 1975], [Goldberg, 1989]. Название алгоритмов связано с использованием эволюционных моделей для поиска в символьном пространстве. Их работа в некоторых аспектах похожа на борьбу за существование живых организмов, образующих единую систему. Эти алгоритмы являются итерационными, и их отличительными признаками можно считать параллельную работу с несколькими допустимыми решениями, которые конкурируют между собой, а также обмен информацией в процессе преобразования решений.

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

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

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

Наиболее известным и удобным для изучения является простой генетический алгоритм [Гладков и др., 2006], устроенный следующим образом.

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

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

Мутация - изменяется случайный двоичный символ или группа символов (ген) в некоторой хромосоме. Хромосома (аи...,ак,...,а„) заменяется хромосомой (йгь..., 1-ак,..., а„), где а, е {0, 1},/= 1 ,...,и.

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

(«ь---, ак, ......... ап) и {Ъ\,..., Ък, Ьк+ ь.„, Ь„) преобразуются в (а,.....ак, Ьм,..., Ь„)

и {Ьи...,Ък,ам.....а„), где а* е {0,1 },Ьке {0, 1},;= 1,..., и.

Репродукция - хромосома копируется без изменений.

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

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

решений с последующей селекцией обеспечивает переход к новой популяции той же численности - следующему поколению хромосом.

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

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

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

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

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

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

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

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

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

Допустим, что генетическим алгоритмом найдено решение задачи. Пусть хромосома, соответствующая оптимальному решению, получена в результате применения оператора кроссинговера (для мутации рассуждение повторяется почти дословно). Обозначив фрагменты хромосом буквами, запишем найденное решение в виде (А|, Аз). Каждый из родителей этой хромосомы содержит фрагмент оптимального решения: (А|, В) и (С, Аг). Таким образом, генетический алгоритм не сможет решить задачу, если для скрещивания не будут отобраны хромосомы, содержащие фрагменты оптимальной. Поэтому хромосоме, содержащей фрагмент оптимального решения, должна соответствовать достаточное, с учетом критерия отбора, значение целевой функции независимо от оставшейся части (этот остаток может быть каким угодно, поскольку не используется в окончательном решении). В то же время добавление новых фрагментов оптимального решения должно сопровождаться монотонным увеличением значения целевой функции, иначе решение задачи может быть найдено лишь случайно, а не создано в ходе эволюции: Р(С, В)<Е(А1,В)<Р(А1, Аг). Это требование можно было бы назвать также «непрерывностью» функции приспособленности в окрестности оптимального решения: хромосомы, имеющие много общих элементов с оптимальной, должны оцениваться почти так же высоко.

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

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

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

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

Задача, для решения которой необходимо разработать алгоритм, в общем виде выглядит следующим образом. ДСМ-система работает с объектами, которые представляют собой кортежи закодированных фрагментов структуры. Сходство - кортеж, содержащий фрагменты, которые являются общими для некоторого множества примеров. Анализируя обучающие примеры, ДСМ-система порождает множество гипотез. Требуется из множества большой мощности выделить подмножество, содержащее гипотезы, абдуктивно объясняющие те же примеры, что и исходное множество. Оптимальным будет считаться подмножество минимальной мощности.

Если множество гипотез уже сформировано ДСМ-системой и определено множество примеров, которые могут быть объяснены, то для ответа на вопрос, объясняется ли данный пример подмножеством гипотез, достаточно сравнить

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Модифицируем генетический алгоритм, заменив операторы мутации и кроссинговера процедурами удаления гипотез из решения и объединения решений (Рис.2).

Рис.2 Эволюционный алгоритм

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

множества с вероятностью р = где $|п1 - количество элементов,

■^тт

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

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

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

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

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

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

Изучая различные алгоритмы преобразования множества гипотез, порожденных ДСМ-системой, выберем конкретную задачу, чтобы иметь возможность оценить результаты работы рассматриваемых алгоритмов. В качестве первого примера рассмотрим гипотезы, построенные на данных из области фармакологии [Блинова и др., 2010].

Структура химического соединения может быть описана на языке ФКСП (фрагментарный код суперпозиции подструктур) [Блинова и др., 2000]. В этом случае соединение кодируется набором дескрипторов, характеризующих тип груш! атомов и их взаимное расположение. Часть используемых в качестве примеров соединений оказывают одинаковое специфическое действие, в то время как у остальных это свойство отсутствует, что позволяет разделить примеры на положительные и отрицательные. На активность соединения может влиять присутствие в молекуле определенных фрагментов, поскольку именно они участвуют в химическом взаимодействии. Так как общие для некоторой группы объектов дескрипторы рассматриваются ДСМ-системой в качестве возможной причины наличия либо отсутствия у соответствующей группы соединений заданного свойства, можно надеяться, что некоторые из найденных гипотез соответствуют реальным причинам биологической активности. При этом можно ожидать, что количество таких причин будет небольшим.

Один цикл «индукция - аналогия» ДСМ-метода с запретом на контрпример породил множество гипотез о причинах, которое было использовано для дальнейшей обработки. Его количественные характеристики представлены в виде таблицы (табл. 1).

Таблица 1

Характеристики множества ДСМ-гипотез (фармакологические данные)

Гипотезы Количество гипотез Примеры Количество объясненных примеров Количество доопределенных (т)-примеров

(+)-гипотезы 15 (+)-примеры 11 18

(-)-гипотезы 116 (-)-примеры 43 13

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

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

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

В качестве другой тестовой задачи рассматривались данные медицинской диагностики. В качестве объектов ДСМ-система использовала характеристики пациентов [Михайлова и др, 2010]. После двух циклов «индукция - аналогия» с запретом на контрпример было получено множество гипотез, характеристики множества представлены в таблице 2.

Таблица 2

Характеристики множества ДСМ-гипотез (медицинская диагностика)

Гипотезы Количество Примеры Количество Количество

гипотез объясненных доопределенных

примеров (т)-примеров

(+)-гипотезы 64 (+)-примеры 16 0

(-)-гипотезы 38 (-)-примеры 8 2

Обрабатывая множество (+)-гипотез, жадный алгоритм получил множество, содержащее 5 гипотез. Модифицированный эволюционный алгоритм обнаружил четыре различных решения, содержащих по 4 гипотезы. Найденные решения объясняли все (+)-примеры. Доля наиболее успешных попыток у эволюционного алгоритма составила 11%. Простой генетический алгоритм обнаружил лишь решения, содержащие 9 и более гипотез. Работая с

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

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

Заключение

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

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

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

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

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

4. Разработаны вероятностные процедуры поэтапной модификации множеств, предназначенные для работы с множеством ДСМ-гипотез.

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

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

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

Библиографический список использованной литературы

1. Аншаков О.М. Об одной интерпретации ДСМ-метода автоматического порождения гипотез // НТИ. Сер. 2. 1999. N 1-2. С. 45-53.

2. Блинова В.Г., Добрынин Д.А. Языки представления химических структур в интеллектуальных системах для конструирования лекарств // НТИ. Сер. 2.2000. N 6. С. 14-21.

3. Блинова В.Г., Решетникова В.В., Булычев Ю.Н., Добрынин Д.А. Интеллектуальный анализ цитотоксической активности химических соединений с помощью стратегий ДСМ-метода // НТИ Сер, 2. 2010. N6. С. 14-23.

4. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы / Под ред. В.М. Курейчика. М.: ФИЗМАТЛИТ, 2006. -320 с.

5. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. - М.: ФИЗМАТЛИТ, 2003. - 432 с.

6. Забежайло М.И. О характеристиках переборных зада«, возникающих при автоматическом порождении гипотез ДСМ-методом // НТИ. Сер. 2.1988. N1.0. 28-31.

7. Кузнецов С.О. Сложность алгоритмов обучения и классификации, основанных на поиске пересечения множеств // НТИ. Сер. 2. 1991. N 9.С. 8-9.

8. Курейчик В.М., Родзин С.И. Эволюционные вычисления: генетическое и эволюционное программирование // Новости искусственного интеллекта. 2003. N5. С. 13-19.

9. Михайлова И.Н., Панкратова Е.С., Добрынин Д.А., Самойленко И.В., Решетникова В.В., Шелепова В.М., Демидов J1.B., Барышников А.Ю., Финн В.К. О применении интеллектуальной компьютерной системы для анализа клинических данных больных меланомой // Российский Биотерапевтический Журнал N2, Том 9, 2010. С. 54.

Ю.Рутковская Д., Пилиньский М., Рутковский JI. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польского И.Д. Рудинского. - М.: Горячая линия - Телеком, 2006. - 452 с.

11 .Финн В.К. Синтез познавательных процедур и проблема индукции // НТИ. Сер. 2.1999. N 1-2. С. 8-45.

12.Харчевникова Н.В., Блинова В.Г., Добрынин Д.А., Нович М., Врачко М. Интеллектуальный анализ канцерогенности химических соединений с помощью стратегий ДСМ-метода // НТИ. Сер. 2. 2009. N11. С. 18-23.

13.Goldberg D.E., Genetic Algorithms in Search, Optimization and Machine Learning // McGraw-Hill, USA, 1989.

14.Holland J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control andArtificial Intelligence. - USA: University of Michigan, 1975.

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

Публикации в изданиях, рекомендованных ВАК

1. Балдин Е.В., Шашкин JI.O. Генетические алгоритмы: возможности и ограничения // НТИ. Сер. 2. 2000. N 8. С. 19-33.

2. Шашкин JI.O. Применение методов эволюционного моделирования для оптимизации множества ДСМ-гипотез // Искусственный интеллект и принятие решений, N 3,2010. С. 33-39.

3. Шашкин Л.О. Сравнение приближенных способов поиска сходств для ДСМ-метода // НТИ. Сер. 2. 2010. N 12. С. 9-13.

Другие публикации

4. Балдин Е.В., Шашкин Л.О. Об эффективности генетических алгоритмов // Математические методы решения инженерных задач. -М.: МО РФ, 1999. С. 5-11.

5. Шашкин Л.О. Применение генетических алгоритмов к оптимизационным задачам // Математика и практика; Математика и культура. - М.: Редакция журнала «Самообразование» и МО «Семигор», 2000. С. 50-58.

6. Шашкин Л.О. Применение генетических алгоритмов для решения оптимизационных задач // Двенадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2010 (20-24 сентября 2010 г., г. Тверь, Россия): Труды конференции. Т. 2. -М.: Физмалит, 2010. С. 397-405.

Подписано в печать 09.11.2010. Уч.-изд. л. 1,0 Тираж 100 экз. Заказ

Издательский центр Российского государственного гуманитарного университета 125993, Москва, Миусская пл. 6

Введение

Глава 1. Задача оптимизации множества ДСМ-гипотез и возможные пути ее решения

1.1. ДСМ-метод автоматического порождения гипотез, абдуктивное объяснение как критерий ценности результата

1.2. Методы решения комбинаторных задач, направленный и случайный поиск

1.3. Генетические алгоритмы и условия их успешного применения

Глава 2. Разработка процедур эволюционного поиска сходств

2.1. Пути преодоления проблем классического генетического алгоритма

2.2. Удаление гипотез в процессе преобразования решений

2.3. Объединение решений как метод передачи информации

2.4. Взаимодействие процедур и выбор значений параметров

Глава 3. Результаты эксперимента и их интерпретация

3.1. Фармакология

3.2. Медицинская диагностика

Актуальность темы исследования

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

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

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

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

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

Целью работы является разработка алгоритма, реализующего приближенные средства выбора оптимального множества ДСМ-гипотез.

Для реализации указанной цели в диссертационной работе решались следующие задачи:

• изучение особенностей работы ДСМ-системы и проблем, связанных с большим объемом перебора и необходимостью его сокращения;

• анализ различных методов решения комбинаторных задач;

• исследование работы классического генетического алгоритма и выявление условий его успешного применения;

• обоснование необходимости модификации классического генетического алгоритма для решения задачи оптимизации множества ДСМ-гипотез;

• разработка алгоритма поиска, основанного на эволюционной модели.

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

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

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

• разработан эволюционный алгоритм поиска, учитывающий структуру ДСМ-гипотез;'

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

• проанализированы результаты тестирования алгоритма обработки множества ДСМ-гипотез.

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

• изучена взаимосвязь между механизмом- работы генетических операторов и возможностями генетического алгоритма в области решения комбинаторных задач;

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

• предложен метод поиска оптимального подмножества множества ДСМ-гипотез;

• впервые-разработана версия приближенного ДСМ-метода. автоматического порождения гипотез, допускающая работу с большими массивами данных.

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

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

• выбор оптимального множества гипотез позволяет сократить перебор при применении ДСМ-системой правил второго рода (вывода по аналогии);

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

Апробация работы. Основные положения диссертационной работы были изложены на Двенадцатой национальной конференции по искусственному интеллекту с международным участием КИИ-2010 (20-24 сентября 2010г., г. Тверь, Россия).

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

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

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

Количество Объяснено Доопределено гипотез (-)-примеров (т)-примеров Частота

Исходное множество гипотез 38 8 2

Решение идентификаторы гипотез)

84} 1 8 2 93

72, 84} 2 8 2 1

84, 101} 2 8 2 1

84, 90} 2 8 2 5

Среднее значение 1,07 8 2

Наименьшее и наибольшее значения

Мт,Мах] [1,21 [В, 81 [2, 2]

Ср. кв. отклонение 0,26 0 0

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

4. Разработаны вероятностные процедуры поэтапной модификации множеств, предназначенные для работы с множеством ДСМ-гипотез.

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

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

1. Аншаков О.М. Об одной интерпретации ДСМ-метода автоматического порождения гипотез //НТИ. Сер. 2. 1999. N 1-2. С. 45-53.

2. Блинова В.Г., Добрынин Д.А. Языки представления химических структур в интеллектуальных системах для конструирования лекарств // НТИ. Сер. 2. 2000. N 6. С. 14-21.

3. Блинова В.Г., Решетникова В.В., Булычев Ю.Н., Добрынин Д.А. Интеллектуальный анализ цитотоксической активности химических соединений с помощью стратегий ДСМ-метода // НТИ Сер. 2. 2010. N6. С. 14-23.

4. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы / Под ред. В.М. Курейчика. М.: ФИЗМАТЛИТ, 2006. -320 с.

5. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: ФИЗМАТЛИТ, 2003. - 432 с.

6. Забежайло М.И. О характеристиках переборных задач, возникающих при автоматическом порождении гипотез ДСМ-методом // НТИ. Сер. 2. 1988. N1.0. 28-31.

7. Кузнецов С.О. Сложность алгоритмов обучения и классификации, основанных на поиске пересечения множеств // НТИ. Сер. 2. 1991. N 9. С. 8-9.

8. Курейчик В.М., Родзин С.И. Эволюционные вычисления: генетическое и эволюционное программирование // Новости искусственного интеллекта. 2003. N5. С. 13-19.

9. Ю.Рутковская Д., Пилиньский М., Рутковский JI. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польского И.Д. Рудинского. М.: Горячая линия - Телеком, 2006. - 452 с.

10. Финн В.К. Синтез познавательных процедур и проблема индукции // НТИ. Сер. 2. 1999. N 1-2. С. 8-45.

11. Харчевникова Н.В., Блинова В.Г., Добрынин Д.А., Нович М., Врачко М. Интеллектуальный анализ канцерогенности химических соединений с помощью стратегий ДСМ-метода // НТИ. Сер. 2. 2009. N11. С. 18-23.

12. Goldberg D.E., Genetic Algorithms in Search, Optimization and Machine Learning // McGraw-Hill, USA, 1989.

13. Holland J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control andArtificial Intelligence. USA: University of Michigan, 1975.

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

15. Публикации в изданиях, рекомендованных ВАК

16. Балдин Е.В., Шашкин Л.О. Генетические алгоритмы: возможности и ограничения // НТИ. Сер. 2. 2000. N 8. С. 19-33.

17. Шашкин Л.О. Применение методов эволюционного моделирования для оптимизации множества ДСМ-гипотез // Искусственный интеллект и принятие решений, N 3, 2010. С. 33-39.

18. Шашкин Л.О. Сравнение приближенных способов поиска сходств для ДСМ-метода//НТИ. Сер. 2. 2010. N 12. С. 9-13.701. Другие публикации

19. Балдин Е.В., Шашкин JI.O. Об эффективности генетических алгоритмов // Математические методы решения инженерных задач. -М.: МО РФ, 1999. С. 5-11.

20. Шашкин JI.O. Применение генетических алгоритмов к оптимизационным задачам // Математика и практика; Математика и культура. М.: Редакция журнала «Самообразование» и МФ «Семигор», 2000. С. 50-58.