Исследование влияния параметров локализаци, регруппировки на эффективность работы алгоритма DMS-PSO - Статья

Для поиска разработано множество поисковых методов, таких как методы нулевого порядка: Метод бисекций, Метод покоординатного спуска, Метод деформируемого многогранника Нелдера-Мида и т.д.; методы первого порядка: Метод наискорейшего спуска, Метод сопряженного градиента Флетчера-Ривса и т.д.; методы второго порядка: Метод Ньютона-Рафсона, Метод Дэвидона-Флетчера-Пауэла и так далее. Простота реализации и эффективность данного алгоритма вызывают повышенный практический интерес к particle swarm optimizer (PSO) в целом и к dynamic multi-swarm particle swarm optimizer (DMS-PSO) в частности, а недостаточная изученность влияния параметров алгоритма требует дополнительных исследований. Топология «клика» это наиболее очевидная структура соседства частиц - каждая с каждой в группе, то есть каждая частица в группе знает информацию о каждой частице в группе, и самое главное «знает» . Одним из ключевых отиличий DMS-PSO от кононического PSO является наличе топологии «кластера», которая состоит из нескольких топологий «клика» или групп, в каждой группе свой и частицы из других групп его не «знают», для нагляности данную топологию можно представить графически, как изображено на рис. Каждые итераций работы алгоритма кластеры обмениваются некоторыми частицами и поиск оптимума продолжается с уже новой конфигурацией соседства частиц. называется периодом регруппировки.Необходимо в дальнейшем сравнить эффективность PSO с другими аналогичными стохастическими алгоритмами, а также предложить варианты автоматизации выбора параметров PSO, позволяющие пользователю избежать необходимости настройки параметров при решении реальных задач оптимизации.

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

Все больший научный и практический интерес вызывают эволюционные алгоритмы глобальной оптимизации, имитирующие процессы естественной эволюции и поведения живых организмов в окружающей среде: генетические алгоритмы, эволюционные стратегии, «муравьиные алгоритмы», «пчелиные алгоритмы». И относительно недавно разработан смежный метод, обобщающий имитацию интеллектуального совместного поведения субъектов, без отнесения их к какой-либо биологической группе, так называемый particle swarm optimizer (PSO).

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

Простота реализации и эффективность данного алгоритма вызывают повышенный практический интерес к particle swarm optimizer (PSO) в целом и к dynamic multi-swarm particle swarm optimizer (DMS-PSO) в частности, а недостаточная изученность влияния параметров алгоритма требует дополнительных исследований.

1. Постановка задачи

Рассмотрим задачу глобальной безусловной минимизации целевой функций:

Множество частиц обозначим , где - количество частиц. В момент времени координаты частицы определяются вектором , а ее скорость - вектором . Начальные координаты и скорости частицы равны , соответственно.

Итерации в каноническом методе PSO выполняются по следующей схеме:

(1.1)

(1.2)

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

где - максимальное значение параметра , - минимальное значение параметра , - номер итерации, - максимальное количство итераций.

Важным параметров в PSO является топология группы частиц, на которые разбивается все частицы. Другими словами топология группы определяет структуру соседства частиц в группе. В данной работе для исследования выбраны такие топологии: «клика», «кластер» размерности 3. Топология «клика» это наиболее очевидная структура соседства частиц - каждая с каждой в группе, то есть каждая частица в группе знает информацию о каждой частице в группе, и самое главное «знает» . Одним из ключевых отиличий DMS-PSO от кононического PSO является наличе топологии «кластера», которая состоит из нескольких топологий «клика» или групп, в каждой группе свой и частицы из других групп его не «знают», для нагляности данную топологию можно представить графически, как изображено на рис. 1.

Рис.1. Топология кластера, размер кластера 5

Например, для P1 соседними являются частицы: P2, P3, P4, P5.

2. DMS-PSO с локальным поиском

PSO с размерностью кластера 5 и более достигает хороших результатов на простых задачах, было проведено множество исследований на эту тему, если же размерность кластера не большая, то PSO работает лучше на комплексных задачах. PSO использует информацию предыдущей итерации, что в совокупности с небольшим размером кластера дает быструю сходимость к локальному оптимуму. Чтобы этого избежать, необходимо дать возможность частицам в разных кластерах обмениваться информацией между собой. Причем информация должна быть как положительной (информация о более «хорошем» решении), так и отрицательной, чтобы более разнообразить популяцию. Поэтому вводится случайная регруппировка элементов кластеров, благодаря чему PSO имеет динамическую структуру соседства частиц. Каждые итераций работы алгоритма кластеры обмениваются некоторыми частицами и поиск оптимума продолжается с уже новой конфигурацией соседства частиц. называется периодом регруппировки. Таким образом, происходит обмен информацией между кластерами и повышается разнообразие популяции.

