ІНСТРУМЕНТАЛЬНІ ЗАСОБИ ДОСЛІДЖЕННЯ ЧАСОВОЇ ТА ФУНКЦІОНАЛЬНОЇ ЕФЕКТИВНОСТІ БІОНІЧНИХ АЛГОРИТМІВ РОЗВ'ЯЗКУ ЕКСТРЕМАЛЬНИХ ЗАДАЧ

Abstract

Розроблене інструментальне середовище для визначення часової та функціональної ефективності алгоритмів. Передбачені можливості дослідження ефективності алгоритмів на множині особливих «незручних» функцій, яку можливо змінювати та доповнювати. Виконані комп'ютерні експерименти з визначенням теоретичних засад, підготовчих заходів, реалізацією та аналізом отриманих результатів. Отримані залежності часової та функціональної ефективності зграйного алгоритму від кількості параметрів функцій, глобальний екстремум яких визначається, та параметрів зграйного алгоритму: розміру популяцій та кількості епох. У розробленому середовищі передбачена можливість дослідження інших біонічних алгоритмів. Ключові слова: часова ефективність, функціональна ефективність, біонічний алгоритм, комп'ютерний експеримент. Разработана инструментальная среда для определения временной и функциональной эффективности алгоритмов. Предусмотрены возможности исследования эффективности алгоритмов на множестве особых «неудобных» функций, которое можно изменять и дополнять. Выполнены компьютерные эксперименты, включая определение теоретических основ, подготовку, реализацию и анализ результатов. Получены зависимости временной и функциональной эффективности роевого алгоритма от количества параметров функций, глобальный экстремум которых определяется, и параметров роевого алгоритма: размера популяций и количества эпох. В разработанной среде предусмотрена возможность исследования других бионических алгоритмов. Ключевые слова: временная эффективность, функциональная эффективность, бионический алгоритм, компьютерный эксперимент. An instrumental environment for determining the time and functional efficiency of algorithms are developed. Abilities of studying the effectiveness of algorithms on a set of special "uncomfortable" functions, which can be changed and implemented are provided. Computer experiments are carried out, including the definition of theoretical foundations, preparation, implementation and analysis of the results. The dependency of the time and functional efficiency of the rouge algorithm on the number of parameters of functions whose global extremum is determined, and the parameters of the roaming algorithm: population size and number of epochs are obtained. In the developed environment, it is possible to study other bionic algorithms.

-

У представленій роботі для оцінки якості біонічних алгоритмів були запропоновані показники функціональної [10] та часової ефективності [11]. Функціональні можливості розробленого інструментального середовища Представлений у даній роботі інструментальний засіб призначений для дослідження будь-якого стохастичного алгоритму пошуку екстремуму функції. Такий алгоритм додається до вже існуючих у системі алгоритмів у призначеному для цього вікні. Алгоритм має бути представленій на мові Java та попередньо відлагоджений. Для опрацювання інструментальних засобів у систему доданий алгоритм PSO.

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

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

Рис. 3. Настройка експерименту та порівняльні графіки У результаті маємо порівняльні графіки та таблиці (приклад останніх на рис. 4)

Рис. 4. Приклад табличного представлення результатів Часова ефективність біонічних алгоритмів

Одна із суттєвих особливостей стохастичних біонічних алгоритмів – потреба в значних часових ресурсах. Виконавцем природних біонічних алгоритмів є значна кількість особин. У комп’ютерній реалізації маємо один обчислювальний механізм та значно складнішу задачу пошуку. Тому й виникає задача оцінки можливостей алгоритмів за часовими показниками.

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

Якщо існує декілька функціонально еквівалентних алгоритмів [11], то їх часову ефективність необхідно визначати за конкретними реалізаціями.

Час виконання алгоритму визначається функцією [11]: де v , t та x – відповідно об’єм, тип та значення вхідних даних;  – програмне середовище функціонування та створення виконуваного файлу; r – архітектура ЕОМ.

