Удивительное путешествие Нильса с дикими гусями по стране алгоритмов оптимизации

За 16 лет существования Хабра на его страницах не один, и даже не тысячу раз публиковались статьи, так или иначе касающиеся вопросов решения задач оптимизации и алгоритмов в целом. В этой статье я хочу рассказать о достаточно новом алгоритме — «алгоритме диких гусей».

Во многих приложениях для решения задач численной оптимизации применяются природные популяционные алгоритмы. На Хабре уже упоминались некоторые из них (например, алгоритм, основанный на поведении косяка рыб). В этой статье основное внимание уделяется простому и мощному алгоритму «диких гусей» (WGA, Wild Geese Algorithm) для решения задач крупномасштабной глобальной оптимизации (LSGO, Large Scale Global Optimization), эффективность и производительность которого проверяются с использованием тестовых функций.

WGA инспирирован поведением диких гусей в природе и моделирует различные аспекты их жизни. Эффективность WGA для поиска глобальных оптимальных решений задач оптимизации высокой размерности сравнивается с эффективностью некоторых известных алгоритмов.

Проблемы оптимизации в реальном мире часто имеют высокую сложность и размерность и называются проблемами LSGO, то есть крупномасштабной глобальной оптимизации.

Многие научные и инженерные задачи, решаемые с помощью алгоритмов, несут в себе характерные проблемы LSGO. Такими задачами являются проектирование сложных электронных систем, задачи планирования с большим количеством ресурсов, логистика, проблемы маршрутизации в сетях, распознавание генов в биоинформатике, химическая динамика и др.

Основные проблемы LSGO:
- пространство поиска увеличивается экспоненциально с увеличением числа переменных решения;
- метаэвристические алгоритмы обычно требуют слишком больших вычислительных ресурсов;
- метод CC, основанный на идее «разделяй и властвуй», требует дополнительного изучения взаимовлияния переменных;
- избыточность и нерелевантность многомерных характеристик снижает эффективность и производительность алгоритмов.

Характерные особенности алгоритма

Нильс и сам не знал, как ему удалось перебраться на спину Мартина. Никогда Нильс не думал, что гуси такие скользкие… 

Практические задачи крупномасштабной глобальной оптимизации (LSGO), имеют дело с множеством переменных. Некоторые практические проблемы таких задач — это проектирование сложных электронных систем, стратегическое планирование, маршрутизация и логистика средств в транспортных сетях, обратная задача химической кинетики (раздел 1.4 по ссылке) и многие другие.

Классические методы математического программирования, как правило, не дают удовлетворительных результатов задач оптимизации из-за большой их размерности. В последние годы было представлено множество метаэвристических алгоритмов оптимизации, вдохновленных природой и основанных на популяционных алгоритмах, для решения проблем LSGO (DECC-D, DECC-DG, CCPSO2, LSCBO, ISSA и другие). Алгоритм диких гусей один из таких.

Дикие гуси совершают дальние, скоординированные и организованные перелёты. На основе общей модели жизнедеятельности этих птиц и разработан алгоритм. По сравнению с другими алгоритмами, WGA достаточно прост в реализации и не требователен к вычислительным ресурсам, при этом демонстрирует удивительную эффективность для различных тестовых функций.

Стоит отметить, что, хотя алгоритм WGA может показаться похожим на метод роя частиц (PSO), особенно из-за существования концепций личного лучшего и глобального лучшего, он имеет существенные различия в структуре и формулировках, основные из которых ниже:

1. Все решения сортируются на основе их объективных значений, так что каждый «гусь» (член совокупности) перемещается, используя информацию от соседних «гусей» в отсортированной совокупности.

2. Формулировка расчета скорости каждого «гуся» полностью отличается от PSO и основана на позициях, скоростях и лучших позициях «гуся» и соседних с ним «гусей» в отсортированной популяции, а также на глобальном лучшем. В то время как в PSO единственным параметром, общим для всех решений, является позиция глобального лучшего решения.

3. Генерируются два различающихся решения для каждого случая, которые используются для следующей итерации на основе механизма, аналогичного оператору кроссовера дифференциальной эволюции.

4. В алгоритме реализуется политика сокращения популяции, которая осуществляется за счет исключения самого слабого «гуся» популяции.

В целом, предлагаемые этапы WGA следующие:

1. Упорядоченная и скоординированная групповая миграция (или фаза скорости миграции и перемещения).

2. Поиск пищи.

3. Размножение и эволюция.

4. Гибель и упорядоченная эволюция.

