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

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

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

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

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

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Тольятти-2012

9 ОЕВ 2С12

005010452

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

Научный руководитель:

доктор физико-математических наук, профессор Мельников Борис Феликсович

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

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

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

Ведущая организация:

Южный федеральный университет

Защита диссертации состоится 21 февраля 2012 года в 13:00 часов на заседании диссертационного совета Д212.264.03 при Тольяттинском государственном университете по адресу: 445667, Тольятти, ул. Белорусская, 14.

С диссертацией можно ознакомиться в библиотеке Тольятгинского государственного университета, с авторефератом - на сайте диссертационного совета http://edu.tltsu.ru/sites/site.php?s=1496.

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

Автореферат разослан 20 января 2012 года Учёный секретарь

диссертационного совета Д212.264.03

к.п.н., доцент

Пивнева С.В.

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

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

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

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

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

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

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

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

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

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

Цель работы

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

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

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

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

• транспортная задача (в частности - псевдогеометрическая версия задачи

коммивояжёра, ЗКВ);

• вершинная минимизация недетерминированных конечных автоматов

(НКА). .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

защиты информации: Сборник статей / Под ред. проф. Е.А. Крука. - СПб.: ГУ АП, 2006.

5

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

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

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

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

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

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

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

• XI Международной научно-технической конференции «Проблемы ин-

форматики в образовании, управлении, экономике и технике» (Пенза, 2009); _

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

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

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

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

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

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

Публикации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(х,у) = £х,у, (1)

ы

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

5 СХудман, С.Хидетниеми. Введение в разработку и анализ алгоритмов: Пер. с англ. Ю.Б. Котова, Л.В. Сухаревой, Л.В. Ухова Под ред. В.В. Мартынюка М.: Мир. 1981.

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

7

(х,у)А = (Ах, у) = (х,Ату) = УтЛх = хтАту (2)

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

И 2 = у1(х,х); (3)

Н, = ^Лх.х) = <](х,х)А (4)

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

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

IIх -х.\]та=(ЛтЛ(х-х.),(х-х.)) = (а(х- х.), А(х -х,)) = (Ах, Ах) = ||Дх|| | (5)

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

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

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

F(x) = t

(7)

12л ->шт,

ы м

где а у - коэф. системы, х1~- решение (неизвестные), 6/ - свободные члены.

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

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

Приведём описание классической транспортной задачи. Однородный товар находится у т поставщиков в объёмах Его необходимо доста-

вить п потребителям в объёмах Ь1,Ь2,...Ь„. Известны стоимости перевозки ся единицы груза - от каждого /-го поставщика каждому /-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены, и при этом суммарные затраты на перевозку всех грузов минимальны.

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

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

7 MJUnger, S.Thienel, G.Reinelt. Provably good solutions for the traveling salesman problem. - Zeitschrift filr Operations Research, Vo.40 (1994) 183-217.

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

1 = ТУ(х,-хм)2 +{у,-ум)1 +4и ,+а*,)2] (8)

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

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

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

X Y Z X У Z

А # #: А 1 1 р

В # # # В 1 1 1

С # О 0 1 0

Рисунок 2

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

■ Алгоритм минимизации непересекающимися классами совместимости сводится к методу «грубой силы», т.е. к полному перебору систем классов совместимости состояний - с целью отыскания системы, содержащей минималь-

8 L.PolAk. Minimalizations of NFA using the universal automaton / Int. J. Found.Comput. Sei., Vol. 16, No. 5(2005)999-1010.

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

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

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

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

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

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

X Y Z и

А 0 0 1 1

В 1 0 0 1

С 1 0 1 1

D 1 1 1 1

Рисунок 3

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

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

10 Д. Б. Шишков. KYBERNETIKA - International journal published by Institute of Information Theory and Automation — TOM 8(1972). Выпуск №4 с. 297-316

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

10

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

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

“*min (9)

ы У-1

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

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

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

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

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

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

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

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

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

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

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

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

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

-у

• если А/ > О (решение ухудшилось), то принять с вероятностью р = е Т в качестве текущего решения новый вариант решения X, к п. 5.

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

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

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

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

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

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

12 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.

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

11

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

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

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

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

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

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

