Применение имитационной нормализации в гибридных алгоритмах

Задачи оптимизации — одна из востребованных проблем современной вычислительной и прикладной математики. Решение подобных проблем требуется во многих задачах из различных отраслей науки и техники. Ещё Леонард Эйлер (1707−1783), один из величайших математиков, говорил: «В мире не происходит ничего, в чём бы не был виден смысл какого-нибудь максимума или минимума» [47]. При этом особый интерес представляет нахождение так называемых глобальных экстремумов (оптимумов) функции — т. е. таких оптиму-мов, которые являются наилучшими на всей рассматриваемой области определения целевой функции, а не только в сравнении с близлежащими точками из некоторой своей окрестности. При этом многие задачи, возникающие в различных сферах человеческой деятельности, могут быть сведены к задаче поиска глобального оптимума. Неудивительно, что в настоящее время оптимизация, особенно глобальная оптимизация, — актуальное и интенсивно развивающееся направление вычислительной математики.

Большинство задач дискретной оптимизации являются трудно-решаемыми [15], т. е. на сегодняшний день нет алгоритмов, решающих такие задачи за время, ограниченное некоторым полиномом относительно размера входных данныхи, возможно, таких алгоритмов не существует вообще. Трудными также считаются задачи, для которых полиномиальная разрешимость доказана — однако (пока) неизвестны полиномиальные алгоритмы небольших степеней.

Для огромного количества практических задач, возникающих в самых разных сферах практической деятельности, в качестве моделей выступают оптимизационные задачи. Основной проблемой решения оптимизационных задач является размерность. Для эффективного решения задач реальных размерностей применение точных алгоритмов на практике невозможно — т.к. вычисление целевой функции на каждом шаге итерации требует слишком больших затрат вычислительных ресурсов (машинного времени и, возможно, памяти).

Для задач дискретной оптимизации характерны такие отличительные признаки, как факториальный (а иногда — более чем фактори-альный) рост вычислительной сложности и допустимость приближённого решения. Представителями указанного класса задач являются НР-полные задачи оптимизации. В 1984 году А. А. Гагановым было показано, что даже для полиномиальной целевой функции /(х) задача глобальной оптимизации является КР-трудной [63] - что фактически равносильно признанию того, что для её решения требуются не менее чем экспоненциальные (в зависимости от размерности п) трудозатраты. Например, полученная недавно теорема Кирфотта-Крейновича, утверждающая, что за пределами класса выпуклых целевых функций решение задачи глобальной оптимизации является МР-труднымодин из важнейших результатов в этой области.

К настоящему времени разработано значительное количество методов для решения задач дискретной оптимизации. Несмотря на экспоненциальный рост возможностей вычислительной техники и огромный прогресс в интересующей нас области до сих пор существует проблема размерности. К тому же решение практических задач требует поиска новых, более эффективных моделей и алгоритмов поиска точных и приближённых решений. Таким образом, исследования в области алгоритмизации труднорешаемых задач остаются по-прежнему актуальными, а их результаты имеют большое практическое значение.

Примером исследования в области алгоритмизации труднорешаемых задач являются подходы к построению так называемых апуйте-алгоритмов [35] - эвристических алгоритмов реального времени. Так как апуйте-алгоритмы обычно основаны на итерационной технике и работают в режиме реального времени, то в любой момент времени можно получить лучшее (на данном шаге) решение, причём последовательность таких псевдо-оптималъных решений в пределе обычно (в случае хорошо разработанных алгоритмов) даёт оптимальное решение.

Итак, одним из важнейших направлений здесь является разработка и реализация эвристических алгоритмов, включающих целый комплекс эвристик. По мнению автора, одними из наиболее известных и надёжных эвристик являются варианты алгоритма имитационной нормализации1 и генетических алгоритмов. Создатели вариантов обеих этих эвристик пытаются имитировать оптимизационные процессы: созданные человеком и созданные природой. А именно, алгоритм имитационной нормализации создан на основе аналогии с термодинамическим процессом, а генетические алгоритмы — с оптимизацией популяции в процессе эволюции.

В данной работе исследуется подход к построению комбинированного алгоритма имитационной нормализации и незавершённого метода ветвей и границ для задач дискретной оптимизации в целях получения более близкого к оптимальному решения за более короткое время.

Для реализации концепции комбинирования эвристик часто ис.

1 В английской литературе — «simulated annealing». В русской чаще, к сожалению, применяется неудачный термин «эмуляция отжига». Термин «имитационная нормализация» правильнее с точки зрения физики и понятнее математикам-программистам. Подробнее см. примечание переводчика в книге: Громкович Ю. Теоретическая информатика.

Введение

