Experimental analysis of multinational genetic algorithm and its modifications
Loading...
Date
2021
Authors
Gulayeva,Nataliia
Yaremko, Solomiia
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Context. Niching genetic algorithms are one of the most popular approaches to solve multimodal optimization problems. When classifying niching genetic algorithms it is possible to select algorithms explicitly analyzing topography of fitness function landscape; multinational genetic algorithm is one of the earliest examples of these algorithms.
Objective. Development and analysis of the multinational genetic algorithm and its modifications to find all maxima of a multimodal function.
Method. Experimental analysis of algorithms is carried out. Numerous runs of algorithms on well-known test problems are conducted and performance criteria are computed, namely, the percentage of convergence, real (global, local) and fake peak ratios; note that peak rations are computed only in case of algorithm convergence.
Results. Software implementation of a multinational genetic algorithm has been developed and experimental tuning of its parameters has been carried out. Two modifications of hill-valley function used for determining the relative position of individuals have been proposed. Experimental analysis of the multinational genetic algorithm with classic hill-valley function and with its modifications has been carried out.
Conclusions. The scientific novelty of the study is that hill-valley function modifications producing less number of wrong identifications of basins of attraction in comparison with classic hill-valley function are proposed. Using these modifications yields to performance improvements of the multinational genetic algorithm for a number of test functions; for other test functions improvement of the quality criteria is accompanied by the decrease of the convergence percentage. In general, the convergence percentage and the quality criterion values demonstrated by the algorithm studied are insufficient for practical use in comparison with other known algorithms. At the same time using modified hill-valley functions as a post-processing step for other niching algorithms seems to be a promising improvement of performance of these algorithms.
Актуальність. Генетичні алгоритми утворення ніш є одним з найпоширеніших підходів до розв’язання задач багатоекстремальної оптимізації. При проведенні класифікації цих алгоритмів можна виділити алгоритми, що ґрунтуються на явному аналізі топографії ландшафту функції пристосованості. Одним з ранніх прикладів таких алгоритмів є багатонаціональний генетичний алгоритм. Мета. Розробка та аналіз багатонаціонального генетичного алгоритму та його модифікацій. Алгоритм застосовується для розв’язання задачі пошуку всіх максимумів багатоекстремальної функції. Метод. Виконано експериментальний аналіз алгоритмів. Проведено численні прогони алгоритмів на відомих тестових задачах та обчислено критерії ефективності роботи алгоритмів, а саме, відсоток збіжності, частка реальних (глобальних, локальних) та хибних піків; зауважимо, що частки піків обчислюються тільки в разі збіжності алгоритму. Результати. Виконано програмну реалізацію багатонаціонального генетичного алгоритму та проведено експериментальне налаштування його параметрів. Запропоновано дві модифікації функції долин і пагорбів, яка використовується в алгоритмі для визначення взаємного розташування особин. Проведено експериментальний аналіз багатонаціонального генетичного алгоритму з класичного функцією долин і пагорбів та з її модифікаціями. Висновки. Наукова новизна роботи полягає в тому, що були запропоновані модифікації функції долин і пагорбів, які продукують меншу кількість помилкових ідентифікацій зон притягання порівняно з класичним варіантом цієї функції. Як наслідок, використання цих модифікацій призводить до покращення продуктивності багатонаціонального генетичного алгоритму для низки тестових задач. Втім, для деяких тестових задач поліпшення критеріїв якості супроводжується зменшенням відсотка збіжності. Загалом, відсоток збіжності та значення критеріїв якості, продемонстровані дослідженим алгоритмом, є недостатніми для практичного використання багатонаціонального генетичного алгоритму у порівнянні з іншими відомими алгоритмами. У той же час, використання модифікованих функцій долин і пагорбів як етапу постобробки в інших алгоритмах утворення ніш видається перспективним підходом до покращення роботи цих алгоритмів.
Актуальность. Генетические алгоритмы образования ниш являются одним из самых распространенных подходов к решению задач многоэкстремальной оптимизации. При проведении классификации генетических алгоритмов образования ниш можно выделить алгоритмы, основанные на явном анализе топографии ландшафта функции приспособленности. Многонациональный генетический алгоритм является одним из ранних примеров таких алгоритмов. Цель. Разработка и анализ многонационального генетического алгоритма и его модификаций. Алгоритм применяется для решения задачи поиска всех максимумов многоэкстремальной функции. Метод. Выполнен экспериментальный анализ алгоритмов. Проведены многочисленные прогоны алгоритмов на известных тестовых задачах и вычислены критерии эффективности работы алгоритмов, а именно, процент сходимости, доля реальных (глобальных, локальных) и ложных пиков; отметим, что доля пиков вычисляется только в случае сходимости алгоритма. Результаты. Выполнена программная реализация многонационального генетического алгоритма и проведена экспериментальная настройка его параметров. Предложены две модификации функции холмов и долин, используемой в алгоритме для определения взаимного расположения особей. Выполнен экспериментальный анализ многонационального генетического алгоритма с классической функцией холмов и долин и с ее модификациями. Выводы. Научная новизна работы состоит в том, что были предложены модификации функции холмов и долин, приводящие к меньшему количеству неправильных определений зон притяжения по сравнению с классическим вариантом этой функции. Как следствие, использование этих модификаций приводит к повышению производительности многонационального генетического алгоритма для ряда тестовых задач. Однако для некоторых тестовых задач улучшение критериев качества сопровождается уменьшением процента сходимости. В целом, процент сходимости и значения критериев качества, продемонстрированные исследуемым алгоритмом, недостаточны для практического использования многонационального генетического алгоритма по сравнению с другими известными алгоритмами. В то же время, использование модифицированных функций холмов и долин в качестве шага постобработки в других алгоритмах образования ниш представляется многообещающим подходом к улучшению производительности этих алгоритмов.
Актуальність. Генетичні алгоритми утворення ніш є одним з найпоширеніших підходів до розв’язання задач багатоекстремальної оптимізації. При проведенні класифікації цих алгоритмів можна виділити алгоритми, що ґрунтуються на явному аналізі топографії ландшафту функції пристосованості. Одним з ранніх прикладів таких алгоритмів є багатонаціональний генетичний алгоритм. Мета. Розробка та аналіз багатонаціонального генетичного алгоритму та його модифікацій. Алгоритм застосовується для розв’язання задачі пошуку всіх максимумів багатоекстремальної функції. Метод. Виконано експериментальний аналіз алгоритмів. Проведено численні прогони алгоритмів на відомих тестових задачах та обчислено критерії ефективності роботи алгоритмів, а саме, відсоток збіжності, частка реальних (глобальних, локальних) та хибних піків; зауважимо, що частки піків обчислюються тільки в разі збіжності алгоритму. Результати. Виконано програмну реалізацію багатонаціонального генетичного алгоритму та проведено експериментальне налаштування його параметрів. Запропоновано дві модифікації функції долин і пагорбів, яка використовується в алгоритмі для визначення взаємного розташування особин. Проведено експериментальний аналіз багатонаціонального генетичного алгоритму з класичного функцією долин і пагорбів та з її модифікаціями. Висновки. Наукова новизна роботи полягає в тому, що були запропоновані модифікації функції долин і пагорбів, які продукують меншу кількість помилкових ідентифікацій зон притягання порівняно з класичним варіантом цієї функції. Як наслідок, використання цих модифікацій призводить до покращення продуктивності багатонаціонального генетичного алгоритму для низки тестових задач. Втім, для деяких тестових задач поліпшення критеріїв якості супроводжується зменшенням відсотка збіжності. Загалом, відсоток збіжності та значення критеріїв якості, продемонстровані дослідженим алгоритмом, є недостатніми для практичного використання багатонаціонального генетичного алгоритму у порівнянні з іншими відомими алгоритмами. У той же час, використання модифікованих функцій долин і пагорбів як етапу постобробки в інших алгоритмах утворення ніш видається перспективним підходом до покращення роботи цих алгоритмів.
Актуальность. Генетические алгоритмы образования ниш являются одним из самых распространенных подходов к решению задач многоэкстремальной оптимизации. При проведении классификации генетических алгоритмов образования ниш можно выделить алгоритмы, основанные на явном анализе топографии ландшафта функции приспособленности. Многонациональный генетический алгоритм является одним из ранних примеров таких алгоритмов. Цель. Разработка и анализ многонационального генетического алгоритма и его модификаций. Алгоритм применяется для решения задачи поиска всех максимумов многоэкстремальной функции. Метод. Выполнен экспериментальный анализ алгоритмов. Проведены многочисленные прогоны алгоритмов на известных тестовых задачах и вычислены критерии эффективности работы алгоритмов, а именно, процент сходимости, доля реальных (глобальных, локальных) и ложных пиков; отметим, что доля пиков вычисляется только в случае сходимости алгоритма. Результаты. Выполнена программная реализация многонационального генетического алгоритма и проведена экспериментальная настройка его параметров. Предложены две модификации функции холмов и долин, используемой в алгоритме для определения взаимного расположения особей. Выполнен экспериментальный анализ многонационального генетического алгоритма с классической функцией холмов и долин и с ее модификациями. Выводы. Научная новизна работы состоит в том, что были предложены модификации функции холмов и долин, приводящие к меньшему количеству неправильных определений зон притяжения по сравнению с классическим вариантом этой функции. Как следствие, использование этих модификаций приводит к повышению производительности многонационального генетического алгоритма для ряда тестовых задач. Однако для некоторых тестовых задач улучшение критериев качества сопровождается уменьшением процента сходимости. В целом, процент сходимости и значения критериев качества, продемонстрированные исследуемым алгоритмом, недостаточны для практического использования многонационального генетического алгоритма по сравнению с другими известными алгоритмами. В то же время, использование модифицированных функций холмов и долин в качестве шага постобработки в других алгоритмах образования ниш представляется многообещающим подходом к улучшению производительности этих алгоритмов.
Description
Keywords
multimodal optimization problem, niching genetic algorithms, multinational genetic algorithm, hill-valley function, genetic algorithm convergence, real peak ratio, fake peak ratio, задача багатоекстремальної оптимізації, генетичні алгоритми утворення ніш, багатонаціональний генетичний алгоритм, функція долин і пагорбів, збіжність генетичного алгоритму, частка реальних піків, частка хибних піків, задача многоэкстремальной оптимизации, генетические алгоритмы образования ниш, многонациональный генетический алгоритм, функция холмов и долин, сходимость генетического алгоритма, доля реальных пиков, доля ложных пиков, article
Citation
Gulayeva N. M. Experimental analysis of multinational genetic algorithm and its modifications / Gulayeva N. M., Yaremko S. A. // Radio Electronics, Computer Science, Control. - 2021. - Issue 2. - P. 71-83. - https://doi.org/10.15588/1607-3274-2021-2-8