Б.К. ЛЕБЕДЕВ, В.Б. ЛЕБЕДЕВ

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

lbk@tsure.ru
ПОКРЫТИЕ НА ОСНОВЕ МЕТОДА РОЯ ЧАСТИЦ^
Рассматриваются новые технологии, принципы и механизмы решения задачи покрытия, использующие математические методы, в которых заложены принципы природных механизмов принятия решений. Для компактного представления решения задачи покрытия используется матрица граничных требований. Это позволило организовать пространство решений, в рамках которого организован поисковый процесс, базирующийся на моделировании адаптивного поведения роя частиц. По сравнению с существующими алгоритмами достигнуто улучшение результатов.
Ключевые слова: коллективный интеллект, адаптивное поведение, самоорганизация, рой частиц, оптимизация
Введение
Одна из первых и важнейших задач, решаемых на этапе проектирования топологии СБИС, – преобразование функциональной схемы в электрическую. Задача покрытия функциональной схемы ячейками из заданного набора эквивалентна задаче о покрытии множествами и является NP-полной. Покрытие во многом определяет качество топологии СБИС. В течение последних лет были предложены различные подходы к решению проблемы покрытия. Главным образом это алгоритмы, основанные на эвристиках, обеспечивающих получение приемлемого результата за полиномиальное время [1]. Тем не менее, возросшие сложность решаемых задач и требования к качеству решения делают актуальной разработку новых более эффективных методов. Приведенный в [1, 2, 3] обзор, сравнение и анализ разработанных алгоритмов покрытия (последовательных, итерационных и т.д.) показывает, что для создания эффективного алгоритма покрытия, отвечающего современным требованиям, необходимы новые технологии и подходы. В последние годы интенсивно разрабатывается научное направление, объединяющее математические методы, в которых заложены принципы природных механизмов принятия решений [4, 5]. Одним из новых направлений таких методов являются мультиагентные методы интеллектуальной оптимизации, базирующиеся на моделировании коллективного интеллекта [6, 7, 8]. Оптимизация с использованием роя частиц (Particle Swarm Optimization, PSO)-это метод поиска, который базируется на понятии популяции, и моделирует поведение птиц в стае и косяков рыб [9,10]. Рой частиц рассматривается как многоагентная система, в которой каждый агент (частица) функционирует автономно по очень простым правилам. В таких случаях говорят о роевом интеллекте (Swarm intelligence).

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

Основные положения
Исходными данными для решения задачи покрытия являются: функциональная схема проектируемой СБИС и схемы типовых ячеек применяемого библиотечного набора. Необходимо найти такое распределение логических функций покрываемой схемы по отдельным ячейкам, при котором достигается экстремум целевой функции. Известные в литературе алгоритмы покрытия функциональной схемы ячейками из заданного набора оптимизируют следующие показатели: суммарную стоимость ячеек, покрывающих схему; общее число ячеек, необходимое для реализации схемы; число типов используемых ячеек; число межъячеечных связей, общее число элементов, входящих в покрывающий набор ячеек [1,3,6].

Пусть задана функциональная схема 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||_nm , где a_ij – число элементов типа e_i в ячейке типа h_i. Вектор C = {c_j | j=1,2,…,m} конкретизирует для каждой ячейки h_j её стоимость c_j. Схема считается покрытой ячейками из набора H, если каждый элемент функциональной схемы реализуется элементами из состава выбранных ячеек. Построим математическую модель. Введём целочисленную переменную x_j, определяющую число ячеек типа h_j, входящих в покрывающий набор. Тогда задача покрытия формулируется следующим образом:

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

, (1)

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

x_j ≥ 0, j = 1, 2,…, m;

a_il ≥ 0.

Решение задачи представляет набор величин x_j , j=1,2,…,m, при которых функция F (суммарная стоимость ячеек покрывающего набора) имеет минимальное значение. Если в качестве показателя c_j принять общее число элементов, присутствующих в составе ячейки t_j , т.е.

,

то F определяет общее число элементов покрывающего набора ячеек.

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

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

(2)

A=	Типы элементов	Типы покрывающих ячеек
		h1	h2	h3	h4	h5
	e1	2	3	1	2	2
	e2	2	2	3	2	1
	e3	3	1	1	2	2

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

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

