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

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


ALGORITHMIC IMPROVEMENT OF GENETIC ALGORITHM FOR ODD QUANTITY OF HOMOGENEOUS DEVICES1Don State Technical Universities

In the given work the new approach to increase in accuracy of the decision of a homogeneous distributive problem for the systems consisting of odd quantity of devices, at the expense of stage-by-stage application of genetic algorithm is considered. Efficiency such strongly the approach depends on an amount of arrangements: than amount of handling arrangements, especially the best effects more are gained at application of the given approach. The offered expedient of the solution of distributive problems for an odd amount of arrangements by means of genetic algorithm is recommended for formulation of schedules for the intelligence systems consisting of an odd amount of processors on which the great many of jobs arrives.


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

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

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

    ?Балибердін Валерій Олексійович

    Центральний науково-дослідний інститут Міноборони РФ.

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

    141006, Московська обл., М Митищі.

    Тел .: +79162386854.

    Дружинін Михайло Олександрович Белевцев Андрій Михайлович

    .: +79037691788.

    Baliberdin Valeriy Alekseevich

    Central Scientific Research Institute of Ministry of Defenses of Russian Federation. E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    Moscow area, Mitishi, 141006, Russia.

    Phone: +79162386854.

    Drujinin Mihail Aleksandrovich Belevtsev Andrey Mihailovich

    Phone: +79037691788.

    681.3 + 681.5

    ОТ. Кобак, Д.В. Титов, В.І. Калюка, В.В. Слєсарєв

    Алгоритмічні ПОЛІПШЕННЯ ГЕНЕТИЧНОГО АЛГОРИТМУ

    ДЛЯ непарною кількістю ОДНОРІДНИХ ПРИСТРОЇВ

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

    ; ; .

    V.G. Kobak, D.V. Titov, V.I. Kalyuka, V.V. Slesarev

    ALGORITHMIC IMPROVEMENT OF GENETIC ALGORITHM FOR ODD QUANTITY OF HOMOGENEOUS DEVICES

    In the given work the new approach to increase in accuracy of the decision of a homogeneous distributive problem for the systems consisting of odd quantity of devices, at the expense of stage-by-stage application of genetic algorithm is considered. Efficiency such strongly the approach depends on an amount of arrangements: than amount of handling arrangements, especially the best effects more are gained at application of the given approach. The offered expedient of the solution of distributive problems for an odd amount of arrangements by means of genetic algorithm is recommended for formulation of schedules for the intelligence systems consisting of an odd amount of processors on which the great many of jobs arrives.

    The theory of the schedules; homogeneous distributive problems; genetic algorithms.

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

    - -

    .

    - -

    .

    Побудова оптимального плану (розкладу) відноситься до завдань NP-повним, тобто трудомісткість рішення розподільної задачі визначається як

    експоненті, як O (nm), де O - тимчасова асимптотична складність алгоритму, a n і m - цілі числа більше одиниці, що позначають кількість пристроїв і завдань, які ставлять розмірність розподільної задачі n х m. Дослідження задач теорії розкладів допомагає вивчити фундаментальні властивості практичних завдань і направлено на побудову більш ефективних алгоритмів .

    Завдання теорії розкладів для однорідних систем обробки інформації може бути сформульована таким чином. Є однорідна обчислювальні, n

    P = {V1, ---, pn}, на які надходить m незалежних завдань Q = {q, •••, qm}, що утворюють паралельну програму, причому відомо ча-

    j - t j -

    ми, де j = 1, m. У кожен момент часу окремий процесор обслуговує

    не більше одного завдання, яке не передається на інший процесор. Завдання складання розкладу зводиться до розбиття вихідного безлічі завдань на n непересічних підмножин, тобто Qi: Vi, j? [1, n] ^ QiOQj = 0 і

    n

    U Q = Q.

    i = 1

    , -

    ня завдань по процесорам, при якому час завершення T паралельної програми мінімально, тобто T = max Ti} ^ min, де T = ^ tj- завантаження

    1-i-n tj? Qi:

    г-го процесора (час закінчення виконання безлічі завдань Qi з Q, призначених на процесор pi, де i = 1, n) [1].

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

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

    Для отримання оптимального рішення однорідної розподільної заду. , NP- , -

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

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

    Базова схема роботи ГА наступна: на першому кроці формується початкова покоління, що складається з певної кількості особин; на другому кроці відбувається відбір особин і застосування операторів кросовера і мутації ГА із заданою веро-,; -

    ,

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

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

    Модифікації генетичного алгоритму. У статті [2] була запропонована

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

    [2]. -мірованія нового покоління називається турнір з батьком.

    У статті [3] було запропоновано декомпозиційний підхід до вирішення розподільних завдань з парною кількістю пристроїв. Суть даного підходу полягала в наступному: спочатку розподіляється т завдань за допомогою ГА на до процесорів, де к = п / 2, виходить до непересічних підмножини завдань,

    тобто аі22і ... ИЕК = о- Далі розподіляється кожна підмножина завдань Про}, О2, ---, Ок, застосовуючи ГА, на два процесори, в результаті виходить 2к = п непересічних підмножини завдань, тобто О11 і О12 = Оь ---, ОК1 і ОК2 = Ок, що утворюють розклад для п-процесорної обчислювальної

    системи, тобто О11 і О ^ і .-- і ОК1 і ОК2 = О. Дана модифікація показала

    [3] -

    .

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

    ня Гт ^ п =? г ^ / п. Потім розподіляються завдання за допомогою ГА по п устрій] = 1

    ствам. Обчислюється, наскільки завантаження кожного пристрою відрізняється від Гт; п, тобто Д7} = | Т - Гт; п |, де - завантаження г-го пристрою. Безліч завдань Оп, призначених на пристрій з самої мінімальної різницею Д7}, запам'ятовується, а всі інші завдання розподіляються за допомогою ГА по п -1 пристроїв. Потім також обчислюється Д7} і безліч завдань Оп -1, призначених на пристрій з самої мінімальної різницею Д7}, запам'ятовуються, а інші завдання розподіляються за допомогою ГА по п - 2 пристроїв і так далі. Дана послідовність дій виконується поки п Ф 2, потім за допомогою ГА розподіляють, О2

    О1 . , ,

    п- , . .

    Оп ^ оп - ^ ... ІАІ О2 = про.

    Експериментальне порівняння генетичних алгоритмів. В рамках дослідження ГА для непарної кількості пристроїв поставлені обчислювальні експерименти, що дозволяють зібрати статистику рішень для 3, 5 і 7 процесорних систем обробки інформації. Кількість завдань, які розподілялися між процесорами, задавалося 29, 113 і 229. В ході експериментів були випадковим чином згенеровані по 500 векторів завантаження, що містять завдання в діапазоні [25, 30] .Як ГА №1 обраний ГА з використанням турніру з батьком, а в якості ГА № 2 - ГА для непарної кількості пристроїв з використанням турніру з батьком. Для всіх використовуваних ГА було обрано такі фіксований: 50,

    500 ,

    кросовера становила 90%, а ймовірність мутації 10%. Отримані результати усереднювалися за кількістю експериментів, а також аналогічно усереднювалися за часом вирішення завдань (табл. 1).

    1

    п т Усереднене значення критерію Усереднений час вирішення завдань, мс

    ГА №1 ГА №2 ГА №1 ГА №2

    3 29 269,104 268,606 33,83 56,32

    113 1036,262 1036,190 128,50 197,30

    229 2099,552 2099,486 273,61 409,34

    5 29 164,512 163,576 33,80 95,75

    113 627,438 624,178 151,83 381,74

    229 1264,256 1261,096 328,25 830,39

    7 29 129,330 126,266 37,10 144,65

    113 453,422 446,472 167,30 587,53

    229 907,178 902,660 373,37 1244,77

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

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

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

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

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

    2. Нейдорф РА., Кобак ОТ., Титов ДМ. Порівняльний аналіз ефективності варіантів турнірного відбору генетичного алгоритму рішення однорідних розподільних завдань // Вісник ДДТУ. - 2009. - Т. 9. - № 3 (42). - С. 410-418.

    3. Титов ДМ. Модифікація генетичного алгоритму розподілу для парного кількіст-

    // . .- . . .

    - 2010. - № 1. - С. 3-6.

    . . ., . . .

    Кобак Валерій Григорович

    Донський державний технічний університет.

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

    344000,. - -,. , 1.

    .: 88632327953.

    Титов Дмитро В'ячеславович

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

    Калюка Володимир Іванович

    ().

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

    346418, м Новочеркаськ, вул. Отаманська, 36.

    Тел .: 88635220931.

    Слєсарєв Володимир Володимирович

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

    Kobak Valeriy Grigorevich

    Don State Technical Universities.

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

    1, Gagarina Street, Rosrov-on-Don, 344000, Russia.

    Phone: +78632327953.

    Titov Dmitriy Vjacheslavovich

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

    Kalyuka Vladimir Ivanovich

    Novocherkassk the Higher Military Command Communication School (Military Institute). E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    36, Atamanskay Street, Novocherkassk, 346418, Russia.

    Phone: +78635220931.

    Slesarev Vladimir Vladimirovich

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


    Ключові слова: Теорія розкладів / ОДНОРІДНІ РОЗПОДІЛЬНІ ЗАВДАННЯ / ГЕНЕТИЧНІ АЛГОРИТМИ / THE THEORY OF THE SCHEDULES / HOMOGENEOUS DISTRIBUTIVE PROBLEMS / GENETIC ALGORITHMS

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

    Завантажити