Покрытие методом муравьиной колонии

Размещено на http://www.allbest.ru/

ПОКРЫТИЕ МЕТОДОМ МУРАВЬИНОЙ КОЛОНИИ

О.Б. Лебедев (lbk@tsure.ru)

Таганрогский Технологический Институт Южного Федерального Университета, Таганрог

Аннотация

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

решение колония муравьиный

Введение

Задача о покрытии множествами [Андерсон, 2003] сводится к нахождению покрывающего набора минимальной стоимости, является NP-полной. В течение последних лет были предложены различные подходы к решению проблемы покрытия. Главным образом это алгоритмы, основанные на эвристиках, обеспечивающих получение приемлемого результата за полиномиальное время [Андерсон, 2003], [Cordone et al., 2001], [Coudert , 1996], [Деньдобренко и др., 2007]. Тем не менее, возросшие сложность решаемых задач и требования к качеству решения делают актуальной разработку новых более эффективных методов. Сравнение и анализ разработанных алгоритмов покрытия (последовательных, итерационных и т.д.) показывает, что для создания эффективного алгоритма покрытия, отвечающего современным требованиям, необходимы новые технологии и подходы.

В последние годы интенсивно разрабатывается научное направление, объединяющее математические методы, в которых заложены принципы природных механизмов принятия решений [Курейчик и др., 2009], [Мazumder et al., 2003], [Лебедев и др., 2009], [Engelbrecht, 2005], [МакКоннелл, 2004], [Курейчик и др., 2006]. Основу поведения муравьиной колонии составляет самоорганизация, обеспечивающая достижения общих целей колонии на основе низкоуровневого взаимодействия благодаря которому, в целом, колония представляет собой разумную многоагентную систему [Dorigo et al., 2004]. В работе используется представление задачи покрытия в виде адаптивной муравьиной системы, на основе сочетания принципов самообучения и самоорганизации.

1. Постановка задачи

Пусть задана функциональная схема S = {s_i | i=1,2,…,w}, состоящая из элементов s_i и множество E ={e_i|i=1,2,…,n} типов элементов, образующих покрываемую функциональную схему. Количественный состав схемы по типам элементов опишем вектором B = {b_i | i=1,2,…,n}, где b_i - число элементов типа e_i , входящих в состав схемы. Кроме того, задан набор покрывающих ячеек H = {h_j | j=1,2,…,m}. Каждая ячейка имеет свой набор элементов из E. Элементы внутри ячейки между собой не соединены. Количественный состав ячеек выразим с помощью матрицы A = ||a_ij||_nm , где a_ij - число элементов типа e_i в ячейке типа h_i. Вектор C = {c_j | j=1,2,…,m} конкретизирует для каждой ячейки h_j её стоимость c_j. Схема считается покрытой ячейками из набора H, если каждый элемент функциональной схемы реализуется элементами из состава выбранных ячеек. Введём целочисленную переменную x_j, определяющую число ячеек типа h_j, входящих в покрывающий набор. Тогда задача покрытия формулируется следующим образом:

минимизировать

, (1.1)

при ограничениях F

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

2.Формирование пространства решений

Для удобства изложения будем осуществлять процесс формирования пространства решений на примере. Пусть покрываемая схема составлена из элементов трех типов: E = {e₁,e₂,e₃}. Количественный состав схемы задается вектором B = {10,30,20}. Набор покрывающих ячеек H = {h₁,h₂,h₃,h₄,h₅}. Матрица A, представлена на Рис.1.

Рис.1. Матрица A, описывающая количественный состав ячеек

Введём матрицу P, которая отражает граничные требования по количественному составу элементов, покрываемых ячейками каждого типа, P =||p_ij||_nm, где p_ij - минимальное число элементов типа e_i , которое обязательно должно быть покрыто ячейками типа h_j, p_ij 0, p_ij - целое число. При этом для реализации полного покрытия всех элементов в соответствии с требованиями матрицы P необходимо выполнение ограничений:

(2.1)

Для вышеприведённого примера один из возможных вариантов матрицы P имеет вид, представленный на Рис.2.

