Экспериментальное сравнение эффективности метаоптимизированных популяционных роевых метаэвристик

АННОТАЦИЯ

Постановка проблемы: существующие роевые метаэвристики обладают многими параметрами, которые можно изменять и настраивать в целях повышения эффективности использования. Целью работы является экспериментальное сравнение разработанного метода метаоптимизации популяционных метаэвристик,распространенного на алгоритм летучих мышей, позволяющее оптимизировать работу алгоритма для выбранного показателя эффективности. Результаты: сформулированы задачи оптимизации алгоритма летучих мышей, с возможностью тестирования на любой выбранной целевой функции и приведен пример решения при заданных параметрах. В качестве оптимизационной составляющей роевого алгоритма используется ограничение скорости. Для данного метода выбрано уравнение изменения скорости. Это уравнение содержит три слагаемых, которые регулируют величину и направление изменения скорости частицы. Сущность предложенного метода состоит в том, что при работе скорость ограничена, в итоге чего частицы не выходят за интересующую границу поиска, не расходятся. Новизна подхода состоит в том, что при работе алгоритма учитываются значения скорости в предыдущих точках на заданное количество шагов назад. Для решения поставленной оптимизационной задачи разработан метод метаоптимизации, который можно применять на роевых популяционных метаэвристиках. Практическая значимость: разработанный метод метаоптимизации популяционных метаэвристик с учетом положения предыдущих значений скорости позволит (как показывают результаты приведенных экспериментов) повысить качество работы алгоритма.

ABSTRACT

Problem statement: existing swarmmetaheuristics have many parameters that can be changed and adjusted in order to increase use efficiency. The aim of the work is an experimental comparison of the developed method of meta-optimization of population metaheuristics extended to the algorithm of bats andallowed to optimize work of the algorithm for the chosen efficiency index.

Results: optimizationproblems of the algorithm for bats are stated with the possibility to test any chosen objective function, and an example of solution is provided for the given parameters. The speed limit is used as an optimization component of the swarm algorithm. For this method, the equation of velocity variation is chosen. This equation contains three items that regulate the magnitude and direction of the particle velocity change.

The essence of the proposed method is that the speed is limited during operation, as a result of which particles do not go beyond the interesting search boundary, do not diverge. The novelty of the approach is that the speed values at previous points are taken into account by a specified number of steps back in the algorithm. To solve the optimization task, a meta-optimization method has been developed that can be used on swarm population metaheuristics.

Practical significance: the developed method of meta-optimization of population metaheuristics taking into account the position of previous values of the speed will allow (as shown by results of the above experiments) to improve the quality of the algorithm.

Введение

Существуют различные способы повышения эффективности работы популяционных роевых метаэвристик. Можно выделить два основных направления: первое – метод настройки параметров (стратегия алгоритма остается фиксированной во время работы алгоритма), второе – метод управления параметрами (параметры стратегии варьируются на отдельных итерациях (на каждой или на некоторых)). В 1986 ученым GrefenstetteJ.J. в работе «Optimization of control parameters for genetic algorithms» были произведены объемные исследования, и на основе их была показана эффективность настройки параметров для случайного поиска[1].

В данной работе предлагается сравнить работу двух метаоптимизированных алгоритмов – алгоритма летучих мышей и метаоптимизированногоалгоритма роя частиц. Рассмотрим указанную выше метаоптимизацию алгоритмов. Идея модификации алгоритмов на основе дробного исчисления, с использованием ряда допущений, была заимствована из работы “Particles warm optimization with fractional – ordervelocity”.   E.J. SolteiroPires, J.A. Tenreiro Machado, P.B. de Moura Oliveira, J. Boaventura Cunha, Luís Mendes, 2010. Также эта тема затрагивалась в следующих зарубежных публикациях: [Rabei, E.M., Altarazi, I.M.A., Muslih, S.I., Baleanu, D.: Fractional WKB approximation. Nonlinear Dyn. 57(1–2), 171–175 (2009)], [den Bergh, F.V., Engelbrecht, A.P.: A study of particle swarm optimization particle trajectories. Inf. Sci. 176(8), 937–971 (2006)].

