Введение к работе
Актуальность темы
Задачи оптимизации - одна из востребованных проблем современной вычислительной и прикладной математики. К настоящему времени разработано значительное количество методов для решения задач дискретной оптимизации. Несмотря на огромный прогресс в интересующей нас области за последние три десятилетия и экспоненциальный рост возможностей вычислительной техники, «проблема размерности» до сих пор существует. К тому же решение практических задач требует поиска новых, более эффективных моделей и алгоритмов поиска как точных, так и приближённых решений. Таким образом, исследования в области алгоритмизации трудно-решаемых задач остаются по-прежнему актуальными, а их результаты имеют большое практическое значение.
Например, исследования в области построения так называемых anytime-алгорипшов' - эвристических алгоритмов реального времени. Так как anytime-алгоритмы основаны на итерационной технике и работают в режиме реального времени, то в любой момент времени можно получить лучшее (на данном шаге) решение, а последовательность таких псевдооптимальных решений в пределе даёт оптимальное решение.
Одним из важнейших направлений здесь является разработка и реализация эвристических алгоритмов, включающих комплекс эвристик. Наиболее известные и надёжные эвристики - алгоритм имитационной нормализации2 и генетический алгоритм. Обе они пытаются имитировать оптимизационные процессы: созданные человеком и природой. А именно, алгоритм имитационной нормализации создан на основе аналогии с термодинамическим процессом, а генетические алгоритмы - с оптимизацией популяции в процессе эволюции.
В данной работе исследуется подход к построению комбинированного алгоритма имитационной нормализации и незавершенного метода ветвей и границ, который даёт гибридный алгоритм, для задач дискретной оп-
' Б.Ф.Мельников. Мультиэвристический подход к задачам дискретной оптимизации // Кибернетика и системный анализ (НАН Украины), 2006, №3. С. 32-42.
2 В английской литературе - «simulated annealing». В русской литературе чаще, к сожалению, применяется неудачный термин «эмуляция отжига». Термин «имитационная нормализация» правильнее с точки зрения физики и понятнее математикам-программистам, он связан с методами имитационного моделирования в статистической физике, основанными на методах Монте-Карло. Подробнее см. примечание переводчика в книге: Ю.Громкович. «Теоретическая информатика...», изд-во БХВ, СПб, 2010; см. также: K.Binder. Monte Carlo methods in statistical physics. Berlin: Springer, 1978.
тимизации - в целях получения более близкого к оптимальному решения за более короткое время.
Для реализации концепции комбинирования часто используются стандартные надёжные технологии, например, метод локального поиска, динамическое программирование и жадные алгоритмы. Задачи, рассмотренные в данной работе, имеют большую размерность, и известно, что получение их оптимального решения возможно не для каждого входа - однако для большинства «типичных» входов вполне реально. Поэтому приемлемые результаты даёт применение метода ветвей и границ с предварительным вычислением, для которого используется генетический алгоритм. Другой способ комбинирования - соединение концепции рандомизации и аппроксимации. При этом имитационную нормализацию можно рассматривать как рандомизированный локальный поиск для метода ветвей и границ. Комбинирование двух концепций (рандомизации и предварительного вычисления) соединения алгоритмов даёт приемлемую эвристику.
Цель работы
Целью диссертационного исследования является разработка и описание гибридных алгоритмов решения задач дискретной оптимизации (ЗДО) -с вычислительной эффективностью немного выше, чем более известные (классические) эвристические алгоритмы.
Объект исследования
Объектом исследования являются эвристические алгоритмы дискретной оптимизации и их комбинирование. Полученные смешанные алгоритмы применимы для решения многих задач дискретной оптимизации во многих сложных областях. В их числе:
системы линейных алгебраических уравнений (СЛАУ);
транспортная задача (в частности - псевдогеометрическая версия задачи коммивояжёра, ЗКВ);
вершинная минимизация недетерминированных конечных автоматов (НКА).
Предмет исследования
Предметом исследования являются несколько эвристик и комбинирование алгоритмов с применением этих эвристик. Первая эвристика - расширение области решений незавершённого метода ветвей и границ. Вторая -ограничение выбора для формирования популяции и операции мутации генетического алгоритма с целью получения начального решения для метода ветвей и границ. Третья - применение имитационной нормализации в качестве
рандомизированного локального поиска в методе ветвей и границ.
Методы исследования
В качестве аппарата исследований применяются математические методы разработки эвристических алгоритмов и эвристические методы анализа их эффективности.
Результаты исследования
Результатами диссертационного исследования являются новые вычислительные методы и алгоритмы решения задач дискретной оптимизации.
Научная новизна
Новизна мультиэвристическогр метода решения задач дискретной оптимизации состоит в применении эвристик для разработки мультиме-тодных алгоритмов. Разработанные алгоритмы является новыми.
Предложены, реализованы и исследованы несколько алгоритмов дискретной оптимизации, проведено их сравнение с классическими методами.
Разработан и опробован комбинированный метод, алгоритм имитационной нормализации и генетический алгоритм дискретной оптимизации.
Предложена схема параллелизации разработанного алгоритма, позволяющая добиться ускорения на некоторых задачах.
Достоверность результатов
Достоверность и научная обоснованность результатов подтверждается результатами вычислительного эксперимента с использованием современных математических методов при разработке и обосновании корректности алгоритмов, использовании современных методик тестирования и проверки вычислительных программ, сопоставлением полученных результатов работы программ, работающих с применением предложенных эвристик и без них.
Теоретическая и практическая значимость исследования
Подходы и эвристики, разработанные в работе, позволяют повысить эффективность работы алгоритмов для решения задач дискретной оптимизации. Разработанные алгоритмы могут быть применены для решения практически любой оптимизационной задачи, возникающей в физике, биологии, химии, экономике, промышленности, приборостроении, транспорте и в других отраслях. Программные реализации разработанных алгоритмов применялись автором для вершинной минимизации недетерминированных конечных автоматов (НКА), для решения транспортных задач (ЗКВ) и систем линейных алгебраических уравнений (СЛАУ) с разрежёнными матрицами большой размерности. К таким СЛАУ приводит решение ряда задач математической физики (задачи гидрогазодинамики, расчета электромаг-
нитных полей, уравнения Максвелла, Навье-Стокса3, атака криптосистем на основе открытого ключа4 и др.) методами конечных элементов (FEM) и конечных объемов (FVM) - особенно на неструктурированных сетках. Основные задачи исследования:
разработка и реализация эвристик для расширения пространства поиска в методе ветвей и границ;
модификация модели вычислений, представляющей собой незавершённый метод ветвей и границ;
разработка и реализация алгоритмов для решения задач дискретной оптимизации, скомбинированных с имитационной нормализацией;
разработка и применение подхода для создания соответствующих компьютерных программ;
подход к сравнению разработанных алгоритмов с классическими алгоритмами.
Основные положения, выносимые на защиту
-
Разработка и компьютерная реализация алгоритмов с применением всех разработанных автором эвристик для решения нескольких задач дискретной оптимизации (СЛАУ, транспортная задача (псевдогеометрический вариант ЗКВ), вершинная минимизация НКА).
-
Разработка модели вычислений, состоящей в модификации муль-тиэвристического подхода решения задач дискретной оптимизации. Эта модель связана с комбинированием работающего в ней незавершённого метода ветвей и границ и имитационной нормализации.
-
Разработка алгоритмов гибридного применения имитационной нормализации и обоснование возможностей их практического применения для решения задач дискретной оптимизации в нескольких предметных областях.
-
Результаты сравнения эффективности эвристических алгоритмов на основе разработанной автором эвристической модели сравнения. Исследование эффективности мультиэвристического подхода к решению задач дискретной оптимизации, модифицированного на основе разработанного комбинированного алгоритма.
Апробация работы
Результаты диссертационной работы докладывались и обсуждались на:
М.Ю.Баландин, Э.П.Шурина. Некоторые оценки эффективности параллельных алгоритмов решения СЛАУ на подпространствах Крылова. - Вычислительные технологии. Том 3 №1 1998
С.В.Беззатеев. Методы защиты информации от несанкционированного доступа Вопросы передачи и защиты информации: Сборник статей / Под ред. проф. Е.А. Крука. - СПб ГУАП
XI Международной научно-технической конференции «Проблемы информатики в образовании, управлении, экономике и технике» (Пенза, 2009);
VI Студенческой международной научно-практической конференции «Интеллектуальный потенциал XXI века: ступени познания» (Новосибирск, 2011);
V Международной научно-технической конференции молодых специалистов, аспирантов и студентов «Математическое и компьютерное моделирование естественнонаучных и социальных проблем» (Пенза, 2011);
XI Международной научно-практической конференции «Наука и современность - 2011» (Новосибирск, 2011);
II Международной научно-практической конференции «Современное состояние естественных и технических наук» (Москва, 2011);
I Международной научно-практической конференции «Теория и практика в физико-математических науках» (Москва, 2011).
Международной научно-практической конференции «Молодежь и наука: модернизация и инновационное развитие страны» (Пенза, 2011).
Публикации
По теме диссертации опубликовано 11 работ, из них 2 - в изданиях, рекомендованных ВАК.
Личный вклад автора
Постановка задач осуществлялась научным руководителем. Описываемые в диссертации математические модели вычислений, разработанные алгоритмы их решения, компьютерные реализации алгоритмов и исследование результатов работы программ выполнены автором самостоятельно. Незавершённый метод ветвей и границ и идея комбинирования с применением имитационной нормализации в соавторстве с научным руководителем.
Структура и объём диссертации
Общий объём диссертации - 124 страницы. Диссертация состоит из введения, четырёх глав, заключения, списка используемой литературы, из 97 наименований и одного приложения.
