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

Анотація наукової статті з математики, автор наукової роботи - Родзін О.Н., Родзін Л.С.


ANALYSIS OF LANDSCAPE OF OPTIMIZABLE FUNCTIONS WHEN MAKING DECISIONS RELATED TO DATA MANAGEMENT

The article states the principle of searching for the most efficient data management solutions by metaheuristic algorithms. Metaheuristics is an iterative procedure that uses randomization and selflearning elements, intensification and diversification of searches, adaptive control mechanisms, constructive heuristics ,, and local search methods. It is a very promising approach to solving many optimization problems. A pseudocode program that illustrates the search for solutions by metaheuristic algorithms is proposed. General landscape model of the optimized function is considered. The distance between the solutions is determined. Various measures are used to analyze the landscape: Changing the average distance between the set of uniformly distributed solutions and the set of locally optimal solutions entropy amplitude correlation.


Область наук:
  • Математика
  • Рік видавництва: 2019
    Журнал: Міжнародний науково-дослідний журнал

    Наукова стаття на тему 'АНАЛІЗ ЛАНДШАФТА оптимізується функція ПРИ ПРИЙНЯТТІ ІНФОРМАЦІЙНО-УПРАВЛЯЮЧИХ РІШЕНЬ'

    Текст наукової роботи на тему «АНАЛІЗ ЛАНДШАФТА оптимізується функція ПРИ ПРИЙНЯТТІ ІНФОРМАЦІЙНО-УПРАВЛЯЮЧИХ РІШЕНЬ»

    ?_ФІЗІКО-математичні науки / PHYSICS AND MATHEMATICS_

    DOI: https://doi.org/10.23670/IRJ.2019.87.9.001

    АНАЛІЗ ЛАНДШАФТА оптимізується функція ПРИ ПРИЙНЯТТІ ІНФОРМАЦІЙНО-

    УПРАВЛЯЮЧИХ РІШЕНЬ

    Наукова стаття

    Родзін О.Н.1, *, Родзін Л.С.2

    1 ORCID: 0000-0002-8032-2362;

    2 ORCID: 0000-0002-4968-1922;

    1 2 Південний федеральний університет, Таганрог, Росія

    * Корреспондирующий автор (srodzin [at] yandex.org.ua)

    анотація

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

    Ключові слова: метаеврістіческій алгоритм, прийняття рішень, оптимізація, ландшафт, ентропія.

    ANALYSIS OF LANDSCAPE OF OPTIMIZABLE FUNCTIONS WHEN MAKING DECISIONS RELATED TO

    DATA MANAGEMENT

    Research article

    Rodzina O.N.1, *, Rodzina L.S.2

    1 ORCID: 0000-0002-8032-2362;

    2 ORCID: 0000-0002-4968-1922;

    1 2 South Federal University, Taganrog, Russia

    * Corresponding author (srodzin [at] yandex.org.ua)

    Abstract

    The article states the principle of searching for the most efficient data management solutions by metaheuristic algorithms. Metaheuristics is an iterative procedure that uses randomization and self-learning elements, intensification and diversification of searches, adaptive control mechanisms, constructive heuristics ,, and local search methods. It is a very promising approach to solving many optimization problems. A pseudo-code program that illustrates the search for solutions by metaheuristic algorithms is proposed. General landscape model of the optimized function is considered. The distance between the solutions is determined. Various measures are used to analyze the landscape: Changing the average distance between the set of uniformly distributed solutions and the set of locally optimal solutions; entropy; amplitude; correlation.

    Keywords: metaheuristic algorithm, decision making, optimization, landscape, entropy.

    Вступ

    Завдань пошуку оптимальних рішень в умовах різних обмежень незліченна безліч. Кожен процес в науці і техніці, економіці та бізнесі має потенціал для оптимізації і може бути сформульований як оптимізаційна задача. Оптимізація полягає в мінімізації часу, вартості, ризику або максимізація прибутку, якості, ефективності. Більшість реальних завдань оптимізації складні, їх важко точно вирішити протягом розумного часу. Основний альтернативою для вирішення цих завдань є наближені алгоритми. Найбільш загальним класом наближених алгоритмів, які можна застосувати до різноманітних оптимізаційних завдань є метаеврістіческіе алгоритми [1]. Вони можуть бути адаптовані, щоб вирішити багато проблем оптимізації в таких областях як логістика, біоінформатика, автоматизація проектування, мережі та телекомунікації, логістика, інтелектуальний аналіз даних, фінанси, бізнес і т.д.

    В даний час, значне число розроблених і застосовуваних на практиці метаеврістік належать до недетермінованим алгоритмам [2], [3]. Це обумовлено їх більш високими показниками ефективності. До того ж, постановки оптимізаційних задач часто містять дані, які мають певні похибки, що остаточно робить значні обчислювальні витрати для знаходження точного рішення невиправданими.

    У статті з єдиних позицій представлений аналіз ландшафту оптимізуються функцій при прийнятті інформаційно-керуючих рішень.

    Принцип пошуку рішень метаеврістіческімі алгоритмами

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

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

    Алгоритм складається в багаторазовому застосуванні процедури пошуку альтернативних рішень в деякій околиці і заміни поточного рішення на альтернативне рішення. Для створення альтернативних рішень використовується поточне рішення s. Безліч альтернативних рішень C (s), як правило, отримують шляхом локальних перетворень рішення s. На етапі заміни поточного рішення s новим рішенням sA вибір здійснюється з безлічі альтернативних рішень C (s). Цей ітераційний процес повторюється багато разів до виконання заданого критерію зупинки.

    Нижче наводиться програма на псевдокоді, що ілюструє пошук рішень метаеврістіческімі алгоритмами.

    Input: Ініціалізація початкового рішення s0.

    t: = 0;

    Repeat

    Створення альтернативних рішень C (st) шляхом застосування певних операторів в деякій околиці рішення st;

    Заміна рішення st на краще рішення st + 1 з безлічі C (st);

    t: = t + l;

    Until Перевірка умови зупинки;

    Output: Знайдено краще рішення.

    Аналіз ландшафту оптимізуються функцій

    Визначимо простір пошуку рішень через орієнтований граф G = (S, E), де безліч вершин S відповідає безлічі кодованих рішень задачі, а безліч ребер E відповідає безлічі операторів переміщення, використовуваних для генерації нових рішень. Вершини і sj є сусідніми і пов'язані ребром, якщо рішення sj може бути отримано з рішення з використанням оператора переміщення.

    Ландшафт L функції оптимізації визначається як кортеж (G, f), де граф G являє собою простір пошуку, а f - оптимізується функція [5]. Двох або тривимірний ландшафт можна уявити з використанням географічних термінів (піки, яри, плато і ін.), А метаеврістіческій алгоритм - як траєкторію пошуку, наприклад, піку [6].

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

    Для аналізу ландшафту оптимізується функції введемо поняття відстані в графі G, що представляє простір пошуку [8]. Це дозволить визначати просторову структуру ландшафту і може виявитися корисним для розробки пошукових механізмів, таких як диверсифікація і інтенсифікації процедури пошуку оптимуму. Визначимо відстань d (si, sj) між рішеннями і sj на графі G як довжину найкоротшого шляху, тобто мінімальна кількість застосувань оператора, щоб перейти з в sj. Відстань має володіти такими властивостями [9]:

    • d (x, y) = 0, якщо і тільки якщо x = y;

    • d (x, y) = d (y, x);

    • d (x, y) + d (y, z) >= D (x, z).

    Відзначимо, що для деяких завдань оптимізації обчислення відстані між рішеннями може виявитися NP-повної проблемою або ж мати оцінку складності високого полиномиального порядку [10], [11], [12]. Ландшафт характеризується різними властивостями: числом локальних оптимумів, їх розподілом, нерівністю, дисперсією і ін. Більшість з цих властивостей засновані на статистиці і є глобальними або локальними характеристиками ландшафту.

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

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

    Для безлічі отриманих метаеврістіческіх рішень Р визначимо середнє відстань dmm (P) і нормоване середнє відстань Dmm (P):

    1 Y>sepY>tep, t * sdist {s, t) dmmjp)

    dmm (P) = -; ---; ---, Dmm (P) = -, diam (P) == maxdist (s. t).

    | P | (| P | -1) diam (S) s, tep

    Тут diam (S) - діаметр безлічі рішень S, рівний максимальному відстані між рішеннями.

    Нормоване середнє відстань характеризує концентрацію безлічі рішень Р в просторі пошуку. Невелика відстань вказує на те, що рішення групуються в малій області простору пошуку. Величина ADmm = (Dmm (U) - Dmm (O)) / Dmm (U) являє собою зміну середньої відстані між безліччю однорідно розподілених рішень U і безліччю локальних оптимальних рішень. При цьому потужність безлічі O в залежності від складності метаеврістіческого алгоритму вибирається на інтервалі 103 < O < 104 .

    Ентропія дозволяє вимірювати різноманітність безлічі рішень в просторі пошуку [13]. Величина Aent = ent (U) - ent (O) / ent (U) являє зміна ентропії між початковими рішеннями U і кінцевим безліччю локальних оптимумів O, отриманих після виконання метаеврістіческого алгоритму. Ентропія дає інформацію про розкид, а не про зернистості рішень. Хоча рішення, сконцентровані в декількох областях, і рішення, сконцентровані в одній області, можуть мати однакову невелику ентропію [14].

    Для аналізу розподілу рішень в просторі функції f може використовуватися амплітуда. Амплітуда - це величина відносної різниці між кращим і гіршим значенням функції f в деякій множині рішень P:

    | P | (max / (s) - min / (s)) Arnp (P) --s%; .eP-.

    Lsep f (s)

    Відносне зміна амплітуди AAmp визначається співвідношенням між початковими рішеннями U і кінцевим безліччю локальних оптимальних рішень O за формулою:

    Amp (U) - Amp (о)

    ^ А-т-п - '

    Атт Amp (U)

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

    1ТТ (Р) = ЦМ,

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

    З іншого боку, цільові функції деяких завдань оптимізації характеризуються наявністю великого плато, подолати яке метаеврістіческій алгоритм часом не в змозі. Нехай є рішення 5 в просторі пошуку Б, V - деяке значення критерію /. Позначимо через N (5), підмножина точок 5 'в околиці рішення 5. Нехай X є підмножиною N (5), яке складається з рішень 5 "ЕХ таких, що / (5") = V. X являє собою плато, тоді і тільки тоді, коли X - 2. Якщо ландшафт функції включає кілька плато, то цільова функція оптимізації / недостатньо, щоб розрізнити підмножини N (5) околиць поточної точки 5. щоб відокремити одне плато від іншого необхідно використовувати додаткову інформацію. Або змінити цільову функцію.

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

    висновок

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

    фінансування

    Дослідження виконано за фінансової підтримки РФФД в рамках наукового проекту № 19-01-00412-а.

    Конфлікт інтересів

    Не вказано.

    Funding

    The study was carried out with the financial support of the Russian Federal Property Fund in the framework of scientific project No. 19-01-00412-a.

    Conflict of Interest

    None declared.

    Список літератури / References

    1. Bischl B. Algorithm Selection Based on Exploratory Landscape Analysis and Cost-Sensitive Learning / B. Bischl, O. Mersmann, H. Trautmann, M. Preuss // Proc. of the 14th Annual Conf. on Genetic and Evolutionary Computation (GECCO). -2012. - P. 313 - 320.

    2. Rodzin S.I. Effectiveness evaluation of memetic and biogeography algorithms using benchmark and trans computational tasks of combinatorial optimization / S.I. Rodzin, O.N. Rodzina // Proc. of the First Int. Scientific Conf. "Intelligent Information Technologies for Industry" (IITI'16). - 2016. vol. 1. Advances in Intelligent Systems and Computing 450. - P. 463-475.

    3. Rodzin S. Smart Dispatching and Metaheuristic Swarm Flow Algorithm / S. Rodzin // Computer and Systems Sciences Intern. - 2014. - N. 1. - P. 109-115.

    4. Hanster C. Exploratory Landscape Analysis for Everyone / C. Hanster, P. Kerschke // Proc. of the 19th Annual Conf. on Genetic and Evolutionary Computation (GECCO). - 2017. - Companion. ACM. doi: 10.1145 / 3067695.3082477.

    5. Kerschke P. Feature-Based Landscape Analysis of Continuous and Constrained Optimization Problems [Electronic resource] / P. Kerschke // R-package version 1.7. - 2017. URL https://github.com/kerschke/ flacco. (Accessed: 23.07.2019)

    6. Kerschke P. Cell Mapping Techniques for Exploratory Landscape Analysis / P. Kerschke, M. Preuss, C. Hern'andez, O. Schutze, J.Q. Sun, C. Grimme, G. Rudolph, B. Bischl, H. Trautmann // EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation. - 2014. - P. 115 - 131.

    7. Malan K.M. Quantifying Ruggedness of Continuous Landscapes using Entropy / K.M. Malan, A.P. Engelbrecht // Proc. of the IEEE Congress on Evolutionary Computation (CEC). - 2009. - P. 1440 - 1447.

    8. Rodzin S. New computational models for big data and optimization / S. Rodzin, O. Rodzina // Proc. of the 9th Int. Conf. on Application of Information and Communication Technologies (AICT'2015). - 2015. - P. 3-7.

    9. Bozhenyuk A. Hybrid Ant Fuzzy Algorithm for MRI Images Segmentation / A. Bozhenyuk, S. El-Khatib, Ja. Kacprzyk, M. Knyazeva, S. Rodzin // Lecture Notes in Computer Science. - 2019. - vol. 11509. P. 127-137.

    10. Mersmann O. Exploratory Landscape Analysis / O. Mersmann, B. Bischl, H. Trautmann, M. Preuss, C. Weihs, G. Rudolph // Proc. of the 13th Annual Conf. on Genetic and Evolutionary Computation (GECCO). - 2011. - P. 829 - 836.

    11. Muller C.L. Global Characterization of the CEC 2005 Fitness Landscapes using Fitness-Distance Analysis / C.L. Muller, I.F. Sbalzarini // Applications of Evolutionary Computation. - 2011. - P. 294 - 303. doi: 10.1007 / 978-3-642-20525-5_ 30.

    12. Munoz M.A. Exploratory Landscape Analysis of Continuous Space Optimization Problems using Information Content / M.A. Munoz, M. Kirley, S.K. Halgamuge // IEEE Trans. on Evolutionary Computation. - 2015. - P. 74 - 87. doi: 10.1109 / TEVC.2014. 2302006.

    13. Rodzin S.I. Metaheuristics memes and biogeography for trans computational combinatorial optimization problems / S.I. Rodzin, O.N. Rodzina // Proc. of the 6th IEEE Int. Conf. on Cloud System and Big Data Engineering (Confluence'2016). AI and Soft Computing. - 2016. - P. 1-5.

    14. Shirakawa S. Bag of Local Landscape Features for Fitness Landscape Analysis / S. Shirakawa, T. Nagao // Soft Computing. - 2016. - N. 20 (10). - P. 3787 - 3802.


    Ключові слова: МЕТАЕВРІСТІЧЕСКІЙ АЛГОРИТМ / ПРИЙНЯТТЯ РІШЕНЬ / ОПТИМІЗАЦІЯ / ЛАНДШАФТ / ЕНТРОПІЯ / META-HEURISTIC ALGORITHM / DECISION MAKING / OPTIMIZATION / LANDSCAPE / ENTROPY

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

    Завантажити