Введение к работе
з
Актуальность темы исследования
ДСМ-метод автоматического порождения гипотез предоставляет один из способов выявления причинно-следственных связей между структурой объекта исследования и его свойствами. Метод представляет собой ориентированную на компьютерные приложения формализацию правдоподобных рассуждений, реализующую синтез познавательных процедур - индукции, аналогии и абдукции. ДСМ-метод успешно применяется в различных областях, в том числе фармакологии, медицинской диагностике, социологии.
Рассматривая характеристики объектов, отобранных в качестве обучающих примеров, ДСМ-система устанавливает все возможные сходства. При этом порождается полный список гипотез о возможных причинах наличия либо отсутствия у объектов определенных свойств. Полученное множество гипотез используется самой системой для построения предсказаний. Кроме того, некоторые гипотезы представляют самостоятельный интерес для исследователя, работающего в соответствующей области, указывая на действительные причины наблюдаемых явлений.
Поскольку средства выдвижения гипотез в ДСМ-методе представляют собой совокупность переборных алгоритмов, возникают ограничения, связанные с величиной используемых массивов данных. Количество порожденных ДСМ-системой гипотез зависит от особенностей конкретной ситуации (количества и вида примеров, а также настроек алгоритма ДСМ-метода) и в некоторых случаях оказывается чрезмерно большим.
В ситуации, когда использование всего множества ДСМ-гипотез становится невозможным из-за его необозримости (при работе с ним эксперта), либо вычислительных проблем (в рамках самой ДСМ-системы), приобретает практическую значимость приближенный подход, позволяющий перейти к подмножеству небольшой мощности. Ограничения, связанные с требованием
минимизации потерь при отсеивании посторонних гипотез, приводят к необходимости решения задачи оптимизации.
Детерминированные и стохастические методы решения оптимизационных задач обладают своими достоинствами и недостатками. Объединить преимущества направленного и случайного поиска способны эволюционные алгоритмы. При этом для максимально полного использования их возможностей необходима модификация и настройка алгоритма с учетом особенностей решаемой задачи. В связи с тем, что оптимизация множества ДСМ-гипотез в качестве области применения эволюционных методов ранее не рассматривалась, проблема адаптации механизма эволюционного поиска для решения указанной задачи представляет научное и практическое значение, что и определило актуальность выбранной темы исследования.
Целью работы является разработка алгоритма, реализующего приближенные средства выбора оптимального множества ДСМ-гипотез.
Для реализации указанной цели в диссертационной работе решались следующие задачи:
изучение особенностей работы ДСМ-системы и проблем, связанных с большим объемом перебора и необходимостью его сокращения;
анализ различных методов решения комбинаторных задач;
исследование работы классического генетического алгоритма и выявление условий его успешного применения;
обоснование необходимости модификации классического генетического алгоритма для решения задачи оптимизации множества ДСМ-гипотез;
разработка алгоритма поиска, основанного на эволюционной модели.
Предметом диссертационного исследования являются алгоритмы решения комбинаторных задач.
Основными методами решения поставленных задач являются анализ принципов работы различных оптимизационных алгоритмов, тестирование алгоритмов с использованием данных из различных предметных областей.
Основные результаты работы:
продемонстрирована ограниченность возможностей генетических алгоритмов при решении оптимизационных задач;
разработан эволюционный алгоритм поиска, учитывающий структуру ДСМ-гипотез;
выполнена экспериментальная проверка работоспособности различных методов поиска, включая разработанный алгоритм, на нескольких массивах эмпирических данных;
проанализированы результаты тестирования алгоритма обработки множества ДСМ-гипотез.
Научная новизна работы заключается в постановке задачи сокращения множества ДСМ-гипотез и ее решении с использованием эволюционных моделей. В ходе исследования:
изучена взаимосвязь между механизмом работы генетических операторов и возможностями генетического алгоритма в области решения комбинаторных задач;
обоснована необходимость использования знаний об особенностях решаемой задачи для успешного применения эволюционных алгоритмов;
предложен метод поиска оптимального подмножества множества ДСМ-гипотез;
впервые разработана версия приближенного ДСМ-метода автоматического порождения гипотез, допускающая работу с большими массивами данных.
Практическая значимость работы состоит в следующем:
разработанный алгоритм позволяет получить сокращенный список гипотез, упрощающий работу эксперта в процессе выявления причинно-следственных связей;
выбор оптимального множества гипотез позволяет сократить перебор при применении ДСМ-системой правил второго рода (вывода по аналогии);
результаты анализа особенностей работы эволюционных алгоритмов могут быть использованы при создании программных систем.
Апробация работы. Основные положения диссертационной работы были изложены на Двенадцатой национальной конференции по искусственному интеллекту с международным участием КИИ-2010 (20-24 сентября 2010г., г. Тверь, Россия).
Публикации. По теме диссертационного исследования опубликовано 6 работ, среди которых 3 работы в ведущих рецензируемых научных журналах, рекомендованных ВАК.
Структура диссертационного исследования. Диссертационная работа состоит из введения, трех глав, заключения и библиографического списка использованной литературы.
