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

А.П. Карпенко,
зав. каф., д.ф.-м.н, проф., apkarpenko@mail.ru,
С.А. Гаджиев,
магистр, g.said.alievich@mail.ru,
МГТУ им. Н.Э. Баумана, г. Москва

Рассматриваем задачу параметрической оптимизации проектных решений как задачу непрерывной многомерной глобальной оптимизации. Для решения таких задач в настоящее время широко используют стохастические алгоритмы, называемые поведенческими, интеллектуальными, метаэвристическими, вдохновленными природой, роевыми, многоагентными, популяционными и т.д. Рассматриваем один из такого рода алгоритмов ‑ алгоритм роя частиц (Particle Swarm Optimization, PSO), основанный на модели коллективного поведения стаи птиц, косяка рыб и т.п. Известно большое число модификаций канонического алгоритма PSO (CPSO). Целью работы является сравнительное исследование эффективности алгоритма CPSO и его наиболее эффективных модификаций ВSPSO и TVACPSO в процессе решения одной из известных тестовых задач – задачи параметрической оптимизации сосуда высокого давления.

We consider the problem of parametric optimization of design solutions as a problem of the continuous multi-dimensional global optimization. To solve these problem are now widely used stochastic algorithms, called intelligent, metaheuristic, inspired by nature, swarms, multi-agent, population-based, etc. We consider one of such algorithm - Particle Swarm Optimization (PSO) algorithm, based on the model of collective behavior of a flock of birds, shoals of fish, etc. It is well known a large number of modifications of the canonical algorithm PSO (CPSO). The aim of this work is the comparative study of the effectiveness of CPSO algorithm and its most effective modifications VSPSO and TVACPSO in the process of solving one of the famous test problem of parametric optimization of the pressure vessel.

Введение

Для численного решения задач многомерной глобальной оптимизации в настоящее время широко используют стохастические алгоритмы, называемые в разных источниках поведенческими, интеллектуальными, метаэвристическими, вдохновленными природой, роевыми, многоагентными, популяционными и т.д. Широкую известность получили такие алгоритмы данного класса, как пчелиные, муравьиные, рассматриваемые в данной работе алгоритмы роя частиц (Particle Swarm Optimization, PSO) [1]. Эти алгоритмы основаны на модели коллективного поведения стаи птиц, косяка рыб и т.п. Канонический алгоритм роя частиц (CPSO) предложен в 1995 году в работе [2]. На каждой итерации алгоритма при перемещении частицы учитывается информация о наилучшей соседней частице, а также информация о данной частице на той итерации, когда этой частице соответствовало наилучшее значение целевой функции. Известно большое число модификаций алгоритма CPSO, например, алгоритм PSO с полной информацией, алгоритм с организацией в клубы, многороевые алгоритмы, гибридные алгоритмы [3]. Целью работы является сравнительное исследование эффективности алгоритма CPSO и его известных потенциально наиболее эффективных модификаций ВSPSO и TVACPSO [4].

Программная реализация указанных алгоритмов выполнена на языке программирования высокого уровня Java. Анализ эффективности рассматриваемых алгоритмических и программных решений выполнен на наборе тестовых функций различной размерности, включающем в себя функции Розенброка, Гриванка и Растригина [5], а также на известной практически значимой задаче о минимизации расходов на изготовление сосуда высокого давления [6]. В последнем случае использован алгоритм TVACPSO, как показавший наиболее высокую эффективность на тестовых функциях.

Работа поддержана РФФИ (проекты № 16-07-00287, 15-07-01764).

1. Канонический алгоритм PSO и его используемые модификации

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

, ,

где – размерность вектора варьируемых параметров X; ‑ -мерное арифметическое пространство; – целевая функция со значениями в пространстве ; , – искомые точные решения задачи. Эти же приближенные решения, полученные с помощью рассматриваемого алгоритма PSO, обозначаем , .

Канонический алгоритм PSO (CPSO). Множество частиц обозначаем , где – размер популяции. На итерации координаты частицы определяет вектор . Начальные координаты частицы заданы и равны ; [2]. Алгоритм CPSO выполняет перемещение частиц по формуле

где – «скорость» частицы , равная

.

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

Эффективность алгоритма СPSO, как и других алгоритмов роя частиц, в значительной мере зависит от используемой топологии соседства частиц. В вычислительной практике чаще всего применяют следующие статические топологии соседства частиц: клика, кольцо, двумерный тор, кластерная топология, топология случайного соседства [3].

Алгоритм c дополнением графа соседства частиц. Алгоритм DSPSO PSO (Dynamic Sociometry PSO) является наиболее известным представителем алгоритмов PSO с динамической топологией соседства. Алгоритм предложен и исследован в работе [7]. Идея алгоритма состоит в следующем. На начальных итерациях процесса оптимизации используется сильно разреженный граф соседства частиц, который обеспечивает широкий обзор поискового пространства (диверсификацию поиска). Через фиксированное число итераций k в этот граф регулярным или случайным образом добавляем новое ребро. В итоге на завершающих итерациях алгоритма граф соседства частиц становится плотным, что обеспечивает высокую точность локализации искомого решения задачи оптимизации (интенсификацию поиска).

