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

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

ЛОРЕШ Максим Андреевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ МУРАВЬИНОЙ КОЛОНИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ ПРЕДПРИЯТИЙ

05.13.01 — системный анализ, управление и обработка информации (в научных исследованиях)

АВТОРЕФЕРАТ

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

Омск - 2006

Работа выполнена в ГОУ ВПО "Омский государственный университет им. Ф.М. Достоевского"

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

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

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

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

профессор

Защита состоится 29 июня 2006 г. в 14 часов на заседании диссертационного совета ДМ 212.179.03 при ГОУ ВПО "Омский государственный университет им. Ф.М. Достоевского" по адресу: 644077, г. Омск, ул. Нефтезаводская, 11.

С диссертацией можно ознакомиться в библиотеке Омского государственного университета им. Ф.М. Достоевского.

Автореферат разослан 2006 г.

Ученый секретарь диссертационного совета

Филимонов Вячеслав Аркадьевич,

кандидат физико-математических наук Пащенко Михаил Георгиевич.

Ведущая организация: Уфимский государственный авиационный

технический университет.

к.ф.-м.н., доцент

А.М. Семенов

/

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

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

Задачи оптимального размещения и методы их решения образуют важное направление в области дискретной оптимизации. Тематика исследований по данным задачам достаточно разнообразна и включает разработку и исследование алгоритмов их решения, изучение структуры и сложности задач, выделение полиномиально разрешимых случаев и построение семейств "трудных" задач для определенных классов алгоритмов [1,2,4,5 15,17,20]. Значительное число исследований посвящено простейшей Задаче размещения, задаче о р-медиане и задаче с ограничениями на мощности производства [1,2,4,15,17]. Данные задачи являются одними из наибе, лее известных моделей размещения, допускают многочисленные обобщения и представляют практический интерес. Вычислительная сложность, а также большая размерность указанных задач размещения, как правило, не позволяют получать оптимальное решение за приемлемое время вследствие чего особое значение приобрела разработка методов получения' приближенных решений [1,3,6,9,11,29].

В последние годы большой интерес проявляется к подходам идеи которых заимствованы у живой природы, в частности к алгоритмам муравьиной колонии (МК). Ранее алгоритмы МК применялись для решения задачи коммивояжера, квадратичной задачи о назначениях, задачи раскроя и упаковки, задачи маршрутизации и других [3,8,11], зарекомендо вав себя как эффективный инструмент решения задач оптимизации. Однако этот подход для решения задач оптимальною размещения предприятий

практически не разрабатывался __

I РОС. НАЦИОНАЛЬНАЯ ! __________...

БИБЛИОТЕКА • С.-Петербург : оэ 200

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались на 12-й Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2003), Всероссийской научной молодежной конференции "Под знаком "Сигма" (Омск, 2003), Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2004), The Second International Workshop "Discrete Optimization Methods in Production and Logistics" (Omsk-Irkutsk, 2004), XIII Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Северобай-кальск, 2005), на научных семинарах в Омском филиале Института математики им. C.JI. Соболева СО РАН (Омск).

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

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

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

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

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

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

Простейшем задача размещения (ПЗР) состоит в следующем. Дано множество пунктов возможного размещения предприятий с номерами из I — {1,...,т} и список клиентов с номерами из J = {1,...,п}. Предприятия могут производить некоторый продукт в неограниченном количестве. Известны стоимости размещения предприятий Ci в указанных пунктах и затраты ty на транспортировку продукции от предприятия в пункте i потребителю j, i £ I,j £ J. Требуется разместить предприятия и прикрепить к ним клиентов так, чтобы суммарные производственно-транспортные затраты были минимальны. Модель целочисленного линейного программирования (ЦЛП) для ПЗР имеет вид:

F(z, X) = £ dZi + Y. £ UjXi] min (1)

»€/ i<El jeJ

T. xij = h Zi> Xij, i € /, j € J, (2)

tel

Zx € {0,1}, xtj > 0, i 6 I, j € J, (3)

где x^ - доля спроса клиента j, которую обеспечивает предприятие из пункта г; z, = 1, если предприятие открыто в пункте г (предприятие г открыто) и 0 - в противном случае, г € /, j £ J.

Задача о р-медиане на минимум отличается от ПЗР тем, что требуется разместить ровно р предприятий и с, = 0 дая всех i £ I.

Задача с ограничениями на мощности производства является обобщением ПЗР. В ней известна мощность производства Vt для каждого г € I, а также потребность dtJ каждого клиента j в продукции предприятия i, i 6 I, j € J. Модель ЦЛП для данной задачи записывается следующим образом:

F(z,X) = Еед + ЕЕiijXij min (4)

tel teljçJ

= j &J, (5)

ш

E dijXtJ < ViZi, i G I, (6)

jzJ

zux4 G {0,1}, !€/. (7)

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

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

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

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

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

Необходимо также отметить, что идея "поощрения" и "наказания" некоторых компонент решения использовалась ранее, например, в алгоритме СПА (случайный поиск с адаптацией) для задачи нахождения наиболее информативной подсистемы признаков [7].

В главе 2 описываются разработанные нами алгоритмы МК для задач размещения предприятий.

