Применение имитационной нормализации в гибридных алгоритмах тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Эйрих, Станислав Николаевич

• Эйрих, Станислав Николаевич
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Эйрих, Станислав Николаевич

Оглавление

Введение

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

алгоритмах

Заключение

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

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

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

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

Заключение

Приложение

Литература

Введение диссертации (часть автореферата) на тему «Применение имитационной нормализации в гибридных алгоритмах»

Введение

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

Краткое содержание диссертации

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

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

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

нированные конечные автоматы, состояния, переходы, блок (грид) регулярного языка.

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

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

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

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

В приложении приведен текст программной реализации гибридных алгоритмов и эвристик, применённых в них, для решения задач дискретной оптимизации. Все комплексы программ выполнены на С++ (Microsoft Visual С++, version 6). Для каждого алгоритма и его применения в практических задачах реализована отдельная программа. Эти программы в совокупности дают комплекс программ для решения целого класса задач. К тому же, например для ЗКВ, была реализована программа, которая входит в комплекс и может использоваться отдельно, для обработки входных данных в библиотеке TSPLib.

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

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

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

Система т линейных алгебраических уравнений с п неизвестными - это система уравнений вида

+ «12^2 + *' * + ЩпХп =

+ а<22Яй +----Н й'2п%п = &2

4- й»иг^2 Н— * + Щпп^п — Ьт

Здесь X], х2, ..., хп - неизвестные, которые надо определить, ац, а12, ..., атп - коэффициенты системы - и Ь1} Ь2, ... Ът- свободные члены - предполагаются известными. Индексы коэффициентов (ау) системы обозначают соответственно номера уравнения (г) и неизвестного (/'), при котором стоит этот коэффициент.

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

В силу невырожденности матрицы А существует точное решение х* =А"1 Ь. Задача получения решения СЛАУ сводится к нахожде-

нию . Невязкой [10], соответствующей вектору х, будем называть вектор Лх = Ъ - А х = А(х* - х), где (х* - х) есть ошибка решения.

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

п

(х,у) = ^х!у! (1)

1=1

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

(х,у)А = (Ах,у) = (Х,АГУ) = утАх - хтАту (2)

На основе скалярных произведений введём в Я" векторные нормы |4 = (3) И || х\\2=л1(Ах,х)=^(х,х)а (4) (евклидова норма и А-норма соответственно).

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

IIх ~ 11^ = (А Г А(х ~ х*)' (х ~ х>)) = (А(х ~ х* )>А(Х ~ )) = (Д*) = ||Н1г (5 )

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

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

т

(6)

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

где о.у - коэф. системы, х— решение (неизвестные), Ь, - свободные члены.

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

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

Транспортная задача (задача Монжа - Канторовича) или задача

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

виде:

(7)

Существует много подклассов транспортных задач. Например, с ограничениями по времени и без, статические и динамические, с одним складом и несколькими, в возвратом товара или транспортного средства на склад и без возврата, с ограничением на грузоподъёмность и без него, с одним транспортным средством и с несколькими, с разнородным и однородным товаром [13].

Приведём описание классической транспортной задачи. Однородный товар находится у т поставщиков в объёмах а],а2,...ат. Его необходимо доставить п потребителям в объёмах ЬьЬ2,...Ъп. Известны стоимости перевозки с. единицы груза - от каждого /-го поставщика

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

Требование полностью вывести запасы всех т поставщиков:

п

(8)

м

где Ху- объёмы перевозок (неизвестные), а, - объёмы запасов.

Требование полностью удовлетворить запросы всех п потребителей:

т

1=1

где Ху— объёмы перевозок (неизвестные), - объёмы потребления.

Так как произведение с. ха определяет затраты на перевозку

груза от /-го поставщика у'-му потребителю, то суммарные затраты на

т п

перевозку всех грузов равны ]Г]Ге,7;с;/. По условию задачи требуется

обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид

от п

^ = (И))

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

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

Рисунок 1

На рисунке 1 изображён простой частный случай ЗКВ, описанный в [14].

1

4 5

3

4

ос 6 10 с? 2

6 ;У' 7 о о 15

10 7 X 9 6

5 13 9 ос 11

2 .1 о 6 11 X

Рисунок 2

На рисунке 2 матрица стоимостей для ЗКВ, изображённой на рисунке 1.

Приведём некоторые варианты ЗКВ [54, 87, 95]:

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

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

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

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

^ = I + + + )2 (11)

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

Определение недетерминированных конечных автоматов сформулированы в [24]. Здесь мы приведём только небольшое описание автоматов в виде ориентированных графов. В терминах теории графов:

• каждой дуге соответствует буква конечного алфавита;