в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию. Пер. с нем. / Под ред. Б. Ф. Мельникова. — 3-е изд. -СПб.: БХВ-Петербург, 2010. — 336 с. пользуются стандартные надёжные технологии — например, метод локального поиска, динамическое программирование и жадные алгоритмы. Задачи, рассмотренные в данной работе, имеют большую размерность, и при этом известно, что получение их оптимального решения возможно не для каждого входа, хотя для большинства типичных входов вполне реально. Поэтому достаточно приемлемые результаты даст применение метода ветвей и границ с предварительным вычислением, для которого используется генетический алгоритм. А другой способ комбинирования — соединение концепции рандомизации и аппроксимации. Имитационную нормализацию можно рассматривать как рандомизированный локальный поиск для метода ветвей и границ. Комбинирование двух концепций (рандомизации и предварительного вычисления) соединения алгоритмов даёт очень мощную эвристику.

Цель работы.

Целью диссертационного исследования является разработка и описание гибридных алгоритмов решения задач дискретной оптимизации (ЗДО) — с вычислительной эффективностью немного выше, чем более известные (классические) эвристические алгоритмы.

Объект исследования.

Объектом исследования являются эвристические алгоритмы дискретной оптимизации и их комбинирование. Полученные смешанные алгоритмы применимы для решения многих задач дискретной оптимизации во многих сложных областях. В их числе:

• системы линейных алгебраических уравнений (СЛАУ);

• транспортная задача (в частных случаях мы рассматриваем её сведёние к псевдогеометрической версии задачи коммивояжёра, ЗКВ);

• вершинная минимизация недетерминированных конечных автоматов (НКА).

Предмет исследования.

Предметом исследования являются несколько эвристик и комбинирование алгоритмов с применением этих эвристик. Первая эвристика — расширение области решений незавершённого метода ветвей и границ. Вторая — ограничение выбора для формирования популяции и операции мутации генетического алгоритма с целью получения начального решения для метода ветвей и границ. Третья — применение имитационной нормализации в качестве рандомизированного локального поиска в методе ветвей и границ.

Методы исследования.

В качестве аппарата исследований применяются математические методы разработки эвристических алгоритмов и эвристические методы анализа их эффективности.

Результаты исследования.

Результатами диссертационного исследования являются новые вычислительные методы и алгоритмы решения задач дискретной оптимизации.

Научная новизна.

Новизна мультиэвристического метода решения задач дискретной оптимизации состоит в применении эвристик для разработки мультиметодных алгоритмов. Разработанные алгоритмы является новыми.

Предложены, реализованы и исследованы несколько алгоритмов дискретной оптимизации, проведено их сравнение с классическими методами.

Разработан и опробован комбинированный метод, алгоритм имитационной нормализации и генетический алгоритм дискретной оптимизации.

Предложена схема параллелизации разработанного алгоритма, позволяющая добиться ускорения на некоторых задачах.

Достоверность результатов.

Достоверность и научная обоснованность результатов подтверждается результатами вычислительного эксперимента с использованием современных математических методов при разработке и обосновании корректности алгоритмов, использовании современных методик тестирования и проверки вычислительных программ, сопоставлением полученных результатов работы программ, работающих с применением предложенных эвристик и без них.

Теоретическая и практическая значимость исследования.

Подходы и эвристики, разработанные в работе, позволяют повысить эффективность работы алгоритмов для решения задач дискретной оптимизации. Разработанные алгоритмы могут быть применены для решения практически любой оптимизационной задачи, возникающей в физике, биологии, химии, экономике, промышленности, приборостроении, транспорте и в других отраслях. Программные реализации разработанных алгоритмов применялись автором для вершинной минимизации недетерминированных конечных автоматов (НКА), для решения транспортных задач (а также ЗКВ) и систем линейных алгебраических уравнений (СЛАУ) с разрежёнными матрицами большой размерности. К таким СЛАУ приводит решение ряда задач математической физики (задачи гидрогазодинамики, расчета электромагнитных полей, уравнения Максвелла, Навье-Стокса [2], атака криптосистем на основе открытого ключа [3] и др.) методами конечных элементов (FEM) и конечных объёмов (FVM) — особенно на неструктурированных сетках.

Основные задачи исследования:

• разработка и реализация эвристик для расширения пространства поиска в методе ветвей и границ;

• модификация модели вычислений, представляющей собой незавершённый метод ветвей и границ;

• разработка и реализация алгоритмов для решения задач дискретной оптимизации, скомбинированных с имитационной нормализацией;

• разработка и применение подхода для создания соответствующих компьютерных программ;

• подход к сравнению разработанных алгоритмов с классическими алгоритмами.

Основные положения, выносимые на защиту.

1. Разработка и компьютерная реализация алгоритмов с применением всех разработанных автором эвристик для решения нескольких задач дискретной оптимизации (СЛАУ, транспортная задача (псевдогеометрический вариант ЗКВ), вершинная минимизация НКА).

