Генетический алгоритм трассировки в коммутационном блоке

2. Генетический алгоритм трассировки в коммутационном блоке

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

2.1. Структура хромосом, их кодирование и декодирование

Построим множество  горизонтальных участков _iÎ, являющихся проекциями всех двухтерминальных соединений _iÎ, т.е. каждому _i соответствует _i. На рис.2а и 2б приведены множества  для ОТ1 и ОТ2.

Обозначим через O(l_i) и O(r_i) координаты по горизонтали левого и правого конца участка _i.

Разобьем множество , на подмножества _k, в соответствии со следующими правилами:

1. , " (ij) [_i Ç_j =0]

2. В пределах каждого _k все участки накладываются друг на друга, т.е

" (ij ½_i Î_k & _j Î_k) [(O(l_j) £ O(l_i) £ O(r_j))Ú((O(l_j) £ O(r_i) £ O(r_j))].

Подмножество _kпронумерованы и сформированы так, что все левые концы участков _k расположены левее левых концов участков _k+1, т.е. " (ij ½_i Î_k & _j Î_k+1) [(O(l_i) < O(l_j) )].

Линейный алгоритм разбиения представлен в работе [7]. Разбиению  соответствует разбиение S.

Для участков, представленных на рис.2а, разбиение S имеет вид:

S₁={21,31,11} ,S₂={32,4,12,22,5};

Для участков, представленных на рис.2б, разбиение S имеет вид:

S₁={11,21,4,31}, S₂={22,32}, S₃={12,5}.

Для ОТ1, представленной на рисунке 1а, m=5, для ОТ2, представленной на рис.1б, m=6, где m - число горизонтальных линий на ОТ.

Формируем на основе каждого S_k вектор V_k путем добавления в S_k нулевых элементов, так, чтобы мощность V_k была равна m, и фиксируем взаимное расположение элементов.

Для ОТ1: V₁=<31,0,11,21,0>; V₂=<32,4,12,22,5>.

Для ОТ2: V₁=<11,21,4,31,0,0>; V₂=<22,32,0,0,0,0>; V₃=<12,5,0,0,0,0>.

Полученный после дополнения набор векторов V={V_i} будем называть решением задачи трассировки коммутационного блока.

Представим решение в виде хромосомы. Хромосома H_m является упорядоченной совокупностью генов . Ген  является одним из вариантов вектора V_i, т.е. значением  является некоторый вектор . Гены  и  хромосом H_m и H_l гомологичны, они одинаковы по составу элементов, соответствуют одному и тому же подмножеству S_i двухтерминальных соединений, но отличаются порядком расположения элементов.

Декодирование хромосомы осуществляется с помощью процедуры декодирования, использующей идеи алгоритма «левого конца» при канальной трассировке. Как и при канальной трассировке будем называть горизонтальные линии опорной сетки ОТ магистралями, пронумерованными сверху вниз.

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

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

Заполнение магистралей двухтерминальными соединениями базируется на трех основных процедурах: укладки, трансформации, резервации.

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

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

Вертикальный столбец считается занятым (зарезервированным) для любой цепи n_i не равной n_f если в нем расположен выше заполняемой магистрали терминал, помеченный цепью n_f и еще не связанный. Если терминал, расположенный выше n-ой магистрали, связывается по вертикали с горизонтальным участком, расположенным на n-ой магистрали, то столбец начиная с магистрали n+1, считается свободным. Изначально все столбцы, подходящие к помеченным цепями терминалам, расположенным на верхней стороне ОТ, считаются занятыми (зарезервированными). Например на рис.3а полностью размещены ДС1, ДС2 ДС3. На рис.3б частично размещены ДС1,ДС2,ДС4. При частичной укладке вводится точка разрыва ДС. Частично уложенное ДС связывает точку разрыва с одним из терминалов исходного ДС.

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

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

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

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

На рис.4а проведены горизонтальные фрагменты от терминалов 1₁ до 1¢₁ и от 2₁ до 2¢₂. В дальнейшем ДС1 и ДС2 трансформируются, т.е. они будут инцидентны терминалам 1¢₁ и 2¢₂ соответственно. Перед резервацией анализируется состояние столбцов и если необходимо и существует возможность формируется ближайший к терминалу свободный столбец.

