WikiDer > Алгоритм спиральной оптимизации - Википедия

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

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

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

Метафора

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

Алгоритм

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

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

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

Параметр

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

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

Этот параметр является эффективным для задач большого размера при максимальной итерации. ${ Displaystyle к _ { макс}}$. Условия на ${ Displaystyle R ( theta)}$ и ${ Displaystyle х_ {я} (0) ~ (я = 1, ldots, м)}$ вместе гарантируют, что спиральные модели периодически генерируют направления спуска. Состояние ${ Displaystyle г (к)}$ работает, чтобы использовать периодические направления спуска под поисковое прекращение ${ Displaystyle к _ { макс}}$.

• Набор ${ 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 (п-1) раз (п-1)}$ единичная матрица и ${ displaystyle 0_ {n-1}}$ это ${ Displaystyle (п-1) раз 1}$ нулевой вектор.
• Поместите начальные точки ${ Displaystyle х_ {я} (0) в mathbb {R} ^ {п}}$ ${ Displaystyle (я = 1, ldots, м)}$ случайным образом, чтобы удовлетворить следующему условию:

${ displaystyle min _ {я = 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 г (к)}$ на Шаге 2) следующим образом:${ displaystyle r (k) = r = { sqrt [{k _ { max}}] { delta}} ~~~~ { text {(постоянное значение)}}}$ где достаточно малая ${ displaystyle delta> 0}$ Такие как ${ Displaystyle дельта = 1 / к _ { макс}}$ или же ${ displaystyle delta = 10 ^ {- 3}}$.

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

Этот параметр гарантирует, что алгоритм SPO сходится к стационарной точке при максимальной итерации. ${ Displaystyle к _ { макс} = infty}$. Настройки ${ Displaystyle R ( theta)}$ и начальные точки ${ Displaystyle х_ {я} (0) ~ (я = 1, ldots, м)}$ такие же, как и в приведенной выше настройке 1. Настройка ${ Displaystyle г (к)}$ как следует.

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

•(Шаг 1) ${ Displaystyle к ^ { звезда} = 0}$.

• (Шаг 4) Если ${ Displaystyle х ^ { звезда} (к + 1) neq x ^ { звезда} (к)}$ тогда ${ Displaystyle к ^ { звезда} = к + 1}$.

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

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

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

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

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