Рис.2. Матрица граничных требований P

Матрица P однозначно соответствует покрывающему набору ячеек, который формируется следующим образом. Сначала строится матрица D = ||d_ij||_nm . Элемент матрицы d_ij - целое число, которое определяется как большее целое от p_ij/a_ij и фактически равно минимальному числу ячеек типа h_j , необходимых для покрытия p_ij элементов типа e_i. Затем в пределах каждого j-го столбца матрицы D находится максимальное число d_jmax, ( i) [d_jmax d_ij]. Оно является минимальным числом x_j=d_jmax ячеек типа h_j , гарантированно обеспечивающих покрытие элементов j-го столбца матрицы P.

Для рассматриваемого примера матрица D и покрывающий набор X имеют вид, представленный на Рис.3.

Рис.3. Матрица D и покрывающий набор X

Общее число ячеек в покрывающем наборе N_я=25. Общее число N_i элементов типа e_i , входящее в состав покрывающего набора ячеек определяются как N₁=51; N₂=46; N₃=41. Общее число элементов, образующих покрывающий набор, N_э= N₁+ N₂+ N₃ =138. Итак, матрице P, значения элементов которой удовлетворяют ограничениям (2.1), соответствует одно решение. Таким образом, матрица P является символьным представлением решения задачи покрытия множествами. В работе пространство решений представляется множеством матриц P. Поиск решения сводится к поиску такой матрицы P, т.е. к поиску совокупности таких значений элементов p_ij матрицы P, которые оптимизируют показатель качества (критерий).

3. Организация поисковых процедур на основе моделировании адаптивного поведения муравьиной колонии

В общем случае поиск решения задачи покрытия осуществляется коллективом кластеров муравьев Z={Z_k |k=1,2,…,l}. На каждой итерации муравьи каждого кластера Z_k строят свое конкретное решение задачи покрытия в виде матрицы граничных требований P^k=||p^k_ij||_nm. Другими словами число решений формируемых муравьями на каждой итерации равно числу кластеров муравьев. Число муравьев в каждом кластере равно числу типов элементов - n в покрываемой функциональной схеме. Каждый i-й муравей z_ik k-го кластера соответствует типу e_i элементов, и решает задачу формирования i-й строки P^k_i матрицы граничных требований P^k путем выбора конкретных значений p^k_ij с соблюдением ограничений (2.1). Таким образом, каждый i-й муравей z_ik k-го кластера формирует частичное решение P^k_i. Полное решение - матрица граничных требований P^k=P^k_i формируется кластером муравьев Z_k={z_ik|i=1,2,…,n}. Поиск решений осуществляется на n графах поиска решений G₁- G_n, имеющих одну и ту же структуру. В работе исследовались два способа откладывания феромона муравьями в процессе поиска решений. При первом способе муравьи откладывают феромон на ребрах графа поиска решений (ГПР), а при втором способе на вершинах ГПР. Кроме того муравьи из разных кластеров обмениваются информацией в соответствии с которой осуществляется коррекция количества феромона на ребрах (или вершинах) ГПР.

Каждый граф G_i(V_i,U_i) соответствует типу e_i элемента покрываемой схемы и на нем муравьем z_ik формируется i-я строка P^k_i матрицы граничных требований P^k. Базовая структура ГПР формируется следующим образом. Множество вершин V_i\O_i графа G_i разбито на (m-1) стадий V_ij, где m - количество типов покрывающих ячеек.

V_ij=V_i\O_i, j=1,2,…,(m-1)

