 |
Лучевой алгоритм трассировки абрайтеса.
|
|
|
|
В этом алгоритме уменьшение временных затрат достигается за счёт распространения волны не по всему полю платы, а только вдоль лучей. Идея: при распространении волны фронт занимает не все свободные соседние ячейки ДРП, а лишь одну, т.о. последовательность фронтов – луч.
Во-вторых, лучевой алгоритм трасс Абрайтеса из начала А и конца В трассы распространяются навстречу друг другу по двум лучам А1, А2, В1, В2.
Лучи А1,2 и В1,2 называются разноимёнными, лучи поочерёдно распространяются (шагают) до тех пор, пока разноимённые лучи не пересекутся или пока 4 луча не смогут продвигаться дальше, т.е. окажутся в тупике. В первом случае, осуществляется переход ко второму этапу – проведению трассы. Для этого от пересечения лучей осуществляют возврат по ячейкам, принадлежащим лучам, в исходные А и В ячейки трассы (используя метод путевых координат). Во втором случае, трассу проложить невозможно.
| | ® | ® | ® | ® | ||||||
| А | ®А2 | ® | ® | ® | # | # | | |||
| ¯А1 | ¯ | # | ¯В1 | В2 | ||||||
| ¯ | ¯ | # | ¯ | В | ||||||
| ¯ | ¯ | # | ¯ | |||||||
| ¯ | # | # | # | ¯ | ||||||
| ¯ | ¯ | |||||||||
Пример приведён на рисунке:
Прежде всего, необходимо выбрать приоритетные направления движения лучей:
Для луча
А1–вниз (основное),вправо(дополнительное);
А2–вправо(основное),вниз (дополнительное);
В1–влево(основное), вверх (дополнительное);
В2–вверх(основное), влево (дополнительное).
Каждый луч осуществляет шаг движения по своему основному направлению или, если соответствующее этому направлению соседняя ячейка занята – по дополнительному.
|
|
|
После выполнения очередного шага всеми лучами, производится проверка на пересечение разноимённых лучей.
Вывод луча из тупика осуществляется следующим образом: луч возвращается в ту ячейку, где он изменил направление движения с основного на дополнительное. Затем, продвигается на шаг в направлении, противоположном дополнительному и делается попытка продвижения его по основному направлению.
Если луч снова оказался в тупике, делается ещё один шаг в направлении, противоположном дополнительному.
Эта процедура повторяется до тех пор, пока луч не получит возможность продвигаться по своим приоритетным направлениям или не будет заблокировано направление, противоположное дополнительному. В последнем случае продвижение луча прекращается.
Если все 4 луча будут заблокированы, то трассу проложить нельзя.
Отметим, что при выводе i-го луча из тупика, другие лучи останавливаются для того, чтобы продвижение лучей было равномерным.
На рисунке луч В1 после 3-х шагов оказывается в тупике в ячейке с координатами (8,6).
При выводе из тупика, В1 сначала возвращается в ячейку (8,4), затем делает шаги в ячейке (8,3) и (8,2) и далее продвигается по своему основному направлению до встречи с лучом А1.
Лучевой алгоритм трассировки осуществляет проведение пути минимальной длины без пересечений.
Вероятность нахождения пути этим алгоритмом меньше, чем алгоритмом Ли.
Целевая функция оценки хромосомы. Кроссовер и мутация
Когда генетические алгоритмы применяются для решения оптимизационных задач, важнейшим требованием является разработка целевой функции (ЦФ) для полученных решений.
ГА обычно используют для минимизации (максимизации), но желательно, чтобы целевая функция была положительной. В нашем случае задача заключается в минимизации целевой функции. Принимая во внимание характеристики задач канальной трассировки целевая функция может быть определена следующим образом:
|
|
|
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) направлена в первую очередь на минимизацию ширины канала, а во вторую на минимизацию суммарной длины соединений.
Кроссовер и мутация
Согласно структуре ГА все хромосомы (случайно полученные решения) оцениваются целевой функцией F(A). Далее, согласно процедуре селекции (отбора) производится построение списка упорядоченных хромосом. На основе анализа этого списка производится подбор пар хромосом на основе элитной селекции(хромосома с наилучшим значением целевой функции и случайно выбранной хромосомой).
После подбора пар применяется оператор кроссовера – ОК с вероятностью Pc к каждой паре хромосом. Исходная хромосома называется родительской, а хромосомы, полученные после операторов ГА – потомки.
Алгоритм применения ОК реализуется следующим образом:
Шаг 1. i=0
Шаг 2. Выбрать хромосом с наилучшим значением целевой функции как первого родителя.
Шаг 3. Выбрать произвольно второго родителя.
Шаг 4. Сгенерировать случайное число 
.
Шаг 5. Если RND<Pc, то применить оператор кроссовера к выбранным хромосомам и добавить получившихся потомков к популяции.
Шаг 6. i=i+1.
Шаг 7. Если i<Mm, переход к шагу 2 (Mm – различные популяции).
Под оператором кроссовера подразумевается обмен, скрещивание генетического материала между двумя различными хромосомами (потенциальными родителями). После окончания оператора кроссовера полученные потомки подвергаются мутации. В большинстве случаев может быть выбран стандартный двухточечный оператор кроссовера. Первая и вторая точки разрыва в таком операторе кроссовера выбираются случайно.
|
|
|
Часть первого родителя перед первой и после второй точки разреза копируется в аналогичные места в потомке 1. Место между первой и второй точкой разреза во втором родителе копируется в аналогичное место первого потомка. Второй потомок строится аналогично.
Рассмотрим пример реализации оператора кроссовера. Пусть вертикальная волнистая линия означает точку разреза оператора кроссовера.
| Родитель 1 | F(A)=72 (рис.7) | |||
| Родитель 2 | F(A)=7 | |||
| Потомок 1 | F(A)=70 (рис.1) | |||
| Потомок 2 | F(A)=77 |
Потомок 2 аналогичен родителю 2. В данном случае получен потомок 1 с лучшим значением целевой функции, чем значение целевой функции (72,77).
Мутация произвольно изменяет 1 ген выбранной хромосомы случайно изменяя значение гена с вероятностью РМ равной норме мутации. Алгоритм применения операции мутации выглядит следующим образом:
Шаг 1. i=i+1.
Шаг 2. Сгенерировать случайное число RND [0,1]
Шаг 3. Если RND< РМ, то применить ОМ к i-ой хромосоме М.
Шаг 4. i=i+1.
Шаг 5 если i<M, то к шагу 1.
Смысл ОМ введение добавочных изменений в популяцию. В простейшем случае может быть выбрана точечная мутация, она заключается в изменении произвольного гена в хромосоме с вероятностью РМ. Это происходит следующим образом: один из генов хромосомы выбирается случайно, а затем меняет свое значение на противоположное. Пример хромосомы (до применения ОМ): 0,(1),0. Значение целевой функции – 72.
Хромосома после применения ОМ: 0,(0),0, значение целевой функции – 70 – min. Выбранная точка мутации показана в скобках. После применения ОМ получается хромосома с лучшим значением целевой функции. Дальнейшее улучшение работы генетического алгоритма можно получить за счет сортировки гена в хромосоме или путем использования более сложной целевой функции. Кроме того, можно анализировать параллельные и последовательно – параллельные методы генетического поиска.
|
|
|
Теоретическая временная сложность рассмотренного генетического алгоритма составляет t*(M*Pc*2)*2*PM*O(N2)
O(N2) – временная сложность декодирования хромосомы;
M – число цепей;
t – число поколений.
|
|
|
