Применение кластеризации ситуаций в эвристических алгоритмах для задач дискретной оптимизации
На правах рукописи
Мельникова Елена Анатольевна
Применение кластеризации ситуаций
в эвристических алгоритмах
для задач дискретной оптимизации
05.13.18 – математическое моделирование,
численные методы и комплексы программ
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата физико-математических наук
Тольятти – 2009
Работа выполнена в Тольяттинском государственном университете
Научный руководитель: доктор физико-математических наук,
профессор Мельников Борис Феликсович
Официальные оппоненты: доктор физико-математических наук,
профессор Смирнов Юрий Геннадьевич
доктор физико-математических наук,
доцент Сафронов Александр Иванович
Ведущая организация: НИИ Механики и прикладной математики
им. И.И. Воровича
Южного Федерального Университета
Защита диссертации состоится «29» декабря 2009 года в 12 часов на заседании диссертационного совета Д212.264.03 при Тольяттинском государственном университете по адресу: 445667, Тольятти, ул. Белорусская, 14
С диссертацией можно ознакомиться в библиотеке Тольяттинского государственного университета.
Отзывы по данной работе в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 445667, Тольятти, ул. Белорусская, 14, ТГУ, диссертационный совет Д212.264.03
Автореферат разослан «___» ноября 2009 года
Учёный секретарь
диссертационного совета
Д212.264.03 ________ _к.п.н. Пивнева С.В.
Общая характеристика работы
Актуальность темы
Большинство задач дискретной оптимизации являются труднорешаемыми, т.е. на сегодняшний день для них нет алгоритмов, решающих такие задачи за время, ограниченное некоторым полиномом относительно размера входных данных, и возможно, таких алгоритмов не существует вообще. Трудными также считаются задачи, для которых полиномиальная разрешимость доказана – однако (пока) неизвестны полиномиальные алгоритмы небольших степеней. В то же время оптимизационные задачи выступают в качестве моделей для огромного количества практических задач, возникающих в самых разных сферах практической деятельности. Для эффективного решения задач реальных размерностей применение точных алгоритмов на практике невозможно, поскольку требуют слишком больших затрат машинного времени и памяти. К настоящему времени разработано значительное количество методов для решения задач дискретной оптимизации. Однако решение практических задач требует поиска новых, более эффективных моделей и алгоритмов поиска точных и приближенных решений. Таким образом, исследования в области алгоритмизации труднорешаемых задач остаются по-прежнему актуальными, а их результаты имеют большое практическое значение.
Одним из важнейших направлений здесь является разработка и реализация эвристических алгоритмов, включающих целый комплекс эвристик. Поскольку на практике требуется решение оптимизационных задач в реальном времени, то эффективным является применение т.н. 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 страницы.
Основное содержание работы
В первой главе диссертации содержится описание задач дискретной оп-тимизации и применяемых методов их решения – как классических, так и раз-работанных автором диссертации. В первом разделе приведено описание не-скольких классических задач дискретной оптимизации (ЗДО). Во втором разделе со-держится обзор классических подходов к созданию эвристических алгоритмов решения задач дискретной оптимизации. В третьем разделе наиболее подроб-но описаны те задачи, на которые делается упор в настоящей диссертации: за-дача вершинной минимизации недетерминированных конечных автоматов (НКА), задача минимизации дизъюнктивных нормальных форм (ДНФ) и псев-догеометрическая версия задачи коммивояжёра (ЗКВ). Рассматривается именно эта версия ЗКВ по следующим причинам:
- псевдогеометрической версия является моделью, которая более точно описывает задачи, возникающие на практике,
- в этом случае один шаг МВГ в среднем не дает значительного упрощения рассматриваемой матрицы ЗКВ,
- именно для этой версии могут быть проверены различные эвристики, не связанные с использованием расположения городов на плоскости, а сведние такой ЗКВ к задачам линейного программирования, по-видимому, малоэффективно.
Четвёртый раздел посвящен алгоритмам решения задач дискретной оп-тимизации, которые могут быть построены только на основе т.н. «жадных» эв-ристик. Приведены интересные примеры, когда эти простейшие эвристические алгоритмы не дают оптимального решения. Здесь же кратко описан классический вариант метода ветвей и границ. В пятом разделе описан разрабатываемый мультиэвристический подход к решению задач дискретной оптимизации – именно к эвристикам этого подхода добавляются эвристики, разработанные ав-тором диссертации.
Вторая глава посвящена предлагаемому алгоритму кластеризации. Здесь приведены данные о самом алгоритме; в частности, даны ссылки на схожие алгоритмы, разрабатываемые другими авторами. Кратко рассмотрены некоторые возможные прикладные области практического применения подобных алгоритмов. Также приведены априорные эвристические обоснования применения авторского алгоритма для работы «по аналогии» с подзадачами (ситуациями), получаемыми в процессе решения различных задач дискретной оптимизации (ЗДО).
Если говорить неформально, то сходство предлагаемого алгоритма с большинством других алгоритмов (принадлежащих этой же группе, т.е. “Hierarchical Clustering Algorithms”) состоит в том, что в качестве «положительной характеристики» используется минимальное расстояние между кластерами. А основное его отличие – в том, что в качестве «отрицательной характеристики» используется не максимальное расстояние среди элементов одного кластера, а минимальный шаг, применяя который можно построить последовательность попарно близких друг к другу элементов, включающую все элементы кластера. Для вычисления расстояния используются несколько вариантов метрик.
Приведём более формальное описание. Пусть Rij – минимальное расстояние между элементами, входящими в кластеры с номерами i и j, а ri – максимальное расстояние между элементами кластера i. Стандартные алгоритмы кластеризации указанной группы – а также алгоритмы для оценки её качества – обычно используют значения
где f и g – специальные возрастающие функции (выбираемые в зависимости от конкретной задачи, конкретного алгоритма и др.), а i и j принимают все возможные значения.
В отличие от других стандартных алгоритмов вышеупомянутой группы, используем ту же самую формулу, но с другим смыслом значений ri. А именно, пусть:
- i – рассматриваемый кластер,
- m1,...,mn – все его элементы,
- lmn – расстояние между его элементами m и n,
- (M1,..., MN) – некоторая конечная последовательность, состоящая из элементов кластера m1,...,mn и включающая каждый элемент кластера по крайней мере 1 раз.
Тогда считаем, что
(1)
Заметим, что данное определение не является алгоритмом, однако возможные алгоритмы вычисления значений ri, построенные на основе этого определения, весьма несложны.
Далее в качестве примера конкретной матричной метрики представлена метрика, применяемая автором при разработке эвристических алгоритмов для задачи вершинной минимизации недетерминированных конечных автоматов.
Третья глава диссертации посвящена разработанному подходу к организации незавершённого метода ветвей и границ, а также подходу к сравнительной оценке эффективности эвристических алгоритмов. Во введении содержится неформальное обоснование того, почему предлагаемый автором подход к кластеризации желательно применять именно при кластеризации подзадач в процессе работы незавершённого метода ветвей и границ для решения ЗДО.
В следующем разделе описан подход к решению ЗДО, развитие которого является фактически предметом данной диссертации. Основное содержание подхода - эвристика, преобразующая завершённый метод ветвей и границ (МВГ) в незавершённый. Тогда построенный на ее основе алгоритм становится anytime-алгоритмом. Приведём её краткое описание. Каждый раз при получении очередной задачи (назовём её задачей T) строится последовательность правых подзадач (ППЗ), содержащая саму задачу T, правую подзадачу задачи T, правую подзадачу правой подзадачи задачи T, и так далее. Каждый раз строятся (и включаются в список задач для потенциального решения в дальнейшем) и соответствующие левые задачи – левая подзадача задачи T, левая подзадача правой подзадачи задачи T и так далее. Описанный процесс заканчивается:
- либо при построении тривиальной задачи – в этом случае её решение сохраняется в качестве текущего на данный момент времени псевдо-оптимального решения anytime-алгоритма;
- либо при вычислении в какой-либо задаче достаточно «плохой» границы (например, в случае задачи максимизации можно получить границу больше, чем стоимость имеющегося на данный момент времени псевдо-оптимального решения).
Отметим, что на практике описанный процесс построения последовательности ППЗ не занимает много лишнего времени и не приводит к большому увеличению списка задач, предназначенных для потенциального решения в будущем.
Следующий раздел представляет собой подробное описание мультиэвристического алгоритма решения ЗДО[1]. В настоящем автореферате, в связи с ограничениями на его объём, мы приводим только краткое его описание, схему. Основу алгоритма составляет итеративный шаг, результатом выполнения которого является очередное пседооптимальное решение, с каждым шагом все больше и больше приближающееся к оптимальному.
loop{
Шаг 1. Выбор очередной подзадачи для рассмотрения, выбор для нее разделяющего элемента и построение описанной выше последовательности ППЗ; т.е. реализация одного шага МВГ.
Шаг 2. Накопившиеся при построении последовательности ППЗ левые подзадачи образуют «малый кластер». Далее в соответствии с (1) выполняется дальнейшая кластеризация, в ходе которой малый кластер может быть объединен с уже имеющимися.
Цель кластеризации состоит в следующем: если в будущем для одной из подзадач кластера принимается какое-то решение (о разделяющем элементе), то по возможности, то же самое выполняется и для других. За счет решения подзадач одного кластера «по аналогии», обработка всего кластера выполняется быстро.
Важно отметить, что при кластеризации в последовательности, объединяющей все элементы кластера, возможно выделение подзадач, встречающихся несколько раз (назовём их ключевыми ситуациями). Решение подзадач некоторого кластера начинается с рассмотрения именно ключевых ситуаций, так как они описывают (неявно) разделяющие элементы, лучше всего подходящие для подзадач этого кластера
Шаг 3. Генерация очередного потенциального разделяющего элемента (блока, плоскости и т.п.). В отличие от шага 1, этот разделяющий элемент пока не является конкретным разделяющим элементом для какой-либо конкретной подзадачи. Аналогично 1-му «малому» шагу, сам алгоритм соответствующей генерации тоже сильно зависит от конкретной задачи. Этот шаг выполняется с помощью «жадных» алгоритмов и случайного выбора – и обязательно даёт результат.
Шаг 4. Один шаг метода ветвей и границ для вспомогательной задачи дискретной оптимизации, которая использует метод ветвей и границ не для решения основной задачи, а для построения близких к максимальным (по какой-либо естественной метрике) потенциальных разделяющих элементов. (т.е. блока, плоскости, и т.п ). При этом, в отличие от основной задачи дискретной оптимизации, здесь сохраняются все решения – даже заведомо далёкие от оптимальных, поскольку для дальнейшей работы (для решения основной задачи дискретной оптимизации) нужны, вообще говоря, все потенциальные разделяющие элементы. Поэтому структура вспомогательной подзадачи как объекта другая, но для неё также формируется последовательность ППЗ.
}
В разделе 3.4 предлагается авторский подход к сравнению эффективности эвристических алгоритмов, предназначенных для решения одной и той же задачи дискретной оптимизации. Важно отметить, что какой-либо законченной, «однозначной» теории по поводу подходов к сравнению эффективности эвристических алгоритмов в настоящее время не существует[2]. Описанный подход предполагается применять прежде всего в тех случаях, когда вообще невозможно дать гарантию получения точного оптимального решения. Приведём его описание.
Для проведения вычислительного эксперимента случайно генерируются входные данные рассматриваемой ЗДО. При этом имеется возможность определить некоторую границу (первоначальную оценку) G для стоимости псевдооптимального решения, вычисляемую согласно алгоритмам генерации входных данных. Отметим, что эта граница имеет большую аналогию с т.н. границей Хелда-Карпа[3], т.к. используется для тех же самых целей, но вычисляется значительно более простым способом.
Входами каждого эксперимента являются:
- размерность оптимизационной задачи
- количество случайно сгенерированных задач (например, для заданной размерности запускается 100 случайно сгенерированных задач; отметим, что, как и ожидалось, от входа «100 случайных задач» итоговые результаты практически не зависят).
- относительная величина превышения границы G (обычно это – величина порядка 0.1, т.е. 10%).
Для каждого конкретного варианта входных данных определяется время работы, в течение которого стоимость текущего псевдооптимального решения достигает этой границы G. Надо отметить, что в общем случае нельзя гарантировать, что достижение границы действительно произойдёт. Однако в рассматриваемых конкретных задачах дискретной оптимизации (прежде всего – в задачах минимизации ДНФ и вершинной минимизации НКА, но и не только в них), достижение границы для рассматриваемых типичных «входных данных» происходит гораздо чаще, чем в 50% случаев. Это время (усреднённое для тех задач, где граница была достигнута) назовем «обычным временем для данной размерности», «единицей времени» для входов данной размерности. Отметим, что «входы» 100 и 10% здесь уже не имеют значения.
Тогда для каждого конкретного частного случая проблемы можно рассматривать результаты работы алгоритмов, полученные в течение интервалов времени, составляющих некоторую часть такой единицы времени. Были рассмотрены следующие интервалы времени: 0.1 единицы времени, 0.3 единицы времени, 1.0, 3.0, 10.0, 30.0 и 100.0 единиц времени. Наиболее интересным результатом для дальнейшего анализа является отношение стоимости полученного (за выделенный интервал времени) решения к первоначальной оценке G. В заключении главы описано возможное развитие тем, рассмотренных в ней.
Четвёртая глава посвящена применению кластеризации ситуаций в задачах дискретной оптимизации. Во введении приведено эвристическое обоснование применения предложенного алгоритма кластеризации – для решения различных ЗДО.
Если ранее (в тексте диссертации и автореферата) были рассмотрены общие принципы организации алгоритмов, формирующих кластеры на множестве подзадач, в предположении, что конкретная метрика на множестве подзадач уже задана, то в этой главе рассматриваются два способа построения конкретных вариантов метрики.
- В первом случае метрика на множестве подзадач определяется по фактическому расстоянию между двумя подзадачами, вычисляемому обычно на основе двух матриц, описывающих рассматриваемые подзадачи. Далее будем называть такую метрику «матричной эвристикой».
- Во втором случае метрика на множестве подзадач определяется на основе описания подзадач, которое формируется в процессе работы МВГ и состоит из двух списков, а именно:
- списка выбранных разрешающих элементов;
- списка запрещённых для будущего выбора (т.н. «табуированных») разрешающих элементов.
Далее будем называть такую метрику «списочной эвристикой».
Удачное применение всех эвристик, соответствующих обеим этим метрикам, можно объяснить следующим обстоятельством. Чем ближе одно из вычисленных значений к минимально возможному, тем больше вероятность применения решения «по аналогии» – т.е. выбора того же самого разделяющего элемента. А конкретные функции для вычисления этой вероятности в конкретных алгоритмах нередко формируются с помощью генетических алгоритмов – однако стит отметить, что на практике часто удачно работают их «упрощённые» варианты, в которых эти функции подобраны априори, «естественным образом».
Далее в этой главе представлены результаты работы мультиэвристического алгоритма, решающего задачу минимизации недетерминированных конечных автоматов (НКА) на основе описанного выше подхода. В таблице 1. содержатся результаты 4 вариантов тестирования: им соответствуют столбцы таблицы. В каждом варианте тестирования выбиралась размерность задачи. В случае минимизации НКА, под размерностью понимается максимум из числа состояний двух канонических конечных автоматов: для заданного регулярного языка и для его зеркального образа. Также для каждого варианта специальным образом выбиралось число случайно сгенерированных блоков. Это же число является первоначальной оценкой стоимости псевдооптимального решения (границей G). Строки таблицы соответствуют различным интервалам времени работы алгоритма, длительность которых выражена в процентах от специальной единицы времени, описанной выше.
Значение в таблице – это отклонение средних результатов от первоначальной оценки стоимости решения (границы G), выраженное в процентах от неё. Положительные (отрицательные) величины – означают улучшение (ухудшение) средних результатов по сравнению с используемым числом блоков (т.е. с заданной границей G). Например, значение –0.17 означает, что стоимость полученного решения в среднем хуже заранее известного псевдооптимального решения на 0.17%. Поскольку точное оптимальное решение не известно, а известна только некоторая его верхняя граница, то среди вычисленных есть решения, стоимость которых лучше чем граница. Здесь улучшение может наблюдаться из-за возможного «склеивания» двух блоков в один блок большей размерности. Но значительно более важен следующий практический вывод: все полученные результаты близки к 100%, т.е. вычисленное псевдооптимальное решение близко к ожидаемому. Этот факт показывает, что применяемый нами подход является вполне приемлемым и может быть использован в самых разных задачах дискретной оптимизации.
| НКА | 20–23 | 40–45 | 60–65 | 80–90 |
| 1% | –1.62 | –0.58 | –0.02 | –0.02 |
| 10% | –0.58 | –0.14 | +0.18 | +0,23 |
| 30% | –0.03 | +0.45 | +1,02 | +1,12 |
| 100% | 0 | +1.01 | +1,07 | +1,21 |
| 300% | 0 | +1.08 | +1,19 | +1,21 |
Таблица 1.
Чтобы показать фактические улучшения, полученные за счет применения предложенных автором вспомогательных алгоритмов выбора разрешающего элемента для решения подзадач «по аналогии», на каждом графике представлены результаты работы программ, использующих эвристики, и программ, работающих без них. Сравниваются относительные результаты: отношение стоимости вычисленного в течение заданного интервала времени решения к первоначальной оценке.
 |  |