Процесс метаоптимизации. Поставленная задача и ее решение

Процесс преобразование формулы скорости. Данная тема была предложена авторами в публикации: [Журнал Современные проблемы науки и образования. – 2015. – № 2 (часть 1) Метаоптимизация роя частиц на основе метода дробного исчисления Дутова И.Г., Мохов В.А.]. В качестве оптимизационной составляющей классического роевого алгоритма используются дробные производные. Существует различные способы улучшения классического алгоритма роя частиц:

1.      Создание оптимизационного метода, который состоит из соединения нескольких алгоритмов роя частиц.
2.      Разовая настройка характеристик движения частиц, посредством которого, можно влиять на вероятность преждевременной сходимости.
3.      Оптимизация с динамическим изменением параметров алгоритма.

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

 – максимально допустимая скорость в i – й компоненте. Скорость частицы можно регулировать следующим образом:

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

В данной модификации алгоритма можно отметить такой важный момент:

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

Поставленная задача и ее решение

Для сравнения эффективности были проведены эксперименты работы алгоритмов летучих мышей, обычного и оптимизированного. Алгоритм летучих мышей реализуется с визуализацией процесса для функций оптимизации. Можно подставлять любую функцию. Алгоритм летучих мышей взят из реализации Янга [YangX. S.20 Jul 2012]. Ниже приведены отдельные фрагменты листинга программы, содержащие заданные параметры для алгоритма и варианты изменения кода.

swarm_size = 20;   % размер популяции

A=20;     % громкость

r=1;                        % частота повторения импульсов агентом

ЭВОЛЮЦИЯ ПАРАМЕТРОВ

N_iter=N_iter+n;

% На каждой итерации текущая скорость становится предыдущей, то есть учитывается память частицы о ее предыдущем состоянии.

v(:,:,[1:3]) = v(:,:,[2:4]); % t-1=>t-2; t=>t-1; t+1=>t;

fori = 1 : n

% Пересчитываем текущую скорость по заданной формуле. Для первых моментов времени предыдущие скорости нулевые.

v(i,:,4) = inertia*v(i,:,3) + inertia*v(i,:,2)/2 + ...

inertia*(1-inertia)*v(i,:,1)/6 + ...

            p1*rand*(Sol(i,:) - best) + ...

            p2*rand*(Sol(i,:) - fmin);

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

Рисунок. 1 график функции 

По графику видны участки локальных экстремумов функции.  Значение локального минимума равно х=-3,552 fmin =-29,371.

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

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

Для классического алгоритма летучих мышей была определена объективная функция f(x) . Заданы параметры по умолчанию и итерационные параметры, размер популяции, количество поколений, громкость, частота повторений импульсов агентом, min и max частоты, размерность переменных поиска.

Рисунок 2. График поиска минимума заданной функции, используя классический алгоритм летучих мышей

На рис. 2 отображена работа классического алгоритма при поиске экстремума. Зеленым кругом обозначается результат работы алгоритма. Черные крестики показывают каждое новое положение мыши. Результаты трех запусков при числе оценок равном 200:

Лучшие = -3,342 fmin=-28,4676 ans =   -3,3420

Лучшие = -3,414 fmin=-28,9692 ans =   -3,4140

Лучшие = -3,7582 fmin=-28,3342 ans =   -3,7582

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

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

Результаты трех запусков при числе оценок равном 200:

Лучшие = -3,5873 fmin=-29,3428 ans =   -3,5873

Лучшие = -3,4745 fmin=-29,2416 ans =   -3,4745

Лучшие = -3,2812 fmin=-27,9066 ans =   -3,2812

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

Заключение

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