Алгоритм спиральной оптимизации - Spiral optimization algorithm

Спираль разделяет глобальное (синий) и интенсивное (красный) поведение.

В алгоритм спиральной оптимизации (SPO) это незамысловатая концепция поиска, вдохновленная спиральными явлениями в природе. Первый алгоритм SPO был предложен для двумерной безусловной оптимизации.^[1]на основе двумерных спиральных моделей. Это было распространено на n-мерные проблемы путем обобщения двумерной спиральной модели на n-мерную спиральную модель.^[2]Есть эффективные настройки для алгоритма SPO: настройка периодического направления спуска.^[3]и настройку сходимости.^[4]

Метафора

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

Алгоритм

Алгоритм спиральной оптимизации (SPO)

Алгоритм SPO - это алгоритм многоточечного поиска, не имеющий градиента целевой функции, который использует несколько спиральных моделей, которые можно описать как детерминированные динамические системы. Поскольку точки поиска следуют по логарифмическим спиральным траекториям к общему центру, определяемому как текущая лучшая точка, могут быть найдены лучшие решения и общий центр может быть обновлен. Общий алгоритм SPO для задачи минимизации при максимальной итерации ${\displaystyle k_{\max }}$ (критерий прекращения) выглядит следующим образом:

0) Установите количество точек поиска ${\displaystyle m\geq 2}$ и максимальное количество итераций ${\displaystyle k_{\max }}$.1) Поместите начальные точки поиска ${\displaystyle x_{i}(0)\in \mathbb {R} ^{n}~(i=1,\ldots ,m)}$ и определить центр ${\displaystyle x^{\star }(0)=x_{i_{\text{b}}}(0)}$, ${\displaystyle \displaystyle i_{\text{b}}=\mathop {\text{argmin}} _{i=1,\ldots ,m}\{f(x_{i}(0))\}}$, а затем установите ${\displaystyle k=0}$.2) Определите скорость шага ${\displaystyle r(k)}$ по правилу.3) Обновите точки поиска: ${\displaystyle x_{i}(k+1)=x^{\star }(k)+r(k)R(\theta )(x_{i}(k)-x^{\star }(k))\quad (i=1,\ldots ,m).}$4) Обновите центр: ${\displaystyle x^{\star }(k+1)={\begin{cases}x_{i_{\text{b}}}(k+1)&{\big (}{\text{if }}f(x_{i_{\text{b}}}(k+1))<f(x^{\star }(k)){\big )},\\x^{\star }(k)&{\big (}{\text{otherwise}}{\big )},\end{cases}}}$ куда ${\displaystyle \displaystyle i_{\text{b}}=\mathop {\text{argmin}} _{i=1,\ldots ,m}\{f(x_{i}(k+1))\}}$.5) Установить ${\displaystyle k:=k+1}$. Если ${\displaystyle k=k_{\max }}$ удовлетворено, затем прекратить и вывести ${\displaystyle x^{\star }(k)}$. В противном случае вернитесь к шагу 2).

Параметр

Производительность поиска зависит от настройки составной матрицы вращения. ${\displaystyle R(\theta )}$, скорость шага ${\displaystyle r(k)}$, а начальные точки ${\displaystyle x_{i}(0)~(i=1,\ldots ,m)}$. Следующие настройки являются новыми и эффективными.

Настройка 1 (настройка направления периодического спуска)^[3]

Этот параметр является эффективным для задач большого размера при максимальной итерации. ${\displaystyle k_{\max }}$. Условия на ${\displaystyle R(\theta )}$ и ${\displaystyle x_{i}(0)~(i=1,\ldots ,m)}$ вместе гарантируют, что спиральные модели периодически генерируют направления спуска. Состояние ${\displaystyle r(k)}$ работает, чтобы использовать периодические направления спуска под поисковое прекращение ${\displaystyle k_{\max }}$.

• Набор ${\displaystyle R(\theta )}$ следующее:${\displaystyle R(\theta )={\begin{bmatrix}0_{n-1}^{\top }&-1\\I_{n-1}&0_{n-1}\\\end{bmatrix}}}$ куда ${\displaystyle I_{n-1}}$ это ${\displaystyle (n-1)\times (n-1)}$ единичная матрица и ${\displaystyle 0_{n-1}}$ это ${\displaystyle (n-1)\times 1}$ нулевой вектор.
• Поместите начальные точки ${\displaystyle x_{i}(0)\in \mathbb {R} ^{n}}$ ${\displaystyle (i=1,\ldots ,m)}$ случайным образом, чтобы удовлетворить следующему условию:

${\displaystyle \min _{i=1,\ldots ,m}\{\max _{j=1,\ldots ,m}{\bigl \{}{\text{rank}}{\bigl [}d_{j,i}(0)~R(\theta )d_{j,i}(0)~~\cdots ~~R(\theta )^{2n-1}d_{j,i}(0){\bigr ]}{\bigr \}}{\bigr \}}=n}$куда ${\displaystyle d_{j,i}(0)=x_{j}(0)-x_{i}(0)}$. Обратите внимание, что это условие почти полностью удовлетворяется случайным размещением, и поэтому никакая проверка на самом деле не подходит.

• Набор ${\displaystyle r(k)}$ на Шаге 2) следующим образом:${\displaystyle r(k)=r={\sqrt[{k_{\max }}]{\delta }}~~~~{\text{(constant value)}}}$ где достаточно малая ${\displaystyle \delta >0}$ Такие как ${\displaystyle \delta =1/k_{\max }}$ или же ${\displaystyle \delta =10^{-3}}$.

Настройка 2 (Настройка сходимости)^[4]