При наявності декількох функціонально еквівалентних алгоритмів слід порівнювати функції:

E1  f1(v,t, x, , r), E2  f2 (v, t, x, , r),..., En  fn (v, t, x, , r) . Для порівняння часової ефективності двох алгоритмів необхідно визначити[11]: 

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

Нехай V * – множина можливих значень об’єму даних, T * – множина можливих типів даних, X * – множина можливих значень даних, * – множина можливих програмних середовищ, R* – множина архітектур ЕВМ, на яких можлива реалізація алгоритмів. Тоді для порівняння часової ефективності альтернативних обчислювальних алгоритмів необхідно визначити ступінь переваги одного (і-го) алгоритму над іншим (j-им) на обмежених множинах, які є підмножинами вказаних вище множин V V * , T T * , X  X * ,   * , R  R* визначається як: SUPij | V ,T , X , , R  1      gij (v,t, x, , r) , gij (v,t, x, , r) 

N vV tT xX   rR

f j (v,t, x, , r)  fi (v,t, x, , r) max( fi (v,t, x, , r), f j (v, t, x, , r)) , ( 3 ) де N – загальна кількість доданків, gij – ступінь переваги i-го алгоритму над j-им при деякому виконанні, fi – час виконання i-го алгоритму.

Визначається також [11] область переваги одного (і-го) алгоритму над іншим (j-им): де hij – ознака переваги і-го алгоритму над j-им в точці

REGij | V ,T , X , , R  1      hij (v, t, x, , r) ,

N vV tT xX   rR 1, якщо x  0 hij (v,t, x, , r)  sign( fi (v,t, x, , r)  f j (v,t, x, , r)) , sign(x)   0, якщо x  0 .

( 1 ) ( 2 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) Слід зазначити, що множини V ,T , X , , R – дискретні. Виходячи з необмеженої кількості можливих вхідних даних X * , значення N є настільки великим, що практичне обчислення запропонованих показників не є можливим.

Оцінка S-показника. S-показник є статистичною оцінкою SUPij | V ,T , X , , R . За [11] S-оцінку ступені переваги i-го алгоритму над j-им визначимо як (%):

Sij | V ,T , X , ,T , R  S 100  1 N

 gijk (v,t, x, , r) 100 , N k1 де gijk – ступінь переваги i-го алгоритму над j-им ( 3 ) при k-му виконанні алгоритмів з випадковими значеннями v,t, x, , r із області   V T  X    R .

Там же [11] надане визначення довірчого інтервалу S-показника при коефіцієнті довіри  : | s  I | t2, 1 3

 ( k  S )2 , 6 k1 де I – точне значення S-показника, s – значення визначене за ( 6 ),  k – значення S-показника обчислене для кожної з трьох частин N / 3 вимірювань, t2, – табличне значення розподілу Стьюдента при коефіцієнті довіри  .

Оцінка R-показника. Оскільки вирази для обчислення SUPij та REGij в ( 3 ) та ( 4 ) відрізняються тільки функцією під знаком суми, R-показник обчислюється аналогічно S-показнику. Випадковим чином обирається N точок в області   V T  X    R . Доцільно взяти ті самі точки, що і для обчислення Sпоказника.

Використовуючи описану вище методику й позначивши, обчислюємо R-показник (%):

Rij | V ,T , X , ,T , R  R 100  1 N hijk (v, t, x, , r) 100

N k1 з довірчим інтервалом при коефіцієнті довіри  : | R  I | t2, 1 3

 ( k  R )2 , 6 k1 де  k – значення R-показника обчислене для кожної з трьох частин N / 3 вимірювань .

Таким чином, для визначення S- та R-показників необхідно:  виконати послідовність експериментів з фіксацією часу виконання алгоритмів та знайденого значення екстремуму;   відповідно до ( 6 ) обчислити S-показник та його ( 7 ) довірчий інтервал; відповідно до ( 8 ) обчислити R-показник та його ( 9 ) довірчий інтервал. Функціональна ефективність біонічних алгоритмів