Стадия V_ij соответствует типу h_j покрывающей ячейки. Если a_ij не равно нулю, то число вершин в каждой стадии равно (b_i+1), где b_i - число элементов типа e_i , входящих в состав покрываемой схемы. V_ij ={v_ijs |s=0,1,2,…, b_i}. Вершины в стадии V_ij имеют вес от 0 до b_i и расположены в порядке возрастания веса сверху вниз. Вес вершины ц(v_ijs) равен ее порядковому номеру s в стадии V_ij, то есть ц(v_ijs)=s. Если a_ij равно нулю, то стадия V_ij включает только одну вершину с нулевым весом. Вершина O_i - начальная. ц(O_i)=0. Ребра графа G_i(V_i,U_i) ориентированные и связывают вершины соседних стадий V_ij и V_i,j+1. Задача каждого муравья z_ik найти в графе G_i маршрут M_ik из вершины O_i до одной из вершин стадии V_i,m-1. Ограничением является суммарный вес ц(M_ik) вершин, входящих в маршрут M_ik, он должен быть не больше b_i, то есть

ц(M_ik)b_i. (3.1)

Каждая вершина x_ijs в маршруте M_ik определяет значение элемента p^k_ij P^k_i. При этом p^k_ij= ц(v_ijs), v_ijs M_ik. Значение последнего элемента p^k_im в строке P^k_i определяется как p^k_im= b_i - ц(M_ik).

С учетом ограничения (3.1) ребра, связывающие вершины соседних стадий V_ij и V_i,j+1 формируются по следующему правилу. Вершина v_ijс V_ij связана с такими вершинами v_ijs V_i,j+1 для которых выполняются условие

ц(v_ijс)+ц(v_i,j+1,s)b_i. (3.2)

Базовая структура ГПР для b_i =3 и m =4 представлена на рис. 4.

В общем случае ГПР представляется совокупностью из m стадий (по числу типов покрывающих ячеек) и начальной вершины O_i. В этом случае по схеме, рассмотренной выше, начальная вершина O_i связывается с каждой стадией, в свою очередь каждая стадия связывается с остальными. Для равномерного распределения муравьев и создания равных стартовых условий можно использовать m начальных вершин, при этом каждая начальная вершина связана со своей стадией. Частным случаем является циклическая структура связей стадий: первая стадия связана со второй, вторая с третьей, …, (m-1)-я стадия с m-ой, m-я стадия с первой. Задача муравья z_ik найти маршрут M_ik, включающий по одной вершине из (m-1)-й стадии. Значение последнего элемента p^k_im в строке P^k_i определяется как p^k_im= b_i - ц(M_ik).

Размещено на http://www.allbest.ru/

Рис. 4. Базовая структура ГПР для b_i =3 и m =4

Отметим, что при построении матрицы D^k значения d^k_ij определяется как большее целое от p^k_ij/a_ij. Другими словами d^k_ij кратно a_ij. В связи с эти целесообразно использовать значения весов вершин в каждом графе G_i кратными величине a_ij, то есть ц(v_ijs)=s·a_ij. При этом вес последней вершины стадии определяется равным b_i. Сформированное таким способом множество вершин в стадии меньше в среднем в a_ij раз.

Процесс поиска решений итерационный. Каждая итерация l включает четыре этапа. На первом этапе муравьями каждого кластера находится решение задачи покрытия, на втором этапе на ребрах (или вершинах) графов G₁- G_n откладывается феромон, на третьем этапе осуществляется коррекция количества феромона на ребрах (или вершинах) ГПР, на четвертом этапе осуществляется испарение феромона. В работе используется циклический (ant-cycle) метод муравьиных систем. В этом случае феромоны откладываются муравьями на ребрах графов G₁- G_n после полного формирования решения. Не теряя общности, рассмотрим процесс поиска решения на базовой структуре ГПР.

На первом этапе каждой итерации каждый муравей z_ik формирует свое собственное частичное решение - маршрут M_ik в графе G_i. Моделирование поведения муравьёв в задаче покрытия связано с распределением феромона на множестве ребер (или вершин) графов G₁- G_n. Предварительно на всех ребрах (или вершинах) каждого графа G_i откладывается одинаковое (небольшое) количество феромона е_i. Значение е_i задается априорно. Процесс построения маршрута M_ik пошаговый, начиная от вершины O_i, поэтому, вначале, все i-е муравьи z_ik из всех кластеров помещаются в вершину O_i. Число таких муравьев равно числу кластеров. На каждом шаге агент применяет вероятностное правило выбора очередной вершины в графе G_i для включения ее формируемый маршрут M_ik, причем на шаге t в маршрут включается вершина стадии V_it. Процесс выбора осуществляется следующим образом. Обозначим как M_ik(t) маршрут, построенный муравьем z_ik за t шагов, и пусть вершина v_itсV_it является последней в маршруте M_ik(t). На шаге t+1 определяется суммарный вес вершин - ц(M_ik(t)), входящих в состав M_ik(t)_. Пусть Г_it(с) множество вершин стадии V_i,t+1, смежных вершине v_itс, Г_it(с)V_i,t+1. Среди множества вершин Г_it(с) выделяется подмножество Р_it(с) Г_it(с) такое, что для каждой вершины v_i,t+1,sР_it(с) выполняется условие