Этот параметр гарантирует, что алгоритм SPO сходится к стационарной точке при максимальной итерации. ${\displaystyle k_{\max }=\infty }$. Настройки ${\displaystyle R(\theta )}$ и начальные точки ${\displaystyle x_{i}(0)~(i=1,\ldots ,m)}$ такие же, как и в приведенной выше настройке 1. Настройка ${\displaystyle r(k)}$ как следует.

• Набор ${\displaystyle r(k)}$ на Шаге 2) следующим образом:${\displaystyle r(k)={\begin{cases}1&(k^{\star }\leqq k\leqq k^{\star }+2n-1),\\h&(k\geqq k^{\star }+2n),\end{cases}}}$ куда ${\displaystyle k^{\star }}$ это итерация, когда центр обновляется заново на шаге 4) и ${\displaystyle h={\sqrt[{2n}]{\delta }},\delta \in (0,1)}$ Такие как ${\displaystyle \delta =0.5}$. Таким образом, мы должны добавить следующие правила о ${\displaystyle k^{\star }}$ к алгоритму:

•(Шаг 1) ${\displaystyle k^{\star }=0}$.

• (Шаг 4) Если ${\displaystyle x^{\star }(k+1)\neq x^{\star }(k)}$ тогда ${\displaystyle k^{\star }=k+1}$.

Будущие работы

• Алгоритмы с указанными выше настройками детерминированы. Таким образом, включение некоторых случайных операций делает этот алгоритм мощным для глобальная оптимизация. Cruz-Duarte et al.^[5] продемонстрировал это, включив в спиральные поисковые траектории стохастические возмущения. Однако эта дверь остается открытой для дальнейших исследований.
• Найти соответствующий баланс между спиралями диверсификации и интенсификации в зависимости от целевого класса проблемы (включая ${\displaystyle k_{\max }}$) важен для повышения производительности.

Расширенные работы

Много расширенных исследований было проведено на SPO из-за его простой структуры и концепции; эти исследования помогли повысить эффективность глобального поиска и предложили новые приложения.^{[6][7][8][9][10][11]}

Рекомендации

1. Тамура, К .; Ясуда, К. (2011). «Первичное исследование спиральной динамики, вдохновленное оптимизацией». IEEJ Transactions по электротехнике и электронике. 6 (S1): 98–100. Дои:10.1002 / тройник.20628.
2. Тамура, К .; Ясуда, К. (2011). «Оптимизация, вдохновленная спиральной динамикой». Журнал расширенного вычислительного интеллекта и интеллектуальной информатики. 132 (5): 1116–1121. Дои:10.20965 / jaciii.2011.p1116.
3. Тамура, К .; Ясуда, К. (2016). «Алгоритм спиральной оптимизации с использованием периодических направлений спуска». Журнал SICE по контролю, измерениям и системной интеграции. 6 (3): 133–143. Bibcode:2016JCMSI ... 9..134T. Дои:10.9746 / jcmsi.9.134.
4. Тамура, К .; Ясуда, К. (2020). «Алгоритм спиральной оптимизации: условия и настройки сходимости». IEEE Transactions по системам, человеку и кибернетике: системы. 50 (1): 360–375. Дои:10.1109 / TSMC.2017.2695577.
5. Крус-Дуарте, Дж. М., Мартин-Диас, И., Муньос-Миньярес, Дж. У., Санчес-Галиндо, Л. А., Авина-Сервантес, Дж. Г., Гарсиа-Перес, А., и Корреа-Сели, К. Р. (2017). Первичное исследование алгоритма стохастической спиральной оптимизации. Международное осеннее совещание по энергетике, электронике и вычислительной технике (ROPEC) 2017 IEEE, 1–6. https://doi.org/10.1109/ROPEC.2017.8261609
6. Насир, А. Н. К .; Тохи, М. О. (2015). «Улучшенный алгоритм спиральной динамической оптимизации с инженерным приложением». IEEE Trans. Syst., Man, Cybern., Syst.. 45 (6): 943–954. Дои:10.1109 / tsmc.2014.2383995.
7. Насир, А. Н. К .; Ismail, R.M.T.R .; Тохи, М. О. (2016). «Адаптивный метаэвристический алгоритм спиральной динамики для глобальной оптимизации с приложением к моделированию гибкой системы» (PDF). Appl. Математика. Modell. 40 (9–10): 5442–5461. Дои:10.1016 / j.apm.2016.01.002.
8. Уади, А .; Bentarzi, H .; Ресиуи, А. (2013). «многокритериальный дизайн цифровых фильтров с использованием техники спиральной оптимизации». SpringerPlus. 2 (461): 697–707. Дои:10.1186/2193-1801-2-461. ЧВК  3786071. PMID  24083108.
9. Benasla, L .; Belmadani, A .; Рахли, М. (2014). «Алгоритм спиральной оптимизации для решения комбинированных экономических и эмиссионных задач». Int. J. Elect. Power & Energy Syst. 62: 163–174. Дои:10.1016 / j.ijepes.2014.04.037.
10. Сидарто, К. А .; Кания, А. (2015). «Нахождение всех решений систем нелинейных уравнений с помощью спиральной динамики вдохновило оптимизацию с кластеризацией». Журнал расширенного вычислительного интеллекта и интеллектуальной информатики. 19 (5): 697–707. Дои:10.20965 / jaciii.2015.p0697.
11. Kaveh, A .; Махджуби, С. (октябрь 2019 г.). «Подход к оптимизации гипотрохоидной спирали для оптимизации размеров и компоновки ферменных конструкций с множественными частотными ограничениями». Разработка с помощью компьютеров. 35 (4): 1443–1462. Дои:10.1007 / s00366-018-0675-6.