Для начала определим переменные в исходной популяции. За вектор положения i-го «гуся» примем x_i, наилучшее локальное положение или личное лучшее решение – p_i  и скорость миграции (векторная скорость) – v_i. Затем все «гуси» популяции сортируются от лучшего к худшему в соответствии с их целевой функцией.

В этой стратегии моделирования каждый член упорядоченной популяции использует данные соседей и зависит от них.

Миграция

Наша стая не может принимать к себе первых встречных. Все, кого ты видишь перед собой, принадлежат к лучшим гусиным семействам. А ты даже летать как следует не умеешь. Что ты за гусь, какого роду и племени?

Как видно из рис. 1, миграция гусей представляет собой групповое, скоординированное, упорядоченное и контролируемое системное перемещение, строго распределенное от лидера к самому слабому члену популяции. Уравнения скорости и смещения ниже (1),(2).

где x_i,d, p_i,d  и v_i,d — d-е значение текущего положения, наилучшее локальное положение и текущая скорость i-го гуся соответственно. Обратите внимание, что в этом исследовании r_k,d — равномерно распределенные случайные числа в интервале от 0 до 1.

Как видно из формулы (1) скорость и изменение положения каждого «гуся» зависят от скоростей переднего и заднего соседа, т. е. (v_i+1^Iter- v_i-1^Iter), а также от позиции смежной птицы.

Согласно модели миграции на рис. 2 и уравнению (1), птицы используют информацию от соседствующих с ними особей в отсортированной популяции в качестве шаблонов для своего движения и навигации и, как правило, сокращают расстояние до них.

Кроме того, член совокупности, занимающий наилучшее локальное положение используется в качестве еще одного ориентира для всей стаи, что отражено в уравнении (2).

где g_d – глобальная лучшая позиция среди всех участников.

Поиск пищи

Этот шаг моделируется таким образом, что i-й гусь движется к своему переднему товарищу, то есть (i+1)-му гусю (p_i^Iter→ p_i+1^Iter).

Другими словами, i-й гусь пытается добраться до (i+1)-го гуся (p_i+1^Iter- p_i^Iter). Уравнение поиска пищи диким гусем x_i^W, выглядит следующим образом:

Размножение и эволюция

Другой этап жизни диких гусей — размножение и эволюция. В данной работе его моделирование выполнено таким образом, что используется комбинация уравнения миграции x_i^V и уравнения поиска пищи x_i^W. Значение Cr для упрощения моделирования с помощью алгоритма WGA принято за 0,5 во всех симуляциях (об этом чуть ниже).

Гибель и упорядоченная эволюция

Предыдущие исследования показывают, что для разных алгоритмов оптимизации размер популяций и количество итераций не имеют одинакового уровня влияния на решение всех типов задач. Для некоторых функций размер популяции важнее и эффективнее, чем количество итераций алгоритма, а для других функций наоборот.

Чтобы сбалансировать производительность алгоритма для всех тестовых функций, используется фаза смерти. На этом этапе алгоритм начинается с максимального числа популяций Np^initial , и во время итераций алгоритма более слабые члены будут удалены из популяции на основе уравнения (5) и размер популяции будет уменьшаться линейно, так что он достигнет своего конечного значения Np^final на последней итерации.

где FEs и FEs_max — количество вычислений функции и их максимум.

Теоретические испытания

Он должен знать, что летать быстро легче, чем летать медленно! Он должен знать, что летать высоко легче, чем летать низко! Кто не может летать, как мы, пусть сидит дома! Скажите это белому!

В ходе экспериментальных оценочных исследований работы алгоритма использовались двадцать широко используемых тестовых функций, чтобы продемонстрировать его эффективность и производительность. Формулировки и характеристики всех тестовых функций перечислены здесь.

Производительность и надежность алгоритма для решения задач оптимизации характеризуются двумя показателями:

1. средним значением наилучших значений тестовой функции,

2. показателями стандартного отклонения.

Тестовые функции включают в себя:

• сепарабельные функции (F1-F3),

• одногрупповые m-несепарабельные функции (F4-F8),

• D/2m-групповые m-несепарабельные функции (F9-F13),

• D/m-групповые m-несепарабельные функции (F14-F18),

• неразделимые функции (F19-F20).

где m — количество переменных в каждом неотделимом подкомпоненте, а D и m взяты равными 1000 и 50 соответственно. Чтобы показать эффективность WGA, во всех симуляциях в этой статье используется 25 независимых симуляций в каждом разделе для каждой тестовой функции.

