Многомерная задача о рюкзаке: новые методы решения

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

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

Сформулируем многомерную задачу о рюкзаке [4]: nn f (X) = £ cjxj ^ max , £ ajXj < b ,    (1)

j = 1                   j = 1

X j ^G {0,1} , j = 1, 2,..., n , i = 1, 2,..., m .

Предполагается, что   Cj > 0 ,   0 < ay < bi, j = 1, 2,..., n , i = 1, 2,..., m .

Приведем экономическую интерпретацию многомерной задачи о рюкзаке [4]. Пусть имеется n проектов и для их реализации задан вектор ресурсов b = (b1, b2,..., bm), bi > 0 . Обозначим через aj > 0 количество единиц ресурса типа i, необходимое для реализации проекта с номе-рому, при этом хотя бы для одного ресурса s выполнено n условие ^ asjX > bs , т. е. реализация всех проектов j=1

невозможна. Пусть Cj > 0 , j = 1, 2,..., n -прибыль, полученная при реализации проекта/. Требуется выбрать для реализации набор проектов с максимальной суммарной прибылью:

Г 0, еслО проект j нереалОзоется,

X j = 1

^J [ 1, еслО проект j реалОзоется.

Многомерная задача о рюкзаке является NP-трудной задачей, имеющей много практических приложений, таких как размещение процессоров в распределенных системах, размещение грузов, распределение бюджетных средств и т. д. [5]. Как известно из теории вычислительной сложности алгоритмов, время нахождения точного решения NP-трудной задачи является величиной, экспоненциально зависящей от размерности задачи. На практике размерность задачи исчисляется сотнями и тысячами переменных. Приближенные алгоритмы, в том числе и муравьиные, позволяют найти субоптимальные решения за полиномиальное время.

Стратегия поиска оптимального решения с помощью алгоритмов муравьиных колоний хорошо соотносится с решением задачи о многомерном рюкзаке [6].

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

Для этого выполним некоторые преобразования. Построим сеть по следующим правилам [7]: по оси абсцисс будем последовательно откладывать номера предметов, по оси ординат - их вес. Из каждой точки (начиная с точки (0;0)) выходят две дуги - горизонтальная (соответствующая альтернативе «не брать предмет») и наклонная (со- ответствующая альтернативе «взять предмет»), вертикальная проекция которой равна весу предмета. Длины наклонных дуг положим равными ценности предметов, длины горизонтальных дуг - нулю. Полученная сеть (конечная вершина является фиктивной и вес любой дуги, соединяющей ее с другими вершинами, равен нулю) обладает следующими свойствами: любому решению задачи (1) соответствует некоторый путь в этой сети; любому пути соответствует некоторое решение задачи. Таким образом, задача свелась к нахождению пути максимальной длины, для чего можно использовать алгоритмы муравьиных колоний.

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

• -    случайность;

• -    многократность;

• -    положительная обратная связь;

• -    отрицательная обратная связь.

Муравьи используют два способа передачи информации. Прямой - обмен пищей, мандибулярный, визуальный и химический контакты. И не прямой - стигмер-жи (stigmergy). Стигиержи - это разнесенный во времени тип взаимодействия, когда один субъект взаимодействия изменяет некоторую часть окружающей среды, а остальные используют информацию об ее состоянии позже, когда находятся в ее окрестности. Биологически стигмержи осуществляется через феромон (pheromone) - специальный секрет, откладываемый как след при перемещении муравья.

Феромон - достаточно стойкое вещество, он может восприниматься муравьями несколько суток. Чем выше концентрация феромона на тропе, тем больше муравьев будет по ней двигаться. Со временем феромон испаряется, что позволяет муравьям адаптировать свое поведение под изменения внешней среды. Распределение феромона по пространству передвижения муравьев является своего рода динамически изменяемой глобальной памятью муравейника. Любой муравей в фиксированный момент времени может воспринимать и изменять лишь одну локальную ячейку этой глобальной памяти [8].

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

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

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

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

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

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

Для каждого муравья решение взять предмет зависит от трех составляющих: памяти муравья (tabu list), значимости и виртуального следа феромона.

Tabu list (память муравья) - это список взятых муравьем предметов, которые брать еще раз нельзя. Используя этот список, муравей гарантированно не возьмет один и тот же предмет дважды. В этот список должны быть включены те предметы, взяв которые мы нарушим одно из ограничений задачи. Очевидно, что tabu list возрастает по мере того, как муравей набирает предметы, и обнуляется в начале каждой итерации алгоритма. Также очевидно, что этот список должен постоянно обновляться. Когда в tabu list входят все предметы, муравей прекращает набор предметов. Обозначим через J k список предметов, которые муравью к можно взять на итерации t . Очевидно, что J k является дополнением к tabu list.

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

cj

П j = — [9]. Когда ограничений в задаче становится боль-aj ше одного, значимость для каждого предмета определить однозначно уже нельзя.

Был предложен следующий вариант расчета значимости:

ⁿ j =

c j

^m a_ij ^b b i

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

После того, как каждый муравей набрал свой рюкзак, происходит изменение следа феромона на предметах. Способ изменения следа феромона зависит от модели муравьиного алгоритма [1].

Ant-density - в этой модели количество феромона, оставляемого муравьем на предмете, является постоянной величиной:

В этом случае мы суммируем коэффициенты по каждому i = 1... т, где т - число ограничений задачи. Нормирование на коэффициенты b i введено для масштабиро

^Ат j , k ( t ) =

q ,

0,

if j e T k ( t ) , if j e T k ( t ) .

вания величин к величинам одного порядка.

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

Ant-cycle - в этой модели количество феромона, оставляемого муравьем на предмете, зависит от общей ценности f (T k ( t )) этого набора предметов:

точным для нахождения оптимального решения.

Виртуальный след феромона на предмете. / представляет подтвержденное муравьиным опытом желание взять предмет. /. В отличие от значимости след феромона является более глобальной и динамичной информацией - она изменяется после каждой итерации алгоритма, отражая приобретенный муравьями опыт. Количество виртуального феромона на предмете, / на итерации t обозначим через ^т j ⁽ t ) .

