автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Применение имитационной нормализации в гибридных алгоритмах

На правах рукописи

Эйрих Станислав Николаевич

ПРИМЕНЕНИЕ ИМИТАЦИОННОЙ НОРМАЛИЗАЦИИ В ГИБРИДНЫХ АЛГОРИТМАХ

05.13.18 - математическое моделирование, численные методы и комплексы программ

4858310

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

2 7 ОПТ 2011

Тольятти 2011

4858310

Диссертация выполнена в Тольяттинском государственном университете.

Научный руководитель доктор физико-математических наук, профессо;

Мельников Борис Феликсович

Официальные оппоненты: доктор технических наук, профессор,

академик МАИ, МАНЭБ, АСН Левин Виталий Ильич;

кандидат физико-математических наук Белозёрова Алла Равильевна

Ведущая организация - Южный федеральный университет.

Защита состоится 3 ноября 2011 года в 13.00 назаседании диссертационног совета Д212.264.03 при Тольяттинском государственном университете по адрес 445667, Тольятти, ул. Белорусская, 14.

С диссертацией можно ознакомиться в библиотеке Тольяттинского государ ственного университета, с авторефератом - на сайте диссертационного совет Ь«р://ес1и.и18и.гиМе5/511е.р11р?5=1496.

Отзывы по данной работе в двух экземплярах, заверенные печатью организа ции, просим направлять по адресу: 445667, Тольятти, ул. Бероссукая, 14, ТГ" диссертационный совет Д212.264.03.

Автореферат разослан 30 сентября 2011 г.

Ученый секретарь

диссертационного совета Д212.264.03 к.п.н., доцент

С.В. Пивнева

1. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

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

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

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

1 Б.Ф.Мельников. Мультиэвристический подход к задачам дискретной оптимизации // Кибернетика и системный анализ (НАН Украины), 2006, №3. С. 32-42.

2 В английской литературе - «simulated annealing». В русской литературе чаще, к сожалению, применяется неудачный термин «эмуляция отжига». Термин «имитационная нормализация» правильнее с точки зрения физики и понятнее математикам-программистам, он связан с методами имитационного моделирования в статистической физике, основанными на методах Монте-Карло. Подробнее см. примечание переводчика в книге: Ю.Громкович. «Теоретическая информатика...», изд-во БХВ, СПб, 2010; см. также: K.Binder. Monte Carlo methods in statistical physics. Berlin: Springer, 1978.

тимизации - в целях получения более близкого к оптимальному решения за более короткое время.

Для реализации концепции комбинирования часто используются стандартные надёжные технологии, например, метод локального поиска, динамическое программирование и жадные алгоритмы. Задачи, рассмотренные в данной работе, имеют большую размерность, и известно, что получение их оптимального решения возможно не для каждого входа - однако для большинства «типичных» входов вполне реально. Поэтому приемлемые результаты даёт применение метода ветвей и границ с предварительным вычислением, для которого используется генетический алгоритм. Другой способ комбинирования - соединение концепции рандомизации и аппроксимации. При этом имитационную нормализацию можно рассматривать как рандомизированный локальный поиск для метода ветвей и границ. Комбинирование двух концепций (рандомизации и предварительного вычисления) соединения алгоритмов даёт приемлемую эвристику.

Цель работы

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

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

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

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

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

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

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

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

рандомизированного локального поиска в методе ветвей и границ.

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

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

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

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

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

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

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

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

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

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

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

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

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

нитных полей, уравнения Максвелла, Навье-Стокса3, атака криптосистем на основе открытого ключа4 и др.) методами конечных элементов (FEM) и конечных объемов (FVM) - особенно на неструктурированных сетках.

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

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

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

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

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

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

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

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

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

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

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

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

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

М.Ю.Баландин, Э.П.Шурина. Некоторые оценки эффективности параллельных алгоритмов решения СЛАУ на подпространствах Крылова. - Вычислительные технологии. Том 3 №1 1998

С.В.Беззатеев. Методы защиты информации от несанкционированного доступа Вопросы передачи и защиты информации: Сборник статей / Под ред. проф. ЕА. Крука. - СПб ГУАП

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

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

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

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

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

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

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

Публикации

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

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

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

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

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

2. КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении описывается предмет представляемой работы, общий обзор диссертации, актуальность и новизна рассматриваемой проблемы.

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

