Етапи генетичного алгоритму

Можна виділити такі етапи генетичного алгоритму:

· Створення початкової популяції:

· Обчислення функції пристосованості для осіб популяції (оцінювання)

· Повторювання до виконання критерію зупинки алгоритму:

· Вибір індивідів із поточної популяції (селекція)

· Схрещення або/та мутація

· Обчислення функції пристосовуваності для всіх осіб

· Формування нового покоління

Створення початкової популяції

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

Відбір

Докладніше: Оператори вибору батьків

На етапі відбору необхідно із всієї популяції вибрати її певну долю, яка залишиться в «живих» на цьому етапі популяції. Є декілька способів провести відбір. Ймовірність виживання особи h повинна залежати від значення її пристосованості Fitness(h). Сама ж доля відібраних s зазвичай є параметром генетичного алгоритму, і її просто задають заздалегідь. Внаслідок відбору із N осіб популяції H повинні залишитись sN осіб, які ввійдуть в наступну популяцію H'. Решта осіб «загине».

Розмноження

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

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

Приклад операції розмноження: Вибрати (1-s)p/2 пар гіпотез із H і провести з ними розмноження, отримавши по два нащадка від кожної пари (якщо розмноження описано так, щоб давати одного нащадка, необхідно вибрати (1 - s)p пар), і добавити цих нащадків в H'. В результаті H' буде складатися з N осіб.

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

Мутації

До мутацій відноситься все те ж, що і до розмноження: є деяка доля мутантів m, що є параметром генетичного алгоритму, і на кроці мутацій необхідно вибрати mN осіб, а згодом змінити їх згідно з заздалегідь заданими операціями мутації.

29. Застосування нейромереж для розв’язування оптимізаційних задач. Переваги та недоліки.

Штучні нейронні мережі (ШНМ) — математичні моделі, а також їхня програмна та апаратна реалізація, побудовані за принципом функціонування біологічних нейронних мереж — мереж нервових клітин живого організму. Системи, архітектура і принцип дії базується на аналогії з мозком живих істот. Ключовим елементом цих систем виступає штучний нейрон як імітаційна модель нервової клітини мозку — біологічного нейрона. Цей термін виник при вивченні процесів, які відбуваються в мозку, та при спробі змоделювати ці процеси. Першою такою спробою були нейронні мережі Маккалока і Піттса. Як наслідок, після розробки алгоритмів навчання, отримані моделі стали використовуватися в практичних цілях: в задачах прогнозування, для розпізнавання образів, в задачах керування та інші.

ШНМ представляють собою систему з'єднаних і взаємодіючих між собою простих процесорів(штучних нейронів). Такі процесори зазвичай достатньо прості, особливо в порівнянні з процесорами, що використовуються в персональних комп'ютерах. Кожен процесор схожої мережі має справу тільки з сигналами, які він періодично отримує, і сигналами, які він періодично посилає іншим процесорам. І тим не менш, будучи з'єднаними в досить велику мережу з керованою взаємодією, такі локально прості процесори разом здатні виконувати достатньо складні завдання. З точки зору машинного навчання, нейронна мережа являє собою окремий випадок методів розпізнавання образів, дискримінантного аналізу, методів кластеризації тощо З математичної точки зору, навчання нейронних мереж — це багатопараметрична задача нелінійної оптимізації. З точки зору кібернетики, нейронна мережа використовується в задачах адаптивного управління і як алгоритми для робототехніки. З точки зору розвитку обчислювальної техніки та програмування, нейронна мережа — спосіб вирішення проблеми ефективного паралелізму. А з точки зору штучного інтелекту, ШНМ є основою філософської течії коннективізму і основним напрямком в структурному підході з вивчення можливості побудови (моделювання) природного інтелекту за допомогою комп'ютерних алгоритмів. Нейронні мережі не програмуються в звичайному розумінні цього слова, вони навчаються. Можливість навчання — одна з головних переваг нейронних мереж перед традиційними алгоритмами. Технічно навчання полягає в знаходженні коефіцієнтів зв'язків між нейронами. У процесі навчання нейронна мережа здатна виявляти складні залежності між вхідними даними і вихідними, а також виконувати узагальнення. Це означає, що у разі успішного навчання мережа зможе повернути вірний результат на підставі даних, які були відсутні в навчальній вибірці, а також неповних та / або «зашумленних», частково перекручених даних.

