Евристичні методи оптимізації

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

Оптимізація топології з використанням евристичних методів виробляється по алгоритму, що ґрунтується на методі усунення ребер (ВМУР). Відповідно до цього алгоритму: 1) вибирають вихідну топологію (часто на практиці вибирають повнозв’язну мережу); 2) для кожного каналу, заданого у вихідній топології, проводять степеневу апроксимацію вартості: ; ; 3) розглянутими методами вирішують спільну задачу вибору пропускних можливостей і розподілу потоків; 4) задаються дискретними змінами безперервних пропускних здібностей, отриманих з рішення задачі; 5) проводять оптимізацію потоків шляхом застосування алгоритму обмеження потоків;

6) повторюють п. 3 і 5 для ряду реалізованих початкових потоків;

7) при необхідності повторюють п. 1—6 для декількох початкових топологій.

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

На мал.4 приведена загальна схема алгоритму автоматизованого топологічного проектування із застосуванням ЕОМ. У блоці А генеруються початкові конфігурації, що проходять топологічну перевірку в блоці В. Приймаються рішення про подальші локальні виправлення, за яких йде визначена послідовність тестів для пошуку найкращої конфігурації.

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

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

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

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

.

Рис. 4. Процедура топологічного Рис.5. Ілюстрація методу

проектування насиченого перетину

 

Нехай у мережі маються дві гілки |i, k|і |j, h|, а гілки |i, h| і |j, k|у мережі відсутні. Шляхом вилучення гілок |i, k|і |j, k|і додавання гілок |i, h| |і |j, h|можна побудувати нову мережу, для якої перевіряється умова:

Рис.6. Ілюстрація методу «виключення замкнутих шляхів»:

а — вихідна структура; б, в — варіанти ітерацій.

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

Гарною евристичною процедурою є процедура, реалізована по методу виключення замкнутих шляхів. Вихідною топологією служить довільне дерево (мал. 6 а)). За допомогою відповідних перетворень можна одержати з одного дерева будь-яке інше. Ці перетворення полягають у наступному. У даному дереві вибирають вузол , і знаходять вузол , найближчий до , але ще не з'єднаний з ним (мал. 6 б)). До вихідного дерева додається гілка (, ) і створюється замкнутий ланцюг, що складається з гілок (, )(, ). Почерговим виключенням гілок (, ), (, ),..., (, )утворяться нові дерева (мал. 6, в)). На кожнім кроці ітерації вирішується задача оптимального розподілу пропускних здібностей гілок, визначається відповідна вартість мережі і робиться необхідне додавання гілок між вузлами і з найближчими до вузлами для утворення дерев з більш низькою вартістю. Процес продовжується доти, доки не будуть досягнуті прийнятні варіанти. Для більшості задач гарні результати виходять при числі ітерацій k, рівному трьом [8].

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

.

Рис.7. До приклада оптимізації багатоконтурних структур у рамках задачі про р- медіану.

 

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

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

У цьому випадку зміст відповідає так званій «задачі комівояжера», що представляє собою наступне. Нехай заданий граф G (V, U), дугам якого приписані різні ваги.Необхідно знайти такий гамільтонів контур, що має найменшу загальну вагу, тобто мінімальний гамільтонів контур. Для рішення задачі знаходження мінімального гамільтонівого контуру користуються алгоритмом Літтла.

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

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

Приведемо приклад оптимізації розподіленої мережі. На мал. 7, а) зображена вихідна мережа, а на мал. 7, б) зазначені гілки, що додаються та виключаються.

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