Сепарабельность функции (separability of function) — в случае функции нескольких переменных (аргументов) — возможность разделения влияния аргументов на общий результат.

Чтобы оценить влияние фазы смерти на производительность WGA и показать ее эффективность, алгоритм был дважды протестирован без ее учета с большой (Np=120) и малой (Np=30) популяциями. Полученные результаты сравнивались с результатами работы алгоритма с учетом сокращения популяции с Np=120 (Np^initial =120) до Np=30 (Np^final =30) с использованием уравнения (5).

Анализ полученных данных показал, что введение фазы гибели повышает эффективность алгоритма для решения задач высокой размерности. На рис. 3 изображены характеристики сходимости этого алгоритма для шести функций различного типа, которые подтверждают эффективность реализации фазы смерти в WGA.

Сходимость в среднем (average convergence) представляет собой более слабое условие, чем равномерная сходимость, но, наряду с этим, является достаточным условием перехода к пределу под знаком интеграла, а сходимость в среднем для функциональных рядов является достаточным условием почленного интегрирования функционального ряда.

Итак, выше я отмечал, что для всех тестовых функций и прогонов было использовано значение Cr=0.5. Почему?

Такое значение было выбрано эмпирическим путем. Проведено пять тестов со значениями — 0.1, 0.25, 0.5, 0.75 и 0.9, результаты которых показали, что, значение 0.5 оказалось в большинстве тестов лучшим.

Сравнение WGA с другими алгоритмами оптимизации

Тирле упал! Тирле! Он влез на спину Дирле, а Пирле толкнул Дирле, и Тирле упал.

Проведенные тесты показали, что предложенный алгоритм способен обеспечить очень эффективные и конкурентоспособные результаты при решении задач по сравнению с ранее предложенными алгоритмами.

WGA показал себя как многообещающий метод для одномодальных и мультимодальных задач оптимизации со сдвигом.

Были обобщены результаты исследований для двадцати различных тестовых функций с D=1000, включая алгоритм MLCC, дифференциальную эволюцию с кооперативной коэволюцией и дельта-группировкой DECC-D и DECC-DML, основанную на вкладе кооперативную коэволюцию и дифференциальную группировку CBCC1-DG и CBCC2-DG, дифференциальную эволюцию с кооперативной коэволюцией и случайным группированием DECC-DG.

Сравнительные показатели (средние значения и стандартные отклонения) для использованных алгоритмов свидетельствуют, что алгоритм WGA показал наилучшие результаты в 12 из 20 функций. Кроме того, ни по одной из тестовых функций WGA не имеет наихудших результатов и достигает лучшего среднего ранга.

WGA превосходит алгоритм MLCC в 18 из 20 функций. У алгоритма MLCC большой разброс результатов для разных тестовых функций, в том числе для 6 из 20 функций он показал наихудшие результаты. Также предлагаемый алгоритм показал приемлемые и подходящие результаты для большинства тестовых функций, а дисперсия его результатов меньше, чем у других алгоритмов.

Сравнение алгоритмов WGA и DECC-D показывает, что WGA работает лучше для 18 из 20 функций. Кроме того, алгоритм DECC-D не обеспечивает решения хорошего качества для различных тестовых функций, например, для F2 и F20 он дает подходящие результаты, но для F5-F8, F10-F12 и F15-F17 его результаты неприемлемы по сравнению с таковыми других алгоритмов.

Хотя алгоритм DECC-DML превосходит WGA для пяти тестовых функций, он имеет наихудшее решение для шести функций. Алгоритмы CBCC1-DG и CBCC2-DG более успешны, чем WGA для двух и трех функций соответственно; однако CBCC1-DG не дает наилучшего результата ни для одной из функций, а CBCC2-DG дает наилучший результат только для одной функции. Алгоритм DECC-DG работает лучше, чем WGA, для 2 из 20 тестовых функций; однако он дает наихудшее решение для 4 тестовых функций среди всех алгоритмов.

Проверка алгоритма на тестовых функциях очень важна, но тестирование на реальных задачах еще важней. Для проверки боем эффективность алгоритма была исследована в сравнении с генетическим алгоритмом GL-25, DE с адаптацией стратегии (SaDE), DE с контрольными компонентами и подходами генерации составных пробных векторов (CoDE), стандартной оптимизацией роя частиц SPSO и гетерогенным всесторонним обучением PSO с улучшенной эксплуатацией и исследованием HCLPSO.

В качестве реальных задач использованы оценка коэффициента для частотно-модулированных звуковых волн и оптимизация надежности-избыточности газовой турбины.

