4479-1 (Генетический алгоритм глобальной трассировки)

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

О.Б. Лебедев

1 Введение

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

Большинство алгоритмов, глобальной трассировки осуществляют последовательное построение соединений на укрупненной модели КП (волновые, лучевые, базирующиеся на построении деревьев Штейнера). [1,2,3,4,5,6,7]. Хотя на каждом шаге для каждого текущего состояния среды алгоритмы дают неплохие результаты, «камнем преткновения» является последовательность трассируемых соединений. Цепи, проложенные раньше ,могут блокировать цепи ,прокладываемые позже.

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

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

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

2. Проблемная формулировка, термины и обозначения

Для решения задачи глобальной трассировки используется графовая модель G = (X, U). Коммутационное поле разбивается на области. Вершины графа x_i Х соответствуют областям на КП. Если области соседние, то вершины x_i и x_к, соответствующие этим областям, связываются ребром u_j. Пусть задано множество цепей Т={t_i| i = 1, 2, ...}. Для каждой цепи определяется множество областей, в которых существуют контакты, связываемые этой цепью. На графовой модели G, множеству областей, связываемых цепью x_i, соответствует подмножество вершин Х_i Х. Для каждого ребра u_i, связывающего вершины, задается вес _j, равный пропускной способности между областями, соответствующими вершинам x_i и x_­k. Будем считать, что граф G метризирован, то есть каждая вершина имеет координаты. Координаты вершины принимаются равными координатам центра соответствующей области. Если области имеют один и тот же размер, то граф G представляет собой ортогональную решетку.

Далее для каждой цепи t_i на множестве вершин Х_i графа G строится минимальное связывающее дерево D_i с помощью алгоритма Прима D_i={r_k | k=1,2, … ,n_k}, где r_k – ребро минимального связывающего дерева.

Для каждого ребра r_k D_i формируется набор V_k вариантов v_ik маршрутов, связывающих на графе G соответствующие вершины. Формирование возможных маршрутов осуществляется следующим образом. Для ребра r_kD_i, связывающего x_nG и x_mG, определяется множество вершин Х_k X, смежных вершинам х_n и х_m ребра r_k,. Через множество вершин Х_к , а так же через вершины x_n и x_m проводятся новые вертикальные и горизонтальные линии.Отметим, что эти линии проходят по ребрам ортогонального графа G. В узлах пересечения этих линий лежат некоторые вершины х_i Х. Эти вершины являются узловыми для формирования вариантов. Будем считать, что варианты маршрутов проходят по тем ребрам графа G, которые лежат на этих линиях, рис 1.

Например: сформируем набор вариантов для ребра г_к, связывающего вершины х_i и х_j. Пронумеруем узлы пересечения вертикальных и горизонтальных линий. Вершина х_i лежит в узле 3, а вершина х_j в узле 10. Для данного ребра г_k существует 10 вариантов прохождения маршрута V_k = {v_k1, v_k2, v_k3, v_k4, v_k5, v_k6, v_k7, v_k8, v_k9, v_k10}

v_k1 = {3, 2, 5, 8, 11, 10}; v_k2 = {3, 6, 5, 8, 11, 10}; v_k3 = {3, 6, 9, 8, 11, 10}; v_k4 = {3, 6, 9, 12, 11, 10}; v_k5 = {3, 2, 1, 4, 7, 10}; v_k6 = {3, 2, 5, 4, 7, 10}; v_k7 = {3, 6, 5, 4, 7, 10}; v_k8 = {3, 2, 5, 8, 7, 10}; v_k9 = {3, 6, 5, 8, 7, 10}; v_k10 = {3, 6, 9, 8, 7, 10}

Такой способ обеспечивает максимальное совпадение вариантов реализации ребра r_k с вариантами ребер, смежных ребру r_k. Формирование варианта осуществляется из следующих соображений:

вариант формируется таким образом, чтобы он был минимальной длины.

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

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

Найдем в графе G ребро, у которого с_i имеет минимальное значение, и обозначим его через с_min, то есть c_min i[c_min c_i].

Для нашей задачи цель оптимизации – максимизация параметра с_min. При перезагрузках параметр с_min может принимать отрицательное значение. Для оценки качества удобнее использовать критерий, который имеет только положительные значения. Обозначим через _m – максимально возможное значение показателя _i среди всех ребер u­_i графа G, т.е. _m (_i)[ _{m i}]. В силу этого величина _m ­– c_min никогда не может быть отрицательной, т.е. _m – c_m 0. Отметим, что _m является константой.

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

Цель оптимизации – максимизация F₁.По своей сути максимизация F₁ совпадает с максимизацией c_min.

В качестве другого критерия оптимизации можно использовать другую характеристику. Обозначим через число ребер графа G для которых c_i имеет отрицательное значение. Очевидно, что целью генетического поиска должен быть поиск решения (индивидуальности) у которого имеет минимальное значение.

Пусть m – число всех ребер графа G. Введем фитнесс F₂=m - .

Цель оптимизации в таком случае – максимизация F₂

