A NEW METHOD OF GROUPING VARIABLES FOR LARGE-SCALE GLOBAL OPTIMIZATION PROBLEMS

Full Text

Введение. Прикладные задачи глобальной опти- мизации с каждым годом становятся все сложнее. Большинство реальных задач оптимизации имеют большую размерность. Данный тип задач сложен для решения по ряду причин: пространство поиска увели- чивается экспоненциально по мере увеличения коли- чества переменных, свойства пространства поиска могут меняться, зачастую стоимость оценки решения высока. В 2002 году NASA опубликовало статью [1], где были продемонстрированы тенденции роста раз- мерности реальных задач глобальной оптимизации. Если раньше большая размерность в задачах глобаль- ной оптимизации означала пару десятков переменных, то сегодня их более тысячи. Существует множество проблем глобальной оптимизации большой размерно- сти из разных областей [2-5]: datamining, инженерия, нейроинформатика, химия и др. Стоит обратить внима- ние на то, что большинство реальных задач оптимиза- ции относятся к типу «черный ящик» (Black-Box (BB)). Особенность данного типа задач заключается в том, что мы не имеем информации о свойствах решаемой задачи, которые могут быть использованы при поиске глобального экстремума, мы можем получить только значения целевой функции f ( x ) для точки x из пространства поиска. При решении задач типа «черный ящик» свою эффективность продемонстрировали эво- люционные алгоритмы (ЭА) [6; 7]. Классическая задача оптимизации в общем случае может быть сформулирована следующим образом [8]: Î f ( x ) = f ( x1, x2,..., xn ) ® min/ max , (1) x X i i i xL £ x £ xU , i =1, n , (2) зано, что наилучшие результаты для задач LSGO дос- тигаются в классе бионических алгоритмов прямого поиска. В частности, высокую эффективность демон- стрируют различные эволюционные алгоритмы. Подходы к решению задачи LSGO на основе эволюционных алгоритмов 1. Дифференциальная эволюция (Differential Evo- lution). Storn и Price представили оригинальный под- ход для параметрической оптимизации в 1995 году, он получил название Differential Evolution (DE) [10]. DE является разновидностью эволюционного алго- ритма, поэтому в ходе его работы используется ите- рационная процедура, которая состоит из повторяю- щегося применения операторов мутации, скрещива- ния, селекции. Более детально с данным алгоритмом можно ознакомиться в [11]. 2. Самонастраивающаяся дифференциальная эво- люция с поиском в окрестности (Self-adaptive differen- tial evolution with neighborhood search (SaNSDE)). SaNSDE - самонастраивающаяся дифференциальная эволюция с поиском в окрестности [12]. На основе классического алгоритма DE в 2008 году была пред- ложена его модификация. Данный алгоритм был вы- бран по той причине, что в нем присутствует самона- стройка его параметров в ходе работы. Это очень важно, так как эффективность работы любого ЭА на- прямую зависит от выбранных параметров. Для DE основными параметрами являются тип мутации, F, CR. F - параметр, характеризующий максимально возможное расстояние, на которое может расширить- ся область поиска оптимума по одной переменной за один шаг эволюции. Зачастую значения параметра F находятся в интервале [0; 2]. CR - параметр, отве- g j ( x1, x2,..., xn ) £ 0, j = 1, m , (3) hk ( x1, x2,..., xn ) = 0, k = 1, l . (4) В уравнении (1) f обозначает целевую функцию, X является допустимым множеством решений, n - целое число, обозначающее размерность задачи оптимиза- ции. В уравнении (2) xiL и xiU обозначают нижнюю и верхнюю границу интервала поиска соответственно. Уравнения (3) и (4) обозначают ограничения типа неравенства и равенства соответственно. В данной статье рассматриваются задачи безусловной оптими- зации, на которые не накладываются ограничения типа (3) и (4). Задачи глобальной параметрической оптимизации моделей типа «черный ящик», в которых число пере- менных равно 1000 и более, принято называть зада- чами глобальной оптимизации большой размерности (Large-Scale Global Optimization (LSGO)). В [9] покачающий за частоту скрещивания: чем выше его зна- чение, тем больше переменных решения будут заме- щены новыми мутантными значениями, значения CR находятся в интервале [0; 1]. Особенность алгоритма SaNSDE заключается в том, что алгоритм фиксирует успешное и неуспешное применение того или иного типа мутации, значения параметров F, CR, после оп- ределенного количества поколений пересчитывает вероятность выбора типа мутации, значения CR и зна- чения F. 3. Кооперативная коэволюция (Cooperative Coevo- lution). Одним из наиболее известных и часто приме- няемых подходов для решения задач большой размерности является декомпозиция на основе метода кооперативной коэволюции. Кооперативная коэволюция (Cooperative Coevolu- tion (CC)) является эволюционной структурой (рис. 1), которая делит вектор задачи оптимизации на несколь- ко субкомпонентов и оптимизирует их независимо с помощью ЭА (до момента кооперации) для решения задачи оптимизации. Впервые данный метод предло- жили Potter и De Jong [13] применительно к генетиче- скому алгоритму. CC на сегодняшний день является эффективным инструментом при решении сепара- бельных задач оптимизации большой размерности. Ниже представлен псевдокод кооперативной коэво- люции: Псевдокод кооперативной коэволюции 1: Произвести декомпозицию целевого вектора на m суб- компонентов меньшей размерности; 2: Присвоить i = 1 и начать новый цикл; 3: Оптимизировать i-ю субкомпоненту с помощью ЭА; 4: Если i < m, i = i+1 и перейти к шагу 3, иначе к шаг 5; 5: Остановить алгоритм, если условие остановки вы- полнено, иначе перейти к шагу 2 для следующего цикла. Стоит заметить, что на сегодняшний день сущест- вует множество подходов, направленных на решение задач оптимизации большой размерности. Данные подходы можно разделить на две группы: подходы с использованием CC и подходы, не использующие декомпозицию вектора решения. Большую эффектив- ность имеют те методы, которые используют CC для решения задачи оптимизации. При использовании CC появляются следующие новые задачи: выбор количе- ства субкомпонентов (на сколько частей делить век- тор решения), выбор размера каждой субкомпоненты и какие переменные объединять в одну группу. В связи с этим сегодня популярны следующие группировки, используемые в CC: группировка, где заранее задает- ся условие, по которому происходит группировка (static grouping) [14], динамическая случайная груп- пировка переменных (random dynamic grouping) [15], адаптивная группировка (learning dynamic grouping) [16], где проводится серия экспериментов по прира- щению значений каждой переменной, на основании полученных результатов переменные группируются. DECC-RAG алгоритм. Сведения, изложенные выше, послужили основой для разработки нового ЭА для решения задач оптимизации большой размерно- сти. Главная идея алгоритма заключается в использо- вании оригинального метода группировки перемен- ных для эволюционной структуры CC с самонастраи- вающимся ЭА (SaNSDE). Самонастройка необходима, так как решаемая задача оптимизации представлена в виде модели «чёрный ящик», мы не знаем функцио- нальной зависимости между переменными, следова- тельно, параметры должны адаптироваться во время работы алгоритма. Подход CC является эффективным, но только в том случае, если правильно сгруппировать перемен- ные. Было решено, что в основе метода группировки переменных должна присутствовать случайность, так как при использовании группировки типа learning dynamic grouping не всегда удается разделить пере- менные на истинное количество субкомпонент [16], но при этом будет затрачено большое количество ре- сурсов (вычисление функции пригодности) в ходе выделения субкомпонентов. Рис. 1. Схематичное представление работы кооперативной коэволюции Fig. 1. Schematic representation of cooperative coevolution Помимо этого, может случиться так, что перемен- ные сгруппируются верно, но оставшееся количество вычислений функции останется малым - внушитель- ная часть бюджета вычислений уходит на группировку переменных. Количество группируемых переменных должно быть одинаковым для каждой субкомпонен- ты, данное решение было принято по причине того, что иначе придётся решать следующие дополнитель- ные задачи: 1. Выбор различного количества индивидов. Например, для ЭА, оптимизирующего субкомпоненты вектора решения, состоящие из 5 переменных и 500 переменных, необходимо разное количество индивидов в популяции. Получается неравномерное распределение ресурсов алгоритма. 2. Минимальное и максимальное количество груп- пируемых переменных. Как упоминалось неодно- кратно выше, задача глобальной оптимизации пред- ставлена в виде модели типа «чёрный ящик», т. е. неизвестно, какое значение выбирать в качестве ми- нимального и максимального размера группы. Предложенный оригинальный метод группировки Random Adaptive Grouping (RAG) работает следую- щим образом: D-мерный вектор решения разбивается на m s-мерных субкомпонент. Случайно, по равно- мерному закону распределения группируем перемен- ные в одинаковые группы. Так как мы изначально не знаем, насколько хорошо себя показала та или иная группировка, необходимо провести определенное ко- личество вычислений функции пригодности T (запус- тить работу ЭА на каждой субкомпоненте), после че- го найти m/2 субкомпонент с худшими значениями функции пригодности индивидов-представителей, по равномерному закону распределения случайно пере- группировать переменные в данных группах. Далее нужно произвести сброс параметров ЭА в худших m/2 субкомпонентах после перегруппировки пере- менных, это делается из-за того, что после перегруп- пировки переменных конкретному ЭА необходимо будет уже решать совершенно другую задачу. Данный метод группировки переменных получил название RAG, а алгоритм, разработанный на его основе - DECC-RAG. Псевдокод алгоритма DECC-RAG пред- ставлен ниже: FEV_local и FEV_global - счетчики для оценки функции пригодности внутри адаптационного перио- да и для всего алгоритма соответственно. В нашем случае мы использовали следующие значения пара- метров алгоритма: NP = 50 (размер популяции для каждой субкомпоненты), m = 10, T = 3 ´ 105. T - параметр, который представляет собой количество FEVs (оценок функций) перед случайным перемеши- ванием худших m/2 субкомпонент. Описание эталонных тестовых задач и крите- риев оценки эффективности алгоритмов LSGO. Алгоритмы DE, SaNSDE и DECC-RAG тестировались на 20 тестовых функциях большой размерности из набора IEEE (The Institute of Electrical and Electronic Engineers) LSGO (Large-Scale Global Optimization) CEC’2010 (Congress on Evolutionary Computation) [17] и 15 тестовых функциях большой размерности из на- бора IEEE LSGO CEC’2013 [18]. Данные тестовые функции специально были наделены свойствами, ко- торые присущи реальным задачам оптимизации большой размерности. Полученные результаты работы алгоритмов (DE, SaNSDE, DECC-RAG) на задачах LSGO CEC’2010 и LSGO CEC’2013 сравнивали с результатами работы известных алгоритмов оптимизации (DMS-L-PSO [19], DECC-G [15], MLCC [20], DECC-DG [16]) для задач большой размерности. Результаты работы DMS-L-PSO, DECC-G, MLCC, DECC-DG на задачах из LSGO CEC’2010 и LSGO CEC’2013 были взяты из [21]. Для проведения экспериментов использовались правила соревнования LSGO CEC’2010 и LSGO CEC’2013, а именно: - размерность тестовых задач оптимизации D = 1000; - количество независимых запусков алгоритма для каждой тестовой задачи равно 25; - количество вычислений функции пригодности в каждом независимом запуске 3 × 106; - после проведения 25 независимых запусков для тестовой функции вычисляется медианное значение (Median) и среднеквадратическое отклонение (Std). Программная реализация алгоритмов (DE, SaNSDE и DECC-RAG) осуществлялась в среде раз- Псевдокод алгоритма DECC-RAG 1: Задать FEV_global, T, FEV_local = 0; 2: n-мерный целевой вектор случайно разделить на m s-мерных субкомпонент; 3: Случайно перемешать индексы всех переменных; 5: 4: i = 1; Эволюционировать i-ю субкомпоненту, ис- пользуя SaNSDE; 6: Если i < m, то i++ и перейти к шагу 5, иначе - к шагу 7; 7: Найти best_solutioni для каждой субкомпоненты; 8: Если (FEV_local < T), то перейти к шагу 4, иначе - к шагу 9; 9: Найти m/2 субкомпонент с худшими значениями целе- вой функции и случайно перемешать индексы перемен- ных в данных субкомпонентах, обновить значения пара- метров SaNSDE в данных m/2 субкомпонентах, FEV_local = 0; 10: Если (FEV > 0), то перейти к шагу 4, иначе - к шагу 11; 11: Произвести возврат лучшего найденного значения (best_solution). работки приложений Visual Studio - 2015 на языке программирования C++. В ходе проведения экспери- ментов значительное время тратится на вычисление функций пригодности. Тестирование алгоритмов про- водилось с использованием параллельных вычисле- ний с помощью технологии OpenMP. Результаты численных экспериментов. В табл. 1, 2 приведено время (в секундах), затраченное на вычис- ление 10 000 раз данной тестовой функции на 1 потоке на процессоре AMD Ryzen 71700x. При проведении экспериментов использовался 16-поточный процессор для распараллеливания экспериментов - каждая тестовая функция вычислялась на отдельном потоке. Если не использовать данный прием, то только на разрешенное правилами конкурса количество вычис- лений функции пригодности в рамках данной работы потребовалось бы порядка 847,6 ч (35,5 дня). В нашем случае время удалось сократить до 80,3 ч. В табл. 3, 4 продемонстрированы результаты работы алгоритмов на тестовых функциях из набора LSGO CEC’2010 и LSGO CEC’2013 соответственно. Первый столбец обозначает номер тестовой функции, последующие столбцы - результаты работы того или иного алгоритма. В каждой ячейке таблицы содержатся два значения - медианное и среднеквадратическое откло- нение, которые получены по результатам 25 незави- симых запусков. Таблица 1 Время вычисления 10 000 функций пригодности в секундах на задачах из набора LSGO CEC’2010 Func. № Время F1 0,396 F2 0,209 F3 0,21 F4 0,52 F5 0,334 F6 0,34 F7 0,309 F8 0,307 F9 1,312 F10 1,134 Func. № Время F11 1,139 F12 0,112 F13 0,126 F14 2,219 F15 2,016 F16 2,04 F17 0,077 F18 0,133 F19 0,072 F20 0,1 Таблица 2 Время вычисления 10 000 функций пригодности в секундах на задачах из набора LSGO CEC’2013 Func. № Время F1 7,76 F2 8,08 F3 8,1 F4 8,36 F5 8,76 F6 8,88 F7 3,19 F8 10,17 F9 10,59 F10 10,62 Func. № Время F11 10,1 F12 0,126 F13 10,04 F14 10,03 F15 7,71 - - - - - - - - - - Таблица 3 Результаты численных экспериментов алгоритмов на задачах (F1-F20) из набора LSGO CEC’2010, D = 1000 № func DECC-RAG DE SaNSDE DMS-L-PSO DECC-G MLCC DECC-DG F1 2,69E-18 5,10E-18 4,19E+08 2,75E+08 2,00E+04 2,04E+06 1,61E+07 1,41E+06 3,53E-07 1,44E-07 1,66E-14 2,97E-12 1,42E+02 4,66E+04 F2 7,33E+02 7,52E+01 7,38E+03 3,02E+02 2,80E+03 1,67E+02 5,53E+03 5,38E+02 1,32E+03 2,55E+01 2,43E+00 1,52E+00 4,46E+03 1,87E+02 F3 1,64E+00 1,77E-01 1,95E+01 8,60E-02 1,47E+01 4,31E-01 1,56E+01 1,08E-01 1,14E+00 3,35E-01 6,24E-10 1,12E-06 1,66E+01 3,02E-01 F4 9,50E+11 3,50E+11 8,78E+12 3,43E+12 2,82E+12 1,01E+12 4,32E+11 8,05E+10 2,46E+13 8,14E+12 1,78E+13 5,47E+12 5,08E+12 1,89E+12 F5 1,54E+08 4,41E+07 7,96E+07 2,12E+07 9,00E+07 8,22E+06 9,35E+07 9,04E+06 2,50E+08 6,84E+07 5,11E+08 1,07E+08 1,52E+08 2,15E+07 F6 2,04E+01 5,75E+06 2,09E+01 6,84E+06 1,27E+06 8,12E+05 3,66E+01 1,21E+01 4,71E+06 1,03E+06 1,97E+07 4,37E+06 1,64E+01 3,45E-01 F7 2,90E+02 8,22E+02 3,08E+08 1,76E+08 1,90E+05 6,18E+04 3,47E+06 1,16E+05 6,57E+08 5,40E+08 1,15E+08 1,45E+08 9,20E+03 1,26E+04 F8 1,78E+07 7,43E+08 2,53E+08 3,88E+08 8,16E+06 2,22E+07 2,02E+07 1,88E+06 9,06E+07 2,64E+07 8,82E+07 3,40E+07 1,62E+07 2,63E+07 F9 6,17E+07 8,72E+06 5,56E+08 8,20E+07 2,31E+08 9,95E+07 2,08E+07 1,58E+06 4,35E+08 4,87E+07 2,48E+08 2,16E+07 5,52E+07 6,45E+06 F10 3,25E+03 1,88E+02 7,72E+03 2,47E+02 9,40E+03 2,82E+02 5,09E+03 4,26E+02 1,02E+04 3,13E+02 3,97E+03 1,45E+03 4,47E+03 1,29E+02 F11 2,16E+02 1,31E+01 1,88E+02 6,40E+00 1,74E+02 1,51E+01 1,68E+02 1,90E+00 2,59E+01 1,73E+00 1,98E+02 1,12E+00 1,02E+01 8,71E-01 F12 8,88E+03 1,15E+03 5,59E+05 6,91E+04 4,03E+05 4,83E+04 2,83E+01 9,88E+00 9,69E+04 9,55E+03 1,01E+05 1,57E+04 2,58E+03 1,08E+03 F13 1,56E+03 3,81E+03 1,01E+09 6,79E+08 2,52E+04 1,61E+05 1,03E+05 6,18E+04 4,59E+03 4,16E+03 2,12E+03 4,70E+03 5,06E+03 3,65E+03 F14 2,01E+08 2,07E+07 1,60E+09 1,52E+08 7,78E+08 1,28E+08 1,25E+07 1,62E+06 9,72E+08 7,52E+07 5,71E+08 5,50E+07 3,46E+08 2,42E+07 F15 5,16E+03 3,60E+02 7,75E+03 2,55E+02 1,06E+04 4,34E+02 5,48E+03 3,46E+02 1,24E+04 8,24E+02 8,67E+03 2,07E+03 5,86E+03 1,05E+02 F16 4,13E+02 3,05E+01 3,77E+02 4,32E+00 3,73E+02 1,12E+01 3,18E+02 2,04E+00 6,92E+01 6,43E+00 3,96E+02 5,76E+01 7,50E-13 6,25E-14 F17 1,68E+05 1,17E+04 1,04E+06 7,94E+04 8,68E+05 6,84E+04 4,75E+01 1,15E+01 3,11E+05 2,24E+04 3,47E+05 3,11E+04 4,02E+04 2,29E+03 F18 4,96E+03 6,35E+03 4,15E+10 1,70E+10 5,83E+05 1,81E+08 2,50E+04 1,10E+04 3,54E+04 1,53E+04 1,59E+04 9,48E+03 1,47E+10 2,03E+09 F19 2,23E+06 1,93E+05 2,96E+06 4,01E+05 1,93E+06 1,89E+05 2,03E+06 1,41E+05 1,14E+06 6,23E+04 2,04E+06 1,42E+05 1,75E+06 1,10E+05 F20 1,84E+03 5,04E+02 5,25E+10 1,58E+10 2,80E+05 1,37E+07 9,82E+02 1,40E+01 4,34E+03 8,25E+02 2,27E+03 2,26E+02 6,53E+10 6,97E+09 Таблица 4 Результаты численных экспериментов алгоритмов на задачах (F1-F15) из набора LSGO CEC’2013, D = 1000 № func DECC-RAG DE SaNSDE DMS-L-PSO DECC-G MLCC DECC-DG F1 1,88E-16 3,11E-16 5,28E+08 2,92E+08 8,53E+05 8,25E+06 1,97E+09 1,27E+08 2,06E-06 4,27E-06 9,07E-14 4,38E-09 6,03E+02 1,81E+04 F2 1,40E+03 1,39E+02 2,46E+04 1,72E+03 2,06E+04 8,50E+02 8,61E+03 4,88E+02 1,30E+03 3,63E+01 3,57E+00 1,73E+00 1,28E+04 7,20E+02 F3 2,03E+01 2,33E-02 2,16E+01 6,07E-03 2,10E+01 8,05E-02 2,08E+01 1,66E-01 2,02E+01 6,18E-03 2,00E+01 2,76E-04 2,14E+01 1,45E-02 F4 1,11E+10 7,50E+09 1,11E+11 3,43E+10 2,93E+10 1,13E+10 2,97E+11 7,25E+10 2,00E+11 1,22E+11 1,99E+11 1,26E+11 7,33E+10 2,82E+10 F5 3,50E+06 7,09E+05 4,62E+06 7,57E+05 4,88E+06 5,29E+05 3,92E+06 5,82E+05 8,44E+06 1,14E+06 1,17E+07 3,46E+06 5,81E+06 3,83E+05 F6 1,06E+06 8,62E+02 1,06E+06 1,36E+03 1,06E+06 1,34E+03 9,98E+05 5,20E+03 1,06E+06 1,84E+03 1,05E+06 4,13E+03 1,06E+06 1,07E+03 F7 2,40E+08 3,68E+08 1,04E+09 6,95E+08 2,20E+08 1,88E+08 1,22E+09 7,64E+08 1,04E+09 4,48E+08 1,15E+09 1,07E+09 4,25E+08 1,92E+08 F8 4,76E+14 1,89E+14 2,15E+15 1,04E+15 2,26E+14 1,32E+14 1,68E+14 5,09E+14 7,90E+15 3,18E+15 8,18E+15 6,18E+15 2,89E+15 1,85E+15 F9 2,32E+08 5,21E+07 4,27E+08 6,45E+07 4,81E+08 4,69E+07 3,50E+08 4,61E+07 5,86E+08 9,76E+07 8,85E+08 2,92E+08 4,95E+08 3,18E+07 F10 9,42E+07 5,91E+05 9,42E+07 1,85E+05 9,40E+07 2,51E+05 9,11E+07 1,06E+06 9,30E+07 6,16E+05 9,27E+07 6,07E+05 9,45E+07 2,46E+05 F11 3,45E+09 6,42E+10 2,50E+11 1,95E+11 3,18E+09 1,12E+10 9,44E+10 7,53E+10 1,26E+11 7,15E+10 1,90E+11 1,53E+11 3,81E+10 4,33E+10 F12 1,82E+03 3,85E+02 4,64E+10 1,61E+10 1,49E+07 3,79E+08 5,22E+04 5,52E+04 4,19E+03 7,83E+02 2,36E+03 7,51E+02 1,68E+11 2,24E+10 F13 7,19E+09 4,77E+09 1,52E+10 4,47E+09 6,92E+09 3,15E+09 1,32E+10 6,58E+09 8,67E+09 2,78E+09 9,94E+09 3,73E+09 2,08E+10 5,53E+09 F14 3,80E+10 6,70E+10 3,42E+11 1,54E+11 5,27E+10 3,39E+10 2,21E+11 1,26E+11 1,28E+11 5,86E+10 2,06E+11 8,54E+10 1,56E+10 1,44E+10 F15 1,59E+07 4,50E+07 7,32E+09 2,13E+11 6,12E+07 4,13E+07 1,54E+07 3,45E+06 1,13E+07 1,26E+06 1,57E+07 1,90E+06 9,52E+06 2,30E+06 Произведем попарное сравнение независимых вы- борок (лучших найденных значений в 25 независимых запусках), используя критерий Уилкоксона - непара- метрический статистический тест, используемый для проверки статистических различий между двумя не- зависимыми выборками. В табл. 5, 6 занесены резуль- таты теста статистической значимости различий между результатами работы алгоритмов DECC-RAG vs DE и DECC-RAG vs SaNSDE на тестовых функциях из набора LSGO CEC’2010 соответственно. В табл. 7, 8 занесены результаты теста на статистическую значи- мость различий между результатами работы алгорит- мов DECC-RAG vs DE и DECC-RAG vs SaNSDE на тестовых функциях из набора LSGO CEC’2013 соот- ветственно. Если в соответствующей ячейке (табл. 5-8) стоит знак «+», то это означает, что результаты рабо- ты алгоритмов статистически различны и лучшее найденное медианное решение - у первого алгоритма, если стоит знак «-», то это означает, что результаты работы алгоритмов статистически различны и лучшее найденное медианное решение - у второго алгоритма, если стоит знак «≈» - результаты работы алгоритмов статистически не различаются на данной тестовой функции. На рис. 2-4 продемонстрированы графики, на ко- торых отражены усредненные результаты работы алгоритмов DE, SaNSDE и DECC-RAG на некоторых (1, 2, 9, 12, 14, 18) тестовых функциях из набора LSGO CEC’2010: по оси абсцисс - количество вычис- лений функции пригодности, по оси ординат - сред- нее значение функции пригодности. На рис. 5 и 6 продемонстрированы результаты работы алгоритмов DE, SaNSDE и DECC-RAG на некоторых тестовых функциях (1, 2, 3, 12) из набора LSGO CEC’2013. На рис. 7 и 8 в виде столбчатых диаграмм отображен средний ранг алгоритмов по всем тестовым функциям из эталонных наборов LSGO CEC’2010 и LSGO CEC’2013 соответственно. Ранг вычислялся по меди- анным результатам из табл. 3 и 4 в зависимости от места, которое занял алгоритм на той или иной функ- ции: чем меньше медианное значение, тем меньше значение ранга. На двух эталонных наборах предло- женный алгоритм DECC-RAG имеет наименьший средний ранг. Анализируя полученные численные результаты работы алгоритма DECC-RAG (рис. 7, 8), можно за- ключить, что он превосходит некоторые известные алгоритмы глобальной оптимизации большой размер- ности (DMS-L-PSO, DECC-G, MLCC, DECC-DG) на 20 эталонных тестовых функциях из набора LSGO CEC’2010 и 15 эталонных функциях из набора LSGO CEC’2013. Статистической значимости различий между результатами работы алгоритмов не наблюдается на F6 из LSGO CEC’2010 у DECC-RAG vs SaNSDE, на F6 у DECC-RAG vs DE и на F7, F10, F11 из LSGO CEC’2013. На всех остальных тестовых функциях наблюдает- ся статистическая значимость различий между ре- зультатами работы алгоритмов. Статистическая значимость работы алгоритмов (DECC-RAG vs DE) на 20 тестовых функциях LSGO CEC’2010 Таблица 5 F1 + F2 + F3 + F4 + F5 - F6 + F7 + F8 + F9 + F10 + F11 - F12 + F13 + F14 + F15 + F16 + F17 + F18 + F19 + F20 + Статистическая значимость работы алгоритмов (DECC-RAG vs SaNSDE) на 20 тестовых функциях LSGO CEC’2010 Таблица 6 F1 + F2 + F3 + F4 + F5 - F6 ≈ F7 + F8 - F9 + F10 + F11 + F12 + F13 + F14 + F15 + F16 - F17 + F18 + F19 - F20 + Статистическая значимость работы алгоритмов (DECC-RAG vs DE) на 15 тестовых функциях LSGO CEC’2013 Таблица 7 F1 + F2 + F3 + F4 + F5 + F6 ≈ F7 + F8 + F9 + F10 + F11 + F12 + F13 + F14 + F15 + - - Статистическая значимость работы алгоритмов (DECC-RAG vs SaNSDE) на 15 тестовых функциях LSGO CEC’2013 Таблица 8 F1 + F2 + F3 + F4 + F5 + F6 + F7 ≈ F8 - F9 + F10 ≈ F11 ≈ F12 + F13 - F14 + F15 + - - Рис. 2. Сходимость DE, SaNSDE и DECC-RAG на задачах (№ 1, 2) из набора LSGO CEC’2010 Fig. 2. The convergence graphs of DE, SaNSDE and DECC-RAG applied to F1, F2 from LSGO CEC’2010 Рис. 3. Сходимость DE, SaNSDE и DECC-RAG на задачах (№ 9, 12) из набора LSGO CEC’2010 Fig. 3. The convergence graphs of DE, SaNSDE and DECC-RAG applied to F9, F12 from LSGO CEC’2010 Рис. 4. Сходимость DE, SaNSDE и DECC-RAG на задачах (№ 14, 18) из набора LSGO CEC’2010 Fig. 4. The convergence graphs of DE, SaNSDE and DECC-RAG applied to F14, F18 from LSGO CEC’2010 Рис. 5. Сходимость DE, SaNSDE и DECC-RAG на задачах (№ 1, 2) из набора LSGO CEC’2013 Fig. 5. The convergence graphs of DE, SaNSDE and DECC-RAG applied to F1, F2 from LSGO CEC’2013 Рис. 6. Сходимость DE, SaNSDE и DECC-RAG на задачах (№ 3, 12) из набора LSGO CEC’2013 Fig. 6. The convergence graphs of DE, SaNSDE and DECC-RAG applied to F3, F12 from LSGO CEC’2013 Рис. 7. Средний ранг алгоритмов на LSGO CEC’2010 Fig. 7. Average rank of algorithms on LSGO CEC’2010 Рис. 8. Средний ранг алгоритмов на LSGO CEC’2013 Fig. 8. Average rank of algorithms on LSGO CEC’2013 Заключение. В данной статье предлагается новый эволюционный алгоритм, названный DECC-RAG, для задач глобальной оптимизации большой размерности. В основе предложенного алгоритма лежит случайная адаптивная группировка переменных для структуры кооперативной коэволюции. В качестве ЭА, который оптимизирует каждую субкомпоненту, мы применили эффективный самонастраивающийся эволюционный алгоритм SaNSDE. Тестирование эффективности DECC-RAG прово- дилось на эталонных задачах из наборов LSGO CEC’2010 и LSGO CEC’2013. Алгоритм DECC-RAG превзошел некоторые известные алгоритмы, которые специально разрабатывались для задач глобальной оптимизации большой размерности. В дальнейших работах будет ставиться вопрос об улучшении эффек- тивности предложенного алгоритма DECC-RAG для задач глобальной оптимизации большой размерности.

About the authors

A. V. Vakhnin

Reshetnev Siberian State University of Science and Technology

Email: alexeyvah@gmail.com
31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

E. A. Sopov

Reshetnev Siberian State University of Science and Technology

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

References

Supplementary files