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



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

БОРИСОВСКИЙ Павел Александрович

ИССЛЕДОВАНИЕ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

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

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

Омск - 2005

Работа выполнена в Омском филиале Института математики имени С.Л.Соболева СО РАН.

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

наук, профессор

Колоколов Александр Александрович.

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

наук, профессор

Попков Владимир Константинович, кандидат физико-математических наук, доцент

Кочетов Юрий Андреевич.

Ведущая организация: Институт динамики систем и

теории управления СО РАН

Защита состоится 2005 г. в /У*0 часов на заседа-

нии диссертационного совета Д 003.061.02 в Институте вычислительной математики и математической геофизики СО РАН по адресу: 630090, Новосибирск, пр. Академика Лаврентьева, 6.

С диссертацией можно ознакомиться в библиотеке Института вычислительной математики и математической геофизики СО РАН

Автореферат разослан "Л_" лА^еть 2005 г.

Ученый секретарь диссертационного совета, д.ф.-м.н.

С.Б.Сорокин

общая характеристика работы

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

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

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

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

'Еремеев А.В Разработка и анализ генетических в гибридных алгоритмов для решения задач дискретной оптимизации: Автореф. дис. канд. физ.-мат. наук. - Омск, 2000. - 16 с.

2Мухачева Э.А. Обзор и перспективы развития комбинаторных метопов решения задач раскроя и упаковки // Материалы конф. "Дискретный анализ и исследование операций". - Новосибирск: Изд-во Ин-та математики, 2002. - С.80-87.

3Reeves C.R. Genetic Algorithms for the Operations Researcher// INFORMS Journal on Computing. -1997. - Vol. 9, N 3. - P.231-250.

'Кочетов Ю.А., Младенович H., Хансен П. Локальный поиск в комбинаторной оптимизации- достижения и перспективы // Материалы конф. "Проблемы оптимизации и экономические приложения". -

Омск: Изд-во Наследие. Диалог Сибирь, 2003. - С.43-47. i "Т..".....

J РОС, НАЦИОНАЛЬНАЯ i 1 ВИМИОТЕКА I

6 I С. Петер * 09 W$J

ШИл

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

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

Научна« новизна. В работе проведено теоретическое и экспериментальное исследование наиболее известных эволюционных алгоритмов: генетического алгоритма, алгоритмов (ц, А)-ЕА, (/х 4- А)-ЕА и алгоритма имитации отжига. Рассмотрены свойства алгоритмов в предположении монотонности оператора воспроизведения, проведено теоретическое сравнение производительности различных вычислительных схем. Экспериментально проверена возможность применения теоретических результатов для двух известных задач дискретной оптимизации. Разработан генетический алгоритм для решения задачи о поставках продукции.

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

1. Построены модели, описывающие распределения значений целевой функции решений, найденных на заданной итерации алгоритмов (1, А)-ЕА и (1+1)-ЕА. Указаны условия сходимости к оптимальному решению. Проведены эксперименты для задачи о независимом множестве графа, подтвердившие адекватность построенных моделей в начальной стадии поиска.

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

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

4. Экспериментально установлено преимущество (1+1)-ЕА по сравнению с другими известными ЭА на задаче о наибольшем независимом множестве графа при использовании штрафной функции. Дано обоснование возможности применения теоретических результатов для объяс-

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

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

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

Апробация работы. Результаты диссертации докладывались на Российских конференциях "Дискретный анализ и исследование операций" (Новосибирск, 2002, 2004), XII Всероссийской конференции "Маг тематическое программирование и приложения" (Екатеринбург, 2003), Международном семинаре "The 1-st European Workshop on Evolutionary Computation in Combinatorial Optimization" (Комо, Италия, 2001), Международной конференции "Foundations of Genetic Algorithms /"'(Малага, Испания, 2002), Международном семинаре "The 3-rd European Workshop on Evolutionary Computation in Combinatorial Optimization" (Колчестер, Великобритания, 2003), Международных семинарах "Theory of Evolutionary Algorithms" (Дагштул, Германия, 2002, 2004), Международном семинаре "The 2-nd International Workshop "Discrete Optimization Methods in Production and Logistics" (Омск, 2004), V Международной научно-технической конференции "Динамика систем, механизмов и маг шин" (Омск, 2004), а также на семинарах в Институте математики им. C.JI. Соболева СО РАН, Институте вычислительной математики и математической геофизики СО РАН и в Омском филиале Института математики им. C.JI. Соболева СО РАН.

Публикации. Основные результаты диссертации опубликованы в 10 работах, список которых приведен в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы (98 наименований) и приложения. Общий объем диссертации - 109 страниц. В каждой главе используется своя нумерация параграфов, утверждений, теорем и формул.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В п. 1.1. описаны схемы различных алгоритмов эволюционного типа, таких как генетический алгоритм, алгоритмы (/х, А)-ЕА и (¡л + А)-ЕА, алгоритм имитации отжига.

Пусть задача состоит в максимизации функционала / на множестве допустимых решений D в пространстве X. Будем предполагать, что X конечно, хотя некоторые результаты справедливы и в более общих случаях.

В генетическом алгоритме5 (ГА) решения обычно представляются в виде генотипов - строк, состоящих из генов - символов некоторого алфавита (часто используется алфавит {0,1}). Предполагается, что имеется способ восстановления (декодирования) решения х(д) е X по генотипу д. Генотип вместе с соответствующим ему решением принято называть особью. Для генотипа определена функция пригодности, которая связана с целевой функцией / и служит для дополнительной настройки алгоритмов. Обычно она представлена в виде Ф(р) = ifr{f{x(g))), если x(g) G D, где ф - некоторая возрастающая функция. Для недопустимых решений Ф может действовать как функция штрафа.

В ГА на каждой итерации t хранится набор генотипов - популяция ПО = ...,дтО). Для перехода к следующей популяции сначала из П^ выбираются две родительские особи pi,p2- Выбор осуществляется оператором селекции, который устроен так, что особи с большей пригодностью имеют более высокие шансы быть выбранными. Далее на основе pi и р2 строятся две новые особи с помощью вероятностных операторов кроссинговера и мутации. Под действием кроссинговера путем комбинирования и обмена генов родительских особей формируются два новых генотипа. Затем каждый из потомков подвергается действию оператора

5Holland J. Adaptation in natural and artificial systems. University of Michigan Press, 1975. - 211 p.

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

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