• вершины графа помечены для удобства работы с ними.

При этом некоторые вершины отмечены входящими и исходящими стрелками - входы и выходы автомата. Могут присутствовать дуги являющиеся петлями. Пример такого автомата приведён на рисунке 3.

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

Недетерминированным автоматом называют такой автомат, который имеет:

\

Рисунок 3

• либо более одного входа ;

• либо хоть один е-переход;

• либо хотя бы одну вершину, из которой выходит 2 (или более) дуг, помеченных одинаковыми буквами.

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

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

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

Существуют и другие возможные задачи минимизации неде-

терминированных конечных автоматов [91]. Первая возможность -дуговая минимизация автоматов [94]. Вторая - звёздно-высотная минимизация [85]. И много различных возможностей представляет собой минимизация по комбинированным критериям.

/ ч-

I л \

У Ь

1

1

/

Й

V У

Л

- И { 3 ) ,

А-'7 ^ ./ ь

У

V

N .

>и

л \

Рисунок 4а

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

4

0Г

Л ГУ В )

II ^ <е *-> 1

V Л

V__^

У , N

+

' ь ( А ) * О Т /

I_2_I У ч-—Л /

(<)

Ч.

а

ж

> ( "

-ы

О

Л

I

Рисунок 46

На рисунке 46 слева изображён канонический автомат, полученный из исходного (рисунок 4а) путём детерминизации и последующей канонизации (т.е. объединения всех эквивалентных вершин).

Справа на рисунке 46 изображён детерминированный (канонический)

автомат для его зеркального образа.

По этим двум К А строится таблица соответствия вершин автоматов, показанная на рисунке 5 (слева отношения соответствия вершин, справа преобразованная в прямоугольные блоки).

X У X У 2

.4 # # А 1 1 0

В # # В 1 1 1

С # С 0 1 0

Рисунок 5

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

• нет одинаковых строк,

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

• нет ни строк, ни столбцов, содержащих только О, является таблицей соответствия вершин некоторого автомата [20].

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

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

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

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

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

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

X V 2 I.

А 0 1 0 ! I

В 1 0 0 1

С ] 0 I 1

о ! 1 1 1 1 1

Рисунок 6

Пример матрицы на рисунке 6, в которой имеются 5 блоков: а = {А,В,С,Б} X {И}, Ь = {А,С,В} X №,15}, ё = {В,С,О} X {Х,и}, й = {СДЭ} X {Х,г,и} {Б} X {Х,У,г,и}. Для покрытия всех значений

1 данной матрицы достаточно использовать 3 из этих 5 блоков: Ь, и \у.

В описанном выше методе «грубой силы», как и в нашем гибридном методе остается один вопрос, на который сами методы не дают ответа. Как определить допустимость решения программно? Теоретически проверить допустимость просто - взяли набор из 4 блоков и, глядя на матрицу на рисунке 5, определить, покрывают блоки все

элементы 1 или нет. Если все наборы из 4 блоков покрывают, то берём наборы из 3 блоков. Как только нашли набор, не покрывающий все элементы 1, мы останавливаемся. Однако программная реализация нашего «взгляда» получится трудоемкой. Т.к. программе придётся пробегать по матрице большой размерности и хранить в памяти массивы элементов, определяющих покрытие блоком элементов 1. При этом количество массивов будет равно количеству комбинаций блоков в заданном наборе. При больших размерностях их будет большое число, а циклы по этим массивам будут медленными. Поэтому для практического решения задачи необходимо применим некоторых эвристических алгоритмов.

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

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

п т

= (12)

ы М

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

Заключение

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Эйрих, Станислав Николаевич

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

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

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

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

3.5е+006

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

2.5е+006 2е+006

1,5е+006 10+006 500000 ■ 0

О 10000 20000 30000 40000 50000 60000 70000 80000 900СЮ число итарации

Рисунок 14

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

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

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

4 } $ j

0 10 29 30 40 50 60

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

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

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

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

0 45 0.4 Ь 0.35 0.3 0 25 02 Ü 5 0 J

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

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

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

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

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

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

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

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

50

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

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

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

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

Заключение.

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

Список литературы диссертационного исследования кандидат физико-математических наук Эйрих, Станислав Николаевич, 2012 год

Литература

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов - М., Мир, 1979.

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

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

4. Беллман Р., Кал аба Р. Динамическое программирование и современная теория управления. М.: Наука, 1969.

5. Белозёрова А., Мельников Б.. Применение комплекса эвристик в задаче составления схемы нуклидных превращений. - Труды II Всеросс. научной конф. «Методы и средства обработки информации», М., Изд-во МГУ, 2005, с.208-212.