В п. 2.1 и 2.2 рассматриваются задача о р-медиане на минимум и простейшая задача размещения. Решением з задачи о р-медиане и ПЗР будем называть булев вектор г размерности т такой, что г, = 1, если г € 1„, и 0 - в противном случае, где /„ - множество открытых предприятий (для р-медианы |/8| = р). Пусть далее - уровень феромона для г-го предприятия на итерации к, Д/,г - изменение значения целевой функции в результате закрытия предприятия г на шаге г алгоритма ИМ, г Е I, I* - множество открытых предприятий для решениия з на шаге г алгоритма ИМ.

В качестве алгоритмов ИМ использовались алгоритмы а^2-рт для задачи о р-медиане и апЬ-зр1р для простейшей задачи разме-

щения, представляющие собой вероятностные модификации жадного алгоритма спуска. На каждом шаге г алгоритма аг^2-рт генерируется множество предприятий

\¥г(\) = {* € II | Д/Г < (1 - А) ттА/{ + АтшсД/Л, (8)

где А 6 [0,1]. Привлекательность г)1 вычисляется по формуле

г = { -А/,г + тах^ичл) ЛЯ> * € И^(А), * Ц г е \ и^Г(А),

где параметр в > 0. Данный параметр необходим для того, чтобы любое предприятие i € Ц имело шанс быть закрытым. Далее случайным образом с распределением вероятностей

РТ, = * € Гв, (10)

Е аЫ

к/;

выбирается предприятие ¿о € которое закрывается. Алгоритм ап!2-рт начинает работу с множества — / и завершает ее при = р.

На каждом шаге г алгоритма а^-вр1р для ПЗР генерируется множество = {г £ /¡¡А/Г > 0}, а также У(Х) = {» е ЦГ\АД > А - Д/^}, где А/тах == тах Д//", параметр А принадлежит отрезку [0,1]. Привлекательность закрытия предприятия г определяется согласно правилу

V,

АД, ге^(А),

е, ¿6 1УГ\КГ(А), (И)

0, ¿е/;\Шг.

На каждом шаге г алгоритма ап(;-8р1р с распределением вероятностей (10) выбирается го 6 \¥т, которое закрывается. Алгоритм ап^вр1р начинает работу с множества 1} = I и завершает ее, если на некотором шаге либо УГ = 0, либо = 1.

Для задачи о р-медиане предлагаются алгоритмы муравьиной колонии АС1-рт и АС2-рт с различными схемами переопределения уровня феромона, а также их аналоги АС1-вр1р и АС2-зр1р для ПЗР.

На каждой итерации алгоритма АС1 при помощи соответствующего алгоритма ИМ строится Ь решений задачи. Затем из этих решений выбираются I лучших по значению целевой функции. Далее на основе отобранных лучших решений определяются значения уровня феромона для всех г € / (причем, чем чаще предприятие г включалось в I таких решений, тем меньше соответствующее Компоненты вектора а*4"1 вычисляются

следующим образом:

аГ = ^ + г 6 /, (12)

Рк

где Рк € (0,1) - коэффициент затухания (испарения феромона) на итерации к\ 7* € [0,1] - частота появления предприятия г в I лучших решениях, выбираемых на итерации к; параметр д е (0,1). Если на некоторой итерации произошла смена рекорда, то для ненулевых компонент соответствующего вектора 2 назначается — ашш, где аШ11 > 0 - параметр, задающий минимально возможный уровень феромона. Такой способ переопределения феромона будем называть схемой слабого типа.

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

В п. 2.3 предлагается алгоритм АС-ср1р для задачи (4)-(7). Здесь решением в является пара (г, X), где г - булев вектор размерности т,Х — (жу) - т х п матрица перевозок. В данном алгоритме МК информация (уровень феромона) хранится и накапливается в матрице (ту), в которой ту соответствует уровню феромона для перевозки ху, г е I,] € 3■

Искусственный муравей ап^ср1р, двигаясь от клиента к клиенту, назначает каждому потребителю ] ровно одно предприятие г согласно некоторому вероятностному закону. Если к потребителю ] прикреплено предприятие г, то ху = 1, предприятие г считается открытым, и вероят-

ность его использования для обслуживания оставшихся клиентов повышается. Результатом работы алгоритма ап<;-ср1р является вектор г и матрица перевозок X.

Вероятность назначения ху = 1 на гааге г вычисляется по формуле, аналогичной (10). Привлекательность определяется следующим образом:

где а и ¡3 - параметры, Vt - остаток мощности предприятия i, г £ I.

Алгоритм муравьиной колонии АС-cplp представляет собой модификацию схемы, для которой доказана асимптотическая сходимость [14}.

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

Для задачи о р-медиане рассматриваются окрестность Swap и окрестность Лина-Кернигана [29]. Для ПЗР предлагается окрестность Drop, каждый элемент которой является результатом работы жадного алгоритма спуска [28]. Процедура локального поиска для задачи (4)-(7) основана на окрестности Shift, представляющей собой модификацию соответствующей окрестности для обобщенной задачи о назначениях [19].

Результаты второй главы опубликованы в работах [23,26,28-30,32].

В главе 3 рассматриваются теоретические вопросы сходимости предложенных алгоритмов МК. Работы, посвященные вопросам сходимости алгоритмов муравьиной колонии, стали появляться относительно недавно [13,14,16,18], причем все полученные результаты относятся к упрощенным версиям фактически применяемых схем и не дают прямых рекомендаций для практического использования. Однако они представляют интерес для изучения общих свойств исследуемых алгоритмов. В п. 3.1 дается краткий обзор результатов о сходимости алгоритмов муравьиной колонии.

