Tools of investigation of time and functional efficiency of bionic algorithms for function optimization problems

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 carri...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2018
Автори: Shynkarenko, V.I., Ilchenko, P.V., Zabula, H.V.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Інститут програмних систем НАН України 2018
Теми:
Онлайн доступ:https://pp.isofts.kiev.ua/index.php/ojs1/article/view/290
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Problems in programming
Завантажити файл: Pdf

Репозитарії

Problems in programming
id pp_isofts_kiev_ua-article-290
record_format ojs
resource_txt_mv ppisoftskievua/39/d2902e3945faa39a272c049ff06f8639.pdf
spelling pp_isofts_kiev_ua-article-2902024-04-28T11:37:25Z Tools of investigation of time and functional efficiency of bionic algorithms for function optimization problems Инструментальные методы исследования временной и функциональной эффективности бионических алгоритмов решения экстремальных задач Інструментальні засоби дослідження часової та функціональної ефективності біонічних алгоритмів розв’язку екстремальних задач Shynkarenko, V.I. Ilchenko, P.V. Zabula, H.V. time efficiency; functional efficiency; bionic algorithm; computer experiment UDC 004.051+004.421.4 временная эффективность; функциональная эффективность; бионический алгоритм; компьютерный эксперимент УДК 004.051+004.421.4 часова ефективність; функціональна ефективність; біонічний алгоритм; комп’ютерний експеримент УДК 004.051+004.421.4 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.Problems in programming 2018; 2-3: 270-279 Разработана инструментальная среда для определения временной и функциональной эффективности алгоритмов. Предусмотрены возможности исследования эффективности алгоритмов на множестве особых «неудобных» функций, которое можно изменять и дополнять. Выполнены компьютерные эксперименты, включая определение теоретических основ, подготовку, реализацию и анализ результатов. Получены зависимости временной и функциональной эффективности роевого алгоритма от количества параметров функций, глобальный экстремум которых определяется, и параметров роевого алгоритма: размера популяций и количества эпох. В разработанной среде предусмотрена возможность исследования других бионических алгоритмов.Problems in programming 2018; 2-3: 270-279 Розроблене інструментальне середовище для визначення часової та функціональної ефективності алгоритмів. Передбачені можливості дослідження ефективності алгоритмів на множині особливих «незручних» функцій, яку можливо змінювати та доповнювати. Виконані комп’ютерні експерименти з визначенням теоретичних засад, підготовчих заходів, реалізацією та аналізом отриманих результатів. Отримані залежності часової та функціональної ефективності зграйного алгоритму від кількості параметрів функцій, глобальний екстремум яких визначається, та параметрів зграйного алгоритму: розміру популяцій та кількості епох. У розробленому середовищі передбачена можливість дослідження інших біонічних алгоритмів.Problems in programming 2018; 2-3: 270-279 Інститут програмних систем НАН України 2018-11-05 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/290 10.15407/pp2018.02.270 PROBLEMS IN PROGRAMMING; No 2-3 (2018); 270-279 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2018); 270-279 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2018); 270-279 1727-4907 10.15407/pp2018.02 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/290/284 Copyright (c) 2018 PROBLEMS OF PROGRAMMING
institution Problems in programming
baseUrl_str https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date 2024-04-28T11:37:25Z
collection OJS
language Ukrainian
topic time efficiency
functional efficiency
bionic algorithm
computer experiment
UDC 004.051+004.421.4
spellingShingle time efficiency
functional efficiency
bionic algorithm
computer experiment
UDC 004.051+004.421.4
Shynkarenko, V.I.
Ilchenko, P.V.
Zabula, H.V.
Tools of investigation of time and functional efficiency of bionic algorithms for function optimization problems
topic_facet time efficiency
functional efficiency
bionic algorithm
computer experiment
UDC 004.051+004.421.4
временная эффективность
функциональная эффективность
бионический алгоритм
компьютерный эксперимент
УДК 004.051+004.421.4
часова ефективність
функціональна ефективність
біонічний алгоритм
комп’ютерний експеримент
УДК 004.051+004.421.4
format Article
author Shynkarenko, V.I.
Ilchenko, P.V.
Zabula, H.V.
author_facet Shynkarenko, V.I.
Ilchenko, P.V.
Zabula, H.V.
author_sort Shynkarenko, V.I.
title Tools of investigation of time and functional efficiency of bionic algorithms for function optimization problems
title_short Tools of investigation of time and functional efficiency of bionic algorithms for function optimization problems
title_full Tools of investigation of time and functional efficiency of bionic algorithms for function optimization problems
title_fullStr Tools of investigation of time and functional efficiency of bionic algorithms for function optimization problems
title_full_unstemmed Tools of investigation of time and functional efficiency of bionic algorithms for function optimization problems
title_sort tools of investigation of time and functional efficiency of bionic algorithms for function optimization problems
title_alt Инструментальные методы исследования временной и функциональной эффективности бионических алгоритмов решения экстремальных задач
Інструментальні засоби дослідження часової та функціональної ефективності біонічних алгоритмів розв’язку екстремальних задач
description 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.Problems in programming 2018; 2-3: 270-279
publisher Інститут програмних систем НАН України
publishDate 2018
url https://pp.isofts.kiev.ua/index.php/ojs1/article/view/290
work_keys_str_mv AT shynkarenkovi toolsofinvestigationoftimeandfunctionalefficiencyofbionicalgorithmsforfunctionoptimizationproblems
AT ilchenkopv toolsofinvestigationoftimeandfunctionalefficiencyofbionicalgorithmsforfunctionoptimizationproblems
AT zabulahv toolsofinvestigationoftimeandfunctionalefficiencyofbionicalgorithmsforfunctionoptimizationproblems
AT shynkarenkovi instrumentalʹnyemetodyissledovaniâvremennojifunkcionalʹnojéffektivnostibioničeskihalgoritmovrešeniâékstremalʹnyhzadač
AT ilchenkopv instrumentalʹnyemetodyissledovaniâvremennojifunkcionalʹnojéffektivnostibioničeskihalgoritmovrešeniâékstremalʹnyhzadač
AT zabulahv instrumentalʹnyemetodyissledovaniâvremennojifunkcionalʹnojéffektivnostibioničeskihalgoritmovrešeniâékstremalʹnyhzadač
AT shynkarenkovi ínstrumentalʹnízasobidoslídžennâčasovoítafunkcíonalʹnoíefektivnostíbíoníčnihalgoritmívrozvâzkuekstremalʹnihzadač
AT ilchenkopv ínstrumentalʹnízasobidoslídžennâčasovoítafunkcíonalʹnoíefektivnostíbíoníčnihalgoritmívrozvâzkuekstremalʹnihzadač
AT zabulahv ínstrumentalʹnízasobidoslídžennâčasovoítafunkcíonalʹnoíefektivnostíbíoníčnihalgoritmívrozvâzkuekstremalʹnihzadač
first_indexed 2024-09-16T04:08:28Z
last_indexed 2024-09-16T04:08:28Z
_version_ 1818568433526112256
fulltext Інструментальні засоби та середовища програмування © В.І. Шинкаренко, П.В. Ільченко, Г.В. Забула, 2018 270 ISSN 1727-4907. Проблеми програмування. 2018. № 2–3. Спеціальний випуск УДК 004.051+004.421.4 ІНСТРУМЕНТАЛЬНІ ЗАСОБИ ДОСЛІДЖЕННЯ ЧАСОВОЇ ТА ФУНКЦІОНАЛЬНОЇ ЕФЕКТИВНОСТІ БІОНІЧНИХ АЛГОРИТМІВ РОЗВ’ЯЗКУ ЕКСТРЕМАЛЬНИХ ЗАДАЧ В.І. Шинкаренко, П.В. Ільченко, Г.В. Забула Розроблене інструментальне середовище для визначення часової та функціональної ефективності алгоритмів. Передбачені можливості дослідження ефективності алгоритмів на множині особливих «незручних» функцій, яку можливо змінювати та доповнювати. Виконані комп’ютерні експерименти з визначенням теоретичних засад, підготовчих заходів, реалізацією та аналізом отриманих результатів. Отримані залежності часової та функціональної ефективності зграйного алгоритму від кількості параметрів функцій, глобальний екстремум яких визначається, та параметрів зграйного алгоритму: розміру популяцій та кількості епох. У розробленому середовищі передбачена можливість дослідження інших біонічних алгоритмів. Ключові слова: часова ефективність, функціональна ефективність, біонічний алгоритм, комп’ютерний експеримент. Разработана инструментальная среда для определения временной и функциональной эффективности алгоритмов. Предусмотрены возможности исследования эффективности алгоритмов на множестве особых «неудобных» функций, которое можно изменять и дополнять. Выполнены компьютерные эксперименты, включая определение теоретических основ, подготовку, реализацию и анализ результатов. Получены зависимости временной и функциональной эффективности роевого алгоритма от количества параметров функций, глобальный экстремум которых определяется, и параметров роевого алгоритма: размера популяций и количества эпох. В разработанной среде предусмотрена возможность исследования других бионических алгоритмов. Ключевые слова: временная эффективность, функциональная эффективность, бионический алгоритм, компьютерный эксперимент. 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. Key words: time efficiency, functional efficiency, bionic algorithm, computer experiment. Вступ Існує велика кількість стохастичних алгоритмів, які використовують соціальні та біологічні ідеї. Одним з найбільш вивчених є зграйний алгоритм або Particle Swarm Optimization (PSO), розроблений Кеннеді та Еберхартом у 1995 році [1]. Ідея даного методу взята з соціальної поведінки деяких видів тварин, наприклад, зграй птахів, косяків риб або стада копитних. Дослідження показали ефективність алгоритму та доцільність його застосування при рішенні задач як безумовної, так і умовної оптимізації функцій дійсних змінних. Постійно пропонуються нові варіанти алгоритму для покращення продуктивності методу або для розширення кола вирішуваних задач (наприклад, одна з перших модифікацій була пов’язана з ідеєю рішення однокритеріальних задач безумовної оптимізації з бінарними змінними за допомогою алгоритму PSO). Крім PSO існують й інші алгоритми, які імітують поведінку окремих видів тварин. Найбільший інтерес з останніх розробок представляють наступні біонічні алгоритми: алгоритм пошуку зозуль (Cuckoo Search Algorithm, CSA) [2], алгоритм кажанів (Bat Algorithm, BA) [3], алгоритм світлячків (Firefly Algorithm, FFA) [4] та алгоритм зграї вовків (Wolf Pack Search, WPS) [5]. Кожен з зазначених алгоритмів імітує деяку характеристику певного виду тварин: CSA – спосіб відкладання яєць зозулями; BA – ехолокацію кажанів, FFA – випромінювання від світлячків, WPS – процес полювання зграї вовків. Зграйний алгоритм – метод чисельної оптимізації, який базується на моделюванні поведінки популяції часток в просторі оптимізації, для використання якого не потрібно знати точного градієнту функції оптимізації [1]. Даний метод приваблює простотою реалізації, він може використовуватися для рішення багатьох задач, включаючи навчання нейронних мереж. Зараз існують різноманітні модифікації зграєвого алгоритму оптимізації, розроблені для рішення різноманітних завдань оптимізації. Одна з перших модифікацій була запропонована Кеннеді та Еберхартом в 1997 році для рішення задач однокритеріальної безумовної оптимізації з бінарними змінними [6]. В 1998 році Ши та Еберхарт опублікували роботу, в якій описувалась методика автоматизованого налаштування параметрів алгоритму [7]. В 1999 році в статті Кеннеді [8] оглядався вплив обраної топології на результат роботи алгоритму при вирішенні тої чи іншої задачі оптимізації. В тому ж році була вперше запропонована модифікація алгоритму для рішення задач багатокритеріальної оптимізації [9]. В наступні роки були розроблені різноманітні методи на основі зграйного алгоритму, зокрема для навчання нейронних мереж. У представленій роботі для оцінки якості біонічних алгоритмів були запропоновані показники функціональної [10] та часової ефективності [11]. Інструментальні засоби та середовища програмування 271 Функціональні можливості розробленого інструментального середовища Представлений у даній роботі інструментальний засіб призначений для дослідження будь-якого стохастичного алгоритму пошуку екстремуму функції. Такий алгоритм додається до вже існуючих у системі алгоритмів у призначеному для цього вікні. Алгоритм має бути представленій на мові Java та попередньо відлагоджений. Для опрацювання інструментальних засобів у систему доданий алгоритм PSO. Для визначення часової та функціональної ефективності має бути сформована представницька множина функцій, подібних до тих, пошук екстремумів яких потребується. Наразі у системі маємо функції, запропоновані в [12]: сфери, гіпер-еліпсоїду, Растригіна, Розенброка, Аклі та Гріванка. Надана можливість додавання нових функцій. На рис. 1 показана вкладка, яка дозволяє додавати, редагувати та видаляти функції для подальшого аналізу. Для цього слід додати реалізацію функції на мові Java. Саме вона і буде використовуватися у процесі аналізу з оптимізації. Додатково можна задати математичне представлення, що дозволить інструменту знайти глобальний екстремум та побудувати графіки функції. При цьому функціональна ефективність буде визначатись у порівнянні знайденого екстремуму з відомим точним значенням. Рис. 1. Вкладка для завдання функції, екстремум якої визначається На рис. 2 показано приклад побудови графіка функції Растригіна. Інструментальні засоби та середовища програмування 272 Рис. 2. Функції Растригіна Користувач має можливість налаштування експерименту (верхня частина вкладники на рис. 3): обрати біонічний алгоритм, що вже є у системі; алгоритми, екстремуми яких знаходяться цим біонічним алгоритмом та показники ефективності. Рис. 3. Настройка експерименту та порівняльні графіки Інструментальні засоби та середовища програмування 273 У результаті маємо порівняльні графіки та таблиці (приклад останніх на рис. 4) Рис. 4. Приклад табличного представлення результатів Часова ефективність біонічних алгоритмів Одна із суттєвих особливостей стохастичних біонічних алгоритмів – потреба в значних часових ресурсах. Виконавцем природних біонічних алгоритмів є значна кількість особин. У комп’ютерній реалізації маємо один обчислювальний механізм та значно складнішу задачу пошуку. Тому й виникає задача оцінки можливостей алгоритмів за часовими показниками. При наявності одного алгоритму вирішення деякої екстремальної задачі можна обмежитись оцінкою обчислювальної складності алгоритмів. Однак, знаходження таких оцінок є досить нетривіальною задачею і вони не враховують значного впливу програмно-апаратного середовища виконання алгоритмів. Якщо існує декілька функціонально еквівалентних алгоритмів [11], то їх часову ефективність необхідно визначати за конкретними реалізаціями. Час виконання алгоритму визначається функцією [11]: ( , , , , )E f v t x r , (1) де v , t та x – відповідно об’єм, тип та значення вхідних даних;  – програмне середовище функціонування та створення виконуваного файлу; r – архітектура ЕОМ. При наявності декількох функціонально еквівалентних алгоритмів слід порівнювати функції: 1 1 2 2( , , , , ), ( , , , , ),..., ( , , , , )n nE f v t x r E f v t x r E f v t x r     . (2) Для порівняння часової ефективності двох алгоритмів необхідно визначити[11]:  наскільки в середньому один з алгоритмів перевершує інший;  чи в усій досліджуваній області спостерігається перевершення одного алгоритму, якщо ні – то як співвідносяться розміри областей переваги кожного алгоритму. Нехай *V – множина можливих значень об’єму даних, *T – множина можливих типів даних, *X – множина можливих значень даних, * – множина можливих програмних середовищ, *R – множина архітектур ЕВМ, на яких можлива реалізація алгоритмів. Тоді для порівняння часової ефективності альтернативних обчислювальних алгоритмів необхідно визначити ступінь переваги одного (і-го) алгоритму над іншим (j-им) на обмежених множинах, які є підмножинами вказаних вище множин *V V , *T T , *X X , * , *R R визначається як: 1 | , , , , ( , , , , )ij ij v V t T x X r R SUP V T X R g v t x r N           , ( , , , , ) ( , , , , ) ( , , , , ) max( ( , , , , ), ( , , , , )) j i ij i j f v t x r f v t x r g v t x r f v t x r f v t x r        , (3) де N – загальна кількість доданків, gij – ступінь переваги i-го алгоритму над j-им при деякому виконанні, fi – час виконання i-го алгоритму. Визначається також [11] область переваги одного (і-го) алгоритму над іншим (j-им): 1 | , , , , ( , , , , )ij ij v V t T x X r R REG V T X R h v t x r N           , (4) де hij – ознака переваги і-го алгоритму над j-им в точці ( , , , , ) ( ( , , , , ) ( , , , , ))ij i jh v t x r sign f v t x r f v t x r    , 1, якщо 0 ( ) 0, якщо 0 x sign x x     . (5) Інструментальні засоби та середовища програмування 274 Слід зазначити, що множини , , , ,V T X R – дискретні. Виходячи з необмеженої кількості можливих вхідних даних *X , значення N є настільки великим, що практичне обчислення запропонованих показників не є можливим. Оцінка S-показника. S-показник є статистичною оцінкою | , , , ,ijSUP V T X R . За [11] S-оцінку ступені переваги i-го алгоритму над j-им визначимо як (%): 1 1 | , , , , , 100 ( , , , , ) 100 N ij S ijk k S V T X T R g v t x r N         , (6) де ijkg – ступінь переваги i-го алгоритму над j-им (3) при k-му виконанні алгоритмів з випадковими значеннями , , , ,v t x r із області V T X R    . Там же [11] надане визначення довірчого інтервалу S-показника при коефіцієнті довіри  : 3 2 2, 1 1 | | ( ) 6 s k S k I t        , (7) де I – точне значення S-показника, s – значення визначене за (6), k – значення S-показника обчислене для кожної з трьох частин / 3N вимірювань, 2,t  – табличне значення розподілу Стьюдента при коефіцієнті довіри  . Оцінка R-показника. Оскільки вирази для обчислення SUPij та REGij в (3) та (4) відрізняються тільки функцією під знаком суми, R-показник обчислюється аналогічно S-показнику. Випадковим чином обирається N точок в області V T X R    . Доцільно взяти ті самі точки, що і для обчислення S-показника. Використовуючи описану вище методику й позначивши, обчислюємо R-показник (%): 1 1 | , , , , , 100 ( , , , , ) 100 N ij R ijk k R V T X T R h v t x r N         (8) з довірчим інтервалом при коефіцієнті довіри : 3 2 2, 1 1 | | ( ) 6 R k R k I t        , (9) де k – значення R-показника обчислене для кожної з трьох частин / 3N вимірювань . Таким чином, для визначення S- та R-показників необхідно:  виконати послідовність експериментів з фіксацією часу виконання алгоритмів та знайденого значення екстремуму;  відповідно до (6) обчислити S-показник та його (7) довірчий інтервал;  відповідно до (8) обчислити R-показник та його (9) довірчий інтервал. Функціональна ефективність біонічних алгоритмів Однією з основних властивостей алгоритму є його функціональність. Ця властивість полягає в тому, що алгоритм реалізує деяку, в математичному розумінні функцію ( )y f x (10) де x X , y Y – вхідні та вихідні дані алгоритмів, елементи деяких визначених множин. Дана властивість є однією з фундаментальних властивостей алгоритму разом з дискретністю, результативністю, доступністю, масовістю, послідовністю та однозначністю [13]. У [10] звертається увага та цю властивість у зв’язку з її особливістю стосовно нечітко специфікованих алгоритмів. Ця особливість в тому, що розроблений відповідно з нечіткою специфікацією алгоритм може в деяких випадках і в деякій ступені задовольняти чи не задовольняти вимогам користувача. Під функціональною ефективністю будемо розуміти експлуатаційну характеристику алгоритму, яка відображає ступінь відповідності алгоритму потребам користувача [10] за своєю функціональністю. Інструментальні засоби та середовища програмування 275 Будь-який чітко специфікований алгоритм реалізує функцію, результати якої завжди повинні задовольняти потребам користувача. Можна вважати, що такий алгоритм має максимальну функціональну ефективність. Нехай на множині Y задана функція ( )y  , (11) де  – оцінка якості отриманих алгоритмом результатів. Для алгоритмів розв’язку екстремальних задач y  , тобто в задачах мінімізації , чим менше значення функції ( )y f x буде знайдене деяким реалізацією деякого алгоритму, тим він кращий за функціональною ефективністю. Аналогічно з попереднім пунктом, пропонується два показники функціональної ефективності алгоритмів:  ступень переваги одного (i-го) алгоритму над іншим (j-им) на обмеженій множині X X визначається наступним чином: ( ( )) ( ( ))1 | max( ( ( )), ( ( ))) i j ij x X i j f x f x S X N f x f x        , (12) де N – загальна кількість реалізацій;  область переваги: 1 | ( ( ( )) ( ( )))ij i j x X R X sign f x f x N      , (13) S- та R-показники є статистичною оцінкою показників функціональної ефективності SUPij та REGij, які визначаються аналогічно S- та R-показникам часової ефективності. Підготовка до експериментів Вибір та підготовка біонічного алгоритму. В даній роботі досліджується зграйний алгоритм. Він є реалізацією методу чисельної оптимізації, який базується на моделюванні поведінки популяції часток в просторі оптимізації. Нехай ( )f x функція цілі, яку необхідно мінімізувати, причому 1( ,..., ,..., )d Dx x x x . Робота алгоритму починається зі створення популяції часток (тобто множини потенційних рішень ix , [1, ]i N , де N – розмір популяції) випадковим чином. Частки являють собою вектор координат точки в просторі оптимізації (дійсних чисел) 1 ) , , , ,(i i id iDx x x x   , , ] [1i N . Кожна частка рухається по поверхні графіку функції з якоюсь швидкістю 1 ) , , , ,(i i id iDv v v v   , , ] [1i N . Частки змінюють свою швидкість та координати, ґрунтуючись на власному досвіді та досвіді інших часток. Таким чином, моделюється багатоагентна система, де агенти-частки рухаються до оптимальних рішень, обмінюючись при цьому інформацією з сусідами. Швидкість та координати часток оновлюються за такими формулами: 1 1 2() ( ) () ( )t t t t id id id id gd idv v c rand p x c rand p x           , 1 1t t t id id idx v x   (14) де 1t idv  , t idv – швидкості частки на (t+1) та t-ітераціях відповідно; 1t idx  , t idx – координати часток на 1t  та t - ітераціях відповідно; idp – краща позиція, знайдена i -ою часткою за t попередніх поколінь; gdp – краща позиція, знайдена всім роєм за весь час роботи алгоритму; ()rand – випадкові числа з проміжку [0,1] ; 1c , 2c – коефіцієнти навчання на проміжку [0,2] ; – інерційна вага. Константу 1c називають когнітивним (пізнавальним) параметром, який дозволяє враховувати «власний досвід» (історію) частинки. Константу 2c називають соціальним параметром. Вона дозволяє частинці враховувати досвід усього рою. Таким чином, 2c керує впливом глобального кращого положення, а 1c керує дією власного кращого положення на швидкість кожної частинки. Роботу алгоритму також визначає топологія сусідства частинок, а саме яким чином вибирається кращий індивід для кожної частинки. Найбільш відомими є наступні топології [14]: кільце, клики. двовимірний тор, кластер. Отже, ідея алгоритму полягає в тому, що частки, які спочатку рівномірно розподілені по поверхні функції, з плином часу (від покоління до покоління) починають групуватися («збиватися в зграї») поряд з Інструментальні засоби та середовища програмування 276 локальними мінімумами, при чому найбільша зграя збирається поряд з глобальним оптимумом. При чому майже завжди існують частки, які знаходяться у стороні від таких зграй, а також частки, які виходять за межі допустимої області. Аналіз та опис використаного програмно-апаратного середовища. Вимірювати продуктивність на віртуальній машині 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 показано часову ефективність із зростанням кількості епох та параметрів, відповідно. Інструментальні засоби та середовища програмування 277 Рис. 5. S-оцінка часової ефективності алгоритмів зі зростанням кількості епох Рис. 6. S-оцінка часової ефективності алгоритмів зі зростанням кількості параметрів Отримані значення часової та функціональної ефективності за пошуком екстремумів вище названих функцій усіх разом. На рис. 7 показані значення часової ефективності алгоритмів PSOpie100 по відношенню до PSOp(i-1)e100, починаючи з PSOp5e100. Кількість епох фіксована, змінюється кількість часток у рої. Перше значення 0,74 отримане при збільшенні часток у 10 разів, при цьому час виконання збільшився приблизно у 4 рази. При подальшому збільшенні кількості часток у два рази приблизно у два рази збільшується час пошуку екстремумів (у середньому для всіх функцій). На рис. 7 відображені також довірчі інтервали. -1 -0,8 -0,6 -0,4 -0,2 0 0,2 0,4 0,6 0,8 1 p25e100 p50e100 p100e100 p200e100 p400e100 p800e100 p1600e100 S-time S-func 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 5 парам 10 парам 30 парам 75 парам 100 парам Сфера Гипер єлипсоид Растригіна Розенброка Акли Інструментальні засоби та середовища програмування 278 Рис. 7. Часова та функціональна ефективність алгоритмів PSOpie100 з довірчими інтервалами Функціональна ефективність алгоритмів PSOpie100 виконана в порівнянні з алгоритмом, який знаходить точний мінімум. Така можливість є при дослідженнях, якщо точний мінімум відомий. Ефективність алгоритмів PSOpie100 суттєво зростає при збільшенні кількості часток рою. Всі отримані результати відповідають очікуваним, та відомим тенденціям обчислювальної складності. За проведеними експериментами та аналізом отриманих результатів щодо достатньо складних функцій можна стверджувати, що інструментальний засіб забезпечує адекватні оцінки часової та функціональної ефективності при розв’язку задач пошуку екстремумів функцій. Висновки Наразі спостерігається бурхливий розвиток перенесення алгоритмів природних систем у програмовані системи. Запропонований інструментальний засіб може бути корисним для розробників біонічних алгоритмів для виявлення ефективних складових алгоритмічних та параметричних рішень. Прикладне значення має використання цього інструменту для розробки програмних засобів, зокрема систем штучного інтелекту, оптимізаційного напрямку. Тут корисна можливість налаштування параметрів біонічних алгоритмів за показниками функціональної та часової ефективності. Література 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. Шинкаренко В.И. Функциональная эффективность нечетко специфицированных алгоритмов. Проблеми програмування. 2006. № 1. С. 24–33. 11. Шинкаренко В.И. Особенности оценки эффективности вычислительных алгоритмов. Проблемы программирования. № 1–2. 2001. С. 23–29. Інструментальні засоби та середовища програмування 279 12. Molga M. and Smutnicki C. Test functions for optimization need. 3 kwietnia. 2005. 43 р. 13. Цейтлин Г.Е. Введение в алгоритмику. Киев: Сфера. 1998. 310 с. 14. Madnes R., Kennedy J., Neves J. The Fully Informed Particle Swarm: Simpler, Maybe Better. IEEE Transactions of Evelutionary Computation. 2014. P. 204–210. 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. Про авторів: Шинкаренко Віктор Іванович, доктор технічних наук, професор, завідувач кафедри «Комп’ютерні інформаційні технології» Дніпропетровського національного університету залізничного транспорту імені академіка В. Лазаряна. Кількість наукових публікацій в українських виданнях – біля 60. Кількість наукових публікацій в зарубіжних виданнях – 7. Індекс Хірша 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. Місце роботи авторів: Дніпропетровський національний університет залізничного транспорту імені академіка В. Лазаряна, вул. акад. Лазаряна, 2, Дніпро, Україна, 49010. Тел.: (056) 373 1535. Моб. тел.: (063) 489 4915, (093) 337 1444, (093) 650 8511. E-mail: shinkarenko_vi@ua.fm, peterilchenko@gmail.com, zabulus12@gmail.com mailto:shinkarenko_vi@ua.fm http://mbox2.i.ua/compose/1155288960/?cto=IDQrDhM2RyxW9A0vNCNDUZ%2FJs5HCwKeQf3yjqIu9yMBsja3BnQ%3D%3D