Алгоритм DSPSO использует следующее правило дополнения графа соседства частиц: из натуральных чисел равномерно распределенных в интервале , выбираем два различных случайных числа , таких, что частицы , не являются соседями в текущем графе соседства; добавляем в данный граф ребро ,. При достаточном числе итераций, в конце концов, получаем граф соседства типа клика.

Алгоритм с динамическим изменением свободных параметров. Алгоритм TVACPSO предложен и исследован в работе [4]. Идея алгоритма заключается в изменении в процессе итераций значений свободных параметров алгоритма СPSO так, чтобы обеспечить диверсификацию поиска на ранних итерациях и интенсификацию поиска ‑ на поздних итерациях.

В алгоритме TVACPSO параметр изменяется по формуле:

,

где , – значения параметра на первой и последней итерациях соответственно. Рекомендуемые значения параметров равны ; . Параметры , изменяются по аналогичным схемам и , , , [4].

2. Вычислительный эксперимент. Классические тестовые задачи

Программная реализация указанных алгоритмов выполнена на языке программирования высокого уровня Java. В качестве тестовых рассматриваем следующие функции [5]: овражная одно-экстремальная функция Розенброка; многоэкстремальная функция Гриванка; многоэкстремальная функция Растригина. В вычислительном эксперименте использован метод мультистарта с числом запусков с последующим усреднением результатов вычислений. В качестве индикаторов эффективности исследуемых алгоритмов рассматриваем значения следующих величин:  – лучшее достигнутое значение целевой функции; – средняя скорость сходимости алгоритма; ‑ оценка вероятности локализации глобального экстремума с заданной точностью.

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

Результаты исследования эффективности алгоритмов CPSO, DSPSO и TVAСPSO представлены в таблицах 1‑ 3 соответственно.

Таблица 1

Эффективность алгоритма CPSO

Тестовая функция
Розенброка	4	1,44E-09	365	0,85
	8	4,29E-07	1250	0,82
	16	1,55E-06	1740	0,79
Гриванка	4	9,81E-03	339	0,94
	8	1,68E-03	538	0,82
	16	4,41E-06	626	0,73
Растригина	4	3,13E-07	410	0,23
	8	2,12	780	0,0
	16	9,94	1423	0,0

В алгоритме TVAСPSO использована топология случайного соседства, когда соседи данной частицы выбираются случайным образом. Таблицы 1 – 3 иллюстрируют рисунки 2 ‑4. Представленные результаты показывают, что алгоритм CPSO обеспечивает высокую вероятность локализации глобального минимума функций Розенброка и Гриванка. Для функции Растригина этот алгоритм показал низкую вероятность и сумел с требуемой точностью локализовать глобальный минимум только при . Число итераций, требуемое для локализации глобального минимума, сильно зависит от типа функции и размерности ее вектора варьируемых параметров X. Так, из таблицы 1 и рисунков 2а, 4а следует, что числа итераций для одноэкстремальной функции Розенброка и многоэкстремальной функции Растригина могут отличаться более чем в два раза. Модификации DSPSO, TVACPSO, как и ожидалось, показали более высокую оценку вероятности локализации глобального минимума, чем алгоритм CPSO. Из таблицы 2 и рисунка 3 вытекает, что алгоритм DSPSO обеспечивает достаточно высокие скорость сходимости и вероятность локализации глобального минимума функций Розенброка и Гриванка. При алгоритм также показал более хорошие результаты для функции Растригина, чем алгоритм CPSO.

Таблица 2

Эффективность алгоритма DSPSO

Тестовая функция
Розенброка	4	1,20E-09	994	0,52
	8	0,73	1550	0,0
	16	7,63	2738	0,0
Гриванка	4	9,61E-04	838	0,96
	8	3,01E-03	1343	0,92
	16	1,34E-03	3598	0,89
Растригина	4	2,51E-03	768	1,0
	8	5,66E-03	948	0,99
	16	3,48E-06	1188	0,95

Таблица 3

Эффективность алгоритма TVACPSO

Тестовая функция
Розенброка	4	9,12E-03	998	0,62
	8	0,4E-01	1578	0,03
	16	3,03	3658	0,0
Гриванка	4	5,03E-03	598	0,97
	8	2,31E-03	4848	0,92
	16	7,78E-04	8408	0,86
Растригина	4	1,24E-03	758	0,98
	8	1,27E-04	1460	0,93
	16	5,84E-05	2408	0,88

а) индикатор эффективности б) индикатор эффективности

Рис. 1 Сравнение эффективности алгоритмов: функция Розенброка

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

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

