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

Размещено на http://www.allbest.ru/

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

В.О. Долин

Научный руководитель: Бежитский С.С.

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

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

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

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

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

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

(1)

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

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

(2)

(3)

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

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

(4)

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

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

Рисунок 1 - Топология «кластер»

На рисунке 1, общее число частиц равно 20, они разделены на 4 кластера по 5 частиц в кластере. Таким образом для частицы соседними являются частицы: .

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

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

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

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

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

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

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

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

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

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

Рост вычислений при возрастании размерности является линейным, а не экспоненциальным как у генетического алгоритма, что характеризует PSO положительно. Необходимо в дальнейшем сравнить эффективность 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.

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