Содержание к диссертации
Введение
Глава 1. Постановки задач и методы решения 11
1.1 Постановки задач 11
1.2 Вычислительная сложность и методы решения 19
1.3 Алгоритмы муравьиной колонии 21
Глава 2. Алгоритмы муравьиной колонии для задач оптимального размещения предприятий 35
2.1 Алгоритмы муравьиной колонии для задачи op-медиане 35
2.2 Алгоритмы муравьиной колонии для простейшей задачи размещения 43
2.3 Алгоритм муравьиной колонии для задачи с ограничениями на мощности производства 47
2.4 Локальный поиск в алгоритмах муравьиной колонии 51
Глава 3. Теоретические вопросы сходимости алгоритмов муравьиной колонии 58
3.1 Известные результаты о сходимости алгоритмов 58
3.2 Асимптотические свойства алгоритмов муравьиной колонии для задачи о медиане 60
3.3 Простейшая задача размещения 67
3.4 Алгоритм муравьиной колонии и локальный поиск 70
Глава 4. Результаты вычислительного эксперимента 74
4.1 Простейшая задача размещения 74
4.2 Задача op-медиане 85
4.3 Задача размещения предприятий с ограничениями на мощности производства 92
Заключение 98
Литература 100
- Вычислительная сложность и методы решения
- Алгоритмы муравьиной колонии для задачи op-медиане
- Известные результаты о сходимости алгоритмов
- Простейшая задача размещения
Введение к работе
В современных условиях для успешного развития производства и сферы услуг необходимо решать достаточно широкий спектр задач оптимального размещения (предприятий, их филиалов, сервисных центров, складов и т.п.). Во многих случаях подобные проекты требуют значительных затрат и имеют большое число возможных вариантов решений. Вследствие этого выбор наилучшей альтернативы с позиций опыта и интуиции является весьма затруднительным. Поэтому для решения таких задач используются модели исследования операций и оптимизации, а также методы системного анализа.
Указанные задачи могут быть описаны в терминах дискретных задач оптимального размещения, в которых при определенных условиях необходимо наилучшим образом расположить предприятия и назначить им потребителей для обслуживания. Под обслуживанием часто понимается транспортировка продукции от пунктов производства к пунктам потребления. В аналогичных терминах также могут быть сформулированы многие другие прикладные задачи, возникающие при проектировании печатных плат, электрических и компьютерных сетей, в стандартизации и других областях.
Задачи оптимального размещения и методы их решения образуют важное направление в дискретной оптимизации. Тематика исследований по данным задачам достаточно разнообразна и включает разработку и исследование точных и приближенных алгоритмов их решения, изучение структуры и вычислительной сложности задач, выделение полиномиально разрешимых случаев, построение семейств "трудных" задач для определенных классов алгоритмов [1,2,4,6,7,11,12,15,17—26,28,31,32,37— 39,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]. Все предложенные алгоритмы реализованы, проведено экспериментальное исследование.
Диссертация состоит из введения, четырех глав, заключения и списка литературы.
В первой главе даются постановки указанных задач размещения предприятий и близких к ним задач. Рассматриваются вопросы сложности решения простейшей задачи размещения, задачи о р-медиане и задачи размещения с ограничениями на мощности производства.
Кроме того, в первой главе кратко изложены основные идеи генетических алгоритмов, алгоритмов поиска с запретами, алгоритмов имитации отжига. В этой же главе подробно описываются алгоритмы муравьиной колонии, дается обзор алгоритмов муравьиной колонии, предложенных различными авторами для задачи коммивояжера и квадратичной задачи о назначениях.
Вычислительная сложность и методы решения
В общей постановке задача о р-медиане, простейшая задача размещения, задача с ограничениями на мощности производства принадлежат к классу iVP-трудных проблем. Известно, например [96], что к ПЗР сводится задача о покрытии множества, которая находится в списке P.M. Карпа так называемых полиномиально полных проблем [27,35]. В [1] доказана эквивалентность задачи о наименьшем покрытии множества и задачи минимизации полинома от булевых переменных с неотрицательными коэффициентами при нелинейных членах. Эквивалентность задачи минимизации полинома и простейшей задачи размещения показана в [6]. Из этих результатов также следует факт принадлежности ПЗР к классу iVP-трудных задач. Задача размещения с ограничениями на мощности производства также относится к классу iVP-трудных задач, так как является обобщением ПЗР. iVP-трудность задачи о р-медиане показана в [91].
В связи с iVP-трудностью рассматриваемых проблем, а также ввиду сложности нахождения оптимума в задачах большой размерности, особое значение приобрела разработка эвристических подходов к их решению. В последнее время большое внимание уделяется так называемым метаэвристикам, которые при соответствующей адаптации показывают хорошие результаты. Ниже будут описаны общие идеи некоторых из таких алгоритмов.
В основе генетических алгоритмов лежит имитация развития популяции живых организмов [111]. Каждая особь популяции соответствует некоторому решению и характеризуется набором генов - генотипом. Генотип хранит всю необходимую информацию о соответствующем решении. Популяция особей ведет поиск решений оптимизационной задачи с учетом функции пригодности, которая определяет степень "приспособлешюсти" особей. На каждой итерации создаются новые особи, замещающие менее "пригодные". Для построения новой особи выбираются родители с помощью оператора селекции. Затем к генам родительских особей применяются операторы кроссинговера и мутации. Алгоритм заканчивает свою работу, когда выполнено заданное число итераций или найдено оптимальное решение. Результатом работы генетического алгоритма считается лучшее найденное решение.
Среди относительно новых методов решения сложных комбинаторных задач необходимо отметить поиск с запретамиabu search (TS) [89]. В отличие от других методов локального поиска, при решении задач с помощью TS в памяти хранится некоторая дополнительная информация. Переход от одного решения к другому осуществляется с учетом хранимой информации и возможен только тогда, когда новое решение не обладает определенными свойствами предыдущих. Запрещенные свойства называются запретами (tabu) и хранятся в списке запретов (tabu list). Такое правило перехода позволяет алгоритму в ряде случаев "выбраться" из точек локального оптимума и продолжить процесс решения.
Одной из метаэвристик также является алгоритм имитации отжига. Отжиг представляет собой физический процесс, при котором разогретое до высокой температуры тело, медленно остывая, стремится перейти в состояние с наименьшей внутренней энергией. В данном подходе оптимизационная задача рассматривается как физическая система, а допустимое решение и значение целевой функции как состояние тела и его внутренняя энергия. В такой аналогии процесс отжига представляет собой процесс нахождения решения с минимальным значением целевой функции. Алгоритм имитации отжига начинает работу с некоторого начального решения и начальной температуры. При каждом значении температуры выполняется определенное число итераций, на которых из окрестности текущего решения случайным образом выбирается новое. Это решение становится текущим согласно определенному вероятностному закону, после чего температура уменьшается. Алгоритм продолжает свою работу до тех пор, пока температура не достигнет критического значения (температура остывания), либо не сработают другие критерии остановки.
К метаэвристикам также относятся алгоритмы муравьиной колонии, которым посвящена данная диссертация. В следующем разделе подробно описывается основная идея этих алгоритмов.
Алгоритмы муравьиной колонии для задачи op-медиане
В данном разделе предлагаются алгоритмы муравьиной колонии для задачи о р-медиане на минимум, постановка которой приведена в первой главе. Для описания алгоритмов будем пользоваться комбинаторной постановкой задачи, которая имеет следующий вид.
Решением s (допустимым решением) задачи о р-медиане будем называть булев вектор z размерности т такой, что Z{ = 1, если г Є Is, и 0 - в противном случае, где Is - множество открытых в решении s предприятий. Там, где это удобно, решением также будем называть множество Is открытых предприятий.
Введем вектор ак = (af), і Є /, с положительными координатами. Величину а\ будем называть уровнем феромона для г-го предприятия на итерации к алгоритма муравьиной колонии, і Є I.
Ниже будут описаны два алгоритма муравьиной колонии для задачи о р-медиане. Назовем их ACl-pm и АС2-рт. Будут предложены также два варианта алгоритма искусственного муравья antl-pm и ant2-pm. В главе 3 будет показано, что при определенных условиях на коэффициент испарения феромона при стремлении числа итераций к бесконечности вероятность нахождения оптимального решения алгоритмами ACl-pm и АС2-рт равна единице. Алгоритм АС2-рт представляет собой измененную схему ACl-pm, что позволяет доказать для него дополнительные асимптотические свойства.
Алгоритм искусственного муравья antl-pm представляет собой вероятностную модификацию жадного алгоритма спуска. Пусть Fs - множество открытых предприятий в текущем решении s на шаге г алгоритма antl-pm; АД - изменение целевой функции в результате закрытия предприятия г на шаге г. Так как при закрытии какого-либо предприятия значение целевой функции F не убывает [26], то АД О для всех і Є Ц.
Алгоритм ant2-pm в целом похож на алгоритм antl-pm, однако, в его схеме есть ряд существенных отличий. Алгоритм искусственного муравья ant2-pm, также как и antl-pm, представляет собой вероятностную модификацию жадного алгоритма спуска. Здесь Ц - множество открытых предприятий; АД - изменение целевой функции в результате закрытия предприятия г, г Є Ц.
На втором шаге итерации к алгоритма АС1-рт в качестве алгоритма искусственного муравья может служить либо алгоритм antl-pm, либо ant2-pm.
Критерием остановки работы алгоритма АС1-ргл может служить, например, предельное число итераций, точность по отношению к заданной нижней оценке целевой функции, число итераций без улучшения или выполнение условия, что все искусственные муравьи получают одни и те же решения.
Для описания алгоритма АС2-рт будем пользоваться обозначениями, введенными в п. 2.1.3. Опишем алгоритм. 0. Определяем начальный вектор уровня феромона а1; л. начальный рекорд / := со, Итерация к, к 1. 1. Строим L допустимых решений алгоритмом ИМ. 2. Выбираем среди этих решений лучшие по целевой функции. 3. Находим значения af+1, і Є І. 4. Если fk fk, то fk+1 = fk, sk+l = sk. Иначе fk+l = fk; sk+1 = sk. 5. Для ненулевых компонент вектора zk+1 полагаем ak+1 := ат[п. 6. Если выполняется критерий остановки, то конец работы алгоритма. Переходим на следующую итерацию, к := к + 1.
Отличие алгоритма АС2-рт от АСІ-pm заключается в том, что переопределение уровня феромона на каждой итерации происходит на основе решений, значение целевой функции которых строго меньше текущего рекорда fk. Особенностью также является то, что вне зависимости от того, произошла смена рекорда на итерации к или нет, ненулевым компонентам рекордного вектора zk назначается минимальный уровень феромона. Такой способ переопределения уровня феромона будем называть схемой сильного типа (аналог global-best).
В качестве искусственного муравья ИМ также могут использоваться либо antl-pm, либо ant2-pm.
На итерации к компоненты вектора ак+1 вычисляются по формуле (2.9). Критерием остановки работы алгоритма АС2-рт может служить, например, предельное число итераций, точность по отношению к заданной нижней оценке целевой функции или выполнение условия, что все искусственные муравьи получают одни и те же решения.
Одним из основных управляющих параметров алгоритмов antl-pm и ant2-pm является параметр Л, используемый в формулах (2.3) и (2.6) и влияющий на формирование множества Wr(X).
Рассмотрим алгоритм antl-pm. Легко заметить, что если Л 1, то на каждом шаге г искусственного муравья antl-pm множество Ц \ Wr(X) не пусто. Следовательно, согласно (2.4), на каждом шаге существует хотя бы одно предприятие і из множества Ц открытых предприятий, для которого привлекательность г}\, а значит и вероятность закрытия, равна 0. Это означает, что при Л 1 нет гарантии, что не существует таких входных данных, при которых вероятность нахождения оптимального решения искусственным муравьем antl-pm равна 0. Это также означает, что, в принципе, могут существовать примеры, на которых вероятность нахождения оптимума алгоритмом муравьиной колонии, использующим antl-pm в качестве искусственного муравья, равна 0 даже при "бесконечном" числе итераций. При этом, если Л = 1, то алгоритм искусственного муравья antl-pm имеет ненулевую вероятность нахождения любого допустимого решения, в том числе и оптимального.
В алгоритме ant2-pm указанный недостаток устранен, так как, в отличие от алгоритма antl-pm, в данном случае при любом 0 Л 1 вероятность закрытия любого предприятия г из множества Ц открытых предприятий не равна 0. Это означает, что при указанных Л есть гарантия того, что для произвольных входных данных алгоритм искусственного муравья ant2-pm имеет ненулевую вероятность нахождения любого допустимого решения, в том числе и оптимального.
Известные результаты о сходимости алгоритмов
Работы, посвященные вопросам сходимости алгоритмов муравьиной колонии, стали появляться относительно недавно. Причем все известные результаты относятся к упрощенным версиям фактически применяемых схем и не дают прямых рекомендаций для практического использования. Однако они представляют интерес для изучения общих свойств исследуемых алгоритмов.
Первые результаты в данном направлении получил Gutjahr [86], который работал с алгоритмами муравьиной колонии на графах, так называемыми Graph-Based Ant System (GBAS). В данных алгоритмах рассматривается граф задачи, причем каждое допустимое решение кодируется как путь в этом графе. Основным результатом работы [86] являлось доказательство того, что текущий рекорд в GBAS стремится к оптимальному решению с вероятностью больше либо равной 1-е. При этом было установлено, что є может быть сколь угодно малым при соответствующем выборе либо количества L искусственных муравьев на одной итерации к алгоритма GBAS, либо коэффициента испарения р. Однако, не было указано никаких границ на величины L или р, позволяющих определять конкретные значения е. Таким образом, сходимость была в некотором смысле "неконтролируемой", т.е., зная конкретные значения L или р, невозможно было узнать точную нижнюю границу вероятности сходимости алгоритма. При этом для доказательства сходимости требовалось, например, такое достаточно жесткое условие как единственность оптимального пути в графе.
Stiitzle и Dorigo в [114] рассмотрели другой алгоритм муравьиной колони - вариант алгоритма MAX-MIN Ant System, который предложили Stiitzle и Hoos в [115]. Авторы показали, что для этого варианта алгоритма, значение целевой функии текущего рекорда стремится к оптимальному значению целевой функии с вероятностью единица. Однако, это свойство сходимости относительно слабое, так как аналогичным свойством сходимости обладает обыкновенный алгоритм случайного поиска. Авторы также показали нижнюю границу вероятности того, что текущий рекорд является оптимальным решением.
Позднее Gutjahr в [85] показал, что для частного варианта GBAS, текущий рекорд сходится к оптимальному решению с вероятностью, равной единице. Кроме того, автором было доказано, что при соответствующих значениях параметров можно гарантировать, что искусственные муравьи будут стремиться находить оптимальные решения при увеличении числа итераций. Это улучшает все предыдущие результаты и доказывает свойство сходимости той же самой силы, которое доказал Hajek в [87] для алгоритма имитации отжига.
В статье [84] Gutjahr рассмотрел сходимость алгоритма муравьиной колонии для стохастических задач комбинаторной оптимизации.
В работе [61] рассмотрена сходимость алгоритмов Ant-density, Ant-quantity и Ant-cycle, предложенные в [77,78] для задачи коммивояжера. В предположении, что все муравьи начинают свой путь из одного города, доказано, что распределение агентов по городам стабилизируется с увеличением номера итерации. Однако, при этом не гарантируется, что найденное решение будет оптимальным.
Один из последних теоретических результатов для алгоритмов муравьиной колонии содержится в работе [109]. Авторами рассматривается один вариант муравьиной колонии, для которого доказывается сходимость за полиномиальное время в среднем.
Напомним некоторые обозначения. Пусть sk - лучшее найденное решение к началу итерации &, тогда zk и fk - булев вектор и значение целевой функции, соответствующее рекордному решению sk. Через sk обозначим лучшее решение, найденное на итерации к, тогда zk и fk - соответствующие булев вектором и значение целевой функции. Уровень феромона для каждого предприятия г Є / на итерации к хранится в векторе ак = (af),i Є I, где ак - положительное вещественное число. Величина oq является уровнем феромона для г-го предприятия. Параметр ат[п - положительное вещественное число, задающее минимальное возможное значение уровня феромона аг-, для всех і Є I. Коэффициент 0k представляет собой коэффициент испарения феромона на итерации к.
Определение. Решение s будем называть просмотренным, если оно было найдено в процессе работы алгоритма муравьиной колонии по крайней мере одним муравьем.
Простейшая задача размещения
В этом разделе представлены результаты вычислительного эксперимента для алгоритмов муравьиной колонии при решении простейшей задачи размещения.
Вычислительный эксперимент проводился с целью изучения влияния использования статистической информации (феромона), а также процедуры локального поиска на качество получаемых решений. Разработанные алгоритмы были реализованы на языке программирования C++ в виде комплекса программ. Расчеты проводилось на процессоре Athlon 1900 ХР с объемом оперативной памяти 256 Мб.
Эксперимент выполнялся для алгоритма ACl-splp со схемой переопределения феромона слабого типа и алгоритма AC2-splp со схемой переопределения феромона сильного типа. В обоих алгоритмах использовалась процедура локального поиска. Алгоритмы муравьиной колонии отличаются от обычных мультистартовых процедур тем, что у них есть "память", реализуемая посредством уровня феромона. Следовательно, важно было установить, влияет ли использование уровня феромона на качество получаемых решений. Поэтому для сравнения в эксперименте также использовался алгоритм multy-drop, представляющий собой муль-тистартовую процедуру с алгоритмом ant-splp без "памяти", т.е. муравьиную колонию без использования "феромона".
Алгоритмы запускались со следующими значениями параметров: максимальное количество итераций Tmax = 15; число искусственных муравьев на одной итерации L = 8; коэффициент испарения феромона /3 = 0,95; начальный уровень феромона а] = 1 для любого г; минимальный уровень феромона amin = 0,3; параметр q = 0,5. В алгоритме ant-splp параметр Л = 0,5.
Выполнялось по 30 запусков алгоритмов на каждой задаче. Решения, полученные разработанными алгоритмами, сравнивались между собой, а также с оптимальными решениями.
Использованные в эксперименте тестовые задачи были взяты из электронной библиотеки "Дискретные задачи размещения" [120]. Данная библиотека содержит примеры, трудные для некоторых классов точных алгоритмов, а также для алгоритмов локального поиска. В библиотеке имеются несколько сравнительно простых серий тестовых примеров.
Примеры с большим разрывом двойственности являются трудными для точных методов. Ниже описываются три серии таких задач Gap-A, Gap-B, Gap-C, заметно отличающиеся по трудоемкости для метода ветвей и границ и алгоритмов локального поиска.
1. Серия Gap—А. Примеры из серии Gap-A являются наиболее легкими в ряду Gap-A, Gap-B, Gap-C. Разрыв двойственности для них в среднем составляет около 26%. Размерность: 100 предприятий, 100 потребителей (га = п = 100). Стоимость открытия любого предприятия СІ равна 3000. Матрица транспортных затрат (Uj) имеет ровно 10 незапрещенных (небесконечных) элементов из множества {0, 1, 2, 3, 4} в каждом столбце. Это означает, что каждый потребитель имеет ровно десять потенциальных предприятий-поставщиков, которые выбираются случайным образом с равномерным распределением из всего множества предприятий. Оптимальное решение содержит 12 или 13 открытых предприятий.
2. Серия Gap-B. Данные примеры являются более трудными, чем задачи серии Gap-A, но уступают серии Gap-C, описанной ниже. Разрыв двойственности для задач данной серии в среднем составляет около 21%. Размерность: 100 предприятий, 100 потребителей (т = п = 100). Стоимость открытия любого предприятия СІ равна 3000. Матрица транспортных затрат (Uj) имеет ровно 10 незапрещенных (небесконечных) элементов из множества {0, 1, 2, 3, 4} в каждой строке. Это означает, что каждое предприятие имеет ровно десять потенциальных клиентов, которые выбираются случайным образом с равномерным распределением из всего множества потребителей. Оптимальное решение содержит 14 или 15 открытых предприятий.
3. Серия Gap-C. Задачи серии Gap-C являются наиболее трудными среди Gap-A, Gap-B, Gap-C. Разрыв двойственности для них в среднем
составляет около 28%. Размерность: 100 предприятий, 100 потребителей (т = п = 100). Стоимость открытия любого предприятия с, равна 3000. Матрица транспортных затрат (tij) имеет ровно 10 незапрещенных (небесконечных) элементов из множества {0, 1, 2, 3, 4} в каждом столбце и каждой строке. Это означает, что каждый потребитель имеет ровно десять потенциальных предприятий-поставщиков, а каждое предприятие имеет ровно десять потенциальных клиентов. И первые, и вторые выбираются случайным образом с равномерным распределением из соответствующих множеств. В оптимальном решении содержится 14 открытых предприятий.
4. Серия РС7. Примеры из данного класса построены с помощью совершенных бинарных кодов с расстоянием 3. Через Вк обозначим множество булевых векторов длины к. Бинарным кодом длины к называется произвольное непустое подмножество множества Вк. Совершенный бинарный код с расстоянием к - это подмножество С С Вк, \С\ = -щ такое, что расстояние Хэмминга d(ci, С2) 3 для всех Сі, С2 Є С, С\ ф с2. Данные коды существуют для к = 2Г — 1, где г 1 - целое число. Оптимальное решение содержит п/(к -f- 1) открытых предприятий и соответствует одному из совершенных кодов, число которых растет экспоненциально с ростом к. Рассматриваются тестовые примеры для k = 7, п = т= 128.
5. Серия СВ4. Примеры из данного класса сформированы с по мощью шахматной доски размера Зк х Зк. Края доски склеены так, чтобы образовывался тор, следовательно, каждая клетка доски име ет 8 соседних. Например, клетка (1,1) имеет следующих соседей: (1,2), (1, г), (2,1), (2,2), (2, г), (г, 1), (г, 2), (г, г), где г = Зк. Каждый эле мент г Є I соответствует одной клетке шахматной доски, т.е. простейшая задача размещения имеет п = 9к2 предприятий, причем I = J. Предпри ятие і может обслуживать потребителя j, если соответствующие клетки шахматной доски имеют хотя бы одну общую точку, т.е.
Похожие диссертации на Разработка и исследование алгоритмов муравьиной колонии для решения задач оптимального размещения предприятий
