NUMERICAL INVESTIGATION OF ANT-ALGORITHMS FOR MANY-DIMENSIONAL KNAPSACK PROBLEM

详细

The ant-algorithms numerical investigations results are presented. Recommendations on the algorithms parameters choice are given.

全文:

Многомерная задача о рюкзаке является NP- трудной задачей. Приближенные алгоритмы, в том числе и ант-алгоритмы, позволяют найти субопти- мальные решения для нее за полиномиальное время. Сформулируем многомерную задачу о рюкзаке [1]: задачи о многомерном рюкзаке [2]. Можно показать, что задача нахождения туристом оптимального набора предметов и задача поиска кратчайшего пути колони- ей муравьев практически совпадают. Для этого выполним некоторые преобразования. n n Построим сеть по следующим правилам [3]. По оси f ( X ) = åc j xj ® max , å aij xj £ bi , (1) абсцисс будем последовательно откладывать номера j =1 j =1 предметов, по оси ординат - их вес. Из каждой точки xj Î{0,1} , j = 1, 2, ..., n , i = 1, 2, ..., m . (начиная с точки (0; 0)) выходят две дуги - горизонтальная (соответствующая альтернативе «не брать Предполагается, что j = 1, 2, ..., n , i = 1, 2, ..., m. c j > 0 , 0 £ aij £ bi , предмет») и наклонная (соответствующая альтернати- ве «взять предмет»), вертикальная проекция которой Стратегия поиска оптимального решения с помо- щью ант-алгоритмов хорошо соотносится с решением равна весу предмета. Длины наклонных дуг положим равными ценности предметов, длины горизонтальных дуг - нулю. Полученная сеть (конечная вершина является фиктивной и вес любой дуги, соединяющей ее с другими вершинами, равен нулю) обладает следую- щими свойствами: любому решению задачи (1) соот- ветствует некоторый путь в этой сети; любому пути соответствует некоторое решение задачи. Таким обра- зом, задача свелась к нахождению пути максимальной длины, для чего можно использовать алгоритмы муопыт. Количество виртуального феромона на предме- те j на итерации t обозначим через t j (t) . Важную роль в муравьиных алгоритмах играет ве- роятностно-пропорциональное правило, определяю- щее вероятность для k -го муравья взять предмет j на итерации t: a b равьиных колоний. Основу «социального» поведения муравьев со- ï ì éët j (t)ùû image = ï ét a b k éëhj ùû , если j Î J , ù éh ù ставляет самоорганизация. Самоорганизация является результатом взаимодействия четырех компонентов: Pj , k (t) í å ë ï jÎ Jk j (t)û ë j û (2) случайность, многократность, положительная обрат- ная связь, отрицательная обратная связь. Ант-алгоритмы основаны на имитации природных механизмов самоорганизации муравьев, использова- ние которых иллюстрируется ниже на примере задачи о рюкзаке. Многократность взаимодействия реализуется ите- рационным поиском оптимального набора предметов в рюкзаке одновременно несколькими муравьями. За одну итерацию алгоритма каждый муравей набирает полный рюкзак. Для задачи о рюкзаке положительная обратная î ï 0, если j Ï Jk , где a и b - два регулируемых параметра, задающих веса следа феромона и значимости при выборе мар- шрута. После того, как каждый муравей набрал свой рюк- зак, происходит изменение следа феромона на пред- метах. Способ изменения следа феромона зависит от модели муравьиного алгоритма [4]. Ant-density - в этой модели количество феромона, оставляемого муравьем на предмете, является посто- янной величиной: связь реализуется следующим стохастическим прави- ìq, если j ÎT (t), Dt (t) = k (3) лом: вероятность положить предмет муравьем в рюкj , k í î0, если j ÏTk (t). зак пропорциональна количеству феромона на этом предмете. Применение такого вероятностного правила обеспечивает реализацию и другой составляющей са- моорганизации - случайности. Количество отклады- Ant-cycle - в этой модели количество феромона, оставляемого муравьем на предмете, зависит от общей ценности f(Tk(t)) этого набора предметов: ваемого муравьем феромона на предмете пропорцио- ìq × f (Tk (t)), если Dt (t) = j Î Tk (t), (4) нально его важности. Чем важнее предмет, тем больj , k í î0, если j Ï Tk (t), ше феромона будет отложено на нем, и тем больше муравьев будут использовать его при синтезе своего где Tk (t) - набор предметов у муравья k на итерации набора предметов. t; f (Tk (t)) - ценность этого набора; q - регулируемый Использование только положительной обратной связи приводит к преждевременной сходимости реше- ний - к случаю, когда все муравьи выбирают одни и те же предметы. Для избегания этого используется отрицательная обратная связь - испарение феромона. параметр. Для исследования всего пространства решений не- обходимо обеспечить испарение феромона - умень- шение во времени количества отложенного на преды- дущих итерациях феромона [5]. Обозначим коэффи- Для каждого муравья решение взять предмет завициент испарения феромона через p Î[0, 1] . Тогда прасит от трех составляющих: памяти муравья (tabu list), значимости и виртуального следа феромона. Tabu list (память муравья) - это список взятых му- равьем предметов, которые брать еще раз нельзя. Исвило обновления феромона примет вид t j (t + 1) = (1- p)t j (t) + Dt j (t), K j å j ,k пользуя этот список, муравей гарантированно не возьмет один и тот же предмет дважды. В этот список где Dt (t) = Dt k =1 (t); K - количество муравьев в должны быть включены те предметы, взяв которые мы нарушим одно из ограничений задачи. Значимость ( h j ) - это локальная статическая ин- формация, выражающая эвристическое желание мура- вья взять предмет. Данная мера зависит от некоторых характеристик предмета, таких как масса, объем, цена и является величиной постоянной для каждой кон- кретной задачи в отличие от tabu list и виртуального следа феромона. Виртуальный след феромона на предмете j пред- ставляет подтвержденное муравьиным опытом жела- ние взять предмет j. В отличие от значимости след феромона является более глобальной и динамичной информацией - она изменяется после каждой итера- ции алгоритма, отражая приобретенный муравьями колонии. В начале работы алгоритма оптимизации количе- ство феромона принимается равным небольшому по- ложительному числу t0. Количество муравьев в коло- нии остается постоянным на протяжении выполнения алгоритма. Многочисленная колония приводит к бы- строму усилению субоптимальных решений, а когда муравьев мало, возникает опасность потери коопера- тивности поведения через ограниченное взаимодейст- вие и быстрое испарение феромона. Число муравьев можно назначить равным произведению числа пред- метов и числа ограничений. Последовательность шагов ант-алгоритма выгля- дит следующим образом: Инициализация параметров алгоритма муравьи- ных колоний: a, b, p и q, m, t0, N - число итераций алгоритма. Задание следа феромона t0 на предметах, расчет значимости предметов hj. Выбор каждым муравьем колонии набора предме- тов по вероятностно-пропорциональному правилу (2). Муравей набирает предметы, пока его tabu list не будет включать список всех предметов. Как только все муравьи колонии набрали свои рюкзаки, вычисля- ем ценность и переходим к шагу 4. Обновление следа феромона на предметах по за- ранее выбранной схеме: ant-density или ant-cycle. Ис- парение феромона. Поиск лучшего решения fmax на итерации, срав- нение с наилучшим f*: если fmax > f*, то f* = fmax и пере- ход к шагу 3. Конец: полученное значение f* является решени- ем задачи. Численные исследования ант-алгоритмов проводи- лись на тестовых примерах. В первом примере число переменных было 10, число ограничений - 3. Посмот- рим, как результат зависит от параметров алгоритма. Пусть число муравьев К = 15, число итераций N = 10, тип алгоритма определения следа феромона - Ant-density, число запусков алгоритма (прогонов) равно 100. Общее число наборов предметов равно 150 (из 1 024). Анализ табл. 1 показывает, что значения парамет- ров a и b значительно влияют на результат, причем значение параметра a существеннее. Наилучшее зна- чение при фиксированных остальных: a = 0,5, b = 0,5, хотя b может быть и немного больше, результат от этого практически не изменится. Величина q незначительно в данном случае влияет на результат (табл. 2). Более значительно влияет па- раметр p. Для данной задачи оптимальное значение р = 0,3. Алгоритм также находит результат на второй, третьей итерации. Как видно, жадный a = 0 стохасти- ческий алгоритм на малой размерности также дает удовлетворительный результат 99 % из ста прогонов. По совокупности данных (табл. 3) можно сделать вывод о том, что число элитных муравьев можно для задачи выбирать произвольным, например е = 3. Судя по времени и итерации, на которой найдено опти- мальное решение, лучше выбрать начальный объем феромона t0 = 2. Изменим в тип алгоритма на Ant-cycle и посмотрим на результаты решения задачи при прочих равных условиях (табл. 4-6). Зависимость работы алгоритма от a и b Таблица 1 № п/п Сочетание параметров Процент верного решения Время выполнения всех прогонов, с Средний номер (вещ.) итерации с лучшим решением a b q p t0 e 1 1 1 0,1 0,3 0,1 3 93 2 1,68 2 2 1 0,1 0,3 0,1 3 65 2 1,22 3 1 2 0,1 0,3 0,1 3 88 2 1,37 4 2 2 0,1 0,3 0,1 3 71 2 1,68 5 0,5 0,5 0,1 0,3 0,1 3 100 2 2,02 6 0,1 0,1 0,1 0,3 0,1 3 93 2 3,29 7 0,5 1 0,1 0,3 0,1 3 100 3 1,75 8 0,5 2 0,1 0,3 0,1 3 99 3 1,66 9 0,5 3 0,1 0,3 0,1 3 95 2 1,57 10 0,5 4 0,1 0,3 0,1 3 93 2 2,05 11 1 0,5 0,1 0,3 0,1 3 89 2 2,16 12 2 0,5 0,1 0,3 0,1 3 48 3 1,29 Зависимость работы алгоритма от q и p Таблица 2 № п/п Сочетание параметров Процент верного ре- шения Время выполнения всех прогонов, с Средний номер (вещ.) итерации с лучшим решением a b q p t0 e 1 0 0,5 0,1 0,3 0,1 3 99 2 2,16 2 0,5 0,5 0,1 0,3 0,1 3 100 3 2,07 3 0,5 0,5 0,5 0,3 0,1 3 100 2 2,14 4 0,5 0,5 1 0,3 0,1 3 100 2 2,26 5 0,5 0,5 5 0,3 0,1 3 98 2 2,35 6 0,5 0,5 0,1 0 0,1 3 99 2 2,43 7 0,5 0,5 0,1 0,5 0,1 3 99 3 2,25 8 0,5 0,5 0,1 1 0,1 3 89 2 1,93 Зависимость работы алгоритма от начального количества феромона t0 и количества муравьев е Таблица 3 № п/п Сочетание параметров Процент верного решения Время выполнения всех прогонов, с Средний номер (вещ.) итерации с лучшим ре- шением a b q p t0 e 1 0,5 0,5 0,1 0,3 0,1 3 100 3 2,07 2 0,5 0,5 0,1 0,3 0,1 5 100 2 2,1 3 0,5 0,5 0,1 0,3 0,1 9 100 2 2,29 4 0,5 0,5 0,1 0,3 0,1 1 100 3 2,75 5 0,5 0,5 0,1 0,3 0 5 100 3 2,71 6 0,5 0,5 0,1 0,3 0,5 5 100 3 2,09 7 0,5 0,5 0,1 0,3 2 5 100 2 2 8 0,5 0,5 0,1 0,3 5 5 100 3 2,26 Зависимость работы алгоритма от a и b Таблица 4 № п/п Сочетание параметров Процент верного решения Время выполнения всех прогонов, с Средний номер (вещ.) итера- ции с лучшим решением a b q p t0 e 1 1 1 0,1 0,3 0,1 3 97 3 1,83 2 2 1 0,1 0,3 0,1 3 76 3 1,41 3 1 2 0,1 0,3 0,1 3 93 2 1,35 4 2 2 0,1 0,3 0,1 3 75 2 1,06 5 0,5 0,5 0,1 0,3 0,1 3 100 3 2,21 6 0,1 0,1 0,1 0,3 0,1 3 97 2 3,6 7 0,5 1 0,1 0,3 0,1 3 99 2 1,76 8 0,5 2 0,1 0,3 0,1 3 99 2 1,49 9 0,5 3 0,1 0,3 0,1 3 97 2 1,65 10 0,5 4 0,1 0,3 0,1 3 84 2 1,93 11 1 0,5 0,1 0,3 0,1 3 97 2 2,08 12 2 0,5 0,1 0,3 0,1 3 79 3 1,55 Зависимость работы алгоритма от q и p Таблица 5 № п/п Сочетание параметров Процент вер- ного решения Время выполнения всех прогонов, с Средний номер (вещ.) итера- ции с лучшим решением a b q p t0 e 1 0,5 0,5 0,1 0,3 0,1 3 99 2 2,22 2 0,5 0,5 0,5 0,3 0,1 3 98 2 2,14 3 0,5 0,5 1 0,3 0,1 3 99 3 2,34 4 0,5 0,5 5 0,3 0,1 3 96 3 2,69 5 0,5 0,5 0,1 0 0,1 3 99 3 2,48 6 0,5 0,5 0,1 0,5 0,1 3 97 2 2,18 7 0,5 0,5 0,1 1 0,1 3 94 2 1,82 Зависимость работы алгоритма от начального количества феромона t0 и количества муравьев e Таблица 6 № п/п Сочетание параметров Процент вер- ного решения Время выполнения всех прогонов, с Средний номер (вещ.) итерации с лучшим решением a b q p t0 e 1 0,5 0,5 0,1 0,3 0,1 3 100 3 2,53 2 0,5 0,5 0,1 0,3 0,1 5 100 3 2,29 3 0,5 0,5 0,1 0,3 0,1 9 100 3 2,11 4 0,5 0,5 0,1 0,3 0,1 1 100 3 2,23 5 0,5 0,5 0,1 0,3 0 5 99 2 2,71 6 0,5 0,5 0,1 0,3 0,5 5 100 3 2,18 7 0,5 0,5 0,1 0,3 2 5 100 2 2,19 8 0,5 0,5 0,1 0,3 5 5 100 3 1,98 В среднем алгоритм типа Ant-Cycle сработал не- сколько лучше алгоритма с типом Ant-Density. Зако- номерности между параметрами a, b и результатами алгоритма остались прежними: a = 0,5, b = 0,5. Алгоритм сработал в среднем на уровне алгоритма Ant-density. Оптимальные параметры также приблизительно совпадают q = 0,1, p = 0,3. Алгоритм типа Ant-cycle в целом сработал на уровне Ant-density. Результаты отличаются по значе- нию параметров: e = 9, t0 = 5. Анализ аналогичных результатов для тестовых задач с 20 переменными и тремя ограничениями и 24 переменными и 6 ограничениями показал значительное влияние параметров a и b на результат, лучшие значения для обеих задач: a = 1, b = 2. Вели- чины q и p незначительно в данном случае влияют на результат. Число элитных муравьев для задач можно выбирать произвольным, например e = 5, начальный объем феромона лучше выбрать небольшим t0 = 0,1. Результаты алгоритма типа Ant-cycle несколько лучше результатов алгоритма Ant-density, что каса- ется выводов по параметрам, то они остаются без изменений. Для задачи с 20 переменными число муравьев K = 20, число итераций N = 10, тип алгоритма опреде- ления следа феромона - Ant-density, число запусков алгоритма (прогонов) - 100. Общее число наборов предметов - 200 (из 1 048 576). Время выполнения всех прогонов - 4-5 с. Для задачи с 24 переменными и шестью ограниче- ниями число муравьев K = 30, число итераций N = 10, тип алгоритма определения следа феромона - Ant- density, число запусков алгоритма (прогонов) - 100. Общее число наборов предметов - 300 (из 16 777 216, что составляет всего 0,001 788 %). Ант-алгоритмы тестировались также на задачах с 42 переменными и двумя ограничениями - точное решение найдено за 18 с, с 39 переменными и 5 огра- ничениями - точное решение найдено за 291 с и на задаче с 50 переменными и пятью ограничениями - точное решение найдено за 68 037 с. По результатам численных исследований можно дать следующие рекомендации по применению ант- алгоритмов на реальных данных в условиях, когда очень трудно решить задачу полным перебором вари- антов и истинное решение нам неизвестно. Относительно типа модели вычисления следа феромона на взятых предметах можно сказать, что обе модели: и Ant-density, и Ant-Cycle, - показали хорошие результаты. Однако при правильном подборе ко- эффициентов вторая модель, как правило, показывает лучшие результаты. Выбор параметров a и b существенно влияет на результат работы алгоритмов. Чаще всего для боль- шеразмерных задач оптимальными являются значения a = 1, b = 2. Остальные параметры не так значительно влияют на результат, однако их влияние на сходи- мость алгоритма также существенно. Главное, выби- рать их значения в разумных пределах. Рекомендуе- мые значения для параметров алгоритмов следующие: q = 1, p = 0,3, t0 = 0,1 ,e = 5.