Главная — Семестр 2

Обновлено: 16 March 2019 17:03

Как завещал эконом: между n и n+1 переывчик о().

Описание

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

  1. Хука Дживса
  2. Алгоритм имитации отжига
  3. Совмещаем алгоритм Хука Дживса и имитации отжига

Хука Дживса

Как обсуждали в классе, псевдо код алгоритма Хука Дживса выглядит следующим образом:

  • Пока шаг больше погрешности
    • Ищем первую понравившеюся точку (\(a_1\))
    • Если нашли
      • Строим новую точку (\(a_2\)) в том же направлении на том же расстоянии до тех пор, пока фунция в том направлении уменьшается (если ищем минимум)
    • иначе уменьшаем шаг

Алгоритм имитации отжига

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

Для алгоритма необходимо определить следующие параметры помимо начальной точки и самой функции:

  • как будет выбираться новая точка
  • функция вероятности
  • какая будет начальная температура и как она будет снижаться

Вероятность

Вероятность можно задать как \[P(dF, T_i) = \exp(-\frac{dF}{T_i})\]

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

\[P(dF, T_i) = \exp(-\frac{dF}{T_i * \overline{|dF|}})\]

где \(\overline{|dF|}\) - значение среднего изменения функции. На первом шаге \(\overline{|dF|} = |dF|\).

Температура

Можно задать уровень снижения температуры и максимальное значение, а можно просто рассчитать скорость кбывания температуры при данных значениях \(T_{start}\) и \(T_{end}\).

\(T_{start}\) надо взять такой, чтобы вероятность перехода в первой момент была равна \(p_{start}\).

Из выражения \(P(dF, T_i)\) надо найти, какой должна быть \(T_1\), чтобы \(P(dF, T_i) = p_{start}\).

Пусть \(p_{start} = 0.8\).

Для алгоритма скорость убывания температуры расчитаем как

\[g = (\frac{T_{end}}{T_{start}})^{\frac{1}{n}}\]

где \(n\) - заданное количество шагов (пусть будет 50).

Тогда на каждом шаге, температура будет убывать как

\[T_i = T_{i-1} / g\]

Алгоритм (минимум)

  1. Задачем начальную температуру, начальную точку \(x\).
  2. for i = 1 to n
    1. for j = 1 to m
      • Ищем случаного соседа. \(x_i = x_{i-1} + dx\), где \(dx\) - случайное приращение в квадрате от -1 до 1
      • Если \(F(x_i) - F(x_{i-1}) < 0\), то переходим в новую точку, иначе расчитываем вероятность \(P(dF, T_i)\) и генерурем случайную величину при помощи функции go = rbinom(n = 1, size = 1, prob = P). Если go = 1, то переходим в новую точку.
    2. Обновляем температуру

Совмещаем алгоритм Хука Дживса и имитации отжига

Придумать, как скорректировать алгоритм Хука Дживса на алгоритм имитации, а именно сделать так, чтобы когда точка \(a_2\) страновилась хуже, то существовала вероятность всё равно в неё перейти.

Функции

\[f(x,y) = \frac{sin((x^2 + y^2)^{(1/2)})}{(x^2 + y^2)^{(1/2)}}\]

\[f(x,y) = 0.2 + x^2 + y^2 - 0.1 * cos(6\pi *x) - 0.1*cos(6\pi*y)\]

Рисование

Для каждого алгоритма должен рисоваться график countour, на котором видно как “шагал” алгоритм.

 /|_/|
= 0.o =
( )_( )