Трассировка на основе метода роя частиц

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

Трассировка на основе метода роя частиц

Б.К. Лебедев

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

Введение

Одной из важнейших задач при построении интеллектуальных систем автоматизированного проектирования (САПР) сверхбольших интегральных схем (СБИС), является трассировка соединений, которая во многом определяет качество топологии СБИС. Задача канальной трассировки (ЗКТ) [1] является хорошо изученной, и существуют сотни подходов к ее решению: алгоритмы левого конца, “жадные”, графовые алгоритмы, иерархические и т.д. [Деньдобренко и др., 2002]. Однако наличие новых тенденций в проектировании СБИС вызывает потребность в разработке новых подходов к ее реализации. В последнее время для решения различных «сложных» задач, к которым относятся и задачи канальной трассировки, всё чаще используются способы, основанные на применении методов искусственного интеллекта [МакКоннелл, 2004]. Особенно наблюдается стремительный рост интереса к разработке алгоритмов, инспирированных природными системами [Di Caro et al., 2005], [Курейчик и др., 2006]. Одним из новых направлений таких методов являются мультиагентные методы интеллектуальной оптимизации, базирующиеся на моделировании коллективного интеллекта [Лебедев и др., 2005], [Лебедев, 2009]. Оптимизация с использованием роя частиц (Particle Swarm Optimization, PSO)-это метод поиска, который базируется на понятии популяции, и моделирует поведение птиц в стае и косяков рыб [Engelbrecht, 2005], [Clerc, 2006], [Poli, 2008]. В работе излагается метод решения задачи канальной трассировки (КТ) на основе роевого интеллекта и генетической эволюции. Используется компактное символьное представления решения задачи трассировки. Предложена композитная архитектура многоагентной системы бионического поиска.

1. Формирование символьного представления решения задачи канальной трассировки

При КТ каждая цепь, представляется в виде набора горизонтальных и вертикальных фрагментов. Задача трассировки в канале рассматривается как задача распределения фиксированного множества горизонтальных участков F ={fi|i=1,2,…,N} в множестве магистралей M ={mj|j=1,2,…,L}. На взаимное расположение горизонтальных фрагментов накладываются ограничения, задаваемые с помощью графа вертикальных ограничений (ГВО) GV=(X,U) и графа горизонтальных ограничений (ГГО) GH=(X,W) [Деньдобренко и др., 2002]. Вершина xi в графе GV и GH соответствует фрагменту fi. Наличие дуги (xi, xj) в GV означает, что fi в канале выше fj для исключения наложения вертикальных отрезков. Ребро (xi, xj) в GH означает, что xi и xj не могут быть размещены в одной магистрали.

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

Разобьем множество горизонтальных фрагментов F на подмножества Fk, F ={Fk|k=1,2,…,V} в соответствии со следующими правилами:

1. .

2.Любые два участка fiFk и fjFk находятся в горизонтальном конфликте и не могут быть помещены в одну магистраль.

3.Подмножества Fk сформированы и пронумерованы так, что все левые концы участков Fk расположены левее всех левых концов участков Fk+1.

Алгоритм разбиения F на Fk имеет линейную трудоемкость [Лебедев, 2005]. Пусть задан канал (рис.1), произведено разбиение цепи на фрагменты и построены ГВО и ГГО. Множество горизонтальных фрагментов F, в соответствии с приведенными правилами, разбивается на подмножества: F1={f1, f10, f2, f8, f3}; F2={f11, f12, f4}; F3={f5, f13, f9}; F4={f7, f6, f14}. Обозначим через бk - мощность подмножества Fk. Среди бk отыскивается бmax с максимальным значением, k[бmaxбk]. Произведем нормирование подмножеств Fk, путем добавления в них (бmax - бk ) нулей в случайной последовательности. Получим F1={f1, f10, f2, f8, f3}; F2={f11,0, f12, 0, f4}; F3={f5,0, f13, f9,0}; F4={f7,0, f6, f14,0}.

