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

  • Математика

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


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


    Наукова стаття на тему 'Алгоритм виділення незалежних підмножин в графі на основі методів генетичного пошуку'

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

    ?681.3.06

    Л.А. Г Ладко, І. А. Болоцкова1

    АЛГОРИТМ ВИДІЛЕННЯ НЕЗАЛЕЖНИХ підмножини В графі НА ОСНОВІ МЕТОДІВ ГЕНЕТИЧНОГО ПОШУКУ

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

    , ,

    графа і т.д.

    Всі перераховані вище завдання ставляться до NP-повним завданням. Розробка нових підходів до вирішення всіх перелічених вище завдань представляє великий,,. , NP ,

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

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

    Нехай G = (X, U) - неорієнтований граф без петель, де X - безліч вершин графа, \ X \ = n, a U - безліч ребер, \ U \ = m. Якщо дві будь-які вершини підмножини X 'графа G = (X, U), X' cX, не суміжні, то воно називається внутрішньо стійким [1]. Підмножина щ cX графа G = (X, U) називається максимальним внутрішньо стійким підмножиною (МВУП) або незалежним підмножиною (НП), якщо додавання до не му будь-якої вершини xt е X робить його не внутрішньо стійким. Підмножина щ буде незалежним, якщо

    \ / ХГ о н (Гхг пщ = 0.

    Незалежні підмножини розрізняються за кількістю вхідних в них елементів. У довільному графі G можна виділити сімейство всіх НП виду W = {/, щ, ...

    , /}. Незалежні підмножини, що містять найбільшу кількість елементів, називаючи-.

    Існуючі методи розв'язання задачі виділення незалежних підмножин в графі можна розділити на кілька груп.

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

    Для подолання цих труднощів було розроблено ряд алгоритмів використовують різні евристики та методи поліпшення перебору. Одним з таких методів є метод систематичного перебору з рекурсією [2].

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

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

    ної вершини, і так надходять до тих пір, поки додавання вершин стане неможливим, а породжене безліч не стане незалежним безліччю. При цьому запам'ятовуються вершини, які вже використовувалися в процесі пошуку. Як і у,, кроки повернення якомога раніше, оскільки це обмежить розміри «непотрібної» частини дерева пошуку. Такого роду алгоритми мають складність порядку 0 (2п).

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

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

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

    ,

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

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

    , -, -

    .

    Вибір ефективної методики кодування рішень дозволяє прискорити процес пошуку за рахунок виключення можливих «нелегальних» (які не відповідають встановленим критеріям) рішень [5].

    У розробленому алгоритмі хромосома являє собою числову після,

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

    п (0) у (О) (1)

    Р +1

    П (О)

    <

    1 (1 ^

    п

    _2 V 1 2)

    (2)

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

    Н1:

    1 7 2 9 4 0 0 0 0

    рис.1

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

    F (H) = (lH) - max (3)

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

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

    При побудові схеми генетичного пошуку особлива увага приділяється , ,

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

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

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

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

    Батько 1: 12, 10 II 6 3 0 0 0 0 0

    Батько 2: 1 7 || 10 13 9 4 0 0 0

    1: 12, 10 II 1 7 13 9 4 0 0

    2: 1 7 II 12 10 6 3 0 0 0

    рис.2

    В алгоритмі також застосовується модифікований оператор. Схема виконання цього оператора наступна. Нехай заповнена частина хромосоми-батька дорівнює I1, а нульова 10. Випадково формується безліч вершин A, котрі належать до батьківської хромосомі, \ А \ є [1,10]. Ці вершини дописують в хромосому. Згенеруємо випадкове число п є [0, 11], і видалимо п генів від початку .

    (Рис. 3).

    : 12 10 6 3 0 0 0 0 0

    Після додавання генів: 12 10 6 3 7 9 11 0 0

    : 6 3 7 9 11 0 0 0 0

    рис.3

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

    В алгоритмі використовувалися спільно елітний і равновероятности оператора відбору. При цьому задається ймовірність елітного відбору Ре, а ймовірність равновероятного відбору обчислюється як Рр = 1 - Ре. Генерується випадкове число p е [0, 1]. Якщо р потрапляє в інтервал [0, Ре], то виконується елітний відбір, інакше виконується рівно можливих відбір. Такий підхід до організації відбору дозволяє управляти різноманітністю генетичного матеріалу і дає кращі результати, ніж при використанні будь-якого одного виду відбору. Структурна схема генетичних-

    . 4.

    Пояснимо роботу алгоритму. На першому кроці алгоритму вводяться початкові дані (вихідний граф О = (X, ^ і параметри ГА (ймовірності кросинговеру, мутації, елітного і равновероятного відбору; розмір популяції хромосом; коли)).

    Далі розраховується верхня і нижня оцінка числа внутрішньої стійко, .

    рис.4

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

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

    ЛІТЕРАТУРА:

    1. Харари Ф. Теорія графів. М .: Світ, 1973. 300 с.

    2. Новиков ФА. Дискретна математика для програмістів. СПб .: Пітер, 2000. 304 с.

    3. . . -

    ектировании із застосуванням САПР. М .: Радио и связь, 1990. 352 с.

    4. Курейчик В.М. Генетичні алгоритми. Монографія. Таганрог, ТРТУ, 1998. 242 с.

    5. Гладке Л.А., Болоцкова І.Л. Еволюційний підхід до вирішення Графова завдань. // Матеріали ХХЬУП науково-технічної конференції. Известия ТРТУ, № 1, 2002. С.84.

    УДК 681.32

    В.М. Курейчик, АЛ Гулевич, Л.А. Зінченко1

    ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ЕВОЛЮЦІЙНОГО ПРОЕКТУВАННЯ ЕЛЕКТРОННИХ ПРИСТРОЇВ НА ОСНОВІ ієрархічних КОНСТРУИРОВАНИЯ ЧІСЛЕННОАНАЛІТІЧЕСКІХ МОДЕЛЕЙ

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

    (),

    () ()-Ня [1].

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

    Синтез схемотехнік спрямований на створення нових варіантів елементів і пристроїв обчислювальної техніки та систем керування. Перший етап (структурний синтез) спрямований на створення структури проектованого об'єкта у вигляді графа в = (Б, 8), де Е - безліч елементів, що входять в схему, 8 - безліч зв'язків між елементами схеми. На другому етапі (параметричний синтез) проводиться пошук параметрів Х = {хьх2, ..., хр} спроектованої на першому етапі

    1 Робота виконана за підтримки РФФД, гранти №01-01-000-44, 02-01-01-275


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

    Завантажити