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

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

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

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

Метафора [ править ]

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

Алгоритм [ править ]

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

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

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

Настройка [ править ]

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

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

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

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

$\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$ где . Обратите внимание, что это условие почти полностью удовлетворяется случайным размещением, и поэтому никакая проверка на самом деле не подходит. $d_{j,i}(0)=x_{j}(0)-x_{i}(0)$

Установите на шаге 2) следующее: где достаточно маленький, например или . ^[3] $r(k)$ $r(k)=r={\sqrt[{k_{\max }}]{\delta }}~~~~{\text{(constant value)}}$ $\delta >0$ $\delta =1/k_{\max }$ $\delta =10^{-3}$

Настройка 2 (Настройка конвергенции) [ править ]

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

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

• (Шаг 1) .

k^{\star }=0

• (Шаг 4) Если то . ^[4]

x^{\star }(k+1)\neq x^{\star }(k)

k^{\star }=k+1

Будущие работы [ править ]

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

Расширенные работы [ править ]

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

Ссылки [ править ]

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

[tamura11a-1] Тамура, К .; Ясуда, К. (2011). «Первичное исследование спиральной динамики, вдохновленное оптимизацией». IEEJ Transactions по электротехнике и электронике . 6 (S1): 98–100. DOI : 10.1002 / tee.20628 .

[tamura11b-2] Тамура, К .; Ясуда, К. (2011). «Оптимизация, вдохновленная спиральной динамикой». Журнал передового вычислительного интеллекта и интеллектуальной информатики . 132 (5): 1116–1121. DOI : 10.20965 / jaciii.2011.p1116 .

[tamura16a-3] а б Тамура, К .; Ясуда, К. (2016). «Алгоритм спиральной оптимизации с использованием периодических направлений спуска» . Журнал SICE по контролю, измерениям и системной интеграции . 6 (3): 133–143. Bibcode : 2016JCMSI ... 9..134T . DOI : 10,9746 / jcmsi.9.134 .

[tamura17a-4] а б Тамура, К .; Ясуда, К. (2020). «Алгоритм спиральной оптимизации: условия и настройки сходимости» . IEEE Transactions по системам, человеку и кибернетике: системы . 50 (1): 360–375. DOI : 10.1109 / TSMC.2017.2695577 .

[5] Cruz-Дуарте, JM, Мартин-Диас, И., Муньос-Minjares, JU, Санчес-Галиндо, LA, Авина-Сервантес, JG, Гарсия Перес, A., & Correa-Cely, CR (2017). Первичное исследование алгоритма стохастической спиральной оптимизации. Международное осеннее совещание по энергетике, электронике и вычислительной технике (ROPEC) 2017 IEEE, 1–6. https://doi.org/10.1109/ROPEC.2017.8261609

[nasir15a-6] Насир, АНК; Тохи, МО (2015). «Улучшенный алгоритм спиральной динамической оптимизации с инженерным приложением». IEEE Trans. Syst., Man, Cybern., Syst . 45 (6): 943–954. DOI : 10.1109 / tsmc.2014.2383995 .

[nasir16a-7] Насир, АНК; Исмаил, РМТР; Тохи, МО (2016). «Адаптивный метаэвристический алгоритм спиральной динамики для глобальной оптимизации с приложением к моделированию гибкой системы» (PDF) . Appl. Математика. Modell . 40 (9–10): 5442–5461. DOI : 10.1016 / j.apm.2016.01.002 .

[ouadi13a-8] Уади, А .; Bentarzi, H .; Ресиуи, А. (2013). «многокритериальный дизайн цифровых фильтров с использованием техники спиральной оптимизации» . SpringerPlus . 2 (461): 697–707. DOI : 10.1186 / 2193-1801-2-461 . PMC 3786071 . PMID 24083108 .

[benasla14a-9] Benasla, L .; Belmadani, A .; Рахли, М. (2014). «Алгоритм спиральной оптимизации для решения комбинированных экономических и эмиссионных задач». Int. J. Elect. Power & Energy Syst . 62 : 163–174. DOI : 10.1016 / j.ijepes.2014.04.037 .

[sidarto15a-10] Сидарто, штат Калифорния; Кания, А. (2015). «Нахождение всех решений систем нелинейных уравнений с помощью спиральной динамики вдохновило оптимизацию с кластеризацией». Журнал передового вычислительного интеллекта и интеллектуальной информатики . 19 (5): 697–707. DOI : 10.20965 / jaciii.2015.p0697 .

[KavehMahjoubi-11] Kaveh, A .; Махджуби, С. (октябрь 2019 г.). «Подход к оптимизации гипотрохоидной спирали для определения размеров и оптимизации компоновки ферм с множественными частотными ограничениями» . Инжиниринг с компьютерами . 35 (4): 1443–1462. DOI : 10.1007 / s00366-018-0675-6 .

[1]