чем экспоненциальные в зависимости от размерности задачи.

В первой главе даются основные определения. Приводятся наиболее важные понятия и определения предметных областей - СЛАУ, транспортная задача (ЗКВ) и НКА. Такие как комбинаторика, окрестность, метод обобщенных минимальных невязок, несимметричная и разреженная матрица, гамильтонов цикл, «мягкие» и «жёсткие» ограничения маршрутизации, динамическое время и движение транспорта, недетерминированные и детерминированные конечные автоматы, состояния, переходы, блок (грид).

Для задач дискретной оптимизации характерны такие отличительные признаки как факториальный рост вычислительной сложности и допустимость приближенного решения. Представителями указанного класса задач являются ЫР-полные задачи оптимизации5.

В работе рассматривается решение СЛАУ Ах = Ь, где А - невырожденная матрица размерности тхп,ахнЬ- вектор размерности их/, составленные из действительных коэффициентов.

В силу невырожденности матрицы А существует некоторое точное решение х- - А"1 Ъ. Задача получения решения СЛАУ сводится к нахождению х*. Невязкой 6, соответствующей вектору х, будем называть вектор Дх = Ъ - А х = А(х. - х), где (х- - х) есть ошибка решения.

Линейный оператор А, заданный матрицей А, действует в пространстве Л". Введём в нём скалярное произведение

с*,=!>,>>,. (о

Для действительного случая сопряжённый оператор А* определяется матрицей А7, так что (Ас, у) = (х, А7у). Иногда также оказывается удобным использование скалярного А-произведения

(х,у)А = (Ах,у) = (х,А'у) = угАх = хТАгу (2)

На основе скалярных произведений введём в Л" векторные нормы

И2 =7(^1); (3)

И 1=4{Ах,х) = 4{х,х)л (4)

(евклидова норма и А-норма соответственно).

Если явно не оговорено обратное, то будем предполагать, что матрица А не обладает свойством симметрии и положительной определённости (А-норма, очевидно, применима лишь к таким матрицам, иначе она вообще

5 С.Гудман, С.Хидетниеми. Введение в разработку и анализ алгоритмов: Пер. с англ. Ю.Б. Ко-

това, Л.В. Сухаревой, Л.В. Ухова Под ред. В.В. Мартынюка М.: Мир. 1981.

'' В.В.Воеводин. Вычислительные основы линейной алгебры. - М.: Наука, 1977. -304 с.

не является нормой).

Для невырожденной А симметризованная матрица А7А является положительно определённой, и тогда для евклидовой и А-нормы справедливо соотношение

|.v - JC.II',= (А7 А(х - х.),(х - х.)) = (А(х - х.), А(х - х.)) = (Д*. Ах) = ||Лх||* (5)

Собственные значения матрицы А (которые, вообще говоря, являются комплексными) будем обозначать Л/А). Максимальный из всех модулей | Я/А) | есть спектральный радиус матрицы. Вектор ек будет обозначать к-й единичный орт:

ек = (0,...,0,1к,0,...,0)т (б)

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

► min, (7)

я*)=2

н

где - коэф. системы, х; - неизвестные, Ь; - свободные члены.

Задача коммивояжёра - классическая проблема дискретной комбинаторной оптимизации7. Она заключается в том, чтобы найти кратчайший Гамильтонов цикл в графе. В области задач дискретной оптимизации ЗКВ служит своеобразным полигоном, на котором испытываются новые методы решения.

Приведём некоторые варианты ЗКВ:

• «случайная» - все элементы матрицы ЗКВ генерируются как случайные величины с заданным законом равномерного распределения;

• «геометрическая» - случайно генерируются координаты всех городов как точек единичного квадрата (с равномерным распределением обеих координат), а элементы матрицы ЗКВ суть расстояния между соответствующими точками;

• «псевдо-геометрическая» - все элементы матрицы метрической ЗКВ после генерации дополнительно умножаются на случайные числа, формируемые с заданным нормальным законом распределения с ц=1.

По-видимому, именно псевдо-геометрический вариант является наиболее «приближённым к реальной действительности» - и при этом наименее исследованным. Для псевдо-геометрической ЗКВ общая длина пути

7 M.Jünger, S.Thienel, G.Reinelt. Provably good solutions for the traveling salesman problem. - Zeitschrift für Operations Research, Vo.40 (1994) 183-217.

