Введение к работе
Актуальность темы
Большинство задач дискретной оптимизации являются труднорешаемыми, т.е. на сегодняшний день для них нет алгоритмов, решающих такие задачи за время, ограниченное некоторым полиномом относительно размера входных данных, и возможно, таких алгоритмов не существует вообще. Трудными также считаются задачи, для которых полиномиальная разрешимость доказана – однако (пока) неизвестны полиномиальные алгоритмы небольших степеней. В то же время оптимизационные задачи выступают в качестве моделей для огромного количества практических задач, возникающих в самых разных сферах практической деятельности. Для эффективного решения задач реальных размерностей применение точных алгоритмов на практике невозможно, поскольку требуют слишком больших затрат машинного времени и памяти. К настоящему времени разработано значительное количество методов для решения задач дискретной оптимизации. Однако решение практических задач требует поиска новых, более эффективных моделей и алгоритмов поиска точных и приближенных решений. Таким образом, исследования в области алгоритмизации труднорешаемых задач остаются по-прежнему актуальными, а их результаты имеют большое практическое значение.
Одним из важнейших направлений здесь является разработка и реализация эвристических алгоритмов, включающих целый комплекс эвристик. Поскольку на практике требуется решение оптимизационных задач в реальном времени, то эффективным является применение т.н. anytime-алгоритмов, которые в каждый определённый момент работы имеют лучшее (на данный момент) приближенное решение. При этом пользователь может просматривать эти псевдооптимальные решения в режиме реального времени, а последовательность таких решений в пределе даёт оптимальное решение. В данной работе исследуется подход к построению anytime-алгоритмов для задач дискретной оптимизации с применением кластеризации подзадач (ситуаций) в целях получения более близкого к оптимальному решения за более короткое время.
Цель работы
Целью работы является повышение эффективности работы эвристических алгоритмов, предназначенных для решения задач дискретной оптимизации, за счет применения эвристик, связанных с кластеризации возникающих в процессе решения подзадач.
Основные задачи исследования:
модификация модели вычислений, представляющей собой незавершенный метод ветвей и границ,
разработка подхода к формированию метрик на множестве подзадач в различных задачах дискретной оптимизации,
разработка оригинального алгоритма кластеризации ситуаций в задачах дискретной оптимизации,
разработка и реализация эвристических алгоритмов для решения задач дискретной оптимизации с применением кластеризации ситуаций,
разработка подхода для создания соответствующих компьютерных программ.
Объект исследования
Объектом исследования являются несколько конкретных задач дискретной оптимизации:
вершинная минимизация недетерминированных конечных автоматов,
минимизация дизъюнктивных нормальных форм,
псевдогеометрическая версия задачи коммивояжёра,
игровые программы для недетерминированных игр (версии бэкгеммона).
Предмет исследования
Предметом исследования являются эвристики для кластеризации ситуаций, возможность и эффективность их применения в совместно разрабатываемом мультиэвристическом методе решения задач дискретной оптимизации.
Методы исследования
В качестве аппарата исследований применяются математические методы разработки и анализа эвристических алгоритмов.
Результаты исследования
Результатами диссертационного исследования являются новые вычислительные методы и алгоритмы, а также полученные новые закономерности, характеризующие изучаемые объекты (решаемые автором задачи дискретной оптимизации).
Научная новизна
Разработанный алгоритм кластеризации является новой модификацией алгоритма из группы “Hierarchical Clustering Algorithms”. Новизна мультиэвристического метода решения задач дискретной оптимизации состоит в применении комплекса эвристик, в том числе кластеризации подзадач на основе разработанных автором метрик. Предложен также подход к разработке компьютерных программ на основе этого метода. Также новыми являются эвристики, предназначенные для работы с деревом перебора в недетерминированных антагонистических играх
Практическая значимость исследования
Разработанные подходы позволяют повысить эффективность работы эвристических алгоритмов для решения задач дискретной оптимизации. Полученные результаты могут быть применены практически для любой оптимизационной задачи.
Достоверность результатов
Достоверность результатов подтверждается результатами вычислительного эксперимента, в ходе которого было проведено сравнение результатов работы программ, работающих с применением предложенных эвристик и без них. Результаты исследований обсуждались на российских и международных конференциях и семинарах.
Основные положения, выносимые на защиту
-
Разработка алгоритма кластеризации и обоснование возможностей его практического применения в некоторых предметных областях.
-
Исследование возможностей применения алгоритма кластеризации в задачах дискретной оптимизации.
-
Разработка конкретных вариантов «матричных» и «списочных» метрик для различных задач дискретной оптимизации.
-
Модификация мультиэвристического подхода решения задач дискретной оптимизации, связанная со включением в работающий в нём незавершённый метод ветвей и границ эвристик для применения кластеризации ситуаций (с использованием «матричной» либо «списочной» метрики).
-
Разработка и компьютерная реализация алгоритмов с применением всех разработанных автором эвристик для решения нескольких задач дискретной оптимизации (вершинной минимизации недетерминированных конечных автоматов, минимизации дизъюнктивных нормальных форм, псевдогеометрической версии задачи коммивояжёра). Описание подхода к созданию таких программ.
-
Разработка эвристического подхода к сравнению эффективности эвристических алгоритмов. Исследование эффективности мультиэвристического подхода к решению задач дискретной оптимизации, модифицированного на основе разработанного алгоритма кластеризации.
-
Разработка алгоритма обработки вершин дерева перебора в недетерминированных антагонистических играх с применением кластеризации ситуаций (позиций) на основе их оценок. Разработка подходов к построению статической и динамической оценок позиций.
Апробация работы
Результаты диссертационной работы докладывались и обсуждались на:
II Всероссийской научно-технической конференции «Искусственный интеллект в XXI веке» (Пенза, 2004);
XIV Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, 2004);
региональной научно-технической конференции «Научные чтения студентов и аспирантов» (Тольятти, 2005);
XI международной конференции “Advances in Computer Games Conference”, ICGA 2005 (Тайвань, Тайпей, 2005);
Всероссийской научной конференции «Методы и средства обработки информации» (Москва, МГУ, 2005);
XVI Международной научно-технической конференции «Математические методы и информационные технологии в экономике социологии и образовании» (Пенза, 2005);
международной конференции “First International Conference on Software and Data Technologies”, ICSOFT 2006 (Португалия, Сетубаль, 2006);
II Международной конференции “Informatics in Secondary Schools: Evolution and Perspectives”, ISSEP 2006 (Литва, Вильнюс, 2006);
IX Международной конференции «Интеллектуальные системы и компьютерные науки» (Москва, МГУ, 2006);
международной конференции “Infinity in Logic and Computation” (ЮАР, Кейптаун, 2007);
международной конференции “9th International Workshop on Computer Science and Information Technologies”, CSIT'2007 (Уфа, 2007);
научном семинаре в НИИ им. И.И.Воровича при ЮФУ (Ростов-на-Дону, 2009).
Публикации
По теме диссертации опубликовано 14 работ, из них 2 – в изданиях, рекомендованных ВАК.
Личный вклад автора
Постановка задач осуществлялась научным руководителем. Описываемые в диссертации математические модели вычислений, их компьютерное исследование и разработанные алгоритмы решения задач дискретной оптимизации выполнены автором самостоятельно либо в соавторстве с научным руководителем и двумя другими соавторами публикаций (А.Н.Радионовым и А.В.Мосеевым).
Структура и объём диссертации
Диссертация состоит из введения, 6 глав, 2 приложений и списка литературы, состоящего из 102 наименований источников отечественных и зарубежных авторов. Общий объём диссертации составляет 152 страницы.
