Применение constraint технологии при решении задач комбинаторной оптимизации в условиях фазовых переходов

• Автор: Беляев, Сергей Алексеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Санкт-Петербург
• Количество страниц: 149 с.

Оглавление

Список иллюстраций.

Список таблиц

Список сокращений

Введение

Глава 1. Обзор проблематики и постановка задачи.

Введение

Язык программирования Пролог

Механизм доказательства в Прологе

Задача удовлетворения ограничениям i ii

Представление ограничений

Алгоритмы разрешения ограничений.
Алгоритмы распространения ограничений
Метод ветвей и границ
Открытие середины х годов фазовые переходы в комбинаторных задачах
Постановка задачи исследования.
Преобразование задачи коммивояжера в
Преобразование задачи коммивояжера в .
Приближенные методы решения задачи коммивояжера
Выводы по главе 1
Глава 2. Анализ поведения метода ветвей и границ при появлении фазового
перехода и разработка методов решения в условиях фазового перехода
Раздел 2.1 Особенности метода ветвей и границ при решении задач с
топологическими особенностями класса I
Топологические особенности.
Особенности решения
Методы кластеризации
Анализ топологии.
Гипотеза о природе фазового перехода от топологии
Оценка вероятности появления топологических особенностей.
Выводы по разделу 2.1
Раздел 2.2. Особенности метода ветвей и границ при решении задач с
топологическими особенностями класса II
Топологические особенности класса II
Экспериментальные результаты
Анализ топологии
Анализ работы метода ветвей и границ на задачах топологическими
особенностями класса II.
Возможные модификации.
Геометрическая интерпретация
Анализ сложности и точности решения приближенным алгоритмом.
Выводы по разделу 2.2.
Раздел 2.3. Метод ветвей и границ при решении комбинаторных задачах с
топологическими особенностями
Задача коммивояжера.
Квадратическая задача о назначении
Задача о 01 рюкзаке
Фазовые переходы
Влияние топологических особенностей на время решения методом ветвей и
границ
Выводы по разделу 2.3.
Раздел 2.4. Методы декомпозиции
Введение
Изменение граничного значения и уровня значимости.
Алгоритм с учетом декомпозиции
Иерархическая декомпозиция
Выводы по разделу 2.4.
Раздел 2.5. Метод интеллектуального возврата.
Введение
Использование топологических особенностей исходных данных.
Подход 1
Подход 2
Алгоритм интеллектуального возврата.
Результаты тестирования
Выводы по разделу 2.5
Выводы по главе 2
Глава 3. Разработка прототипа i системы
Раздел 3.1. Введение.
Интеграция методов в Прологподобную систему.
Выводы по разделу 3.1
Раздел 3.2. Разработка прототипа i системы.
Этапы разработки.
Разработка идеологии Пролог подобной системы
Структура данных языка Пролог
Синтаксический и семантический анализ при преобразовании данных
Синтаксический и семантический анализ Выражения.
Алгоритм доказательства цели
Алгоритм доказательства предиката.
Алгоритм возврата.
Выводы по разделу 3.2.
Раздел 3.3. Интеграция методов разрешения i.
Абстрактная Машина Варрена
Использование объектноориентированного подхода.
Интеграция методов решения задачи удовлетворения ограничениям
Выводы по разделу 3.3.
Выводы по главе 3.
Глава 4. Проверка применимости предложенного подхода.
Оценка времени вычисления и точности реализованных методов, сравнение с
приближенными и точными подходами.
Сравнение с существующим программным комплексом.
Задача коммивояжера.
Задача кумулятивного расписания.
Задача о 01 рюкзаке
Выводы по главе 4.
Заключение
Направления дальнейших исследований
Научные положения работы.
Обобщенные результаты но некоторым главам
Список литературы


Одним из основополагающих методов точного решения задач исследования операций является метод ветвей и границ. Однако, в середине х годов был обнаружен эффект фазового перехода, заключающийся в том, что при незначительном изменении исходных данных NP-трудной задачи время ее точного решения методом ветвей и границ может возрастать на порядки. Данный эффект наблюдается как на тестовых примерах, так и в реальных индустриальных задачах. Па настоящий момент не опубликовано методов идентификации фазовых переходов сложности в NP-полных задачах, следовательно, нет возможности определить возможно ли точное решение задачи за приемлемое время или нет. Существующие программные системы, реализующие constraint технологию, не отслеживают факт наличия фазового перехода, что приводит к резкому снижению эффективности constraint системы. Это обстоятельство свидетельствует об актуальности разработки constraint системы, учитывающей возможность появления фазовых переходов в решаемых задачах. В данной работе разрабатывается метод идентификации наличия фазового перехода сложности в некоторых комбинаторных задачах при решении методом ветвей и границ, метод решения в условиях фазовых переходов и механизм интеграции данного подхода в constraint систему. Цель работы. Основной целью работы является создание подхода, позволяющего повысить эффективность работы constraint систем при наличии фазового перехода. Выявление особенностей поведения метода ветвей и границ в зависимости от исходных данных, приводящих к появлению фазового перехода в процедурах решения constraint систем. Разработка алгоритмов идентификации особенностей исходных данных, приводящих к появлению фазового перехода в constraint системах, использующих метод ветвей и границ. Разработка алгоритмов работы процедур решения constraint системы при наличии фазового перехода. Разработка программного прототипа constraint системы, работающего в условиях фазового перехода. Оценка эффективности предлагаемого подхода. Методы исследования включают методы и технологии теории графов, теории кластерного анализа, математической статистики, оптимизации, методы исследования операций, технологии программирования. Выявлены особенности поведения метода ветвей и границ, приводящие к появлению фазового перехода в constraint системах, обусловленные топологией исходных данных. Данный эффект продемонстрирован на задачах коммивояжера, о 0/1 рюкзаке и квадратической задачи о назначении при их решении методом ветвей и границ. Предложен подход к идентификации топологических особенностей исходных данных, приводящих к появлению фазового перехода в процедурах решения constraint систем, использующих метод ветвей и границ. Предложен алгоритм реализации процедур решения constraint систем в условиях фазовых переходов, основывающийся на декомпозиции пространства поиска. Предложен метод интеллектуального возврата в Пролог системах, позволяющий исключить из поиска поддеревья, наименее влияющие на точность решения. Разработан объектно-ориентированный прототип constraint системы, обеспечивающий возможность решения ряда задач в условиях фазового перехода. С использованием разработанного прототипа проведена экспериментальная оценка вычислительной сложности и точности решения задач коммивояжера, о 0/1 рюкзаке и кумулятивного расписания в условиях фазового перехода, которая показала, что время их решения предложенными методами меньше, чем классическим методом ветвей и границ в 3 и более раз. Проведена экспериментальная оценка точности вычислений данной системы и типовых приближенных алгоритмов, которая показала уменьшение относительной погрешности на тестовых примерах в среднем более чем в 2 раза. Выполнено экспериментальное сравнение точности и времени решения при наличии фазовых переходов между разработанной системой и коммерческой constraint системой SICStus Prolog, созданной Swedish Institute of Computer Science версия июля года, на задачах коммивояжера и кумулятивного расписания, показавшая сокращение времени решения до раз. Апробация работы.