если Vi > dij, в противном случае,

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

Теорема 3.1. Пусть в алгоритме АС2-рт для задачи о р-медиане в качестве искусственного муравья используется алгоритм агй2-рт, и пусть для некоторого N >1 выполняется условие

т'( ^Ц- < Рк < 1 для всех к> N. N к + 2 ~

Тогда F(sfc) —+ F(s*) почти наверное при к —* оо, где ¡к - текущий рекорд, аз* - оптимальное решение.

Отметим, что теорема имеет место также для алгоритма АС1-рт. Кроме того, для алгоритма АС2-рт, в котором используется схема переопределения феромона сильного типа, верно следующее следствие.

Следствие 3.1. Если в алгоритме АС2-рт выполняются условия теоремы 3.1, причем £1о§/?£ = —оо, то для каждого запуска алгоритма АС2-рт найдется такое оптимальное решение в*, что для алгоритма апШ-рт имеет место сходимость Рк(з*) —* 1 при к —> оо.

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

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

Утверждение 3.2. Пусть в алгоритме АС2-рт используется алгоритм апЬ2-рт с процедурой локального поиска и Ек^/?*, = —оо. Тогда математическое ожидание числа шагов алгоритма локального поиска

до локального оптимума стремится к нулю при к —* оо.

Данное утверждение верно также для алгоритма АС2-эр1р с алгоритмом искусственного муравья ап1;-8р1р.

Результаты третьей главы опубликованы в работах [25,28].

В главе 4 излагаются результаты экспериментальных исследований, проведенных на основе предложенных в предыдущих главах алгоритмов муравьиной колонии. В 4.1 и 4.2 приводятся результаты экспериментального исследования алгоритмов для простейшей задачи размещения и задачи о р-медиане. Эксперимент выполнялся на тестовых примерах размерности т — п = 100 из электронной библиотеки "Дискретные задачи размещения" Института математики СО РАН [20]. Данные задачи являются трудными для некоторых точных алгоритмов, а также для алгоритмов локального поиска. Кроме того, рассматривались примеры из ОЯ-ГлЬгагу [10].

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

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

алгоритмы муравьиной колонии не только получают решения с меньшими отклонениями от оптимальных, но и работают быстрее по сравнению с обычной мультистарто-вой процедурой, основанной на локальном поиске. Следует отметить, что число шагов локального поиска до локального оптимума может быть экспоненциальным [6].

В п. 4.3 излагаются результаты вычислительного эксперимента для задачи размещения предприятий с ограничениями на мощности производства. Эксперимент проводился на тестовых примерах размерности т = п = 100 из электронной библиотеки "Дискретные задачи размещения" Института математики СО РАН [20]. Для данных задач оптимальные решения не известны, а найдены нижняя и верхняя оценки значений целевой функции, вычисленные при помощи алгоритмов, в которых используется релаксация Лагранжа [9]. Кроме того, рассматривались примеры из электронной библиотеки ОН-1лЬгагу [10]. Для этих задач оптимальные решения известны.

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

На примерах из библиотеки OR-Library алгоритм АС-cplp также показал небольшие средние отклонения (порядка 1%) от оптимальных значений целевой функции.

Результаты четвертой главы опубликованы в работах [23,24,26-32].

В заключении приводятся основные результаты диссертации.

Список литературы

[1] Агеев A.A. Точные и приближенные алгоритмы для задач размещения: обзор последних достижений // Материалы конференции.- Новосибирск: Изд-во ИМ СО РАН, 1998. - С. 4-10.

[2] Береснев B.JL, Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. - Новосибирск, 1978. - 333 с.

[3] Валеева А.Ф. Применение метаэвристики муравьиной колонии к задачам двухмерной упаковки // Информационные технологии, N 10, 2005. - С. 36-43.

[4] Колоколов A.A., Косарев H.A., Рубанова H.A. Исследование отсечений Бендерса в декомпозиционных алгоритмах решения некоторых задач размещения // Омский научный вестник, 2005. - Т.2(31). -С. 76-80.

[5] Колоколов A.A., Леванова Т.В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения // Вестник Омского ун-та - Омск: ОмГУ, 1996. - N 1. - С. 21-23.

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

[7] Лбов Г.С. Выбор эффективной системы зависимых признаков // Вычислительные системы, 1965, вып. 19. - С. 21-34.

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

[9] Пащенко М.Г. Лагранжевы эвристики для задачи размещения с ограничениями на мощности // Труды XI международной Байкальской школы-семинара. Иркутск, Байкал, 5-12 июля 1998г., Т.1. -С. 175-178.

[10] Beasley J.E. An algorithm for solving large capacitated warehouse location problems // European Journal of Operational Research. - 1988. - V. 33. - P. 314-325.

[11] Dorigo M., Di Caro G., Gambardella L.M. Ant Algorithms for Discrete Optimization // Artificial Life. - 1999. - V. 5(2). - P. 137-172.

[12] Dorigo M., Maniezzo V., Colorny A. Ant System: An Autocatalytic Optimizing Process // Report No. TR-91-016. - Milan: Politécnico di Milano, 1991.

[13] Gutjahr W.J. A graph-based Ant System and its convergence // Future Generation Computer Systems. - 2000. - V. 16. - P. 873-888.

