Область наук:

  • Математика

  • Рік видавництва: 1996


    Журнал: Известия Південного федерального університету. Технічні науки


    Наукова стаття на тему 'Алгоритм задачі канальної трасування, заснований на методі генетичного пошуку'

    Текст наукової роботи на тему «Алгоритм задачі канальної трасування, заснований на методі генетичного пошуку»

    ?2. Burkard R.E., Karisch S., Rendel F. QAPLIB A Quadratic Assignment Problem Library, EJOR 55, 1991, pp. 115-119. Goldberg D.E., Lingl J.R. "Alleles, Loci and the Traveling Salesman

    3. Problem, Proceedings of the International Conference on Genetic Algorithms and their Applications, Hillsdale NJ, 1985, pp. 154-159. Heragu S.S .. Facility Layout (Special Issue), EJOR 57 (2), 1991, pp.

    4. Kureichik V.M., Melikhov A.N .. Miagkikh V V. Some New Feati ^ es in Genetic Solution of the Traveling Salesman Problem, to appear in Proc. of the IC on Adaptive Computing in Eng. Design and Control'96, Plymouth UK, March тисяча дев'ятсот дев'яносто шість.

    5. Nissen V., Paul H. A Modification of Threshold Accepting and its Application to the Quadratic Assignment Problem.OR Spektrum (1995) 17, 205-210.

    6. Nissen V. Evolutionary Facility Layout - A Comparison, submitted to Studies in Locational Analysis. Heuristics in Location (Special Issue).

    7. Skorin-Kapov J. Tabu Search Applied to the Quadratic Assignment Problem, ORSA Jomal on Computing, v.2, 1990, pp. 33-45.

    УДК 681.356

    Давиденко В.Н.

    АЛГОРИТМ Завдання канального трасування, БАЗОВАНИЙ НА МЕТОД ГЕНЕТИЧНОГО ПОШУКУ

    ВСТУП

    Трасування - це заключний етап конструкторського проектування інтегральних схем (ІС). Осйовная завдання трасування полягає у визначенні ліній, що з'єднують Еквіпотенціальна контакти елементів і компонентів ІС. У даній роботі ми пропонуємо генетичний алгоритм для задачі канальної трасування в класичній постановці.

    Завдання канального трасування В КЛАСИЧНОЇ ПОСТАНОВЦІ

    I

    Завдання канальної трасування в класичній постановці - це простий метод трасування двостороннього каналу, по верхній і нижній сторонах якого проходять лінійки контактів. Злами, тобто перехід горизонтальної ділянки з однієї магістралі на іншу, не допускаються. Трасування ведеться в двох шарах: у одному проводяться горизонтальні сегменти, в іншому - вертикальні. З'єднання горизонтальних і вертикальних відрізків здійснюються через перехідні отвори.

    Канал описується двома послідовностями Тор і Bottom, в яких розміщені верхня і нижня лінійки каналу [6]. Розмір обох послідовностей дорівнює С, - числу колонок в каналі. Безліч ланцюгів визначається як Net = {Nj, .... Nn}, де n - число ланцюгів.

    При канальної трасування не допускаються накладення вертикальних і горизонтальних сегментів ланцюгів. Для вирішення цього завдання вводяться графи вертикальних і горизонтальних обмежень. вертикальні обмеження

    Матеріали Всеросійської конференції "Інтелектуальні САПР-95"

    -------------------,------------------------------------------------

    описуються орієнтованим графом вертикальних обмежень (ГВО) GV = (ENel, EV), де Not безліч вершин, відповідних безлічі ланцюгів NPt, EV безліч спрямованих ребер. Ребро (п, ш)

    належить ребру EV, існує тоді і тільки тоді, коли ланцюг п розташована вище ланцюга m для запобігання накладень вертикальних сегментів ланцюгів.

    Для того, щоб завдання вирішувалася в рамках класичної постановки граф GV повинен бути ациклічним, в іншому випадку це може стати вирішеною тільки з введенням зламів, а це суперечить умовам класичної постановки задачі канальної трасування.

    У нашій роботі ми будемо використовувати розширений граф вертикальних обмежень (РГВО) GRV = (EN0t, ERV), де Nel-безліч вершин, відповідних безлічі ланцюгів Net, ERV-безліч спрямованих ребер. Ребро (n, m) належить ERV, існує тоді і тільки тоді, коли в ГВО існує шлях з вершини п в вершину т.

    Горизонтальні обмеження представлені неорієнтованим графом горизонтальних обмежень (ГТО) GH = (ENe (, EH), де ENet-безліч ланцюгів, ЄП безліч ребер Ребро (п, ш) належить ЄП існує тоді і тільки тоді, коли магістралі для піт повинні бути різними Для виключення накладення горизонтальних сегментон піт.

    ГЕНЕТИЧНИЙ АЛГОРИТМ ДЛЯ канальний ТРАССІЮВКІ

    Генетичний алгоритм 'вимагає щоб хромосоми оцінювалися з точки зору цільової функції завдання. Цільова функція оцінює будь-які якості особи (довжину ланцюгів, число магістралей і т.д.). Як було зазначено вище, генетичний алгоритм обробляє популяцію рішень закодованих в хромосоми. В процесі обробки популяції, до неї послідовно застосовуються різні генетичні оператори, такі як до зростав інговер і "точкова" мутація, з заданими ймовірностями (РС і РМ відповідно). Потім проводиться селекція збільшилася популяції Для відбору кращих рішень, які складуть наступне покоління, після чого цикл повторюється. Число таких циклів називається числом поколінь Т

    Для нашого генетичного алгоритму, ми прийняли наступну схему:

    Крок 1. Визначення розміру популяції М, числа поколінь Т, ймовірності кросинговеру РС і ймовірності мутації РМ.

    Крок 2. Завдання випадковим чином початкової популяції П (0) розміром

    М.

    Крок 3. 1 = 0.

    Крок 4. Вибір випадковим чином М пар хромосом з популяції П (1) і застосування операції кросинговеру до кожної пари із заданою вірогідністю РС.

    Крок 5. Застосування операції мутації до кожної особини популяції

    П (1) із заданою вірогідністю РМ.

    Крок 6. Селекція. Відбір М особин з найкращим значенням цільової Функції з отриманої популяції П (Ц в нову популяцію П (1 + 1).

    Крок 7 1 = 1 + 1.

    Крок 8. Якщо КТ, то перехід до кроку 4.

    Крок 9. Висновок особини з найкращим значенням цільової функції. Далі в статті ми розглянемо генетичні операції застосовуються в нашому дієтичному алгоритмі.

    Беручи до уваги характеристика завдання канальної трасування, ми визначаємо цільову функцію як:

    І (А) = (изе<1Тгаск (А) + 2) * З + То1а! Уег15 * д (А »,

    де С - число контактів, функція 1>аіГГгаск (Л) повертає число магістралей займаних каналом отриманому при відновленні з хромосоми А, а функція То1а1Уе115ед (А) повертає довжину вертикальних сегментів ланцюгів в отриманому рішенні. Довжина вертикальних сегментів ланцюга визначається як відстань між контактами і перехідними отворами, які з'єднують вертикальні і горизонтальні сегменти. Після процесу селекції, всі хромосоми розбиваються на пари, і потім застосовується операція кросинговеру з ймовірністю РС до кожної пари хромосом.

    Мутація довільно змінює один ген обраної хромосоми, за допомогою випадкової зміни з імовірністю РМ, рівній нормі мутації. Сенс оператора мутації - це введення додаткових змін в популяцію.

    ЕКСПЕРИМЕНТАЛЬНІ РЕЗУЛЬТАТИ

    Для ілюстрації обгрунтованості нашого підходу для вирішення завдання канальної трасування, описаного в попередніх розділах, алгоритм реалізували на мові Сі для 1ВМ РС. Установки керуючих параметрів були знайдені емпірично. Розмір популяції М був обраний рівним 50. Ми встановили значення ймовірності кросинговеру РС рівним 1. Була обрана щодо висбкая ймовірність мутації РМ 0.1, так як мутація в нашому випадку вносить дуже невеликі зміни в хромосому. Була застосована "елітна" селекція, тобто з популяції отриманої після проведення операцій кросинговеру і мутації вибирається М особин з найменшим значення цільової функції. На стандартному потоці завдань алгоритм показав високу якість отриманих рішень. Протягом перших п'яти поколінь у всіх випадках було отримано рішення з мінімально можливим числом зайнятих магістралей. А після двадцяти поколінь відхилення від оптимального результату по довжині з'єднань склало менше 1%. Тимчасова складність відновлення ескізу каналу з хромосоми становить <Е (И2).

    Таблиця

    Ио Число Число Мінімальна Відхилення від

    тесту контактів ланцюгів довжина ланцюгів оптимуму,%

    0 80 51 8 0.001%

    1 80 36 9 0.0005%

    2 80 37 10 0%

    3 80 37 10 0%

    4 {00 66 10 0.92%

    Таким чином, загальна тимчасова складність алгоритму становить Т * (М * РС * 2) * РМ'0 (И2), де М - розмір популяції, а Т - число поколінь. У таблиці наведено оптимальні результати для обраних прикладів, і середнє відхилення від оптимального результату, отримане в результаті проведення 10 випробувань для кожного прикладу з різними початковими

    Матеріали Всеросійської конференції "Інтелектуальні САПР-95"

    установками генератора випадкових чисел. Випробування проводилися при М = 50, Т = 20, РС = 1.00 і РМ = 0.10.

    ВИСНОВОК

    У цій статті ми досліджували застосування нашого генетичного алгоритму до задачі канальної трасування в класичній постановці. Результати експериментів показали що даний алгоритм дозволяє отримувати рішення близькі до оптимальні ^ * за досить короткий час. Розроблений метод кодувань хромосом також завершився перемогою. Хоча результати отримані хороші, можна поліпшити роботу алгоритму за рахунок застосування сортування генів в хромосомі. Іншим джерелом удосконалень є використання більш складної функції оцінки, яка буде працювати краще, ніж та, яку ми використовували в цій статті. Застосування операції мутації вносить більше змін в хромосому, також може привести до поліпшення.

    ЛІТЕРАТУРА

    1. Yoshimura, T and Kuh, E S. "Efficient, algorithms for channel routing, IEEE Trans. Comput. - Aided Des. Integrated Circuits & Syst., Vol.I, no.l, PP-25 -35,1982.

    2. Burstein, M. "Channel routing" Layout Design and Verification, pp. 133 - 167, Elsevier Science, 1986.

    3. Michalewicz, Z., Genetic Algorithms 4 Data Structures Evolution Programs, Springer - Verlag, 1992

    4. Liu, X. Sakamoto, A., Shimamoto, T. "Restructive Channel Routing with Evolution Programs", Trans. IEICE. vol.E76 -A, no.10, pp.1738-1745, 1993.

    5 Goldberg, D.E. "Genetic Algorithm in Search, Optimization & Machine Learning "Addison - Westley, 1989.

    ИК 658.512.2

    В.НЛуценко

    ГЕНЕТИЧНИЙ АЛГОРИТМ ДЛЯ ВИРІШЕННЯ ТРАНСПОРТНОЇ

    ЗАВДАННЯ

    Існує великий клас практично цікавих завдань, що включає багато завдань оптимізації, які не можуть бути вирішені за прийнятний час. Однак у багатьох додатках допустимі рішення, близькі до оптимальних, за умови що вони отримані досить швидко.

    Генетичні алгоритми (ГА) .позволяющіе отримувати такі рішення, особливий клас алгоритмів, що поєднують в собі позитивні якості випадкових градієнтних методов.ГА починають свою роботу з популяції якимось чином сформованих рішень, а потім покращують їх використовуючи генетичні оператори (ГО), моделюючи тим самим в більшій чи меншій мірі -'волюціоннний процес в природі [2]. Структуру простого ГА можна спчсать бедующім чином [1]


    Завантажити оригінал статті:

    Завантажити