О.Б. Лебедєв
1 Введення
Основною метою задачі глобальної трасування є рівномірний і доцільне розподіл ресурсів комутаційного поля для створення сприятливих умов для подальшої детальної трасування.
Більшість алгоритмів, глобальної трасування здійснюють послідовне побудова сполук на укрупненої моделі КП (хвильові, променеві, що базуються на побудові дерев Штейнера). [1,2,3,4,5,6,7]. Хоча на кожному кроці для кожного поточного стану середовища алгоритми дають непогані результати, «каменем спотикання» є послідовність трассируемого сполук. Ланцюги, прокладені раніше, можуть блокувати ланцюги, прокладаються пізніше.
Іншим недоліком є те, що більшість алгоритмів використовують критерії більшою мірою враховують параметри сполук (наприклад: загальна довжина) і у меншій мірі параметри комутаційного поля, що не зовсім узгоджується з головною метою глобальної трасування.
Виходячи з цих міркувань, в роботі використовується комбінаторний підхід, заснований на методах генетичної адаптації, при якому в один і той же момент часу розглядаються всі з'єднання, а критерій враховує розподіл ресурсів КП.
При розробці генетичних процедур основний вплив приділялася розробці з урахуванням знань про предметну область методів кодування рішень, модифікації генетичних операторів і організації еволюційного процесу.
2. Проблемна формулювання, терміни і позначення
Для вирішення задачі глобальної трасування використовується графова модель G = (X, U). Комутаційне поле розбивається на області. Вершини графа xi Î Х відповідають областям на КП. Якщо області сусідні, то вершини xi і XК, відповідні цим областям, зв'язуються ребром uj. Нехай задано безліч ланцюгів Т = {ti | i = 1, 2, ...}. Для кожного ланцюга визначається безліч областей, в яких існують контакти, які пов'язують цієї ланцюгом. На графових моделі G, безлічі областей, що пов'язуються ланцюгом xi, відповідає підмножина вершин Хi Ì Х. Для кожного ребра ui, що зв'язує вершини, задається вага aj, рівний пропускної здатності між областями, відповідними вершин xi і xk. Будемо вважати, що граф G метрізірован, тобто кожна вершина має координати. Координати вершини приймаються рівними координатами центру відповідної області. Якщо області мають один і той же розмір, то граф G є ортогональну грати.
Далі для кожного кола ti на безлічі вершин Хi графа G будується мінімальне зв'язує дерево Di з допомогою алгоритму Прима Di = {rk | k = 1,2, ..., nk}, де rk - ребро мінімального зв'язує дерева.
Для кожного ребра rk ÎDi формується набір Vk варіантів vik маршрутів, що зв'язують на графі G відповідні вершини. Формування можливих маршрутів здійснюється наступним чином. Для ребра rkÎDi, що зв'язує xnÎG і xmÎG, визначається безліч вершин Хk Ì X, суміжних вершин хn і хm ребра rk,. Через безліч вершин Хк, а так само через вершини xn і xm проводяться нові вертикальні і горизонтальні лініі.Отметім, що ці лінії проходять по ребрах ортогонального графа G. У вузлах перетину цих ліній лежать деякі вершини хi Î Х. Ці вершини є вузловими для формування варіантів. Будемо вважати, що варіанти маршрутів проходять за тими ребрам графа G, які лежать на цих лініях, рис 1.
Наприклад: сформуємо набір варіантів для ребра гк, що зв'язує вершини хi і хj. Пронумеруємо вузли перетину вертикальних і горизонтальних ліній. Вершина хi лежить у вузлі 3, а вершина хj у вузлі 10. Для даного ребра гk існує 10 варіантів проходження маршруту Vk = {vk1, vk2, vk3, vk4, vk5, vk6, vk7, vk8, vk9, vk10}
vk1 = {3, 2, 5, 8, 11, 10}; vk2 = {3, 6, 5, 8, 11, 10}; vk3 = {3, 6, 9, 8, 11, 10}; vk4 = {3, 6, 9, 12, 11, 10}; vk5 = {3, 2, 1, 4, 7, 10}; vk6 = {3, 2, 5, 4, 7, 10}; vk7 = {3 , 6, 5, 4, 7, 10}; vk8 = {3, 2, 5, 8, 7, 10}; vk9 = {3, 6, 5, 8, 7, 10}; vk10 = {3, 6 , 9, 8, 7, 10}
Такий спосіб забезпечує максимальний збіг варіантів реалізації ребра rk з варіантами ребер, суміжних ребру rk. Формування варіанта здійснюється з таких міркувань:
варіант формується таким чином, щоб він був мінімальної довжини.
варіанти формуються, щоб забезпечувалося максимально можливе збіг варіантів різних ребер одного ланцюга один з одним.
Нехай є деяке рішення задачі глобальної трасування, що полягає в тому, що для всіх ребер гk всіх МСД-ланцюгів, обрані варіанти їх реалізації. Введемо деякі позначення. Позначимо через bi число ланцюгів, що проходять по ребру ui графа G. Для кожного ребра ui графа G введемо параметр сi, рівний сi = ai - bi.
Знайдемо в графі G ребро, у якого сi має мінімальне значення, і позначимо його через Сmin, тобто cmin ® "i [cmin £ ci].
Для нашої задачі мета оптимізації - максимізація параметра Сmin. При перезагрузках параметр Сmin може приймати від'ємне значення. Для оцінки якості зручніше використовувати критерій, який має тільки позитивні значення. Позначимо через am - максимально можливе значення показника ai серед всіх ребер ui графа G, тобто am ® ("i) [am ³ ai]. У силу цього величина am - cmin ніколи не може бути негативною, тобто am - cm ³ 0. Зазначимо, що am є константою.
Як фітнесу (оцінки якості) індивідуальності буде використовуватися критерій
Мета оптимізації - максимізація F1.По своєю суттю максимізація F1 збігається з максимізацією cmin.
В якості іншого критерію оптимізації можна використовувати іншу характеристику. Позначимо через g число ребер графа G для яких ci має негативне значення. Очевидно, що метою генетичного пошуку має бути пошук рішення (індивідуальності) у якого g має мінімальне значення.
Нехай m - число всіх ребер графа G. Введемо фітнес F2 = m - g.
Мета оптимізації в такому випадку - максимізація F2
Якщо при оптимізації за критерієм F1 не вдається знайти такого рішення при якому у всіх ребер ui Î G, відповідні їм сi мають позитивні значення, то оптимізація за критерієм F2 мінімізує число таких ребер. Це робиться з наступних міркувань: щоб забезпечити 100% реалізацію (розведення) з'єднань, буде потрібно менше число деформацій областей або меж.
Позначимо через j число ребер всіх ланцюгів, для яких обрані й реалізовані варіанти з'єднань включають ребра ui графа G з негативними значеннями сi.
Нехай Nd - загальне число ребер всіх максимальних зв'язують дерев.
Введемо третій критерій оптимізації: F3 = Nd - j
Мета оптимізації полягає в максимізації F3. Це забезпечує мінімальне число з'єднань, що вимагають перетрассіровкі, тобто оптимізація по F3 зменшує число перетрассіруемих сполук. Якщо при оптимізації за F1, є ребра з негативними сi, то залежно від методу дотрассіровкі, деформації областей або меж, використовується критерій F2 або F3.
3. Розробка генетичних процедур для задачі глобальної трасування
3.1. Кодування і декодування хромосом
Для вирішення задачі глобальної трасування використовуються генетичні методи оптимізації. Уявімо рішення у вигляді хромосоми. Кодування здійснюється наступним чином. Хромосома складається з генів. Кількість генів у хромосомі Hi дорівнює кількості ребер мінімальних зв'язують дерев для всіх ланцюгів, розташованих на КП. Значенням гена є номер варіанта із заданого набору варіантів маршрутів, що зв'язують на графі G відповідні вершини.
Наприклад, дано КП, на якому розташована безліч ланцюгів Т = {t1, t2, t3}, рис. 2.
Так як ми використовуємо графову модель, то КП можна представити відповідно рис. 3.
Для ланцюга t1 безліч з'єднуваних вершин - Х1 = {x6, x2, х11}. Для ланцюга t2 безліч з'єднуваних вершин - Х2 = {x7, x9, x13}. Для ланцюга t3 безліч з'єднуваних вершин - Х3 = {x5, x14}. За допомогою алгоритму Прима для кожного кола будується мінімальне зв'язує дерево МСД. Для кожної з ланцюгів це виглядає так: рис. 4.
Після цього для кожного ребра rij МСД формується набір варіантів маршрутів, що зв'язують на графі G відповідні вершини.
Ребро Г11 (тобто перше ребро МСД для ланцюга 1) має два варіанти проходження маршруту r11 = {v111, v112}: v111 = {x6, x1, x2}, v112 = {x6, x7, x2}.
Ребро r12 (друге ребро ланцюга 1) має один варіант V121 = {x6, x11}
Ребро г21 (тобто перше ребро МСД для ланцюга 2) має два варіанти проходження маршруту r21 = {v211, v212}: v211 = {x7, x8, x13} v212 = {x7, x12, x13}.
Ребро r22 має два варіанти v221 = {x13, x8, x9}, v222 = {x13, x14, x9}.
Ребро г31 (тобто перше ребро МСД для ланцюга 3) має три варіанти проходження маршруту, r31 = {v311, v312, v313}, v311 = {x5, x10, x9, x14}; v312 = {x5, x4, x9, x14 }; v313 = {x5, x10, x15, x14}.
Для вирішення представленого на рис. 2. структура хромосоми має вигляд рис. 5
Рис. 5
Кількість генів дорівнює 5. Гени g1 і g2 відповідають ребрам r11 і r12 дерева D1; g3 і g4 відповідають ребрам r21 і r22 дерева D2; g5 відповідає ребру r31 дерева D3. Значення g1 дорівнює 2, тому що для реалізації r11 обраний варіант V112. g2 дорівнює 1, тому що r12 реалізований варіантом V121. Аналогічно, тому що r21, r22 і r31 реалізовані відповідно варіантами V211, V221 і V313, то g3 = 1, g4 = 1, g5 = 3.
Відзначимо, що між структурою і виглядом хромосоми з одного боку і рішенням (розподілом сполук на КП) з іншого боку існує взаємно - однозначна відповідність. Відмінною особливістю запропонованої структури хромосоми є те, що відсутня будь-яка залежність між генами, обумовлена самою структурою. Це властивість виключає можливість появи нелегальних хромосом, подібно до того, як це відбувається з хромосомами, що представляють собою Спискові структури. У свою чергу це спрощує реалізацію розглянутих нижче генетичних операторів.
Нехай L - число всіх ребер всіх МСД. L = число висновків - число ланцюгів. Тоді обсяг V1 ОЗУ, необхідної для зберігання інформації про варіанти реалізації ребер МСД, буде , Де nv - число варіантів реалізації одного ребра.
Обсяг V2 ОЗУ необхідний для однієї хромосоми . К2 крім усього іншого враховує необхідність зберігання фітнесу хромосоми.
Для популяції складається з М хромосом .
Таким чином, загальний обсяг пам'яті має лінійну залежність і при заданих параметрах nv і M просторова складність алгоритму ~ O (L).
3.2 Формування вихідної популяції
Для організації генетичного пошуку формується вихідна популяція особин P = {Hi | i = 1,2, .., M}, де М розмір популяції. Популяція Р-представляє собою репродукційного групу - сукупність індивідуальностей, будь-які дві з яких HiÎP і HjÎP, i ¹ j можуть розмножуватися виступаючи в ролі «батьків». Попередньо за допомогою процедури FORM здійснюється розбиття КП на області і формування моделі КП у вигляді графа W = (X, U). Далі для кожного кола ti Î Т будується алгоритмом Прима один з варіантів мінімального зв'язує дерева Di = {ri, li = 1, ... ni}
Потім для кожного rij синтезується набір Vij варіантів маршрутів у ортогональному графі G, що реалізують ребро rij. Нехай nij = | Vij | - число варіантів реалізації ребра rij.
Визначається довжина L хромосоми, що є носієм інформації про конкретному рішенні:
Параметр L визначає число генів у хромосомі. За допомогою графіка відповідності Q встановлюється відповідність Г (G, Q, R) між генами хромосоми і ребрами мінімальних зв'язують дерев для всіх ланцюгів.
G = {gn | n = 1, 2, ..., L}; R = {rij | i = 1, 2, ..., ni, j = 1,2, ... ni}
Образом Г (rij) є ген gn. Прообразом Г-1 (gn) є ребро rij Значенням гена gn, буде номер варіанта реалізації ребра rij = Г-1 (gn).
Ген gn може приймати будь-яке значення від 1 до nij.
У роботі використовується принцип випадкового формування вихідної популяції.
Для цього в межах кожної хромосоми Нк кожен ген gn приймає випадкове значення в межах від 1 до nij, де nij число варіантів реалізації ребра rij = Г-1 (gn).
Керованими параметрами при формуванні популяції є М - розмір популяції, nmax - максимальне число варіантів реалізації ребер, тобто ("Ij) [nij nmax]. Якщо можливе число варіантів nij більше nmax то виникає можливість формування альтернативних наборів варіантів Vij для rij. Крім того існує можливість побудови альтернативних МСД Di для однієї і тієї ж ланцюга ti.
Все це дає можливість для комбінування при синтезі вихідної популяції. Відомо, що для виходу з локальних оптимумів використовується механізм зміни вихідних популяцій.
У найпростішому випадку це можна реалізувати за допомогою повторної, випадкової генерації.
3.3 Генетичні оператори
Для отримання нового рішення (індивідуальності) використовуються генетичні оператори: кросинговер та мутація.
Кросинговер полягає у взаємному обміну генами між «батьками» - хромосомами попередньо вибраної пари.
У нашому випадку всі хромосоми гомологічних, тому що мають одну і ту ж структуру, одну і ту ж довжину і несуть інформацію про одне й те ж наборі МСД. Гени, розташовані в одному і тому ж локусі хромосом, гомологічних, тому що несуть інформацію про одне й те ж ребрі хромосоми.
Попередньо задається величина PK - ймовірність кросинговеру і вводиться прапорець FG з двома станами «виконувати», «не виконувати». Вихідний стан FG «не виконувати». При виконанні кросинговеру послідовно проглядаються локуси вибраної пари хромосом. З вірогідністю Pk «прапорець» FG переходить у стан «виконувати». Якщо FG перейшов у стан «виконувати», то проводиться обмін генами між парою хромосом в поточному локусі, далі «прапорець» переходить в стан «не виконувати», а потім здійснюється перехід до наступного локусу.
Такий алгоритм кросинговеру забезпечує мультіобмен. Число пар обмінюються генів визначається параметром Pk.
Операція мутації полягає в зміні значення гена. Алгоритм мутації реалізується наступним чином.
Попередньо, для кожного гена gn, визначається діапазон його можливих значень від 1 до yn, де yn - число сформованих варіантів реалізації ребра .
Задається параметр PM - ймовірність мутації і «прапорець» FG з двома станами «виконувати» і «не виконувати». Вихідний стан FG - «не виконувати».
Послідовно вибираються хромосоми з поточної популяції. У межах обраної хромосоми послідовно проглядаються гени. Після переходу до чергового гену, FG з імовірністю PM переходить у стан «виконувати». Якщо FG перейшов у стан «виконувати», то випадковим чином ген gn приймає одне зі значень у заданому діапазоні, за винятком значення, яке ген має перед мутацією. Далі FG переходить в стан «не виконувати» і вибирається наступний ген хромосоми, або наступна хромосома.
Для поліпшення процесу пошуку кращого рішення введемо диференціюється значення показника , Що приймає різні значення в залежності від значення гена.
Введемо для гена gn оцінку , Де ln - число ребер ui, що входять у маршрут vijk реалізує ребро
, Відповідне гену gn.
- Число таких ui,, що входять до vijk, для яких показник завантаження ci має негативне значення.
Кn змінюється від 0 до 1. Чим більше Kn, тим "гірше" маршрут vijk, і тим більше підстав до його зміну.
Значення показника з урахуванням Кn для гена gn визначається наступним чином
параметр D пов'язаний з Pm наступним співвідношенням
,
тобто D змінюється від 0 до (1-Pm).
У граничному випадку
Як видно з алгоритмів, що реалізують процедури кросинговеру і мутації, часова складність операторів кросинговеру і мутації від імені однієї хромосомі мають лінійну залежність, , Де L - довжина хромосоми.
3.4 Загальна структура генетичного пошуку для глобальної
трасування
Відповідно до методики описаної вище на перших підготовчих етапах здійснюється розбиття КП на площині. Для всіх ланцюгів будуються мінімальні зв'язують дерева. Для всіх ребер МСД формуються набори варіантів реалізують їх сполук. Керуючими параметрами генетичної адаптації є: М - розмір вихідної популяції, Т - число генерацій, PK - ймовірність кросинговеру, Pm - ймовірність мутації.
Після сформування вихідної популяції Пі для кожної індивідуальності розраховується фітнес.
Алгоритм розрахунку фітнесу має наступний вигляд: у якості вихідних даних використовується вектор А = {al | l = 1,2, ...}, де al - пропускна здатність ребра ul. Для розрахунку фітнесу використовується вектор B, що має ту ж розмірність, що і вектор А. Спочатку елементи мають нульове значення. Вектор У служить для обліку завантаження ребер Ur усіма ланцюгами.
Значення ростуть послідовно і, після перегляду всіх генів, bl є значенням числа ланцюгів, що проходять через ul.
Маючи вектора А і В, розраховуються значення показників cl = al-bl для кожного ребра ul. На підставі значень cl расcчітиваются критерії F1, F2 і F3.
Якщо врахувати, що кількість варіантів має фіксоване значення і зазвичай, не перевищує 4-6, то трудомісткість підрахунку вектора В лінійна і пропорційна довжині хромосом. Трудомісткість процедури пошуку cmin також лінійна. У зв'язку з цим трудомісткість tф розрахунку фітнесу для однієї хромосоми має лінійну залежність від довжини хромосоми tф ~ O (L).
Після розрахунку фітнесу для вихідної популяції застосовується оператор кросинговеру.
Селекція батьківських пар хромосом здійснюється або на основі «принципу рулетки», або на основі рейтингу популяції.
З цією метою всі хромосоми популяції сортуються відповідно з розрахованими значеннями фітнесу. Після цього здійснюється селекція пари споріднених хромосом за правилом: i - я з i +1 - ой.
Для кожної нової індивідуальності, утвореної в результаті кросинговеру, розраховується фітнес. Після кросинговеру поточна популяція ПТ включає вихідну ПІ і популяцію ПК, що утворилася в результаті виконання кросинговеру.
ПТ = ПІ + ПК.
Далі до всіх індівідуальнастям ПТ застосовується оператор мутації. Для всіх індивідуальностей популяції ПМ, що утворилися в результаті мутації розраховується фітнес. Заключним етапом у межах одного покоління є процес редукції популяції ПТ = ПІ + ПК + ПМ до розмірів ПІ на основі селективного відбору. Селекція здійснюється на основі "принципу рулетки".
Імовірність вибору індивідуальності визначається як:
За допомогою коефіцієнтів Кi, які для «кращих» індивідуальностей мають великі значення, ніж у «гірших», досягаються збільшення ймовірності вибору «кращих» індивідуальностей.
Тимчасова складність алгоритму визначається загальними (підготовчими) витратами to і витратами в межах кожного покоління td. Загальні витрати складаються з витрат на побудові мінімальних зв'язують дерев td, формування варіантів реалізації ребер tb, і формування вихідної популяції tи: to = td + tb + tи.
Витрати на побудову МСД знаходяться в залежності від числа МСД. З іншого боку при побудові конкретного МСД витрати пропорційні квадрату числа пов'язують вершин. Враховуючи, що число ребер n всіх МСД пропорційно числу МСД, можна вважати, що оцінка ВСА tо лежить в межах О (n)-O (n2), причому чим більше n тим ближче до О (n).
Витрати в межах покоління tn складаються з витрат на оператори кросинговеру tк, мутації tm, розрахунку фітнесу tф і селекції tс.
Як вже зазначалося вище витрати tк, tм і tф при обробці однієї хромосоми мають лінійну залежність від n. tс має лінійну залежність від обсягу популяції М. Тоді тимчасові витрати в межах покоління мають оцінку О (n × M). Для Т генерацій часова складність алгоритму має оцінку О (n × M × T). Враховуючи що параметри М і Т порівнянні або значно менше n, можна вважати, що оцінка часової складності всього алгоритму в цілому лежить в межах О (n2)-O (n3).
4. Експериментальні дослідження генетичного алгоритму глобальної трасування
Алгоритм глобальної трасування був реалізований на мові С + +, експериментальні дослідження проводилися на ЕОМ типу IBM PC / AT Pentium 133.
При проведенні експериментальних досліджень переслідувалися дві мети:
Першою метою було дослідження механізмів генетичного пошуку для задачі глобальної трасування. Для досягнення цієї мети досліджувався вплив управлінців операторів, таких як: розмір популяції М, кількість поколінь Т, ймовірність мутації РМ, ймовірність кросинговеру РК. У результаті цих досліджень визначалося таке поєднання значень цих параметрів, що забезпечує найвищу ефективність генетичних процедур для задачі глобальної трасування.
Другою метою було дослідження власне, ефективності розробленого генетичного алгоритму. Досліджувалися впливу таких параметрів, як кількість варіантів маршрутів для кожного ребра.
Для проведення досліджень були синтезовані 5 тестових прикладів.
Основні характеристики прикладів.
Використовувалося КП з розмірами 10 * 10 (10 дискретом по горизонталі і 10 дискретом по вертикалі). Висновки, які пов'язують ланцюгами, розміщувалися всередині дискретний. У кожному дискретний тільки один висновок одного ланцюга. Число висновків, що пов'язуються однією метою - від 2 до 5. В один дискрет призначалося до 10 висновків. Середнє число ланцюгів - 200 -250. Призначення висновків у дискрети здійснювалося випадковим чином.
Оптимізація проводилася за критерієм:
F1 = ("I) [Cmin £ Ci = ai-bi]
Якщо виявлялося, що СMI