Область наук:
  • Комп'ютер та інформатика
  • Рік видавництва: 2003
    Журнал: Известия Південного федерального університету. Технічні науки

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

    ?особистих постановках, залишаючи окремі види хромосом незмінними в процесі генетичного пошуку.

    Наприклад, при фіксованих H1, H2 шукати оптимальне рішення тільки лише за рахунок зміни h3, тобто типів розрізів (Н або V).

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

    - . -

    таким чином. Спочатку на обраної батьківської парі R1 і R2 реалізується

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

    2, . . . -

    R1 R2 1 2 -

    ється дочірня пара R1 "і R2".

    , -

    , -

    нальна O (N), де N - число блоків.

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Naveed Sherwani. Algorithms for VLSI physical design automation. Kluwer academic publishers. Boston / Dordrecht / London. 1995.

    2. K. Bazargan, S. Kim, and M. Sarrrafzadeh, Nostradamus: a Floorplanner of Uncertain Designs.// IEEE Transaction on Computer Aided Design of Integrated Circuits and Systems, vol. 18, no.4, April тисяча дев'ятсот дев'яносто дев'ять.

    3.. . . // .

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

    УДК 621.3.06

    В.А. Литвиненко, В.А. Калашников

    АЛГОРИТМ АДАПТАЦІЇ проектної ОПЕРАЦІЇ ВИЗНАЧЕННЯ

    КЛИК ГРАФА

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

    допомогою параметрів адаптації, які вибираються на основі заздалегідь отриманий, [1,2].

    В роботі [8,10] розглянуто склад адаптивного програмного модуля проектної операції визначення клік графа [3,4], побудованого на основі бібліотеки

    (),

    основі параметричної адаптації. Структурна схема програмного модуля показана на рис.1.

    вхідні

    параметри

    ялинок

    адаптації

    база.

    даних

    бібліотека

    ПМ1

    програмних

    модулів

    ПМ2

    ПМ 3

    _]

    .l

    Вхідними параметрами є: d - необхідна точність рішення, t - ресурс часу, відведений для виконання проектної операції, n - число вершин графа, m - число ребер графа (р ^ мірність завдання).

    Під точністю рішення задачі визначення клік графа розуміється кількість виділених клік. Точне рішення відповідає виділенню всіх клік графа [6-9].

    ПМ1 і ПМ2 реалізують алгоритми визначення сімейств клік графа, що покривають відповідно всі вершини і ребра графа [5], і призначені для отримання наближених рішень. ПМ3 реалізує адаптивний алгоритм [7]. Адаптація алгоритму проводиться завданням цілочисельного значення керуючому,. цьому точність рішення лежить в межах від виділення всіх клік графа - точного , , .

    Блок адаптації виконує наступні функції:

    - робить аналіз вхідних даних;

    - вибирає необхідні дані з бази даних;

    - -;

    - -

    ;

    - -

    ;

    - розпізнає графи, критичні для задачі визначення клік графа - графи Муна-Мозера [4].

    Аналіз вхідних даних. Здійснюється з метою вибору ПМ, що дозволяє отримати найбільш точний результат при заданому ресурсі часу. У зв'язку з цим повинен бути таким пріоритет вибору ПМ. Спочатку аналізується віз-

    3, ,

    - 2, - 1,,,, найменш точного. Вибір ПМ1 і завдання значення параметру адаптації h виконується на основі аналізу таблиці Tab, що зберігається в базі даних (див. Рис.1).

    База даних. Таблиця Tab являє собою табличное завдання сімейства функцій залежно часу і точності рішення від розмірності графа (числа) h: T (n, m), D (n, m) при h = const.

    n m. n

    змінювалося від 20 до 1000 з кроком 10, a m - від n / 100 до n (n-1) / 2 c кроком 20.

    На рівні структури даних таблиця задається тривимірним динамічним масивом структур з різною розмірністю рядків, що дозволяє вносити зміни в базу даних, при необхідності проведення додаткових досліджень. Кожен елемент масиву представляє собою структуру з двома полями: перше поле відповідає часу рішення, а друге - точності, тобто кожен елемент таблиці Tab (i, j, k) має поля Tab (i, j, k) .T і Tab (i, j, k) .D. кількість двовимірних

    h.

    [8,11] показали, що діапазон значень параметра h від 1 до 9 для графів до 1000 .

    алгоритм адаптації.

    :

    n1, m1 - , -

    нання яких складено масив Tab; d - необхідна точність рішення (%); t -,;

    tr - ресурс часу, достатній для отримання точного рішення при n = 1, m = m1;

    tm - ресурс часу при відсутність обмеження на час вирішення завдання; t1 - час виконання модуля ПМ1; t2 - 2; t3- час виконан ня модуля ПМ3;

    ts - сумарний час виконання декількох ітерацій модулів;

    l - лічильник кількості ітерацій при виконанні модулів ПМ1 і ПМ2;

    g - номер виконуваного модуля, g = {1,2,3};

    q (i) - локальна ступінь вершини з номером i;

    h1 - Tab;

    Inf - інформація про графа, яка може бути задана матрицею суміжності або списком суміжних вершин.

    Сформулюємо алгоритм адаптації.

    1. Введення даних: t, d - параметрів, що відповідають умовам роботи проектної операції, і n, m, Inf - розмірність і структура графа. Перехід до п.2.

    2. Якщо d = 0, то перехід до п.13, інакше, якщо t = tr і d = 100, то h = 1 і перехід до п.7, інакше перехід до п.3.

    3. Якщо 100 > d >30, то перехід до п.4, інакше перехід до п.12.

    4. Визначити локальну ступінь q (i) будь-яку i-ї вершини графа. Якщо для кожної i-ї вершини q (i) = n-3 і n>100, то перехід до п.7, інакше перехід до п.5.

    5. n>n1 m>m1, -

    нительного дослідження графа і, якщо t = tm, то k = h1 і перехід до п.6., інакше, якщо t< tr, то перехід до п.7. якщо n<n1 або m<m1, то перехід до п.9.

    6. Виконання ПМ3. Потім k = 1 і виконання ПМ3 до закінчення ресурсу часу, при цьому перехід до п.18.

    7. Виконання ПМ1. якщо t1<t, то виконання ПМ2 до закінчення ресурсу часу, при цьому перехід до п.18. Задати ts = t1 + t2. якщо ts< t, то k = h1 і перехід до

    .8.

    8. Виконання ПМ3 до закінчення ресурсу часу, при цьому перехід до п.18. При виконанні ПМ3 до кінця задати ts = ts + t3, і, якщо ts<t, то k = k-1 і, якщо k = 0, то перехід до п.18, інакше повторити п.8.

    9. i j Tab, n m,

    задати k = 1 і перехід до п.10.

    10. Якщо елемент таблиці Tab (i, j, k) такою, що Tab (i, j, k) .T > t, то, якщо d > Tab (i, j, k) .D, задати h = k, g = 3 і перехід до п.12, інакше перехід до п.11.

    11. Поставити k = k + 1. якщо k > h1, то перехід до п.13, інакше перехід до п.10.

    12. Виконання ПМ3. якщо t>t3, то задати ts = t3, g = 2, l = 0 і перехід до п.14,

    .18.

    13. ts = 0; l = 0. якщо 30 > d >15, то g = 2 і перехід до п.14, інакше g = 1 і пере-.15.

    14. Виконання ПМ2. ts = ts + t2 і перехід до п.16.

    15. Виконання ПМ1. ts = ts + t1 і перехід до п.16.

    16. l = l + 1. якщо t>ts + ts / l), то перехід до п.17, інакше перехід до п.18.

    17.. g = 2, -

    хід до п.9, інакше, якщо g = 1, то перехід до п.10.

    18. .

    Розглянемо роботу алгоритму адаптації.

    .2 1, -шей точністю, а, якщо ресурс часу досить великий і необхідно визначити всі кліки графа, то вибирає ПМ3, задавши для нього значення параметра, рав-

    1, .

    .3: , -

    шення більше 30%, то вибирається для виконання ПМ3. Але спочатку перевіряється -не є граф графом Муна-Мозера (п.4), тому що відомо, що ці графи містять експоненціальне число клік, і, отже, є найбільш критичними для завдання виділення клік графа. Для цього визначаються локальні, n-3 ,

    , - . , дозволяє виявити критичні графи. В цьому випадку процес пошуку клік направляється на отримання спочатку рішення найменш точного, але і найменш трудомісткого, тобто вибирається для виконання ПМ1 (п.7). Потім, якщо ресурс часу ні, 2,, буде вичерпаний ресурс часу. Якщо модуль ПМ2 все ж буде виконаний, то вибирається модуль ПМ3 (п.6), при цьому параметр адаптації вибирається так, щоб забезпечити найменш трудомісткий процес визначення клік (п.7). така стратегія , .

    .5 -

    , . , -

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

    При цьому (п.5) проводиться формування вимоги відкладеного додаткового дослідження графа, яке повинно бути виконано після завершення проектної процедури або всього процесу проектування. Якщо ресурс време-, ,

    Муна-Мозера (п.п.7,8), з тією відмінністю, що модуль ПМ3 може виконуватися не-

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

    П.п.9-12 призначені для вибору з бази даних відповідної інформації про час і можливої ​​точності рішення при різних значеннях параметра адаптації модуля ПМ3 в залежності від розмірності графа. При цьому вибирається найменше значення параметра адаптації, при якому можливо отримати рішення необхідної точності. Якщо після виконання ПМ3 ресурс час не буде вичерпаний (п.12), то вибирається модуль ПМ2, багаторазове виконання якого до різних підстановки графа направлено на підвищення точ-.

    П.п.13-17 призначені для організації ітераційного процесу визна-

    1, 2, -ся до різних підстановки вихідного графа. Кількість ітерацій обмежено ресурсом часу. Вибір для виконання або модуля ПМ1, або ПМ2 залежить від необхідної точності. Дослідження [8] показали, що ПМ2 доцільно використовувати для отримання рішень з точністю від 15 до 30%, а ПМ1 - для отримання точності менше 15%. Перехід до чергової ітерації проводиться на основі прогнозу часу виконання наступної ітерації.

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

    . -

    ні методи вибору ПМ, а сама бібліотека ПМ може бути розширена за рахунок включення в неї інших ПМ, наприклад ПМ, який реалізує алгоритм Брона-Кербоша (адгорітм №457) [4], для якого в [9] запропонована модифікація, яка переводить його в клас адаптивних алгоритмів. Для отримання наближених реше-, 1, 2, генетичні алгоритми визначення клік графа.

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

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Растригин Л.А. Адаптація складних систем. Рига: Зинатне, 1981. 315с.

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

    3. Крістофідес Н. Теорія графів. Алгоритмічний підхід. / Пер. з англ. Під редакцією Г.Г. Гаврилова. М .: Світ, 1978. 432с.

    4. Рейнгольд Е., Нівергельт Ю., Део Н. Комбінаторні алгоритми. Теорія і практика. / Пер. з англ. Під ред. В.Б.Алексеева, М.: Мир, 1980. 476с.

    5. . ., . ., . .

    дискретних пристроїв. М .: Сов.радіо, 1975. 224с.

    6.. . / -

    . 2. , . -

    . 1982. .90-92.

    7.. .,. . . 30.

    Intern. Wiss. Koll. TH llmenau Vortragsreihe. 1985. C.41-44.

    8. . .

    / Известия ТРТУ. Тематичний випуск «Інтелектуальні САПР». Таганрог: Изд-во ТРТУ, 2000., №2 (16). С.186-189.

    9. . ., . ., . . -

    діфіцірованного алгоритму визначення клік графа / Известия ТРТУ. Тематичний випуск «Інтелектуальні САПР». Матеріали міжнародної науково-технічної конференції «ІСАПР». Таганрог: Изд-во ТРТУ, 2002 №3 (26). с.204-205.


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

    Завантажити