30. Методи та алгоритми розв’язування комбінаторних задач високих розмінностей.

31. Математичне формулювання задач декомпозиції складних схем.

32. Алгоритми декомпозиції задач високих розмінностей.

33. Задача комівояжера. Математичне формулювання задачі та алгоритми розв’язування.

34. Задача пакування. Математичне формулювання задачі та алгоритми розв’язування.

 

35. Класифікація методів та алгоритмів для розв'язування задачі розбиття, їх переваги та недоліки. Обчислювальна складність.

 

розбиття множин.
алгоритми: генерування всіх підмножин n-елементної множини, генерування всіх k-елементних підмножин множини {1,..., n} в лексикографічному порядку, генерування всіх розбиттів множини {1,..., n} (на цьому алгоритмі зупинимося докладніше), знаходження всіх розбиття числа.
Перший з цих алгоритмів використовує ідею бінарного коду Грея, інші засновані на видаленні або додавання одного елемента. Останній алгоритм використовує схему розбивки більшого числа на менші числа.
Постановка завдання
Формулювання першого завдання, яку ми розглянемо, виглядає так: необхідно згенерувати всі розбиття множини, що містить n елементів.
Для формулювання другого завдання необхідно ввести деякі поняття.
Отже, дано безліч, що складається з n елементів. Кожен елемент цієї множини утворює деяке поняття. Два або більше поняття можуть бути об'єднані в нове поняття. Відмінна риса понять - взяття їх у круглі дужки.
Завдання виглядає так: згенерувати всі поняття, які можуть бути утворені з n елементів. Наприклад, для n = 3 маємо такі поняття (круглі дужки на початку і в кінці опущені для стислості): (*)**, (*)(*)*, (*)(*)(*), (**) *, (**)(*), ((*)*)*, ((*)*)(*), ((*)(*))*, ((*)(*))(*).
Математичне обгрунтування

Під розбивкою n-елементної множини Х на k блоків будемо розуміти довільне сімейство , Таке, що для 1 £ І <j £ k і для 1 £ i £ k. Підмножини будемо називати блоками сімейства π. Безліч всіх розбиттів множини Х на k блоків будемо позначати , А множина всіх розбиття через П (Х). Очевидно, що (Більше того, є розбиттям множини П (Х)).

Число Стірлінга другого роду S (n, k) визначається як число розбиття n-елементної множини на k блоків:
де | X | = n.
Очевидно, що S (n, k) = 0 для k> n. Приймають також S (0,0) = 1, так як пусте сімейство блоків є відповідно до визначення розбивкою порожньої множини. З числами Стірлінга другого порядку пов'язано багато цікавих тотожностей:
S (n, k) = S (n-1, k-1) + kS (n-1, k) для 0 <k <n, (1)
S (n, n) = 1 для n ≥ 0, (2)
S (n, 0) = 0 для n> 0. (3)
Формули (2) та (3) очевидні. Для доказу формули (1) розглянемо безліч всіх розбиттів множини {1,..., n} на k блоків. Це безліч розпадається на два різних класи: тих розбиттів, які містять одноелементні блок {n}, і тих розбиття, для яких n є елементом більшого (принаймні, двоелементною) блоку. Потужність першого класу дорівнює S (n-1, k-1), тобто така, яке число розбиття множини {1,..., n-1} на (k-1) блоків. Потужність іншого класу становить kS (n-1, k), оскільки кожному розбиття множини {1,..., n-1} на k блоків відповідає в цьому класі в точності k розбиття, утворених додаванням елемента n по черзі до кожного блоку.
Формули (1) - (3) дозволяють легко обчислювати значення S (n, k) навіть для великих значень n і k.
Ось інша рекурентна залежність:
для k ≥ 2. (4)
Для доказу тотожності розглянемо безліч всіх розбиття S (n, k) множини Х = {1,..., n}. Це безліч розпадається на різні класи, що відповідають різним підмножиною множини Х, які є блоками, які містять елемент n. Відзначимо, що для кожного b-елементного підмножини містить елемент n, існує в точності S (nb, k-1) розбиттів множини Х на k блоків, що містять В як блоку. Дійсно, кожне таке розбиття однозначно відповідає розбиття множини Х \ В на k-1 блоків. b-елементне безліч містить елемент n, можна вибрати способами; таким чином,