Оценка коэффициента частотно-модулированных звуковых волн

Сложная задача оптимизации мультимодального частотно-модулированного звука играет ключевую роль в различных современных музыкальных системах для оценки оптимальных факторов синтеза FM волны.

Оценка оптимальных факторов синтеза FM звуковых волн представляет собой оптимизационную задачу с D решающими переменными. В данной работе случай D=6 рассматривается только в соответствии с [41,42]. Шесть компонентов включены в 6-мерный вектор параметров как x = [x₁(a₁), x₂(ω₁), x₃(a₂), x₄(ω₂), x₅(a₃), x₆(ω₃)] в диапазоне 6.35-6.5 для всех переменных. Уравнения, представленные для целевых и аппроксимированных звуковых волн для t, определенного в диапазоне 1-100, следующие:

Целевая функция задачи оптимизации рассматривается как сумма квадратов ошибок между y(t) (аппроксимированная волна) и y₀(t) (целевая волна) с оптимальным значением f(x)=0 следующим образом:

Задача с ограничениями надежности-избыточности газовой турбины

Нелинейные задачи оптимизации надежности-избыточности в основном направлены на повышение надежности системы (максимизацию общей надежности системы) за счет оптимизации вектора надежности элементов r=(r₁, r₂, …, r_m) и вектора чисел присвоения избыточности n=(n₁, n₂, …, n_m) для всех подсистем.

Данную задачу можно сформулировать как нелинейную модель смешанно-целочисленного программирования, выбрав надежность системы в качестве целевой функции, которая должна быть, максимизирована с учетом нескольких нелинейных ограничений следующим образом:

где Z⁺ — множество натуральных чисел, R_s — надежность различных систем, f(.) и g(.) обозначают целевую и ограничивающую функции задачи оптимизации для полных параллельно-последовательных систем соответственно, из которых g(.) обычно связано со стоимостью системы, весом и объемом.

n=(n₁, n₂, …, n_m) и r=(r₁, r₂, …, r_m) показывают числа резервирования и векторы надежности компонентов для подсистем, включающих m подсистем, соответственно. Кроме того, l показывает предел системных ресурсов.

При обнаружении превышения скорости подача топлива должна быть остановлена с помощью регулирующих клапанов (V₁-V_m).

На рис. 4 представлена система защиты газовой турбины от разгона, оптимизирующая смешанно-целочисленную нелинейную задачу. Структура крупномасштабного теста включает m×2=40 решений.

Данную задачу оптимизации надежности можно сформулировать следующим образом:

К системным ограничениям относятся:

– комбинированное ограничение веса, объема и избыточности g₁(r, n):

где v_d показывает объем d-й подсистемы для всех компонентов, а V представляет собой верхний предел объема продуктов подсистемы.

– ограничение стоимости системы g₂(r, n):

где C — верхний предел стоимости системы, C(r_d) — стоимость всех элементов с надежностью r_d на d-м этапе, T — время работы компонентов.

– ограничение веса системы g₃(r, n):

Для решения данных задач применили WGA и пять других алгоритмов. В сравнительных исследованиях FEs_max корректируются до 5,00E+04, и для всех алгоритмов выбирается достаточно большой размер популяции. В таблице представлены результаты оптимизации (среднее значение и стандартное отклонение) различных алгоритмов, выполненных в 30 прогонах для решения двух задач.

Лучшие результаты выделены жирным шрифтом. Отметим, что WGA обеспечивает наиболее качественные решения, что как бы намекает)))

Средние значения пригодности и стандартные отклонения для реальных задач оптимизации

Предлагаемый алгоритм WGA достаточно прост и эффективен для  решения задач оптимизации высокой размерности.

Одним из преимуществ WGA является то, что он имеет только один параметр управления, Cr. Экспериментально показано, что WGA показывает конкурентные результаты по отношению к другим алгоритмам, а также превосходит многие из них по большинству тестовых функций.

В последние годы проводятся многочисленные исследования в области многомерной оптимизации, большинство из которых были сосредоточены на методах совместной коэволюции (CC). В дальнейшем WGA может быть встроен в рамки таких методов с разнообразными дополнениями для повышения его производительности. Математическая наука не стоит на месте и в соответствии с требованиями времени развивается. И самое важное, что сегодня результаты исследований не остаются «пылиться» на страницах научных журналов, а активно применяются в различных отраслях и получают очень широкий спектр реальных приложений.

Исходный код алгоритма WGA (MATLAB).

НЛО прилетело и оставило здесь промокод для читателей нашего блога:

— 15% на все тарифы VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.