Наиболее простым среди ЭА является алгоритм (1+1)-ЕА, известный также, как (1+1)-эволюционная стратегия,6 или как алгоритм локального поиска с пересчетом при неудачном шаге.7 Популяция данного алгоритма состоит из одной особи. Начальный генотип х^ генерируется случайным образом. На каждой итерации t к текущему генотипу х® применяется оператор мутации: х' = Л4(х^) и далее полагается = х', если Ф(х') > Ф(®Ю), иначе =

Алгоритм имитации отжига можно рассматривать как модификацию (1+1)-ЕА, в которой допускается переход к худшим решениям. Вероятность перехода к х1 при Ф(х') < Ф(х^) составляет р = ехр((Ф(х') — Ф(х^')/т), где г > 0 - параметр, называемый температурой. Как правило, т является убывающей функцией от t.

В п. 1.2 дан краткий обзор некоторых результатов теории эволюционных вычислений. Среди важнейших направлений в теории ЭА можно отметить выявление и объяснение причин успешной (или неудачной в некоторых случаях) работы ЭА на определенных классах задач.

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

6ftechenberg I. Evolutionsstrategie: Optimerung Technischcr Systeme nach Prinzipen der Biologischen Evolution // Stuttgart: Formann-Holzboog Verlag, 1973. - 170 p.

7Растригин Л.А. Статистические методы поиска. - M.: Наука, 1968 - 376 с.

данной работе рассматривается более строгое предположение монотонности операторов построения новых решений.

Методом исследования выступает обычно метод математического моделирования с применением аппарата теории вероятности (к примеру ряд результатов об оценках трудоемкости и вероятности нахождения оптимума был получен с использованием теории цепей Маркова). Надо отметить, что известные модели, как правило, описывают лишь простейшие алгоритмы в применении к задачам простой структуры с заранее известными оптимальными решениями. Тем не менее, данные результаты представляют большой интерес для понимания общих принципов работы ЭА.

В качестве примеров применения ЭА в п. 1.3 и 1.4 приводятся генетические алгоритмы для решения задачи о вершинном покрытии и одной прикладной задачи о поставках продукции. Вершинным покрытием графа G = (V, Е) называется множество С С V, такое, что для любого ребра е = (v\,v2) € Е либо Vi 6 С, либо г>2 € С. Задача вершинного покрытия (ЗВП) состоит в нахождении покрытия С* наименьшей мощности. ЗВП эквивалентна задачам поиска наибольшего независимого множества и наибольшей клики в графе. Данные задачи являются /У Р-трудными, для их решения предложено множество точных и приближенных алгоритмов, в том числе эволюционных.8'9'10

Предложенный ГА основан на использовании жадного кроссинговера, который работает следующим образом. Пусть С\ и Сг - два покрытия. Предполагается, что потомок С содержится во множестве С\ U С*2- При построении С сначала в него включаются все вершины, смежные с некоторыми вершинами из V\(CiUC2), затем с помощью жадного алгоритма решается задача на подграфе, порожденном оставшимися вершинами.

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

8Еремеев A.B., Заозерская Л.А., Колоколов A.A. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискрет, анализ и исслед. операций - 2000 - Сер. 2. Т. 7, N 2. С.22-46.

'Нечспуренко М.И., Попков В.К., Майкагашев С.М. и др. Алгоритмы и программы решения заоач на графах и сетях. - Новосибирск, Наука (Сибирское отделение), 1990. - 515 с.

10Kuznetsova A., Strekalovsky A.S. On solving the maximum clique problem // J. Global Optim. - 2001. - Vol. 21. N. 3. - P. 265-288.

нительные ограничения на объемы поставок. Пусть количество поставщиков равно п, а количество потребителей - т. Обозначим через М, максимальный объем продукции, который способен предоставить поставщик i, Aj - объем продукции, необходимый потребителю j, хij - объем поставки от поставщика г потребителю j (г = 1,...,п, j = 1, ...,тп). Стоимость поставки задана функцией fey(xy), которая равна нулю при xtj — 0, и kij(xij) = atJ + ctjXl0 иначе, где ау > 0 и q7 > 0 - коэффициенты постоянных и переменных затрат. Кроме того, если поставка осуществляется, то ее объем должен быть не меньше заданного значения ту. Требуется найти план перевозок, минимизирующий суммарные затраты. Модель дискретного программирования данной задачи выглядит следующим образом:

п m

£ £ min

«=ij=i

m _

]ГХу < Mi, i=l,n,

3=1

n

£ xtj ~ Д/> J = i» mi

i=1

x,j € {0} U [mtJ, M,], г = T7H, j = l,m.

Указанная задача является NP-трудной. Для ее решения в данной работе предложен генетический алгоритм, в котором генотипы представлены в виде перестановок потребителей. Для построения решения заг-дачи по заданному генотипу разработана процедура декодирования, в которой последовательно решается задача о поставках для каждого потребителя в отдельности в порядке, заданном перестановкой. Задача с одним потребителем решается с помощью жадной эвристики. Проведены вычислительные эксперименты на тестовых задачах, которые показали высокое качество решений, найденных генетическим алгоритмом. Результаты первой главы опубликованы в работах [2,3].

Вторая глава посвящена моделированию и теоретическому сравнению ЭА. В п. 2.1 приводится описание используемой модели.11 Пусть заданы d + 1 линий уровня функции пригодности таким образом, что

11Eremeev A.V. Modeling and Analyste of Genetic Algorithm with Tournament Selection //In Proc. of The 4th Artificiel Evolution Conférence. - Springer Verlag. LNCS, Vol. 1829. 2000. - P.84-95.

О = Ф0 < Фх < Фг - . < Фй- Каждой линии уровня сопоставим подмножество Н{ — {д е X : Ф(д) > Ф^}, г = 0,...,£?. Предполагается, что для произвольного решения д € Нг\Щ+1, г = 0,...,<1 известны оценки вероятностей перехода в Н] под действием мутации, т.е. а13 < Р{М{д) € Я;} < = 1,..., <1. Оператор мутации будем называть монотонным, если верхние и нижние оценки совпадают и матрица (ау) монотонна, т.е. < ау для всех ъ,з = 1,

В п. 2.2 получены оценки вероятностей достижения заданного уровня для алгоритма (1,А)-ЕА. Приведем сначала его формальную схему. Пусть задано начальное решение € X. На итерации í к текущему решению Ь^ оператор М применяется Л раз, и лучший из полученных потомков становится текущим решением на следующей итерации. Пусть = Р{Ь® € Н,},] = 1, ...,«*, тогда:

Р?} > 1 ~ (1 - <*о;)А + ¿((1 - сц.^ - (1 - а„Ы*~1)- (1) »=1

Здесь же получены выражения для предельных значений р'р при £ —> оо, указано условие сходимости, а также показано, что при монотонном операторе мутации (1,А)-ЕА не уступает одному из простых вариантов ГА. В п. 2.3 получены аналогичные оценки для (1+1)-ЕА. Пусть = Р{х® С = 1, ...Д тогда:

9? > <*<У + Е К' - о.-и)«,^4 + (1 - (2)

«=1

Показано, что если ащ > 0 для всех з = 1,..., <1 и матрица (оу) монотонна, то д^ —* 1 при < —+ оо. Также получено выражение для среднего времени первого достижения множества для з = 1,..., <1

В п. 2.4 сформулирован и доказан один из основных результатов данной работы (теорема о сравнении), в котором показало превосходство (1+1)-ЕА над другими эволюционными алгоритмами при выполнении условий монотонности или доминирования. В данном разделе не используется предположения о дискретности пространства решений X. Будем считать, что X С К" - борелевское множество (И - множество вещественных чисел), и функция пригодности Ф измерима.

Определим оператор воспроизведения Ц.{хх,...,хг) как вероятностный алгоритм, который получает на вход г родительских решений и

случайным образом строит s решений-потомков, распределение которых зависит от входных решений и данных задачи.

Рассмотрим общую схему эволюционного алгоритма БА, основанного на операторе И. Дано множество начальных решений а^0,1^,..., и на каждой итерации t набор решений строится применением

Т1(х1, ...,хг), где каждое хк е X, к = 1, ...,г найдено на каком-либо из предыдущих шагов. Иначе говоря, хк € Л^"1^, где

A(t-i) = {а(о,0 :l = lf ; Nj у |a(rj) .T = h >t _ j j = 1( ; sj

Легко показать, что большинство эволюционных алгоритмов, таких как генетические алгоритмы, эволюционные стратегии (д, А)-БА и (fj, 4- А)-ЕА, методы генетического программирования12 и многие другие удовлетворяют этой схеме.

Пусть 1Zmax(xl, •,хг) обозначает наилучшего из s потомков, полученных применением И к набору х1,..., хг (если таких потомков оказалось несколько, то выбирается равновероятно один из них). Будем называть оператор 1Z монотонным, если для любых наборов решений х1,..., хг и у1,...,уг таких, что Ф(х*) < Ф(уг),..., Ф(хг) < Ф(уг), следующее условие выполняется для всех (р € R:

Р {Ф(ЯтЖ,х")) > ip) < Р {Ф(Птах(у\..., /)) > у>}.

Оператору 72. сопоставим оператор мутации М.% так, что Мп(х) = Итах{х, ...,х), если Ф(71таХ(х,..., х)) > Ф(х), и Мъ(х) = X иначе.

Пусть а^ обозначает лучшее решение из множества Л^ (напомним, что х® обозначает текущее решение на итерации t алгоритма (1+1)-ЕА).

Теорема 1 (о сравнении). Пусть монотонный оператор TL используется в алгоритме ЕА, соответствующий ему оператор Мц применяется в алгоритме (1+1)-ЕА. Пусть также работа (1ч-1)-ЕА начинается с генотипа х^ такого, что Ф(х^) > max Ф(а(°''>). Тогда для любого t > 0 и всех <р € R

Р{Ф(5(4)) ><р}< Р{Ф(х«) > 9?}.

I2Koza J.R. Genetic programming: On the programming of computers by means of natural selection. MT Press. 1992. - 840 p.

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

Будем говорить, что оператор воспроизведения 1Z доминируется оператором мутации М, если для любого набора генотипов а1,..., ат и любого х € X таких, что Ф(х) > max $(afc), следующее условие выполняется

к=1,.. ,г

для всех tp € R:

Р{Ф('ЯтаХ(а1,...,аГ)) > ц>} < Р{Ф(М(х) > <р}.

Следующая теорема доказана для дискретного случая. Будем предполагать, что функция пригодности принимает конечное число значений Ф0, ...,Ф<j, определяющих ее линии уровня.

Теорема 2 Утверждение теоремы 1 верно, если оператор 1Z (возможно немонотонный) доминируетсл оператором мутации М., который используется в (1+1)-ЕА.

Данный результат позволяет получать обобщения оценок времени поиска оптимального решения. В качестве примера рассматривается задача сортировки: требуется найти перестановку тг* элементов массива (zi, ...,хп) так, чтобы 2^.(1) < 2V(2) < ... < Предполагается, что

все элементы (xi,..., хп) различны. Задачу можно сформулировать как максимизацию функции Н AM (тг) = |{г : ж(г) = тт*(г)}|.

Рассмотрим оператор мутации М.х следующего вида: случайно выбираются две различные позиции i,j € {1, ...,n}, и элементы ж(г) и w(j) меняются местами. Данная процедура повторяется k + 1 раз, где к -случайная величина с распределением Пуассона с параметром А = 1.

Показано,13 что среднее время поиска оптимума алгоритмом (1+1)-ЕА с оператором Мх составляет Q(n2lnn). С помощью теоремы 2 нижнюю оценку можно распространить на все ЭА, использующие Мх в качестве оператора воспроизведения.

l3Scharnow J., Tinnefeid К., Wegener I. The analysis of evolutionary algorithms on sorting and shortest paths problems // Journ. Math. Mod. and Alg. 2004. V 3. - P.349-366.

В п. 2.5 с точки зрения теории сложности рассмотрены вероятностные характеристики монотонного оператора мутации при решении ЫР-трудных задач. Пусть Ртах ~ некоторая массовая задача максимизации, х - индивидуальная задача из Ртах с целевой функцией Фх, оптимальное значение которой равно Ф*, |х| - длина входа. Классом ВРР называется класс задач распознавания для которых существует полиномиальный вероятностный алгоритм А такой, что:

1) для всех примеров с ответом "да" Р{А возвращает "да"} > 2/3.

2) для всех примеров с ответом "нет" Р{А возвращает "нет"} >2/3.

Для заданной функции г : —> [1,оо) назовем задачей аппроксимации Ртах с оценкой г задачу нахождения такого решения д, что Фх(д) > Ф*/г(|х|) для любого х из Ртах■ Пусть задача аппроксимации РГПах с оценкой г Л/Р-трудна, но существует полиномиальный алгоритм для решения задачи аппроксимации Ртах с оценкой г'.

Теорема 3 Если ЫР % ВРР, то не существует полиномиального оператора мутации с монотонными нижними оценками, удовлетворяющими ау > 1/ро1у(\х\) при Ф* < ФФ] > Ф*/г, для некоторого полинома ро1у(\х\) и произвольной индивидуальной задачи х из Ртах.

Предположение ЫР ВРР широко используется в качестве рабочей гипотезы в теории сложности.

Результаты главы 2 опубликованы в работах [1,4-6,8,9].

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

В п. 3.1 дана формулировка задачи о независимом множестве (ЗНМ), описан способ представления решений и вычисления функции пригодности. Пусть задан граф С=(У,Е), где V = {г^,..., ьп} - множество вершин, Е С V х V - множество ребер. Независимым множеством называется множество попарно несмежных вершин, т. е. 5 С V такое, что для всех VI, V] € в выполняется (и,, г^) ^ Е, где 6 {1, ...,п}. Требуется найти независимое множество максимальной мощности.

В алгоритмах используется двоичное представление решений, где каждому генотипу х 6 (0,1}п ставится в соответствие множество 5(х) = {и* | х* = 1, к € {1, ...,п}}. Функция пригодности включает в

себя штраф, назначаемый каждому недопустимому решению:14 Ф0(я) = £ Xк- Е aXiXj.

к=1 (v„Vj)eE J

В п. 3.2 приводится исследование влияния выбора величины а на производительность эволюционных алгоритмов. Для этого был проведен эксперимент для ГА и (1 + 1)-ЕА на задачах из электронной библиотеки DIMACS (http://dimacs.rutgers.edu) и случайно сгенерированных графах с изменением значения а от 1 до 100. Было замечено, что значения аф\ дают примерно одинаковые результаты, а при а = 1 происходит значительное улучшение работы обоих алгоритмов. Данный эффект может быть объяснен тем, что при а. — 1 возникают большие "плато", т.е. подмножества решений с одинаковым значением пригодности.

В п. 3.3 приводятся результаты эксперимента по применению алгоритмов ГА, (/i+A)-EA и имитации отжига к тестовым задачам из библиотеки DIMACS. Целью эксперимента было выявить наиболее подходящие вычислительные схемы в зависимости от выбора величины штрафа а. Сравнение проводилось для двух вариантов: при а = 1 и а = 100. В ходе эксперимента наилучшие результаты были получены алгоритмами, в которых популяция состоит из одной пробной точки: (1+1)-ЕА и алгоритмом имитации отжига. При а — 1 алгоритм (1+1)-ЕА показал заметное превосходство над остальными алгоритмами для всех тестовых задач, за исключением специально предложенного семейства ЗНМ на двудольных графах. Вопрос о связи данного наблюдения с утверждением теоремы о сравнении представляет большой интерес и рассматривается в следующем разделе.

В п. 3.4 проведен эксперимент для исследования соответствия теоретических результатов экспериментальным данным. Первый этап эксперимента заключался в оценке переходных вероятностей оператора мутации. Пусть х - некоторое случайное решение. Введем условную вероятность 7У = Р{Ф(Х(х)) > j | Ф(х) = г'}. Статистические оценки значений 7ц для некоторых тестовых задач из DIMACS были получены путем последовательного генерирования случайных решений х и подсчетом количества исходов, в которых Ф(э:) = i и Ф(М(х)) > j. При этом было замечено выполнение условия монотонности матрицы (7у),

"Bäck, Th , Khuri, S. An Evolutionary Heuristic for the Maximum Independent Set Problem //In Proo. First IEEE Conference on Evolutionary Computation, IEEE Press. 1994. - P. 531-535.

т.е. 7»-ij < 7tj для всех i,j. Подчеркивая случайный характер решения х, будем называть это свойство монотонностью в среднем.

На втором этапе эксперимента проводилось сравнение наблюдаемого поведения алгоритма (1+1)-ЕА и его теоретической модели. Теоретическая оценка заключалась в вычислении последовательности векторов и т.д. по формулам (2), где в качестве atJ использовались 7У. По вектору находилась средняя пригодность £?[Ф(х^)]. Для получения экспериментальных оценок было произведено 400 запусков (1+1)-ЕА так, что на каждой итерации t отмечалось значение пригодности, которое затем усреднялось. Аналогичное исследование проведено также для алгоритма (1,2)-ЕА с использованием формул (1).

Эксперименты показали хорошее соответствие теоретических моделей реальному поведению алгоритмов на начальной стадии поиска, когда значения функции пригодности найденных решений невелики. Это дает основание утверждать, что в начале поиска условие монотонности можно с большой степенью точности заменить на монотонность в среднем, и превосходство (1+1)-ЕА можно объяснить с помощью теоремы о сравнении. На конечной стадии такого заключения сделать нельзя, тем не менее, было замечено, что (1+1)-ЕА показывает лучшие результаты, когда с помощью мутации можно с большой вероятностью переходить к решениям с тем же значением функции пригодности.

В п. 3.5 проведено аналогичное п. 3.3 сравнение алгоритмов на задаче выполнимости логической формулы. Наилучшие решения получены алгоритмами (1+1)-ЕА и имитации отжига, как и для задачи о независимом множестве при а = 1. Это может быть объяснено тем, что задачи обладают похожими свойствами, а именно, небольшим количеством значений целевой функции, и, соответственно, наличием обширных "плато" - множеств решений одного уровня. Результаты главы 3 опубликованы в [7,10].

Автор выражает благодарность A.A. Колоколову и A.B. Еремееву за помощь в работе над диссертацией. Работа выполнена при частичной поддержке РГНФ (проект 04-02-00238а) и INTAS (проект 03-51-5501).

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ

[1] Борисовский П.А. Сравнение и оценка трудоемкости некоторых эволюционных алгоритмов: Препринт. - Омск: "Полиграфический центр КАН", 2005. - 12с.

[2] Борисовский П. А. Генетические алгоритмы для задачи о поставках продукции // Материалы V Междунар. науч.-техн. конф. "Динамика систем, механизмов и машин". - Омск: Изд-во ОмГТУ, 2004, Кн. 2. - С.255-258

[3] Борисовский П.А. Разработка генетического алгоритма для задачи о вершинном покрытии // Тезисы докладов XXIII научной студенческой конференции. - Омск: ОмГУ, 1999. - С.7-8.

[4] Борисовский П.А., Еремеев A.B. О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика. N3, 2004. - С.3-9.

[5] Борисовский П.А., Еремеев A.B. Об одном алгоритме случайного поиска // Материалы конф. "Дискретный анализ и исследование операций". - Новосибирск: Изд-во Ин-та математики, 2002. - С.225.

[6] Борисовский П.А., Еремеев A.B. Использование стохастического упорядочения для сравнения эволюционных алгоритмов с одним алгоритмом случайного поиска // Материалы конф. "Дискретный анализ и исследование операций". - Новосибирск: Изд-во Ин-та математики, 2004. - С.180.

[7] Борисовский П.А., Еремеев A.B., Заволовская М.С. Экспериментальное исследование двух эволюционных алгоритмов для задачи о независимом множестве // Информационный бюллетень Ассоциации математического программирования. 10. - Екатеринбург: УрО РАН, 2003. - С.52-53.

[8] Borisovsky P.A., Eremeev A.V. On Performance Estimates for Two Evolutionary Algorithms // In E.J.W.Boers et al. (Eds.) Applications of Evolutionary Computing: Proceedings of Evo Workshops 2001. -Springer Verlag, LNCS. - 2001. - Vol. 2037, - P.161-171.

[9] Borisovsky P.A., Eremeev A.V. A Study on Performance of the (1+1)-Evolutionary Algorithm // In K. De Jong, R. Poli, and J. Rowe (Eds.) Foundations of Genetic Algorithms 7. San Francisco: Morgan Kaufmann. 2003. - P.271-287.

[10] Borisovsky P.A., Zavolovskaya M.S. Experimental Comparison of Two Evolutionary Algorithms for the Independent Set Problem // In S.Cagnoni et al. (Eds.) Applications of evolutionary computing: Proc. of EvoWorkshops 2003. Springer Verlag. LNCS, V. 2611. 2003. - P. 154-164.

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

Подписано в печать2?.о/.tbb5" Формат 60 x 84/16. Бумага офсетная. Усл. печ. n.1,Q Уч.-изд. n.1J. Тираж 100 экз. Заказ 3.2.

Отпечатало в "Полиграфическом центре К АН" 644050, г. Омск, пр. Мира, д.32, к.11 тел.: (3812) 65-47-31 Лицензия ПЛД 58-47 от 21.04.1997.

if

3

^15 7 5 6

РНБ Русский фонд

2006-4 19579

Введение.

Глава 1. Эволюционные методы вычислений и некоторые

Диссертация посвящена разработке, моделированию и сравнению различных эволюционных алгоритмов для решения задач дискретной оптимизации. Эволюционные алгоритмы (ЭА) - сравнительно новые эвристические методы поиска, которые успешно применяются при решении оптимизационных задач различных типов. В основе ЭА лежат элементы теории эволюции Ч. Дарвина [16], такие как наследственность, изменчивость и отбор. Многие термины, используемые при описании ЭА (особь, мутация, кроссинговер и др.), заимствованы из биологии, и обозначают элементы алгоритма, сходные с аналогичными объектами и процессами в природе.

Область практического применения ЭА включает в себя задачи планирования и размещения производства [14,82], управления потоками продукции [62,96], составления расписаний [98], раскроя и упаковки [29], проектирования автоматических производственных линий [59] и многие другие [12,17,65]. Известно большое количество различных реализаций ЭА для решения классических задач дискретной оптимизации, таких как задача целочисленного линейного программирования [18,64], задача коммивояжера [68], задача о выполнимости логической формулы [70], задачи о покрытии и упаковке множеств [43,45,49] и т.д.

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

I ' , I * * ко реализуется программно, хотя, несомненно, связан с большими вычислительными затратами. Появление в последнее время доступных компьютеров высокой скорости вычислений и с большим объемом памяти позволило преодолеть эту трудность, благодаря чему популярность ЭА значительно возросла.

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

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

В области эволюционных алгоритмов можно выделить два направления: теоретическое и экспериментальное. Теоретические исследования ЭА направлены в основном на построение математических моделей различных алгоритмов, исходя из которых выдаются рекомендации по выбору тех или иных вычислительных схем и настройке внутренних параметров, а также вычисляются оценки точности и скорости работы алгоритмов [52,54,63,74,77,87,91,92]. В рамках экспериментального направления разрабатываются алгоритмы, предназначенные для решения прикладных задач. Особое место здесь занимают способы гибридизации ЭА, методов локального поиска и алгоритмов, разработанных для решения конкретного типа задач с учетом их специфики [29,34,45,49,59,64,98]. Вопросы о сравнении алгоритмов и настройке параметров решаются путем вычислительных экспериментов. Важную роль здесь играет создание общедоступных библиотек тестовых задач, размещенных в сети Интернет, которые позволяют исследователю сравнивать свои результаты с работами других авторов. В качестве примеров можно привести проект DIMACS Challenge II [75] (http://dimacs.rutgers.edu), библиотеку OR Library [48] (http://mscmga.ms.ic.ac.uk/infoMtm1), библиотеку тестовых задач Института математики им. C.JI. Соболева [13] (http://math.nsc.ru/AP/benchmarks/).

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

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

В диссертации построены модели для эволюционных алгоритмов (1,А)-ЕА и (1+1)-ЕА и проведены эксперименты по проверке адекватности построенных моделей. Рассмотрено введенное в [63] условие монотонности оператора воспроизведения, а также более общее условие доминирования. Показано, что при выполнении этих условий алгоритм (1+1)-ЕА обладает наилучшими вероятностными характеристиками среди всех ЭА. Предложено обобщение известной штрафной функции, используемой при решении задачи о независимом множестве графа с помощью генетических алгоритмов и указано наилучшее значение величины штрафа. Экспериментально установлено преимущество алгоритма (1+1)-ЕА по сравнению с другими наиболее известными ЭА на задаче о независимом множестве графа и проведено исследование соответствия теоретических результатов экспериментальным данным. Предложен и реализован генетический алгоритм для задачи о поставках продукции, основанный на использовании жадной эвристики. Проведен вычислительный эксперимент.

Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. В первой главе приведены схемы различных алгоритмов эволюционного типа, таких как имитация отжига, генетический алгоритм, алгоритмы (//, А)-ЕА и (/z + А)-ЕА, показана их связь с алгоритмами локального поиска. Дан краткий обзор некоторых классических результатов теории эволюционных вычислений, имеющих отношение к вопросам, обсуждаемым в данной работе: теорема об эквивалентности алгоритмов поиска (известная в англоязычной литературе как теорема "no free lunch"), моделирование генетического алгоритма и (1+1)-ЕА с помощью цепей Маркова, исследование метрических свойств пространства поиска. В качестве примеров практического применения ЭА приводятся генетические алгоритмы для решения классической задачи о вершинном покрытии графа и одной прикладной задачи о поставках продукции. Проведены вычислительные эксперименты, которые показали хорошую производительность алго

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

1. Построены модели, описывающие распределения значений целевой функции решений, найденных на заданной итерации алгоритмов (1,А)-ЕА и (1+1)-ЕА. Указаны условия сходимости к оптимальному решению. Проведены вычислительные эксперименты для задачи о независимом множестве графа, подтвердившие адекватность построенных моделей в начальной стадии процесса поиска.

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

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

4. Экспериментально установлено преимущество (1+1)-ЕА по сравнению с другими известными ЭА на задаче о независимом множестве графа при использовании штрафной функции. Дано обоснование возможности применения теоретических результатов для объяснения экспериментальных наблюдений. Кроме того, указано наилучшее значение коэффициента при штрафной функции.

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

Заключение

В работе проведено теоретическое и экспериментальное исследование наиболее известных эволюционных алгоритмов: генетического алгоритма, алгоритма имитации отжига и алгоритмов (/г, А)-ЕА, (/ч + А)-ЕА. Рассмотрено поведение алгоритмов при выполнении условия монотонности оператора воспроизведения, сформулировано более общее условие доминирования. Проведен вычислительный эксперимент с различными эволюционными алгоритмами на задачах о независимом множестве графа и выполнимости логической формулы. Разработан генетический алгоритм для решения одной прикладной задачи о поставках продукции.

1. Альсведе Р., Вегенер И. Задачи поиска. М.: Мир, 1982. - 368 с.

2. Бахтин А.Б., Колоколов А.А., Коробкова З.В. Дискретные задачи производственно-транспортного типа. Новосибирск: Наука, 1978. - 167 с.

3. Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. - 316 с.

4. Борисовский П.А. Сравнение и оценка трудоемкости некоторых эволюционных алгоритмов: Препринт. Омск: "Полиграфический центр КАН", 2005. - 12с.

5. Борисовский П.А. Генетические алгоритмы для задачи о поставках продукции // Материалы V Междунар. науч.-техн. конф. "Динамика систем, механизмов и машин". Омск: Изд-во ОмГТУ, 2004, Кн. 2. - С.255-258

6. Борисовский П.А. Разработка генетического алгоритма для задачи о вершинном покрытии // Тезисы докладов XXIII научной студенческой конференции.-Омск: ОмГУ, 1999. С.7-8.

7. Борисовский П.А., Еремеев А.В. О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика. N2, 2004. С.3-9.

8. Борисовский П.А., Еремеев А.В. Об одном алгоритме случайного поиска // Материалы конф. "Дискретный анализ и исследование операций". Новосибирск: Изд-во Ин-та математики, 2002. - С.225.

9. Боровков А.А. Теория вероятностей. М.: Наука, - 1986. - 431 с.

10. Вороновский Г.К., Махотило К.В., Петрашев С.Н., Сергеев С.А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности // Харьков: ОСНОВА, 1997. -112 с.

11. Гончаров Е.Н., Иваненко Д.А., Кочетов Ю.А., Кочетова Н.А. Электронная библиотека "Дискретные задачи размещения" // Труды Байкальской международной конференции, Иркутск, 2001, Т. 1. С. 132-137.

12. Гончаров Е.Н., Кочетов Ю.А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискретный анализ и исследование операций, Серия 2, 9(2), 2002. -С.13-30.

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

14. Дарвин Ч. Происхождение видов. М., JL: ОГИЗ: Сельхозгиз, 1937. - 608 с.

15. Еремеев А.В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации: Авто-реф. дис. канд. физ.-мат. наук. Омск, 2000. - 16 с.

16. Еремеев А.В., Заозерская J1.A., Колоколов А.А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискретный анализ и исследование операций. Сер. 2. 2000. Т. 7, N 2. С.22-46.

17. Заозерская J1.A. Алгоритм ветвей и границ для решения одной задачи о поставках продукции // Материалы конференции "Проблемы оптимизации и экономические приложения". Омск, Изд-во Наследие. Диалог Сибирь, 2003. - С.88.

18. Зыков А.А. Основы теории графов. М.: Наука, - 1987. - 384 с.

19. Колоколов А.А. Методы дискретной оптимизации // Учебное пособие. Омск: ОмГУ, 1984. - 75 с.

20. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журн. исслед. операций. -Новосибирск. 1994. -T.I, N.2. - С. 18-39. - Омск: ОмГУ, 1992. -С.67-93.

21. Колоколов А.А. Ярош А.В. Некоторые обобщения задачи максимальной выполнимости и их приложения // Информационный бюллетень Ассоциации математического программирования. 10. Екатеринбург: УрО РАН, 2003. - С.151-152.

22. Кочетов Ю.А., Младенович Н., Хансен П. Локальный поиск в комбинаторной оптимизации: достижения и перспективы // Материалы конференции "Проблемы оптимизации и экономические приложения". Омск, Изд-во Наследие. Диалог Сибирь, 2003. - С.43-47.

23. Кочетов Ю.А., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. Сер. 2, 2003, Т. 10, N 1, С. 11-43.

24. Крамер Г. Математические методы статистики. М.: Мир, 1975. - 648 с.

25. Леванова Т.В., Лореш М.А. Алгоритмы муравьиной колонии и имитации отжига для задачи о р-медиане // Автоматика и телемеханика, 3, 2004.- С.80-88.

26. Мухачева Э.А. Обзор и перспективы развития комбинаторных методов решения задач раскроя и упаковки // Материалы конф. "Дискретный анализ и исследование операций". Новосибирск: Изд-во Ин-та математики, 2002. - С.80-87.

27. Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях. Новосибирск, Наука (Сибирское отделение), 1990. - 515 с.

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

29. Растригин Л.А. Статистические методы поиска. М.: Наука, 1968. - 376 с.

30. Ширяев А.Н. Вероятность. М.: Наука, 1980. - 576 с.

31. Aggarwal C.C., Orlin J.B., Tai R.P. An Optimized Crossover for Maximum Independent Set // Operations Research. 1997. -Vol.45. - P.225-234.

32. Aldous D., Vazirani U.U."Go with the Winners" Algorithms // Proc. IEEE Symposium on Foundations of Computer Science. 1994. P.492-501.

33. Altenberg, L.: The evolution of evolvability in genetic programming // In К. E. Kinnear (ed.) Advances in Genetic Programming. MIT Press, Cambridge, MA. 1994. P. 47-74

34. Altenberg L. Fitness distance correlation analysis: an instructive counterexample // In T. Back (ed.) Proc. of the Seventh International Conference on Genetic Algorithms (ICGA97), San Francisco: Morgan Kaufmann. 1997. P. 57-64.

35. Altenberg, L.: The schema theorem and Price's theorem // In D. Whitley and M. Vose (eds.) Foundations of Genetic Algorithms 3, San Francisco: Morgan Kaufmann. 1995. P. 23-49.

36. Angel E., Zissimopolous V., On the classification of NP-complete problems in term of their correlation coefficient // Discrete Applied Mathematics, 2000. - Vol. 99. - P.261-277.

37. Arora S., Lund C. Hardness of approximations //In S.D.Hochbaum (ed.) Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1995. - P.399-446.

38. Ausiello G., Protasi M. Local search, reducibility and approximabi-lity of NP-optimization problems // Information Processing Letters, Vol. 54. 1995. P.73-79.

39. Back Т. Evolution Strategies: Ail Alternative Evolutionary Algorithm // In J.M. Alliot et al (eds.) Artificial Evolution. -Springer Verlag, LNCS. 1995. - Vol. 1063, - P.3-20.

40. Back Т., Khuri S. An Evolutionary Heuristic for the Minimum Vertex Cover Problem //In J. Hopf (ed.) Genetic Algorithms within the Framework of Evolutionary Computation. Max Planck Institut fur Informatik, Saarbrucken, 1994. - P. 86-90.

41. Back Т., Schwefel H.-P. An overview of evolutionary algorithms for parameter optimization // Evolutionary Computation, 1993. - Vol. 1, N 1, - P. 1-23.

42. Balas E., Niehaus W. Optimized Crossover-Based Genetic Algorithms for the Maximum Cardinality and Maximum Weight Clique Problems // Journ. of Heuristics. 1998. - Vol. 4, N 4, -P.107-122.

43. Balas E., Niehaus W. A Max-Flow Based Procedure for Finding Heavy Cliques in Vertex-Weighted Graphs // MSRR No. 612. -GSIA, Carnegie-Melon University. 1996. P.29-53.

44. Batitti R., Protasi M. Reactive local search for the maximum clique problem // Algorithmica, 2001. - Vol. 29, N. 4. - P. 610-637.

45. Beasley J.E. OR-Library: Distributing Test Problems by Electronic Mail // J. Oper. Res. Soc. 1990. - Vol. 41, N 11. - P.1069-1072.

46. Beasley J.E., Chu P.C. A Genetic Algorithm for the Set Covering Problem // European J. Oper. Res. 1996. - Vol. 94, N 2. - P.394-404.

47. Boese K.D., Kahng А.В., Muddu S. A new adaptive multy-start technique for combinatorial dlobal optimization // Oper. Res. Lett. 1994. - Vol. 16, N.2. - P.101-114.

48. Bomze I. M., Budinich M., Pardalos P. M., Pelillo M. The maximum clique problem //In D.-Z. Du and P. M. Pardalos (eds) Handbook of Combinatorial Optimization. Dordrecht: Kluwer. 1999. - Suppl. Vol. A. - P. 1-74.

49. Borisovsky P.A., Eremeev A.V. On Performance Estimates for Two Evolutionary Algorithms // In E.J.W.Boers et al. (Eds.) Applications of evolutionary computing: Proceedings of EvoWorkshops 2001. Springer Verlag, LNCS. - 2001. - Vol. 2037, - P.161-171.

50. Borisovsky P.A., Eremeev A.V. Comparing Evolutionary Algorithms to the (1+1)-EA by Means of Stochastic Ordering // Wide materials of Dagstuhl Seminar "Theory of Evolutionary Algorithms". February 2004. (http://www.dagstuhl.de/04081/ Talks/).

51. Borisovsky P.A., Eremeev A.V. A Study on Performance of the (l+l)-Evolutionary Algorithm // In K. De Jong, R. Poli, and J. Rowe (eds.) Foundations of Genetic Algorithms 7. San Francisco: Morgan Kaufmann. 2003. P.271-287.

52. Chauhan S.S., Eremeev A.V., Kolokolov A.A., Servakh V.V. On Solving Concave Cost Supply management problem with single manufacturing unit. // Proc. of Production System Design, Supply Chain Management and Logistics Conf. Poland, 2002. P. 147-154.

53. Chauhan S.S., Proth J.-M. The Concave Cost Supply Problem // European J. Oper. Res. 2003. V. 148. N. 2. P. 374-383.

54. Daley D.J. Stochastically monotone Markov chains // Z. Wahrscheinlickeitstheorie und Verw. Gebiete, 10,1968. P.307-317.

55. Dolgui A., Eremeev A., Kolokolov A., Sigaev V. A genetic algorithm for the allocation of buffer storage capacities in a production line with unreliable machines // Journal of Mathematical Modelling and Algorithms, 2002. Vol. 1. - P. 89-104.

56. Dorigo M., Di Caro G. The ant colony optimization meta-heuristic // In D. Corne at al.(eds.) New ideas in optimization McGraw Hill, UK, 1999. P. 11-32.

57. Droste S., Jansen Т., Tinnefeld K., Wegener I. A new framework for the valuation of algorithms for black-box optimisation //In K. De Jong, R. Poli, and J. Rowe (eds.) Foundations of Genetic Algorithms 7. San Francisco: Morgan Kaufmann. 2003. P. 197214.

58. Eckert C., Gottlieb J. Direct Representation and Variation Operators for the Fixed Charge Transportation Problem // Proc. of Parallel Problem Solving from Nature (PPSN VII), Springer, LNCS 2439, 2002. P. 54-63.

59. Eremeev A.V. Modeling and Analysis of Genetic Algorithm with Tournament Selection // Proc. of The 4th Artificial Evolution Conference. Dunkerque, 1999. - P.215-226.

60. Eremeev A.V., Kolokolov A.A. On Some Genetic and L-class Enumeration Algorithms in Integer Programming // Proc. of the First International Conference on Evolutionary Computation and Its Applications. Moscow, 1996. - P.297-303.

61. Fuchs MM. An evolutionary approach to support web page design // Proc. 2000 Congress on Evolutionary Computation (CEC-2000). IEEE Press, Piscataway, NJ, 2000. - P. 1312-1319.

62. Glover F., Laguna M. Tabu Search //In C.Reeves (ed.) Modern heuristic techniques for combinatorial problems. Blackwell, Oxford, UK, 1993. - P. 70-141.

63. Goldberg D.E., Deb K. (1991). A comparative study of selection schemes used in genetic algorithms //In G.Rawlins (ed.) Foundations of Genetic Algorithms. San Mateo: Morgan Kaufmann. 1991. P. 197-214. P. 69-93.

64. Goldberg D.E., Linge R. Alleles, Loci and the Travelling Salesman Problem //In J.J. Grefenstette (ed.) Proc. of an International Conference on Genetic Algorithms and Their Applications. -Hillsdale, NJ, 1985. P.154-159.

65. Halldorsson, M.M., Radhakrishnan, J. Greed is good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs // Algorithmica. 1997. - Vol. 18. - P.143-163.

66. Hao J.-K., Lardeux F., Saubion F. Evolutionary Computing for the Satisfiability Problem //In S.Cagnoni et al. (eds.) Applications of evolutionary computing: Proc. of EvoWorkshops 2003. Springer Verlag. LNCS, V. 2611. 2003. P.258-267.

67. Hastad, J. Some Optimal Inapproximability Results. Report No. TR-97-037. Trier: Electronic Colloquium on Computational Complexity, 1997.

68. Hochbaum D.S. Efficient bounds for the stable set, vertex cover and set packing problems // Discrete Applied Mathematics, 1983. -Vol. 6. - R243-254.

69. Hochbaum D.S. Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems // In D.S. Hochbaum (ed.) Approximation algorithms for NP-hard problems. PWS Publishing Company, 1995. P.94-143.

70. Holland J. Adaptation in natural and artificial systems. University of Michigan Press, 1975.

71. Jones Т., Forrest S. Fitness distance correlation as a measure of problem difficulty for genetic algorithms //In L.J. Eshelman (ed.) Proc. of the 6th International Conference on Genetic Algorithms. San Mateo: Morgan Kaufmann. 1995. P. 184-192.

72. Juliany J., Vose M.D. The Genetic Algorithm Fractal // Evolutionary Computation 1994. - Vol 2, N 2, - P. 165-180.

73. Kamae Т., Krengel U., O'Brien G.L. Stochastic inequalities on partially ordered spaces, The Annals of Probability 1977. - Vol 5, N 6, - P. 899-912.

74. Kirkpatrick S., Gellatt C.D., Vecchi M.P. Optimization by simulated annealing // Science 1983. - Vol 220, N 4598, - P.671-780.

75. Ко К. Some observations on the probabilistic algorithms and NP-hard problems // Information Processing Letters, 1982. N 14, -P.39-43.

76. Koza J.R. Genetic programming: On the programming of computers by means of natural selection. MIT Press. 1992.

77. Kratica J., Tosic D., Filipovic V., Ljubic I. Solving the Simple Plant Location Problems by Genetic Algorithm // RAIRO Operations Research, 35, 2001. P.127-142.

78. Kuznetsova A., Strekalovsky A.S. On solving the maximum clique problem // J. Global Optim. 2001. - Vol. 21. N. 3. - P. 265-288.

79. Lindvall T. Lectures on the coupling method. Whiley, New York. 1992.

80. Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H., Teller E. Equation of state calculation by fast computing machines // Journal of Chemical Physics 1953. - Vol. 21. - P.1078-1092.

81. Motwani R., Raghavan P. Randomized Algorithms. Cambridge University Press, 1995.

82. Miihlenbein H. How genetic algorithms really work I: Mutation and hillclimbing // Proc. of Parallel Problem Solving from Nature (PPSN II). North Holland, 1992. P.54-63.

83. G.L. Nemhauser, Trotter, J.L.E. Vertex packing: structural properties and algorithms// Math. Progr. 1975. - Vol. 8. - P.232-248.

84. Rechenberg I., Evolutionsstrategie: Optimerung Technischer Systeme nach Prinzipen der Biologischen Evolution // Stuttgart: Formann-Holzboog Verlag, 1973.

85. Reeves C.R. Genetic Algorithms for the Operations Researcher// INFORMS Journal on Computing. 1997. - Vol. 9, N 3. - P.231-250.

86. Reeves C.R., Rowe J.E. Genetic Algorithms Principles and Perspectives: A Guide to GA Theory // Kluwer Academic Publishers, 2003.

87. Richardson J. Т., Palmer M. R., Liepins G., Hilliard M. Some guidelines for genetic algorithms with penalty functions.// In J.D. Schafer (Ed.) Proc. of the 3rd International Conf. on Genetic Algorithms. Morgan Kaufmann. 1989. - P. 191-197.

88. Rudolph G. Finite Markov Chain Results in Evolutionary Computation: A Tour d'Horizont // Fundamenta Informaticae 35 (1-4) 1998. P.67-89.

89. Scharnow J., Tinnefeld K., Wegener I. Fitness landscapes based on sorting and shortest paths problems // Proc. of Parallel Problem Solving from Nature (PPSN VII), Springer, LNCS 2439, 2002. -P.54-63.

90. Syswerda G. A study of reproduction in generational and steady state genetic algorithm // In G. Rawlings (ed.) Foundations of Genetic Algorithms 7. San Mateo: Morgan Kaufmann. 1991. 94101.

91. Sun M., Aronson J.E., McKeown P.G., Drinka D. A Tabu Search Heuristic Procedure for the Fixed Charge Transporation Problem // European J. Oper. Res. 1998. V. 106. P. 441-456.

92. Wolpert D.H., Macready W.G. No free lunch theorem for optimization // IEEE Transactions on Evolutionry Computation V. 1. P. 67-82.

93. Yamada Т., Nakano R. Job-shop scheduling //In A.M.S.Zalzala and P.J.Fleming (eds.) Genetic Algorithms in Engeneering Systems. Peter Peregrinus, London. 1997. - P. 134-160.