Если при оптимизации по критерию F₁ не удается найти такого решения при котором у всех ребер u_i G, соответствующие им с_i имеют положительные значения, то оптимизация по критерию F₂ минимизирует число таких ребер. Это делается из следующих соображений: чтобы обеспечить 100% реализацию (разводки) соединений, потребуется меньшее число деформаций областей или границ.

Обозначим через число ребер всех цепей, для которых выбранные и реализованные варианты соединений включают ребра u_i графа G с отрицательными значениями с_i.

Пусть N_d – общее число ребер всех максимальных связывающих деревьев.

Введем третий критерий оптимизации: F₃=N_d -

Цель оптимизации заключается в максимизации F₃. Это обеспечивает минимальное число соединений, требующих перетрассировки, т.е. оптимизация по F₃ уменьшает число перетрассируемых соединений. Если при оптимизации по F₁, имеются ребра с отрицательными с_i, то в зависимости от метода дотрассировки, деформации областей или границ, используется критерий F₂ или F₃.

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

3.1. Кодирование и декодирование хромосом

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

Например, дано КП, на котором расположено множество цепей Т = {t₁, t₂, t₃} , рис. 2.

Так как мы используем графовую модель, то КП можно представить соответственно рис. 3.

Для цепи t₁ множество связуемых вершин – Х₁ = {x₆, x₂, х₁₁}. Для цепи t₂ множество связуемых вершин – Х₂ = {x₇, x₉, x₁₃ }. Для цепи t₃ множество связуемых вершин – Х₃ = {x₅, x₁₄}. С помощью алгоритма Прима для каждой цепи строится минимальное связывающее дерево МСД. Для каждой из цепей это выглядит так:рис. 4.

После этого для каждого ребра r_ij МСД формируется набор вариантов маршрутов, связывающих на графе G соответствующие вершины.

Ребро г₁₁ (то есть первое ребро МСД для цепи 1) имеет два варианта прохождения маршрута r₁₁ = {v₁₁₁, v₁₁₂}: v₁₁₁={x₆,x₁,x₂}, v₁₁₂={x₆,x₇,x₂}.

Ребро r₁₂ (второе ребро цепи 1) имеет один вариант V₁₂₁={x₆,x₁₁}

Ребро г₂₁ (то есть первое ребро МСД для цепи 2) имеет два варианта прохождения маршрута r₂₁={v₂₁₁,v₂₁₂} : v₂₁₁={x₇,x₈,x₁₃} v₂₁₂={x₇,x₁₂,x₁₃}.

Ребро r₂₂ имеет два варианта v₂₂₁={x₁₃,x₈,x₉}, v₂₂₂={x₁₃,x₁₄,x₉}.

Ребро г₃₁ (то есть первое ребро МСД для цепи 3) имеет три варианта прохождения маршрута, r₃₁ = {v₃₁₁, v₃₁₂, v₃₁₃}, v₃₁₁={x₅,x₁₀,x₉,x₁₄}; v₃₁₂={x₅,x₄,x₉,x₁₄}; v₃₁₃={x₅,x₁₀,x₁₅,x₁₄}.

Для решения представленного на рис. 2. структура хромосомы имеет вид рис. 5

Рис. 5

Число генов равно 5. Гены g₁ и g₂ соответствуют ребрам r₁₁ и r₁₂ дерева D₁; g₃ и g₄ соответствуют ребрам r₂₁ и r₂₂ дерева D₂; g₅ соответствует ребру r₃₁ дерева D₃. Значение g₁ равно 2, т.к. для реализации r₁₁ выбран вариант V₁₁₂. g₂ равно 1, т.к. r₁₂ реализован вариантом V₁₂₁. Аналогично, т.к. r₂₁,r₂₂ и r₃₁ реализованы соответственно вариантами V₂₁₁, V₂₂₁ и V₃₁₃, то g₃=1, g₄=1, g₅=3.

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

Пусть L – число всех ребер всех МСД. L= число выводов – число цепей. Тогда объем V₁ ОЗУ, необходимой для хранения информации об вариантах реализации ребер МСД, будет , где n_v – число вариантов реализации одного ребра.

Объем V₂ ОЗУ необходимый для одной хромосомы . К₂ помимо всего прочего учитывает необходимость хранения фитнесса хромосомы.

Для популяции состоящей из М хромосом .

Таким образом, общий объем памяти имеет линейную зависимость и при заданных параметрах n_v и M пространственная сложность алгоритма O(L).

3.2 Формирование исходной популяции

Для организации генетического поиска формируется исходная популяция особей P={H_i|i=1,2,..,M}, где М размер популяции. Популяция Р- представляет собой репродукционную группу – совокупность индивидуальностей, любые две из которых H_iP и H_jP, i j могут размножаться выступая в роли «родителей». Предварительно с помощью процедуры FORM осуществляется разбиение КП на области и формирование модели КП в виде графа W=(X,U). Далее для каждой цепи t_i Т строится алгоритмом Прима один из вариантов минимального связывающего дерева D_i={r_i, l_i=1, … n_i}