Простая и эвристическая оптимизация

На этой неделе на конференции Rmetrics прошла интересная дискуссия об эвристической оптимизации. Начальная точка была проста: в сложных задачах оптимизации (здесь мы имеем в виду множество локальных максимумов, например), нам не обязательно нужны чрезвычайно продвинутые алгоритмы, которые очень быстро сходятся, если мы не можем гарантировать, что они достигают оптимума. Очень быстрая сходимость с большой числовой точностью до некоторой точки (это не та точка, которую мы ищем) бесполезна. И некоторые алгоритмы могут быть намного медленнее, но, по крайней мере, они с большей вероятностью сходятся к оптимальному. С чего бы мы ни начали.
Мы испытали это с Матье, в то время как мы искали максимальную вероятность нашего MINARпроцесс: генетический алгоритм выполнил чрезвычайно хорошо. Идея предельно проста и естественна. Давайте рассмотрим в качестве отправной точки следующий алгоритм,

1. Начните с некоторых 
2. На шаге  нарисуйте точку   в окрестности  ,  

• либо   тогда  
• или   тогда 

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

• либо  тогда  
• или   тогда 

для некоторых  . Чтобы проиллюстрировать идею, рассмотрим следующую функцию

> f=function(x,y) { r <- sqrt(x^2+y^2);
+ 1.1^(x+y)*10 * sin(r)/r }

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

> x0=15
> MX=matrix(NA,501,2)
> MX[1,]=runif(2,-x0,x0)
> k=.5
> for(s in 2:501){
+  bruit=rnorm(2)
+  X=MX[s-1,]+bruit*3
+  if(X[1]>x0){X[1]=x0}
+  if(X[1]<(-x0)){X[1]=-x0}
+  if(X[2]>x0){X[2]=x0}
+  if(X[2]<(-x0)){X[2]=-x0}
+  if(f(X[1],X[2])+k>f(MX[s-1,1],
+    MX[s-1,2])){MX[s,]=X}
+  if(f(X[1],X[2])+k<=f(MX[s-1,1],
+    MX[s-1,2])){MX[s,]=MX[s-1,]}
+}

 

 

Это не всегда сходится к оптимальному,

а иногда мы просто пропустили это из-за крайне неудачного

Обратите внимание, что если мы запустим 10 000 сценариев (с разными случайными шумами и начальной точкой), в 50% сценариев мы достигнем максимума. Или, по крайней мере, мы рядом с ним, сверху.
Что, если мы сравним со стандартной процедурой оптимизации, такой как Nelder-Mead, или квази градиент? Поскольку мы ищем максимумы в ограниченной области, мы можем использовать следующую функцию:

> g=function(x) f(x[1],x[2])
> optim(X0, g,method="L-BFGS-B",
+ lower=-c(x0,x0),upper=c(x0,x0))$par

В этом случае, если мы запустим алгоритм с 10 000 случайных начальных точек, это то, где мы заканчиваем, внизу справа (в то время как эвристический метод находится слева),