[14] Gutjahr W.J. ACO algorithms with guaranteed convergence to the optimal solution // Information Processing Letters. - 2002. - V. 82(3). -P. 145-153.

[15] Krarup J., Pruzan P.M. The simple plant location problem: survay and synthesis // European Journal of Operational Research. - 1983. - V.12, N1. - P. 36-81.

[16] Neumann F., Witt C. Runtime Analisys of a Simple Ant Colony Optimization Algorithm // Technical Report, Reihe CI 200/06, SFB 531, Universität Dortmund, 2006.

[17] Sridharan, R. The capacitated plant location problem // European Journal of Operational Research. - 1995. - V 87. - P. 203-213.

[18] Stutzle Т., Dorigo M. A Short Convergence Proof for a Class of ACO Algorithms // IEEE Transactions on Evolutionary Computation. - 2002. - V. 6(4). - P. 358-365.

[19] Yagiura, M., Ibaraki, Т., Glover, F. An ejection chain approach for generalized assignment problem // INFORMS Journal on computing. -2004. - V. 16. - P. 133-151.

[20] http://www.math.nsc.ru/AP/benchmarks/index.hnml

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[21] Леванова Т.В., Лореш М.А. Алгоритм муравьиной колонии и имитации отжига для простейшей задачи размещения // Материалы российской конференции "Дискретный анализ и исследование операций", Новосибирск, 2002. - С. 235.

[22] Леванова Т.В., Лореш М.А. Алгоритм муравьиной колонии для задачи о р-медиане // Информационный бюллетень Ассоциации математического программирования. № 10. Научное издание. Екатеринбург: УрО РАН, 2003. - С. 172-173.

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

[24] Леванова Т.В., Лореш М.А. Алгоритм муравьиной колонии для задачи размещения предприятий с ограничениями на мощности производства // Материалы российской конференции "Дискретный анализ и исследование операций", Новосибирск, 2004. - С. 189.

[25] Леванова Т.В., Лореш М.А. О сходимости одного алгоритма муравьиной колонии для задачи о р-медиане // Труды XIII Байкальской международной шк.-сем. Северобайкальск, 2005. - Т. 1. - С.535-541.

[26] Леванова Т.В., Лореш М.А., Никитин А.Г. Алгоритмы муравьиной колонии и имитации отжига для одной задачи размещения предприятий // Материалы ежегодного научного семинара аспирантов и студентов-выпускников "Под знаком "Сигма". - Омск: ООО "Издатель-Полиграфист", 2003. - С. 21-26.

[27] Лореш М.А. Некоторые метаэвристики для задачи о р-медиане // Материалы Всероссийской научной молодежной конференции "Под знаком "Сигма", Омск, 2003. - С. 11-12.

[28] Лореш М.А. Алгоритмы муравьиной колонии для простейшей задачи размещения: Препринт. - Омск: "Полиграфический центр"КАН", 2006. - 19 с.

[29] Kochetov Y., Alekseeva Е., Levanova Т., Loresh М. Large neighborhood local search for the p-median problem // Yugoslav Journal of Operations Research. - 2005. - V. 15, N1. - P. 53-63.

[30] Levanova T.V., Loresh M.A. Ant colony and simulated annealing algorithms for the p-median problem // Proceedings of The Second International Workshop "Discrete Optimization Methods in Production and Logistics", Omsk-Irkutsk, 2004. - P. 70-74.

[31] Levanova T.V., Loresh M.A., Nikitin A.G. Some local search algorithms for uncapacitated facility location problem // Proc. of XXXIII annual conference "AIRO 2002", L'Aquila, 2002. - P. 170.

[32] Loresh M.A., Levanova T.V. The Ant Colony algorithm for the Capacitated Plant Location Problem // EWGLA XV Meeting, Saarbrücken, 2004. - P. 39-40.

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

Лицензия ПЛД №58-47 от 21.04.1997.

Подписано в печать 25.05.06 Формат 60x 84/16

Бумага офсетная Ризография

Усл. печ. л. 1,25 Уч.-изд. л. 1,3

Тираж 100 экз. Заказ №185

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

/Y* M

]^4 3 0 l

ï

i

\

Введение.

Глава 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.3 Задача размещения предприятий с ограничениями на мощности производства.

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

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

Задачи оптимального размещения и методы их решения образуют важное направление в дискретной оптимизации. Тематика исследований по данным задачам достаточно разнообразна и включает разработку и исследование точных и приближенных алгоритмов их решения, изучение структуры и вычислительной сложности задач, выделение полиномиально разрешимых случаев, построение семейств "трудных" задач для определенных классов алгоритмов [1,2,4,6,7,11,12,15,17-26,28,31,32,3739,49,57,59,62,70,94,95,110, ИЗ, 120].

В данной области существуют классические задачи, к которым можно отнести простейшую задачу размещения и задачу о р-медиане. Указанные задачи допускают многочисленные обобщения и представляют большой практический интерес. Именно поэтому им посвящено значительное число работ [2,6,38,41,45,66,70,90,96]. Кроме того, ведутся исследования задач размещения предприятий с ограничениями на мощности производства [43,52,104,113]. Можно также отметить работы по многопродуктовым [4] и многоуровневым [12,17,51] задачам размещения.