2. Разработка модели вычислений, состоящей в модификации мультиэвристического подхода решения задач дискретной оптимизации. Эта модель связана с комбинированием работающего в ней незавершённого метода ветвей и границ и имитационной нормализации.

3. Разработка алгоритмов гибридного применения имитационной нормализации и обоснование возможностей их практического применения для решения задач дискретной оптимизации в нескольких предметных областях.

4. Результаты сравнения эффективности эвристических алгоритмов — на основе разработанной автором эвристической модели сравнения. Исследование эффективности мультиэвристического подхода к решению задач дискретной оптимизации, модифицированного на основе разработанного комбинированного алгоритма.

Апробация работы.

Результаты диссертационной работы докладывались и обсуждались на:

• XI Международной научно-технической конференции «Проблемы информатики в образовании, управлении, экономике и технике» (Пенза, 2009);

• VI Студенческой международной научно-практической конференции «Интеллектуальный потенциал XXI века: ступени познания» (Новосибирск, 2011);

• V Международной научно-технической конференции молодых специалистов, аспирантов и студентов «Математическое и компьютерное моделирование естественнонаучных и социальных проблем» (Пенза, 2011);

• XI Международной научно-практической конференции «Наука и современность — 2011» (Новосибирск, 2011);

• II Международной научно-практической конференции «Современное состояние естественных и технических наук» (Москва, 2011);

• I Международной научно-практической конференции «Теория и практика в физико-математических науках» (Москва, 2011).

• Международной научно-практической конференции «Молодежь и наука: модернизация и инновационное развитие страны» (Пенза, 2011).

Публикации.

По теме диссертации опубликовано 11 работ, из них 2 — в изданиях, рекомендованных ВАК.

Личный вклад автора.

Постановка задач осуществлялась научным руководителем.

Описываемые в диссертации математические модели вычислений, разработанные алгоритмы их решения, компьютерные реализации алгоритмов и исследование результатов работы программ выполнены автором самостоятельно. Незавершённый метод ветвей и границ и идея комбинирования с применением имитационной нормализации разработаны в соавторстве с научным руководителем.

Основные результаты диссертации.

• Рассмотрены варианты применения алгоритма имитационной нормализации к решению задач дискретной оптимизации (СЛАУ, транспортная задача (ЗКВ), вершинная минимизация НКА).

• Модифицирована модель вычислений, представляющая собой незавершённый метод ветвей и границ.

• Представлены способы решения задач дискретной оптимизации незавершённым методом ветвей и границ в комбинации с генетическим алгоритмом.

• Разработаны и реализованы эвристики для расширения пространства поиска в методе ветвей и границ.

• Описаны и реализованы гибридные алгоритмы с применением имитационной нормализации в качестве локального поиска — с целью расширения пространства поиска МВГ.

• Разработаны и реализованы следующие эвристики: ограничение выбора для генетического алгоритмарасширение пространства поиска для МВГих комбинирование.

• Модифицирована эвристическая оценка эффективности эвристических алгоритмов — на основе модели сравнения алгоритмов с эвристиками и без них.

• Показаны результаты сравнительного улучшения эффективности алгоритмов с применением приведенных в работе эвристик.

Структура и объём диссертации.

Общий объём диссертации -124 страницы. Диссертация состоит из введения, четырёх глав, заключения, списка используемой литературы из 97 наименований и одного приложения.

4.2. Результаты исследования гибридных алгоритмов.

Исследование проводилось автором методом проб: алгоритм запускался с различными значениями параметров (на каждом новом запуске прибавлялось 0.0005 к параметру). Значение считается «хорошим», если получаем «хорошее» решение. Критерии «хорошего» решения — минимизация суммы целевой функции для различных матриц. Таким образом, мы вычислили оптимальные значения параметров алгоритма, которые находятся в интервалах:

• порог вероятности мутации — от 0.0075 до 0.0085.

• порог вероятности скрещивания — от 0.3 до 0.5 размер популяции — 25 (для ГА).

3.5е+006.

Температура Зе+006.

2.5е+006 2е+006.

1,5е+006 10+006 500 000 ¦ 0.

О 10 000 20 000 30 000 40 000 50 000 60 000 70 000 80 000 900СЮ число итарации.

Рисунок 14.

На рисунке 14 показан график зависимости температуры от числа итераций в алгоритме имитационной нормализации. На первой итерации увеличиваем температуру с 30 градусов до Зе+006 градусов для того, чтобы решение можно было принять с вероятностью 1. Как видно из графика делаем так около 500 первых шагов и получаем приемлемое Т0. Далее понижаем температуру. После 15 000 шагов значение Т почти не меняется. Т. е. понижается очень медленно с целью стабилизации решения.