Число Белла визначається як число всіх розбиття n-елементної множини
де | X | = n.
Іншими словами,

Доведемо рекуррентную залежність, пов'язану з числами Белла:
(5)
(Приймаємо ). Доведення проводиться аналогічно докази тотожності (4). Безліч всіх розбиттів множини Х = {1,..., n +1} можна розбити на різні класи в залежності від блоку В, що містить елемент n +1, або - що рівнозначно - в залежності від багатьох Х \ В. Для кожного безлічі існує в точності розбиттів множини Х, що містять В як блоку. Групуючи наші класи в залежності від потужності множини Х \ В, отримуємо формулу (5).
Тепер опишемо алгоритм генерування всіх розбиттів множини.
Зазначимо, що кожне розбиття p множини {1,..., n} однозначно визначає розбиття множини {1,..., n-1}, що виникло з p після видалення елемента n звідповідного блоку (і видалення утворився простого блоку, якщо елемент n утворював одноелементні блок). Навпаки, якщо дано розбиття множини {1,..., n-1}, легко знайти всі розбиття π множини {1,..., n}, такі що , Тобто такі розбиття:

Якщо нам дано список всіх розбиттів множини {1,..., n-1}, то список всіх розбиттів множини {1,..., n}, будемо створювати, замінюючи кожне розбиття σ в списку на відповідну йому послідовність (6). Якщо звернути порядок послідовності (6) для кожного другого розбиття , То елемент n буде рухатися поперемінно вперед і назад, і розбиття «на стику» послідовностей, утворених з сусідніх розбиття списку мало відрізняються один від іншого.

Розбиття множини {1,..., n} ми будемо представляти за допомогою послідовності блоків, впорядкованої за зростанням самого маленького елемента в блоці. Цей найменший елемент блоку ми будемо називати номером блоку. Відзначимо, що номери сусідніх блоків, взагалі кажучи, не є сусідніми натуральними числами. У цьому алгоритмі ми будемо використовувати змінні divd [і], sled [і], 1 ≤ І ≤ n, що містять відповідно номер попереднього і номер наступного блоку з номером і (sled [і] = 0, якщо блок з номером І є останнім блоком розбиття). Для кожного елемента І, 1 ≤ І ≤ n, номер блоку, що містить елемент І, буде зберігатися у змінній blok [і], напрям, в якому «рухається» елемент І, буде закодовано в булевою змінної wper [і] (wper [і ] = true, якщо І рухається вперед).
Можна показати, що середня кількість кроків, необхідних для побудови кожного наступного розбиття, обмежена постійною, не залежної від n (звичайно, якщо не враховувати число кроків, необхідних для написання розбиття).

(1 2 3 4) (1 2 3) (4) (1 2) (3) (4) (1 2) (3 4) (1 2 4) (3) (1 4) (2) (3) (1) (2 4) (3) (1) (2) (3 4) (1) (2) (3) (4) (1) (2 3) (4) (1) (2 3 4) (1 4) (2 3) (1 3 4) (2) (1 3) (2 4) (1 3) (2) (4)

Табл.1. Послідовність розбиттів множини {1,2,3,4}
Наведемо тепер алгоритм розв'язання задачі про перерахування всіх понять.
Рекурсивний алгоритм використовувати не можна, бо всі рішення підзадачі меншої розмірності необхідно скомбінувати з усіма рішеннями підзадачі залишилася розмірності. Тому, будемо просто перебирати всі варіанти.
Ідея така: зберігаємо всі розбиття меншої розмірності і комбінуємо їх так, щоб
1) вони не повторювалися;
2) кількість елементів нового розбиття не було б більше кількості елементів n.
Отже, нехай ми маємо два початкових стану: (*) та *. Для n = 2 маємо тільки одне вихідна поняття: (*)*. Для n = 3 необхідно скомбінувати всі відомі раніше стану з урахуванням умов 1) -2).
Умова 1) забезпечимо з таких міркувань: кожному елементу присвоїти порядковий номер і комбінувати поняття так, щоб порядковий номер наступного поняття не перевершував порядковий номер попереднього поняття, а також стежити, щоб виконувалася умова 2). Звідси видно, що повторень не буде, і ми перерахуємо всі поняття.
Для реалізації умови 2) необхідно кожному поняттю привласнити число, яке буде показувати кількість елементів цього стану.
Також необхідно мати деякий масив, кожен елемент якого буде вказувати на поняття, що відповідає номеру поняття у вихідному понятті. Елементи цього масиву будуть змінюватися, відповідно до перебором варіантів.

