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

Имитация отжига (SA) широко используется в задачах поиска (например, поиск наилучшего пути между двумя городами), где пространство поиска дискретно (разные и отдельные города). Замечательное объяснение с примером можно найти в этой книге, написанной Стюартом Расселом и Питером Норвигом. AIMA.

Код на Python для псевдокода можно найти здесь.



aimacode / aima-python
Реализация на Python алгоритмов из книги Рассела и Норвига« Искусственный интеллект - современный подход … github.com»



Чтобы интуитивно понять, что такое имитация отжига, нам нужно иметь краткое представление о Восхождении на холм. Восхождение на холм - это алгоритм, который стремится найти наиболее оптимальное состояние системы. Давайте быстро рассмотрим пример.

Предположим, что есть 5 состояний с именами A, B, C, D, E, и у нас есть наш алгоритм AI, который в данном случае является восхождением по холму, первоначально в состоянии A. Давайте назначим значения энергии состояний в порядке убывания и Предположим, что состояние с наименьшей энергией будет наиболее оптимальным. Для облегчения понимания возьмем параметр Optimal Points, который обратно пропорционален энергии и определяет, насколько хорошее состояние. Таким образом, оптимальные точки должны быть в порядке возрастания, и давайте установим значения 6, 7, 8, 9, 10 в состояния A, B, C, D, E.

Здесь E - наиболее оптимальное состояние, потому что у него меньше энергии, а A - наименее оптимальное состояние, потому что у него больше энергии.

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

def hillClimbing(system):
    current_state = system.initial_state
    while(True):
         if energy(neighbour_left_current) <=  energy(neighbour_right_current):
    next_state = neighbour_left_current
  else:
    next_state = neighbour_right_current
  if (energy(next_state) < energy(current_state)):
    current_state = next_state
  else:
    final_state = current_state
    return final_state

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

Теперь мы видим, что алгоритм переходит в состояние E, поскольку оно имеет наименьшее количество энергии и, следовательно, является наиболее оптимальным состоянием.

Но у этого подхода есть проблема. Если мы присвоим значения 5, 6, 7, 6 и 8 состояниям A, B, C, D и E соответственно с начальным состоянием в A, мы никогда не достигнем состояния E, поскольку алгоритм выберет C в качестве конечного состояния. потому что C имеет больше оптимальных точек (меньше энергии), чем смежные состояния, и когда текущее состояние и следующее состояние совпадают, алгоритм остановится. Как видим, это не глобальный оптимум. Это проблема восхождения на холм. Оно может прийти к локальному оптимальному состоянию и пометить его как конечное состояние.

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

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

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

SA устраняет проблему «шансов достичь локального оптимума» с помощью этого метода. Он проверяет все состояния на начальных этапах (когда температура высока) и тщательно выбирает состояние в качестве следующего состояния при понижении температуры.

def simulatedAnnealing(system, tempetature):
    current_state = system.initial_state
    t = tempetature
    while (t>0):
          t = t * alpha
          next_state = randomly_choosen_state
          energy_delta = energy(next_state) - energy(current_state)
          if(energy_delta < 0 or (math.exp( -energy_delta / t) >= random.randint(0,10))):
             current_state = next_state
    final_state = current_state
    return final_state

Здесь альфа (который равен ‹1) - это скорость распада, при которой температура понижается. Коэффициент вероятности math.exp(-energy_delta / t ).

Это очень простая версия SA, и мы изменим ее в следующей части, пока будем пытаться использовать SA для помещения объектов в кластеры. Если то, что я объяснил, не имело для вас никакого смысла, обратитесь к этому видео, потому что действительно важно понимать SA, чтобы двигаться дальше. Скоро будет еще одна часть этого документа - код в сообщении, объясняющий эту Бумагу.

ПРИМЕЧАНИЕ. Есть несколько версий SA, которые объясняются по-разному. Есть несколько примеров, когда начальная температура установлена ​​на ноль и начинает повышаться до предела. Здесь P_E будет math.exp(energy_delta / t ) и альфа ›0. Пожалуйста, не запутайтесь с такими примерами. Просто убедитесь, что вы поняли концепцию.