Однією з основних властивостей алгоритму є його функціональність. Ця властивість полягає в тому, що алгоритм реалізує деяку, в математичному розумінні функцію y  f (x)    ( y) , де x  X , y Y – вхідні та вихідні дані алгоритмів, елементи деяких визначених множин.

Дана властивість є однією з фундаментальних властивостей алгоритму разом з дискретністю, результативністю, доступністю, масовістю, послідовністю та однозначністю [13].

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

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

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

Нехай на множині Y задана функція де  – оцінка якості отриманих алгоритмом результатів.

Для алгоритмів розв’язку екстремальних задач   y , тобто в задачах мінімізації , чим менше значення функції y  f (x) буде знайдене деяким реалізацією деякого алгоритму, тим він кращий за функціональною ефективністю.

Аналогічно з попереднім пунктом, пропонується два показники функціональної ефективності алгоритмів:

 ступень переваги одного (i-го) алгоритму над іншим (j-им) на обмеженій множині X  X визначається наступним чином: де N – загальна кількість реалізацій;  область переваги:

 ( fi (x))   ( f j (x)) Sij | X  1 

N xX max( ( fi (x)), ( f j (x))) Rij | X  1

 sign( ( fi (x))   ( f j (x))) , N xX ( 8 ) ( 9 ) ( 10 ) ( 11 ) ( 12 ) ( 13 )

S- та R-показники є статистичною оцінкою показників функціональної ефективності SUPij та REGij, які визначаються аналогічно S- та R-показникам часової ефективності. Підготовка до експериментів

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

Нехай f (x) функція цілі, яку необхідно мінімізувати, причому x  (x1,..., xd ,..., xD ) . Робота алгоритму починається зі створення популяції часток (тобто множини потенційних рішень xi , i  [1, N ] , де N – розмір популяції) випадковим чином. Частки являють собою вектор координат точки в просторі оптимізації (дійсних чисел) xi  (xi1,, xid ,, xiD ) , i  [1, N] . Кожна частка рухається по поверхні графіку функції з якоюсь швидкістю vi  (vi1,, vid ,, viD ) , i  [1, N] . Частки змінюють свою швидкість та координати, ґрунтуючись на власному досвіді та досвіді інших часток. Таким чином, моделюється багатоагентна система, де агенти-частки рухаються до оптимальних рішень, обмінюючись при цьому інформацією з сусідами. Швидкість та координати часток оновлюються за такими формулами: vitd1    vitd  c1  rand ()  ( pid  xitd )  c2  rand ()  ( pgd  xitd ) , xitd1  vitd1  xitd ( 14 ) де vitd1 , vitd – швидкості частки на (t+1) та t-ітераціях відповідно; xitd1 , xitd – координати часток на t 1 та t ітераціях відповідно; pid – краща позиція, знайдена i -ою часткою за t попередніх поколінь; pgd – краща позиція, знайдена всім роєм за весь час роботи алгоритму; rand () – випадкові числа з проміжку [0,1] ; c1 , c2 – коефіцієнти навчання на проміжку [0, 2] ; – інерційна вага.

Константу

називають когнітивним (пізнавальним) параметром, який дозволяє враховувати «власний досвід» (історію) частинки. Константу називають соціальним параметром. Вона дозволяє частинці враховувати досвід усього рою. Таким чином, керує впливом глобального кращого положення, а керує дією власного кращого положення на швидкість кожної частинки. Роботу алгоритму також визначає топологія сусідства частинок, а саме яким чином вибирається кращий індивід для кожної частинки. Найбільш відомими є наступні топології [14]: кільце, клики. двовимірний тор, кластер.

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