Для отображения решения задачи канальной трассировки (ЗКТ) формируется матрица D={dik| i=1,2,..., бmax; k=1,2,...,V}, число столбцов которой равно числу V подмножеств Fk, а число строк равно бmax. (рис.2). В каждый k-й столбец Dk в случайной последовательности заносятся элементы множества Fk. Для удобства на рис.2 элементам матрицы D присвоены значения индексов фрагментов.

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

Рис.1. Множество горизонтальных фрагментов

Процедура получения решения ЗКТ по матрице D осуществляется следующим образом. Магистрали заполняются последовательно, начиная с первой. Последовательно по строкам, начиная с первой, а в пределах строки слева направо просматриваются элементы матрицы D. Для каждого выбранного элемента матрицы (фрагмента) определяется возможность его размещения в текущей магистрали в соответствии с GV и GH. Если возможно, то фрагмент помещается в текущую магистраль и удаляется из D. По окончании просмотра матрицы D осуществляется сжатие всех столбцов, из которых удалялись фрагменты, снизу-вверх. После этого осуществляется переход к заполнению следующей магистрали. Процесс последовательного заполнения магистралей m1 - m3 показан на рис.2.

В результате применения вышеуказанной процедуры к матрице D магистрали будут заполнены следующим образом: m1={1,5}; m2={10,11,7}; m3={2,13,6}; m4={9,14}; m5={4}; m6={3}; m7={12}; m8={8}.

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

Рис.2. Процесс заполнения магистралей

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

Рис. 3. Оптимальное решение

2. Механизмы трассировки на основе роевого интеллекта

В методе оптимизации роем частиц агентами являются частицы в пространстве параметров задачи оптимизации. Процесс поиска решений итерационный. На каждой итерации каждая частица перемещается в новую позицию. В каждый момент времени (на каждой итерации) частицы имеют в этом пространстве некоторое положение и вектор скорости. Для каждого положения частицы вычисляется соответствующее значение целевой функции. При определении следующего положения частицы учитывается информация о наилучшей частице из числа «соседей» данной частицы, а также информация о данной частице на той итерации, когда этой частице соответствовало наилучшее значение целевой функции, и на этой основе по определенным правилам частица меняет свое положение и скорость в пространстве поиска [Engelbrecht, 2005].

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

xi(t+1)= xi(t)+ vi(t+1),

где vi(t+1) скорость перемещения частицы i из позиции xi(t) в позицию xi(t+1). Начальное состояние определяется, как xi(0), vi(0).

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

fi(t) - текущее значение целевой функции частицы i в позиции xi(t) (решение Di(t));

f*(t)- лучшее значение целевой функции среди частиц роя в момент времени t, а x*(t)- позиция с этим значением (решение D(t));

x*i(t) - лучшая позиция частицы i, которую она посещала с начала первой итерации (решение D*i(t)), а f*i(t)- значение целевой функции в этой позиции - лучшее значение частицы i.

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

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

В нашем случае позиция xi(t) соответствует i-ому решению, задаваемому матрицей Di(t). Число осей в пространстве решений равно числу столбцов Dik(t) в матрице Di(t)={Dik(t)| k=1,2,...,V}. Точками отсчета на каждой оси k являются значения лингвистической переменной xik(t) неупорядоченные друг относительно друга. Значением xik(t) является некоторая комбинация взаимного расположения элементов в k-м столбце Dik(t) матрицы Di(t). Позиция xi(t), то есть матрица Di(t) является решением, а скорость vi(t+1) рассматривается как средство изменения решения. В отличие от канонического метода роя частиц, в нашем случае скорость vi(t+1) не может быть представленной в виде аналитического выражения. В качестве скорости vi(t+1) выступает процедура перемещения, суть которой заключается в изменения взаимного расположения элементов в столбцах матрицы Di(t). Частица i перемещается в новую позицию c новыми значениями лингвистических переменных xik(t).

