Optimizacion No Lineal: 2010

Técnicas de Búsqueda Multidimensionales

Algunos modelos son:

Eliminación multivariable

a) Downhill simplex
En el método downhill simplex, cada punto de un simplex representa una posible solución del problema. El simplex correspondiente a una función de N variables se representa por una matriz de (N+1)xN. Cada columna de la matriz contiene las N coordenadas de un vértice

El algoritmo consiste en la búsqueda de un mínimo siguiendo una sucesión de operaciones sobre el simplex: expansión, contracción, y reflexión. Primero se localiza el vértice nmax donde la función objetivo f toma el valor máximo, y se lo refleja respecto de la cara opuesta del simplex determinando un nuevo punto n prueba. Se evalúa la función en una serie de puntos que pertenezcan a la recta perpendicular a dicha cara y que contiene a n prueba.

Si en alguno de esos puntos, la función toma un valor menor que f(nmax), entonces ese punto
reemplaza a nmax en el simplex. En caso contrario, se conserva el simplex original y se lo contrae en todas las direcciones alrededor del mínimo y se vuelve a ejecutar el algoritmo. El método invariablemente converge a un mínimo luego de una serie de contracciones.

b) Algoritmos genéticos

El método de optimización por algoritmos genéticos simula un proceso de evolución y selección natural en una población de individuos. Cada individuo de la población representa una posible solución. Por otra parte, un cromosoma caracteriza a un individuo y está formado por un conjunto de genes, cada uno de los cuales es un parámetro de optimización.

Métodos geométricos

El método geométrico consiste en suponer que el crecimiento de una comunidad es en todo instante proporcional a su población, es decir que responde a la ecuación:

Este método da resultados superiores, por lo que se califica de “optimista” y debe emplearse con mucha precaución. Tan sólo debe aplicarse a comunidades en plena dinámica de crecimiento, con grandes posibilidades de desarrollo y horizontes líbres.

Métodos lógicos

La optimización lógica mediante eliminación de redundancias tiene una aplicación muy limitada. Esto es debido a que no es una técnica completa, en el sentido de que una vez que se han eliminado todas las redundancias de un circuito no es posible continuar optimizándolo mediante esta técnica. Para obtener un algoritmo general de optimización, la eliminación de redundancias se puede completar con su operación inversa: la adición de redundancias. Esta operación inversa tiene por objetivo la creación de nuevas redundancias, de forma que, tras la eliminación de estas últimas, el circuito presenta menor área o menor retraso o ambas cosas a la vez.

Búsqueda Aleatoria
Este método se basa en la generación de una secuencia de aproximaciones mejoradas al mínimo, cada una de las cuales se deriva de la aproximación previa. Entonces, si xi es la aproximación al mínimo obtenida en la etapa (o iteración) (i − 1), la nueva aproximación en la etapa i se obtiene de: xi+1 = xi + λui donde λ es una longitud de paso (valor escalar), ui es un vector aleatorio unitario generado en la i- esima etapa.

Algunas de las ventajas de los métodos de búsqueda aleatoria son las siguientes:

Estos métodos funcionan aunque la función objetivo sea discontinua y no diferenciable en alguno de sus puntos. Estos métodos pueden usarse para encontrar el mínimo global cuando la función objetivo posee varios mínimos relativos.

Estos métodos son aplicables cuando otros métodos fallan debido a dificultades locales tales como funciones con formas determinadas y regiones de búsqueda difíciles de explorar. Aunque estos métodos no son muy eficientes, pueden usarse en las etapas iniciales de la optimización para detectar la región donde es más probable encontrar el mínimo global. Una vez localizada esta región, puede usarse una técnica más eficiente para ubicar con mayor precisión el mínimo global.

Procedimientos de aproximación estocásticos

Consiste en la elaboración de modelos de optimización con escenarios, Muestreo de escenarios: Si el número de casos que hay que evaluar es muy elevado es necesario reducirlo. Por ello se procede a un muestreo de los mismos. Se determina la función de probabilidad acumulada y se procede al muestreo ( el muestreo se realiza por el método de Montecarlo).

La función objetivo final se determina empleando el método de la aproximación media de muestra. Finalmente se analizan los resultados: determinándose el tamaño de muestra mínimo para obtener una solución fiable. Para luego analizar la solución y diseñar el proceso.

Búsqueda en forma de malla

El método de la malla fija ha sido utilizado en problemas en donde la geometría del objeto, o las propiedades físicas del cuerpo cambian con el tiempo. En este trabajo se muestra la posibilidad de utilizar el método de la malla fija como alternativa al método de los elementos finitos convencional, para resolver problemas de elasticidad.

El desarrollo de los métodos para la optimización de estructuras ha sido bastante desordenado como resultado de la división de ideas: programación matemática (MP), criterios de optimalidad (OC), optimización estructural evolucionaria (ESO), microestructuras sólidas isótropas con penalización (SIMP), optimización estructural basada en el crecimiento biológico (BGSO), método de la curva de nivel (LSM), computación evolutiva (EC), etc. Existen diferentes métodos evolucionarios: estrategias evolutivas (ESs), programación evolucionaria (EP), programación genética (GP), y algoritmos genéticos (GAs); éstos últimos disponen de una base teórica más robusta, y están biológicamente mejor adaptados.

El objetivo de la optimización de estructuras es obtener un diseño, es decir, un conjunto de valores para las variables de diseño que hacen mínima una función objetivo, y satisfacen un conjunto de restricciones que dependen de estas variables. Los problemas de optimización de estructuras se pueden dividir en tres categorías: propiedades, forma, y topología

Método de búsqueda patrón: Hooke – Jeeves

