АМИРГАЛИЕВА ЖАЗИРА ЕДИЛХАНОВНА Метаэвристические алгоритмы на основе поиска с чередующимися окрестностями для решения задач квадратичного программирования

Короткий опис

Казахский национальный университет им. аль-Фараби
На правах рукописи
АМИРГАЛИЕВА ЖАЗИРА ЕДИЛХАНОВНА
Метаэвристические алгоритмы на основе поиска с чередующимися окрестностями для решения задач квадратичного программирования 6D070500 - Математическое и компьютерное моделирование
Диссертация на соискание степени доктора философии (PhD)
Отечественный научный консультант доктор физико-математических наук, профессор Арсланов М.З.
Зарубежный научный консультант доктор философии (Ph.D), профессор Младенович Н.
Республика Казахстан Алматы, 2017

ВВЕДЕНИЕ....................................................................................................................... 3
1 МАТЕМАТИЧЕСКИЕ ОСНОВЫ ОПТИМИЗАЦИОННЫХ ЗАДАЧ................. 10
1.1 Введение в оптимизационные задачи................................................................... 10
1.2 Классы сложности................................................................................................ 18
1.3 Точные и эвристические методы оптимизации.................................................... 20
1.4 Квадратичное программирование........................................................................ 25
1.5 Метаэвристические методы.................................................................................. 30
1.6 Локальный поиск с чередующимися окрестностями............................................ 35
Выводы по 1 разделу........................................................................................................ 46
2 ЗАДАЧА НЕПРЕРЫВНОГО БИЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ..47
2.1 Билинейное программирование............................................................................ 47
2.2 Постановка задачи объединения.......................................................................... 48
2.3 Формулировки математической модели............................................................... 49
2.4 Алгоритмы решения............................................................................................. 52
2.5 Исходное решение для непрерывного билинейного программирования ....56
Выводы по 2 разделу........................................................................................................ 69
3 ЗАДАЧА МАКСИМАЛЬНОЙ МИНИМАЛЬНОЙ СУММЫ ДИСПЕРСИИ .70
3.1 Задача дисперсии (разнородности)....................................................................... 70
3.2 Поиск с чередующимися формулировками для Max-min-sum ДЗ........................ 79
3.3 Результаты расчетов............................................................................................. 91
Выводы по 3 разделу...................................................................................................... 105
4 ЗАДАЧА ДВУДОЛЬНОГО КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ
БЕЗ ОГРАНИЧЕНИЙ..................................................................................................... 106
4.1 Математическая формулировка задачи.............................................................. 106
4.2 Методы решения задачи BQP............................................................................. 108
4.3 Поиск с чередующимися окрестностями для решения BQP............................... 110
4.4 Вычислительные эксперименты......................................................................... 119
Выводы по 4 разделу...................................................................................................... 122
ЗАКЛЮЧЕНИЕ.............................................................................................................. 123
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ........................................................ 125
ПРИЛОЖЕНИЕ А.......................................................................................................... 136
ПРИЛОЖЕНИЕ Б.......................................................................................................... 140

ПРИЛОЖЕНИЕ В.......................................................................................................... 149

Список літератури

