Evop

Esta técnica fue propuesta por el estadístico ingles George E.P. Box en 1957. Su algoritmo, denominado Evolutionary Operation (EVOP) se propuso en el contexto de optimización de producciónindustrial.

EVOP.-
Este algoritmo requiere (2N + 1) puntos, de los cuales 2N son las Esquinas de un hipercubo, con centro en el otro punto. Se comparan entre sí los (2N + 1) valores de la función y seidentifica el mejor punto entre ellos. En la siguiente iteración, se forma otro hipercubo alrededor del mejor punto. Si en cualquier iteración, no se mejora el punto actual, entonces se reduce el tamañodel hipercubo. Este proceso continúa hasta que el hipercubo se vuelve muy pequeño.

Pasos del EVOP
Algoritmo

Paso 1:

• Elegir un punto inicial x(0) y parámetros de reducción de tamaño _i paratodas las variables de decisión, i = 1, 2, . . . ,N.
• Elegir una tolerancia _.
• Hacer ¯x = x(0)
Paso 2:

• IF ||_|| < _ THEN Terminar
• ELSE crear 2N puntos sumando y restando _i/2 de cadavariable en el punto ¯x

Paso 3:

• Calcular los valores de la función en los (2N + 1) puntos.
• Encontrar el punto con el menor valor de la función.
• Hacer que el punto mínimo sea ¯x.

Paso4:

• IF ¯x = x(0), reducir los parámetros de tamaño _i = _i/2. GOTO Paso 2.
• ELSE x(0) = ¯x. GOTO Paso 2.

Nótese que en el algoritmo, x(0) siempre contiene al mejor punto. Por tanto, al finalde su ejecución, x(0) se vuelve nuestra mejor aproximación al ´optimo. Es evidente de este algoritmo que se requiere evaluar 2N veces la función objetivo por cada iteración. Por tanto, el número deevaluaciones de la función que se requieren crece exponencialmente con N. Sin embargo, el algoritmo es fácil de implementar y ha sido exitoso en la solución de muchos problemas industriales.
Puedeverse fácilmente que en EVOP, la convergencia del algoritmo depende del tamaño del hipercubo inicial, de su ubicación y del parámetro de reducción de tamaño (_i) elegido. Comenzar con una _i grande es...