Запуск алгоритма с другими значениями параметров значительно ухудшает качество получаемых результатов. Все дальнейшие исследования проводились при различной комбинации значений параметров из указанных интервалов. Алгоритм для каждого варианта исходных данных запускался несколько раз с различными комбинациями значений параметров.

Подходящее решение находилось за 35 000 — 80 000 итераций алгоритма. Зависимость числа итераций больше 40 000 на качество получаемых решений и параметров алгоритма не выявлена. До 40 000 наблюдаются значительные ошибки. error". j J i i.

4 } $ j.

0 10 29 30 40 50 60.

Рисунок 15 (ось X — номер популяции, ось Y — ошибки решения СЛАУ).

Наибольшее влияние на сложность получения и качество решения оказывает порог вероятности мутации. Для большинства тестов основное число хороших решений алгоритм получает при пороге вероятности мутации, равном 0.008 и при значениях остальных параметров находящихся в указанных выше интервалах.

Очень сильное влияние на качество получаемых решений для генетического алгоритма оказывает размер популяции. Он имеет ярко выраженный оптимум, равный 25 (алгоритм в этом случае сходится быстро и стабильно).

Классическим методам Якоби и Гаусса-Зейделя алгоритм устуи 3.

0 45 0.4 Ь 0.35 0.3 0 25 02 U 5 0 J.

1Ш пает как в размерности матриц, так и в скорости. Важно отметить, что ГА не требует т.н. «предобусловливания» — которое при исследовании этих методов автором не учитывалось. Однако отметим, что применение «предобуславливания» в ГА всё же возможно.

4.2. Результаты сравнения эффективности гибридных алгоритмов.

Для количества городов от 29 до 150 (в псевдогеометрической версии ЗКВ, не допускающей применения методов, используемых в геометрической версии [79], а также в широко известной библиотеке TSPLib [89]) были получены следующие результаты:

• эвристические алгоритмы по сравнению с классическими алгоритмами делает в 2−3 раза меньше итераций;

• в среднем комбинированный алгоритм получал решение в 2 раза быстрее, чем эвристический;

• в среднем качество и скорость комбинированного алгоритма по сравнению с классическими эвристическими алгоритмами не зависят от параметров и размерности задачи.

Исследовано качество решений при одинаковом времени работы алгоритмов. Получены следующие результаты. Комбинированный алгоритм в среднем получает решение со временем выполнения на 1.8% меньшим, чем классический эвристический, и на 2.7% меньшим, чем мультиэвристические.

Сравнение метаэврнстичеких алгоритмов с комбинированным ГА+МВГ+ИН от 100 до 150 от 50 до 100.

Количество городов классические эвристические алгоритмы.

В комбинированный метаэвристический алгоритм Рисунок 16.

Оценка алгоритмов — как эвристических, так и мультиэвристи-ческих — для ИР-полных задач не является тривиальной задачей. Важным свойством всех эвристических алгоритмов является время выполнения и близость полученного решения к оптимальному. Обычно в данных алгоритмах идет «размен» между качеством получаемого решения и временем выполнения алгоритма. Чем большее количество итераций проходит алгоритм, тем более качественное решение мы получаем. Наиболее общий метод сравнения алгоритмов — эмпирический. Но при сравнении алгоритмов опытным путем исследователи сталкиваются с различными используемыми вычислительными ресурсами и типами решаемых задач. Также на время выполнения влияет разный профессиональный уровень кодирования алгоритма. Некоторые алгоритмы сравнения, показав себя хорошо на одних типах задач, не справляются с другими. [19] Для задач типа ЗКВ широко используются методы сравнения на основе решения тестовых задач (benchmark problems). Эти задачи имеют меньше 50, от 50 до 100 и от 100 до 150 городов.

Тестирование алгоритма для решения ЗКВ на данных тестовых задачах показало, что качество решений полученных с использование комбинированного метаэвристического алгоритма превосходит качество решений полученных с помощью классических эвристических методов и методов локального поиска. Мультиэвристические методы более затратны по времени и более сложны в применении — однако именно они являются наиболее эффективными в решении практических задач. Следует отметить, что мультиэвристические методы не противопоставляются классическим эвристическим методам, а наоборот, используются для формирования стратегии поиска в рамках конкретного мультиэвристического алгоритма. Подробные результаты счёта смотреть в таблице 2 и на рисунке 17.

Заключение

.

Разработанный комбинированный алгоритм и эвристики, применённые в нём, в дальнейшем планируется развивать и применить для решения еще трёх задач дискретной оптимизации: минимизация НКА по комбинированным критериям, оптимизация таблиц маршрутизации (в сетях передачи данных) и минимизация дизъюнктивной нормальной формы (ДНФ).