Генетичний алгоритм глобального трасування
О.Б. Лебедєв
1
Введення
Основною метою завдання
глобальної трасування є рівномірне та доцільне розподіл
ресурсів комутаційного поля для створення сприятливих умов для
подальшої детальної трасування.
Більшість алгоритмів,
глобальної трасування здійснюють послідовне побудова з'єднань на
укрупненій моделі КП (хвильові, променеві, що базуються на побудові дерев
Штейнера). [1,2,3,4,5,6,7]. Хоча на кожному кроці для кожного поточного стану
середовища алгоритми дають непогані результати, «каменем спотикання» є
послідовність трасуванню з'єднань. Ланцюги, прокладені раніше, можуть
блокувати ланцюга, що прокладаються пізніше.
Іншим недоліком
є те, що більшість алгоритмів використовують критерії більшою мірою
враховують параметри з'єднань (наприклад: загальна довжина) і в меншому ступені
параметри комутаційного поля, що не зовсім узгоджується з головною метою
глобальної трасування.
Виходячи з цих
міркувань, в роботі використовується Комбінаторний підхід, заснований на методах
генетичної адаптації, при якому в один і той же момент часу розглядаються
всі з'єднання, а критерій враховує розподіл ресурсів КП.
При розробці
генетичних процедур основний вплив приділялася розробці з урахуванням знань про
предметної області методів кодування рішень, модифікації генетичних
операторів і організації еволюційного процесу.
2.
Проблемна формулювання, терміни та позначення
Для вирішення завдання
глобальної трасування використовується Графова модель G = (X, U). Комутаційне
поле розбивається на області. Вершини графа xi