Актуальность исследования дискретных задач размещения связана с iVP-трудностью многих таких проблем. Вопросы сложности задач размещения производственно-транспортного типа и сводимости к ним известных задач рассматриваются, например, в [1,16, 27, 35, 70]. Задача о р-медиане, простейшая задача размещения, задача размещения предприятий с ограничением на мощности производства также являются ЛГР-трудными. Поэтому значительное внимание уделяется разработке алгоритмов решения указанных задач размещения и исследованию их эффективности.

Вычислительная сложность, а также большая размерность задач размещения предприятий, как правило, не позволяют находить оптимальное решение за приемлемое время. В связи с этим особое значение приобрела разработка методов получения приближенных решений. В последние годы активно развиваются алгоритмы, основанные на процедуре локального поиска [34,88,93,103]. Значительный интерес проявляется к алгоритмам, идеи которых заимствованы у живой природы или физических процессов. К таким методам можно отнести генетические алгоритмы, алгоритм имитации отжига, нейронные сети, а также алгоритмы муравьиной колонии [3,8,19,33,50,65,72,89,93,97,101,102].

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

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

Ранее алгоритмы муравьиной колонии применялись для решения задачи коммивояжера [64,67,73-78,80,116-118], квадратичной задачи о назначениях [81,82,106-108], задачи календарного планирования [68], задач раскроя и упаковки [8,50] и ряда других комбинаторных задач [60,63,72], зарекомендовав себя как эффективный инструмент решения задач оптимизации. Однако, этот подход для решения задач оптимального размещения предприятий практически не применялся.

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

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

Диссертация состоит из введения, четырех глав, заключения и списка литературы.

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

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

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

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

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

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

Заключение

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

1. Агеев А.А. О сложности задач минимизации полиномов от булевых переменных // Управляемые системы. - Новосибирск, 1983. — Вып. 23. - С. 3-19.

2. Агеев А.А. Точные и приближенные алгоритмы для задач размещения: обзор последних достижений // Материалы конференции. Новосибирск: Изд-во ИМ СО РАН, 1998. - С. 4-10.

3. Александров Д.А. Алгоритм муравьиной колонии для задачи о минимальном покрытии // Труды XI междунар. Байкальской школы-семинара "Методы оптимизации и их приложения", Т.З, Иркутск, 1998. - С. 17-20.

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

5. Береснев B.JI. Эффективный алгоритм для задачи размещения производства с вполне уравновешенной матрицей // Дискретный анализ и исследование операций, Серия 1, 1998, том 5, N1. — С. 20-31.

6. Береснев B.JL, Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск, 1978. - 333 с.

7. Булатов В.П. Методы погружения в задачах оптимизации. — Новосибирск: Наука, 1977. 161 с.

8. Валеева А.Ф., Аглиуллин М.Н. Алгоритм муравьиной колонии для задач двухмерной упаковки: результаты вычислительного эксперимента // Труды XIII Байкальской международной школы-семинара, Иркутск, Байкал, 2005. Т.1. - С. 429-434.

9. Гидоян JI.K., Трубин В.А. О некоторых классах задач размещения деревьев на цепи // Кибернетика, 1991, N2. С. 76-79.

10. Гимади Э.Х. Задачи стандартизации с данными произвольного знака и связными, квазивыпуклыми и почти квазивыпуклыми матрицами // Управляемые системы, Новосибирск, 1987. Вып. 27. С. 3-11.

11. Гимади Э.Х. Обоснование априорных оценок качества приблио/сен-ного решения задачи стандартизации // Управляемые системы. -Новосибирск, 1987. Вып.27. - С. 12-27.

12. Гончаров Е.Н. Метод ветвей и границ для простейшей двухуровневой задачи размещения предприятий // Дискретный анализ и исследование операций, Серия 2, 1998, том 5, N1. С. 19-39.

13. Гончаров Е.Н., Кочетов Ю.А. Вероятностный жадный алгоритм с ветвлением для многостадийной задачи размещения // Труды XI междунар. Байкальской школы-семинара "Методы потимиза-ции и их приложения", Иркутск, Байкал, 1998. С. 121-124.

14. Горбачевская JI.E., Кочетов Ю.А. Вероятностная эвристика для двухуровневой задачи размещения If Труды XI междунар. Байкальской школы-семинара "Методы потимизации и их приложения", Иркутск, Байкал, 1998. С. 249-252.

15. Гришухин В.П. Полиномиальность в простейшей задаче размещения. // Препринт ЦЭМИ АН СССР. М.: 1987. 64 с.

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

17. Дементьев В.Т., Ерзин А.И., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур. ~ Изд-во НГУ, Новосибирск, 1996. 167 с.

18. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981. - 344с.

19. Еремеев А.В. Генетический алгоритм для задачи о минимальном покрытии // Материалы конф. Новосибирск: Изд-во ИМ СО РАН, 1998. - С. 21-24.

20. Еремин И.И., Мазуров В.Д., Астафьев Н.Н. Несобственные задачи линейного выпуклого программирования. М.: Наука, 1983. - 336с.

21. Живетьева И.А., Леванова Т.В. Анализ градиентных алгоритмов решения задачи о р-медиане на основе крутизны целевой функции II Матер, междунар. конф. "Дискретный анализ и исследование операций". Новосибирск, 2000. С. 167.