может быть вычислена по следующей формуле (х и у- координаты города, Л - некоторое случайное число, // - дополнительный параметр города):

(8)

Задача вершинной минимизации (или минимизация внутренних состояний) конечного автомата (КА) заключается в нахождении такого автомата, эквивалентного заданному, который имел бы наименьшее число со-£

стояний . Возможность сокращения числа состояний определяется тем, что некоторые внутренние состояния автомата, обозначаемые как совместимые, можно объединять в одно состояние, не нарушая при этом закона функционирования автомата.

Рассмотрим на примере алгоритм минимизации непересекающимися классами совместимости.

Рисунок 1

На рисунке 1 изображены два конечных автомата, ассоциированных с исходным НКА. По этим двум КА строится таблица соответствия вершин автоматов.

X Y Z X Y z

.4 # # A 1 1 0

В # # # В 1 1 I

V # С 0 I 0

Рисунок 2

Далее для таблицы минимизируется число прямоугольных блоков, содержащих все её непустые элементы, затем по блокам, входящим в найденное покрытие, строится НКА. При этом важно отметить, что каждая такая таблица соответствует даже не автомату, а задаваемому им языку. Более того, можно доказать, что любая прямоугольная таблица, заполненная О и 1 и имеющая специальные свойства: • нет одинаковых строк,

8 L.Polak. Minimalizations of NFA using the universal automaton / Int. J. Found Comnut Sci Vol 16, No. 5(2005)999-1010. '

• нет одинаковых столбцов,

• нет ни строк, ни столбцов, содержащих только О,

является таблицей соответствия вершин некоторого автомата9.

Алгоритм минимизации непересекающимися классами совместимости

сводится к методу «грубой силы», т.е. полный перебор систем классов совместимости состояний с целью отыскания системы, содержащей минимальное число классов. Этот алгоритм позволяет находить «абсолютно минимальные» автоматы, но его применение практически возможно только для сравнительно несложных автоматов (обычно - с числом состояний меньше 8), т.к. при большем числе состояний метод становится очень затратным с вычислительной точки зрения. Одним из методов решения данной проблемы является использование эвристических (мультиэвристических) алгоритмов -которые позволяют за приемлемое время получать решения близкие к оптимальным. В данной работе для решения рассматриваемой задачи предлагается использование гибридного метода имитационной нормализации (имитации отжига), генетического алгоритма и метода ветвей и границ.

Задачу вершинной минимизации недетерминированных конечных автоматов можно свести к важнейшей и наиболее трудоёмкой подзадаче в данных алгоритмах (даже в случае относительно небольших НКА). Задана прямоугольная матрица, заполненная элементами 0 или 1. Некоторую пару подмножеств строк и столбцов назовём блоком (гридом)10, если

• на их пересечениях стоят только 1;

• множество нельзя пополнить ни строкой, ни столбцом, не нарушив первого свойства.

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

Пример матрицы, в которой имеются 5 блоков: а = {А,В,С,0} X {II}, Ь = {А,С,Б} X {2, и}, % = {В,С,Б} X {Х,и}, (3 = {СД}} X {Х,г,и} ии={0} X {Х,У,2,и}. Для покрытия всех значений 1 данной матрицы достаточно использовать 3 из этих 5 блоков: Ь, § , и лу .

9 М.Р.Зузанова. Некоторые алгоритмы эквивалентного преобразования недетерминированных конечных автоматов: дис. ... канд. физ.-мат. наук: 05.13.18 / Тольятти: ТГУ, 2010. - 115 е..

10 Б.Ф.Мельников, С.В.Пивнева, О.А.Рогова. Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов/ // Стохастическая оптимизация в информатике. Том 6. Санкт-Петербургский государственный университет НИИ информационных технологий. Изд-во СПбГУ, 2010.

X У г и

А 0 0 1 1

В 1 0 0 1

С 1 0 1 1

О 1 1 ] 1

Рисунок 3

Потенциальная недопустимость получаемых решений (т.е. наборы блоков, покрывающих не все 1 в матрице 8, изображённой на рисунке 3) решается добавлением целочисленной матрицы Н, имеющей такой же размер. Для каждого ненулевого элемента матрицы Б в матрице Н хранится число покрывающих его блоков. При добавлении или удалении блока значения матрицы Н пересчитываются. Если при удалении некоторого блока из текущего покрытия счетчик числа покрывающих блоков в матрице Н для какой-либо 1 матрицы Б обнуляется, то такое покрытие признается недопустимым и блок возвращается в покрытие.