Теорема про ідеальні розбиття. Для будь-яких натуральних чисел m та n всі m -елементні підмножини mn -елементної множини можна розбити на групи по n штук таким чином, щоб підмножини в кожній групі не перетиналися.

Доведення. Нехай дано n -елементну множину, та S₁, S₂,..., S _k – набори підмножин цієї множини. Причому для кожного натурального i (1≤ i ≤ k) набір S _i містить всі m_i -елементні підмножини нашої множини по одному разу, де m ₁, m ₂,..., m_k – задана послідовність натуральних чисел, не більших за n. Також нехай задано деякі набори J₁, J₂,..., J _z натуральних чисел від 1 до k (ці числа будуть служити індексами для S₁, S₂,..., S _k). При цьому виконуються дві умови. По‑перше, для кожного набора чисел J _x, якщо його члени позначити через j ₁, j ₂,..., j_p, буде виконуватися рівність m_{j 1}+ m_{j 2}+...+ m_jp = n. По‑друге, кожне натуральне число i (1≤ i ≤ k) зустрічається у всіх наборах J₁, J₂,..., J _z стільки ж разів, скільки є підмножин у S _i.

Якщо ці умови виконані, то існує розбиття на групи всіх підмножин з наборів S₁, S₂,..., S _k, таке, що підмножини кожної групи не перетинаються. І при цьому всі групи можна привести у відповідність з заданими наборами J₁, J₂,..., J _z так, що для кожної групи виконуватиметься наступна умова: якщо члени набора J _x, відповідного цій групі, позначити через j ₁, j ₂,..., j_p, то підмножини у цій групі (при деякому впорядкуванні) будуть саме з наборів S _{j 1}, S _{j 2},..., S _jp відповідно. (Навіть якщо деякі підмножини з різних наборів – однакові, для кожної підмножини ми зазначаємо, в якому саме наборі S _y вона міститься.)

Доведення цього факту можна провести по тій же схемі, що й доведення існування ідеальних розбиттів. При цьому слід зауважити, що у відповідному графі вершину, що відповідає перетину з множиною {1; 2;...; x } підмножини з набору S _i (для деякого i), ми з’єднаємо не з усіма групами розбиття, що містять такі ж перетини, а лише з тими групами, що містять такі ж перетини з підмножиною з того ж набору.

Такі розбиття підмножин будемо називати мішаними ідеальними. Очевидно, “чисті” ідеальні розбиття є частковим випадком мішаних – для одного набору підмножин S₁.

А що робити у випадках, коли сумарний розмір множин у деяких групах має бути меншим за n? Наприклад, ми хочемо розбити на мінімальну кількість груп m ‑елементні підмножини n ‑елементної множини у випадку, коли n не дилиться на m. Виявляється умову m_j1 + m_{j 2}+...+ m_jp = n можна замінити на m_{j 1}+ m_{j 2}+...+ m_jp ≤ n.

Щоб довести можливість розбиття при такій умові, можна ввести додаткові набори одноелементних множин S _{k +1}, S _{k +2},..., S _l, і додати їх індекси у кожний набір J _x стільки разів, на скільки сума m_{j 1}+ m_{j 2}+...+ m_jp (де j ₁, j ₂,..., j_p – члени J _x) менша за n. Загальна кількість підмножин у додаткових наборах має дорівнювати загальній кількості нестач сум m_{j 1}+ m_{j 2}+...+ m_jp до n. Для можливості рівності треба, щоб ця сума сума нестач ділилася на n. Але це довести нескладно. Для наборів S₁, S₂,..., S _l і поповнених наборів J₁, J₂,..., J _z побудуємо мішане ідеальне розбиття, а потім видалимо з груп цього розбиття підмножини, що були членами додаткових наборів S _{k +1}, S _{k +2},..., S _l, і отримаємо розбиття, яке вимагалося спочатку.

Такі розбиття будемо називати мішаними субідеальними, або якщо розбиваються на групи підмножини лише з одного набору – то просто субідеальними.

 

36. Задача розміщення. Математичне формулювання задачі розміщення.