22. Заблоцкая О.А. L-разбиение многогранника стандартизации // Моделирование и оптимизация систем сложной структуры: Меж-вуз. сб. научн. труд./ Омск: ОмГУ, 1987. С. 151-154.

23. Забудский Г.Г. О минимаксной и минисуммной задачах размещения на плоскости с запрещенными областями // Труды XIII Байкальской международной школы-семинара "Методы потимизации и их приложения", Иркутск, Байкал, 2005. Т.1. - С. 455-460.

24. Заозерская Л.А., Китриноу Е., Колоколов Задача оптимального размещения центров телекоммуникаций в регионе // Труды XI Байкальской международной школы-семинара "Методы оптимизации и их приложения", Иркутск, Байкал, 2005. Т.1. - С. 469-476.

25. Ильев В.П. Оценка точности алгоритма жадного спуска для задачи минимизации супермодулярной функции // Дискретный анализ и исследование операций. Серия 1. - 1998. - Т.5. - N4. - С. 45-60.

26. Ильев В.П., Леванова Т.В. Анализ градиентного алгоритма минимизации супермодулярной функции на матроиде // Труды XI междунар. Байкальской школы-семинара "Методы потимизации и их приложения", 1998. Т.1. - С. 143-146.

27. Ричард М. Карп. Сводимость комбинаторных проблем // Кибернетический сборник, 12, М.: Мир, 1975. С.16-38.

28. Ковалев М.М. Дискретная оптимизация (целочисленное программирование). Минск: БГУ, 1977. - 192 с.

29. Колоколов А.А. Выпуклые множества с альтернирующим L-разбиением // Моделирование и оптимизация систем сложной структуры: Межвуз. сб. научн. труд./ ОмГУ. Омск, 1987. -С. 144-150.

30. Колоколов А.А. Применение регулярных разбиений в целочисленном программировании // Изв. вузов. Математика, 1993, N 12. С. 11-30.

31. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании. // Сиб. журнал исслед. операций. Новосибирск. - 1994. - Т.1, N 2. - С.18-39.

32. Колоколов А.А., Леванова Т.В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. // Вестник Омского ун-та. Омск: ОмГУ, 1996. - N 1. -С.21-23.

33. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения: Сборник лекций молодежных научных школ по дискретной математике и ее приложениям. М.: МГУ, 2001. - С. 84-117.

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

35. Кук С.А. Сложность процедур вывода теорем/ Кибернетический сборник, 12, М., Мир, 1975, с.5-15.

36. Лбов Г.С. Выбор эффективной системы зависимых признаков // Вычислительные системы, 1965, вып. 19. С. 21-34.

37. Леванова Т.В. Решение некоторых задач размещения на информационно-вычислительной сети // Информ. технологии и радиосети (ИНФОРАДИО'96): Междунар. науч. -практ. конф. Новосибирск: Изд-во ИМ СО РАН, 1998. - С. 44-47.

38. Леванова Т.В. Двойственный жадный алгоритм для задачи о р-медиане и ее обобщений // Препринт 98-4. Омск: Омский госуниверситет, 1998. 13 с.

39. Леванова Т.В. Алгоритмы решения одной задачи размещения на основе декомпозиции и перебора L-классов // В сб. докладов Междунар. конф. "Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде", 2000. С. 146— 149.

40. Леванова Т.В., Лореш М.А. Алгоритм муравьиной колонии для задачи о р-медиане // Информационный бюллетень Ассоциации математического программирования. № 10. Научное издание. Екатеринбург: УрО РАН, 2003. С. 172-173.

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

42. Леванова Т.В., Лореш М.А. Алгоритм муравьиной колонии и имитации отоюига для простейшей задачи размещения // Материалы конференции "Дискретный анализ и исследование операций", Новосибирск, 2002. С. 235.

43. Леванова Т.В., Лореш М.А. Алгоритм муравьиной колонии для задачи размещения предприятий с ограничениями на мощности производства // Материалы конференции "Дискретный анализ и исследование операций", Новосибирск, 2004. С. 189.

44. Леванова Т.В., Лореш М.А. О сходимости одного алгоритма муравьиной колонии для задачи о р-медиане // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения", Иркутск, Байкал, 2005. Т.1. - С. 535-541.

45. Лореш М.А. Некоторые метаэвристики для задачи о р-медиане II Материалы Всероссийской научной молодежной конференции "Под знаком "Сигма", Омск, 2003. С. 11-12.

46. Лореш М.А. Алгоритмы муравьиной колонии для простейшей задачи размещения: Препринт. Омск, ОмГУ, 2006. - 19 с.

47. Лэсдон Л.С. Оптимизация больших систем. М.: Наука, 1975. -432 с.

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

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

50. Пащенко М.Г. Нижние оценки для целевой функции в динамической задаче выбора оптимального состава двухуровневой системы технических средств // Дискретный анализ и исследование операций, Серия 2, 1997, Т.4, N1. -С. 40-53.

51. Пащенко М.Г. Лагранэюевы эвристики для задачи размещения с ограничениями на мощности // Труды XI международной Байкальской школы-семинара "Методы оптимизации и их приложения", Иркутск, Байкал, 1998. Т.1. - С. 175-178.

52. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наук, дум., 1988. - 472 с.

53. Схрейвер А. Теория линейного и целочисленного программирования./ Пер. с англ. В 2-х т. М.: Мир, 1991. - 702 с.

