Métodos de búsqueda
Funcion unimodal
La modalidad de las funciones es particularmente importante en optimización, el termino unimodal se refiere a funciones que tienen un solo extremo, mínimo o máximo, mientras que multimodal se refiere a funciones que presentan dos o más extremos.
Una función es unimodal sobre el intervalo a ≤ x ≤ b, si y solo sí es monótona a ambos lados del punto optimo del intervalo. En otras palabras si x* es el único punto mínimo del intervalo (a,b), luego se dice que f(x) es unimodal en el intervalo, si y solo sí para dos puntosa cualquiera x1 y x2 se cumple que:
x* ≤ x1 ≤ x2 --> f (x* ) ≤ f(x1) ≤ f(x2)
x* ≥ x1 ≥ x2 --> f (x* ) ≤ f(x1) ≤ f(x2)
Para que se cumpla esta propiedad (unimodalidad), la función no necesariamente debe ser continua, ya que lo mismo se cumple si es discreta. Si bien el concepto de unimodalidad es muy simple de plantear y puede convertirse en una estrategia eficiente para la búsqueda de un óptimo, tiene un inconveniente básico y es que para asegurar su cumplimiento debería conocerse exactamente el comportamiento de la función objetivo.
· Bajo la suposición de Unimodalidad, el mínimo local se transforma automáticamente en un mínimo global.
· Cuando la función No es Unimodal, son posibles múltiples mínimos locales, y el mínimo global solo se puede encontrar, localizando todos los mínimos locales, y seleccionando el mejor (menor f(x)).
· Invirtiendo el signo de la desigualdad obtenemos las definiciones para máximo local y global .
Búsqueda de Fibonacci
Con este método se conoce ya el rango inicial de búsqueda y en cada evaluación el método tiende a acorralar el punto óptimo.
El intervalo inicial de es L0 y se define ∆1 como el siguiente incremento:
donde n, es el número de iteraciones que se desea realizar (en función a la tolerancia de error que se desea) y Fn es el número de Fibonacci para n evaluaciones, y se define así: F0=F1=1, Fn=Fn-1+Fn-2, n=2,3,... , la secuencia de Fibonacci es entonces 1,1,2,3,5,8,13,21,34,55… Se tiene entonces x1 = ∆1 y x2 = L0 - ∆1
Se supone que se quiere minimizar a la función unimodal f(x). Entonces si f (x1) ≥ f( x2) , rechazamos el intervalo 0 ≤ x ≤x1 y si f (x1 ) ≤ f ( x2) , rechazamos el intervalo x2 ≤ x1 ≤ L0.
El proceso se repite hasta llegar al número n de iteraciones prefijadas. La efectividad en este caso, 1/Fn, mide la tolerancia del error en el entorno del punto óptimo. Así, por ejemplo, si se desea un error menor al 1%, se necesitan 11 evaluaciones de este método, puesto que F11=144 y 1/F11 = 1/144.
Búsqueda por la sección Dorada
La búsqueda (o método) de la sección dorada es una técnica para hallar el extremo (mínimo o máximo) de una función unimodal, mediante reducciones sucesivas del rango de valores en el cual se conoce que se encuentra el extremo. La técnica debe su nombre al hecho de que el algoritmo mantiene los valores de la función en tríos de puntos cuyas distancias forman una proporción dorada. El algoritmo es el límite de la búsqueda de Fibonacci (también descrita debajo) para un largo número de evaluaciones de la función. La búsqueda de Fibonacci y la búsqueda de la sección dorada fueron descubiertos por Kiefer (1953) .
Los valores de la función f (x) están en el eje vertical y el horizontal es el parámetro x . El valor de f (x) ha sido calculado ya para los tres puntos x1,x2 y x3 , y . Dado que f2 es más pequeño que f1 y que f3, es evidente que el mínimo se encuentra dentro del intervalo desde x1 hasta x3 (porque es unimodal) .
Este método requiere que ambos intervalos sean de igual tamaño. Si no lo son, es posible que una "mala suerte" pueda llevar a utilizar el intervalo más grande muchas veces, ralentizando así la convergencia del método. o. Para garantizar que b = a + c , el algoritmo debe escoger x4 = x1 + (x3—x2).
La búsqueda de la sección dorada escoge los espacios entre estos puntos de forma tal que se mantenga la proporción entre ellos y los de los puntos subsecuente x1, x2, x4 o x2, x4, x3. Al mantener la misma proporción durante todo el algoritmo, se evita la situación en la cual x2 está muy cerca de x1 o x3 , y se garantiza que la longitud del intervalo se estreche con la misma proporción en cada paso.
Matemáticamente, para asegurar que el espaciado después de evaluar f(x4) es proporcional al espaciado antes de la evaluación, si f(x4) = f4a y el nuevo trío de puntos es x1 x2 y x4 , y entonces se quiere:
En cambio, si f(x4) = f4a y el nuevo trío de puntos es x2,x4 y x3 , entonces se quiere:
Eliminando c de este sistema de dos ecuaciones se obtiene:
donde φ es la proporción dorada:
La aparición del número dorado en el espaciado proporcional de la evaluación de los puntos es el motivo por el cual este algoritmo de búsqueda recibe su nombre.
Método de Interpolación Cuadrática
Cuando el polinomio que conviene es de 2º grado la interpolación recibe el nombre de cuadrática. El polinomio interpolador es único, luego como se encuentre da igual., sin embargo, a veces los cálculos son muy laboriosos y es preferible utilizar un método que otro. A la vista de los datos se decide.
En el ejemplo 1 se da el método de resolver el sistema para encontrar los valores que determinan a la función cuadrática (a, b y c) .
También podemos utilizar la expresión del polinomio interpolador así:
y= a + b(x-x0) + c(x-x0)(x-x1), con lo que la búsqueda de los coeficientes es muy sencilla.
Lagrange (1736-1813) dio una manera simplificada de calcular los polinomios interpoladores de grado n Para el caso de un polinomio de 2º grado que pasa por los puntos (x0, y0 ), (x1, y1), (x2, y2):
Que es la fórmula de Lagrange para n=2, con frecuencia se tienen que estimar valores intermedios entre valores conocidos. El método mas común empleado para este propósito es la interpolación polinomial.
Recuérdese que la fórmula general de un polinomio de n-ésimo orden es:
Para n + 1 puntos, existe uno y sólo un polinomio de n-ésimo orden o menor que pasa a través de todos los puntos. Por ejemplo, hay sólo una línea recta (es decir un polinomio de primer orden) que conecta dos puntos.
El polinomio de interpolación consiste en determinar el único polinomio de n-ésimo orden que se ajusta a los n + 1 puntos dados. Este polinomio proporciona una fórmula para calcular los valores intermedios.
Aunque existe uno y sólo un polinomio de n-ésimo orden que se ajusta a los n + 1 puntos, existen una gran variedad de fórmulas matemáticas mediante las cuales se puede expresar este polinomio. En esta unidad se estudian dos técnicas alternativas que están bien condicionadas para implementarse en una computadora (PC)., estos son los polinomios de Newton y de Lagrange.
Métodos de Búsqueda Multidimensionales
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 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.
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.
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.
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 procesos.
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.
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 restricción, 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 recibe 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 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 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.
Método de Fletcher – Reeves
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étodos de Variaciones Cíclicas
Variaciones Cíclicas: (Serie temporales) se refiere a las oscilaciones de larga duración alrededor de la recta o curva de tendencia; estos ciclos, como se llaman a veces, pueden ser o no periódicos, es decir, puede seguir o no exactamente caminos analógicos después de intervalos de tiempo iguales.
Estos se caracterizan por tener lapsos de expansión y contracción, los movimientos se consideran cíclicos solo si se produce en un intervalo de tiempo superior al año.
1. Métodos para determinar la tendencia de las variaciones cíclicas:
Los Métodos Gráficos
· Se efectúa la representación gráfica de la serie ordenada Yt.
· Se unen mediante segmentos rectilíneos todos los puntos altos de la serie, obteniéndose una poligonal de cimas.
· Se realiza lo mismo con los puntos bajos, obteniéndose la línea poligonal de fondos.
· Se trazan perpendiculares al eje de abscisas por los puntos cimas y fondos.
· La tendencia viene dada por la línea amortiguada que une los puntos medios de los segmentos.
. Los Métodos de las Medias Móviles
Empleando 3 observaciones
· Partimos de la serie temporal observada Yt .
· Se obtienen sucesivas medias aritméticas para cada Yt, con un número de observaciones anteriores y posteriores fijado de antemano. Si el número de observaciones es impar la media Yt, está centrada y coincide con el período t.
· La serie formada por las medias de Yt, nos indica la línea amortiguada de la tendencia 6 .
Empleando 4 observaciones
· Partimos de la serie temporal observada Yt.
· Se obtienen las sucesivas medias aritméticas Si el número de observaciones empleados para obtener la media es par, Yt no está centrada y no coincide con el período t, y habrá que volver a calcular una nueva media aritmética Yt, utilizando los Yt, obteniendo de esta manera una nueva serie de medias móviles centradas. Como se puede observar la serie de las medias obtenidas no está centrada, y debemos obtener una nueva serie de medias centradas, a partir de la serie “ descentrada ” .
· La serie formada por Yt, nos indica la línea amortiguada de la tendencia.
3. Los Método Analítico de los Mínimos Cuadrados:
· Obtendremos la tendencia a partir de la recta Yt= a+ bt, siendo Yt, la media anual de las observaciones trimestrales de los casos anteriores.
· Calculamos los coeficientes “a” y “b” de la recta de regresión. Deshaciendo el cambio de variable, tendremos la siguiente predicción de la tendencia.
Comentarios
Publicar un comentario