El método de patrones de búsqueda de Hooke-Jeeves crea un conjunto de direcciones de búsqueda de manera iterativa. Este método se propuso en 1966 y fue uno de los primeros algoritmos en incorporar la historia previa de una secuencia de iteraciones en la generación de una nueva dirección de búsqueda.

La idea básica del algoritmo de Hooke-Jeeves es combinar movimientos “exploratorios” del tipo una-variable-a-la-vez con movimientos de “patrones” o aceleraciones, los cuales se regulan mediante algunas reglas heurísticas.

Los movimientos exploratorios examinan la vecindad del punto actual para encontrar el mejor punto alrededor del mismo. Posteriormente, se usan estos dos puntos (el actual y el mejor en su vecindad) para realizar un movimiento de “patrones”.

De tal forma, los movimientos exploratorios examinan el comportamiento local de la función y buscan localizar la dirección de cualquier pendiente existente en la zona. Los movimientos de patrones utilizan la información generada en la exploración para escalar rápidamente las pendientes.

Método de interpolación cuadrática de Powell

No usa derivadas
_ Se parte de un punto P0 y N direcciones (por ejemplo, base del espacio) (ui) arbitrarios
_ Se calculan los Pi, mínimos a lo largo de ui
_ Se elimina u1 y se añade nuevo uN = PN - P0
_ Nuevo P0 es mínimo a lo largo de nuevo uN
_ Direcciones se van haciendo conjugadas, y se llega a mínimo de forma cuadrática tras N iteraciones del ciclo
_ Problema de tendencia a dependencia lineal de (ui) (convergencia a mínimo de un subespacio):
_ Re inicialización de (ui) tras ≈ N iteraciones
_ Powell: Eliminación (salvo excepciones) de dirección en que f disminuyó más en lugar de u1; pérdida de direcciones conjugadas (y de convergencia cuadrática)

Método del ascenso acelerado

Proceso interactivo de modelo de primer orden ajustado para acceder a las cercanías del óptimo. Esto se logra realizando un conjunto de experimentos que requieren llamar al modelo de simulación con puntos de operación definidos en la dirección dada por el signo de los coeficientes del modelo ajustado, con incremento en las variables proporcionales a la magnitud de los coeficientes. Lo anterior se realiza mientras exista mejoramiento de la respuesta o hasta encontrarse con una restricción, debido a que, si se encuentra una restrincion, los experimentos deben realizarse a través de la dirección impuesta por el vector director de la misma. El mejor punto encontrado en la trayectoria de búsqueda se toma como el punto central para un nuevo diseño experimental.

Este método se experimenta en una función que emula el funcionamiento del mismo; para ello recie como parámetros los coeficientes del modelo ajustado, el margen de operación y el punto actual de operación, retornando un nuevo punto de operación.

Método de Newton – Raphson

Es un algoritmo eficiente para encontrar aproximaciones de los ceros o raíces de una función real. También puede ser usado para encontrar el máximo o mínimo de una función, encontrando los ceros de su primera derivada.

La idea de este método es la siguiente: se comienza con un valor razonablemente cercano al cero (denominado punto de arranque), entonces se reemplaza la función por la recta tangente en ese valor, se iguala a cero y se despeja (fácilmente, por ser una ecuación lineal). Este cero será, generalmente, una aproximación mejor a la raíz de la función. Luego, se aplican tantas iteraciones como se deseen. Supóngase f : [a, b] → R función derivable definida en el intervalo real [a, b]. Empezamos con un valor inicial x0 y definimos para cada número natural n.
Xn+1 = f(Xn) / f ‘ (Xn). Donde f ‘ denota la derivada de f.

Método de Davidon – Fletcher – Powell

El método de Davidon-Fletcher-Powell ha sido y sigue siendo una técnica de gradiente ampliamente utilizada. El método tiende a ser robusto; esto es, típicamente tiende a tener un buen comportamiento en una amplia variedad de problemas prácticas. La mayor desventaja de este tipo de métodos es su necesidad de almacenar la matriz A de N × N. Una de las dificultades practicas comunes de estos métodos es la tendencia de A(k+1) a estar mal condicionada, lo que causa una mayor dependencia a un procedimiento de re inicialización.

Método de Broyden – Fletcher

Es un método para solucionar un libre optimización no lineal problema. El método de BFGS se deriva de Método del neutonio en la optimización, usa técnicas que busca punto inmóvil de una función, donde gradiente es 0. El método del neutonio asume que la función se puede localmente aproximar como ecuación cuadrática en la región alrededor del grado óptimo, y utiliza los primeros y segundos derivados para encontrar el punto inmóvil.

Método de Fletcher – Reeves

Corresponde a la versión del método del gradiente conjugado en el caso de una función f general. La iteración se define de la siguiente manera:

Método de Smith.

Permite resolver el problema de varianza no constante en regresión en un solo paso, ya que simultáneamente se hallan las distribuciones posteriores de todos los parámetros involucrados, un problema que para la aproximación tradicional es complejo y requiere primero modelar la heteroscedasticidad y luego estimar los parámetros del modelo realizando los ajustes necesarios.

Dado que este proceso de generación de muestras es un proceso markoviano donde la distribución estacionaria es la distribución posterior de la cual se pretende extraer las muestras, se deben descartar los valores generados al comienzo del proceso. Este es un problema complejo pero se acostumbra eliminar los primeros 1000 valores y generar 5000 valores o más.

Optimizacion No Lineal

martes, 29 de junio de 2010

Integrantes del Blog

Métodos de Variaciones Cíclicas

Mètodo de Bùsquedas Multidimencionales