Рассматриваем задачу изготовления сосуда высокого давления (рисунок 4). Целью является минимизация стоимости расхода материала на изготовление частей сосуда и последующей их сварки [6]. Компонентами вектора варьируемых параметров X являются следующие величины (в дюймах): – толщина стенки цилиндра; – толщина сферической головки; – внутренний радиус цилиндрической оболочки; – длина цилиндрической части.

а) индикатор эффективности б) индикатор эффективности

Рис.2 Сравнение эффективности алгоритмов: функция Гриванка

а) индикатор эффективности б) индикатор эффективности

Рис.3 Сравнение эффективности алгоритмов: функция Растригина

Рис. 4 Схема сосуда высокого давления [6]

Имеют место следующие ограничения на указанные величины: значения величин , должны быть кратны 0,0625 в соответствии с имеющейся толщиной листового проката стали; внутренний радиус и длина должны удовлетворять соответственно неравенствам

; . (1)

Кроме того, имеют место ограничения

, , (2)

, , (3)

, . (4)

Целевую функцию определяет выражение

(5)

Ограничения (1) – (4) учитываем с помощью метода штрафных функций, используя функции штрафа вида

, если ; , иначе; .

Для обеспечения кратности переменных , величине 0,0625 используем ближайшие к , значения, кратные этой величине.

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

Таблица 4

Результаты решения задачи

	Метод ветвей и границ [8]	Гармонический поиск [9]	Генетический алгоритм [6]	Метод кукушки [10]	TVACPSO
	1,125	1,125	1,125	1,114	0,832
	0,625	0,625	0,625	0,600	0,394
	48,97	58,20	58,28	57,71	43,76
	106,72	44,29	43,75	46,95	166,53
	-0,1790	-0,0018	-0,0002	-0,0001	0,00015
	-0,158	-0,070	-0,069	-0,049	-0,045
	97,76	-974,30	-3,72	-334,11	-1256,72
	-133,28	-195,71	-196,24	-193,04	-64,32
	7980,89	7207,49	7198,43	7036,48	6051,82

В работе [6] для решения рассматриваемой задачи использован метод ветвей и границ. При этом получено оптимальное значение целевой функции, равное 7980,89, однако условие оказалось не выполненным. Решение задачи методом, основанном на генетическом алгоритме, рассмотрено в работе [7]. Полученное там лучшее значение целевой функции равно 7207,49. В работе [8] использован алгоритм гармонического поиска, позволивший уменьшить значение целевой функции до 7198,43. В работе [9] для решения той же задачи применен алгоритм кукушки, который позволил достичь значения целевой функции, равного 7036,48. Исследованный нами алгоритм TVACPSO позволил достичь значения целевой функции, равного 6051,82, однако при этом не удалось выполнить условие .

Литература

1. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. ‑ Москва: Издательство МГТУ им. Баумана. ‑ 2014. ‑ C. 128-146.

2. Kennedy J., Eberhart R.C. Particle swarm optimization // Proceedings of IEEE International Conference on Neural Networks, Australia. ‑ 1995. ‑ Vol. 4. ‑ P. 1942-1948.

3. Карпенко А.П., Селиверстов Е.Ю. Обзор методов роя частиц (PSO) для задачи глобальной оптимизации [Электронный ресурс] // Наука и образование: электронное научно- техническое издание. – 2009. – 3 (http://technomag.edu.ru/doc/116072.html).

4. Engelbrecht A. Computational Intelligence – An Introduction 2nd Edition. – Wiley. ‑ 2007. ‑ P. 205-211.

5. Test functions for optimization [Электронный ресурс] / (https://en.wikipedia.org/wiki/Test_functions_for_optimization).

6. Lee K.S., Geem Z.W. A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice // Computation Methods Applied Mechanics and Engineering. ‑ 2005. – Vol. 194. ‑P. 3902–3933.

7. Suganthan P.N. Particle swarm optimizer with neighborhood operator. / Proceedings of the 1999 Congress on Evolutionary Computation. – 1999. ‑ Vol. 3. ‑ P. 1958-1962.

8. Sandgren E. Nonlinear integer and discrete programming in mechanical design optimization // ASME Journal of Mechanical Design. ‑ 1990. ‑ Vol. 112. ‑ No. 2. ‑ P. 223 - 229.

9. Wu S.J., Chow P.T. Genetic algorithms for nonlinear mixed discrete-integer optimization problems via meta-genetic parameter optimization // Engineering Optimization. ‑ 1995. ‑ Vol. 24. ‑ No. 2. ‑ P. 137-159.

10. Карпенко А.П., Бенза Н.Н. Модифицированный метод кукушки в задаче глобальной оптимизации [Электронный ресурс] // Научная электронная библиотека: электронное научно-техническое издание. – 2009. №3. (http://cyberleninka.ru/article/n/modifitsirovannyy-metod-kukushki-v-zadache-globalnoy-optimizatsii).