| Рис. 1. НКА; матричная метрика; 0.1 единицы времени | Рис. 2. НКА; списочная метрика; 0.1 единицы времени |
 |  | ||
| Рис. 3. НКА; матричная метрика; 3 единицы времени | Рис. 4. НКА; списочная метрика; 3 единицы времени | ||
Во всех 4 случаях были случайно сгенерированы НКА размерности 80–90, имеющие 300–350 блоков разных размерностей. Графики на рис.1 и рис.2 описывают решение, найденное в течение интервала времени, равного 1 специальной единице времени, а графики на рис.3 и рис.4 – в течение интервала времени, равного 3 таким единицам.. Графики на рис.1 и рис.3 соответствуют «матричной» эвристике для вычисления метрики, графики на рис.2 и рис.4 – «списочной» эвристике. На каждом из 4 графиков отмечено по 40 точек, каждая из которых представляет собой описание решения одной из 40 случайно сгенерированных задач минимизации НКА (частных случаев проблемы). Х-координата каждой точки - относительный результат работы алгоритма без применения эвристик для решения подзадач «по аналогии», а y-координата – относительный результат работы алгоритма с применением одной из эвристик.
Прямые x=1 и y=1. на каждом из графиков соответствует относительным результатам, равным 1, полученным этими алгоритмами. Кроме того, на каждом графике проведена прямая x=y. Тот факт, что большинство точек двух нижних графиков находятся под прямой x=y, свидетельствует об улучшении результатов работы алгоритмов в результате применения каждой из двух эвристик. Отметим также, что вряд ли возникнет необходимость сравнивать эти две эвристики: по-видимому, в anytime-алгоритмах первую из них есть смысл применять при наличии временных ресурсов – т.е. времени, необходимого для вычисления фактического расстояния между подзадачами.
В следующем разделе главы представлены «матричная метрика» и некоторые результаты счёта для задачи минимизации дизъюнктивных нормальных форм (ДНФ); отметим, что организация таблиц и графиков совпадает с представлением результатов для задачи минимизации НКА – и поэтому в тексте автореферата опущены.
В случае минимизации ДНФ расстояния между подзадачами с применением «матричной метрики» вычисляется следующим образом. Пусть имеются две функции f,g:{0,1}N{0,1}, каждая из которых является описанием текущей подзадачи. Тогда расстояние между подзадачами есть число элементов множества {x
{0,1}N|f(x)g(x)}.
Однако в программе подзадачи-функции представляются в виде множества плоскостей – т.е. фактически в виде тех же ДНФ. Каждая из плоскостей в данном представлении имеет свой номер – и другим вариантом вычисления расстояния («списочной метрикой») можно считать число, обратное к числу совпадающих номеров. При этом для того, чтобы выполнялись необходимые свойства расстояния, должны быть предусмотрены варианты, когда это расстояние равно 0. В данном случае достаточно считать, что это происходит тогда и только тогда, когда обе подзадачи описывают уже решённые задачи – хотя, возможно, ни одно из полученных решений не является оптимальным.
В качестве примера рассмотрим функцию от переменных x1, x2, x3 и x4, принимающую значения 1 на следующих наборах переменных (и только на них):
(0,0,0,0) (1,0,0,0) (0,0,1,0) (1,0,1,0) (1,1,0,0) (0,1,1,0) (0,0,0,1) (1,0,1,1)
Для неё рассмотрим следующие две ДНФ – которые действительно описывают подзадачи в процессе решения:
(x2 & x4) V (x1 & x3 & x4) и (x1 & x3 & x4) V (x1 & x2 & x3).
При этом обе ДНФ одновременно принимают значение 1 в следующих 2 точках (и только в них):
(0,0,1,0) (1,0,1,0)
и поэтому первая метрика даёт значение 1/2 (т.е. значение, обратное к числу совпадающих точек). А вторая метрика при этом может дать значение 1 – значение, обратное к числу общих плоскостей. При этом минимальное (но не равное 0) значение расстояния для случая первой эвристики будет равно 1/7 (т.к. имеется всего 8 точек, значения функции в которых равны 1). А для второй, при дополнительном требовании о вхождении в формируемую ДНФ только максимальных плоскостей, минимальным будет значение 1/4 (т.к. существуют 5 максимальных плоскостей).
Далее представлены «матричная метрика» и некоторые результаты вычислений для псевдо-геометрической версии задачи коммивояжера. Заранее отметим, что автором ещё не производилось сравнение приводимой в данном разделе «матричной метрики» для ЗКВ с другими возможными вариантами «матричных метрик». Однако улучшение практических результатов работы программы при её применении (см. рис.5, 6) говорит о перспективности работ в этом направлении.
Тестирование производилось на основе тестов, полученных путём генерации псевдогеометрических версий, являющихся преобразованиями известного геометрического теста ЗКВ “ber52.txt”.
Расстояние (T1,T2) между подзадачами T1 и T2 вычисляется по следующему алгоритму.
Шаг 1. badness:=0
Шаг 2. badness:=badness+2*N, для каждого i, такого что i-я строка присутствует ровно в одной из матриц подзадач,
Шаг 3. badness:=badness+2*N, для каждого j, такого что j-й столбец присутствует ровно в одной из матриц подзадач,
Шаг 4. badness:=badness+min(Т1(i,j)-Т2(i,j),1.414), для каждых i и j, таких что (i,j)-я клетка присутствует ровно в одной из матриц подзадач[4],
Шаг 5. (T1,T2):=badness
Отметим, что размерности рассматриваемых подзадач могут и не совпадать. Это часто отражает реальную ситуацию. Например, если обе подзадачи являются правой и левой подзадачами, полученными из одной и той же исходной, то полезно две эти подзадачи считать близкими по метрике – несмотря на то, что они обязательно будут иметь разную размерность.
Кроме того, «списочные метрики» (например – их варианты, приведённые в предыдущих разделах, которые возможны и для задачи коммивояжёра) допускают возможность работы с матрицами ЗКВ разных размерностей. При этом подобные метрики (например – число, обратное к числу совпадающих номеров в списках разделяющих элементов) действительно дадут малое итоговое значение.
 |  |