6. Биркгоф Г., Барти Т. Современная прикладная алгебра. - СПб.: Лань, 2005.

7. Брауэр Э. Введение в теорию конечных автоматов. - М.: Радио и связь, 1987.

8. Васильев Ф. Численные методы решения экстремальных задач. -М.: Наука, 1988.

9. Вишневский К.П., Чижиков В.И. Вероятностный полиноминальный алгоритм для решения np-полных задач. - Труды ФОРА, №12, 2007 г.

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

11. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. - М.:

Мир, 1985.

12. Гермейер Ю. Введение в теорию исследования операций. - М.: Наука, 1971.

13. Голыптейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. - М.: Наука, 1969. - 382с.

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

15. Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи. - М.: Мир, 1982.

16. Дейкстра Э. Дисциплина программирования. — М.: Мир, 1978.

17. Дюк В., Самойленко A. Data Mining. - СПб.: Питер, 2001.

18. Елкин Д.И., Тяхти A.C. Искусственный интеллект. Алгоритм имитации отжига. 2008. http ://rain.i fmo. ru/cat/vi ew.php/theory/unsorted/ai-anneal ing-2008/article.pdf

19. Емельянова T.C. Эвристические и метаэвристические методы решения динамической транспортной задачи. // Перспективные информационные технологии и интеллектуальные системы. - Таганрог: Изд-во ТРТУ, 2007. №3(31). - С. 33-43.

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

21. Калашников A.B., Костенко В.А. Параллельный алгоритм имитации отжига simulated annealing для построения многопроцессорных расписаний. - Известия РАН. Теория и системы управления. -№3,2008, С. 133-142

22. Карлин С. Математические методы в теории игр, программирова-

нии и экономике. - М., 1964.

23. Карманов В. Математическое программирование. - М.: Наука, 1975.

24. Карпов Ю. Теория автоматов. - СПб.: Питер, 2002.

25. Ковалев М. Дискретная оптимизация (целочисленное программирование). - М.: УРСС, 2003.

26. Колмогоров А. Теория информации и теория алгоритмов. - М.: Наука, 1987.

27. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности / Хачатуров В. и др. - М.: Наука, 2000.

28. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы - построение и анализ. - М.: МЦНМО, 2004.

29. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978.

30. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. - М.: Энергоатомиздат, 1988.

31. Липпман С. Весь С++. От азов до совершенства. - СПб.: Невский диалект, 2007.

32. Липский В. Комбинаторика для программистов. - М.: Мир, 1988.

33. Люгер Д. Искусственный интеллект - стратегии и методы решения сложных проблем. - М.-СПб-Киев: Вильяме, 2003.

34. Майника Э. Алгоритмы оптимизации на сетях и графах. - М.: Мир, 1981.

35. Мельников. Б. Мультиэвристический подход к задачам дискретной оптимизации. - «Кибернетика и системный анализ» (HAH Украины), 2006, №3, с.32-^2.

36. Мельников Б.Ф., Пивнева C.B., Рогова O.A. Репрезентативность

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

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

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

39. Минский М. Вычисления и автоматы. - М.: Мир, 1971

40. Мину М. Математическое программирование. Теория и алгоритмы. - М.: Наука, 1990.

41. Моисеев Н. Элементы теории оптимальных систем. - М.: Наука, 1975.

42. Ope О. - Графы и их применение. - M.: URSS, 2006.

43. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985.

44. Пойа Дж. Математика и правдоподобные рассуждения. - М., 1975.

45. Полак Э. Численные методы. Единый подход. - М.: Мир, 1974.

46. Поляк Б. Введение в оптимизацию. - М.: Наука, 1988.

47. Протасов В. Максимумы и минимумы в геометрии. (Серия: «Библиотека Математическое просвещение»). - М.: МЦНМО, 2005.

48. Рассел С., Норвиг П. Искусственный интеллект: современный подход. - М.-СПб-Киев: Вильяме, 2006.

49. Рейнгольд Э. Комбинаторные алгоритмы - М.: Мир, 1980.

50. Реклейтие Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике - М.: Мир, 1986.

51. Руднев А.С. Алгоритм имитации отжига для решения задач двумерной прямоугольной упаковки в контейнеры с запрещёнными областями. Дискретн. анализ и исслед. опер., 17:4 (2010), с. 43-66.

52. Самарский А., Михайлов А. Математическое моделирование. -М.: ФИЗМАТЛИТ, 2001.

53. Сачков В. Введение в комбинаторные методы дискретной математики. - М.: Наука, 1982.

54. Сигал И., Иванова А. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмыю. - М.: ФИЗМАТЛИТ, 2003.

55. Современное состояние теории исследования операций / Под ред. Моисеева H. -М.: Наука, 1979.