Аналіз та опис використаного програмно-апаратного середовища. Вимірювати продуктивність на віртуальній машині Java (втім, як і в будь-якому іншому керованому середовищі часу виконання) за своєю природою більш складно, ніж при роботі з кодом, що працює в некерованому вигляді. Причина в тому, що програмісти, які пишуть на C / C ++, практично все роблять самі. Операційна система надає лише мінімальний набір служб, наприклад, рудиментарні планування потоків.

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

Ось деякі важливі функції платформи, через які ускладняється процес вимірювання оптимізація продуктивності: диспетчеризація потоків; прибирання сміття; динамічна компіляція.

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

Для проведення експериментів використовувалося апаратне середовище наступної конфігурації: процесор Intel(R) Core(TM) i7-6500U CPU @ 2.50GHz (тактова частота 2.6 – 3.0 ГГц); 16 Гб оперативної пам’яті типу DDR4 та програмне середовище: Microsoft Windows 10 Версія 1709; Java SE Runtime Environment build 9.0.1+11; Java HotSpot 64-Bit Server VM build 9.0.1+11, mixed mode.

Опис підходу для визначення часу роботи алгоритму. У Java є два основні методи для доступу до часу: System.currentTimeMillis() і System.nanoTime(). Другий використовується для вимірювання часу з точністю вище мілісекунди. Значення System.nanoTime() відносне відповідно певного моменту часу, в більшості сучасних операційних системи цей метод отримає інформацію від лічильника міток реального часу (Time Stamp Counter, TSC). Це означає, що цей метод можна використовувати для запису тривалості виконання.

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

Вплив «розігріву» JIT компілятору на результати вимірювань. Платформу Java краще всього представляти як платформу з динамічною компіляцією. Це означає, що класи додатків піддаються подальшій компіляції під час виконання, в результаті чого перетворюються в машинний код.

Такий процес називається динамічною (just-in-time) компіляцією або джейнтингом. Зазвичай такій компіляції піддається тільки один метод в одиницю часу. Під «розігрівом» компілятору будемо розуміти попередній виклик вимірюваного методу 10000 разів. За результатами досліджень встановлено, що швидкість виклику скомпільованого методу може бути у 12 разів більшою, ніж інтерпретованого методу.

В подальшому, перед проведенням вимірювань, будемо використовувати «розігрів» JIT компілятору. Для задання кількості раз виклику методу перед тим як він буде розглянутий як кандидат для динамічної компіляції, можна використовувати перемикач JVM “-XX:CompileThreshold=10000”, де 10000 – кількість викликів методу. Валідація досліджень інструментального середовища для проведення експериментальних Випробування інструментальних засобів виконане на основі декількох експериментальних досліджень. Так, виконані дослідження впливу кількості часток, епох, параметрів функції на показники часової та функціональної ефективності алгоритму рою часток (Particle Swarm Optimization, PSO) для пошуку глобального мінімуму функцій. Позначимо PSOpiej – алгоритм рою часток, де i – кількість часток, j – кількість епох. Наприклад алгоритм PSOp500e10 використовує кількість часток 500, кількість епох – 10.

Для експериментів будемо використовувати «важкі» функції оптимізації, запропоновані в [12]: сфери, гіпер-еліпсоїду, Растригіна, Розенброка, Аклі та Гріванка.

На рис. 5 та 6 показано часову ефективність із зростанням кількості епох та параметрів, відповідно. 0,8 0,5 0,2 0,1 0 Сфера Гипер єлипсоид Растригіна Розенброка Акли 5 парам 10 парам 30 парам 75 парам 100 парам Рис. 5. S-оцінка часової ефективності алгоритмів зі зростанням кількості епох Рис. 6. S-оцінка часової ефективності алгоритмів зі зростанням кількості параметрів Отримані значення часової та функціональної ефективності за пошуком екстремумів вище названих функцій усіх разом. На рис. 7 показані значення часової ефективності алгоритмів PSOpie100 по відношенню до PSOp(i-1)e100, починаючи з PSOp5e100. Кількість епох фіксована, змінюється кількість часток у рої. Перше значення 0,74 отримане при збільшенні часток у 10 разів, при цьому час виконання збільшився приблизно у 4 рази. При подальшому збільшенні кількості часток у два рази приблизно у два рази збільшується час пошуку екстремумів (у середньому для всіх функцій). На рис. 7 відображені також довірчі інтервали.

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

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

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

