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

Анотація наукової статті з математики, автор наукової роботи - Кобак Валерій Григорович, Титов Дмитро В'ячеславович


THE GENETIC APPROACH TO REDUCTION OF THE OPERATING TIME OF EXACT ALGORITHM ROMANOVSKIY IN HOMOGENEOUS SYSTEMS

This paper gives the estimation of exact algorithm Romanovskiy at use as initial value of the top border of one updatings genetic algorithm. The given approach leads to sharp reduction of time of reception of the exact decision, especially for dual-processor computing systems.


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

  • Математика

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


    Журнал: Вісник Донського державного технічного університету


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

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

    ?УДК 681.3.681.5

    В.Г. Кобаки, Д.В. ТИТОВ

    Алгоритмічні ПІДХІД ДО ЗМЕНШЕННЯ ЧАСУ РОБОТИ ТОЧНОГО МЕТОДУ В ОДНОРІДНИХ СИСТЕМАХ

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

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

    Постановка задачі. Слід скласти розклад для п однорідних паралельних процесорів, на які необхідно розподілити m незалежних завдань [1], що утворюють паралельну програму. Математична постановка даного завдання наведена в [2], де також було відзначено, що при п > 2 дана задача відноситься до класу NP-повних.

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

    т

    потім обчислюється нижня межа (оцінка знизу) е ^ = X / п і верх-

    3 = 1

    т

    няя межа (оцінка зверху) гес = X * з. Вибираємо будь-яке число

    3 = 1

    г е, гес) і розглядаємо z-завдання, тобто знаходимо такий розподіл завдань по процесорам, при якому мінімальна загальна час виконання завдань Т < 2. Якщо вдається знайти рішення цього завдання, то z береться в якості нового значення верхньої межі, після чого процес повторюється. Якщо z-завдання рішення не має, то z береться в якості нового значення нижньої межі, і також процес повторюється. Для виділення наступних z-завдань рекомендовано в [3] брати полусумму верхньої і нижньої меж, тобто г = + гес) / 2. Процес повторюється, поки не буде

    знайдено оптимальне рішення, яке досягається при виконанні умови гес = Е81 + 1. Для вирішення z-завдання використовується метод гілок і меж з одностороннім обходом дерева варіантів. Передбачається, що завантаження кожного процесора не перевищує максимально допустимого завантаження z, тобто Т < г, де г = 1, п. Таким чином, сумарна завантаження процес-

    соров Tsum = X tj буде менше максимально допустимого завантаження про-

    j = 1

    цессора Tmax = z х n на величину sl = Tmax - Tsum. Завдання призначаються на процесори послідовно зі списку завдань, прагнучи, кожен раз призначити на процесор завдання з найбільшим часом виконання, при цьому обчислюється різниця si між максимально допустимої завантаженням процесорів і завантаженням i-го процесора, тобто st = z - Ti, причому st кожен раз віднімається з sl, і результат повинен протягом всього обчислювального процесу залишатися невід'ємним. Якщо результат стане негативним, то відбувається скасування останнього з призначень.

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

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

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

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

    Використання різних підходів до формування меж алгоритму Романовського. У стандартному алгоритмі Романовського для виділення наступних z-завдань рекомендовано брати полусумму верхньої і нижньої меж [3]. Як було зазначено вище, якщо z-завдання має рішення, то z береться в якості нового значення верхньої межі, інакше -нижній кордону. У статті [4] були запропоновані методи виділення наступних z-задач: послідовний спуск і прискорений спуск з кроком два.

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

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

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

    У статті [5] була запропонована модифікація ГА, яка була найкращою з розглянутих у статті інших модифікацій ГА. Дана модифікація полягала в тому, що при формуванні нового покоління використовувався турнірний відбір, в якому брала участь чергова особина (батьківська) і результуюча (нащадок), отримана в ході виконання операторів кросовера і мутації. Даний спосіб формування нового покоління будемо називати турнір з батьком. Модифікацію алгоритму Романовського, що використовує описаний генетичний алгоритм, будемо позначати як МАР [ГА (т.р.)].

    Були реалізовані генетичні алгоритми з використанням елі-тизма і турніру з батьком. У першому випадку була задана одна елітна особина. Алгоритм Романовського, який використовує даний генетичний алгоритм, будемо позначати як МАР [ГА (1ел.о., Т.р.)]. У другому випадку в якості елітної особини в початковому поколінні вибиралася особина, отримана з перетвореного рішення, що повертається метод СРМ. Алгоритм Романовського, який використовує даний генетичний алгоритм, будемо позначати як МАР [ГА (1ел.о. + СРМ, т.р.)].

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

    Для проведення експерименту були випадковим чином згенеровані 100 векторів завантаження, що містять завдання в діапазоні 25 ... 30, кожен з векторів вирішувалося МАР [ГА (т.р.)], МАР [ГА (1ел.о., Т.р.) ] і МАР [ГА (1ел.о. + СРМ, т.р.)]. Для виділення наступних пана завдань використовувалися полусумма верхньої і нижньої меж, послідовний спуск і прискорений спуск з кроком два. Число завдань т було фіксоване і дорівнювало 17. Для всіх використовуваних генетичних алгоритмів було обрано такі фіксовані параметри: число особин становило 50, умовою зупинки було поява в процесі вирішення більш 500 поколе-

    ний з кращого однаковою особиною, ймовірність кросовера становила 90%, а ймовірність мутації - 10%.

    Отримані результати усереднювалися за часом вирішення завдань,

    100

    тобто ТСР = X ti / 100, де ti - час знаходження рішення для / -го вектора

    I = 1

    завантаження.

    Результати першого обчислювального експерименту.

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

    ц 2800

    кількість процесорів

    | 1. МАР [ГА (т.р.)], Послідовний спуск | 2.МАР [ГА (т.р.)], Прискорений спуск

    | 3. МАР [ГА [т.р.)], Полусумма кордонів | 4.МАР [ГА (1ел.о., Т.р.)]. послідовний спуск

    | 5. МАР [ГА (1ел.о., Т.р.)], прискорений спуск | 6.МАР [ГА (1ел.о., т.р.)], Полусумма кордонів

    | 7.МАР [ГА [1ел.о. + СРМ.тр)], послідовний спуск | 8. МАР [ГА (1ел.о. + СРМ, т.р.)], прискорений спуск Е. МАР [ГА (1ел .про. + СРМ, т.р.)], полусумма кордонів

    Рис.1. Усереднений час вирішення алгоритмів для двох-трьох процесорів

    | 1. МАР [ГА (т.р.)], Послідовний спуск

    | 2. МАР [ГА (т.р.)], Прискорений спуск

    | З.МАР [ГА (т.р.)], Полусумма кордонів

    | 4.МАР [ГА (1ел.о., Т.р.)], послідовний спуск

    | 5. МАР [ГА (1ел.о., Т.р.)], прискорений спуск

    | 5. МАР [ГА (1ел.о, т.р.)], полусумма кордонів

    | 7. МАР [ГА (1ел.о. + СРМ, т.р.)], Послідовний спуск

    8. МАР [ГА (1ел.о. + СРМ, т.р.)], Прискорений спуск

    9.МАР [ГА (1ел.о. + СРМ, т.р.)], Полусумма кордонів

    кількість процесорів

    Рис.2. Усереднений час вирішення алгоритмів для чотирьох процесорів

    Другий обчислювальний експеримент. Для визначення, який із запропонованих модифікацій алгоритму Романовського: МАР [СРМ] або МАР [ГА (т.р.)] - є найкращим, було проведено ряд обчислювальних експериментів для 2-4-процесорних систем обробки інформації. Для проведення експерименту були випадковим чином згенеровані 100 векторів завантаження, що містять завдання в діапазоні 25.30. Для 2-процесорних систем число завдань становило 41 і 43, для 3-процесорних - 41, а для 4-процесорних - 19. Для генетичного алгоритму були обрані ті ж самі фіксовані параметри, що і в першому експерименті. Отримані результати усереднювалися за часом вирішення завдань.

    Результати другого обчислювального експерименту. Основні результати обчислювального експерименту відображені на ріс.З.

    кількість завдань

    | 1. МАР [СРМ], послідовний спуск

    | 2. МАР [ГА (т.р.)], Послідовний спуск

    кількість завдань

    | 1. МАР [СРМ], послідовний спуск

    | 2. МАР [ГА (т.р.)], Послідовний спуск

    а)

    б)

    кількість завдань

    | 1.МАР [СРМ], послідовний спуск

    | 2. МАР [ГА (т.р.)], Послідовний спуск

    в)

    Рис.3. Усереднений час вирішення алгоритмів для двох (а), трьох (б) і чотирьох (в) про-цесії-рів

    обчислювального експерименту, рис.3), можна зробити висновок, що Романовського, що використовує для

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

    Висновки. Модифікація алгоритму Романовського, яка використовує генетичний алгоритм з турнірним відбором для формування нового покоління без елітної особини і використовує для виділення наступних z-завдань послідовний спуск, працює більш ефективно, ніж розглянуті інші модифікації алгоритму Романовського, особливо для двопроцесорних обчислювальних систем, отже, її можна рекомендувати для використання складання точного розкладу для 2-4-процесорних обчислювальних систем.

    бібліографічний список

    1. Коффман Є.Г. Теорія розкладу і обчислювальні машини. / Е.Г.Коффман. - М .: Наука, 1987.

    2. Кобак В.Г. Дослідження роботи алгоритму Романовського з використанням облікових алгоритмів при формуванні верхньої межі / В.Г.Кобак, Д.В.Тітов // Системний аналіз, управління і обробка інформації: 1-й межвуз. зб. науч. ст. / ДДТУ; ТТІ ПФУ. - Ростов н / Д, 2007.

    3. Романовський І.В. Алгоритми рішення екстремальних задач. / І.В.Романовскій. - М .: Наука, 1977.

    4. Кобак В.Г .. Аналіз роботи алгоритму Романовського з використанням різних підходів до формування верхньої і нижньої меж / В.Г.Кобак, Д.В.Тітов // Зб. тр. МНК ММТТ-20. Т.2. Ярославль: ЯГТУ, 2007.

    5. Кобак В.Г. Аналіз підходів до поліпшення результатів роботи генетичного алгоритму при вирішенні однорідної мінімаксної задачі / В.Г.Кобак, Д.В.Тітов // Проблеми інформатики в освіті, управлінні, економіці і техніці // Зб. ст. VIlI Всерос. наук.-техн. конф. - Пенза, 2008.

    Матеріал надійшов до редакції 23.05.09.

    V.G.KOBAK, D.V.TITOV

    THE GENETIC APPROACH TO REDUCTION OF THE OPERATING TIME OF EXACT ALGORITHM ROMANOVSKIY IN HOMOGENEOUS SYSTEMS

    This paper gives the estimation of exact algorithm Romanovskiy at use as initial value of the top border of one updatings genetic algorithm. The given approach leads to sharp reduction of time of reception of the exact decision, especially for dual-processor computing systems.

    Кобаки Валерій Григорович (р.1961), докторант ДДТУ, кандидат технічних наук. Закінчив Новочеркаський політехнічний інститут (1983). Наукові інтереси: методи вирішення екстремальних завдань в однорідних обчислювальних системах.

    Автор понад 70 наукових праць.

    ТИТОВ Дмитро В'ячеславович (р.1981), аспірант ДДТУ. Закінчив магістратуру в ДДТУ (2005).

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

    Автор понад 8 наукових робіт.

    Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.


    Ключові слова: Теорія розкладів /ЗАВДАННЯ ПЛАНУВАННЯ /АЛГОРИТМ Романовський /ГЕНЕТИЧНИЙ АЛГОРИТМ /спискова АЛГОРИТМИ /ОБЧИСЛЮВАЛЬНИЙ ЕКСПЕРИМЕНТ /ВЕКТОР ЗАВАНТАЖЕННЯ

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

    Завантажити