Пусть «центром притяжения» частицы i, размещенной в позиции xi(t), является позиция x0(t). Рассмотрим работу процедуры перемещения, приводящую к модификации решения Di(t). Введем характеристику, отражающую степень различия между матрицами Di(t) и D0(t). Для этого произведем сравнение взаимного расположения пары элементов в сравниваемых матрицах Di(t) и D0(t) у всех возможных пар, таких, что оба элемента пары принадлежат одному столбцу. Пусть Sik(t)- число пар, у которых взаимное расположение элементов в k-м столбце матриц Di(t)) и D0(t) не совпадает. Общее число несовпадений определится как

интеллектуальный трассировка интегральный

Wi(t)=.

Чем больше Wi(t), тем больше различие между Di(t) и D0(t), и наоборот, чем меньше Wi(t), тем различие между Di(t) и D0(t) меньше. Тяготение частицы в позиции xi(t) к позиции x0(t) выражается в стремлении уменьшения различия между Di(t) и D0(t), то есть уменьшения показателя Wi(t). Будем считать, чем меньше различие между Di(t) и D0(t), тем ближе позиция xi(t) к позиции x0(t).

Модификация матрицы Di(t), то есть переход к матрице Di(t+1), производится путём выборочных групповых парных перестановок соседних элементов в столбцах матрицы Di(t).

На каждом шаге за два такта анализируются пары элементов в столбцах матрицы Di(t) и осуществляется ее модификация, приводящая к уменьшению показателя Wi(t).

На каждом такте рассматриваются множество непересекающихся пар элементов (dlk, dl+1,k) матрицы Di(t), каждая из которых расположена в одном столбце Dik(t) и в двух соседних строках l и l+1. Будем в дальнейшем первый элемент пары называть верхним, а второй нижним. На первом такте в каждом столбце Dik(t) анализируется множество P1 непересекающихся пар элементов, у которых l-нечетное числою На втором такте анализируется множество P2 непересекающихся пар элементов, у которых l-четное число. Пары элементов на каждом такте анализируются независимо друг от друга. По результатам анализа принимается решение о перестановке элементов каждой пары, вычисляются показатели Sik(t) и осуществляется модификация Di(t).

Если взаимное расположение рассматриваемой пары отличных от нуля элементов в столбце Dik(t) матрицы Di(t) не совпадает с взаимным расположением этих элементов в столбце D0k(t) матрицы D0(t), производится парная перестановка этих элементов в Di(t).

При совпадении взаимного расположения элементов рассматриваемой пары в матрицах Di(t) и D0(t), перестановка этих элементов не производится.

Если один из элементов рассматриваемой пары имеет нулевое значение, то рассчитывается число нулей n0i, размещенных в столбце Dik(t) над вторым (ненулевым) элементом и число нулей n0, размещенных над таким же элементом в столбце D0k(t). Если перестановка такой пары элементов в Dik(t) приводит к уменьшению величины |n0i-n0|, то эти элементы переставляются. В противном случае перестановка этих элементов не производится. Таким способом осуществляется выравнивание числа нулей, расположенных выше и ниже рассматриваемого элемента в столбце Dik(t) по отношению к столбцу D0k(t).

Локальная цель перемещения частицы i - достижение ею позиции с наилучшим значением целевой функции. Глобальная цель роя частиц - формирование решения ЗКТ в минимальном числе магистралей.

Рассмотрим пример работы процедуры перемещения. На рис.4 представлена матрица D0(t), матрица Di(t), матрица D1i(t+1), полученная после первого такта, матрица Di(t+1), полученная после второго такта.

D0(t) Di(t) D1i(t+1) Di(t+1)

Рис.4. Работа процедуры перемещения

Рассмотрим характерные ситуации. На первом такте в первом столбце матрицы Di(t) рассматриваются пары <1,3 > и <2,10>. Расположение элементов в паре <2,10> не совпадает с относительным расположением этих же элементов в первом столбце матрицы D0(t), поэтому производится парная перестановка этих элементов. В третьем столбце матрицы Di(t) рассматриваются пары <5,0> и <9,13>. Значение второго элемент пары <5,0> равно нулю. Рассчитывается число нулей n0i = 0, размещенных в столбце над вторым (ненулевым) элементом пары <5,0> со значением 5 в Di(t) и число нулей n0 =1, размещенных в столбце над таким же элементом в D0(t). Перестановка пары элементов <5,0> в Di(t) приводит к уменьшению величины |n0i-n0|, поэтому элементы пары <5,0> переставляются. На втором такте в первом столбце матрицы D1i(t+1) рассматриваются пары <3,10 > и <2,8>. Расположение элементов в паре <3,10> не совпадает с расположением этих же элементов в первом столбце матрицы D0(t), поэтому производится парная перестановка этих элементов. Аналогичные действия производятся во всех столбцах рассматриваемых матриц.

