Программная система выбора эффективных параметров Particle Swarm Optimization при оптимизации многоэкстремальных функций

Программная система выбора эффективных  параметров Particle Swarm Optimization при оптимизации многоэкстремальных функций

В.О. Долин

     Сибирский государственный  аэрокосмический  университет имени академика М.Ф. Решетнева, г. Красноярск 

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

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

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

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

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

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

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

                                              (2)

                                                                                                                (3)           

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

                                                      (4)

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

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

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

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

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

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

     Во  всех запусках алгоритма число прогонов равнялось 50 точность поиска экстремума равна 0.01, значения параметров алгоритма с1=1.5, с2=1.5. Параметр инерции скорости изменялся динамически, либо был статическим и равным 0,71.

     Область определения функций по всем координатам: для Сферической функции , для Повернутой Эллиптической , для Розенброка , для Гринвока , для Экли , для Растригина , для Самбреро .

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

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

Таблица 1 – Результаты эффективности алгоритма  на функции Экли.

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

     Рисунок 2 - Зависимость количества вычислений функции Экли от размерности пространства оптимизации

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

     Список  литературы:

1. Holland, J. H. Adaptation in natural and artificial systems [Text]/ J. H. Holland. – [MI]: University of Michigan Press, 1975.
2. Dorigo,  M. Optimization, Learning and Natural Algorithms [Text]: thesis … PhD / M. Dorigo. - Milan, 1992. – Unpublished doctoral dissertation.
3. Pham, D.T. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre [Text]/ D.T. Pham. – [Cardiff University]: 2005.
4. Kennedy, J. Particle swarm optimization [Text]/ J. Kennedy,  R. Eberhart // in Proc. of the IEEE Int. Conf. on Neural Networks. - Piscataway, 1995. – PP. 1942–1948.