54. Хачатуров В.Р. Математические методы регионального программирования. М.: Наука, 1989. - 304 с.

55. Ху Т.С. Целочисленное программирование и потоки в сетях./ Пер. с англ. М., Мир, 1974. 519 с.

56. Шевченко В.Н. Качественные вопросы целочисленного программирования. М.: Физматлит, 1995. - 190 с.

57. Adolfson D., Ни Т.С. Optimal Linear Ordering // SIAM Jornal on Applied Mathematics. 1973. - V.25, N.3. - P.403-423.

58. Ageev A.A., Sviridenko M.I. Approximation Algorithms for some Problems with cardinalyty-type contraints // Труды XI международной Байкальской школы-семинара "Методы оптимизации и их приложения", Иркутск, Байкал, 1998. С. 107-110.

59. Ant Colony Optimization / Dorigo M., Stutzle Т., MIT Press, 2004.

60. Badr A., Fahmy A. A proof of convergence for Ant algorithms // Information Sciences, 160, 2004. P. 267-279.

61. Beasley J.E. An algorithm for solving large capacitated warehouse location problems // Europ. J. of Oper. Res. 1988. - 33. - P.314-325.

62. Bonabeau E., Dorigo M., Theraulaz G. From Natural to Artificial Swarm Intelligence // Oxford University Press, 1999.

63. Bullnheimer В., Hartl R.F., Strauss C. A New Rank Based Version of the Ant System: A Computational Study // Central European Journal for Operations Research 7(1), 1999. P. 25-38.

64. Chvatal V. A greedy heuristic for the set-covering problem // Math. Oper. Res. 1979. - 4, N8. - P. 789-810.

65. Chudak F.A. Improved approximation algorithms for uncapacitated facility location // IPC06 Proceedings, 1998.

66. Colorny A., Dorigo M., Maniezzo V. Distributed optimization by ant colonies //In Proceedings of the First European Conference on Artificial Life, Elsevier, 1992. P. 134-142.

67. Colorny A., Dorigo M., Maniezzo V., Trubian M. Ant system for job-shopscheduling // Belgian Journal of Operations Research, Statistics and Computer Science (JORBEL), 34, 1994. R 39-53,

68. Cornuejols G., Fisher M.L. and Nemhauser G.L. Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms // Management Science. 1977. - V. 23. - P. 789-810.

69. Discrete Location Theory / Ed. by Pitu B.Mirchamdani and Richard L.Franscis, 1990, by John Wiley & Sons, Inc.

70. Dorigo M. Optimization, Learning and Natural Algorithms // PhD thesis, Dipartimento di Electronica, Politecnico di Milano, IT, 1992 (in Italian).

71. Dorigo M., Di Caro G., Gambardella L.M. Ant Algorithms for Discrete Optimization // Artificial Life, 1999. V.5(2). - P.137-172.

72. Dorigo M., Gambardella L.M. Ant-Q: A reinforcement learning approach to the traveling salesman problem //In Proceedings of the Twelfth International Conference on Machine Learning, ML-95, Palo-Alto, 1995. P. 252-260.

73. Dorigo M., Gambardella L.M. A study of some properties of Ant-Q //In Proceedings of PPSN-IV, Fourth International Conference on Parallel Problem Solving From Nature, Berlin: Springer-Verlag, 1996. P. 656-665.

74. Dorigo M., Gambardella L.M. Ant colonies for the traveling salesman problem // BioSystems, 43, 1997. P. 73-81.

75. Dorigo M., Gambardella L.M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation, 1(1), 1997. P. 53-66.

76. Dorigo M., Maniezzo V., Colorny A. Ant System: An Autocatalytic Optimizing Process // Report No. TR-91-016. Milan: Politecnico di Milano, 1991.

77. Dorigo M., Maniezzo V., Colorny A. The ant system: Optimization by ' a colony of cooperating agents // IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1), 1996. P. 29-41.

78. Eremeev A.V. A Genetic Algorithm with a Non-Binary Representation for the Set Covering Problem. In Proceedings of OR'98, Springer-Verlag, 1999. P. 175-181.

79. Gambardella L.M., Dorigo M. Solving symmetric and asymmetric TSPs by ant colonies //In Proceedings of the IEEE Conference on Evolutionary Computation, ICEC96, IEEE Press, 1996. P. 622-627.

80. Gambardella L.M., Taillard E. D., Dorigo M. Ant colonies for the QAP // Technical Report 4-97, IDSIA, Lugano, Switzerland, 1997.

81. Gambardella L.M., Taillard E. D., Dorigo M. Ant colonies for the QAP // Journal of the Operational Research Society (JORS), 50(2), 1999. -P. 167-176.

82. Guha S., Khuller S. Greedy strikes back: improved facility location algorithms // The Ninth Annual ACM-SIAM Symposium on discrete algorithms (SODA), 1998. P. 649-654.

83. Gutjahr W.J. A Converging ACO Algorithms for Stochastic Combinatorial Optimization // Proc. SAGA 2003, Springer LNCS 2827, 2003. P. 10-25.

84. Gutjahr W.J. ACO algorithms with guaranteed convergence to the optimal solution // Information Processing Letters, 82(3), 2002, P. 145-153.

85. Gutjahr W.J. A graph-based Ant System and its convergence // Future Generation Computer Systems. 2000. - 16. - P. 873-888.