Важную роль в муравьиных алгоритмах играет вероятностно-пропорциональное правило, определяющее вероятность для k-го муравья взять предмету на итерации t :

^Ат j , k ( t ) = '

q - f ( T k ( t ) ) , 0,

if j e T k ( t ) , if j e T k ( t ) ,

где T k ( t ) - набор предметов у муравья k на итерации t ; f ( T k ( t ) ) - ценность этого набора; q - регулируемый

параметр.

Для исследования всего пространства решений необходимо обеспечить испарение феромона - уменьшение

во времени количества отложенного на предыдущих итерациях феромона [10]. Обозначим коэффициент испарения феромона через p e [0,1]. Тогда правило обновления феромона примет вид т j (t +1) = (1 - p) -т j (t) + Ат j (t),

P j , k ( t ) = '

[j t) I" |nj Г' b [j t)]“-[nj ]e je Jk if j e Jk, (2)

0, if j 6 Jk, где аир- два регулируемых параметра, задающих вес следа феромона и значимость при выборе маршрута. Заметим, что если а = 0 или р ^ ^, то мы получаем муравьиный алгоритм, которому в классической теории оптимизации соответствует жадный (greedy) алгоритм.

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

Можно заметить, что вероятности выбора того или иного предмета зависят от трех параметров: значимости предметов, которые являются постоянными величинами в ходе решения задачи, следа феромона, значение которого постоянно обновляется, и tabu list - чем больше предметов в этот список входят, тем больше вероятность у оставшихся предметов быть выбранными.

K где Ат j (t) = b Ат j (t) ,K-количество муравьев в колонии. k=1

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

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

Подготовительные процедуры:

• 1)    инициализация параметров алгоритма муравьиных колоний: а , в , p и q , m , т о , N - число итераций алгоритма;