Соответственно целевой функцией вершиной минимизации является:

= ->тт (9)

1-1 ;=1

где Ьи - коэф. матрицы Н.

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

В настоящей работе рассматривается смешанный метод. В его основе - незавершённый метод ветвей и границ (МВГ). Для формирования начального множества допустимых решений применяется генетический алгоритм (ГА). В качестве локального поиска используется имитационная нормализация (ИН).

Обоснованием выбора генетического алгоритма и имитационной нормализации для комбинирования служили следующие соображения:

• алгоритмы основаны на простой и ясной идее - и легко реализуемы;

• алгоритмы могут применяться почти для всех задач оптимизации;

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

Алгоритм имитационной нормализации можно представить следую-

щей схемой ":

1. Задать начальное корректное решение Х" и считать его текущим (Х=Х").

2. Задать начальную температуру Та и считать её текущей (Г-То).

3. Применить операцию мутации решения к текущему решению X it получить новый корректный вариант решения X.

4. Найти изменение целевой функции А/ = /(Л' )-/(А'):

• если А/ < О (решение улучшилось), то новый вариант решения считать текущим (Х=Х), к п. 5;

• если А/ >0 (решение ухудшилось), то принять с вероятностью

р = е Т в качестве текущего решения новый вариант решения X, к п. 5.

5. Вызвать функции изменения текущей температуры и шага мутации.

6. Если не выполнен критерий останова, то перейти к п.З.

Генетический алгоритм можно представить следующей схемой12:

1. Сгенерировать начальную популяцию

Xa.

2. Вычислить приспособленность каждой особи и популяции в целом. Посчитать вероятность выбора особей.

3. С определённой вероятностью выбрать две особи и применить операцию скрещивания.

4. Выполнить onepaiptu мутации и/или инверсии решения.

5. Поместить полученную хромосому в новую популяцию.

6. Выполнить операции, начиная с пункта 3, к раз - где к равно либо количеству особей в начальной популяции, либо необходимому количеству особей в новой популяции.

7. Если не выполнен критерий останова, то перейти к п.2, и выполнить операции для новой популяции.

Метод ветвей и границ.

Основная идея метода ветвей и границ (на примере ЗКВ) состоит в том, что в начале работы строится нижняя граница <р длин множества маршрутов Z. Затем множество маршрутов разбивается на два подмножества таким образом, чтобы первое подмножество состояло из маршрутов, содержащих некоторую дугу (i,j), а другое подмножество не содержало этой дуги. Для каждого из подмножеств определяются нижние границы - по

" E.H.L.Aarts, J.H.M.Korst, P.J.M. van Laarhoven. Simulated annealing. In: Lo-cal search in combinatorial optimization. Chichester: Wiley, 1997, 91-120.

11 J.Hromkovic. Algorithms for Hard Problems. - Springer, 2003.

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

