Спираль разделяет глобальное (синий) и интенсивный (красный) поведение
спиральная оптимизация (SPO) Алгоритм - это несложная концепция поиска, вдохновленная спиральными явлениями в природе. Первый алгоритм SPO был предложен для двумерной безусловной оптимизации на основе двумерных спиральных моделей. Это было распространено на n-мерные проблемы путем обобщения двумерной спиральной модели на n-мерную спиральную модель. Существуют эффективные настройки для алгоритма SPO: настройка направления периодического спуска и настройка сходимости.
Содержание
- 1 Метафора
- 2 Алгоритм
- 3 Настройка
- 3.1 Настройка 1 (Настройка направления периодического спуска)
- 3.2 Настройка 2 (Настройка конвергенции)
- 4 Будущие работы
- 5 Расширенные работы
- 6 Ссылки
Метафора
Мотивация для сосредоточения внимания на спиральных явлениях было связано с пониманием того, что динамика, порождающая логарифмические спирали, разделяет поведение диверсификации и интенсификации. Поведение диверсификации может работать для глобального поиска (исследования), а поведение интенсификации позволяет интенсивный поиск текущего найденного хорошего решения (эксплуатация).
Алгоритм
Алгоритм спиральной оптимизации (SPO)
Алгоритм SPO - это алгоритм многоточечного поиска, не имеющий градиента целевой функции, который использует несколько спиральных моделей, которые могут быть описаны как детерминированные динамические системы. Поскольку точки поиска следуют по логарифмическим спиральным траекториям к общему центру, определяемому как текущая лучшая точка, могут быть найдены лучшие решения и общий центр может быть обновлен. Общий алгоритм SPO для задачи минимизации при максимальной итерации (критерий завершения) выглядит следующим образом:
0) Установите количество точек поиска и максимальное количество итераций . 1) Поместите начальные точки поиска и определите центр , , а затем установите . 2) Определите скорость шага с помощью правила. 3) Обновите точки поиска: 4) Обновить центр:
Настройка
Эффективность поиска зависит от настройки составной матрицы вращения R (θ) {\ displaystyle R (\ theta)}, скорости шага r (k) {\ displaystyle r (k)}, и начальные точки xi (0) (i = 1,…, m) {\ displaystyle x_ {i} (0) ~ (i = 1, \ ldots, m)}. Следующие настройки являются новыми и эффективными.
Настройка 1 (настройка направления периодического спуска)
Эта настройка является эффективной настройкой для задач большого размера при максимальной итерации k max {\ displaystyle k _ {\ max}}. Условия для R (θ) {\ displaystyle R (\ theta)}и xi (0) (i = 1,…, m) {\ displaystyle x_ {i} ( 0) ~ (i = 1, \ ldots, m)}вместе гарантируют, что спиральные модели периодически генерируют направления спуска. Условие r (k) {\ displaystyle r (k)}работает для использования периодических направлений спуска при завершении поиска k max {\ displaystyle k _ {\ max}}.
- Установите R (θ) {\ displaystyle R (\ theta)}следующим образом: R (θ) = [0 n - 1 ⊤ - 1 I n - 1 0 n - 1] {\ Displaystyle R (\ theta) = {\ begin {bmatrix} 0_ {n-1} ^ {\ top} - 1 \\ I_ {n-1} 0_ {n-1} \\\ конец {bmatrix}}}где I n - 1 {\ displaystyle I_ {n-1}}- это (n - 1) × (n - 1) {\ displaystyle (n-1) \ times (n-1)}единичная матрица и 0 n - 1 {\ displaystyle 0_ {n-1}}- (n - 1) × 1 {\ displaystyle (n-1) \ times 1}нулевой вектор.
- Поместите начальные точки xi (0) ∈ Р n {\ displaystyle x_ {i} (0) \ in \ mathbb {R} ^ {n}}(i = 1,…, m) {\ displaystyle (i = 1, \ ldots, m)}произвольно, чтобы удовлетворить следующему условию:
min i = 1,…, m {max j = 1,…, m {rank [dj, i (0) R (θ) dj, i (0) ⋯ R (θ) 2 n - 1 dj, i (0)]}} = n {\ disp Laystyle \ 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}где dj, i (0) = xj (0) - xi (0) {\ displaystyle d_ {j, i} (0) = x_ {j} (0) -x_ {i} (0)}. Обратите внимание, что это условие почти полностью удовлетворяется случайным размещением, и поэтому никакая проверка на самом деле не подходит.
- Задайте r (k) {\ displaystyle r (k)}на этапе 2) следующим образом: r (k) = r = δ k max (постоянное значение) { \ displaystyle r (k) = r = {\ sqrt [{k _ {\ max}}] {\ delta}} ~~~~ {\ text {(постоянное значение)}}}где достаточно small δ>0 {\ displaystyle \ delta>0}, например δ = 1 / k max {\ displaystyle \ delta = 1 / k _ {\ max}}или δ = 10 - 3 {\ displaystyle \ delta = 10 ^ {- 3}}.
Настройка 2 (настройка сходимости)
Эта настройка гарантирует, что алгоритм SPO сходится к стационарной точке при максимальной итерации k max = ∞ {\ displaystyle k _ {\ max} = \ infty}. Параметры R (θ) {\ displaystyle R (\ theta)}и начальные точки xi (0) (i = 1,…, m) {\ displaystyle x_ {i} (0) ~ (i = 1, \ ldots, m)}совпадают с указанная выше настройка 1. Настройка r (k) {\ displaystyle r ( k)}выглядит следующим образом.
- Задайте r (k) {\ displaystyle r (k)}на шаге 2) следующим образом: r (k) = {1 (k ⋆ ≦ k ≦ k ⋆ + 2 N - 1) час (К ≧ К ⋆ + 2 N), {\ Displaystyle г (к) = {\ begin {case} 1 (k ^ {\ star} \ leqq k \ leqq k ^ {\ star } + 2n-1), \\ h (k \ geqq k ^ {\ star} + 2n), \ end {cases}}}где k ⋆ {\ displaystyle k ^ {\ star}}- это итерация, когда центр обновляется заново на шаге 4) и h = δ 2 n, δ ∈ (0, 1) {\ displaystyle h = {\ sqrt [{2n }] {\ delta}}, \ delta \ in (0,1)}, например, δ = 0,5 {\ displaystyle \ delta = 0,5}. Таким образом, мы должны добавить в алгоритм следующие правила о k ⋆ {\ displaystyle k ^ {\ star}}:
- • (Шаг 1) k ⋆ = 0 { \ displaystyle k ^ {\ star} = 0}.
- • (Шаг 4) Если x ⋆ (k + 1) ≠ x ⋆ (k) {\ displaystyle x ^ {\ star} (k + 1) \ neq x ^ {\ star} (k)}, затем k ⋆ = k + 1 {\ displaystyle k ^ {\ star} = k + 1}.
Будущее работает
- Алгоритмы с указанными выше настройками детерминированы. Таким образом, включение некоторых случайных операций делает этот алгоритм мощным для глобальной оптимизации. Cruz-Duarte et al. продемонстрировал это, включив в спиральные поисковые траектории стохастические возмущения. Однако эта дверь остается открытой для дальнейших исследований.
- Чтобы найти подходящий баланс между спиралями диверсификации и интенсификации в зависимости от целевого класса задачи (включая k max {\ displaystyle k _ {\ max}}) важен для повышения производительности.
Расширенные работы
Много расширенных исследований было проведено на SPO из-за его простой структуры и концепции; эти исследования помогли повысить эффективность глобального поиска и предложили новые приложения.
Ссылки