Если есть несколько столбцов, занятых терминалами одной цепи и эти терминалы уже связаны, то их можно объединить в один терминал, что приводит к освобождению столбцов. Например на рис.4в при резервации терминала 2₃ два столбца заняты терминалами 1¢₂ и 1₂. 1¢₂ входит в ДС(1¢₁ , 1¢₂), 1₂ входит в ДС (1₂, 1₃), но они связаны и их можно объединить в один терминал1¢₂, при этом ДС(1₂,1₃) трансформируется в ДС (1¢₂, 1₃). Это приводит к освобождению столбца в который можно поместить терминал 2¢₃, связанный горизонтальным фрагментом с резервируемым терминалом 2₃.

Представим хромосому H_k виде матрицы V_k, где каждый столбец соответствует гену. Магистрали заполняются последовательно, начиная с первой. Заполнение магистралей осуществляется следующим образом. Вначале осуществляется резервация терминалов левой и правой сторон ОТ, лежащих на магистрали. Затем последовательно по строкам, начиная с первой в пределах строки слева направо просматриваются элементы матрицы V_k. Для каждого выбранного элемента матрицы (ДС) определяется возможность его размещения в формируемой магистрали. Если возможно, то ДС полностью или частично помещается в формируемую магистраль. Если ДС полностью помещается, то оно удаляется из матрицы V_k. Если ДС помещается частично, то трансформируется и остается в матрице. По окончании просмотра матрицы V_k осуществляется сжатие всех столбцов, из которых удалялись ДС, снизу вверх. После этого осуществляется переход к заполнению следующей магистрали. Процесс декодирования и заполнения магистралей показан на рис.5 и 6 для ОТ представленных соответственно на рис.1а и 1б. Отметим, что это фактически одна и та же задача трассировки.

Рассмотрим сначала процесс укладки в ОТ1, показанный на рис.1а. На рис.5а показаны два этапа заполнения первой магистрали: резервация и укладка. Вначале осуществляется резервация терминала 3₃, лежащего на 1-й магистрали. Для этого от терминала 3₃ проводится горизонтальный фрагмент до ближайшего свободного столбца. Терминал 3₃ резервируется терминалом 3¢₃, а ДС32=(3₂,3₃) трансформируется в ДС32¢=(3₂,3¢₃). Затем проводится укладка ДС в первую магистраль. Просматривается матрица V_kи первым выбирается ДС31=(3₁,3₂). ДС31 укладывается частично, при этом трансформируясь в ДС31¢=(3₁,3¢₂). Следующим из V_k выбирается ДС32¢, которое полностью помещается в первую магистраль и удаляется из V_k . Процесс заполнения завершается и V_k сжимается. На рис.5б заполняется вторая магистраль. Вначале резервируются терминалы 2₁ и 4₂, ДС21=(2₁,2₂) и ДС4=(4₁,4₂) трансформируются в ДС21¢=(2¢₁,2₂) и ДС4¢=(4₁,4¢₂).

Затем просматривается матрица V_k. ДС31¢ не помещается, ДС4¢ помещается полностью и удаляется из V_k , которое потом сжимается. На рис.5в,г,д, показан процесс укладки 3, 4, и 5-й магистралей.

При заполнении 3-й магистрали (рис.5в) в результате трансформации образуются ДС31¢¢=(3¢₁,3¢₂), ДС11¢=(1₁,1¢₂), ДС12¢=(1¢¢₂,1¢₃). Полностью помещается ДС31¢, частично ДС12 и ДС11.

При заполнении 4-й магистрали (рис.5г) при трансформации образуется ДС12¢¢=(1¢¢₂,1¢₃). Полностью помещаются ДС12¢, ДС22, ДС21¢.

При заполнении 5-й магистрали (рис.5д) полностью помещаются ДС11¢, ДС5.

Рассмотрим процесс заполнения ОТ2, представленной на рисунке 1б.