Для примера, возьмем 9 частиц, топология соседства - кластер размерности 3. Кластеры формируются случайным образом. Через некоторый период частицы (кластеры) могут сгруппироваться вокруг локальных оптимумов. Затем применятся операция регруппировки и продолжается поиск оптимума. Этот процесс повторяется, пока не будет выполнен критерий останова алгоритма. Изменение структуры соседства дает возможность небольшим группам частиц охватывать большие области поиска. Операция регруппировки представлена на рис. 2.

Рис.2. Работа оператора регруппировки

При достижении болшего разнообразия популяции, уменьшается скорость сходимости и благодаря стахостическому поведению алгоритма нет вообще гарантии, что найденное алгоритмом PSO решение будет хотябы локально-оптимальным. По этой причине, в DMS-PSO добавлен локальный поиск: каждые L итераий популяция сортируется согласно пригодсности, выбирает 25% лучших индивидов и эти индивиды улучшаются, использую локальный поиск. L называется периодом локализации. Улучшенные индивиды возвращаются в популяцию, структура топологии при этом переинициализируется.

3. Эксперимент

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

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

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

Во всех запусках алгоритма число прогонов равнялось 50 точность поиска экстремума равна 0.01, значения параметров алгоритма , . Параметр инерции скорости изменялся динамически на отрезке , либо был статичным равным . Область определения функций по всем координатам: для Сферической функции , для Повернутой Эллиптической , для Розенброка , для Гринвока , для Экли , для Растригина . Размерности функций: 2, 4, 8, 16.

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

В случае Таблицы 1, настройками алгоритма являлись: количество частиц , количество итераций работы алгоритма , точность поиска , параметр инерции скорости , топология соседства частиц - кластер размерности 3, тип локализации - градиентный спуск.

Из рисунка 3 и таблицы 1 видно, что алгоритм DMS-PSO, при настройках, работает с наибольшей надежностью при периоде локализации равном 0, т.е. локализация не используется. Наименьшую надежность алгоритм показывает при периоде локализации, равном , что равняется от максимального количества итераций (поколений).

Рис.3. Зависимость надежности алгоритма от периода локализации для функции Растригина при настройках

Зависимость надежности работы алгоритма, разброса, скорости и среднего лучшего решения от периода локализации на функции Растригина размерности 8

Табл. 1

Период локализации надежность разброс скорость сред. лучший

0 92% 254:674 473,7188 0,114868

116 86% 404:700 567,8333 0,058817

233 60% 290:680 500,4762 0,423223

349 72% 262:687 466,8 0,239284

466 74% 291:663 492,5385 0,137471

582 74% 253:693 458,68 0,138243

699 80% 195:684 453,7143 0,144116

На рис. 4 отражена зависимость надежности работы алгоритма от периода регруппировки на функции Растригина при тех же настройках алгоритма.

Рис.4. Зависимость надежности алгоритма от периода регруппировки для функции Растригина при настройках

Наибольшая надежность, при настройках, достигается на периоде регруппировки, находящемся в интервале . Наименьшая надежность достигается на периоде регруппировки, равном , что равняется от максимального количества итераций (поколений).

Анализ полученных результатов показал, что надежность работы алгоритма зависит от периода локализации (регруппировки). При большинстве настроек алгоритм показывает наивысшую надежность при периоде, равном от максимального количества итераций работы алгоритма. Условно, зависимости надежности алгоритма от периода локализации (регруппировки) можно представить на рисунке 5. По горизонтальной оси - период локализации, по вертикальной оси - надежность работы алгоритма. - максимальное количество итераций работы алгоритма. Красной линией обозначена зависимость для динамической скорости, зеленой для статичной.

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

Рис.5. а) отражает зависимость на унимодальных «простых» функциях; б) отражает зависимость на полимодальных функциях при использовании топологии «клика»; в) отражает зависимость на полимодальных функциях при использовании топологии «кластер 3»; г) отражает зависимость на полимодальных функциях при использовании топологии «кластер 3» с использованием регруппировки

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

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

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

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

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

[Holland et al., 1975] Holland J. H. Adaptation in natural and artificial systems. // University of Michigan Press. 1975.

[Kennedy et al., 1995] Kennedy J. and Eberhart R. Particle swarm optimization // Proc. of the IEEE Int. Conf. on Neural Networks. - Piscataway. 1995.

[Kennedy, 1999] Kennedy J. Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance // Proc. of IEEE Congress on Evolutionary Computation (CEC 1999), Piscataway. 1999.

[Kennedy et al., 2002] J. Kennedy and R. Mendes Population structure and particle swarm performance [Text] // Proc. of the IEEE Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii USA. 2002

[Liang et al., 2005] Liang J. J. and Suganthan P. N. Dynamic Multi-Swarm Particle Swarm Optimizer // IEEE International Swarm Intelligence Symposium. 2005.

Размещено на .ru