ц(M_ik(t))+ ц(v_i,t+1,s) b_i, (3.3)

обеспечивающее выполнение ограничения (3.1). Вершины подмножества Р_it(с) являются кандидатами для включения в маршрут на шаге t+1.

Агент просматривает все вершины Р_it(с). При первом способе для каждой вершины v_i,t+1,sР_it(с) рассчитывается f_cs - суммарное количество феромона, отложенного на ребре графа G_i, связывающего v_itсV_it с v_i,t+1,sР_it(с). При втором способе рассчитывается f_cs - суммарное количество феромона, отложенного на каждой вершине v_i,t+1,sР_it(с). Вероятность P_v включения на шаге t+1 вершины v_i,t+1,vР_it(с) в формируемый отдельным муравьем маршрут пропорциональна суммарному количеству феромона f_cv. P_v определяется следующим соотношением

P_v= f_cv /, (s | v_i,t+1,sР(v_itс)) (3.4)

С вероятностью P_v агент выбирает одну из вершин, которая включается в маршрут M_ik(t+1).

После построения муравьями маршрутов (каждый муравей z_ik - свой маршрут M_ik за m-1 шагов), формируются частичные решения P^k_i и полное решение P^k, построенное кластером муравьев Z_k. В соответствии с методом, изложенным выше, для каждого решения P^k, находится значение целевой функции F^k.

На втором этапе итерации, каждый муравей откладывает феромон на рёбрах (или вершинах) построенного маршрута.

Количество феромона ф_ik(l), откладываемое муравьем z_ik на каждом ребре (или вершине) построенного маршрута M_ik, определяется следующим образом:

ф_k(l)= Q_i / F^k(l), (3.5)

где l-номер итерации, Q_i - общее количество феромона, откладываемое муравьем на ребрах(или вершинах) маршрута в графе G_i, F^k(l)- целевая функция для решения, полученного кластером муравьев Z_k на l-ой итерации. Чем меньше F^k(l), тем больше феромона откладывается на ребрах (или вершинах) построенного маршрута и, следовательно, тем больше вероятность выбора этих ребер (или вершин) при построении маршрутов на следующей итерации.

Далее, на третьем этапе, осуществляется корректировка количества феромона, отложенного на ребрах (или вершинах) графов G₁- G_n, путем обмена информацией о количествах элементов, выбранных агентами, которые должны быть покрыты ячейками типа h_j.

Просмотрим матрицу D^k по столбцам. В столбце j находим максимальный элемент (d^k_oj)_max, который и определяет число x_j ячеек типа h_j в покрывающем наборе, найденное агентами k-го кластера. Величина (d^k_oj)_max соответствует весу вершины j-ой стадии в маршруте M_ok, построенном агентом z_ok , то есть величине (p^k_oj)_max. Для нашего примера рассмотрим 2-й столбец матрицы D^k. Максимальное значение имеет d^k₃₂=6. Значение d^k₃₂ определяется весом, равным 6, вершины стадии V₃₂ графа G₃ в маршруте агента z_3k. d^k₃₂= p^k₃₂ /a₃₂= 6/1=6. Отметим, что число ячеек x_j =(d^k_oj)_max будет избыточным для покрытия тех количеств p^k_ij элементов типа e_i e_o, которые определены в столбце j матрицы P^k.

