Б. К. Лебедєв
Введення
Зважаючи грандіозної складності трасування НВІС розбивається на два етапи: глобальна і детальна. При глобальної трасуванні вирішується два завдання: розбивка комутаційного поля на області і розподіл сполук по областях. Детальна трасування полягає в проектуванні топології з'єднань усередині областей. Традиційно комутаційне поле розбивається на два типи областей: канал і комутаційний блок (switch box).
У класичній постановці комутаційний блок - це прямокутна область на всіх чотирьох сторонах якої розміщені у фіксованих позиціях термінали (висновки). Термінали позначені цифрами - номерами підключених до них ланцюгів. Завдання полягає в тому щоб зробити термінали кожному ланцюзі електрично зв'язковими так, щоб ланцюги і перехідні отвори, реалізують зв'язку, вписувалися в область трасування і задовольняли конструктивним обмеженням.
Зазвичай проблема вирішується за додатково накладеними обмеженнями, одним з яких є кількість шарів. У роботі розглядається двошарова трасування.
Завдання трасування в обмеженій прямокутної області є NP-повною. Тому незважаючи на велику кількість розробок, проблема побудови ефективного трасувальника є актуальною.
Більшість алгоритмів трасування у комутаційному блоці грунтуються на евристика, що реалізують в тій чи іншій мірі ідею послідовної трасування [1,2,3,4]. У процесі прокладки на кожному кроці використовуються правила спрямовані на мінімізацію впливу прокладається ланцюга на невбитій. Проте повною мірою проекстраполіровать всі ситуації не представляється можливим. Це призводить до необхідності додаткової трасування. Основу цих алгоритмів складають два принципи: локальна деформація, розрив частини сполук і перетрассіровка їх різними методами [2]. Але на жаль і тут виникає проблема черговості перетрассіруемих сполук. У зв'язку з цим інтерес представляють комбінаторні алгоритми, що оперують з усіма сполуками. Серед математичних методів забезпечують комбінаторний підхід до розв'язуваної задачі останнім часом найбільше поширення одержали методи моделювання відпалу та еволюційного програмування. Особливий інтерес представляють генетичні алгоритми, засновані на механізмах природної селекції та генетики [5,6].
У роботі запропоновано нові генетичні процедури для вирішення задачі трасування у комутаційному блоці, що враховують знання про проблемну області. Розроблено нові структури та принципи кодування хромосом, модифіковані генетичні оператори, і структура генетичного пошуку. Проведено експериментальні дослідження.
1. Формулювання завдання, основні терміни і позначення
Дамо формальний опис завдання трасування комутаційного блоку (ЗТКБ). Дано: верхній ряд контактів К1 = {к1i} і нижній ряд контактів К2 = {к2i}, пронумеровані зліва направо, лівий ряд контактів К3 = {к3i} і правий ряд контактів К4 = {к4i}, пронумеровані зверху вниз, і розташовані на сторонах прямокутника. До них відповідно підходять безлічі ланцюгів N1 = {n1i}, N2 = {n2i}, N3 = {n3i}, N4 = {n4i}, N = N1 È N2 È N3 È N4 - загальне безліч ланцюгів. На область трасування (ОТ) накладена сітка (рис.1). Термінали (контакти) збігаються з лініями сітки. З'єднання підходять до контактів і поширюються в області трасування тільки по лініях сітки.
На ріс.1в от2 є розгорнутий на 90 ° от1 на рис.1а. Кожен ланцюг представляється у вигляді зв'язного набору вертикальних і горизонтальних фрагментів. Не допускаються накладення один на одного вертикальних і горизонтальних фрагментів, які належать різним ланцюгах, не допускається їх перетин у спільному ескізі топології. Кожен ланцюг розбивається на двухтермінальние з'єднання (ДС). У найпростішому випадку розбиття на ДС здійснюється при послідовному перегляді стовпців сітки зліва направо, починаючи з крайнього лівого стовпця. На рис.1 ланцюг 1 підходить до терміналів (11,12,13), ланцюг 2 до (21,22,23), ланцюг 3 до (31,32,33), ланцюг 4 до (41,42), ланцюг 5 до (51,52). На рис.1 ланцюг 1 розбивається на ДС11 = (11,12) і ДС12 = (11,13), ланцюг 2 на ДС21 = (21,22) і ДС22 = (22,23), ланцюг 3 на ДС31 = (31 , 32) та ДС32 = (32,33).
Кожне ДС реалізується у вигляді зв'язного набору горизонтальних і вертикальних фрагментів, що зв'язують відповідні два термінали. У загальному випадку розбиття ланцюга на ДС здійснюється наступним чином. На безлічі терміналів, що пов'язуються одним ланцюгом, алгоритмом Прима будується мінімальне зв'язує дерево. Кожне ребро цього дерева визначає ДС.
Позначимо через S = {si | i = 1,2 ,..., n} безліч всіх ДС. Нехай в області трасування реалізований з дотриманням всіх обмежень безліч ДС S1, S1ÌS, і нехай S2 безліч ДС, які не можуть бути реалізовані без порушень в ОП, заповненої S1, S2ÌS, S1ÈS2 = S. Позначимо через d - потужність S2, тобто d = ½ S2 ½.
В якості оцінки якості трасування буде використовуватися критерій:
Мета оптимізації - максимізація F збігається з мінімізацією d, де d число нереалізованих ДС.
У разі повної реалізації ланцюгів, тобто при d = 0 (або F = 1), оцінкою якості служить критерій:
де li сумарна довжина реалізованої (протрасовано) ланцюга ni і L - сумарна довжина всіх ланцюгів.
2. Генетичний алгоритм трасування у комутаційному блоці
Особливістю генетичного алгоритму, що моделює процес природної еволюції, є те, що оперування проводиться з кодами рішень. Кожному рішенням відповідає одна або кілька хромосом. Хромосоми складаються з генів. Гени можуть мати різні значення. Генетичні алгоритми працюють з популяцією рішень. Рішення виходять на основі декодування хромосом. Розробка генетичного алгоритму включає етапи розробки структури хромосом і принципів їх кодування і декодування, генетичних операторів, методики формування вихідної популяції і її селекції, загальної структури генетичного пошуку.
2.1. Структура хромосом, їх кодування та декодування
Побудуємо безліч горизонтальних ділянок
iÎ
, Що є проекціями всіх двухтермінальних сполук
iÎ
, Тобто кожному
i відповідає
i. На рис.2 і 2б наведено безлічі
для от1 і от2.
Позначимо через O (li) і O (ri) координати по горизонталі лівого і правого кінця ділянки i.
Розіб'ємо безліч , На підмножини
k, у відповідності з наступними правилами:
1. , "(Ij) [
i Ç
j = 0]
2. У межах кожного k всі ділянки накладаються один на одного, тобто
"(Ij ½ i Î
k &
j Î
k) [(O (lj) £ O (li) £ O (rj)) Ú ((O (lj) £ O (ri) £ O (rj))].
Підмножина k пронумеровані і сформовані так, що всі ліві кінці ділянок
k розташовані лівіше лівих решт ділянок
k +1, тобто "(Ij ½
i Î
k &
j Î
k +1) [(O (li) <O (lj))].
Лінійний алгоритм розбиття представлений у роботі [7]. Разбиению
відповідає розбиття S.
Для ділянок, представлених на рис.2, розбиття S має вигляд:
S1 = {21,31,11}, S2 = {32,4,12,22,5};
Для ділянок, представлених на рис.2б, розбиття S має вигляд:
S1 = {11,21,4,31}, S2 = {22,32}, S3 = {12,5}.
Для от1, представленої на малюнку 1а, m = 5, для от2, представленої на рис.1б, m = 6, де m - кількість горизонтальних ліній на ВІД.
Формуємо на основі кожного Sk вектор Vk шляхом додавання в Sk нульових елементів, так, щоб потужність Vk дорівнювала m, і фіксуємо взаємне розташування елементів.
Для от1: V1 =; V2 =.
Для от2: V1 =; V2 =; V3 =.
Отриманий після доповнення набір векторів V = {Vi} будемо називати рішенням задачі трасування комутаційного блоку.
Уявімо рішення у вигляді хромосоми. Хромосома Hm є упорядкованою сукупністю генів . Ген
є одним з варіантів вектора Vi, тобто значенням
є деякий вектор
. Гени
і
хромосом Hm і Hl гомологічних, вони однакові по складу елементів, відповідають одному й тому ж підмножині Si двухтермінальних сполук, але відрізняються порядком розташування елементів.
Декодування хромосоми здійснюється за допомогою процедури декодування, що використовує ідеї алгоритму «лівого кінця» при канальної трасування. Як і при канальної трасуванні будемо називати горизонтальні лінії опорної сітки ВІД магістралями, пронумерованими зверху вниз.
Процедура декодування полягає в послідовному заповненні магістралей, починаючи з першої, фрагментами двухтермінальних сполук.
Порядок у якому ДС вибирають для заповнення магістралей задається відповідної хромосомою і фактично визначається порядком розташування елементів у генах.
Заповнення магістралей двухтермінальнимі сполуками базується на трьох основних процедурах: укладання, трансформації, резервації.
У процесі укладання ДС у яку заповнюють магістраль воно може бути укладено або повністю, або частково, або не вкладатися взагалі.
При повній укладанні в яку заповнюють магістраль повністю містяться всі горизонтальні складові ДС і здійснюється підведення до них усіх вертикальних складових. Для цього необхідно, щоб були вільні з одного боку відповідну ділянку горизонтальної магістралі, а з іншого боку вертикальні стовпчики, за якими здійснюється прокладання вертикальних складових.
Вертикальний стовпець вважається зайнятим (зарезервованим) для будь-ланцюга ni не рівної nf якщо в ньому розташований вище заповнюваної магістралі термінал, позначений ланцюгом nf і ще не пов'язаний. Якщо термінал, розташований вище n-ої магістралі, зв'язується по вертикалі з горизонтальним ділянкою, розташованою на n-ій магістралі, то стовпець починаючи з магістралі n +1, вважається вільним. Спочатку всі стовпці, що підходять до поміченим ланцюгами терміналам, розташованим на верхній стороні ВІД, вважаються зайнятими (зарезервованими). Наприклад на рис.3 повністю розміщені ДС1, ДС2 ДС3. На ріс.3б частково розміщені ДС1, ДС2, ДС4. При частковій укладанні вводиться точка розриву ДС. Частково укладене ДС пов'язує точку розриву з одним з терміналів вихідного ДС.
Точка розриву вводиться таким чином, щоб у горизонтальній складовою була максимально можлива довжина.
Після часткового розміщення ДС проводиться його трансформація, яка полягає в тому, що термінал, пов'язаний з частково розміщеним ДС переноситься в точку розриву. Надалі ДС розглядається як ДС, що зв'язує ще не зв'язний термінал з терміналом у точці розриву.
Можливо введення двох точок розриву ДС. При цьому два фрагменти ДС, що зв'язують кожен точку розриву з терміналом вихідного ДС, будуть укладені, а третій фрагмент, що зв'язує дві точки розриву, буде укладатися в наступних магістралях. Таким чином вихідне ДС трансформується в ДС, що зв'язує дві точки розриву. Відзначимо, що ДС може в процесі укладання піддаватися кільком послідовним трансформаціям. На ріс.3б надалі ДС1, ДС2, ДС4 будуть розглядатися, як ДС зв'язують пари незв'язних терміналів, позначених відповідно (11,1 ¢ 2), (21,2 ¢ 2), (4 ¢ 1,4 ¢ 2).
Кожного разу після переходу до нової магістралі реалізується процедура резервації мета якої виключення можливості блокування терміналів, що лежать по краях магістралі. Якщо термінали лівої і правої сторін комутаційного блоку, що лежать на обраній магістралі позначені ланцюгами, то від них по магістралі проводяться горизонтальні фрагменти. Від лівого терміналу вправо, від правого терміналу вліво. Частковий поширюється до найближчого вільного стовпця.
На рис.4а проведені горизонтальні фрагменти від терміналів 11 до 1 ¢ 1 та від 21 до 2 ¢ 2. Надалі ДС1 і ДС2 трансформуються, тобто вони будуть інцидентних терміналам 1 ¢ 1 і 2 ¢ 2 відповідно. Перед резервацією аналізується стан стовпців і якщо необхідно і існує можливість формується найближчий до терміналу вільний стовпець.
Якщо є декілька стовпців, зайнятих терміналами одного ланцюга і ці термінали вже пов'язані, то їх можна об'єднати в один термінал, що призводить до звільнення стовпців. Наприклад на ріс.4в при резервації терміналу 23 два стовпці зайняті терміналами 1 ¢ 2 і 12. 1 ¢ 2 входить в ДС (1 ¢ 1, 1 ¢ 2), 12 входить в ДС (12, 13), але вони пов'язані і їх можна об'єднати в один термінал1 ¢ 2, при цьому ДС (12,13) трансформується в ДС (1 ¢ 2, 13). Це призводить до звільнення стовпця в який можна помістити термінал 2 ¢ 3, пов'язаний горизонтальним фрагментом з резервуються терміналом 23.
Уявімо хромосому Hk вигляді матриці Vk, де кожен стовпець відповідає гену. Магістралі заповнюються послідовно, починаючи з першої. Заповнення магістралей здійснюється наступним чином. Спочатку здійснюється резервація терміналів лівої і правої сторін ВІД, що лежать на магістралі. Потім послідовно по рядках, починаючи з першої у межах рядка зліва направо проглядаються елементи матриці Vk. Для кожного обраного елемента матриці (ДС) визначається можливість його розміщення в формованої магістралі. Якщо можливо, то ДС повністю або частково поміщається в формовану магістраль. Якщо ДС повністю поміщається, то воно видаляється з матриці Vk. Якщо ДС поміщається частково, то трансформується і залишається в матриці. Після закінчення перегляду матриці Vk здійснюється стиснення всіх стовпців, з яких віддалялися ДС, знизу вгору. Після цього здійснюється перехід до заповнення наступної магістралі. Процес декодування і заповнення магістралей показаний на рис.5 і 6 для ВІД представлених відповідно на рис.1а і 1б. Відзначимо, що це фактично одна й та ж завдання трасування.
Розглянемо спочатку процес укладання в от1, показаний на рис.1а. На рис.5 показано два етапи заповнення першої магістралі: резервація і укладання. Спочатку здійснюється резервація терміналу 33, лежачого на 1-й магістралі. Для цього від терміналу 33 проводиться горизонтальний фрагмент до найближчого вільного стовпця. Термінал 33 резервується терміналом 3 ¢ 3, а ДС32 = (32,33) трансформується в ДС32 ¢ = (32,3 ¢ 3). Потім проводиться укладання ДС в першу магістраль. Проглядається матриця Vk і першим вибирається ДС31 = (31,32). ДС31 укладається частково, при цьому трансформуючись у ДС31 ¢ = (31,3 ¢ 2). Наступним з Vk вибирається ДС32 ¢, яке повністю поміщається в першу магістраль і видаляється з Vk. Процес заповнення завершується і Vk стискається. На ріс.5б заповнюється другу магістраль. Спочатку резервуються термінали 21 і 42, ДС21 = (21,22) і ДС4 = (41,42) трансформуються в ДС21 ¢ = (2 ¢ 1,22) і ДС4 ¢ = (41,4 ¢ 2).
Потім проглядається матриця Vk. ДС31 ¢ не поміщається, ДС4 ¢ поміщається повністю і видаляється з Vk, яке потім стискається. На ріс.5в, г, д, показаний процес укладання 3, 4, і 5-й магістралей.
При заповненні третього магістралі (ріс.5в) в результаті трансформації утворюються ДС31 ¢ ¢ = (3 ¢ 1,3 ¢ 2), ДС11 ¢ = (11,1 ¢ 2), ДС12 ¢ = (1 ¢ ¢ 2,1 ¢ 3). Повністю поміщається ДС31 ¢, частково ДС12 і ДС11.
При заповненні 4-й магістралі (ріс.5г) при трансформації утворюється ДС12 ¢ ¢ = (1 ¢ ¢ 2,1 ¢ 3). Повністю поміщаються ДС12 ¢, ДС22, ДС21 ¢.
При заповненні 5-й магістралі (ріс.5д) повністю поміщаються ДС11 ¢, ДС5.
Розглянемо процес заповнення от2, представленої на малюнку 1б.
На рис.6а заповнюється перша магістраль. Спочатку резервується термінал 51 лежачий на 1-й магістралі. ДС5 = (51,52) трансформується в ДС5 ¢ = (5 ¢ 1,52). Потім при перегляді Vk вибирається ДС11 яке частково вкладається в 1-у магістраль і трансформується в ДС11 ¢ = (11,1 ¢ 2).
При заповненні 2-й магістралі (ріс.6б) спочатку резервується термінал 11 за це ДС11 ¢ трансформується в ДС11 ¢ ¢ = (1 ¢ 1,1 ¢ 2). Для резервації терміналу 23 формується вільний стовпець. Для цього термінали 1 ¢ 2 Î ДС11 ¢ ¢ і 12 Î ДС12, оскільки вони вже пов'язані, об'єднуються в термінал 1 ¢ 2, а стовпець, зайнятий терміналом 12, звільняється. ДС12 = (12,13) трансформується в ДС12 ¢ = (1 ¢ 2,13). Після цього термінал 23 резервується терміналом 2 ¢ 3, а ДС22 = (22,23) трансформується в ДС22 ¢ = (22,2 ¢ 3). При перегляді Vk повністю в 2-у магістраль поміщається тільки ДС11 ¢ ¢, яке видаляється з Vk.
При заповненні третього магістралі (ріс.6в) резервуються термінали 21 і 52. Трансформуються: ДС21 = (21,22) у ДС21 ¢ = (2 ¢ 1,22), ДС5 ¢ = (5 ¢ 1,52) в ДС5 ¢ ¢ = (5 ¢ 1,5 ¢ 2). Повністю поміщається тільки ДС5 ¢ ¢, яке видаляється з Vk.
При заповненні 4-й магістралі (ріс.6г) резервується термінал 41. ДС4 = (41,42) трансформується в ДС4 ¢ = (4 ¢ 1,42). При перегляді Vk частково
поміщається ДС12 ¢ і повністю ДС4 ¢. ДС12 ¢ трансформується в ДС12 ¢ ¢ = (1 ¢ ¢ 2,13), а ДС4 ¢ видаляється з Vk.
При заповненні 5-й магістралі (ріс.6д) резервуються термінали 31.і 13. ДС31 = (31,32) трансформується в ДС31 ¢ = (3 ¢ 1,32), а ДС12 ¢ ¢ = (1 ¢ ¢ 2,13) в ДС12 ¢¢¢=( 1 ¢ ¢ 2,1 ¢ 3). При перегляді Vk повністю поміщаються ДС21 ¢, ДС22 ¢, ДС31 ¢, ДС12 ¢ ¢, які видаляються з Vk.
При заповненні 6-й магістралі (рис.6) повністю міститься ДС32.
При заданих способах кодування от1 і от2, при декодуванні хромосом Hk, відповідних от1 і от2 і представляються у вигляді вищенаведених матриць Vk, кінцеві результати збіглися, хоча це і не є обов'язковим.
Матриця Vk проглядається при заповненні кожній магістралі. Розмір матриці Vk пропорційний числу as містяться в ній ДС.
as = ak-an, де ak - число терміналів, розташованих на кордонах ВІД, і an - число ланцюгів. Звідси оцінка трудомісткості процедури декодування пропорційна O (m * as).
Генетичні оператори
Загальна структура генетичного пошуку представлена на рис.7.
Попередньо здійснюється формування структури хромосоми. Ця процедура включає розбиття кожного ланцюга на ДСj, розбиття множини ДС на підмножини, визначення числа і розміру генів у складі хромосоми: визначення складу кожного гена (тобто визначення ДС, що входять в кожен ген). Далі, випадковим чином генерується вихідна популяція Пі хромосом розміром М. Суть випадкового формування в тому, що для кожного гена кожної хромосоми випадковим чином встановлюється порядок розташування в ньому елементів (ДС). Для кожної хромосоми розраховується фітнес. Розрахунок фітнесу здійснюється на основі декодування хромосоми, тобто фактично рішення задачі трасування.
Метою генетичного пошуку є знаходження такої хромосоми і з таким розташуванням елементів у генах, які забезпечують при декодуванні оптимальне значення фітнесу.
Основними генетичними операторами є кросинговер та мутація. У нашому випадку операція кросинговер реалізується шляхом імовірнісного вибору батьківської пари хромосом і формування на її основі нащадків шляхом взаємооднозначної обміну гомологічними генами. У загальному випадку хромосоми можуть обмінюватися групами гомологічних генів. Оператор кросинговеру для вибраної пари виконується наступним чином.
Задається ймовірність кросинговеру Pk. Потім послідовно проглядаються пари гомологічних генів (генів, розташованих в одному і тому ж локусі хромосом), які із заданою вірогідністю Pk міняються місцями. При виборі пари хромосом для кросинговеру використовується ² принцип рулетки ², при якому ймовірність P (Hi) Вибору хромосоми Hi визначається як:
,
де Fi - фітнес хромосоми Hi.
Число пар хромосом W є керуючим параметром процедури генетичного пошуку.
В результаті виконання операції кросинговеру формується додаткова популяція Пк, яка об'єднується з Пі і надалі піддається мутації. Для кожної хромосоми популяції Пк розраховується фітнес. Операція мутації полягає у виборі гена, який піддається мутації і мутації цього гена. Мутація гена полягає у випадковому виборі пари елементів, що входять до складу гена, і обміні місцями їх розташування в гені.
Реалізація операції мутації здійснюється наступним чином. Задається ймовірність мутації PM, послідовно проглядаються всі хромосоми з популяції Пі + Пк, а в хромосомі всі гени, і із заданою вірогідністю PM ген мутує. Мутація полягає у випадковому виборі в гені пари елементів, які потім обмінюються місцями. Виконання оператора мутації призводить до формування додаткової популяції ПМ, для кожної хромосоми якої розраховується фітнес.
Заключною операцією в межах одного покоління є селекція розширеної популяції Пт = Пі + Пк + ПМ. У результаті селекції на основі ² принципу рулетки ² відбирається нова популяція Пі кращих рішень, яка є вихідною для наступної генерації. Число генерацій (поколінь) Т, розмір популяції М і параметри Рк і РМ є керуючими параметрами, що впливають на ефективність процесу генетичного пошуку.
3. Експериментальні дослідження
Алгоритм був реалізований на мові С + + для ПЕОМ типу IBM PC.
Першою метою експериментальних досліджень - було знаходження найкращого поєднання значень керуючих параметрів таких, як Pм, PК, М і Т, де М - обсяг популяції.
Дослідження проводилися так. Для кожного прикладу спочатку фіксувалося значення РМ і змінювалися параметри PК і М. Потім фіксувалося значення PК і змінювалися Pм і М. Для кожного набору значень Pм, PК, і М проводилася серія з 10 експериментів в результаті якої визначалося середнє, максимальне і мінімальне значення Т , при якому не спостерігалося поліпшення кращого рішення. Було встановлено, що при значенні PК = 0,4 і Pм = 0,1, М = 50 і Т = 130 забезпечується знаходження оптимального рішення.
Дослідження трудомісткості алгоритму показали, що при фіксованих значеннях Pм, PК, М і Т вона має лінійну залежність і пропорційна O (N), де N - число пов'язують контактів.
Висновок
У статті був представлений генетичний алгоритм трасування у комутаційному блоці. При розробці структури і методів кодування і декодування хромосом, генетичних операторів використовувалися специфічні знання про проблему. Дослідження показали досить високу ефективність розробки генетичних процедур.
Джерелом вдосконалення може стати правильна настройка параметрів управління. Інша можливість полягає в тому, щоб при частковій укладанні вводити більше двох точок розриву, що призведе до трансформації укладається ДС у кілька ДС.
Поняття верхньої та нижньої сторін ВІД відносно, оскільки ВІД можна розвернути на 180 ° і верхня сторона стане нижньої, а нижня верхньою. У зв'язку з цим можливо використовувати прийом, що полягає в чергуванні порядку заповнення магістралей: перша зверху, перша знизу, друга зверху, друга знизу і т.д. При заповненні n-ої зверху магістралі послідовно проглядаються рядки матриці Vk, починаючи з першої, а при заповненні n-й знизу магістралі рядки матриці Vk проглядаються у зворотному порядку, починаючи з останньої.
Засобом підвищення збіжності генетичного алгоритму може стати подання рішення у вигляді двох хромосом H1k і H2k. При цьому ВІД представляється, як і було показано вище, у вигляді двох от1 і от2 одночасно. Структура H1k відповідає от1, а структура H2k відповідає от2. Заповнення магістралей проводиться послідовно і поперемінно то в от1, то в от2. При трансформації деякого ДС у от1 здійснюється відповідна трансформація в от2, і навпаки.
Подання одного рішення у вигляді двох хромосом, дає можливість використовувати генетичний оператор комбінування набором хромосом в одному рішенні. При цьому пара батьківських рішень дає чотири нащадка.
Відзначимо, що запропонований підхід цілком застосовний для «безсеточной» трасування з'єднань різної ширини. Для цього на основі конструктивних параметрів (ширина ланцюга, відстань між ланцюгами і вікнами, розміри перехідних контактів) розраховуються допустимі відстані між фрагментами. У цьому випадку завдання трасування зводиться не до розподілу фрагментів по магістралях, а до упаковки фрагментів. Модернізована процедура декодування буде послідовно розміщувати ДС «притискаючи» їх на допустиму величину до раніше розміщеним. В якості базису вибирається верхня сторона ВІД. Результатом роботи будуть фізичні координати розміщених фрагментів.
Шляхом модифікації процедур укладання, трансформації та резервації можна використовувати вище наведену методику для трасування з числом шарів більше двох.
Список літератури
WKLuk. A greedy switch box router INTEGRATION, the VLCI Journal, 3: pp. 129-149, 1985.
H. Shin and A. Sangiovanni Vincentelli. Mighty: a rip-up and reroute detailed router. Proceedings of IEEE International conference on Computer-Aided Design, pages 2-5, November 1986.
JPCohoon and PLHeek. Beaver: A computational geometry based tool for switch box routing. IEEE Transactions on Computer-Aided Design, 7:684-697, June, 1988.
M.Marek-Sadowska. Switch box routing: a retrospective. INTEGRATION, the VLCI Journal, 13, pp. 36-65 1992.
YL Lyn, YC Hsu, and Tsai. Silk: A simulated evolution router. IEEE Transactions on Computer-Aided Design, 8:1108-1114, October, 1989.
T. Cho, S. Pyo, and J. Heath. Parallex: A parallel approach to switch box routing. IEEE Transactions on CAD of Integrated Circuits and Systems, 13:684-693, June 1994.
Лебедєв Б.К. Канальна трасування на основі генетичних процедур. Інтелектуальні САПР. Таганрог: ТРТУ, 1997, N3 (6) с. 53-60.