3. Роевой алгоритм канальной трассировки

Для учета одновременного тяготения частицы i к позициям x*(t) и x*i(t) формируется центр притяжения xci(t) этой частицы. Среди позиций x*(t) и x*i(t) определяется худшая - xbi(t) и лучшая - xgi(t). Формирование xci(t) осуществляется путем применения модифицированной процедуры перемещения к худшей позиции xbi(t) для перемещения из нее в направлении к лучшей xgi(t). Отличие модифицированной процедуры перемещения состоит в том, что обязательные в процедуре перемещения перестановки в модифицированной процедуре перемещения осуществляются с заданной вероятностью с. После определения центра притяжения xci(t) частица i с помощью процедуры перемещения перемещается в направлении xci(t) из позиции xi(t) в позицию xi(t+1).

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

1. В соответствии с исходными данными формируется множество горизонтальных участков F ={fi|i=1,2,…,N}.

2. Множество горизонтальных фрагментов F разбивается на подмножества Fk, F={Fk|k=1,2,…,V}. Формируется пространство решений, каждая ось которого соответствует подмножеству Fk.

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

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

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

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

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

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

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

9. t=t+1.

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

5. Заключение

Поисковый процесс, базирующийся на моделировании адаптивного поведения роя частиц, организован в пространстве решений с неупорядоченными лингвистическими шкалами. В отличие от канонического метода роя частиц, в качестве скорости vi(t+1) выступает процедура перемещения, суть которой заключается в изменения взаимного расположения элементов в столбцах матрицы Di(t). Частица i перемещается в новую позицию c новыми значениями лингвистических переменных xik(t).

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

Сравнительный анализ с другими алгоритмами трассировки [Деньдобренко и др., 2002], [Taniguch et al., 1993] производился на стандартных тестовых примерах и схемах (бенчмарках). Представленный роевой алгоритм канальной трассировки в сочетании с генетическим алгоритмом находит решения для задач большой размерности, не уступающие по качеству, а иногда и превосходящие своих аналогов с меньшими временными затратами, кроме того, он оптимизирует длину соединений.

Исследования трудоемкости гибридного алгоритма показали, что общая оценка временной сложности при любом подходе к гибридизации лежит в пределах О(n2), где N - число связываемых контактов.

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

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

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

3. [Лебедев и др., 2005] Лебедев Б.К., Лебедев О.Б. Трассировка в канале на основе коллективной адаптации. Международная НТК IEEE AIS'05 CAD 2005.М: Изд-во Физматлит. 2005.

4. [Лебедев, 2009] Лебедев О.Б.Трассировка в канале методом муравьиной колонии // Известия ЮФУ. Изд-во ТТИ ЮФУ, 2009, №2.

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

6. [Clerc, 2006] Clerc M.. Particle Swarm Optimization. ISTE, London, UK, 2006.

7. [Di Caro et al., 2005] Di Caro G., Ducatelle F., Gambardella L. M. AntHocNet: An adaptive nature-inspired algorithm for routing in mobile ad hoc networks. // European Transactions on Telecommunications, 2005. №16(5).

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

9. [Poli, 2008] Poli R.. Analysis of the publications on the applications of particle swarm optimisation. Journal of Artificial Evolution and Applications, Article ID 685175, 2008.

10. [Taniguch et al., 1993] Taniguch N., Liu X., Sakamoto A.& Shimomoto T. “An Approach to channel routing using genetic algorithms”, Bulletin of Faculty of Engineering, Tokyshima University, no. 38, 1993.

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