ЗАКЛЮЧЕНИЕ
Исследование данной диссертационной работы посвящено разработке алгоритмов и компьютерных программ на основе метода локального поиска с чередующимися окрестностями для решения непрерывных билинейных программ на примере задачи объединения, а также следующих задач комбинаторной оптимизации: 1) Задача о максимальной минимальной сумме дисперсии; 2) Задача двудольного 0-1 квадратичного программирования без ограничений. Актуальность проблемы создания эффективных эвристических и метаэвристических алгоритмов для решения задач квадратичного программирования обусловлена высокой сложностью решаемых задач, а также обширной областью практического применения.
Рассматриваемые задачи принадлежат к классу NP-трудных задач, то есть для их точного решения не существует алгоритма полиномиальной сложности. В связи с этим использование точных алгоритмов для решения подобных задач часто оказывается нецелесообразным и невозможным по причине больших затрат времени. Поэтому большое значение уделяется разработке и исследованию эвристических методов оптимизации, которые являются одним из перспективных направлений с успехом используемых для решения многих задач как дискретной, так и непрерывной оптимизации.
В диссертационной работе были представлены теоретические и математические основы оптимизационных задач. Приводится их классификация, общая формулировка, а также основные понятия точных и эвристических методов оптимизации. Описывается математическая формулировка задач квадратичного программирования, условия оптимальности и способы их решения. Также рассматриваются общие алгоритмы локального поиска с чередующимися окрестностями.
Были рассмотрены математические модели стандартной задачи объединения и основные алгоритмические методы для ее решения. На примере нескольких задач билинейного программирования были продемонстрированы возможности выполнения процедур поиска с чередующимися окрестностями. Для нахождения допустимого начального решения был использован программный комплекс GLOB, предназначенный для минимизации непрерывной функции c граничными ограниченениями. Используя классический метод штрафа, в качестве метаэвристики - поиск с чередующимися окрестностями и локального минимизатора - метод Нельдера-Мида были получены начальные решения, которые затем были использованы в качестве входных параметров в программе VNS-ALT для решения выбранных задач билинейного программирования.
Также в данной работе мы предлагаем расширенные алгоритмы Variable Formulation Search (VFS) для решения NP-трудной задачи Max-мин-суммы дисперсии (max-min-sum DP). VFS и расширенная VFS имеют те же самые шаги в алгоритме. Однако вместо использования различных формулировок той же проблемы, как в VFS, в расширенной VFS мы допускаем использование формулировок различных, хотя и схожих, задач оптимизации. Здесь мы используем формулировки только двух задач. Сравнение между основной VNS и VFS показал необходимость использования такого механизма, исследуя пространство решений задачи, в то время как сравнение двух алгоритмов VFS, которые используют различные локальные процедуры поиска, мы обнаружили, что применение вспомогательной целевой функции перед первичным в процедуре локального поиска представляет значичельные преимущества. Результаты расчета по 140 тестовым экземплярам показывают, что предложенный алгоритмы превосходят алгоритм, использованный в литературе, основанный на табу поиске. В частности, протестированным эвристикам удалось улучшить 99 из 140 наиболее известных предыдущих результатов расходуя меньше процессорного времени. Мы также провели тестирование на 255 экземплярах MDPLIB, сравнивая предлагаемые алгоритмы с процедурами GRASP, где средний процент улучшения был также достигнут.
Дальнейшая работа, которая будет следовать за весьма замечательными результатами, полученными здесь, может рассмотреть возможность решения еще больших задач теста, используя декомпозицию для дальнейшего ускорения процесса решения. Показывается, что альтернативная формулировка для задачи дисперсии max-min-sum может быть представлена соответствующей дисперсионной моделью дисперсии максимальной суммы, используемой в рамках VFS. Очевидно, что интересный вопрос для будущей работы - насколько эффективна такая формулировка для решения других задач max-min или min-max с помощью VFS?
Последний раздел посвящен задаче двудольного 0-1 квадратичного программирования без ограничений, для решения которой была предложена метаэвристика на основе поиска с чередующимися окрестностями. Проведен сравнительный анализ результатов, полученных разработанным алгоритмом и методами условного марковского цепного поиска и поиска табу из литературы, которые в текущий момент являются наилучшими подходами для решения задач BQP. С помощью разработанного алгоритма удалось уменьшить среднее процентное отклонение от наилучших известных значений. Будущая работа может включать в себя использование других видов локального поиска и инициализации процедур, а также установку оптимальных параметров для тестирования средних и крупных экземпляров множества примеров из литературы.
Проведение численных экспериментов на тестовых наборах данных и сравнительного анализа результатов, полученных разработанными методами поиска с чередующимися окрестностями и существующими эффективными метаэвристиками выявило успешность использования разработанных алгоритмов решения.