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

The problems of optimization of using the computing resources of a distributed information system are considered. Mathematical statements of optimization problems have been made and efficient computational algorithms for solving problems based on the greedy choice strategy and using genetic algorith...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2018
Автори:	Tsegelyk, G. G., Krasniuk, R. P.
Формат:	Стаття
Мова:	Українська
Опубліковано:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018
Теми:	математичне моделювання оптимізація розподілені інформаційні системи жадібний алгоритм генетичний алгоритм
Онлайн доступ:	https://journal.iasa.kpi.ua/article/view/117692
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	System research and information technologies
Завантажити файл:

Репозитарії

System research and information technologies

_version_	1866302152655241216
author	Tsegelyk, G. G. Krasniuk, R. P.
author_facet	Tsegelyk, G. G. Krasniuk, R. P.
author_sort	Tsegelyk, G. G.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2019-01-17T13:29:35Z
description	The problems of optimization of using the computing resources of a distributed information system are considered. Mathematical statements of optimization problems have been made and efficient computational algorithms for solving problems based on the greedy choice strategy and using genetic algorithms have been proposed. For genetic algorithms for constructing solutions close to optimal, in binary and real coding problems, the computational efficiency of introducing self-training parameters of the algorithm that provided the correction of populations in the direction of better adaptability was proposed and investigated.
doi_str_mv	10.20535/SRIT.2308-8893.2018.2.07
first_indexed	2025-07-17T10:23:20Z
format	Article
fulltext	 Г.Г. Цегелик, Р.П. Краснюк, 2018 Системні дослідження та інформаційні технології, 2018, № 2 63 TIДC МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ УПРАВЛІННЯ І ТЕОРІЯ ІГОР УДК 519.7, 519.8 DOI: 10.20535/SRIT.2308-8893.2018.2.07 МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ОПТИМАЛЬНОГО ОБРОБЛЕННЯ ДАНИХ У РОЗПОДІЛЕНИХ ІНФОРМАЦІЙНИХ СИСТЕМАХ Г.Г. ЦЕГЕЛИК, Р.П. КРАСНЮК Анотація. Розглянуто задачі оптимізації використання обчислювальних ре- сурсів розподіленої інформаційної системи. Виконано математичні постановки оптимізаційних задач та запропоновано ефективні обчислювальні алгоритми побудови розв’язку задач, які ґрунтуються на стратегії «жадібного» вибору та використанні генетичних алгоритмів. Для генетичних алгоритмів побудови розв’язків, близьких до оптимальних, у задачах бінарного та дійсного коду- вання запропоновано та досліджено обчислювальну ефективність уведення параметрів самонавчання алгоритму, що забезпечує коригування популяцій у напрямі найкращої пристосованості. Ключові слова: математичне моделювання, оптимізація, розподілені інфор- маційні системи, «жадібний» алгоритм, генетичний алгоритм. ВСТУП Ефективне використання інформаційних систем потребує розв’язання сукуп- ності задач керування ресурсами системи та розподілу вхідних задач між вузлами. Метою керування є визначення ефективності розподілу задач і ре- сурсів з використанням різних критеріїв. Процес керування здійснюється динамічно (у процесі надходження задач та зміни конфігурації розподіленої інформаційної системи) спеціальною програмою — балансиром наванта- ження системи. Балансир навантаження керує потоком задач, що надходять у систему, розбиває їх на підзадачі та розподіляє між вузлами системи. Крім того, оброблення задач у вузлах інформаційної системи може вимагати до- даткових ресурсів (зміни ємності запам’ятовувальних пристроїв, реплікації баз даних, використання спеціалізованих програмних комплексів тощо). Ба- лансир навантаження має оптимізувати загальний час виконання завдань, а також мінімізувати вартість використання обчислювальних ресурсів. Зазвичай керування ресурсами інформаційної системи та потоком задач зводиться до багатокритеріальних задач оптимізації, розв’язки яких доволі складно отримати із застосуванням точних методів, і для отримання резуль- татів з достатньою для практики точністю застосовують низку евристичних підходів, що враховують специфіку предметної галузі, масштабованість Г.Г. Цегелик, Р.П. Краснюк ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 64 окремих задач у завданнях і таких, що використовують можливості паралель- ного виконання незалежних задач. Оскільки натепер не існує універсального за ефективністю методу, який може забезпечити оптимальний розподіл для довільного класу задач та сукупності доступних ресурсів, то для проектування розподіленої інформа- ційної системи необхідно використовувати у сукупності якомога більше ма- тематичних моделей та обчислювальних алгоритмів, що мають бути закріп- лені за окремими функціональними модулями балансира навантаження. Вибір відповідної моделі або обчислювального алгоритму має ґрунтуватися на динамічній природі та забезпечувати ефективне керування у режимі реа- льного часу. Мета роботи — дослідити проблему оптимізації використання обчис- лювальних ресурсів розподіленої інформаційної системи. Для досягнення поставленої мети потрібно:  сформулювати та дослідити математичні моделі оптимізації викори- стання обчислювальних ресурсів розподіленої інформаційної системи;  навести ефективні обчислювальні алгоритми пошуку наближеного розв’язку однокритеріальних та двокритеріальних оптимізаційних задач, що використовують стратегію «жадібного» вибору та генетичні алгоритми;  для генетичних алгоритмів побудови розв’язків запропонувати та дослідити обчислювальну ефективність уведення параметрів самонавчання алгоритму, що забезпечує коригування популяцій у напрямі найкращої при- стосованості. ОГЛЯД ЛІТЕРАТУРНИХ ДЖЕРЕЛ Для збереження оптимального стану обчислювальної системи використову- ється балансування навантаження для усіх її ресурсів. Перевага динамічного балансування ресурсами перед статичним полягає в тому, що інформаційна система не повинна мати інформацію про поведінку завдання під час його виконання до його запуску на оброблення. Крім того, за динамічного плану- вання бажаним є резервування ресурсів для отримання деякої впевненості в продуктивності ресурсів. Як наслідок, оптимальною стратегією оброблен- ня завдань за такого сценарію є мінімізація часу виконання вхідних завдань, що складаються з наборів задач. За динамічних сценаріїв керування за прийняття глобальних рішень щодо планування ресурсів може відповідати як один центральний планува- льник, так і декілька розподілених планувальників. Вибір центрального пла- нувальника має перевагу у простоті реалізації, але цей варіант погано масш- табується, не є відмовостійким і зазвичай стає вузьким місцем для продуктивності системи. Наприклад, у праці [1] розглядається центральний метапланувальник, який використовує алгоритм зворотного заповнення (Backfill) для планування паралельного виконання завдань. У праці [2] до- сліджено повністю децентралізований, динамічний та ініційований відправ- ником алгоритм планування та балансування навантаження для розподі- лених обчислювальних середовищ, головною особливістю якого є використання інтелектуальної стратегії пошуку вузлів-партнерів, на які мо- жуть бути перенесені задачі. Якщо вся інформація про стан ресурсів і стан Математичне моделювання оптимального оброблення даних у розподілених … Системні дослідження та інформаційні технології, 2018, № 2 65 завдань відома, оптимально поєднати завдання відповідно до ресурсів мож- на з використанням деякої цільової функції, що забезпечує мінімізацію часу виконання завдань. Оскільки керування процесами у розподіленій інформаційній системі у загальному випадку є NP-повною задачею [3], то довести оптимальність ал- горитмів чи зробити певні раціональні припущення щодо оптимальності не завжди можливо. Тому у прикладних дослідженнях розглядаються субопти- мальні розв’язки, з яких виокремлюють такі категорії:  наближені алгоритми, що використовують формальні обчислювальні моделі замість отримання усього простору розв’язків та вибору з нього оп- тимального варіанта. Ці алгоритми виконують пошук прийнятного резуль- тату, близького до оптимального за метрикою, що дозволяє оцінити похибку обчислень;  евристичні методи, що є класом алгоритмів, які надають найбільш реалістичні припущення про апріорні знання щодо характеристик наванта- ження системи та процесів виконання завдань. Оцінки результатів, знайде- них за цими методами, зазвичай ґрунтуються на числових експериментах над тестовими даними або на моделюванні. Найбільш популярними у дослі- дженнях є економічні підходи [4–6] та евристики, що ґрунтуються на при- родних процесах: генетичний алгоритм (GA – Genetic Algorithm) [7–9], імітаційний відпал (SA — Simulated Annealing) [10, 11], заборонений пошук (TS — Taboo Search) [10] та комбінована евристика [12]. ОПТИМІЗАЦІЯ ВИКОРИСТАННЯ ОБЧИСЛЮВАЛЬНИХ РЕСУРСІВ РОЗПОДІЛЕНОЇ ІНФОРМАЦІЙНОЇ СИСТЕМИ Нехай необхідно розподілити m задач серед n комп’ютерів розподіленої інформаційної системи (комп’ютери можуть мати неоднакову потужність). Задається план за часом та продуктивністю кожного комп’ютера системи:  iT , mi ,1 − час активності кожного вузла системи, що є важливою характеристикою розподілених обчислень, які працюють за схемою «оплата за використання»;  на кожному j-му комп’ютері системи має бути виконано не менше jC задач. Необхідно скласти такий план роботи вузлів системи, щоб забезпечити мінімальні витрати на оброблення пакета задач, якщо відомі час виконання кожної j-ї задачі на i-му комп’ютері системи — продуктивності ij та вар- тість одиниці машинного часу ijp , що витрачається на оброблення та транс- портування j-ї задачі до i-го вузла розподіленої системи. Інакше кажучи, потрібно визначити час роботи i-го комп’ютера з оброблення j-ї задачі в i-му вузлі мережі ijx , щоб забезпечити мінімальні витрати на оброблення пакета задач за дотримання обмежень на час роботи вузлів мережі та задану мінімальну кількість задач ,jC які обробляються у вузлах. За умовою пакет задач обробляється за заданий час }{max ,1 i mi T  , тому це обмеження можна подати так: Г.Г. Цегелик, Р.П. Краснюк ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 66 i n j ij Tx  1 , mi ,1 . (1) Обмеження за заданою мінімальною кількістю задач, які можуть бути оброблені у вузлі, виглядає таким чином: j m i ijij Cx  1 , nj ,1 . (2) Ураховуючи невід’ємність змінних 0ijx , можна сформувати як одно- критеріальну оптимізаційну задачу — пошук мінімуму витрат на оброблен- ня пакета підзадач для цільової функції     m i n j ijijij xpxF 1 1 min})({ , (3) так і двокритеріальну — пошук мінімуму цільової функції (3) з умовою мі- німізації загального часу оброблення пакета задач: }{max ,1 i mi T  . (4) Задачу поставлено так, щоб витратити ввесь відведений час (за потреби мінімізувавши його) роботи комп’ютерів на оброблення пакета задач, але кількість розв’язаних задач на кожному комп’ютері системи не повинна бу- ти меншою за jC . У деяких випадках можна послабити умову (2), тобто накласти обме- ження на максимально допустиму кількість задач, які можуть бути обробле- ні у вузлі: j m i ijij Cx  1 , nj ,1 . (5) Оптимізаційні моделі (1)–(5) стосувалися випадку, коли розподілена система розв’язує пакет незалежних задач. Розглянемо ситуацію, коли у ро- зподіленій інформаційній системі має бути розв’язана задача, що складаєть- ся з m різних підзадач, які допускають паралельне виконання у n вузлах сис- теми. Через неоднорідність комп’ютерів системи продуктивність виконання j-ї підзадачі неоднакова і дорівнює ijp . Кожен i-й комп’ютер має максима- льний сумарний ресурс часу для оброблення m задач, що дорівнює iT . По- трібно максимізувати розв’язок задач, що за сутністю еквівалентно забезпе- ченню мінімізації дисбалансу, який виникає через затримання оброблення задач на комп’ютерах системи. Необхідно визначити витрати часу на оброблення j-ї задачі на i-му вуз- лі системи, які не перевищують за сумою часові ресурси i-го вузла і забез- печують максимальну кількість оброблених задач. Нехай ijx — час, необхідний для розв’язання задачі j на комп’ютері i. Тоді загальна кількість задач, які можуть бути розв’язані на i-му комп’ютері системи, становить   n i ijij xp 1 , mj ,1 . Математичне моделювання оптимального оброблення даних у розподілених … Системні дослідження та інформаційні технології, 2018, № 2 67 Оскільки кожна задача складається з різних підзадач, наявних в одному екземплярі, то кількість підзадач, які може обробити інформаційна система, повинна дорівнювати кількості задач, якщо загальна їх кількість є мінімаль- ною: min 1   n i ijij xp , mj ,1 . (6) Умова задачі (6) установлює обмеження на час, який використовує ву- зол i . Таким чином, математичну модель можна подати в такому вигляді: i m j ijx  1 , ni ,1 ; (7) 0ijx , ni ,1 , mj ,1 . (8) Модель (6)–(8) є нелінійною, тому її можна звести до лінійної форми за допомогою перетворення, увівши в розгляд кількість розв’язаних задач          mjxpxC n i ijijij ,1,min)}({ 1 , (9) Виразу (9) з математичної точки зору еквівалентне таке формулювання: максимізувати )}({)}({ ijij xCxF  за обмежень 0)}({ 1   ij n i ijij xCxp , mj ,1 (10) та задач (7), (8). ОПТИМАЛЬНЕ ВИКОРИСТАННЯ КОМП’ЮТЕРІВ РОЗПОДІЛЕНОЇ МЕРЕЖІ ЗА ПАРАЛЕЛЬНОГО РОЗВ’ЯЗАННЯ ЗАДАЧ Нехай n — кількість доступних вузлів розподіленої інформаційної системи; m — загальна кількість задач, що допускають паралельне виконання у вуз- лах інформаційної системи; ij — час, потрібний для розв’язування i-ї зада- чі у вузлі j; jT — час, протягом якого можна використовувати обчислю- вальні потужності j-го вузла; ijc — затрати на розв’язання i-ї задачі в j-му вузлі інформаційної системи; }1,0{ijx , де 1 відповідає випадку розв’язання i-ї задачі в j-му вузлі, а нуль — у противному випадку. Тоді задача оптималь- ного використання обчислювальних потужностей розподіленої інформацій- ної системи полягає у такому розподілі задач між вузлами системи, щоб за- безпечити одночасно мінімальний час розв’язання усіх обчислювальних задач та мінімальні затрати на їх розв’язування. Математична модель задачі є такою:     m i n j ijijji xxF 1 1 min)}({ ;     m i n j ijijjik xcxE 1 1 min)}({ (11) за умов: j m i ijij x  1 , nj ,1 ; 1 1   n j ijx , mi ,1 ; }1,0{ijx , mi ,1 , nj ,1 .(12) Г.Г. Цегелик, Р.П. Краснюк ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 68 Оскільки розглянуті вище оптимізаційні задачі характеризуються вели- кою розмірністю, то застосовувати точні методи до побудови їх розв’язків недоцільно через значні часові втрати. Задовільні для практичного викорис- тання результати можна отримати, застосувавши евристичні алгоритми, зо- крема такі, як «жадібні» та генетичні, що дають наближений розв’язок по- ставленої задачі. СТРАТЕГІЯ «ЖАДІБНОГО» ВИБОРУ ЗА ОПТИМІЗАЦІЇ ОБЧИСЛЕНЬ У РОЗПОДІЛЕНИХ ІНФОРМАЦІЙНИХ СИСТЕМАХ «Жадібні» алгоритми [13–16] є інтуїтивними евристиками, у яких на кож- ному кроці приймається найбільш вигідне для цього кроку рішення, без урахування того, що відбувається на наступних кроках пошуку. Опишемо загальну схему алгоритму для сформульованих вище матема- тичних моделей (1)–(5) і (7)–(10), яка використовує ідею «жадібного» ви- бору. Позначимо: )( * ijxX — множина допустимих планів вихідної задачі, для яких * ijij xx  ; },1,,1{ mjniI  — множина індексів змінних; 00I — множина індексів змінних, яким процедурою «жадібного» вибору присвоєні нові значення. Алгоритм. Крок 0. Покладемо XX 00 , 00I Ø і виберемо початковий допусти- мий план 00 00 12 0 11 0 ),...,,( Xxxxx nm  . Для кожної з mn змінних знаходимо межі R ijij L ij xxx  такі, що 00 00 12 0 11 0 ),...,,...,,( Xxxxxx nmij  для всіх ijx , R ijij L ij xxx  . Межі нерівностей можуть задаватись наближено. Нехай сформовано множини klI та XX kl  . Крок 1. Якщо IIkl  , то всі змінні набули нових значення. Тобто по- будовано допустимий вектор x , який береться за наближений розв’язок. В іншому випадку переходимо до кроку 2. Крок 2. Для klIIji \),(  знаходимо           })({minmax),( \),( 00 ij xxxIIji xFji R ijij L ijkl , де      .),(, ;,,\),(, * 0 , klkl klklRL kl Ilkx jlikIIlkx x Покладемо ,min 000000 00 * Fx R jiji L ji xxx ji   ),( * 1,1 00 jikllk xXX   1,1 lkI }),({ 00 jiIkl  і переходимо до кроку 1. Для зменшення похибки наближеного розв’язку, отриманої з викорис- танням цього алгоритму, пропонується процедура покращення результату. Зокрема, припускатимемо, що змінні вектора x пронумеровані в послідов- ності отримання значень у «жадібному» алгоритмі. Математичне моделювання оптимального оброблення даних у розподілених … Системні дослідження та інформаційні технології, 2018, № 2 69 Алгоритм покращення розв’язку. Як початковий план беремо розв’язок, отриманий за «жадібним» алго- ритмом. Покладемо )}.(),...,2,1(),1,1{( mnM  , )1,1(),( qp . Крок 1. Вибираємо ще не опрацьовану змінну 0pqx з мінімальними індексами Mqp ),( і підбираємо значення 0 pq , на яке необхідно змен- шити величину pqx . Крок 2. Знаходимо змінну rsx , pr  , qs  і величину 0rs , на яку можна зменшити значення rsx , не порушуючи допустимості плану та збільшивши при цьому цільову функцію. Для цього pq та rs повинні задовольняти умову ,...),...,(...,,...),...,(..., rsrspqpqrspqpq xxFxxF  . Після закінчення кроку 2 незалежно від того, знайдена чи ні змінна rsx , покладемо )},{(\ qpMM  і переходимо до наступного значення із множи- ни M і повертаємося до кроку 1. Процес припиняється, коли всі змінні у початковому плані будуть переглянуті ( M ). Як показали результати числових експериментів (табл. 1), середня по- хибка наближеного розв’язку порівняно з точним, отриманим методом пов- ного перебирання, знижується від 20% до 5% із застосуванням алгоритму покращення розв’язку. Т а б л и ц я 1 . Оцінка точності використання «жадібного» алгоритму та алгоритму покращення розв’язку в задачах (1–5) і (7)–(10) у відсотках Розмірність задачі Величина середньої похибки «жадібного алгоритму» задачі (1)–(5) Величина середньої похибки алгоритму покращення розв’язку задачі (1)–(5) Величина середньої похибки «жадібного алгоритму» задачі (7)–(10) Величина середньої похибки алгоритму покращення розв’язку задачі (7)–(10) 5,10  nm 15,2 3,9 16,7 4,2 5,0.18  nm 17,4 4,8 18,9 5,4 6,0.28  nm 21,9 5,1 22,3 5,8 СТРАТЕГІЯ ВИБОРУ РОЗПОДІЛУ РЕСУРСІВ В ІНФОРМАЦІЙНИХ СИСТЕМАХ, БЛИЗЬКОГО ДО ОПТИМАЛЬНОГО, З ВИКОРИСТАННЯМ ГЕНЕТИЧНИХ АЛГОРИТМІВ Генетичні алгоритми (Genetic Algorithms) є варіантами еволюційних методів пошуку, за якими створюється популяція елементів (особин), де в задачі оптимізації кожна особина відповідає одному з можливих розв’язків. Для пошуку найкращого розв’язку використовується цільова функція або пов’язана з нею функція пристосування, значення якої показують, наскільки особина відповідає розв’язку задачі. Для забезпечення процесу еволюційно- Г.Г. Цегелик, Р.П. Краснюк ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 70 го пошуку до початкової популяції застосовуються основні генетичні опе- рації (селекції, схрещування, мутації та клонування), за результатами яких генерується нова популяція за допомогою додавання нових елементів з кра- щими показниками цільової функції або функції пристосування. Генетичні алгоритми поділяють на дві групи: генетичні алгоритми з бі- нарним кодуванням [17, 18] та генетичні алгоритми з дійсним кодуванням [19]. Перша група використовує двійкову систему числення для кодування розв’язків на множині допустимих значень. Це забезпечує високу ефектив- ність пошуку екстремального значення на множині допустимих розв’язків, що досягається використанням теореми про схеми [18]. Друга група виникла як результат відмови від ідеї кодування, тобто розв’язок в особині подається у вигляді набору дійсних чисел. У цьому ви- падку реалізація алгоритмів змінюється, а операції кодування–декодування відсутні. Далі пропонується реалізація генетичних алгоритмів за двома підхода- ми, що зумовлюється структурами математичних моделей. Підхід 1 — для задач бінарної оптимізації Крок 1. Формування початкової популяції. 1. Задається номер популяції 0np , максимальна кількість популяцій pmax, номер ітерації 0itern . 2. Задається розмір популяції q і випадковим чином формується почат- кова популяція розміру q. Для цього за допомогою рівномірного розподілу генерується q матриць розміру nm (наприклад, для задачі (11)–(12)) — особин популяції, елементи яких є випадкові значення з одиничного відрізка ).1,0( Однак усі елементи матриці мають бути цілими числами з множини }.1,0{ Тому в роботі пропонується вводити матрицю самонавчання алгорит- му }{ ij , що буде засобом цілеспрямованого впливу на характеристики пошуку, де елементи цієї матриці спочатку також розраховуються випадко- вим чином з відрізка )1,0( із застосуванням рівномірного розподілу. Заува- жимо, що за такого підходу до кодування розв’язку особиною популяції є матриця, стовпці якої є хромосомами особини. 3. Для кожної матриці — особини з популяції перед розрахунком ці- льової функції — застосовуватиметься процедура дискретизації: якщо зна- чення елемента матриці менше або дорівнює відповідному значенню матри- ці коригування, то значення зменшується до нуля, у противному випадку — зростає до одиниці. Якщо за умовою обмежень оптимізаційної задачі тільки одне значення в стовпці (хромосомі) матриці популяції має дорівнювати одиниці, то збільшується до одиниці тільки перше значення стовпця, що є більшим від відповідного значення елемента матриці самонавчання. 4. Для кожної дискретизації матриці з популяції розраховується зна- чення цільової функції (або функції пристосування) і перевіряється задово- лення додаткових обмежень, сформованих в оптимізаційній моделі. Якщо у сформованій популяції відсутні варіанти, що задовольняють обмеження оптимізаційної моделі, то популяція має бути перестворена заново. Крок 2. Селекція. Особини для схрещування пропонується обирати ві- дповідно до стратегії панміксії — випадкового рівномірного вибору двох батьківських особин — двох матриць з популяції. Математичне моделювання оптимального оброблення даних у розподілених … Системні дослідження та інформаційні технології, 2018, № 2 71 Крок 3. Схрещування — формування нових нащадків у популяції. Для формування нащадків пропонується застосування одноточкового та багато- точкового схрещування. За першого варіанта кожна пара стовпців (хромо- сом) матриць батьків випадково розривається в одній точці і формуються два нові стовпці матриць нащадків з використанням двох частин хромосоми кожної батьківської особини: перший нащадок отримує, наприклад, кожну верхню частину вектора-стовпчика першого батька і нижню другого, тоді як другий нащадок — навпаки. За другого варіанта схрещування випадково вибираються дві або біль- ше точок розриву для кожної пари хромосом з матриць батьків, і нащадки отримають нові хромосоми, що складатимуться із сегментів, розміщених між цими точками. Зауважимо, що варіант вибору кількості сегментів роз- биття також визначається випадковим чином для кожної нової популяції Результатом цього кроку є два нащадки, що отримуються з викорис- танням вибраних на другому кроці алгоритму батьківських особин. Крок 4. Мутація — перетворення хромосоми, що випадково змінює один або декілька з її генів. Застосовується для підтримання різноманітності хромосом у популяції. У роботі пропонується для мутації використовувати оператор інверсії, за яким кожен стовпець (хромосома) матриці особини випадково ділиться на дві частини, які потім обмінюються місцями — нижня частина стає верх- ньою і навпаки. Як наслідок, результатом цього кроку є два нащадки-мутанти, що були отримані застосуванням оператора мутації до двох нових особин, отриманих на третьому кроці алгоритму. Крок 5. Формування нової популяції. З отриманих на попередньому кроці особин вибирається одна, результат застосування якої до цільової фу- нкції є найкращим. Вона замінить у вихідній популяції особину, що має найгіршу пристосованість. Зауважимо, що значення пристосовуваності об- раховується з використанням матриці самонавчання алгоритму за схемою, наведеною на кроці 3. Далі перевіряються умови:  якщо qitern  , то покласти 1 iternitern і перейти до кроку 2;  якщо qitern  , то покласти 1 npnp і перейти до кроку 6. Крок 6. Перевірка умови завершення роботи генетичного алгоритму. Умовою завершення роботи генетичного алгоритму є формування заданої кількості популяцій np pmax:  якщо умову не виконано, то покладаємо 1itern і переходимо до кроку 2. Уточнюється матриця самонавчання алгоритму. Для цього значення матриці  обраховуються за формулою          ,1)/1(1 ;1)/1(0),/1( ;0)/1(,0 10 1010 10 FF FFFF FF ij ijij ij ij де знак плюс вибирається для оптимізаційних задач на максимум, мінус — для задач пошуку мінімуму цільової функції. Значення 1F — найкраще зна- чення функції пристосовуваності для поточного покоління популяції; 0F — відповідно найкраще значення функції пристосовуваності для попереднього покоління. Очевидною є вимога побудови двох поколінь популяцій перед Г.Г. Цегелик, Р.П. Краснюк ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 72 застосуванням цієї процедури уточнення для матриці самонавчання. Уве- дення такої залежності робить процес самонавчання генетичного алгоритму більш чутливим до змін якості розв’язку. Дійсно, за малих змін функції при- стосовуваності значення елементів матриці змінюються незначно і навпаки;  якщо умову завершення роботи виконано, то як розв’язок (наближе- ний) вибираємо особину з найбільшою пристосованістю з поточної популя- ції, застосувавши процедуру дискретизації (із кроку 3). Як показали проведені числові експерименти побудови розв’язку задачі (11)–(12), уведення у генетичний алгоритм процедури самонавчан- ня алгоритму дозволило у середньому зменшити кількість поколінь при фо- рмуванні популяцій на п’ятнадцять відсотків, а кількість задач, для яких розв’язок не був знайдений за десять тисяч поколінь популяцій, зменшився на п’ять відсотків (табл. 2). Таблиця 2. Оцінка точності використання генетичного алгоритму в задачі (11)–(12) з урахуванням процедури самонавчання алгоритму Функція пристосу- вання (13) Середня кількість поколінь генетичного алгоритму без самонавчання Кількість задач, розв’язків для яких не було знайдено за десять тисяч поколінь за алгоритмом без самонавчання Середня кількість поколінь генетичного алгоритму із самонавчанням Кількість задач, розв’язків для яких не було знайдено за десять тисяч поколінь за ал- горитмом із са- монавчанням 1 1220 11 1040 10 2 1300 21 1110 19 3 1450 8 1230 7 4 1180 45 1000 40 Функція пристосування визначалася такими залежноcтями: 1) })({ 1000 })({ })({ ij xF ijp xE xF ij  ; 2) })({ })({ })({ ij xF ijp xE e xF ij  ; 3) })({ })({ })({ ij ij ijp xE xF xF  ; 4) })({ })({ })({ ijxE ij ijp e xF xF  , де вирази для функцій })({ ijxF та })({ ijxE наведено у формулі (11). Підхід 2 — для задач оптимізації з дійсними розв’язками Крок 1. Формування початкової популяції. 1. Як і для задачі бінарної оптимізації задається номер популяції 0np , максимальна кількість популяцій pmax, номер ітерації 0itern . 2. Задається розмір популяції q і випадковим чином формується почат- кова популяція розміру q. Для цього за допомогою рівномірного розподілу генерується q матриць }{ 0 ijx розміру nm (наприклад, для задачі (1)–(3)) — особин, елементи яких є випадковими значеннями з одиничного відрізка ]1,0[ . Із використанням лінійного перетворення кожне значення елемента Математичне моделювання оптимального оброблення даних у розподілених … Системні дослідження та інформаційні технології, 2018, № 2 73 матриці відображається на відповідний проміжок ],[ ijij  : ijx ijijijij x  0)( , коли, наприклад, за умовою (1) 0ij , iij T . 3. Обчислюється значення функції пристосування для кожної матриці }{ ijx — особини популяції і перевіряється задоволення додаткових обме- жень, що сформовані в оптимізаційній моделі. Якщо у сформованій популя- ції немає варіантів, що задовольняють обмеження оптимізаційної моделі, то популяція має бути перестворена заново. Крок 2. Селекція. Особини для схрещування, як і у випадку бінарної оптимізації, пропонується обирати із застосуванням стратегії панміксії — випадкового рівномірного вибору двох батьківських особин — двох мат- риць з популяції. Крок 3. Схрещування — формування нових нащадків у популяції. Для формування нащадків пропонується застосування кросоверу, що імітує двійковий [20], коли нащадки формуються з особин батьків за формулою ])1()1[( 2 1 2 1 1 1 1 p ij p ij c ij xxx  ; ])1()1[( 2 1 2 2 1 2 2 p ij p ij c ij xxx  , де }{ 1p ijx , }{ 2p ijx — батьківські особини; }{ 1c ijx , }{ 2c ijx — матриці нащадків. Значення r , 2,1r обчислюються за формулою             , 2 1 ,))1(2( ; 2 1 ,)2( 1 1 1 1 uu uu r де значення u обирається випадковим чином з інтервалу )1,0( на кожній ітерації алгоритму. Значення  за працею [20] має належати інтервалу ]5,2[ . Надалі, як і за варіантом бінарної оптимізації, пропонується засто- совувати підхід самонавчання алгоритму, тобто змінювати коефіцієнт схре- щування  відповідно до кращого пристосування популяції. Тобто, зафік- сувавши на початку формування першої популяції деяке початкове значення  з інтервалу ]5,2[ , для кожної наступної, починаючи з другої, буде засто- совуватися схема самонавчання алгоритму         ,5)/1(5 ;5)/1(2),/1( ;2)/1(,2 10 1010 10 FF FFFF FF (13) де, як і раніше, знак плюс вибирається для оптимізаційних задач на макси- мум, знак мінус — для задач пошуку мінімуму цільової функції. Значення 1F — найкраще значення функції пристосовуваності для поточного поко- ління популяції, 0F — відповідно найкраще значення функції пристосову- ваності для попереднього покоління. Очевидно, що за такого вибору оператора схрещування значення мат- риць особин-нащадків також будуть задовольняти обмеження відповідної Г.Г. Цегелик, Р.П. Краснюк ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 74 оптимізаційної задачі, якщо координати батьківських особин також задово- льняли ці обмеження. Крок 4. Мутація. У роботі пропонується для мутації використовувати випадкову мутацію: випадковим чином вибирається декілька елементів ко- жної матриці нащадків і їх значення замінюються випадковим чином на нові за схемою формування особини 1.2. Як наслідок, результатом цього кроку є два нащадки-мутанти, що були отримані застосуванням оператора мутації до двох нових особин, отриманих на третьому кроці алгоритму. Крок 5. Формування нової популяції. З отриманих на попередньому кроці особин вибирається одна, результат застосування якої до цільової фу- нкції є найкращим. Вона замінить у вихідній популяції особину, що має найгіршу пристосованість. Далі перевіряються умови:  якщо qitern  , то покласти 1 iternitern і перейти до кроку 2;  якщо qitern  , то покласти 1 npnp і перейти до кроку 6. Крок 6. Перевірка умови завершення роботи генетичного алгоритму. Умовою завершення роботи генетичного алгоритму є формування заданої кількості популяцій np pmax:  якщо умову не виконано, то покладаємо 1itern і переходимо до кроку 2. При цьому відбувається процедура (13) самонавчання алгоритму — уточнення коефіцієнта схрещування  ;  якщо умову завершення роботи виконано, то як розв’язок (наближе- ний) вибираємо особину з найкращою пристосованістю з поточної популя- ції. Як наслідок, модифікація генетичного алгоритму — уведення парамет- рів самонавчання алгоритму — забезпечує коригування популяцій у напрямі найкращої пристосованості. Тобто рівноймовірний процес генетичного ал- горитму отримує властивість пам’яті, що зменшує кількість генерацій поко- лінь популяцій для досягнення необхідної точності результату. ВИСНОВКИ Інтеграція інформаційних та обчислювальних ресурсів у єдине середовище та організація ефективного доступу до них є одним з основних напрямів ро- звитку сучасних інформаційних технологій. На перший план виходить про- блема ефективного використання обчислювальних ресурсів кожного вузла мережі для вирішення складних наукових, виробничих і технологічних за- вдань. Тому одним з актуальних завдань сьогодення є ефективне керування обчислювальними ресурсами у розподіленому середовищі. Зростання кіль- кості ресурсних центрів, що складають розподілену інфраструктуру, за від- сутності або низької оптимальності підсистеми планування, яка забезпечує керування потоком задач, не тільки знижує ефективність використання усієї розподіленої інфраструктури, але й може зробити беззмістовним її створен- ня. Тому розширення класу математичних моделей та інструментарію чис- лових методів, які можуть бути залучені у комп’ютерні системи адміністру- вання розподілу ресурсів, є актуальною науковою проблемою, що і Математичне моделювання оптимального оброблення даних у розподілених … Системні дослідження та інформаційні технології, 2018, № 2 75 зумовило значущість досліджень цієї роботи; здійснено побудову та дослі- джено математичні моделі оптимального оброблення даних у розподілених інформаційних системах. Побудовано наближені обчислювальні алгоритми з використанням процедури «жадібного» вибору. Для зниження обчислювальної похибки розв’язку, що отримується за сформованими алгоритмами, запропоновано процедуру покращення розв’язку, яка зменшує відносну обчислювальну по- хибку до рівня, прийнятного у прикладних дослідженнях. Наведено дві схеми розрахунку наближеного розв’язку задач оптиміза- ції за бінарного та дійсного кодування параметрів моделі. Запропоновано модифікацію генетичного алгоритму — уведення параметрів самонавчання алгоритму, що забезпечує коригування популяцій у напрямі найкращої при- стосованості. Тобто рівноймовірний процес генетичного алгоритму отримує властивість пам’яті, що зменшує кількість генерацій поколінь популяцій для досягнення необхідної точності. Як показали числові експерименти, уведен- ня в генетичний алгоритм процедури самонавчання алгоритму дозволило у середньому зменшити кількість поколінь у формуванні популяцій на два- дцять відсотків, а кількість задач, для яких розв’язок не був знайдений за десять тисяч поколінь популяцій, зменшився на п’ять відсотків. Як наслідок, сформульовані та досліджені математичні моделі оптимі- зації розподілу ресурсів та наближені методи розв’язання відповідних опти- мізаційних задач можуть бути покладені в основу створення програмних комплексів керування розподіленою комп’ютерною інфраструктурою, що можна розглядати предметом подальших досліджень. ЛІТЕРАТУРА 1. Sabin G. Scheduling of Parallel Jobs in a Heterogeneous Multi-Site Environment / G. Sabin, R. Kettimuthu // Job Scheduling Strategies for Parallel Processing (JSSPP’03): Proceedings of the 9th International Workshop (Seattle, WA, USA, June 24, 2003). — Springer, Lecture Notes in Computer Science, 2003. — Vol. 2862. — P. 87–104. 2. Arora M. A Decentralized Scheduling and Load Balancing Algorithm for Heteroge- neous Grid Environments / M. Arora, S.K. Das, R. Biswas // International Con- ference on Parallel Processing Workshops (ICPPW’02): Proceedings of Interna- tional Conference (Vancouver, British Columbia Canada, August 20–23, 2002). — IEEE Computer Society, 2002. — P. 499–505. 3. El-Rewini H. Task Scheduling in Parallel and Distributed Systems / H. El-Rewini, T. Lewis, H. Ali. — Prentice Hall, 1994. — 290 p. 4. Buyya R. The Grid Economy / R. Buyya, D. Abramson, S. Venugopal // Proceedings of the IEEE. — 2005. — Vol. 93, N 3. — P. 698–714. 5. Zhu Y. Incentive–based P2P Scheduling in Grid Computing / Y. Zhu, L. Xiao // Pro- ceedings of the 3rd International Conference on Grid and Cooperative Comput- ing (GCC2004), Wuhan, China, October 21–24, 2004. Springer, Lecture Notes in Computer Science, 2004. — P. 209–216. 6. Young L. Scheduling Architecture and Algorithms within the ICENI Grid Middle- ware / L. Young, S. McGough // Proceedings of UK e–Science All Hands Meet- ing. — Nottingham, UK: IOP Publishing Ltd., 2003. — P. 5–12. 7. You S.Y. Task Scheduling Algorithm in GRID Considering Heterogeneous Environ- ment / S.Y. You , H.Y. Kim // Proceedings of the International Conference on Г.Г. Цегелик, Р.П. Краснюк ISSN 1681–6048 System Research & Information Technologies, 2018, № 2 76 Parallel and Distributed Processing Techniques and Applications (PDPTA ‘04), June 21–24, 2004. — Nevada, USA: CSREA Press, 2004. — P. 240–245. 8. Kim S. A Genetic Algorithm Based Approach for Scheduling Decomposable Data Grid Applications / S. Kim, J.B. Weissman // Proceedings of the 2004 Interna- tional Conference on Parallel Processing (ICPP’04), Montreal, Quebec Canada, August 15–18, 2004). IEEE Computer Society, 2004. — P. 406–413. 9. Song S. Security–Driven Heuristics and A Fast Genetic Algorithm for Trusted Grid Job Scheduling / S. Song, Y. Kwok, K. Hwang // Proceedings of 19th IEEE In- ternational Parallel and Distributed Processing Symposium (IPDPS’05), Denver, Colorado USA, April 25–29, 2005. IEEE Computer Society, 2005. — P. 65–74. 10. Braun R. A Comparison of Eleven Static Heuristics for Mapping a Class of Inde- pendent Tasks onto Heterogeneous Distributed Computing Systems / R. Braun, H.Siegel // Journal of Parallel and Distributed Computing. — 2001. — Vol. 61, N 6. — P. 810–837. 11. Young L. Scheduling Architecture and Algorithms within the ICENI Grid Middle- ware / L. Young, S.McGough // Proceedings of UK e–Science All Hands Meet- ing, September 2003). — Nottingham, UK: IOP Publishing Ltd., 2003. — P. 5–12. 12. Abraham A. Nature’s Heuristics for Scheduling Jobs on Computational Grids / A. Abraham, R. Buyya, B. Nath // Proceedings of 8th IEEE International Confer- ence on Advanced Computing and Communications (ADCOM 2000), Cochin, India, December 14–16, 2000. IEEE Computer Society, 2000. — P. 45–52. 13. Ахо А.В. Построение и анализ вычислительных алгоритмов / А.В. Ахо, Д.Э. Хонкрофт, Д.Д. Ульман. — М.: Мир, 1979. — 380 c. 14. Ахо А.В. Структуры даных и алгоритмы / А.В. Ахо, Д.Э. Хонкрофт, Д.Д. Ульман. — М.: Издательский дом «Вильямс», 2003. — 426 с. 15. Новиков Ф.А. Дискретная математика для программистов / Ф.А. Новиков. — Спб.: Питер, 2011. — 526 с. 16. Сигал И.Х. Введение в прикладное дискретное программирование: модели и вычислительные методы / И.Х. Сигал, А.П. Иванова. — М.: Физматлит, 2002. — 320 с. 17. Chambers D.L. Practical Handbook of Genetic algorithms, Applications / D.L. Chambers. — Chapman and Hall; CRC Press, 2001. — 650 p. 18. Halland J.N. Adaption in natural and artificial systems / J.N. Halland. — Ann Arbor, Michigan: University of Michigan Press, 1975. — 726 p. 19. Michalewicz Z. Genetic algorithms, numerical optimization and constraints / Z. Michalewicz // Proceedings of the 6th Intern. Coference on Genetic Algo- rithms, 1995. — P. 151–158. 20. Deb K. Realcoded genetic algorithms with simulated binary crossover: Studies on multimodal and multiobjective problems / K. Deb, A. Kumar // Complex Sys- tems, 1995. — Vol. 9, N 6. — P. 431–454. Надійшла 12.02.2018
id	journaliasakpiua-article-117692
institution	System research and information technologies
keywords_txt_mv	keywords
language	Ukrainian
last_indexed	2025-07-17T10:23:20Z
publishDate	2018
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/ec/e30b87f757953ae4f1b534e4b3d0a5ec.pdf
spelling	journaliasakpiua-article-1176922019-01-17T13:29:35Z The mathematical modeling of optimal data processing in distributed information systems Математическое моделирование оптимальной обработки данных в распределенных информационных системах Математичне моделювання оптимального оброблення даних у розподілених інформаційних системах Tsegelyk, G. G. Krasniuk, R. P. mathematical modeling optimization distributed information systems greedy algorithm genetic algorithm математическое моделирование оптимизация распределенные информационные системы жадный алгоритм генетический алгоритм математичне моделювання оптимізація розподілені інформаційні системи жадібний алгоритм генетичний алгоритм The problems of optimization of using the computing resources of a distributed information system are considered. Mathematical statements of optimization problems have been made and efficient computational algorithms for solving problems based on the greedy choice strategy and using genetic algorithms have been proposed. For genetic algorithms for constructing solutions close to optimal, in binary and real coding problems, the computational efficiency of introducing self-training parameters of the algorithm that provided the correction of populations in the direction of better adaptability was proposed and investigated. Рассмотрены задачи оптимизации использования вычислительных ресурсов распределенной информационной системы. Выполнены математические постановки оптимизационных задач и предложены эффективные вычислительные алгоритмы построения решения задач, основанные на стратегии "жадного" выбора и использовании генетических алгоритмов. Для генетических алгоритмов построения решений, близких к оптимальным, в задачах бинарного и действительного кодирования предложена и исследована вычислительная эффективность введения параметров самообучения алгоритма, обеспечивающих коррекцию популяций в направлении наилучшей приспособляемости. Розглянуто задачі оптимізації використання обчислювальних ресурсів розподіленої інформаційної системи. Виконано математичні постановки оптимізаційних задач та запропоновано ефективні обчислювальні алгоритми побудови розв’язку задач, які ґрунтуються на стратегії "жадібного" вибору та використанні генетичних алгоритмів. Для генетичних алгоритмів побудови розв’язків, близьких до оптимальних, у задачах бінарного та дійсного кодування запропоновано та досліджено обчислювальну ефективність уведення параметрів самонавчання алгоритму, що забезпечує коригування популяцій у напрямі найкращої пристосованості. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018-06-20 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/117692 10.20535/SRIT.2308-8893.2018.2.07 System research and information technologies; No. 2 (2018); 63-76 Системные исследования и информационные технологии; № 2 (2018); 63-76 Системні дослідження та інформаційні технології; № 2 (2018); 63-76 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/117692/136903 Copyright (c) 2021 System research and information technologies
spellingShingle	математичне моделювання оптимізація розподілені інформаційні системи жадібний алгоритм генетичний алгоритм Tsegelyk, G. G. Krasniuk, R. P. Математичне моделювання оптимального оброблення даних у розподілених інформаційних системах
title	Математичне моделювання оптимального оброблення даних у розподілених інформаційних системах
title_alt	The mathematical modeling of optimal data processing in distributed information systems Математическое моделирование оптимальной обработки данных в распределенных информационных системах
title_full	Математичне моделювання оптимального оброблення даних у розподілених інформаційних системах
title_fullStr	Математичне моделювання оптимального оброблення даних у розподілених інформаційних системах
title_full_unstemmed	Математичне моделювання оптимального оброблення даних у розподілених інформаційних системах
title_short	Математичне моделювання оптимального оброблення даних у розподілених інформаційних системах
title_sort	математичне моделювання оптимального оброблення даних у розподілених інформаційних системах
topic	математичне моделювання оптимізація розподілені інформаційні системи жадібний алгоритм генетичний алгоритм
topic_facet	mathematical modeling optimization distributed information systems greedy algorithm genetic algorithm математическое моделирование оптимизация распределенные информационные системы жадный алгоритм генетический алгоритм математичне моделювання оптимізація розподілені інформаційні системи жадібний алгоритм генетичний алгоритм
url	https://journal.iasa.kpi.ua/article/view/117692
work_keys_str_mv	AT tsegelykgg themathematicalmodelingofoptimaldataprocessingindistributedinformationsystems AT krasniukrp themathematicalmodelingofoptimaldataprocessingindistributedinformationsystems AT tsegelykgg matematičeskoemodelirovanieoptimalʹnojobrabotkidannyhvraspredelennyhinformacionnyhsistemah AT krasniukrp matematičeskoemodelirovanieoptimalʹnojobrabotkidannyhvraspredelennyhinformacionnyhsistemah AT tsegelykgg matematičnemodelûvannâoptimalʹnogoobroblennâdanihurozpodílenihínformacíjnihsistemah AT krasniukrp matematičnemodelûvannâoptimalʹnogoobroblennâdanihurozpodílenihínformacíjnihsistemah AT tsegelykgg mathematicalmodelingofoptimaldataprocessingindistributedinformationsystems AT krasniukrp mathematicalmodelingofoptimaldataprocessingindistributedinformationsystems

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

Репозитарії

Схожі ресурси