Прикладне значення має використання цього інструменту для розробки програмних засобів, зокрема систем штучного інтелекту, оптимізаційного напрямку. Тут корисна можливість налаштування параметрів біонічних алгоритмів за показниками функціональної та часової ефективності. Література Про авторів: Дніпропетровськии національнии університет залізничного транспорту імені академіка В. Лазаряна, вул. акад. Лазаряна, 2, Дніпро, Україна, 49010. Тел.: [phone]. Моб. тел.: [phone].

E-mail: [e-mail], [e-mail], [e-mail]

References

1. Kennedy J. , Eberhart R . Particle Swarm Optimization . In proceedings of IEEE International Conference on Neural Networks . 1995 . P. 1942 - 1948 .

2. Yang X.S. , Deb S. Cuckoo search via Levy flights . In proceedings of World Congress of Nature & Biologically Inspired Computing . 2009 . P. 210 - 214 .

3. Yang X.S. A new metaheuristic bat-inspired algorithm . Nature Inspired Cooperative Strategies for Optimization . Springer. 2010 . P. 65 - 74 .

4. Yang X.S. Firefly algorithms for multimodal optimization . In proceedings of the 5th Symposium on Stochastic Algorithms, Foundations and Applications . 2009 . P. 169 - 178 .

5. Yang X.S. , Chen J . Algorithm of Marriage in Honey Bees Optimization Based on the Wolf Pack Search . In proceedings of the International Conference of Intelligent Pervasive Computing . 2007 . P. 462 - 467

6. Kennedy J. , Eberhart R.C. A discrete binary version of the particle swarm algorithm . In proceedings of the International Conference on Computational Cybernetics and Simulation . 1997 . P. 4104 - 4108 .

7. Shi Y.R. , Eberhart C. Parameter selection in particle swarm optimization . In proceedings of Evolutionary Programming VII (EP98) . 1998 . P. 591 - 600 .

8. Kennedy J . Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance . In proceedings of IEEE Congress on Evolutionary Computation (CEC 1999 ). 1999 . P. 1931 - 1938 .

9. Moore J. , Chapman R . Application of particle swarm to multiobjective optimization . Department of Computer Science and Software Engineering . Auburn University. 1999 . 840 p.

10. Shynkarenko V. I. ( 2006 ). Functional effectiveness of algorithms with fuzzy specification. Problems in programming, (1 ), 24 - 33

11. Shynkarenko V. I. ( 2001 ). Features of an estimation of efficiency of computational algorithms . Problems in programming, (1-2) , 23 - 29 .

12. Molga , M. , & Smutnicki , C. ( 2005 ). Test functions for optimization needs . Test functions for optimization needs , 101 .

13. Zeitlin , H. E. ( 1998 ). Introduction to algorithmics . K.: Sphera, 310 .

14. Mendes , R. , Kennedy , J. , & Neves , J. ( 2004 ). The fully informed particle swarm: simpler, maybe better . IEEE transactions on evolutionary computation , 8 ( 3 ), 204 - 210 .

Індекс Хірша 2 (Scopus), 7 (Google Scolar) . https://orcid.org/0000-0001-8738-7225, Ільченко Петро Володимирович, магістрант Дніпропетровського національного університету залізничного транспорту імені академіка В . Лазаряна. https://orcid.org/0000-0001-8615-7831, Забула Геннадій Володимирович, кандидат технічних наук, асистент Дніпропетровського національного університету залізничного транспорту імені академіка В. Лазаряна. Кількість наукових публікацій в українських виданнях - 7. Кількість наукових публікацій в зарубіжних виданнях - 1 . https://orcid.org/0000-0002-8607- 5729 . Місце роботи авторів: