Métodos de Simulación (MUIA) PDF

Máster Universitario en Inteligencia Artificial MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas ÍNDICE 1....

Máster Universitario en Inteligencia Artificial MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas ÍNDICE 1. Optimización global y local 2. Métodos clásicos - Búsqueda aleatoria pura - Métodos de multicomienzo - Métodos de direcciones aleatorias 3. Métodos modernos - Recocido/enfriamiento simulado - Algoritmos genéticos 4. Referencias MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas 1. Optimización global y local Supongamos que queremos resolver el siguiente problema de optimización: min f(x) s. a x ÎX donde X es el conjunto factible (definido por un conjunto de restricciones) y f: X → R la función objetivo. x*Î X es mínimo global del problema si f(x*) ≤ f(x), para todo x Î X. xoÎ X es mínimo local del problema si f(xo) ≤ f(x), para todo x Î X: 0 < ||x – xo|| ≤ δ para cierto δ > 0. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Ejemplo. Sea la función f: R →R representada gráficamente en la siguiente figura, tomando como región factible el intervalo [-2, 3] Dicha función tiene un mínimo local en el punto x = -1, mientras que el mínimo global (dentro de la región factible) se encuentra en el punto x = 2. Es importante identificar/alcanzar el mínimo global. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Heurísticas más populares à Basadas en la mejora de la técnica de Búsqueda Local (BL). Procedimiento iterativo en el que partiendo de una solución inicial se va mejorando progresivamente mediante la aplicación de una serie de modifica- ciones locales o movimientos. Sean X el conjunto de soluciones factibles, xi la solución de la iteración i-ésima, E[xi] un entorno de xi y xi* la mejor solución en E[xi]. El esquema es: Seleccionar una solución inicial x1en X Hacer x* = x1, f* = f(x1), i = 1 Mientras xi ≠ xi* xi+1 = xi* i=i+1 Encontrar xi*: f(xi*) < f(x), para todo x en E[xi] Posibilidad → entornos centrados en el punto y con radio r, para la distancia euclídea, es decir, E[xn] = [xn - r, xn + r]. Obviamente, intersecaremos los entornos con la región factible cuando sea necesario. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Ejemplo (problema continuo). Supongamos que tenemos el problema de progra- mación no lineal min f(x) = x3 - 60x2 + 900x + 100 s.a -1 ≤ x ≤ 40 f(x) -1 10 20 30 40 X Sean entornos de radio 1 y comenzamos por x1 = 20. Aplicando BL, obtenemos x2 = 21, x3 = 22, x4 = 23,..., x11 = 30. En este punto, para todo x ÎE[x11], f(x) ≥ f(x11), luego x11* = x11 y el algoritmo para. Obtenemos, por lo tanto, un mínimo local en x*=30, con valor f*=100. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Ejemplo (problema discreto). Problema del viajante o del cartero chino (Nem- hauser y Wolsey, 1988). Un viajante, partiendo de una ciudad, debe visitar un conjunto de ciudades volviendo a la ciudad de la que partió, pasando por cada ciudad una única vez y con coste o distancia mínima. para cada capa solo puedo ir de una sola ciudad a otra ciudad si en la etapa k he salido de i a j, en la siguiente tengo que salir de j e ir a otra diferente de i MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas numero de soluciones factibles = todas las permutaciones de 5 elementos Sea x = {x1, x2, x3, x4, x5} una solución factible genérica. Entorno asociado a x se define como todos los caminos que se pueden obtener a partir de x mediante una trasposición de 2 ciudades. Sea x1={1,2,3,4,5}, con f(x1)=19. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas La siguiente tabla recoge todas las soluciones factibles pertenecientes al entorno de x1. intercambiar posiciones de 2 elementos La mejor solución en el entorno de x1 es x2 = {1,2,3,5,4} (podríamos haber considerado también la solución {3,2,1,4,5}, con el mismo valor en f). Las soluciones factibles en el entorno de x2 son: con la nueva solucion {1,2,3,5,4} calculo soluciones de su entorno Se cumple la condición de parada y x2 es el mínimo (se trata en realidad del mínimo global). MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas 2. Métodos clásicos Para los problemas de optimización a los que nos enfrentamos no existen condiciones generales de optimización global a diferencia de lo que ocurre con la optimalidad local, como las condiciones de Karush-Kuhn-Tucker, lo que dificulta el problema. Por ello, debemos optar entre: métodos determinísticos que funcionan sólo bajo condiciones restrictivas (éstos requieren la simplificación del sistema real bajo estudio con el fin de que cumpla condiciones que fundamentan la teoría del modelo en uso, lo que en sistemas complejos podría llevarnos a resolver un sistema muy lejano del real bajo estudio) o modelos estocásticos, que incorporan algún elemento probabilístico. Para estos últimos suele utilizarse el término convergencia probabilística o garantía, que aseguran que bajo ciertas condiciones se obtiene el óptima global con probabilidad alta. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Búsqueda aleatoria pura Consiste en generar aleatoriamente un número grande de soluciones y escoger la mejor. Sean X el conjunto de soluciones factibles, xi la solución de la iteración i-ésima, f* el mejor valor obtenido de f y x* el valor asociado a f*. El esquema es: f* = ∞ Para i = 1 hasta N Generar xi ~ U(X) Si f(xi) < f*, hacer f* = f(xi), x* = xi Implementación sencilla si se dispone de un método para muestrear uniforme- mente de X. El método no es muy eficiente, pues no utiliza información sobre f. Es sencilla su paralelización y demostración de convergencia bajo condiciones débiles. Dos posibles mejoras son: MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas 1. Utilizar una distribución no uniforme si se dispone de información sobre la localización del óptimo. 2. Iniciar una optimización local desde el óptimo x* obtenido. Ejemplo. Supongamos de nuevo que tenemos el problema de programación no lineal min f(x) = x3 - 60x2 + 900x + 100 s.a -1 ≤ x ≤ 40 f(x) -1 10 20 30 40 X MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas En la siguiente tabla se muestran 20 valores escogidos de forma aleatoria en el conjunto factible y sus valores asociados para la función a minimizar: Marcado con un asterisco se muestra el valor que menor valor proporciona para la función objetivo, resultado de la aplicación de este algoritmo, x* = 29.86 y f* = 100.55. Si aplicamos búsqueda local desde x* obtenemos el mínimo local x* = 30. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Métodos de multicomienzo La versión básica del método de multicomienzo genera N puntos desde los que se comienza una optimización con un método local proponiendo como solución la mejor así obtenida. Sean X el conjunto de soluciones factibles, xi la solución de la iteración i-ésima, f* el mejor valor obtenido de f y x* el valor asociado a f*. El esquema es: f* = ∞ Desde i = 1 hasta N Generar xi ~ D(X) Aplicar el algoritmo local desde xi con óptimo xi* Si f(xi*) < f*, hacer f* = f(xi*), x* = xi* D es una distribución que recoge, cuando sea posible, la información disponible sobre el óptimo de f. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Continuación del ejemplo. Generamos 10 valores de forma uniforme del intervalo [-1, 40] y aplicamos el método de máximo descenso a partir de cada uno de ellos, obteniendo los resultados que se muestran en la siguiente tabla: Por tanto, el mínimo se alcanza en -1. Posible inconveniente del método es que algunas optimizaciones locales que parten de distintas soluciones iniciales pueden conducir al mismo mínimo local. Se han propuesto varias ideas para mitigar este problema. Las principales son: Reducción. Se elimina una fracción de las peores soluciones iniciales. Concentración. Se agrupan las soluciones por proximidad, mediante algún método de análisis de conglomerados (Romesburg, 1984), de forma que soluciones. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas que pertenezcan a un mismo conglomerado se asimilan a soluciones que conducen a un mismo óptimo. La demostración de convergencia del método es sencilla. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Métodos de direcciones aleatorias Sean X el conjunto de soluciones factibles, xi la solución de la iteración i-ésima, f* el mejor valor obtenido de f y x* el valor asociado a f*. La mayoría de los métodos de direcciones aleatorias se adaptan al esquema siguiente: Seleccionar x1 en X, f* = f(x1), x* = x1, i = 1 Hasta que se satisfaga el criterio de parada Generar ε i ~ Fi Hacer xi+1 = D(xi, εi), i = i + 1 Si f(xi+1) < f*, hacer f* = f(xi+1), x* = xi+1 Distintas elecciones de Fi y D conducen a distintos algoritmos. Por ejemplo, si Fi = U(X) y D(x, ε) = argmin{f(x), f(ε)}, recuperamos el método de búsqueda aleatoria pura. En muchos casos, se suele escoger Fi como distribución uniforme centrada en xi y con cierto radio, o normal con media xi y matriz de varianzas-covarianzas fija. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas El nombre del método proviene de que (x, ε) definen una línea aleatoria y, en muchos casos, D se escoge mediante búsqueda lineal en la dirección (ε - x). En particular, en algunas versiones del algoritmo básico se hace D(x, ε)= x + α* (ε - x) α* = argminα f(x + α(ε - x)), habitualmente con α Î [0,1] ó α ≥ 0. La convergencia del algoritmo es de demostración sencilla. Sin embargo, resulta complicado proporcionar reglas de parada con garantía de convergencia. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas 3. Métodos modernos Recocido Simulado Búsqueda Tabú De Búsqueda Global Noising methods Búsqueda en entornos variables Manejan una única solución cada … iteración Algoritmos genéticos Scatter search Algoritmos meméticos Metaheurísticas Evolutivas Algoritmos culturales Algoritmos de nubes de partículas Manejan un conjunto de soluciones o de partículas inteligentes (población) en cada iteración … GRASP Colonia de hormigas Constructivas Concentración heurística POPMUSIC Parten de una solución inicial vacía … y van añadiéndole componentes has- ta construir una solución. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Recocido/enfriamiento simulado Se introduce para superar el inconveniente del método de máximo descenso de quedar atrapado en óptimos locales. Se debe a Kirpatrick et al. (1983) y Cerny (1985), en Science y Journal of Opti- mization Theory and Application, respectivamente. En ambos artículos se aplica al problema del viajante. Se ha estudiado bastante el problema de convergencia. La idea del RS surge de la metalurgia y la termodinámica: mediante un enfriamiento lento se consigue un sólido de entropía mínima. Al principio se aceptan todos los movimientos, lo que permite explorar todo el espacio de soluciones. Posteriormente, la temperatura decrece de forma gradual, lo que significa que se hace más selectiva la aceptación de una nueva solución. Al final, sólo se aceptan movimientos que mejoran la solución actual. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas El método no busca la mejor solución en un entorno E(xi) de la solución actual xi, sino que escoge al azar una solución y Î E(xi), y Si f(y) ≤ f(xi), y se convierte en la actual solución. En caso contrario, se selecciona alguna de las dos alternativas siguientes de acuerdo con alguna probabilidad (o ley probabilística) - y se convierte en la solución actual con probabilidad p(i) - xi permanece como solución actual con prob. complementaria 1- p(i) Típicamente, p(i): 1. decrece con el tiempo (i) al disminuir también la temperatura, y 2. decrece con el deterioro de f (f(y) - f(xi)) MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Algoritmo Inicialización. Escoger una solución inicial x1Î X. Hacer x* = x1 , f* = f(x1), i = 1 y escoger T1 > 0. Pasos i = 1,2,... ; xi denota la solución actual Generar aleatoriamente y Î E(xi) Si f(y) < f(xi), hacer xi+1 = y, si f(y) < f *, hacer x* = y, f* = f(y). En caso contrario (f(y) ≥ f), generar u ~ U(0,1). æ f ( y ) - f ( xi ) ö -çç ÷ T ÷ Si p(i) = e è i ø> u, hacer xi+1 = y En caso contrario (p(i) ≤ u), hacer xi+1 = xi Actualizar Ti Hasta satisfacer el criterio de parada MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Selección del valor inicial de la temperatura Si se escoge un valor próximo a cero, no posibilita empeoramiento. Si el valor es muy alto, se ralentiza. Sugerencia: Tomar T1 tal que la probabilidad inicial de aceptación de soluciones peores sea alta, por ejemplo, 0.9. Aceptación de nuevas soluciones Por analogía con la termodinámica (distribución de Boltzman) se suele escoger la probabilidad æ f ( y )- f ( x ) ö i -çç ÷ ÷ Ti p(i ) = e è ø donde Ti es la temperatura. Otras expresiones de p(i) en Serafini (1992). Si Ti es grande, entonces p(i) es grande lo que significa que se aceptan más transiciones a valores peores. Si Ti se reduce, entonces p(i) disminuye y por tanto el número de transiciones. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Actualización de la temperatura Si el decrecimiento es muy lento, la ejecución es lenta. Si el decrecimiento es muy rápido, se aumenta la probabilidad de quedar atrapado en un mínimo local. El esquema habitual es mantener la temperatura constante durante L iteraciones. Después decrece multiplicándose por (0 < α < 1), de forma que, después de hL pasos la temperatura es ThL = αh T1. Un valor típico de α es 0.95. (véase Hajek, 1988). T T1 T2 T3...... iteraciones L 2L 3L 4L MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Criterio de parada 1) Parar si f∗ no ha mejorado al menos un ε1%, tras k1 iteraciones de L pasos. 2) Parar si el número de transiciones aceptadas es menor que el ε2% de L tras k2 iteraciones de L pasos. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Ejemplo (Recocido Simulado) Supongamos que tenemos el problema de programación no lineal min f(x) = x3 - 60x2 + 900x + 100 s.a -1 ≤ x ≤ 40 f(x) -1 10 20 30 40 x Comenzamos con x1 = 20 y vemos cómo es capaz de salir del mínimo local. Utilizando entornos de radio 2 y probando con varios valores de x2, decidimos utilizar T1 = 4000. Para el resto de parámetros, consideramos L = 10 y α = 0.9. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas En las siguientes tablas recogemos lo ocurrido en los 20 primeros pasos. æ 1951.17 -1485.92) ö -ç ÷ p(4) = e è 4000 ø = 0.89019 MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Continuamos y tomamos como regla de parada que realice 500 iteraciones más. El resultado obtenido para el mínimo es -860.40, alcanzándose en el punto x* = -0.9994. Recordemos que el mínimo global es -1 con valor -861. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Comportamiento del recocido simulado MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Algoritmos genéticos Se introduce para superar el inconveniente del método de máximo descenso de quedar atrapado en óptimos locales. Holland (1975), Adaptation in Natural and Artifical Systems, The University of Michigan Press. Goldberg (1989), Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley. Los algoritmos genéticos son, de hecho, variantes del método de multicomienzo. Por medio de operaciones que derivan de los principios de la evolución natural, se identifican soluciones prometedoras, a partir de las que, eventualmente, se puede proceder a realizar una optimización local. Supongamos que disponemos de una codificación del conjunto factible en un alfabeto finito. Obtener tal codificación puede no resultar sencilla. En el caso continuo, conlleva una discretización de X. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas El algoritmo genético parte de un conjunto (población) de N soluciones (individuos) que evoluciona, manteniéndose su tamaño en las siguientes iteraciones. Es decir, la generación i+1 se obtiene a partir de la i a través de una serie de operaciones. Designamos mediante {x1i,..., xNi} = X(i) la población en la iteración i-ésima. Se consideran, entonces, las siguientes operaciones sobre la población X(i): Selección de buenos individuos. Se escogen de forma determinística o probabilística, y con reemplazamiento, los mejores individuos de la población actual (tomando como referencia la función a minimizar). 1 / f ( x ij ) Probabilísticamente à p(escoger xji) = ål (1 / f ( x i l )) Determinísticamente à Tomar los individuos con menor valor para f(xji) MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Cruce de individuos. Dos individuos parten e intercambian partes de su codificación. La elección de los individuos a cruzar y la selección del punto de intercambio se puede hacer de forma determinística o probabilística. Supongamos dos individuos con codificaciones xji = (xj1i,..., xjni) e xki = (xk1i,..., xkni) pertenecientes a la población de la iteración i-ésima. Suponiendo que la posición de cruce (escogida de forma aleatoria o probabilística) es la m-ésima (m < n), los individuos resultantes serían: (xj1i,..., xjm-1i , xkmi..., xkni) y (xk1i,..., xkm-1i , xjmi,..., xjni) Mutación de un individuo. Se cambia el valor del algún/os elementos de la codificación de un individuo. La decisión de mutar o no un individuo, la selección del elemento de la codificación sobre la que se realiza la mutación y el nuevo valor que se le asigna a dicho elemento pueden tener carácter probabilístico. La mutación se aplica a los hijos o descendientes obtenidos como consecuencia de la operación de cruce, que a su vez se realiza sobre buenos individuos. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Selección de malos individuos. Se escogen de forma determinística o probabilística, y sin reemplazamiento, los peores individuos de la población actual (tomando como referencia la función a minimizar.) f ( x ij ) Probabilísticamente à p(escoger xji) = å l) f l ( x i Determinísticamente à Tomar los individuos con mayor valor para f(xji) Estos individuos son sustituidos en la siguiente población por los obtenidos como resultado de las operaciones descritas anteriormente. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Algoritmo Seleccionar aleatoriamente la población inicial X(1) ={x11,..., xN1} Hacer f* = arg mini (f(xi1)), x*= mini (f(xi1)), j = 1 Hasta que se cumpla la condición de parada: - Seleccionar 2M buenos individuos de la población {y1,..., y2M} - Para k = 1,…,M cruzar los pares (y2k-1, y2k) obteniendo los pares {z2k-1, z2k} - Para k = 1,…,2M mutar zk obteniendo wk. Sea Mj = {w1,…,w2M} - Seleccionar 2M malos individuos de la población Vj = {v1,..., v2M} - Hacer j = j+1 y X(j) = (X(j-1) \ Vj) U Mj - Actualizar f* y x*. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Ejemplo (Algoritmo genético) Supongamos que tenemos el problema de programación no lineal min f(x) = x3 - 60x2 + 900x + 100 s.a -1 ≤ x ≤ 40 f(x) 0 10 20 30 40 x Codificamos las soluciones: Sumamos 1 a cada solución y la multiplicamos por 1000. Estamos considerando el intervalo [0,41] para evitar ambigüedad en la codificación. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Así, cada solución está asociada a cinco valores. Tomamos una población inicial de tamaño N = 8: X(1) = {0.532, 8.876, 13.751, 18.873, 25.123, 30.752, 33.491, 39.163}. 1 / 561.969 » 0.139 1 / 561.969 +... + 1 / 3388.147 x61 3 1 7 5 2 x11 0 1 5 3 2 x61 3 1 7 5 2 x61 3 1 7 5 2 Selección de 4 (M = 2) buenos individuos: Determinísticamente: Probabilísticamente: MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Formamos dos pares al azar y realizamos las operaciones de cruce y mutación: (1) Para seleccionar la posición de cruce obtenemos dos números aleatorios de una U[0,1]. Suponiendo que se tratan de los valores 0.6166 y 0.5822, en ambos casos el intercambio se intercambia a partir del tercer elemento de la codificación. (2) Obtenemos cuatro valores de la distribución U[0,1] para ver sobre que individuos realizo mutación (0.013, 0.977, 0.256, 0.640). Los valores superiores a 0.5 me indican los individuos sobre los que realizar la mutación. A continuación, selecciono el elemento de la codificación que voy a mutar para cada individuo (0.360 à posición 2 y 0.788 à posición 4) y también de forma aleatoria elijo el nuevo valor que tomará el elemento de la codificación. (0.1077 à valor 1, 0.819 à valor 8). MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Seleccionamos los 4 peores individuos de la población: 561.969 » 0.03639 561.969 +... + 3388.147 x21 0 9 8 7 6 x71 3 4 4 9 1 Vj x41 19873 x81 40163 Determinísticamente: Probabilísticamente: MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Calculamos la nueva población X(j+1) = (X(j) \ Vj) U Mj MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas 4. Referencias Cerny, V. (1985). A Thermodynamical Approach to the Travelling Salesman problem: An Efficient simulated Algorithm, Journal of Optimization Theory and Application 45, 41-51. Charon, I. y Hudry, O. (2001a). The Noising methods: A Survey, in C.C. Ribeiro y P. Hansen (eds.), Essays and Surveys in Metaheuristics, 469-492, Kluwer Academic Publishers. (disponible en Aula Virtual) Charon, I. y Hudry, O. (2001b), The noising methods: A generalization of some metaheuristics, European Journal of Operational Research 135, 86-101. (disponible en Aula Virtual) Coello C., Van Veldhuizen D. y Lamont G. (2002). Evolutionary Algorithms for Solving Multi- Objective Problems, Kluwer Academic Publishers. Engelbrecht, A.P. (2005), Fundamentals of Computational Swarm Intelligence, John Wiley & Sons. De Jong, K.A. (2006). Evolutionary computation: a unified approach, MIT Press. Dorigo, M., Maniezzo, V. y Colorni, A. (1996). The Ant System: Optimization by a Colony of Cooperating Agents, IEEE Tranactions on Systems, Management and Cybernetics-Part B 26, 1- 13. (disponible en Aula Virtual) MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Dorigo, M. y Stützle, T. (2003). The Ant Colony Optimization Metaheuristic: Algorithms, Applications and Advances, in F. Glover and G. Kochenberger (eds.) Handbook of Metaheuristics, 251-285, Kluwer Academic Publishers. Dorigo, M. y Stützle, T. (2004). Ant Colony Optimization, The MIT Press. Feo, T.A. y Resende, M.G.C. (1995). Greedy Randomized Adaptive Search Procedures, Journal of Global Optimization 6 (2), 109-133. Glover, F. (1977). Heuristics for Integer Programming using Surrogate Constraints, Decision Science 8, 156-166. Glover F. (1986). Future Paths for Integer Programming and Links to Artificial Intelligence, Computers and Operations Research 13, 533-549. Glover F. (1989). Tabu Search- Part I., ORSA Journal on Computing 1, 190-206. Glover F. (1990). Tabu Search- Part II., ORSA Journal on Computing 2, 4-32. Glover, F. y Kochenberg, G.A. (1993). Handbook of Metaheuristics. Operations Research Management Science, Kluwer Academic Publishers. Glover, F. y Laguna, M. (1997). Tabu Search, Kluwer Academic Publishers. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Glover, F. y Melián, B. (2003). Tabu Search, Revista Iberoamericana de Inteligencia Artificial 19, 29-48. (disponible en Aula Virtual) Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Hajek, B. (1988). Cooling schedules for optimal annealing, Mathematical Operations Research 13, 311-329. Hansen, P., Mladenovic, N. y Moreno, J.A. (2003). Variable Neighbourhood Search, Revista Iberoamericana de Inteligencia Artificial 19, 77-92. (disponible en Aula Virtual) Holland, J.H. (1975). Adaptation in Natural and Artificial Systems, The University of Michigan Press. Kennedy, J. y Eberhart, R.C. (1995), Particle Swarm Optimization, Proceedings 1995 IEEE International Conference on Neural Networks, 1942-1948, IEEE Press. (disponible en Aula Virtual) Kennedy, J. y Eberhart, R.C. (2001), Swarm Intelligence, Morgan Kauffmann. Kirkpatrick, S., Gelatt, C.D. y Vechi, M.P. (1983). Optimization by Simulated Annealing, Science 220, 671-680. MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Larranaga, P. y Lozano, J.A. (eds.) (2001), Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Springer. Manrique, D. y Ríos, J. (2006). Redes de Neuronas Artificiales y Computación Evolutiva, Facultad de Informática, Universidad Politécnica de Madrid. Moscato, P. (1999). Memetic Algorithms: A Short Introduction, in D. Corne, M. Dorigo, F. Glover (eds.), New Ideas in Optimization, 219-234, McGraw Hill. Moscato, P. y Cotta, C. (2003). A Gentle Introduction to Memetic Algorithms, in F. Glover, G. Kochenberger (eds.), Handbook of Metaheuristics, 105-144, Kluwer Academic Publishers. Moscato, P. y Cotta, C. (2003). Una Introducción a los Algoritmos Meméticos, Revista Iberoamericana de Inteligencia Artificial 19(2), 131-148. (disponible en Aula Virtual) Nemhauser, G. y Wolsey, L. (1988). Integer and Combinatorial Optimization, Wiley. Reynolds, R.G. (1994). An Introduction to Cultural Algorithms, Proceedings of the 3rd Annual Conference on Evolutionary Programming, World Scienfific Publishing, 131–139. (disponible en Aula Virtual) Resende, M.G.C. y Ribeiro, C.C. (2003). Greedy randomized adaptive search procedures, in F. Glover y T. Kochenberger (eds.), Handbook of Metaheuristics, 219-249, Kluwer. (disponible en Aula Virtual) MÉTODOS DE SIMULACIÓN Capítulo 5. Simulación y optimización. Metaheurísticas Romesburg, H.C. (1984). Cluster Analysis for Researchers, Lifetime Learning Pub. Rosing K.E. y ReVelle C.S. (1997). Heuristic concentration: two stage solution construction, European Journal of Operational Research 97, 75-86. (disponible en Aula Virtual) Serafini, P. (1992). Simulated Annealing for Multiple Objective Optimization Problems, in G.H. Tzeng, H.F. Wang, V.P. Wen and P.L. Yu, (eds.), Proceedings of the Tenth International Conference on MCDM, 87-96, Springer Verlag. É.D. Taillard y S. Voss (2001). POPMUSIC: Partial Optimization Metaheuristic Under Special Intensification Conditions, in C. Ribeiro y P. Hansen (eds.), Essays and surveys in metaheuristics, 613-629, Kluwer.