На рис.6а заполняется первая магистраль. Вначале резервируется терминал 5₁ лежащий на 1-й магистрали. ДС5=(5₁,5₂) трансформируется в ДС5¢=(5¢₁,5₂). Затем при просмотре V_k выбирается ДС11 которое частично укладывается в 1-ю магистраль и трансформируется в ДС11¢=(1₁,1¢₂).

При заполнении 2-й магистрали (рис.6б) вначале резервируется терминал 1₁ при этом ДС11¢ трансформируется в ДС11¢¢=(1¢₁,1¢₂). Для резервации терминала 2₃ формируется свободный столбец. Для этого терминалы 1¢₂ Î ДС11¢¢ и 1₂ Î ДС12, поскольку они уже связаны, объединяются в терминал 1¢₂, а столбец, занятый терминалом 1₂, освобождается. ДС12=(1₂,1₃)трансформируется в ДС12¢=(1¢₂,1₃). После этого терминал 2₃ резервируется терминалом 2¢₃, а ДС22=(2₂,2₃) трансформируется в ДС22¢=(2₂,2¢₃). При просмотре V_k полностью во 2-ю магистраль помещается только ДС11¢¢, которое удаляется из V_k.

При заполнении 3-й магистрали (рис.6в) резервируются терминалы 2₁ и 5₂.Трансформируются: ДС21=(2₁,2₂) в ДС21¢=(2¢₁,2₂), ДС5¢=(5¢₁,5₂) в ДС5¢¢=(5¢₁,5¢₂). Полностью помещается только ДС5¢¢, которое удаляется из V_k.

При заполнении 4-й магистрали (рис.6г) резервируется терминал 4₁. ДС4=(4₁,4₂) трансформируется в ДС4¢=(4¢₁,4₂). При просмотре V_k частично

помещается ДС12¢ и полностью ДС4¢. ДС12¢ трансформируется в ДС12¢¢=(1¢¢₂,1₃), а ДС4¢ удаляется из V_k.

При заполнении 5-й магистрали (рис.6д) резервируются терминалы 3₁.и 1₃. ДС31=(3₁,3₂) трансформируется в ДС31¢=(3¢₁,3₂), а ДС12¢¢=(1¢¢₂,1₃) в ДС12¢¢¢=(1¢¢₂,1¢₃). При просмотре V_k полностью помещаются ДС21¢, ДС22¢, ДС31¢, ДС12¢¢, которые удаляются из V_k.

При заполнении 6-й магистрали (рис.6е) полностью помещается ДС32.

При заданных способах кодирования ОТ1 и ОТ2, при декодировании хромосом H_k, соответствующих ОТ1 и ОТ2 и представляемых в виде вышеприведенных матриц V_k, конечные результаты совпали, хотя это и не является обязательным.

Матрица V_k просматривается при заполнении каждой магистрали. Размер матрицы V_k пропорционален числу a_s содержащихся в ней ДС.

a_s=a_k-a_n , где a_k - число терминалов, расположенных на границах ОТ, и a_n - число цепей. Отсюда оценка трудоемкости процедуры декодирования пропорциональна O(m*a_s).

Генетические операторы

Общая структура генетического поиска представлена на рис.7.

Предварительно осуществляется формирование структуры хромосомы. Эта процедура включает разбиение каждой цепи на ДС_j, разбиение множества ДС на подмножества, определение числа и размера генов в составе хромосомы: определение состава каждого гена (т.е. определение ДС, входящих в каждый ген). Далее, случайным образом генерируется исходная популяция Пи хромосом размером М. Суть случайного формирования в том, что для каждого гена каждой хромосомы случайным образом устанавливается порядок расположения в нем элементов (ДС). Для каждой хромосомы рассчитывается фитнесс. Расчет фитнесса осуществляется на основе декодирования хромосомы, т.е. фактически решения задачи трассировки.

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

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

Задается вероятность кроссинговера P_k. Затем последовательно просматриваются пары гомологичных генов (генов, расположенных в одном и том же локусе хромосом), которые с заданной вероятностью P_k меняются местами. При выборе пары хромосом для кроссинговера используется ²принцип рулетки², при котором вероятность P(H_i) Выбора хромосомы H_i определяется как:

,

где F_i - фитнесс хромосомы H_i.

Число пар хромосом W является управляющим параметром процедуры генетического поиска.

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

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