86. Hajek B. Cooling schedules for optimal annealing // Math, of OR, 13, 1988. P. 311-329.

87. Hansen P., Mladenovic N. An introduction to variable neighborhood search // S. Voss (eds.), Metaheuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, Dorchester, 1998.

88. A.Hertz, E.Taillard, Dominique de Werra Local search in combinatorial optimization // John Wiley &; Sons, Inc., New York, 1997. 512 p.

89. D.S. Hochbaum Heurustics for the fixed cost median problem // Math. Progr. 1982. - 22. - P. 148-162.

90. Kariv 0., Hakimi L. An algorithmic approach to network location problems. II: The p-medians // SIAM J. Appl. Math. Vol 37, No.3, 1979. P.539-560.

91. Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs // Bell System Technical Journal. 1970. - V.49. - P. 291-307.

92. Kochetov Y., Alekseeva E., Levanova Т., Loresh M. Large neighborhood local search for the p-median problem // Yugoslav Journal of Operations Research, 15, N1, 2005. P. 53-63.

93. Kolokolov A.A. On the L-structure of the integer linear programming problems //Proceedings of the 16th IFIP-TC7 Conference on System Modelling and Optimization. Compiegne. France, 1993. P. 756-760.

94. Kolokolov A.A. Decomposition Algorithms for Solving of some Production-Transportation Problems // Triennal Symposium on

95. Transportation Analysis II. Preprints. Vol. 1. Capri, Italy, 1994. -P. 179-183.

96. Krarup J., Pruzan P.M. The simple plant location problem: survay and synthesis //European J. Oper. Res. 1983. V.12, N1. P. 36-81.

97. M. Laguna, F. Glover Bandwing Packing: A tabu Search Approach // Managment Science. Vol. 39, No.4, April 1993, P. 492-500.

98. Lawler E.L. The Quadratic Assignment Problem // Management Science, 1963. V.9. - P. 586-599.

99. Lin J. -H., Vitter J.S., Approximation algorithms for geometric median problems // Inform. Process. Lett. 44 (1992), no.5. P. 245-249.

100. Lin S. Computer solutions of the traveling salesman problem // Bell System Journal, 1965. V.44. - P. 2245-2269.51999. P.76.

101. Levanova T.V., Loresh M.A. Ant colony and simulated annealing algorithms for the p-median problem // Proceedings of The Second International Workshop "Discrete Optimization Methods in Production and Logistics", Omsk-Irkutsk, 2004. P. 70-74.

102. Levanova T.V., Loresh M.A., Nikitin A.G. Some local search algorithms for uncapacitated facility location problem // Proc. of XXXIII annual conference "AIRO 2002", L'Aquila, 10-13 September, 2002. P. 170.

103. Local search in Combinatorial optimization / Edited by E.Aarts and J.K.Lenstra, 1997, John Wiley and Sons Ltd.

104. Loresh M.A., Levanova T.V. The Ant Colony algorithm for the Capacitated Plant Location Problem // EWGLA XV Meeting, Saarbriicken, September 5-8, 2004. P. 39-40.

105. Love R.F., Wong J.Y. On Solving a One-Dimensional Space Allocation Problem with Integer Programming // INFOR. V.12, N2. - R 139143.

106. Maniezzo V. Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem // Technical Report CSR 98-1, C. L. In Scienze dell'Informazione, University di Bologna, sede di Cesena, Italy, 1998.

107. Maniezzo V., Colorni A. The ant system applied to the quadratic assignment problem // IEEE Trans. Knowledge and Data Engineering, 1999

108. Maniezzo V., Colorni A., Dorigo M. The ant system applied to the quadratic assignment problem // Technical Report IRIDIA/94-28, Universite Libre de Bruxelles, Belgium, 1994.

109. Neumann F., Witt C. Runtime Analisys of a Simple Ant Colony Optimization Algorithm // Technical Report, Reihe CI 200/06, SFB 531, Universitat Dortmund, 2006.

110. Picard J.C., Queranne M. On the One-Dimensional Space Allocation Problem // Oper. Res. 1981. - Vol. 29. - P. 371-391.

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

112. Resende M.G.C., Werneck R.F. On the implementation of a swap-based local search procedure for the p-median problem // Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, SIAM, 2003. P. 119-127.

113. Sridharan R. Invited Review. The capacitated plant location problem // Europ. J. of Operational Research 87, 1995. P. 203-213.

114. Sttitzle Т., Dorigo M. A Short Convergence Proof for a Class of ACO Algorithms // IEEE Transactions on Evolutionary Computation, 2002, 6(4). -P. 358-365.

115. Stutzle Т., Hoos H.H. MAX-MIN Ant System // Future Generation Computer Systems. 2000. - 16. - P. 889-914.

116. Stutzle Т., Hoos H.H. Improvements on the Ant System: Introducing the MAX-MIN Ant System //In R.F. Albrecht G.D. Smith, N.C. Steele, editor, Artificial Neural Networks and Genetic Algorithms. Springer-Verlag, Wien, New York, 1998. P. 245-249.

117. Yagiura M., Ibaraki Т., Glover F. An ejection chain approach for generalized assignment problem /j INFORMS Journal on computing, 16, 2004. P. 133-151.120. http://www.math.nsc.ru/AP/benchmarks/index.hnml