Розміщенням із n елементів по m, або впорядкованою (n, m) вибіркою із множини M (потужність n, m ≤ n) називають довільний кортеж що складається із m попарно відмінних елементів. Розміщення можна розглядати як різнозначну функцію f: , для якої .

Кількість розміщень із n по m позначається як або і обчислюється за наступною формулою:

 

Розміщенням з повтореннями із n елементів по m або впорядкованою (n, m) вибіркою з поверненнями називається довільний кортеж елементів множини M, для якого | M | = n.

Кількість можливих розміщень з повтореннями із n елементів по m дорівнює n піднесене до степеня m:

Наприклад, із цифр 1, 2, 3, 4 можна скласти трьохзначних числа.

 

37. Класифікація методів та алгоритмів для розв'язування задачі розміщення, їх переваги та недоліки. Обчислювальна складність.

АЛГОРИТМИ РОЗМІЩЕННЯ

 

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

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

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

До таких критеріїв відносяться: 1) мінімум сумарної зваженої довжини з'єднань; 2)мінімум числа сполук, довжина яких більше заданої; 3) мінімум числаперетин провідників; 4) Максимальна кількість з'єднань між елементами,що знаходяться в сусідніх позиціях або в позиціях, зазначених розробником;
5) максимум числа ланцюгів простої конфігурації.

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

Залежно від конструкції комутаційної плати і способів виконаннясполук відстань між позиціями установки елементів підраховується заоднією з наступних формул:

,,

У загальному вигляді завдання розміщення конструктивних елементів на комутаційної?? лате формулюється наступним чином. Визнач безліч конструктивнихелементів R = (r1, r2,..., rn) і безліч зв'язків між цими елементами
V = (v1, v2,..., vp), а також безліч настановних місць (позицій) накомутаційної платі T = (t1, t2,..., tk). Знайти таке відображення множини R набезлічі T, який забезпечує екстремум цільової функції

, де cij - коефіцієнт зваженої зв'язності.

 

Силові алгоритми розміщення

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

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

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

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

Ітераційні алгоритми розміщення

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

У випадку мінімізації сумарної зваженої довжини з'єднань формуладля розрахунку зміни значення цільової функції при перестановці місцямиелементів ri і rj, закріплених в позиціях tf і tg, має вигляд:

,де p і h (p) - порядковий номер і позиція закріплення нерухомого елементаrp. Якщо, то здійснюють перестановку ri і rj, що приводить дозменшення цільової функції на, після чого проводять пошук іперестановку наступної пари елементів і т.д. Процес закінчуєтьсяотриманням такого варіанту розміщення, для якого подальше поліпшення зарахунок парних перестановок елементів неможливо.

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

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

Послідовні алгоритми розміщення

Послідовні алгоритми грунтуються на припущенні, що для отриманняоптимального розміщення необхідно в сусідніх позиціях розташовуватиелементи, максимально пов'язані одна з одною. Сутність цих алгоритмівполягає в послідовному закріплення заданого набору конструктивнихелементів на комутаційної плати щодо раніше встановлених. Уяк спочатку закріплених на платі елементів зазвичай вибираютьроз'єми, які штучно «розсовують» до країв плати. При цьому всіконтакти роз'ємів рівномірно розподіляються по секціях (стовпцях і рядкахкоординатної сітки). На кожному l-му кроці (l = 1,2,..., n) для установки накомутаційну плату вибирають елемент з числа ще не розміщених,що має максимальну ступінь зв'язності з раніше закріпленими елементами Rl-
1. У більшості використовуються в даний час алгоритмів оцінку ступенязв'язності виробляють по одній з наступних формул:

;

,де cij - коефіцієнт зваженої зв'язності елементів i та j; Jl-1 --безліч індексів елементів, закріплених на попередніх l-1 кроки; n --загальна кількість розміщених елементів.

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

,де dfj - відстань між f-ої позицією установки елемента іпозицією розміщеного раніше елементу rj; Tl-1 - безліч позицій, зайнятихелементами після (l-1)-го кроку алгоритму.

Процес розміщення алгоритму закінчується після виконання n кроківалгоритму.

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

 

38 Задача трасування. Математичне формулювання задач трасування.

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

Як критерій оптимальності тут беруть: мінімум сумарної довжини трас, мінімум числа з’єднуючих трас довжини більше заданої та ін.

 

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

,

де - Адитивний критерій; - Ваговий коефіцієнт; - Приватний критерій; - Число приватних критеріїв.