Матрица P однозначно соответствует покрывающему набору ячеек, который формируется следующим образом. Сначала строится матрица D = ||d_ij||_nm. Элемент матрицы 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, гарантированно обеспечивающих покрытие р_1j элементов типа e₁ , р_2j элементов типа e₂ ,…, р_nj элементов типа e_n, в соответствии с требованиями матрицы P. Причём, кроме элементов типа e_i , для которых d_ij = d_jmax , остальные типы элементов могут быть покрыты с избытком.

P =	Типы элементов	Типы покрывающих ячеек					bi= pij
		h1	h2	h3	h4	h5
	e1	2	3	3	1	1	b1 = 10
	e2	4	4	8	5	9	b2 = 30
	e3	2	6	5	1	6	b3 = 20

Рис. 2. Матрица P

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

Общее число ячеек N_я в покрывающем наборе и общее число N_i элементов типа e_i , входящее в состав покрывающего набора ячеек определяются по формулам: N_я=∑x_j ; N_i=∑x_j ∙a_ij .

Для нашего примера: N_я = ∑x_j = 25; N₁ = 2  2 + 6  3 + 5  1 + 3  2 +  + 9  2 = 51; N₂ = 2  2 + 6  2 + 5  3 + 3  2 + 9  1 = 46; N₃ = 2  3 + 6  1 +  + 5  1 + 3  2 + 9  2 = 41. Общее число элементов, образующих покрывающий набор, N_э = N₁ + N₂ + N₃ = 138. Итак, матрице P, значения элементов которой удовлетворяют ограничениям (2), соответствует одно решение. Различные решения получаются путём комбинирования значениями p_ij матрицы P, удовлетворяющими ограничениям (2).

D =	Типы элементов	Типы покрывающих ячеек
		h1	h2	h3	h4	h5
	e1	1	1	3	1	1
	e2	2	2	3	3	9
	e3	1	6	5	1	3
X =	xj	х1	x2	x3	x4	x5
	25	2	6	5	3	9

Рис. 3. Матрица D и покрывающий набор X
Таким образом, матрица P является символьным представлением решения задачи покрытия множествами. В работе множество решений представляется множеством матриц Π={P_k|k=1,2,…,m}. Поиск решения сводится к поиску такой матрицы P_k, т.е. к поиску совокупности таких значений элементов матрицы P_k, которые оптимизируют показатель качества (критерий).
Механизмы покрытия на основе роевого интеллекта
В методе оптимизации роем частиц агентами являются частицы в пространстве параметров задачи оптимизации. Основу поведения роя частиц составляет самоорганизация, обеспечивающая достижение общих целей роя на основе низкоуровневого взаимодействия. Каждая частица связана со всем роем, может взаимодействовать со всем роем и она тяготеет к лучшему решению роя. Процесс поиска решений итерационный. На каждой итерации каждая частица перемещается в новую позицию. В каждый момент времени (на каждой итерации) частицы имеют в этом пространстве некоторое положение и вектор скорости. Для каждого положения частицы вычисляется соответствующее значение целевой функции. При определении следующего положения частицы учитывается информация о наилучшей частице из числа «соседей» данной частицы, а также информация о данной частице на той итерации, когда этой частице соответствовало наилучшее значение целевой функции, и на этой основе по определенным правилам частица меняет свое положение и скорость в пространстве поиска [10]. В работе позиция x_k(t) k-й частицы в момент времени t соответствует решению, задаваемому матрицей P_k(t). Перемещение k-й частицы в дискретные моменты времени соответствует изменению матрицы P_k(t).

В каноническом методе роя частиц [10], использующем метрические шкалы, новая позиция частицы k определяется как

x_k(t+1)= x_k(t)+ v_k(t+1),

где v_k(t+1) – скорость перемещения частицы k из позиции x_k(t) в позицию x_k(t+1). Начальное состояние определяется, как x_k(0), v_k(0). Приведенная формула представлена в векторной форме. Для отдельного измерения i пространства поиска формула примет вид

x_ki(t+1)= x_ki(t)+ v_ki(t+1), (3)

где x_ki(t) – позиция частицы k в измерении i, v_ki(t+1) – скорость частицы k в измерении i.

Введем обозначения:

• 
  f_k(t) – текущее значение целевой функции частицы k в позиции x_k(t) (решение P_k(t));
  
• 
  f^*(t) – лучшее значение целевой функции среди частиц роя в момент времени t, а x^*(t) – позиция с этим значением (решение P(t));
  
• 
  x^*_k(t) – лучшая позиция частицы k, которую она посещала с начала первой итерации (решение P^*_k(t)), а f^*_k(t) – значение целевой функции в этой позиции – лучшее значение частицы k.
  

Лучшие частицы с точки зрения целевой функции объявляется «центром притяжения». Векторы скоростей всех частиц устремляются к этим центрам.

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

В нашем случае позиция x_k(t) соответствует решению, задаваемому матрицей P_k(t). Число n осей в пространстве решений равно числу строк P_ki(t) в матрице P_k(t). Точками отсчета на каждой оси i являются значения лингвистической переменной x_ki(t) неупорядоченные друг относительно друга. Значением x_ki(t) является набор значений элементов p_kij(t) в i-ой строке P_ki(t) матрицы P_k(t) для которых выполняется ограничение (2). Позиция x_k(t), то есть матрица P_k(t) является решением, а скорость v_i(t+1) рассматривается как средство изменения решения. В отличие от канонического метода роя частиц, в нашем случае скорость v_k(t+1) не может быть представленной в виде аналитического выражения. В качестве скорости v_k(t+1) выступает процедура перемещения, суть которой заключается в изменения значений элементов в строках P_ki(t) матрицы P_k(t) с соблюдением ограничений (2). Частица k перемещается в новую позицию c новыми значениями лингвистических переменных x_ki(t).

Пусть «центром притяжения» частицы k, размещенной в позиции x_k(t) (решение P_k(t)), является позиция x_c(t) (решение P_c(t)).

Рассмотрим работу процедуры перемещения, приводящую к модификации позиции x_ki(t) частицы k в измерении i. Введем характеристику, отражающую степень различия между строками P_ki(t) и P_сi(t). Для этого для каждой пары элементов p_kij(t) и p_cij(t) рассчитывается величина δ_kcij(t) = p_kij(t) – p_cij(t). Подсчитывается число α_kci(t) положительных и число β_kci(t) отрицательных значений величины δ_kcij(t).

Если α_kci(t) < β_kci(t), то значения всех α_kci(t) элементов p_kij(t), для которых величина δ_kcij(t) положительна, уменьшаются на единицу, а значения случайно выбранных α_kci(t) элементов p_kij(t), для которых δ_kcij(t) отрицательна, увеличиваются на единицу.

Если α_kci(t) > β_kci(t), то для значения всех β_kci(t) элементов p_kij(t), для которых величина δ_kcij(t) отрицательна, увеличиваются на единицу, а значения случайно выбранных β_kci(t) элементов p_kij(t), для которых δ_kcij(t) положительна, уменьшаются на единицу.

При таком подходе суммарное значение элементов строки P_ki(t+1) не изменится.

Локальная цель перемещения частицы k – достижение ею наилучшей позиции. Глобальная цель роя частиц – формирование решения задачи покрытия с наилучшим значением целевой функции.

Пример работы процедуры перемещения. Пусть P_ki(t) = <2, 4, 3, 5, 3, 6, 3>, P_ci(t) = <1, 6, 3, 2, 3, 7, 4>. Рассчитываем значения δ_kcij(t) = p_kij(t) – p_cij(t). δ_kci(t) = <+1, –2, 0, +3, 0, –1, –1>. Число α_kci(t) = 2, а число β_kci(t) = 3. Имеем α_kci(t) < β_kci(t). Тогда в соответствии с вышеприведенным правилом значения 1-ого и 4-ого элементов строки P_ki(t) уменьшаем на единицу, а значения случайно выбранных 6-ого и 7-ого элементов строки P_ki(t) увеличиваем на единицу. В результате получаем P_ki(t+1) = <1, 4, 3, 4, 3, 7, 4>.

По аналогии с каноническим методом роя частиц позицию x^*_k(t) будем называть когнитивным центром притяжения, а позицию x^*(t) социальным центром притяжения. Когнитивный центр выступает в роли индивидуальной памяти о наиболее оптимальных позициях данной частицы. Благодаря социальному центру частица имеет возможность передвигаться в оптимальные позиции, найденные соседними частицами.

