Heurística para la optimización

9

Como es viernes, es hora de una pregunta de CW. Estoy buscando heurísticas que tengan un amplio uso en problemas de optimización. Para limitar el alcance a más heurísticas 'amigables con la teoría', aquí están las reglas (algunas arbitrarias, otras no)

  • Debe ser un método bien definido sin numerosos parámetros y con un tiempo de ejecución concreto (tal vez por iteración)
  • Debería tener algunos resultados teóricos conocidos asociados con él (tasa de convergencia, límites de aproximación si los hay, propiedades estacionarias, etc.)
  • Debe tener una amplia aplicabilidad y al menos una aplicación emblemática donde sea el método de elección o uno de los pocos.
  • no debería estar inspirado en la naturaleza (aunque esto parece una objeción frívola, estoy tratando de excluir algoritmos genéticos, optimización de colonias de hormigas y similares).

Lo ideal es que las respuestas tengan el siguiente formato: aquí hay un ejemplo.

Nombre : Optimización alterna

Objetivo : minimizar una función (generalmente no convexa) F(X,y)

sol(X)=minyF(X,y)h(y)=minXF(X,y)

Algoritmo : la iteración comienza con .yothXyo,yyo

  1. Xyo+1argminXF(X,yyo)
  2. yyo+1argminyF(Xyo+1,y)

Aplicación más conocida : significa, par más cercano iterado.k

Teoría : Resultados conocidos sobre medios , condiciones generales suficientes para la optimización global del marcok

ps Puede encontrar que su respuesta termina como una conferencia en un seminario de algoritmos que estoy planeando :)

Suresh Venkat
fuente
"No debería estar inspirado por la naturaleza (aunque esto parece una objeción frívola, estoy tratando de excluir algoritmos genéticos, optimización de colonias de hormigas y similares)". Entonces, ¿no hay recocido simulado, mecánica estadística, etc.?
Joe Fitzsimons
En realidad no tengo ningún problema con el recocido simulado, y cuando escribí esto, estaba tratando de encontrar una manera de mantener SA y excluir GA :).
Suresh Venkat

Respuestas:

2


w(θ)F(θ)2θRnorteF(θ)Rmetrow(θ)R


Lpags

espejo2imagen
fuente