Кодирование хромосомы

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

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

Генетические алгоритмы – итерационная процедура, которая обрабатывает гр. хромосом решений, названное популяцией.

Число хромосом в популяции – ее размер N. Каждая хромосома состоит из генов, каждый ген хромосомы может быть в нескольких состояниях – аллели.

Приведем соответ-е терминов генетических алгоритмов и классические задачи.

Денотип – топология расположения цепей на кристалле.

Генотип – генетическая схема кодирования топологии.

Хромосома – кодированное представление первого варианта топологии.

Ген – элемент хромосомы, задающий некоторый фрагмент топологии.

Популяция – набор хромосом.

Фитнеса – целевая функция, определяющая качество решения задачи.

Генерация – первый цикл работы генетических алгоитмов.

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

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

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

Число таких циклов называется числом генерации Т.

Стандартная схема генетического поиска. Структура г.а.

1) Определение размера популяции М, числа генерации Т, вероятности кроссовера Р(С), вероятности мутации Р(М).

2) Задание случайным образом начальной популяции П(0) размером М.

3) Т положить равным 0.

4) Выбор случайным образом М пар хромосом из популяции П(t) и применение кроссовера к каждой паре с заданной вероятностью Р(С)

5) Применение операции мутации к каждой хромосоме популяции П(t) с заданной вероятностью Р(m).

6) Отбор М хромосом с наилучшим значением F из получившейся популяции П(t) в новую популяцию П (t + 1)

7) t = t + 1

8) Если t < Т, то переход к пункту 4

9) Вывод хромосомы с наилучшими значениями.

Пусть хромосома описывает взаимное расположение цепей канала. Для этого каждой паре цепей (n, m) ставиться соответствие ген, который может принимать 3 состояния: 0 – если m должна располагаться выше n, 1 – если m должна располагаться ниже n и * – если их взаимное расположение не имеет значения или определяется из взаимного расположения остальных цепей (это происходит если цепи не имеют горизонтальных ограничений)

Для нашего примера хромосома может иметь вид, приведенный в таблице:

В строке «ген» записывается значение гена в хромосоме, задающий расположение цепей, показанное на рисунке 1.

Длина хромосомы L = N*(N–1)/2 = 6*5/2 = 15. длина хромосомы достаточно большая, что не приемлемо. Поэтому для понижения длины хромосомы используется анализ р.г.в.о и г.г.о (рис. 2)

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

Второй прием позволяющий уменьшить длину хромосомы основывается на том, если цепи не имеют горизонтальных ограничений, то их взаимное положение либо не важно, либо определяется из соотношения с остальными цепями. Такие состояния отмечены «*». Таким образом длинна хромосомы может быть определена: L = NGO – NRVO, где NGO – число горизонтальных ограничений в г.г.о.(9), а NRVO – число вертикальных ограничений в р.г.в.о.(6).

Цепи 4 и 5 не зависят друг от друга, как по горизонтали так и по вертикали. Для пары цепей (1, 6) (2,5) (3,4) (3,5) (3,6) (4,6) взаимное расположение жестко задано р.г.в.о., а а взаиморасположение цепей в (1, 2) (1, 5) (2, 4) (2, 6) (4, 5) (5, 6) (см. г.г.о) не имеет значения, так как цепи в этих парах не конфликтуют по горизонтали.

В нашем примере хромосома будет выглядеть так:

1 – должна быть выше 4, а 2 должна быть выше 3.

Получение из хромосомы эскиза канала с разведенными цепями

Для получения из хромосомы вида А=(а₁, а₂, а₃,), где а_i равна 0 или 1 эскиза канала с разведенными цепями используется граф топологии (ГТ). ГТ – ориентированный граф вида GT=(ENet, ET), где ENet – множество цепей, ET – множество направленных ребер, описывающих взаимное расположение цепей в канале.

Ребро существует тогда и только тогда, когда цепь m расположена в канале выше цепи n, т.е. на магистрали с меньшим номером. ГТ строится на основе РГВО, направленные ребра которого соответствуют параметрам цепей, взаимное расположение которых жестко задано с добавлением направленных ребер, соответствующих параметрам ветвей, образующих хромосому А. для нашего примера рис.1 ГТ будет иметь вид, приведенный на рис.3.

А=(0,0,0)

Граф топологии для хромосомы А=(0,0,0).

Канал восстанавливается из хромосомы следующим образом:

Шаг 1. Строим по хромосоме граф топологии.

Шаг 2. Полагаем i=0.

Шаг 3. Находим вершины (1 и 2 для нашего случая), у которых есть только исходящие дуги. Размещаем их на магистрали с номером i или на магистрали с меньшим номером, если это возможно и удаляем эти вершины с инцидентными им ребрами из ГТ.

Шаг 4. i=i+1

Шаг 5. Если ГТ не пуст, то возвращаемся к шагу 3.

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

Шаг 7. Возвращаем полученный образец размещения цепей в канале шириной i (см. алгоритм расслоение МПП).

Для хромосомы А=(0,0,0) имеем: на первом шаге находим вершины 1 и 2, у которых есть только исходные дуги. Цепи 1 и 2 размещаем на магистрали m1, получаем следующий граф топологии:

На втором шаге исключаем вершину 4, а цепь 4 размещаем на m2 получаем ГТ представленный на рис.5.

На третьем шаге исключаем вершину 3, а цепь 3 размещаем на магистрали 3.

На 4-ом шаге назначаем цепям 5 и 6 магистраль m4 (5 и 6 не конфликтуют ни по вертикали, ни по горизонтали).

На рис.1 показан полученный образец трассировки, который является оптимальным решением для нашего примера. Если хромосома А=(0,1,0) (отличие от представленного решения заключается в том, что цепь 4 располагается выше цепи 1), то граф топологии будет иметь вид:

Цепи 2 и 4 располагаем на магистрали m1(удаляем 1 и 4).

Цепь 1 располагаем на магистрали m2.

Цепь 3 располагаем на магистрали М3, 5 и 6 – на магистрали М4.

Эскиз канала с разведенными цепями для хромосомы А=(0,1,0) показан на рисунке:

Подсчитаем суммарную длину вертикального сегмента:

Целевая функция оценки хромосомы

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

ГА обычно используют для минимизации (максимизации), но желательно, чтобы целевая функция была положительной. В нашем случае задача заключается в минимизации целевой функции. Принимая во внимание характеристики задач канальной трассировки целевая функция может быть определена следующим образом:

F(A)=(Used Track(A)+2)*C + Total Vert Seg(A)

C – число контактов ( 8 линеек Top или Bottom )

2 – число слоев печатной платы

Программная функция Used Track(A) определяет число магистралей (в нашем примере 4) занимаемые каналом, полученным при восстановлении хромосомы А, а программная функция Total Vert Seg(A) определяет длину вертикальных сегментов цепи в полученном решении.

Длина вертикального сегмента цепи определяется как расстояние между контактами и переходными отверстиями, которые соединяют вертикальные и горизонтальные сегменты. Например для канала приведенного на рис.1 занятых магистралей равно 4, длина вертикального сегмента равна 22, т.о.целевая функция хромосомы F(A)=(4+2)*8+22=70, а для канала с хромосомой А=(0,1,0) (рис.7) F(A)=72.

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