Металл и алгоритм отжига

В этой статье я продемонстрирую алгоритм Брайна Люка "Отжиг", который помогает найти подходящее решение среди множества возможных. И его реализацию на примере задачи о N - Ферзей.

Алгоритм вероятностный и его преимущество в том, что он изучает разные варианты, чтобы не застрять на плохом решении, в отличие от жадных алгоритмов.

Понимание алгоритма

В области оптимизационных алгоритмов особое место занимает Алгоритм Отжига — мощный метод, вдохновленный процессами термической обработки металлов, используемый для улучшения кристаллической структуры материалов. Основная идея заключается в том, чтобы начать с системы при высокой температуре и постепенно снижать её, приближаясь к состоянию с минимальной энергией. Этот алгоритм, разработанный Брайаном Луком в конце 1980-х годов, получил широкое распространение в таких областях, как инженерия, информатика, финансы и биология, благодаря своей способности эффективно находить решения в сложных пространствах.

Реализация

• Инициализация: Сначала выбираем случайное начальное состояние и устанавливаем температуру. Она определяет вероятность принятия нового состояния на каждом шаге: при высокой температуре вероятность ниже, при низкой — выше

• Итеративное изменение: Генерируем новое состояния путем минимального случайного изменения текущего состояния

• Проверка нового состояния: Сравниваем новое состояние с текущим, принимая лучшее из двух. Но если оно хуже, то принимаем с определенной вероятностью, зависящей от температуры по
  формуле:

• Расписание охлаждения: Постепенно снижаем температуру

• Завершение: При выполнении условия завершения - остановка

Решение на примере задачи

Рассмотрим решение на примере задачи о шахматах, где нужно расположить N - Ферзей на доске размера N, не угрожающих друг другу по диагоналям, вертикалям и горизонталям.

Для простоты будем хранить доску в одномерном массиве, где значения соответствуют позициям по оси Y. Все значения разные, что гарантирует, что ферзи не угрожают друг другу ни по вертикали, ни по горизонтали.

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

Чтобы изменить состояние на каждом шаге, будем менять позиции двух случайных ферзей по оси X.

Алгоритм в виде кода на Kotlin:

for (temperature in temperatures) {
  val new = current.randomSwapQueens()
  // acceptNewScore is always true here new.score < current.score
  val acceptNewScore = exp((current.score - new.score) / temperature) > Random.nextFloat()
  if (acceptNewScore) {
    current = new
    if (current.score < best.score) {         
      best = current  
      if (best.score == 0) {  return  }  
    } 
  }
}

val temperatures = sequence { 
  var t = 0.7        // initial temperature
  while (t > 0.02) { // final temperature 
    repeat(400) {    // steps per change
      yield(t)       // send t to sequence
    }  
    t *= 0.99        // decreasing coefficient
  }
}

val QueenBoard.score get() = this.threatingQueenCount

Решение позволяет добиться времени выполнения ~180 ms для поля размера 100 на чипе Apple M1.

Завершение

Алгоритм Отжига, описанный в этой статье, демонстрирует свою эффективность как мощный инструмент для поиска оптимальных решений в сложных задачах, таких как поиск кратчайшего маршрута и проектирование схемы СБИС — размещение компонентов на кристалле для минимизации площади.

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

Все исходники можно найти на github: simulated annealing.
Cравнить их с источником на C github: archive data
Спасибо за прочтение!