Заключительной операцией в пределах одного поколения является селекция расширенной популяции Пт=Пи+Пк+Пм. В результате селекции на основе ²принципа рулетки² отбирается новая популяция Пи лучших решений, которая является исходной для следующей генерации. Число генераций (поколений) Т, размер популяции М и параметры Рк и Рм являются управляющими параметрами, влияющими на эффективность процесса генетического поиска.

3. Экспериментальные исследования

Алгоритм был реализован на языке С++ для ПЭВМ типа IBM PC.

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

Исследования проводились следующим образом. Для каждого примера сначала фиксировалось значение Р_М и изменялись параметры P_К и М. Затем фиксировалось значение P_К и изменялись P_М и М. Для каждого набора значений P_М, P_К, и М проводилась серия из 10 экспериментов в результате которой определялось среднее, максимальное и минимальное значение Т, при котором не наблюдалось улучшения лучшего решения. Было установлено, что при значении P_К=0,4 и P_М=0,1, М=50 и Т=130 обеспечивается нахождение оптимального решения.

Исследования трудоемкости алгоритма показали, что при фиксированных значениях P_М, P_К, М и Т она имеет линейную зависимость и пропорциональна O(N), где N - число связываемых контактов.

Заключение

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

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

Понятие верхней и нижней сторон ОТ относительно, поскольку ОТ можно развернуть на 180° и верхняя сторона станет нижней, а нижняя верхней. В связи с этим возможно использовать прием, заключающийся в чередовании порядка заполнения магистралей: первая сверху, первая снизу, вторая сверху, вторая снизу и т.д. При заполнении n-ой сверху магистрали последовательно просматриваются строки матрицы V_k, начиная с первой, а при заполнении n-й снизу магистрали строки матрицы V_k просматриваются в обратном порядке, начиная с последней.

Средством повышения сходимости генетического алгоритма может стать представление решения в виде двух хромосом H¹_k и H²_k . При этом ОТ представляется, как и было показано выше, в виде двух ОТ1 и ОТ2 одновременно. Структура H¹_k соответствует ОТ1, а структура H²_k соответствует ОТ2. Заполнение магистралей производится последовательно и попеременно то в ОТ1, то в ОТ2. При трансформации некоторого ДС в ОТ1 осуществляется соответствующая трансформация в ОТ2, и наоборот.

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

Отметим, что предложенный подход полностью применим для «безсеточной» трассировки соединений разной ширины. Для этого на основе конструктивных параметров (ширина цепи, расстояние между цепями и окнами, размеры переходных контактов) рассчитываются допустимые расстояния между фрагментами. В этом случае задача трассировки сводится не к распределению фрагментов по магистралям, а к упаковке фрагментов. Модернизированная процедура декодирования будет последовательно размещать ДС «прижимая» их на допустимую величину к ранее размещенным. В качестве базиса выбирается верхняя сторона ОТ. Результатом работы будут физические координаты размещенных фрагментов.

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

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

W.K.Luk. A greedy switch box router INTEGRATION, the VLCI Journal, 3: pp. 129-149, 1985.

H.Shin and A.Sangiovanni Vincentelli. Mighty: a rip-up and reroute detailed router. Proceedings of IEEE International conference on Computer-Aided Design, pages 2-5, November 1986.

J.P.Cohoon and P.L.Heek. Beaver: A computational geometry based tool for switch box routing. IEEE Transactions on Computer-Aided Design, 7:684-697,June,1988.

M.Marek-Sadowska. Switch box routing: a retrospective.  INTEGRATION, the VLCI Journal, 13, pp. 36-65 1992.

Y.L. Lyn, Y.C. Hsu, and Tsai. Silk: A simulated evolution router. IEEE Transactions on Computer-Aided Design, 8:1108-1114,October,1989.

T.Cho, S. Pyo, and J. Heath. Parallex: A parallel approach to switch box routing. IEEE Transactions on CAD of Integrated Circuits and Systems, 13:684-693, June  1994.

Лебедев Б.К. Канальная трассировка на основе генетических процедур. Интеллектуальные САПР. Таганрог: ТРТУ, 1997, N3(6) с. 53-60.