<р(2)< <р(г'у), <р(2) < <р(21ф.

Одно из подмножеств содержит оптимальное решение. Выберем ту ветку, в которой нижняя граница меньше другой (<р(2] ф, либо <р(21ф). Далее это подмножество {?!и или 21 ^ также разбивается на два новых (левое и правое) подмножества - 2 у и 12у. Продолжаем процесс ветвления до тех пор, пока не получим единственное решение. Назовём его первым псевдо-оптимальным решением. Теперь необходимо рассмотреть все незавершённые ветки. Если все их нижние границы больше длины первого псевдо-оптимального решения, то задача решена. Если же есть ветви, для которых нижние границы меньше, чем целевая функция первого псевдо-оптимального решения, то мы продолжаем процесс ветвления для подмножества с наименьшей нижней границей. Процесс решения заканчивается, когда будут проанализированы все подмножества.

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

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

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

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

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

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

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

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

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

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

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

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

13

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

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

• либо при получении тривиальной задачи (задачи нулевой размерности)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 4 (ось X - номер популяции, ось У - ошибки решения СЛАУ) Наибольшее влияние на сложность получения и качество решения оказывает порог вероятности мутации. Для большинства тестов основное число хороших решений алгоритм получает при пороге вероятности мутации, равном

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

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

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

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

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

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

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

Исследовано качество решений при одинаковом времени работы алго-

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

16 INFORMS J. on Computing 2005 17:290-304, http: //www. tsp.gatech.edu/data/index.html.

16

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

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

—W

-Jralfel - ■ Я Е

Кол-во городов

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

Ш классические эвристические алгоритмы Нкомбинированный метаэвристический алгоритм

Рисунок 5

Для задач типа ЗКВ широко используются методы сравнения на основе решения тестовых задач (benchmark problems). Эти задачи имеют меньше 50, от 50 до 100 и от 100 до 150 городов. Подробные результаты счёта смотреть в таблице 1 и на рисунке 6.

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

Problem (TSPLIB) Opt (TSPLIB) SA GA GA+SA SA+flip GA+B&B+SA

brazils 8 - 25354 25664 25643 23681 22854

Pr76 103629 109118 109207 105118 105171 102242

st70 751 695 689 688 727 671

berlin52 7754 7542 7544 7544 7443 7325

ЄІ151 422 431 442 433 429 416

eil76 537 546 566 560 548 518

1ІПІ05 14370 14382 14626 14622 14383 14329

eillOl 627 635 662 661 640 619

prl44 - 58169 59334 59334 58535 58137

prl36 - 95907 101820 101820 97587 93772

prl07 - ■ 44225 45072 45028 44301.68 44303

bayg29 1608 1614 1628 1628 1610 1601

chi 50 6486 6594 6743 6699 6562 6428

В библиотеке ТЗРЫВ на 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% более оптимальный.

17 Перестановка части пути производится инверсионно. В данном случае до применения flip: {0123

4 5 6 7 8 9 10 11 12 13 14 15}, после применения flip (с 5 по 10 позицию): {0 1234 10 9876511 12

13 1415}

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

О 10000 20000 30000 40000 50000 60000 70000 80000 90000

итерации

Рисунок 6

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

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

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

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

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

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

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

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

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

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.

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

Подписано в печать 17.01.2012. Формат 60x84/16. Печать оперативная. Уел. п. л. 1,16.

Тираж 120 экз. Заказ № 3-04-12.

Издательство Тольятгинского государственного университета 445667, г. Тольятти, ул. Белорусская, 14

61 12-1/619

Тольяттинский государственный университет

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

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

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

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

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

Научный руководитель: д. ф.-м. н., профессор Мельников Б.Ф.

Тольятти-2012

Оглавление

Введение...............................................................................................................3

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

1.1. Система линейных алгебраических уравнений.............................18

1.2. Транспортная задача. Задача коммивояжера.................................20

1.3. Минимизация недетерминированных конечных автоматов......25

Заключение...................................................................................................32

Глава 2. О методах решения.............................................................................33

2.1. Обоснование выбора алгоритмов......................................................33

2.2. Алгоритм имитационной нормализации.........................................34

2.3. Генетический алгоритм.......................................................................35

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

Глава 3. Комбинированный алгоритм с настройкой на решение конкретной задачи дискретной оптимизации.....................................................................39

3.1. Настройка генетического алгоритма на предметные области.... 39

3.2. Настройка алгоритма имитационной нормализации на предметные области....................................................................................44

3.3. Преобразование метода ветвей и границ в незавершённый.......45

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

алгоритмах....................................................................................................47

Заключение...................................................................................................55

Глава 4. Сравнительные характеристики гибридных алгоритмов...............57

4.1. Обзор методов и анализ сравнения алгоритмов............................57

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

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

Заключение.........................................................................................................75

Приложение.......................................................................................................76

Литература.......................................................................................................115

Введение

Задачи оптимизации - одна из востребованных проблем современной вычислительной и прикладной математики. Решение подобных проблем требуется во многих задачах из различных отраслей науки и техники. Ещё Леонард Эйлер (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 наименований и одного приложения.

Кра