• 2)    задание следа феромона т о на предметах, расчет значимости предметов n j ■

Основной цикл (повторяется N раз). Начало:

• 3)    выбор каждым муравьем колонии набора предметов по вероятностно-пропорциональному правилу (2). Муравей набирает предметы, пока его tabu list не будет включать список всех предметов. Как только все муравьи

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

• 4)    обновление следа феромона на предметах по заранее выбранной схеме: ant-density или ant-cycle. Испарение феромона;

• 5)    поиск лучшего решения f _max на итерации, срав^{нение с наил}у^чшим f * ^{: если} f _n ax >  f * ^то f * = f max и переход к шагу 3.

Конец : полученное значение f * является решением задачи.

Для ускорения сходимости оптимизационной процедуры можно ввести так называемых элитных муравьев [10]. Элитный муравей на каждой итерации усиливает наилучшее решение f , достигнутое с начала работы алгоритма. Количество феромона Ат j , откладываемого на предметах, дающих наилучшее решение, составляет Ат j = е • Ат j , _е , где е - количество элитных муравьев,

^Ат j , _е -количество феромона, откладываемого одним элитным муравьем в соответствии с формулами (3) или (4). Дополнительное количество феромона побуждает муравьев исследовать предметы, которые содержатся в наилучших решениях.

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

Были проведены экспериментальные исследования построенного алгоритма, за основу которых были приняты результаты, полученные С. Фидановой в работе [11]. В данной работе С. Фиданова исследовала свой муравьи-

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

п X т heuristicl heuristic2 heuristic3 Ant-МКР 100 X 5 21640 22224 23984 24285 100 X 5 21175 22542 24143 24086 100 X 5 20477 22177 23515 23410 100 X 5 21443 22390 22874 23389 100 X 5 22169 23246 23263 23772 100 X 5 20675 22427 24523 24400 100 X 5 22068 24286 25177 25448 100 X 5 21432 21771 23204 23243 100 X 5 20501 22832 23762 23930 100 X 5 22006 22893 24208 24186 100 X 5 39510 41700 42705 42705 100 X 5 40700 41804 42445 42442 100 X 5 40329 40922 41435 41662 100 X 5 41390 43856 44911 44867 100 X 5 39253 40979 42025 42128 100 X 5 40268 42130 42671 42815 100 X 5 38138 40307 41776 42774 100 X 5 41406 43304 44559 44892 100 X 5 40029 42015 43122 43104 100 X 5 41968 43135 44364 44529 100 X 5 58178 58660 59798 59822 100 X 5 60031 60913 61821 62081 100 X 5 58109 59117 59694 59734 100 X 5 58592 59633 60479 60417 100 X 5 59144 60050 60954 61000 100 X 5 57218 58127 58695 58919 100 X 5 59464 60193 61406 61461 100 X 5 60180 60360 61520 61421 100 X 5 57836 58659 59121 59311 100 X 5 58186 59060 59864 59929 Среднее 40117,17 41390,4 42400,67 42538,73 ный алгоритм с 3 различными способами расчета значимости предметов: heuristicl, heuristic2 иheuristic3. В качестве тестовых задач были выбраны 30 задач из библиотеки «OR-Library». Размерность представленных задач -100 переменных, количество ограничений - 5. Параметры алгоритма были выбраны такие же, как и в исследованиях С. Фидановой: количество муравьев в колонии m = 100, количество итераций муравьиного алгоритма N = 200 . Остальные параметры: а = 2 , в = 1, p = 0,3 и q = 1, Т0 = 0,01. Сравнение муравьиных алгоритмов С. Фидановой и алгоритма Ant-MKP, описанного в настоящей работе, представлено в таблице. Жирным шрифтом в каждой строке выделено лучшее значение целевой функции среди муравьиных алгоритмов. Построенный алгоритм показал хорошие результаты, в большинстве задач он не уступает муравьиному алгоритму С. Фидановой и даже находит решения, с большим значением целевой функции.