Сравнивая нижние границы <р(7!и <р(2'можно выделить то подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины. Затем одно из подмножеств 71ц или т!ц по аналогичному правилу разбивается на два новых 22ц и '¿2Ч. Для них снова отыскиваются нижние границы (р (¿'¡), и <р (¿¡¡) - и т.д. Процесс ветвления продолжается до тех пор, пока не отыщется единственный маршрут. Его называют первым рекордом (или первым псевдооптимальным решением). Затем просматривают оборванные ветви. Если все их нижние границы больше длины первого рекорда, то задача решена. Если же есть такие, для которых нижние границы меньше, чем длина первого рекорда, то подмножество с наименьшей нижней границей подвергается дальнейшему ветвлению - до тех пор пока не будет установлено, что оно не содержит лучшего маршрута.

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

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

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

Алгоритм имитационной нормализации и генетический алгоритм с настройкой на предметные области:

1. Конфигурация (допустимое решение). Для ЗКВ - города пронумерованы числами к=1..п, каждый город имеет координату (х„у^. Последовательность (к^къ-.Лп) интерпретируется как порядок городов - маршрут объезда [3]; СЛАУ - коэффициенты вектора х; НКА - двоичный вектор, каждый элемент которого равен 1, если соответствующий блок включается в покрытие, и 0 в противном случае.

2. Мутаг/ия. Проанализировав критерии выживаемости и операции скрещивания, мутации и селекции, улучшим работу ГА. Без операции мутации популяция никогда не выйдет за границы значений, определённых при формировании стартовой популяции. Следовательно, при этом не удастся найти решение, которое содержит значение генов, не использующееся при формировании стартовой популяции. Таким образом, алгоритм сразу может попасть в локальный минимум и не выбраться из него. Но замена одной хромосомы на случайное значение может преобразовать хромосому настолько сильно, что она выйдет за границы окрестности допустимых решений. Ввиду вышесказанного мы модернизируем операцию мутации. Будем изменять значение хромосомы следующим образом. По задачам: ЗКВ - заменять на часть пути с номерами городов, равномерно распределённых на интервале [min(X),max(X)]; СЛАУ - заменять на случайное число, равномерно распределённое на интервале f-л/А), 1/AJJ, где | À/А) | - спектральный радиус матрицы; НКА - заменять на 0 или 1. Это дает возможность выйти за границы окрестности, но не дает уйти далеко за ее пределы.

3. Целевая функция. Вычисляется для задач по формулам: в СЛАУ (7) - невязка, т.е ошибка решения; в ЗКВ (8) - общая длина пути; в НКА (9) - сумма вхождений блоков в покрытие.

4. Критерий останова (только для ГА). Зададим критерии останова следующим образом: если хромосома достигнет коэффициента выживаемости 0, то есть станет решением, то происходит останов алгоритма. В противном случае алгоритм останавливается через заданное число итераций, и лучшая хромосома будет решением.

5. График охлаждения (только для ИН). Начальная температура и конфигурация генерируется случайно. После выбора соседнего состояния X' увеличиваем температуру Т таким образом, чтобы X' можно было принять с вероятностью 1. Делая так для некоторого числа первых шагов, получаем приемлемое Тп. После каждых d шагов значение Т умножается на а. Т.е. понижаем температуру через каждые d шагов по следующей формуле:

Т=а*Т,0<а<1 (11)

Незавершённый метод ветвей и границ13

Будем далее называть правой задачей очередного шага МВГ задачу, полученную при уменьшении размерности. Например, в ЗКВ таковой является та подзадача, в которой мы обязательно включаем в выбираемый маршрут

1J B.Melnikov. Discrete Optimization Problems - Some New Heuristic Approaches, Proceedings of the Eighth International Conference on High-Performance Computing in Asia-Pacific Region, p. 7380, 2005.

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

Несложная эвристика, преобразующая завершённый МВГ в незавершённый (а именно на основе незавершённого МВГ и формируются описанные выше апуПте-алгоритмы), заключается в следующем. Каждый раз при получении очередной правой задачи (назовём её задачей Т) мы фактически строим последовательность правых задач (ППЗ) - т.е. саму задачу Т, правую задачу задачи Т, правую задачу правой задачи задачи Т, и так далее. Естественно, каждый раз строятся (и включаются в список задач для потенциального решения в последующем) и соответствующие левые задачи - левая задача задачи Г, левая задача правой задачи задачи Т, и так далее. Описанный процесс заканчивается:

• либо при получении тривиальной задачи (задачи нулевой размерности) - в этом случае мы запоминаем её решение (границу, получаемый к моменту её постановки тур, и т.п. характеристики) в качестве текущего на данный момент времени псевдо-оптимального решения сформулированного ранее апуйте-алгоритма;

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

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

Итак, мы описали простой процесс построения апуйте-алгоритма на основе некоторого конкретного варианта МВГ.

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

так и большой размерностях.

Комбинированный алгоритм состоит из следующих этапов:

1. Сформировать начальное решение генетическим алгоритмом с эвристикой ограничения операции мутации решений.

2. Построить ППЗ незавершённым МВГ.

3. По окончании работы МВГ осуществить поиск решений алгоритмом имитационной нормализации.

4. В дереве решений МВГ мы можем построить полный путь до решения полученного ИН.

Центральным алгоритмом для комбинированного метаэвристическо-го метода является МВГ. Привлекательность данного метода в том, что МВГ позволяет быстро отсекать множества заведомо неоптимальных решений и на малых размерностях находить решение близкое к найденному точными методами. Однако МВГ может попасть в локальный оптимум. Возникает потребность в том, чтобы расширить пространство поиска - в надежде найти решение близкое к оптимальному.

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

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

Улучшаем качество:

• Начальное решение. Генетический алгоритм даёт решение, близкое к оптимальному, за малое время. Чтобы повысить качество конечного решения будем применять ГА для формирования начального решения.

• Механизм получения окрестности. Используем комбинирование МВГ с алгоритмом имитационной нормализации для того, чтобы расширить пространство поиска МВГ. Хоть в основе имитационной нормализации и лежит метод локального поиска, ИН позволяет продолжать поиск после нахождения локального оптимума, тем самым расширяя пространство поиска. Решение, полученное ИН, находится в окрестности решений МВГ, до него есть путь в дереве решений и это не локальный оптимум, а решение, близкое к глобальному оптимуму. Т.к. с помощью ненулевой ве-

роятности принятия худшего решения алгоритма ИН осуществляется выход из локального оптимума.

Четвёртая глава описывает исследования и методы решения, а также основные результаты сравнения полученного комбинированного алгоритма с классическими эвристическими, мультиэвристическими и точными алгоритмами.

Методы решения многих W-трудных задач можно разделить на точные (exact approaches), эвристические (heuristic aproaches) и метаэвристические (metaheuristics aproaches). Точные методы решения такого класса задач основаны на полном переборе всех возможных решений, и являются не эффективными при решении задач большой размерности - из-за их больших временных затрат (время решения экспоненциально зависит от размерности задачи). Поэтому в данной работе они не будут рассматриваться, основное внимание уделим эвристическим и мультиэвристическим методам. Недостаток данных методов в том, что они являются приблизительными (approximate methods), решение, полученное данными методами, может быть далёким от оптимального. А преимущество - в том, что они позволяют найти приемлемое решение NP-полных задач большой размерности за приемлемое время.

Сократить временные затраты на поиск решений помогает распараллеливание алгоритмов. В настоящее время известно несколько подходов к распараллеливанию эвристических алгоритмов14:

• параллельный независимый запуск алгоритма на нескольких узлах;

• параллельный запуск алгоритма с периодическим обменом информацией;

• разбиение пространства решений на области и поиск в каждой отдельно.

Придерживаясь этого разделения, наилучшие решения на сегодняшний день были получены распараллеливанием классических эвристических алгоритмов. Одним из таких алгоритмов является метод ветвей и границ, основанный на локальном поиске. Как и у большинства методов, основанных на локальном поиске, у МВГ есть недостаток - попадание в локальный оптимум.

Основными понятиями в методах локального поиска, являются пространство поиска (search space) и механизм построения окрестности решения (neighborhood structure). Рассмотрим эти понятия более подробно. Пространство поиска - это все возможные решения, которые могут быть

14 D.R.Greening. Parallel simulated annealing techniques. - Emergent computation. 1991, 293-306. G.C.Gomez. A general interface for distributed and sequential simulated annealing. - Qualifier II Research. Purdue University. 1994.

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

В последние годы для решения задач оптимизации используются так называемые мультиэвристические методы. К данным методам относятся: алгоритм имитационной нормализации или метод имитации отжига (simulated annealing), метод поиска с запретами (tabu search), метод муравьиной колонии (ant colony optimization), генетические и эволюционные алгоритмы.

Мультиэврестические алгоритмы наиболее применимы. Однако у них есть недостаток - решения близкие к оптимальным удается получить только на задачах большой размерности Р =NM =Ю9 -¡-ю10. Для задач сверхбольшой размерности P=NM >10" на момент написания работы не найдены алгоритмы решения NP-трудных задач за приемлемое время.

Суть мультиэврестических методов можно кратко изложить следующим образом. Имеется текущее решение задачи. Данное решение итеративно сравнивается с модифицированным решением из окрестности текущего решения. Если модифицированное решение лучше текущего (в смысле целевой функции), то модифицированное решение становится текущим. Набор модифицированных решений, которые можно получить из текущего, называется окрестностью текущего решения. Механизм получения модифицированного решения из текущего является важным элементом метода, в ЗКВ используется перестановка г-дуг между маршрутами; при этом следует заметить, что рассматриваются только допустимые решения. Качество полученного решения зависит от начального решения и от используемого механизма получения окрестности данного решения.

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

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

ров алгоритма, которые находятся в интервалах:

■ порог вероятности мутации - от 0.0075 до 0.0085

• порог вероятности скрещивания - от 0.3 до 0.5

• размер популяции - 25 (для ГА)

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

Подходящее решение находилось за 35000 - 80000 итераций алгоритма. Зависимость числа итераций больше 40000 на качество получаемых решений и параметров алгоритма не выявлена. До 40000 наблюдаются значительные ошибки.

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

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

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

Классическим методам Якоби и Гаусса-Зейделя алгоритм уступает как в размерности матриц, так и в скорости. Важно отметить, что ГА не требует т.н. «предобусловливания» - которое при исследовании этих методов автором не учитывалось. Однако отметим, что применение «предобу-славливания» в ГА всё же возможно.

0.5

0.2

Для количества городов от 29 до 150 (в псевдогеометрической версии ЗКВ, не допускающей применения методов, используемых в геометрической версии15, а также в широко известной библиотеке ТБРЫЬ ) были получены следующие результаты:

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

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

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

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

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

II

r,..,..,,...

1 ( —г 1

от 100 до 150 от 50 до 100 <50

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

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

Оценка алгоритмов - как эвристических, так и мультиэвристических -для NP-полных задач не является тривиальной задачей. Важным свойством всех эвристических алгоритмов является время выполнения и близость полученного решения к оптимальному. Обычно в данных алгоритмах идет «размен» между качеством получаемого решения и временем выполнения алгоритма. Чем большее количество итераций проходит алгоритм, тем более качественное решение мы получаем. Наиболее общий метод сравнения алго-

15 J.Allwright, D.Carpenter. A distributed implementation of simulated anneling for traveling salesman problem. - Parallel Computing. 1989, No 3,335-338

16 INFORMS .1. on Computing 2005 17:290-304,

http://www.tsp.gatech.edu/data/index.html.

ритмов - эмпирический. Но при сравнении алгоритмов опытным путем исследователи сталкиваются с различными используемыми вычислительными ресурсами и типами решаемых задач. Также на время выполнения влияет разный профессиональный уровень кодирования алгоритма. Некоторые алгоритмы сравнения, показав себя хорошо на одних типах задач, не справляются с другими. Для задач типа ЗКВ широко используются методы сравнения на основе решения тестовых задач (benchmark problems). Эти задачи имеют меньше 50, от 50 до 100 и от 100 до 150 городов.

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

Таблица 1: Результаты теста, ограниченного по времени, на TSPLIB

Problem (TSPLIB) Opt (TSPLIB) SA GA GA+SA j SA I flip .....................] GA+B&B+SA

brazil58 - 25354 25664 25643 ; 23681 22854

pr76 103629 j109118 109207 105118 ; 105171 102242

st70 751 j 695 689 688 727 671

berlin52 7754 7542 7544 7544 7443 7325

eilSI 422 431 442 433 429 416

eil76 537 546 566 560 548 518

linlOS 14370 14382 14626 14622 14383 14329

eil 101 627 635 662 661 640 619

prl 44 - 58169 59334 59334 58535 58137

pr 136 - 95907 101820 101820 97587 93772

prl 07 - 44225 45072 45028 44301.68 44303

bayg29 1608 1614 1628 1628 1610 1601

chl50 6486 6594 6743 6699 6562 6428

В библиотеке Т8РЬ(В на 1994 год получены оптимальные, на тот момент, пути. Например, для задачи «Ьег1т52» показан путь - {1 49 32 45 19 41 8 9 10 43 33 51 11 52 14 13 47 26 27 28 12 25 4 6 15 5 24 48 38 37 40 39 36 35 34 44 46 16 29 50 20 23 30 2 7 42 21 17 3 18 31 22} , стоимость которого равна 7754. Алгоритмом имитационной нормализации с применением эвристики мутации Шр17 получен путь {33 43 10 9 8 41 19 45 1 22 31 18 3 17 7 2 42 30 20 23 21 52 14 13 11 51 12 28 27 26 47 29 50 16 44 46 25 4 6 15 5 24 48 38 37 40 39 34 35 36 49 32}, стоимость которого равна 7443, - т.е. примерно на 4% более оптимальный.

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

35000

Длина пун

30000 25000 20000 15000 10000

5000

0 10000 20000 30000 40000 50000 60000 70000 80000 90000

итер31у1и

Рисунок 6

3. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

17 Перестановка части пути производится инверсионно. В данном случае до применения flip: {0 1 23 4 5 6 7 8 9 10 И 12 13 14 !5j, после применения flip (с 5 по 10 позицию): (0 1 2 3 4 10 9 8 7 65 11 12 13 14 15}

горитмом.

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

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

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

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

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

4. ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в рецензируемых журналах, рекомендованных ВАК

1. Эйрих С.Н. Подход к модернизации генетического алгоритма для решения систем линейных алгебраических уравнений. Известия высших учебных заведений. Поволжский регион. Физико-математические науки. Пенза 2009. № 3. С. 88-95. (Импакт-фактор РИНЦ 2009- 0,247.)

2. Мельников Б.Ф., Эйрих С.Н. Подход к комбинированию незавершенного метода ветвей и границ и алгоритма имитационной нормализации. Вестник Воронежского гос. унив, серия: Системный анализ и информационные технологии, 2010, № 1. С. 35-38. (Импакт-фактор РИНЦ 2009-0,024.)

Публикации в рецензируемых научных журналах и изданиях

3. Эйрих С.Н. Исследование имитационной нормализации на примере решения систем линейных алгебраических уравнений. Проблемы информатики в образовании, управлении, экономике и технике: Сб. материалов Междунар. научно-техн. конф - Пенза: ПДЗ, 2009. - С. 74-76.

4. Эйрих С.Н. Подход к модернизации генетического алгоритма для решения систем линейных алгебраических уравнений. Вектор науки Толь-ятгинского государственного университета. 2009. № 4. С. 5-8.

5. Эйрих С.Н. Вариант комбинирования алгоритма имитационной нормализации с эвристическими методами. Математическое и компьютерное моделирование естественнонаучных и социальных проблем: Сб. материалов Междунар. научно-техн. конф.-Пенза: ПДЗ,2011.-С. 143-145.

6. Эйрих С.Н. Смешанный алгоритм имитационной нормализации и незавершённого метода ветвей и границ. Интеллектуальный потенциал XXI века: ступени познания: Сборник материалов VI Международной студенческой научно-практической конференции / Под общ. ред. С.С. Чернова. - Новосибирск: Издательство НГТУ, 2011. - С. 182-185.

7. Эйрих С.Н. Версия гибридного алгоритма имитационной нормализации для решения транспортной задачи. Наука и современность - 2011: сборник материалов XI Международной научно-практической конференции / Под общ. С.С.Чернова. - Новосибирск: Издательство НГТУ, 2011. -С. 325-329.

8. Эйрих С.Н. Способ гибридного применения алгоритма имитационной нормализации. Научный журнал «Естественные и технические науки». Современное состояние естественных и технических наук: Материалы II Межд. научно-практ конф. (25.05.2011) - Москва, изд-во «Спутник+»,

2011.-С. 107-110.

9. Эйрих С.Н. Решение транспортной задачи гибридным алгоритмом имитационной нормализации. Теория и практика в физико-математических науках: Материалы I Международной научно-практической конференции (01.06.2011) - Москва, изд-во «Спутник+», 2011. - С. 45-49.

10. Эйрих С.Н. Вершинная минимизация недетерминированных конечных автоматов гибридным алгоритмом с применением имитационной нормализации. Материалы Межд. научно-практической конф. «Молодежь и наука: модернизация и инновационное развитие страны». Том 1- Пенза: Изд-во ПГУ, 2011. С. 69-73.

П.Мельников Б.Ф., Эйрих С.Н. Варианты гибридного применения алгоритмов имитационной нормализации. В кн.: «Некоторые вопросы математического моделирования дискретных систем», монография. Тольятти, изд-во ТГУ, 2011.

Лицензия на издательскую деятельность № 03912 от 2.02.2001 г. Сдано в набор 28.09.2011. Подписано к печати 29.09.2011. Формат 60x84/16. Бумага офсетная. Гарнитура Times ЕТ. Печать оперативная. Усл. п.л. 1,6. Уч.-изд. л. 1,5. Тираж 120 экз. Заказ № 257.

Отпечатано в типографии ВУиТ. Лицензия на полиграфическую деятельность № 7 - 0027 от 23.06.2000 г.