56. Схрейвер А. Теория линейного и целочисленного программирования. - М.: Мир, 1991.

57. Taxa X. Введение в исследование операций. - М.: Мир, 1988.

58. Уоссермен Ф. Нейрокомпьютерная техника. Теория и практика.-М.: Мир, 1992.

59. Успенский В., Семенов А. Теория алгоритмов: основные открытия и приложения - М.: Наука, 1987.

60. Хаггарти Р. Дискретная математика для программистов - М.: Техносфера, 2003.

61. Харари Ф. Теория графов. - М.: Мир, 1973.

62. Ху Т., Шинг М. Комбинаторные алгоритмы - Нижний Новгород:

Изд-во Нижегородского госуниверситета им. Н.И.Лобачевского, 2004.

63. Шарый С.П. Рандомизированные алгоритмы в интервальной глобальной оптимизации // Сиб. журн. вычисл. математики / РАН. Сиб. отд-ние. - Новосибирск, 2008. - Т. 11, № 4. - С. 457-474.

64. Шень А.. Программирование: теоремы и задачи. - М.: Изд-во МЦНМО, 2004.

65. Шимко П. Оптимальное управление экономическими системами. - СПб.: Бизнесс-пресса, 2004.

66. Эделстейн Г. Интеллектуальные средства анализа, интерпретации и представления данных в информационных хранилищах -СотрШег\¥еек-Москва. 1996. № 16. с. 32-33.

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

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

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

70. Эйрих С.Н. Вариант комбинирования алгоритма имитационной нормализации с эвристическими методами. Математическое и

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

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

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

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

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

75. Эйрих С.Н. Вершинная минимизация недетерминированных конечных автоматов гибридным алгоритмом с применением имитационной нормализации. Материалы Межд. научно-практической конф. «Молодежь и наука: модернизация и инновационное разви-

тие страны». Том 1-Пенза: Изд-во ПГУ, 2011. С. 69-73.

76. Яблонский С. Введение в дискретную математику - М.: Высшая школа, 2006.

77. Ясницкий JI.H. Введение в искусственный интеллект. - М.: Академия, 2005.

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

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

80. Barbosa V., Gafni E. A distributed implementation of simulated annealing// J. of Parallel and Distributed Computing. 1989. P.411-433.

81. Braysy Olli, Gendreau Michel. Route Construction and Local Search Algorithms for the Vehicle Routing Problem with Time Windows. Internal Report STF42 AO 1024, SINTEF Applied Mathematics, 2001.

82. Czech Z.J. Parallel Simulated Annealing for the Delivery Problem// Parallel and Distributed Processing. 2001. Volume of Ninth Euromicro Workshop. P.219 - 226.

83. Gomez G.C. A general interface for distributed and sequential simulated annealing. - Qualifier II Research. Purdue University. 1994.

84. Greening D.R. Parallel simulated annealing techniques. - Emergent computation. 1991,293-306.

85. Hashiguchi K. Algorithms for Determining Relative Star Height and Star Height. - Inform. Comput. No.78 (1987) 124-169.

86. Holland J.N. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. Michigan Press, 1975.

87. Hromkovic J. Algorithmics for Hard Problems. Introduction to Com-

binatorial Optimization, Randomization, Approximation, and Heuristics. - Springer, 2003.

88. Hromkovic J. An Introduction to Automata, Computability, Complexity, Algorithmics, Randomization,Communication and Cryptography. - Springer, 2003.

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

90. Janaki Ram D., Sreenivas T.H., Ganapathy Subramaniam K. Parallel Simulated Annealing Algorithms// J. of parallel and distributed computing. 1996. №37, P.207-212.

91. Jiang T., Ravikumar B. Minimal NFA Problems are Hard. - SIAM Inform. Comput. V.22 (1993) 1117-1141

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

93. Melnikov B. 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.

94. Melnikov B., Melnikova A. Edge-minimization of non-deterministic finite automata. - The Korean Journal of Computational and Applied Mathematics, Vo.8, No.3 (2001) 469^179.

95. Melnikov B., Gumayunov V., Radionov A. Some special heuristics for discrete optimization problems. - 8th International Conference on Enterprise Information Systems, Paphos (Cyprus) (ICEIS-2006), pp. 360-364.

96. Melnikov B., Melnikova E., Moseev A., Radionov A. Some specific heuristics for situation clustering problems. - 1 st International Conference on Software and Data Technologies, Setübal (Portugal)

(ICSOFT-2006), Vol.2, pp.272-279. 97. Polak L. Minimalizations of NFA using the universal automaton / Int. J. Found.Comput. Sci., Vol. 16, No. 5 (2005) 999-1010.