Область наук:
  • Математика
  • Рік видавництва: 2001
    Журнал: Известия Південного федерального університету. Технічні науки
    Наукова стаття на тему 'Адаптивний алгоритм рознесення з'єднань по верствам'

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

    ?розділ 2

    Генетичні і еволюційні алгоритми

    УДК 681.3.001.63

    Б.К. Лебедев1

    АДАПТИВНИЙ АЛГОРИТМ рознесених СОЕДИНЕНИЙ ПО ВЕРСТВАМ

    1. Введення. При двошарової трасування НВІС зазвичай реалізується наступний підхід. Спочатку одним з алгоритмів трасування розробляється суміщений ескіз трасування межсоединений, що задовольняє наступним обмеженням: не допускаються накладення ланцюгів друг на друга; відсутні точки дотику кіл; в одній точці перетинаються не більше двох ланцюгів [1].

    Виключити точки перетину кіл, тобто забезпечити правильне функціонує-,

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

    мінімально необхідного числа МП, що забезпечують рознесення з'єднань по .

    Існує два основних способи вирішення поставленого завдання [2,3]. При першому способі на ескізі трасування відшукуються розташування мінімально необхідного числа вузлів, в яких розміщуються міжшарові переходи, що забезпечують розміщення суміщеного ескізу трасування. Відзначимо, що визначення конфігурації ділянок і їх рознесення по верствам здійснюється після введення міжшарових переходів. 1 Робота виконана за підтримки РФФД, грант №99-01-00050

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

    Робота виконана за підтримки РФФД, грант №99-01-00050

    Отже, при другому способі спочатку ділянки розносяться по верствам, а потім в деяких вузлах вводяться необхідні МП, щоб забезпечити ця рознесення.

    Завдання рознесення на основі другого способу можна звести до задачі псевдо-булевого програмування [4]. Однак використання класичних методів дослідження операцій неприйнятно зважаючи на велику розмірності задачі.

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

    принципами адаптації на основі самонавчання і самоорганізації..

    2. .

    ескіз трасування Т, що відповідає перерахованим вище обмеженням. За методикою, наведеною в роботі [5], на ескізі визначається місце розташування вузлів, в яких можуть розташовуватися МП, що забезпечують рознесення з'єднань по сло-.

    Введені вузли природним чином розбивають ланцюга на фрагменти. будемо ,

    конфлікту один з одним. На рис.1 показано розбиття з мінімізованих чис, - ().

    | сл

    15 9 б 17 7

    5 п1 10 11

    1 8 *

    4 • 1 + 1 ^ 14 '' 2 18 3

    »4 > • 4

    рис.1

    Нехай є ескіз трасування Т, який розбитий на безліч фрагментів / 1 Фрагменти? і? перебувають у відношенні конфлікту,

    якщо перетинаються один з одним. Побудуємо граф перетинів Я = (Х, і), X = {11 = 1,2, ... П}, і = {| / = 1,2, ... П}, де х1 відповідає фрагменту ?,

    а дві вершини х (і х ^ пов'язані ребром ик, якщо відповідні їм фрагменти? і? перебувають у відношенні конфлікту, тобто перетинаються один з одним. Отриманий граф Я = (Х, і) складається з деякого безлічі а незв'язних між собою подгрев-- .

    однозначно відповідає деякий безліч фрагментів Е, се, яке назвемо конфліктно зв'язковий групою (КСГ).

    Безліч фрагментів Е = {11 = 1,2, ... п}. розбивається на конфліктно зв'язкові групи (КСГ). Для кожної КСГ Е існує тільки дві альтернативи Л і А2 рознесення по верствам. Для ескізу трасування Т (рис.1) утворюються такі КСГ:

    Е1 = {1,4,5,9,13,15}; Е2 = {6,12,16}; Е3 = {2,14}; Е4 = {3,18};

    Е5 = {8,11}; Е6 = {7,10,17};

    (Щ (У№пе = 0, иЕ = Е.

    2

    На рис.2 представлені альтернативи рознесення КСГ Е1. Кожне безліч Fi розпадається на два підмножини Е1 і Е2, Е1 ^ Е2 = Е1, де Е1 - безліч фрагментів, що розміщуються в одному шарі, а Е - в іншому. Для нашого прикладу Е1 = {1,4,9}; Е / = {5,13,15}; Е ^ = {6,16}; Е22 = {12}; Е / = {2}; Е32 = {14}; Е41 = {3}; Е42 = {18}; Е5 = {8}; Е ^ = {11}; Е6 = {7,10}; Еб2 = {17}.

    Будемо вважати, що альтернативі Л1 відповідає розміщення Е ^ в першому шарі, а Е2 - у другому. Альтернативі Л2 відповідає протилежне розміщення Е1 і Е2.

    Для кожної КСГ можна реалізувати будь-яку альтернативу, незалежно від обраних альтернатив для інших КСГ.

    б

    рис.2

    Очевидно, що конкретний набір альтернатив А = {А до | і = 1,2, ...; к є {1,2}} визначає конкретний варіант рознесення фрагментів по верствам і як наслідок -

    а

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

    У зв'язку з цим завдання рознесення з'єднань по верствам зводиться до пошуку такого набору альтернатив А *, при якому число міжшарових переходів Р (А *) мінімально, тобто.

    Р (Л *) ^ тт.

    3. Організація процесу генетичного пошуку при рознесенні з'єднань по верствам. Як уже указ ивалось вище, рішення задачі рознесення фрагментів ланцюгів по верствам повністю залежать від альтернатив Л = (Л, до | 1 = 1,2, ..., у; ке {1,2}}. Отже, хромосома повинна нести інформацію про альтернативи, обраних для КСГ.

    Хромосома И1, що несе інформацію про 1-м вирішенні (індивідуальності), має наступну структуру: І ^^ - |] = 1,2, ..., у}, де

    1, якщо для КСГ? Й обрана альтернатива А}; 0, якщо для КСГ Г и обрана альтернатива А 2.

    н,

    н.

    про

    1

    про

    1

    1

    про

    Отже, хромосома являє собою рядок, що складається з нулів і одиниць. Просторова складність і тимчасова складність декодування хромосоми мають оцінки 0 (у), де у-число КСГ.

    Основними генетичними операторами є кроссинговер і мутація. Кроссинговер виконується наступним чином. Нехай є дві роди-И1 И2 (.3).

    Послідовно проглядаються локуси хромосом, і з імовірністю Рк здійснюється обмін генами в поточному локусі. В результаті виходить дві хромосоми: Щи И2.

    Модифікований кроссинговер передбачає обмін гомологічними ділянками. можливі .

    ділянок I (1<у), на які розбиваються хромосоми. Параметр 1 може здаватися випадково перед виконанням кросинговеру. Потім визначається 1У від ділення у на I. Всі ділянки хромосоми (можли-

    1

    Про

    Про

    І '

    1

    про

    про

    н

    1

    1

    про

    1

    про

    про

    н.

    про

    про

    про

    1

    1

    про

    рис.3

    ні, крімс ііідсднсі і) іуду и мати одну довжину.

    При другому підході перед виконанням кросинговеру задається параметр, такий, що 1<у, і випадковим чином хромосома розбивається на I ділянок різної довжини.

    В обох підходах після розбиття пари хромосом на ділянки послідовно проглядаються пари гомологічних ділянок і з ймовірністю Рк здійснюється їх обмін.

    На рис.4 показаний кроссинговер для першого підходу, а на рис.5 - для другого.

    Н,

    н,

    н,

    0 1 1 | 0 и i | o 1 про | 1 i |

    г

    1 0 oil и 10 0 oh ° l

    про

    1 0 Про Про и 10 0 0 1 про

    0 1 "і! | 0 1» | i про |

    0 10 0 1 0 1 1 10 0 |

    ] 0 1 1 0 0 1 0 11 1 |

    про

    0 1 1 1 0 0 1 1 11 1

    ] 0 0 0 1 0 1 0 10 0

    рис.4

    рис.5

    н

    н

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

    мутує

    В результаті мутації ген набуває протилежного значення: замість нуля - одиниця, замість одиниці - нуль (рис.6).

    В роботі використовується стандартна структура генетичного пошуку, яка передбачає формування випадковим чином вихідної популяції розміром М і виконання До Ітера.

    На кожній ітерації послідовно виконуються оператори кросинговеру, мутації і

    1

    1

    Про

    1

    1

    1

    про

    про

    1

    1

    про

    1

    1

    про

    рис.6

    ж ,, ед генетичного алгоритму.

    У масиві ескіз зберігаються вихідні дані, що описують суміщений ескіз трасування. У масивах вузли і фрагменти зберігаються вихідні дані про вузли та розбитті ескізу на фрагменти. За допомогою процедури ГРАФ (ескіз, вузли, фрагменти) будується граф перетинів К = (Х, і), інформація про який заноситься в масив граф перетнути. За допомогою процедури

    Algorithm рознесених СОЕДИНЕНИЙ begin

    ескіз = ІСХОДНИЕ_ДАННИЕ; вузли = ІСХОДН_УЗЛИ; фрагменти = ІСХОДН_ФРАГМЕНТИ; генетика = НАСТРОЙКА; граф_пересеч = ГРАФ (ескіз, вузли, фрагменти); суміжність = ФРАГ_СМЕЖН (ескіз, вузли, фрагменти); групи = КОІФЛІКТ ^ в'язнів (граф ^ ересеч); нач_попул = генерітся ЦНЯ (групи); фітнес = РОЗРАХУНОК (нач_попул, групи, суміжність); К = число генерацій; while До > 0 do {

    крос ^ опул = 0;

    И = чісло_кросс; мут_попул = 0; while N > 0 do {

    рід ^ ара = ВИБІР (поч ^ опул, фітнес, генетика); доч_пара = кросинги (род_пара, генетика); крос ^ опул = ВКЛЮЧИТИ (крос ^ опул, дочко ^ ара);

    N = N-1;

    };

    фітнес = РОЗРАХУНОК (крос ^ опул, групи, суміжність); тек ^ опул = ОБ'ЄДНАТИ (поч ^ опул, крос ^ опул); мут_попул = МУТАЦІЯ (тек_попул, генетика); фітнес = РОЗРАХУНОК (.іут_попул, групи, суміжність); тек ^ опул = ОБ'ЄДНАТИ (тек ^ опул, мут_попул); лучш_ ^ еш = ВІДБІР (тек_попул, фітнес);

    К = К-1;

    нач_попул = СЕЛЕКЦІЯ (тек_попул, фітнес, генетика);

    };

    end

    рис.7

    ФРАГ_СМЕЖН (ескіз, вузли, фрагменти) для кожного вузла визначаються інцідентние йому, тобто суміжні один одному, фрагменти.

    Дані заносяться в масив суміжність. Нагадаємо, що МП відсутня, якщо суміжні фрагменти (тобто інцідентние одному вузлу) розташовані в одному шарі. Далі процедурою КОНФЛІКТ_ 'ЗВ'ЯЗКУ (графпересеч) граф перетинів R розбивається на незв'язні компоненти - конфліктно зв'язкові групи.

    Після цього процедурою ГЕНЕРАЦНЯ (г0тпи) формується початкова популяція - поч ^ опул. Для кожної індивідуальності початкової популяції процедурою РОЗРАХУНОК (нач_попул, групи, суміжність) розраховується значення фітнесу, яке заноситься в масив фітнес.

    На кожній генерації (число генерацій одно К) спочатку реалізуються оператори кросинговеру і мутації, а потім розширена популяція піддається редукції за допомогою селективного відбору, тобто зменшення до початкового об'єму.

    Оператор кроссинговера виконується N раз. Кожен раз процедурою СЕЛЕК_ПАРИ (нач_попул, фітнес) вибирається батьківська пара. Вибір родпара здійснюється одним із способів, що задаються при налаштуванні механізмів генетичного пошуку. Це може бути «принцип рулетки», вибір на основі рейтингу і т.д.

    Процедурою кросинги (род_пара, генетика) реалізується оператор кросинговеру і утворюється пара дочірніх хромосом доч_пара, яка процедурою ВКЛЮЧИТИ (кросс_попул, доч_пара) включається в масив кросс_попул. Потім процедурою ОБ'ЄДНАТИ (нач_попул, кросс_попул) масиви нач_попул і кросс_попул об'єднуються в тек_попул.

    Кожна хромосома популяції тек_попул піддається мутації за допомогою процедури МУТАЦІЯ (тек_попул) і утворюється подпопуляція мут_попул. Для кожної індивідуальності масиву мут_попул процедурою РОЗРАХУНОК (мут_попул, групи, суміжність) розраховується значення фітнесу, яке заноситься в масив фітнес. Процедура ОБ'ЄДНАТИ (тек_попул, мут_попул) об'єднує мас-_ _ _ .

    Заключним етапом в межах одного покоління є реалізація процесу «природного відбору», тобто скорочення популяції тек_попул до розмірів початкової популяції нач_попул за допомогою процедури СЕЛЕК_ПОПУЛ (тек_попул, фітнес), найчастіше використовує «принцип рулетки».

    Всі хромосоми в представлених алгоритмах є гомологічними, що виключає виникнення нелегальних рішень і спрощує виконання генетіче-,. перш за все є лінійна оцінка часової і просторової складності,, вирішувати завдання великої можливості, а це важливо при проектуванні НВІС. Тимчасові витрати в межах одного покоління складаються з витрат на декодування хромосом, витрат на оператори кросинговеру, мутації, селекції і. . -ні витрати в межах одного покоління для популяції хромосом обсягу M мають оцінку O (vM).

    4. Організація комбінованої адаптивної пошукової процедури. Матеріали статті є другою складовою частиною загального підходу до побудови адаптивної пошукової процедури для вирішення завдання рознесення з'єднань по верствам. В раніше виданої статті "Рознесення з'єднань по верствам на основі колективної адаптації" [5] процес оптимізації розглядається як адаптивний пошуковий процес на основі самонавчання і самоорганізації, що моделюється ймовірносними навчаються автоматами адаптації [6].

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

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

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

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

    якщо рішення з глобальним оптимумом лежить поза цієї околиці, то воно не бу-

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

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

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

    основі самонавчання і самоорганізації.

    У зв'язку з цим для подолання бар'єру локальних оптимумів обгрунтованим

    ,

    основі самонавчання і самоорганізації.

    Найпростішим способом поєднання генетичного і адаптивного навчається алгоритму є їх послідовна реалізація.

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

    У загальному випадку адаптивна пошукова процедура на основі самонавчання і самоорганізації включається в структуру процедури генетичного пошуку. На рис.8 наведено псевдокод комбінованої адаптивної пошукової процедури.

    Масив завдання включає всі вихідні дані. На початку процедурою ФОРМ (завдання) формується початкова популяція поч ^ опул. На кожній генерації (число генерацій одно К) спочатку процедурою ГЕНЕТИКА (поч ^ опул) реалізуються,. розширена популяція тек ^ опул. Процедурою А_СЕЛЕКЦІЯ (тек_попул) в по-_ _ -работкі адаптивним навчаються алгоритмом. Відзначимо, що в безліч ад_попул не включаються рішення, раніше отримані алгоритмом адаптивного навчання і не піддавалися подальшим змінам генетичними операторами. Далі кожне рішення безлічі ад_попул за допомогою процедури АДАПТАЦІЯ (ад_попул) піддається обробці алгоритмом адаптивного навчання і виходить оновлене безліч рішень ад_попул. Отримані рішення процедурою ОБ'ЄДНАТИ (тек_попул, ад ^ опул) включаються в популяцію тек ^ опул. На закінчення процедури СЕЛЕКЦІЯ (тек ^ опул) на базі популяції тек ^ опул здійснюється відбір і формування популяції поч ^ опул.

    Algoritm ПОШУКОВА АДАПТАЦІЯ begin

    задача = ВИХІДНІ ДАНІ нач_попул = ФОРМ (завдання):

    К = число генерацій;

    while > 0 do

    {

    _ = (_);

    _ = _ (_);

    _ = (_);

    _ = (_, _);

    _ = (_);

    = -1

    };

    end.

    рис.8

    Додатковим джерелом удосконалення є правильна настройка параметрів управління.

    Використання розглянутих засобів і методів пошукової адаптації дозволило синтезувати ефективний алгоритм рознесення з'єднань по верствам.

    6. Експериментальні дослідження. Генетичний алгоритм рознесення з'єднань по верствам був реалізований на мові Сі ++ в середовищі Windows. Експериментальні дослідження проводилися на ЕОМ типу IBM PC / AT Pentium 166.

    Основною метою експериментальних досліджень було виявлення залежності і впливу на якість виконання завдання різних комбінацій керуючих параметрів і структур. В результаті експериментів було встановлено, що для генетичного алгоритму такими значеннями є Рк = 0,35; Рм = 0,1; М = 80; К = 120.

    Імовірність отримання оптимального рішення після одного прогону генетичного алгоритму склала 0,8. Дослідження трудомісткості алгоритму показали, що при фіксованих значеннях Рк і Рм, М і К вона має оцінку O (v). Час виконання 120 генерацій для рознесення 200 ланцюгів склало 48 секунд.

    Кращі за якістю рішення виходили при використанні підходу, пов'язаного з розпаралелюванням генетичного алгоритму. В процесі генетичного пошуку здійснюється еволюціонування декількох подпопуляцій. На кожній генерації хромосоми випадковим чином мігрують з однієї подпопуляціі в іншу. Дослідження показали, що достатньо трьох подпопуляцій, при цьому ймовірність отримання оптимального рішення склала 0,92. експериментальні , -

    , , = 20 5 -

    роятность отримання оптимального рішення склала 0,99.Сравненіе з алгоритмом [1,3,4],

    роботи запропонований алгоритм дає більш якісні рішення. Перевага особливо помітно для задач великої розмірності.

    ЛІТЕРАТУРА

    1. Курейчик В. М. Математичне забезпечення конструкторського і технологічного проектування із застосуванням САПР. М .: Радио и связь, 1990. 352с.

    2. Селютин В.А. Машинне конструювання електронних пристроїв. М .: Сов.радіо, 1977. 384с.

    3. Каляєв А.В. та ін. Автоматизація проектування обчислювальних структур. Ростов н / Д: Изд-во РГУ, 1983. 224 с.

    4. Карелін В.П., Калашников В.А. Застосування методу бівалентного програмування для вирішення деяких завдань технічного проектування // Мікроелектроніка. 1979. Вип.5. Т.8.

    5.. . // -

    Вести ТРТУ. Тематичний випуск "Інтелектуальні САПР". Таганрог: Изд-во ТРТУ, 1999. №3. С.176-186 .

    6. Лебедєв Б.К Адаптація в САПР: Монографія. Таганрог: Изд-во ТРТУ, 1999. 160с.

    УДК 681.3.001.63

    Ю.В. Чернухін, Ю.Ю. Здоровеющее

    СЕТЕВОЙ еволюційного-ГЕНЕТИЧНИЙ АЛГОРИТМ ПРИЙНЯТТЯ КОЛЕКТИВНИХ РІШЕНЬ В людина-машина СИСТЕМАХ

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

    В роботі [1] обґрунтована можливість використання ЕГМ для вирішення завдання колективного складання фотопортретів. Таке завдання виникає в слідчій практиці в тому випадку, коли кілька людей бачили підозрюваного, запам'ятали різні риси його обличчя і намагаються спільно скласти його консолідований фоторобот. Як випливає з [1], використання ЕГМ дозволяє отримувати портрети підозрюваних на підставі колективних знань свідків.

    Для організації колективного прийняття рішень на ЕОМ в даному випадку використовується простий генетичний алгоритм [2], графічний образ якого має вигляд, показаний на рис. 1.

    Рис.1. Схема класичного еволюційно-генетичного алгоритму

    З рис.1 видно, що процес прийняття колективних рішень відбувається за , .


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

    Завантажити