Определение наилучшего распределения вычислительных ресурсов в алгоритме particle swarm optimization

Секция «Математические методы моделирования, управления и анализа данных»

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

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

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

У обоих алгоритмов возникли трудности с решением данной задачи. Лучший обход, найденный муравьиным алгоритмом, имеет длину 5420.57 км, а ге-

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

Библиографические ссылки

1. Мудров В. И. Задача о коммивояжере. М. : Знание, 1969. С. 62.

2. Dorigo М. & Gambardella L. M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation, 1997. 1 (1). Р. 53-66.

3. Рутковская Д., Пилиньский M., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы ; пер. с польск. И. Д. Рудинского. М. : Горячая линия - Телеком, 2006.

© Семенкина О. Е., Семенкин Е. С., 2011

УДК 519.68

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

ОПРЕДЕЛЕНИЕ НАИЛУЧШЕГО РАСПРЕДЕЛЕНИЯ ВЫЧИСЛИТЕЛЬНЫХ РЕСУРСОВ В АЛГОРИТМЕ PARTICLE SWARM OPTIMIZATION

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

Алгоритм particle swarm optimization (PSO) впервые был предложен в работе [http://www.engr.iupui. edu/~shi/Coference/psopap4.html]. Разработанный ими алгоритм довольно прост и может быть реализован буквально в нескольких десятках строчек кода на любом высокоуровневом языке программирования. Он моделирует многоагентную систему, где агенты-частицы двигаются к оптимальным решениям, обмениваясь при этом информацией с соседями.

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

На каждой итерации алгоритма направление и длина вектора скорости каждой из частиц изменяются в соответствие со сведениями о найденных оптиму-мах:

К, = Vt + * гяУ * (pierff - xt) +

,

где V* - вектор скорости частицы (V' - его У-я компонента); оа: - постоянные ускорения, р^езГ-лучшая найденная частицей точка; - лучшая

точка из пройденных всеми частицами системы; х -текущее положение частицы, а функция ^воз-

вращает случайное число от 0 до 1 включительно. После вычисления направления вектора К, частица

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

Данный алгоритм, являясь прямым конкурентом генетическому алгоритму (ГА) имеет ряд схожих проблем, например, выбор наилучших комбинаций параметров. Основными параметрами алгоритмов являются количество частиц и итераций.

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

Актуальные проблемы авиации и космонавтики. Информационные технологии

разбросу. Для решения поставленной задачи использовался классический PSO алгоритм без модификаций (инерция, сжатие). Применялись следующие параметры программы для решения задачи: границы поиска оптимума {-10;10}, число запусков 100, шаг дискретизации: 0.001, социальные параметры {2; 2}, общее число вычислений для 1 и 2 таблицы соответственно:

Анализ результатов показывает, что для любой функции наблюдается большая надежность при большем количестве итераций, чем частиц. Для функций Растригина, Катковника, Гриванка следует распределять ресурсы в сторону итераций в процентном соотношении 1:99. Для более сложных функций (Сомбреро, Мультипликативной) соотношение немного изменяется в сторону частиц 20:80 и 40:60 про-

1000, 50 000. Разница в количестве вычислений объясняется сложностью используемых тестовых функций. Размерность задачи равна 2.

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

Таблица 2

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

© Синяев И. Ф., Бежитский С. С., 2011

Таблица 1

Соотношение частиц и итераций Процентное соотношение % Ф-я Растригина Ф-я Гриванка Ф-я Катковника

надежность надежность надежность

1:1000 0,1:99,9 0,73 0,77 0,88

2:500 0,5:99,5 0,69 0,69 0,93

5:200 3:97 0,65 0,64 0,96

10:100 10:90 0,51 0,63 0,95

20:50 28,5:71,5 0,4 0,57 0,87

25:40 38,5:61,5 0,31 0,44 0,82

33:33 50:50 0,27 0,43 0,8

40:25 61,5:38:5 0,19 0,34 0,73

50:20 71,5:28,5 0,13 0,29 0,5

100:10 90:10 0,01 0,07 0,13

200:5 97:3 0,02 0,02 0,03

500:2 99,5:0,5 0,009 0,009 0,02

1000:1 99,9:0,1 0 0,009 0,009

Соотношение частиц и итераций Процентное соотношение, % Функция Сомбреро Мультипликативная функция

надежность надежность

1:50000 0,01:99,99 0,74 0,09

10:5000 0,5:99,5 0,93 0,11

20:2500 1:99 0,98 0,09

40:1250 3:97 0,94 0,13

50:1000 5:95 0,96 0,12

100:500 16,5:83,5 0,99 0,14

200:250 45:55 0,93 0,2

224:224 50:50 0,97 0,13

250:200 55,5:44,5 0,95 0,15

500:100 83,5:16,5 0,95 0,19

1000:50 95:5 0,94 0,09

1250:40 97:3 0,89 0,14

2500:20 99,2:0,8 0,87 0,07

5000:10 99,8:0,2 0,81 0,125