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

Например, дано КП, на котором расположено множество цепей Т = {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_i ÎP и H_j ÎP, i¹j могут размножаться выступая в роли «родителей». Предварительно с помощью процедуры FORM осуществляется разбиение КП на области и формирование модели КП в виде графа W=(X,U). Далее для каждой цепи t_i Î Т строится алгоритмом Прима один из вариантов минимального связывающего дерева D_i ={r_i , l_i =1, … n_i }

Затем для каждого r_ij синтезируется набор V_ij вариантов маршрутов в ортогональном графе G, реализующих ребро r_{ij .} Пусть n_ij =| V_ij |- число вариантов реализации ребра r_{ij .}

Определяется длина L хромосомы, являющейся носителем информации о конкретном решении:

Параметр L определяет число генов в хромосоме. С помощью графика соответствия Q устанавливается соответствие Г(G, Q, R) между генами хромосомы и ребрами минимальных связывающих деревьев для всех цепей.

G={g_n | n=1, 2,… ,L}; R={r_ij | i=1, 2, … ,n_i , j=1,2, … n_i }

Образом Г(r_ij ) является ген g_n . Прообразом Г­­^-1 (g_n ) является ребро r_ij Значением гена g_n , будет номер варианта реализации ребра r_ij =Г­­^-1 (g_n ) .

Ген g_n может принимать любое значение от 1 до n_ij .

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