Содержание к диссертации
Список иллюстраций 6
Список таблиц 8
Список сокращений 9
Введение 10
Глава 1. Обзор проблематики и постановка задачи 14
Введение 14
Язык программирования Пролог 15
Механизм доказательства в Прологе 16
Задача удовлетворения ограничениям (Constraint Satisfaction Problem) 17
Представление ограничений 21
Алгоритмы разрешения ограничений 21
Алгоритмы распространения ограничений 24
Метод ветвей и границ 25
Открытие середины 90х годов: фазовые переходы в комбинаторных задачах 27
Постановка задачи исследования 30
Преобразование задачи коммивояжера в BCSP 30
Преобразование задачи коммивояжера в CSP 31
Приближенные методы решения задачи коммивояжера 32
Выводы по главе 1 38
Глава 2. Анализ поведения метода ветвей и границ при появлении фазового
перехода и разработка методов решения в условиях фазового перехода 39
Раздел 2.1 Особенности метода ветвей и границ при решении задач с
топологическими особенностями класса I 39
Топологические особенности 39
Особенности решения 40
Методы кластеризации 41
Анализ топологии 44
Гипотеза о природе фазового перехода от топологии 45
Оценка вероятности появления топологических особенностей 49
Выводы по разделу 2.1 52
Раздел 2.2. Особенности метода ветвей и границ при решении задач с
топологическими особенностями класса II 53
Топологические особенности класса II 53
Экспериментальные результаты 54
Анализ топологии 55
Анализ работы метода ветвей и границ на задачах топологическими
особенностями класса II 56
Возможные модификации 57
Геометрическая интерпретация 59
Анализ сложности и точности решения приближенным алгоритмом 62
Выводы по разделу 2.2 62
Раздел 2.3. Метод ветвей и границ при решении комбинаторных задачах с
топологическими особенностями 63
Задача коммивояжера 63
Квадратическая задача о назначении 63
Задача о 0/1 рюкзаке 65
Фазовые переходы 66
Влияние топологических особенностей на время решения методом ветвей и
границ 66
Выводы по разделу 2.3 72
Раздел 2.4. Методы декомпозиции 73
Введение 73
Изменение граничного значения и уровня значимости 74
Алгоритм с учетом декомпозиции 75
«Иерархическая декомпозиция» 77
Выводы по разделу 2.4 78
Раздел 2.5. Метод интеллектуального возврата 80
Введение 80
Использование топологических особенностей исходных данных 80
Подход 1 81
Подход 2 82
Алгоритм интеллектуального возврата 84
Результаты тестирования 85
Выводы по разделу 2.5 86
Выводы по главе 2 88
Глава 3. Разработка прототипа constraint системы 89
Раздел 3.1. Введение 89
Интеграция методов в Пролог-подобную систему 90
Выводы по разделу 3.1 91
Раздел 3.2. Разработка прототипа constraint системы 92
Этапы разработки 92
Разработка идеологии Пролог -подобной системы 92
Структура данных языка Пролог 93
Синтаксический и семантический анализ при преобразовании данных 100
Синтаксический и семантический анализ «Выражения» 101
Алгоритм доказательства цели 103
Алгоритм доказательства предиката 105
Алгоритм возврата 107
Выводы по разделу 3.2 109
Раздел 3.3. Интеграция методов разрешения constraint ПО
Абстрактная Машина Варрена 110
Использование объектно-ориентированного подхода 110
Интеграция методов решения задачи удовлетворения ограничениям 111
Выводы по разделу 3.3 117
Выводы по главе 3 117
Глава 4. Проверка применимости предложенного подхода 118
Оценка времени вычисления и точности реализованных методов, сравнение с
приближенными и точными подходами 118
Сравнение с существующим программным комплексом 120
Задача коммивояжера 120
Задача кумулятивного расписания 121
Задача о 0/1 рюкзаке 128
Выводы по главе 4 130
Заключение 131
Направления дальнейших исследований 131
Научные положения работы 133
Обобщенные результаты по некоторым главам 134
Список литературы 136
Приложение 1. Статистические методы 146
Поиск начального кластера 146
Критерий согласия Колмогорова-Смирнова 146
Статистический критерий Стьюдента 147
Список иллюстраций
Рис. 1. Частота использования ребер длиной от 0 до 1 методом ветвей и границ при топологии класса I на матрице, нормированной на [0, 1]
Рис. 1.1. Структура constraint системы
Рис. 2.1 «Строгая» кластеризация
Рис. 2.2. Частота исследования ребер длиной от 0 до 1 при решения задачи коммивояжера с топологическими особенностями методом ветвей и границ
Рис. 2.3. Частота исследования ребер длиной от 0 до 1 при решения задачи коммивояжера без топологических особенностей методом ветвей и границ
Рис. 2.4 Поиск решения методом ветвей и границ в матрице с топологическими особенностями
Рис. 2.5. Оценка среднего количество кластеров из диапазонов [1, 5], [6, 10], [11, 15] и [16, 20] на матрицах от 50x50 до 250x250
Рис. 2.6. Вероятность появления кластеров "от 11x11 до 15x15" в матрицах данной размерности
Рис. 2.7. Зависимость времени вычисления от количества кластеров на матрице 30x30
Рис. 2.8. Зависимость времени вычисления от количества кластеров на матрице 50x50
11.Рис. 2.9. Пример матрицы с топологическими особенностями класса II
Рис. 2.10. Пример редуцированной матрицы с топологическими особенностями класса II
Рис. 2.11. Пример матрицы типа «Класс II - верхняя граница»
14. Рис. 2.12. Пример матрицы типа «Класс II - нижняя граница»
15.Рис. 2.13. Геометрическая интерпретация топологии класса II
Рис. 2.14. Пример «накладывающихся» кластеров
Рис. 2.15. Решение QAP для нескольких размерностей
Рис. 2. 16. Решение QAP для размерности 11 и кластеров размерностью от 1 до 10
Рис. 2.17. Исследование количества возвратов при проведении вычислений с 0/1 рюкзаком из 48 элементов и С = Zw / 3
Рис 2.18. использование алгоритма «Иерархической декомпозиции»
Рис. 2.19 Соединение, когда вход и выход из кластера - соседние вершины по ходу оптимального решения
Рис. 2.20. Соединение в общем случае
23.Рис. 2.21. Выбор элементов для нового кластера 24.Рис. 3.1. Иерархия наследования элементов Пролога
Рис. 3.2. Постановка CSP в языке SICStus Пролог
Рис. 3.3. Постановка CSP с функцией минимизации в SICStus Пролог
Рис. 3.4. Иерархическая модель вычислений
Рис. 3.5. Диаграмма деятельности: доказательство в языке Пролог 29.Рис. 3.6. Диаграмма деятельности: доказательство
Рис. 3.7. Диаграмма деятельности: вычисление математического выражения
Рис. 3.8. Диаграмма деятельности: доказательство встроенного функтора solve
Рис. 4.1. Время вычисления при возрастании интервала для ресурсов. Ограничение по ресурсам =15
33.Рис. 4.2. Время вычисления при возрастании интервала для ресурсов. Ограничение по ресурсам =15
Рис. 4.3. Изменение сложности решения при изменении исходных данных на двух разных В&В
Рис. 4.4. Зависимость времени решения от размера кластеров при решении методом Pisinger В&В
36.Рис. 4.5. Зависимость времени решения от размера кластеров при решении методом Mallba В&В
Список таблиц
1. Таблица 1. Среднее количество ребер, используемых при поиске решения
методом ветвей и границ на матрицах с топологическими особенностями по (3),
(4)
Таблица 2. Время и относительная погрешность решения при кластеризации класса I.
Таблица 2.1. Среднее число ребер, исследуемых методом ветвей и границ
Таблица 2.2. Оценка количества кластеров, выявленных в некоторых асимметрических матрицах из TSPLIB
Таблица 2.3 Среднее количество ребер, используемых методом ветвей и границ при решении задач с топологическими особенностями класса II
Таблица 2.4. Среднее количество ребер, используемых при поиске решения при топологии «класса II - симметрическая»
Таблица 2.5. Оценка точности вычислений алгоритма вставки на матрицах с кластеризацией класса II. Кластеры 4x4.
Таблица 2.6. Точность и время решения методом декомпозиции матриц со строгой кластеризацией, кластеры 4x4.
Таблица 2.7. Результаты тестирования алгоритма интеллектуального возврата.
Таблица 4.1. Погрешность алгоритма интеллектуального возврата при строгой кластеризации класса II
11. Таблица 4.2. Оценка точности решения методами интеллектуального возврата,
декомпозиции и вставки при особенностях по формуле (2.2) и кластерах
размером 5x5.
12.Таблица 4.3. Оценка количества кластеров, выявленных в некоторых
асимметрических матрицах TSBLIB и точность вычислений алгоритмом
интеллектуального возврата. 13.Таблица 4.4. Время решения TSP в зависимости от наличия или отсутствия
строгих кластеров в SUCStus Прологе и BBmod 14. Таблица 4.5. Сравнение времени решения задачи о 0/1 рюкзаке методами В&В
при размерности задачи 40 и различных характеристиках исходных данных
Список сокращений
Введение к работе
Актуальность работы. Бурное развитие constraint технологии, объединяющей в себе методы логического программирования и теорию исследования операций, обусловило вторую волну популярности языка Пролог, использующего подход «ограничить и сгенерировать» как противопоставление подходу «сгенерировать и проверить». Применение данной технологии позволяет при корректной формальной постановке задачи получить решение, не акцентируя внимание на используемых методах.
В настоящее время constraint системы используются для решения многих практических задач, в том числе в областях самолетостроения, энергетики, медицины, административных систем, химической промышленности и других. При этом эффективность данных систем эквивалентна специализированным программным комплексам.
Одним из основополагающих методов точного решения задач исследования операций является метод ветвей и границ. Однако, в середине 90х годов был обнаружен эффект фазового перехода, заключающийся в том, что при незначительном изменении исходных данных NP-трудной задачи время ее точного решения методом ветвей и границ может возрастать на порядки. Данный эффект наблюдается как на тестовых примерах, так и в реальных индустриальных задачах.
На настоящий момент не опубликовано методов идентификации фазовых переходов сложности в NP-полных задачах, следовательно, нет возможности определить возможно ли точное решение задачи за приемлемое время или нет.
Существующие программные системы, реализующие constraint технологию, не отслеживают факт наличия фазового перехода, что приводит к резкому снижению эффективности constraint системы. Это обстоятельство свидетельствует об актуальности разработки constraint системы, учитывающей возможность появления фазовых переходов в решаемых задачах.
В данной работе разрабатывается метод идентификации наличия фазового перехода сложности в некоторых комбинаторных задачах при решении методом ветвей и границ, метод решения в условиях фазовых переходов и механизм интеграции данного подхода в constraint систему.
Цель работы. Основной целью работы является создание подхода, позволяющего повысить эффективность работы constraint систем при наличии фазового перехода.
Основные задачи исследования:
Выявление особенностей поведения метода ветвей и границ в зависимости от исходных данных, приводящих к появлению фазового перехода в процедурах решения constraint систем.
Разработка алгоритмов идентификации особенностей исходных данных, приводящих к появлению фазового перехода в constraint системах, использующих метод ветвей и границ.
Разработка алгоритмов работы процедур решения constraint системы при наличии фазового перехода.
Разработка программного прототипа constraint системы, работающего в условиях фазового перехода.
Оценка эффективности предлагаемого подхода.
Методы исследования включают методы и технологии теории графов, теории кластерного анализа, математической статистики, оптимизации, методы исследования операций, технологии программирования.
Научная новизна заключается в том, что
Выявлены особенности поведения метода ветвей и границ, приводящие к появлению фазового перехода в constraint системах, обусловленные топологией исходных данных. Данный эффект продемонстрирован на задачах коммивояжера, о 0/1 рюкзаке и квадратической задачи о назначении при их решении методом ветвей и границ.
Предложен подход к идентификации топологических особенностей исходных данных, приводящих к появлению фазового перехода в процедурах решения constraint систем, использующих метод ветвей и границ. На основании предложенного подхода разработаны алгоритмы идентификации топологических особенностей, приводящих к появлению фазового перехода в
процедурах решения constraint систем, использующих метод ветвей и границ для решения задач коммивояжера, о 0/1 рюкзаке и квадратической задачи о назначении.
Предложен алгоритм реализации процедур решения constraint систем в условиях фазовых переходов, основывающийся на декомпозиции пространства поиска.
Предложен метод интеллектуального возврата в Пролог системах, позволяющий исключить из поиска поддеревья, наименее влияющие на точность решения.
Практическая ценность и значимость результатов диссертационной работы заключается в том, что
Разработан объектно-ориентированный прототип constraint системы, обеспечивающий возможность решения ряда задач в условиях фазового перехода.
С использованием разработанного прототипа проведена экспериментальная оценка вычислительной сложности и точности решения задач коммивояжера, о 0/1 рюкзаке и кумулятивного расписания в условиях фазового перехода, которая показала, что время их решения предложенными методами меньше, чем классическим методом ветвей и границ в 3 и более раз.
Проведена экспериментальная оценка точности вычислений данной системы и типовых приближенных алгоритмов, которая показала уменьшение относительной погрешности на тестовых примерах в среднем более чем в 2 раза.
Выполнено экспериментальное сравнение точности и времени решения при наличии фазовых переходов между разработанной системой и коммерческой constraint системой SICStus Prolog, созданной Swedish Institute of Computer Science версия июля 2001 года, на задачах коммивояжера и кумулятивного расписания, показавшая сокращение времени решения до 10 раз.
Апробация работы. Основные положения работы докладывались на следующих конференциях: вторая всероссийская научно-техническая конференция
«Теоретические и прикладные вопросы современных информационных технологий - 2001», Улан-Удэ, 2001; вторая международная научно-практическая дистанционная конференция «Компьютерные технологии в науке, производстве, социальных и экономических процессах», 2001; международная конференция «Современные технологии обучения», Санкт-Петербург, 2002.
Предложенные методы использовались в НИОКР «Разработка интеллектуальных систем управления и систем транспортной логистики Санкт-Петербурга» (№5905/САУ-225), выполненной для правительства Санкт-Петербурга в 1998 году.
Разработанный подход использовался в образовательном проекте «Учебно-научный центр университета информатики, электроники и управления» регистрационный номер АО 1500150 ФЦП «Интеграция»: «Интегрированная система подготовки кадров и фундаментальных научных исследований в области информатики» (Проект регистрационный номер 142, книга 2) в 2001 году.
Материалы использовались при чтении курсов «Логическое программирование» и «Логическое и функциональное программирование» для специальностей 0102 и 2204, а так же в курсовом проектировании курса «Логическое программирование» для специальности 0102.