Поскольку целью оптимизации является минимизация числа покрывающих ячеек, естественным является стремление изменить, а именно уменьшить (d^k_oj)_max, при этом уменьшится как число покрывающих ячеек, так и число избыточно покрытых элементов. В связи с этим при построении маршрута агентом z_ok на следующей итерации целесообразно вершины стадии V_oj с весом равным и большим величины (p^k_oj)_max сделать менее предпочтительными. При первом способе это достигается путем уменьшения количества феромона на величину б на всех ребрах графа G_o входящих в вершины стадии V_oj с весами от (p^k_oj)_max до b_i. В нашем примере уменьшается количество феромона на всех ребрах входящих в вершины стадии V₃₂ графа G₃ с весами от 6 до 20. При втором способе это достигается путем уменьшения количества феромона на величину б на всех вершинах стадии V_oj с весами от (p^k_oj)_max до b_i.

На четвертом этапе происходит общее испарение феромона на ребрах (или вершинах) графов G₁- G_n в соответствии с формулой (3.6).

f_ik = f_ik·(1- с), (3.6)

где с - коэффициент обновления.

После выполнения всех действий на итерации находится агент с лучшим решением, которое запоминается. Далее осуществляется переход на следующую итерацию. Временная сложность этого алгоритма зависит от времени жизни колонии l (число итераций), количества вершин графа n и числа муравьев m, и определяется как O(l*n²*m).

Заключение

Отличительной особенностью представленного алгоритма является то, что поиск решений осуществляется на n графах поиска решений G₁- G_n, имеющих многостадийную структуру связей. С другой стороны муравьиная колония разбита на кластеры и поиск конкретного решения задачи покрытия осуществляется коллективом кластеров муравьев. Экспериментальные исследования проводились на IBM PC. Наивысшая эффективность была достигнута при использовании: циклической структуры ГПР; с числом начальных вершин равным числу стадий; значения весов вершин в каждой стадии V_ij графа G_i кратными величине a_ij; подхода, при котором феромон откладывался на вершинах ГПР. Вероятность получения оптимального решения составила 0.9, а оценки локально оптимальных решений, отличались от глобального оптимума в среднем на 1%. Сравнение с известными алгоритмами показало, что при меньшем времени работы у полученных с помощью муравьиного алгоритма решений значения целевой функции лучше (меньше) в среднем на 6%.

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

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

[Андерсон, 2003] Андерсон Д. Дискретная математика и комбинаторика. М.: Вильямс, 2003.

[Деньдобренко и др., 2002] Деньдобренко Б.П., Малика А.С. Автоматизация проектирования радиоэлектронной аппаратуры. М., Высш. шк., 2002.

[Курейчик и др., 2006] Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Поисковая адаптация: теория и практика. М.: Физматлит, 2006.

[Курейчик и др., 2009] Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Решение задачи покрытия на основе эволюционного моделирования //Известия РАН.Теория и системы управления. 2009, №1.

[Лебедев и др., 2009] Лебедев Б.К., Лебедев В.Б. Планирование на основе роевого интеллекта и генетической эволюции // Известия ЮФУ. Изд-во ТТИ ЮФУ, 2009, №2.

[МакКоннелл , 2004] МакКоннелл Дж. Основы современных алгоритмов. Москва, Техносфера, 2004.

[Cordone et al., 2001] Cordone R., Ferrandi F., Sciuto D., Calvo R.W. An Efficient Heuristic Approach to Solve the Unate Covering Problem. IEEE Transactions on computer-aided design of integrated circuits and systems, vol.120, No.12, December 2001.

[Coudert , 1996] Coudert O., “On solving covering problems”, in proceedings of 30th ACM/IEEE Design automation conference, 1996, pp. 197-202.

[Dorigo et al., 2004] Dorigo M. and Stьtzle T.. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.

[Engelbrecht, 2005] Engelbrecht A. P. Fundamentals of Computational Swarm Intelligence. John Wiley & Sons, Chichester, UK, 2005.

[Мazumder et al., 2003] Мazumder P., Rudnick E. Genetic Algorithm

Размещено на Allbest.ru