Для учета одновременного тяготения частицы k к позициям x^*(t) и x^*_k(t) формируется центр притяжения x^c_k(t) этой частицы. Среди позиций x^*(t) и x^*_k(t) определяется худшая – x^b_k(t) и лучшая – x^g_k(t). Формирование x^c_k(t) осуществляется путем применения модифицированной процедуры перемещения к частице в худшей позиции x^b_k(t) для перемещения из нее в направлении к лучшей x^g_k(t). После определения центра притяжения x^c_k(t) частица k с помощью процедуры перемещения перемещается в направлении x^c_k(t) из позиции x_k(t) в позицию x_k(t+1).

Схема работы роевого алгоритма покрытия включает следующие шаги:

1. В соответствии с постановкой задачи покрытия и исходными данными формируется структура матрицы P_k. Формируется пространство решений, каждая ось которого соответствует строке P_k.

2. Создается исходная «случайная» популяция частиц, t = 0. Для каждой частицы случайным образом задается начальная позиция x_k(0). С этой целью формируется матрица P_k(0). В каждую i-ю строку матрицы заносятся случайные значения элементов p_kij(0), с соблюдением ограничения (2).

3. Шаги 4-10 итерационно повторяются заданное число раз.

4. Рассчитывается целевая функция f_к(t) для каждой частицы.

5. Определяются лучшая позиция роя x^*(t) на шаге t и значение целевой функции f^*(t) в этой позиции.

6. Для каждой частицы определяются лучшая позиции x^*_k(t), которую она посещала с начала первой итерации, и значение целевой функции f^*_k(t) в этой позиции.

7. Для каждой частицы определяется центр притяжения x^c_i(t) этой частицы.

8. Рассчитываются новые позиции частиц в пространстве решений. С помощью процедуры перемещения каждая частица перемещается из позиции x_k(t) в позицию x_k(t+1).

9. t = t + 1.

10.Запоминается лучшее решение, найденное роем к моменту t.

По аналогии с эволюционными стратегиями, рой можно трактовать как популяцию, а частицу – как индивида (хромосому). Это дает возможность построения гибридной структуры поиска решения, основанную на сочетании генетического поиска с методами роевого интеллекта. Связующим звеном такого подхода является структура данных, описывающая в виде хромосомы решение задачи. Если в качестве частицы используется хромосома, то число параметров, определяющих положение частицы в пространстве решений должно быть равно числу генов в хромосоме. В работе предлагается подход к построению структур и принципов кодирования хромосом, обеспечивающих их гомологичность и возможность одновременного использования в генетическом алгоритме, и в алгоритме на основе роя частиц [6]. Первый и наиболее простой подход к гибридизации заключается в следующем. С начала поиск решения осуществляется генетическим алгоритмом. После этого дальнейший поиск решения осуществляется роевым алгоритмом.

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

Для анализа точности получаемых решений был синтезирован ряд примеров с априори известным оптимальным значением целевой функции. Исследованию подвергались примеры, содержащие до 1000 элементов. В среднем 70 итераций достаточно для нахождения лучшего решения. Вероятность получения оптимального решения составила 0.9, а оценки локально оптимальных решений, отличались от глобального оптимума в среднем на 1%. Сравнение с известными алгоритмами [2,3] показало, что при меньшем времени работы у полученных с помощью гибридного алгоритма решений значения целевой функции лучше (меньше) в среднем на 6%.

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

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

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

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

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

Coudert O. On solving covering problems, in proceedings of 30th ACM/IEEE Design automation conference, 1996, pp. 197–202.

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 , pp. 1377–1387.

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

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

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

Курейчик В.В., Полупанова Е.Е. Эволюционная оптимизация на основе алгоритма колонии пчел // Известия ЮФУ. Изд-во ТТИ ЮФУ, 2009. №12. С.41–46.

Курейчик В.М. Модифицированные генетические операторы // Известия ЮФУ. Изд-во ТТИ ЮФУ, 2009. №12. С. 7–15.

Poli R. Analysis of the publications on the applications of particle swarm optimisation // Journal of Artificial Evolution and Applications, Article ID 685175, 10 pages, 2008.

Clerc M. Particle Swarm Optimization. ISTE, London, UK, 2006.