| Рис.5. ЗКВ; матричная метрика; размерность 52;(псевдогеометрические варианты теста«ber52.txt» с дисперсией 0.045) | Рис.6. ЗКВ; списочная метрика; размерность 52; (псевдогеометрические варианты теста «ber52.txt» с дисперсией 0.045) |
В заключительной части приведено описание возможных направлений работы, связанных с развитием тем, рассмотренных в данной главе.
В пятой главе рассматриваются подходы к программированию недетерминированных игр – то есть игр, включающих в себя некоторые случайные факторы. Метод, предлагаемый в настоящей работе, основан на использовании специального дерева поиска для недетерминированных игр и является дополнением (а иногда – альтернативой) методам, использующим только нейросетевые оценочные функции. Предложены некоторые эвристики для упорядочивания вершин в дереве поиска, задающие такой порядок обработки узлов дерева, который в реальном времени и с высокой вероятностью позволяет получать оценку позиции, очень близкую к оптимальной.
Множество ситуаций, возникающих в игре, т.е. множество вершин в дереве поиска можно рассматривать как множество подзадач, возникающих в процессе решения ЗДО с помощью незавершенного метода ветвей и границ. Оценки некоторых вершин могут отличаться весьма несущественно. Поэтому в качестве одной из эвристик, применяемых в процессе обработки вершин дерева поиска, целесообразно использовать разделение множества вершин на кластеры и проводить обработку близких по оценочным значениям вершин «по аналогии», как это делается в ЗДО.
Описание разработанного автором и проверенного при практическом построении игровых программ подхода к организации перебора вершин в дереве поиска, описание применяемых эвристик сопровождается детальными примерами.
Шестая глава диссертации содержит описание применяемого автором подхода к реализации разработанных эвристических алгоритмов. В начале главы приведена программная реализация одной несложной переборной задачи, которая фактически является упрощённым описанием подхода к построению программ для описанных эвристических алгоритмов. Следующие разделы посвящены программной реализации задачи вершинной минимизации НКА и задачи коммивояжёра: описаны основные принципы построения и даны подробные комментарии к программным проектам, тексты которых содержатся в приложениях. В заключении приведено описание применяемых методов программирования – с точки зрения современных методов создания программ в различных средах ООП.
В приложении А содержится практически полный текст программного проекта для решения задачи минимизации недетерминированных конечных автоматов. В приложении Б содержится описание основных классов программного проекта для решения задачи коммивояжёра. Оба проекта выполнены на Си++.
Основные результаты работы
- Разработан алгоритм кластеризации и обоснованы возможности его практического применения в некоторых предметных областях.
- Обоснована эффективность применения предложенного автором алгоритма кластеризации в задачах дискретной оптимизации.
- Разработаны конкретные варианты т.н. «матричных» метрик для нескольких различных задач дискретной оптимизации, а также т.н. «списочной» метрики, возможной для каждой из подобных задач.
- Все разработанные алгоритмы применены в нескольких конкретных задачах дискретной оптимизации. Выполнено сравнение времени работы компьютерных программ, работающих со включением разработанных эвристик, и программ, работающих без этих эвристик.
- Модифицирован мультиэвристический подход к решению задач дискретной оптимизации. Модификации связаны со включением в незавершённый метод ветвей и границ эвристик для применения кластеризации ситуаций (с использованием «матричной» либо «списочной» метрики).
- Разработаны алгоритмы и реализованы компьютерные программы с применением всех рассмотренных эвристик для решения нескольких задач дискретной оптимизации (вершинной минимизации недетерминированных конечных автоматов, минимизации дизъюнктивных нормальных форм, псевдогеометрической версии задачи коммивояжёра). Описан подход к созданию таких программ.
- Предложен эвристический подход к получению сравнительной оценки эффективности эвристических алгоритмов и применен к сравнению реализованных алгоритмов.
- Разработан алгоритм обработки вершин дерева перебора в недетерминированных антагонистических играх на основе кластеризации ситуаций (позиций) в соответствии с их оценками. Разработаны подходы к построению статической и динамической оценок позиций.
ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ
Публикации в изданиях, рекомендованных списком ВАК
- Мельников, Б.Ф. Кластеризация ситуаций в алгоритмах реального времени для задач дискретной оптимизации / Б.Ф.Мельников, Е.А.Мельникова // Системы управления и информационные технологии. – Москва-Воронеж: «Научная книга», №2, 2007. – C. 16-19.
- Мельникова, Е.А. Применение алгоритмов кластеризации в задаче минимизации дизъюнктивных нормальных форм // Известия Самарского центра Российской академии наук. – Самара, издательство Самарского научного центра РАН, выпуск 10, 2008. – С. 242-247
Прочие публикации:
- Мельников, Б.Ф. «Проблема формирования первого экрана» и функции риска / Б.Ф.Мельников, Е.А.Мельникова // Сборник статей II Всероссийской научно-технической конференции «Искусственный интеллект в XXI веке» – Пенза, ПДЗ, 2004, ноябрь. – С. 89- 91.
- Мельникова, Е.А. Применение некоторых методов теории принятия решений при поиске информации в Интернете // Сборник статей XIV Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании». – Пенза, ПДЗ, 2004, 21-22 декабря. – С. 282-284.
- Мельникова, Е.А. Специальные алгоритмы для поисковых машин // Сборник материалов региональной научно-технической конференции «Научные чтения студентов и аспирантов». – Тольятти, ТГУ, 2005, 12-13 апреля. – С. 49-51.
- Мельникова, Е.А. Применение некоторых вопросов теории принятия решений при поиске информации в Интернете // Ученые записки Ульяновского государственного университета. Серия «Информационные технологии». Вып.1 – Ульяновск, УлГУ, 2005. – С.30-33.
- Мельникова, Е.А. Построение классификационной иерархии документов на основе лексико-частотных характеристик с применением функций риска / Е.А.Мельникова, А.Н.Радионов // Труды Всероссийской научной конференции «Методы и средства обработки информации». – Москва, МГУ, 2005, 5-7 октября. – C.103-106.
- Мельникова, Е.А. Применение специальных алгоритмов для кластеризации результатов поиска в Интернете // Сборник статей XVI Международной научно-технической конференции «Математические методы и информационные технологии в экономике социологии и образовании». – Пенза, ПДЗ, 2005, 27-28 декабря. – С.197-198.
- Melnikov, B. Some specific heuristics for situation clustering problems / B.Melnikov, A.Radionov, A.Moseev, E.Melnikova // Proceedings of the First International Conference on Software and Data Technologies». – Setubal, Portugal, INSTICC, 2006, 11-14 September. – P. 272-279.
- Мельников, Б.Ф. Некоторые вопросы кластеризации ситуаций в алгоритмах реального времени / Б.Ф.Мельников, Е.А.Мельникова // Материалы IX Международной конференции «Интеллектуальные системы и компьютерные науки». – Москва, МГУ, 2006, 23-27 октября. – С.200-202.
- Melnikov, B. Some Programming Olympiad Problems with Detailed Solutions / B.Melnikov, E.Melnikova // Proceedings of the Second International Conference “Informatics in Secondary Schools: Evolution and Perspectives”. – Vilnius, Lithuania, Institute of Mathematics and Informatics, 2006, 7-11 November. – P. 573-584.
- Melnikov, B. Some competition programming problems as the beginning of artificial intelligence / B.Melnikov, E.Melnikova // Informatics in Education. – v.6, n.2, 2007. – P.385–396.
- Melnikov, B. Billiard Languages and Corresponding Forbidden Languages / B.Melnikov, E.Melnikova // International Conference “Infinity in Logic and Computation”. – Cape Town, South Africa, University of Cape Town, 2007, 3-5 November. – P.21.
- Melnikov, B. Some heuristics for working with searh tree in non-deterministic games / B.Melnikov, E.Melnikova, A.Moseev // 9th International Workshop on Computer Science and Information Technologies (CSIT'2007). – Ufa, 2007.
Публикации, в которых автор принимала участие в качестве переводчика:
- Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию. 3 изд.: Пер. с англ. Б.Ф.Мельникова, Е.А.Мельниковой. – СПб.: БХВ-Петербург, 2009. – 336 с. (Учебная литература для вузов).
[1] Этот алгоритм разрабатывается всеми участниками нашей научной группы. Личный вклад автора связан с кластеризацией подзадач, возникающих в процессе решения некоторой ЗДО с помощью незавершённого МВГ.
[2] Hromkovi J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. - Springer, 2003. См. также [15].
[3] Held M., Karp R.M. The traveling-salesman problem and minimum spanning trees. Operation Research, 18 (1970) 1138–1162.
[4] поскольку ни в одной из «геометрических» постановок не имеет смысла считать что badness превышает диагональ квадрата – причём даже в псевдогеометрическом случае.
