**IAIC** Optimización Global # Sobre Optimización La optimización de funciones es un tema de gran importancia tanto teórica como práctica. Los problemas de optimización se plantean en muchos contextos diferentes, en los que un escenario común es que se debe optimizar una medida objetivo con respecto a sus parámetros. Vamos a comenzar viendo la relación existente entre **Búsquedas** y **Optimización**, con el fin de usar los algoritmos que desarrollemos de optimización para resolver los problemas de búsqueda vistos en temas anteriores. Para ello, vamos a presentar algunas clases de algoritmos para la optimización global, es decir, para encontrar todos los mínimos o máximos globales de una función dada en un dominio concreto sin tener en cuenta ningún óptimo local. La optimización global es un campo amplio con muchas aplicaciones, y se han desarrollado muchos métodos de optimización deterministas y estocásticos (aquellos cuyos resultados dependen de procesos basados en variables aleatorias, por ejemplo, por medio del uso de números aleatorios generados mientras se ejecuta el algoritmo, aunque la función a optimizar sigue siendo determinista). Como ya vimos en el tema de búsquedas, los métodos heurísticos son estrategias para buscar en el dominio de forma *inteligente*. En relación a los algoritmos de optimización, entre los métodos heurísticos más habituales podemos encontrar la evolución diferencial, la computación evolutiva (incluidas, por ejemplo, las estrategias de evolución, los algoritmos genéticos y la programación genética), el templado simulado, la optimización basada en enjambres (por ejemplo, basada en enjambres de partículas y basada en colonias de hormigas) y la búsqueda tabú. Podemos considerar distintas clasificaciones dentro de la optimización, según atendamos a unas características u otras: * Dos ramas de la optimización son la optimización **continua** y la **discreta**. En la optimización discreta, algunas o todas las variables de la función objetivo son discretas, es decir, sólo asumen valores de un conjunto finito de valores o, como mucho, un conjunto disperso de valores similar a los números naturales. Dos campos importantes de la optimización discreta son la optimización combinatoria y la programación entera. * Además, los problemas de optimización pueden clasificarse en función de la presencia de restricciones sobre las variables independientes de la función objetivo (de forma similar a como vimos en Problemas de Satisfacción de Restricciones). Las restricciones pueden ser **duras**, que deben satisfacer obligatoriamente las variables independientes, o **blandas**, en las que se penaliza la función objetivo si no se satisfacen las restricciones (el valor de la penalización suele ir en función de la medida en que no se satisfagan). * En la elección del método de optimización también influye el coste computacional de la evaluación de la función objetivo. Si la función objetivo se da como una expresión analítica, normalmente es posible realizar muchas evaluaciones de la función, lo que hace que el problema de optimización sea más manejable. Pero si la función objetivo es costosa desde el punto de vista computacional (como el resultado de un experimento que hay que hacer en un laboratorio de química o de una simulación lenta), la elección del método de optimización es más limitada y también más importante. En este tema nos centraremos únicamente en un par de métodos que pueden ser característicos: el método del **Templado Simulado** y el de **Optimización por Enjambre de Partículas** (**PSO**). Dejamos fuera el método de **Algoritmos Genéticos**, no porque carezca de interés, sino porque es probable que el alumno ya los haya estudiado en otras asignaturas o lo vaya a hacer en el futuro. Todas estas variantes y requisitos plantean la cuestión de qué método utilizar cuando se presenta un problema de optimización. Por desgracia, no hay una respuesta general a esta pregunta, ya que **no existe el mejor algoritmo de optimización**. Esta incapacidad de responder adecuadamente a esta cuestión se formaliza en los **Teoremas No-Free-Lunch**: !!!note: No-Free-Lunch Los **Teoremas No-free-lunch** son resultados en optimización y complejidad computacional que implican que, para ciertos tipos de problemas, el coste computacional de encontrar una solución cuando se promedia sobre todos los problemas de una clase es el mismo para cualquier método de solución. En otras palabras, **no existe ningún método de optimización que supere a todos los demás métodos en todos los problemas**. Cualquier mejora del rendimiento en una clase de problemas siempre se ve compensada por una disminución del rendimiento en otra clase de problemas. Los métodos de optimización especializados tienen el mejor rendimiento para resolver una determinada clase de problemas. Todavía puede haber algoritmos que den buenos resultados en diversas clases de problemas, pero siguen siendo superados por los métodos especializados en cada una de ellas. Aunque estos resultados nos dicen que no existe ningún algoritmo de optimización ingenioso que funcione mejor que todos los demás algoritmos en todos los problemas, también motivan consideraciones especializadas y trabajos centrados en clases de problemas bien definidos, para los que existen algoritmos especializados que superan a los genéricos. # Optimización para Búsquedas Hasta ahora hemos visto métodos de resolución de problemas en los que el objetivo ha sido buscar un camino en un espacio de estados, ya sea porque estamos interesados en cómo alcanzar un estado final (búsqueda de estados simple), o porque es el propio camino el que nos interesa (planificación), pero podemos encontrarnos que no siempre es factible esta aproximación, algo que puede ocurrir por dos razones principalmente: * Porque este planteamiento resulte **demasiado artificial** y lejano al problema, por ejemplo, porque **no sea natural definir operadores de transición**, o porque **no sea una tarea sencilla definir una función heurística adecuada** para la búsqueda (que sea consistente y admisible). * Porque no hay buenas opciones de hallar una solución óptima debido a que el **tamaño del espacio de búsqueda es demasiado grande**, y en este caso nos podríamos conformar con una solución que podamos considerar **suficientemente** buena. !!!note Aunque antes hemos indicado que es normal añadir la restricción de que el Espacio de Estados sea finito, algo conveniente para los métodos seguidos en las búsquedas clásicas, ahora no es estrictamente necesario, y los métodos que veremos aquí también se pueden aplicar en casos en los que el Espacio de Estados es infinito, incluso no numerable (como los espacios euclídeos, $\mathbb{R}^n$). Si estamos ante un caso así, podemos optar por dos vías: 1. Si es relativamente asequible encontrar una solución inicial, aunque no sea demasiado buena, podemos cambiar nuestra tarea de buscar un camino entre estados a la de **encontrar una mejora sucesiva** de soluciones no óptimas en el espacio de soluciones. 2. Si no es posible encontrar una solución inicial (aunque no sea suficientemente buena) podemos ver si, partiendo de una solución no válida, podemos ir construyendo una solución que sí se vaya aproximando a una que sí lo sea. En este cambio de perspectiva, pues, lo que suponemos es que podemos navegar dentro del espacio de representación, realizando operaciones sobre ellas que pueden ayudar a mejorarlas. Estas operaciones no tienen por qué tener una representación en el mundo real, sino que son simplemente formas de manipular las posibles soluciones para encontrar otras opciones. El coste de estas operaciones no será tan relevante, ya que lo que estamos buscando es la calidad de las soluciones, y no la forma de llegar a ellas. Al igual que en las estrategias vistas en temas anteriores disponíamos de una función de coste que indicaba lo bueno que podía ser el camino que hacía uso de esas operaciones, ahora necesitamos una función que, según algún criterio (dependiente del dominio), medirá la calidad de las posibles soluciones y permitirá ordenarlas respecto a lo buenas que sean (en cierta forma, parecido a lo que hace una heurística para búsquedas, pero con menos propiedades impuestas). La estructura general que tendremos en este tipo de aproximaciones es similar a la que ya vimos en las búsquedas en estados de espacios: 1. Una **propuesta de solución inicial**. 2. **Operadores de transformación de la solución**, que permiten ir generando o modificando las propuestas de solución actuales. No tienen coste explícito asociado, pero se suelen buscar muy ligeras computacionalmente. 3. Una **función de calidad**, que debe medir lo buena que es una propuesta de solución y permitirá dirigir la búsqueda. A diferencia de las funciones heurísticas anteriores, en este caso esta función no indica cuánto falta para encontrar la solución que buscamos (y tampoco deben verificar condiciones adicionales como la admisibilidad o la consistencia), sino que proporciona una forma de comparar la calidad entre soluciones para indicarnos qué transformaciones pueden ser las más adecuadas. Debido a que puede no ser posible encontrar la mejor solución, saber cuándo hemos acabado la búsqueda dependerá totalmente del tipo de algoritmo que diseñemos, que tendrá que decidir cuándo debemos parar porque ya no sea posible encontrar una solución mejor o porque no merezca la pena seguir avanzando. En cierta forma, el proceso que se sigue es **similar al proceso de encontrar óptimos (máximos o mínimos) de funciones**, donde en este caso la función a optimizar es la función de calidad de la solución. En muchos casos, como los que a menudo nos encontramos en problemas de Inteligencia Artificial, las funciones de calidad con las que se trabaja no tienen una expresión analítica conocida, o no verifican las condiciones necesarias para aplicar algoritmos analíticos de búsqueda de óptimos en funciones, por lo que tenemos que explorar la función de calidad utilizando únicamente evaluaciones aisladas y, con suerte, lo que podamos obtener de los vecinos de la solución actual, es decir, haciendo uso únicamente de información local durante el proceso. # Templado Simulado Hay muchas veces en los que los algoritmos de optimización se quedan atascados enseguida en óptimos locales, no demasiado buenos globalmente. Para estos casos se han diseñado algoritmos que a veces pueden dar soluciones relativamente buenas. El algoritmo del **Templado Simulado** (**Simulated Annealing**, o **Recocido Simulado**) es uno de ellos y está inspirado en un fenómeno físico que se observa en el templado de metales y en la cristalización de disoluciones: !!!note: Templado Simulado en el Mundo Físico Todo conjunto de átomos o moléculas tiene un estado de energía que depende de la temperatura del sistema. A medida que el sistema se enfría, va perdiendo energía hasta que se estabiliza debido a los enlaces que se van formando entre los elementos del sistema (y que, cuando la temperatura es adecuadamente alta, no tienen fuerza suficiente para mantenerse y se crean y destruyen de forma continua). El fenómeno físico que se observa es que, dependiendo de cómo se realiza el enfriamiento, el estado alcanzado de energía final es muy diferente. Por ejemplo, si una barra de metal se enfría demasiado rápido la estructura cristalina a la que se llega al final está poco cohesionada (un número bajo de enlaces entre átomos, o mal distribuidos) y, consecuentemente, se rompe con facilidad. Si el enfriamiento se realiza más lentamente, el resultado final es totalmente diferente, el número de enlaces entre los átomos es mayor y está mejor distribuido, lo que proporciona una barra mucho más difícil de romper. Durante este enfriamiento controlado se observa que la energía del conjunto de átomos no disminuye de manera constante, sino que a veces la energía total puede ser mayor que en un momento inmediatamente anterior (y, si es necesario, se aporta energía artificalmente, como hace el herrero en el templado del hierro). Esta circunstancia hace que el estado final que se alcanza bajo estas condiciones controladas sea mejor que cuando el enfriamiento se hace rápidamente. Inspirados en este fenómeno físico podemos idear un algoritmo que permite, para ciertos problemas, obtener soluciones mejores que las proporcionadas por los algoritmos de búsqueda vistos hasta ahora. En este algoritmo el estado siguiente a explorar no será siempre el mejor vecino, sino que se elige aleatoriamente (en función de los valores de unos parámetros) de entre todos los vecinos (tanto los que pueden parecer mejores como los peores). Una ventaja de este algoritmo es que no hay por qué generar todos los sucesores de un estado (algo que puede ser muy costoso), basta elegir un sucesor al azar y decidir si continuamos por él o no (por lo que es un algoritmo estocástico). Además, puede aplicarse a problemas de optimización y búsqueda tanto continuos como discretos. Solo requiere dos operaciones sencillas: la elección de un punto de partida aleatorio, y una operación unaria que lleva un estado a un estado vecino. ![](./img/simann.jpg align="right")El algoritmo de templado simulado intenta transportar la analogía física al problema que se quiere solucionar: * En primer lugar, se denomina **función de energía** a la función que mide la calidad de una solución (es el equivalente a la función de energía del sistema físico). * Se considera un parámetro de control, que denominaremos **temperatura**, que permitirá controlar el funcionamiento del algoritmo. * También se tiene una función que depende de la temperatura y de la diferencia de calidad (incremento de energía) entre el estado actual y un sucesor. Esta función dirigirá la aceptación de los sucesores de la siguiente forma: * Cuanta mayor sea la temperatura, más probabilidad habrá de que al generar como sucesor un estado peor, este sea elegido. * La elección de un estado peor dependerá de su diferencia de calidad con el estado actual, cuanta más diferencia, menos probabilidad de elegirlo. * El último elemento es la **estrategia de enfriamiento**. Por ejemplo, el algoritmo podría realizar un número total de iteraciones prefijado y cada cierto número de ellas el valor de la temperatura disminuye en cierta cantidad, partiendo desde una temperatura inicial y llegando a $0$ (o a un valor mínimo) en la última iteración. La elección de estos dos parámetros (**número total de iteraciones** y **número de iteraciones entre cada bajada de temperatura**) determina el comportamiento completo del algoritmo, y puede modificar su eficiencia de forma considerable. Aunque hay algunos resultados teóricos acerca de la influencia de estos parámetros, en general hay que decidir experimentalmente cuál es la temperatura inicial más adecuada y también la forma más adecuada de hacer que vaya disminuyendo. Un pseudocódigo que se sigue esta idea es el siguiente (no es el único posible, ya que hemos fijado varios de los grados de libertad que hemos comentado): ~~~~~~~~ Algoritmo: Templado Simulado (T₀, s₀, N, γ < 1, ϵ > 0) T = T₀ while T > ϵ Repeat N: s₁ = Genera_vecino(s₀) ∆E = E(s₀) − E(s₁) if ∆E > 0 s₀ = s₁ else con probabilidad exp(∆E/T): s₀ = s₁ T = T ⋅ γ return s₀ ~~~~~~~~ Como en la analogía física, si el número de pasos es muy pequeño, la temperatura bajará muy rápidamente, y el camino explorado será relativamente aleatorio. Si el número de pasos es más grande, la bajada de temperatura será más suave y la búsqueda será mejor. El algoritmo favorece la disminución de la energía, $E$, ya que $\Delta E>0$ es equivalente a que $E(s_0)>E(s_1)$, y en ese caso $s_1$ se convierte en el estado actual. Cuando $\Delta E < 0$, se tiene que $e^{\Delta E/T} < 1$ y, de hecho: $$\displaystyle \lim_{T\to 0} e^{\Delta E/T}=0$$ por lo que el hecho de admitir nuevos estados que empeoran la búsqueda se hace cada vez más improbable a medida que avanza el algoritmo y la temperatura decae. Además, los estados que empeoran mucho la energía (es decir, aquellos que hacen que $\Delta E$ sea más negativo) se hacen menos probables que los que la empeoran menos. La introducción de la función de energía nos permite trasnformar la búsqueda en un problema de optimización (en este caso, de minimización), porque realmente pasamos de buscar un estado con ciertas propiedades generales a buscar un estado que tiene valor mínimo respecto a la función de energía considerada. Esta función tiene muchas similitudes con las funciones heurísticas de algoritmos como $A^∗$, ya que de alguna forma mide lo buena, o cerca de una solución ideal, que está el estado actual, pero tiene una ventaja computacional, y es que no imponemos ninguna propiedad adicional (en $A^∗$, la función heurística debía ser admisible para asegurar la convergencia a la solución, por ejemplo). En cualquier caso, a $E$ se le supone un comportamiento bastante básico: 1. $E(s)\geq 0$, para cualquier estado, $s$, de nuestro espacio. 2. $E(s)$ mínimo solo en el caso en que $s$ sea una solución adecuada del problema (es común que, a veces, se prepare $E$ para que su mínimo sea $0$). 3. $E(s_1) < E(s_2)$, si $s_1$ es *mejor solución* que $s_2$. Este algoritmo es especialmente bueno para problemas con un espacio de estados grande en los que el óptimo global está rodeado de muchos óptimos locales. Se puede utilizar también para problemas en los que encontrar una heurística discriminante es difícil (donde una elección aleatoria es tan buena como otra cualquiera), ya que en estos casos muchos otros algoritmos no tienen mucha información con la que trabajar y se quedan atascados enseguida, mientras que el templado simulado puede explorar un espacio de soluciones más grande y tiene mayor probabilidad de encontrar una solución buena. El mayor problema de este algoritmo es determinar los valores de los parámetros, y requiere una importante labor de experimentación que depende de cada problema. Los valores óptimos de estos parámetros varían con el dominio e incluso con el tamaño de la instancia concreta del problema. ## Mejoras al Templado Simulado ### Caso continuo Además de utilizarse en la búsqueda en espacios discretos (a veces también se le llama a este proceso **optimización combinatoria**), el templado simulado puede extenderse a la minimización de funciones continuas, donde si hay mucha variabilidad es muy fácil quedarse atascado en uno de los muchos mínimos locales. El problema empeora a medida que la dimensionalidad del problema (el número de variables que intervienen) crece. El método de templado, comparado con otros métodos habituales en búsqueda optimizada continua (como el [método simplex de Nelder-Mead](https://es.wikipedia.org/wiki/M%C3%A9todo_Nelder-Mead), o la [búsqueda aleatoria adaptativa GRASP](https://ccc.inaoep.mx/~emorales/Cursos/Busqueda/node66.html)) sobre una serie de funciones continuas de prueba, da muy buenos resultados, consiguiendo identificar el mínimo global, y de forma más eficiente en términos del número de evaluaciones de la función, pero sigue siendo un procedimiento costoso desde el punto de vista computacional, ya que el número de evaluaciones crece linealmente con el número de dimensiones. Este coste es menos prohibitivo que el de las otras técnicas, sobre todo porque el coste depende únicamente de la temperatura inicial, lo que significa que el tiempo de cálculo se conoce de antemano, una ventaja del algoritmo. ### Paralelización Uno de los principales problemas del templado simulado, tanto para el caso discreto como continuo, es el elevado tiempo de cálculo para encontrar una solución cercana o exactamente óptima. Este problema surge al proponer y evaluar los valores de las funciones para luego rechazarlos y puede mitigarse en cierta medida paralelizando el proceso. Muchos intentos de paralelización del templado simulado para problemas específicos han tenido éxito, especialmente para problemas bien estudiados (como el problema del viajante de negocios). Esta paralelización suele hacerse dividiendo el problema en subproblemas más pequeños, cada uno de los cuales se resuelve mediante templado simulado estándar, como el presentado aquí, y luego recombinando estas soluciones. Dividir el problema de esta manera debe hacerse con mucho cuidado, ya que la alta interdependencia de los subproblemas puede ser problemática. Si los subproblemas interdependientes no se comunican, la recombinación conducirá a una solución que está potencialmente lejos del óptimo global, análoga a las estructuras localmente óptimas del enfriamiento del sistema en su conjunto. Por otra parte, si los subproblemas se comunican, debido a su gran interdependencia, se requiere la comunicación entre los procesadores, lo que sólo supone pequeñas ganancias de eficiencia en comparación con la ejecución de un templado secuencial. !!!note: Clases de Problemas y Paralelización Los métodos de paralelización diferencian dos clases de problemas para medir si compensa paralelizarlos o no en la resolución del Templado Simulado: * Clase $K_1$: el tiempo para generar configuraciones vecinas es aproximadamente igual al tiempo que se tarda en calcular el incremento de energía entre la configuración actual y la propuesta. Por ejemplo: el problema de viajante de negocios. * Clase $K_2$: el tiempo para generar una configuración vecina es mucho menor que el tiempo para calcular el incremento de energía. Por ejemplo: el problema clustering (que veremos en la parte de aprendizaje automático). # Optimización por Enjambres de Partículas (PSO) La **Optimización por Enjambres de Partículas** (conocida como **PSO**, por sus siglas en inglés, **Particle Swarm Optimization**) puede considerarse una extensión del templado simulado. En lugar de utilizar una sola partícula, se mueve un enjambre de partículas de iteración en iteración. Se puede considerar que el movimiento de los miembros del enjambre imita la *inteligencia de enjambre* de sistemas sociales como las bandadas de pájaros, algunas colonias de insectos, o los bancos de peces. Los miembros del enjambre se dispersan y se mueven aleatoriamente con la esperanza de encontrar un óptimo local. Como el enjambre es social, los miembros anuncian su éxito a sus vecinos para atraerlos a regiones prometedoras y ayudarles en la búsqueda de un óptimo (por ejemplo, las abejas por medio de la danza que realizan en la colmena al volver de la recolección de néctar, indicando la distancia y calidad de la fuente encontrada a las demás). ![](img/abeja.jpg align="right" width=20%)Este método fue descrito alrededor de 1995 por James Kennedy y Russell C. Eberhart (Kennedy, J. & Eberhart, R. (1995), 'Particle swarm optimization', Neural Networks, 1995. Proceedings., IEEE International Conference), y se inspira en el comportamiento de los enjambres de insectos en la naturaleza. En concreto, podemos pensar en un enjambre de abejas, ya que éstas a la hora de buscar polen buscan la región del espacio en la que existe más densidad de flores, porque la probabilidad de que haya polen es mayor. La misma idea fue trasladada al campo de la computación en forma de algoritmo y se emplea en la actualidad en la optimización de distintos tipos de sistemas. Formalmente hablando, se supone que tenemos una función desconocida, $f(\mathbf{x})$, que podemos evaluar en los puntos que queramos pero a modo de caja negra, por lo que no podemos conocer su expresión. El objetivo es el habitual en optimización, encontrar valores de $\mathbf{x}$ para los que la función $f(\mathbf{x})$ sea máxima (o mínima, o bien verifica alguna relación extremal respecto a alguna otra función). Como ya hemos visto, a $f(\mathbf{x})$ se le suele llamar **función de fitness** u **objetivo**, ya que va a determinar cómo de buena es la posición actual para cada partícula. La idea que vamos a seguir en PSO comienza situando partículas al azar en el espacio de búsqueda, pero dándoles la posibilidad de que se muevan a través de él de acuerdo a unas reglas que tienen en cuenta el conocimiento personal de cada partícula y el conocimiento global del enjambre. Veremos que proporcionándoles una capacidad simple de movimiento por este espacio y de comunicación entre ellas pueden llegar a descubrir valores particularmente altos para $f(\mathbf{x})$ gastando pocos recursos computacionales (cálculos, memoria y tiempo). Supondremos que tenemos $N$ partículas, denotadas $\{1,\dots,N\}$, y cada partícula tiene una **posición**, $\mathbf{x}_i$, en el espacio de búsqueda y una **velocidad**, $\mathbf{v}_i$, que determina su movimiento a través del espacio. Además, simulando partículas de un mundo real físico, tienen una cantidad de **inercia**, que los mantiene en la misma dirección en la que se movían, así como una **aceleración** (cambio de velocidad), que depende principalmente de dos características: 1. Cada partícula es atraída hacia la mejor localización que ella, personalmente, ha encontrado en su historia (**mejor personal**), $\mathbf{x}_i^{pb}$. 2. Cada partícula es atraída hacia la mejor localización que ha sido encontrada por el conjunto de partículas en el espacio de búsqueda (**mejor global**), $\mathbf{x}^{gb}$.  La fuerza con que las partículas son empujadas en cada una de estas direcciones depende de dos parámetros que pueden ajustarse (**atracción-al-mejor-personal** y **atracción-al-mejor-global**) de foma que, a medida que las partículas se alejan de estas localizaciones mejores, la fuerza de atracción es mayor. También se suele incluir un factor aleatorio que influye en cómo las partículas son empujadas hacia estas localizaciones. Formalmente, lo podemos escribir como: $$\mathbf{v}_i(t+1)=\mathbf{v}_i(t)+c_1\cdot r_1\cdot (\mathbf{x}_i^{pb}−\mathbf{x}_i(t))+c_2\cdot r_2\cdot (\mathbf{x}^{gb}−\mathbf{x}_i(t))$$ donde las posiciones y velocidades se indican en función del tiempo, $c_1$ y $c_2$ son, respectivamente las constantes de atracción al mejor personal y mejor global, y $r_1$ y $r_2$ son dos números aleatorios en $[0,1]$ (que se lanzan en cada iteración y para cada partícula). Una vez actualizadas las velocidades de todas las partículas, sus posiciones se actualizan siguiendo una ley simple: $$\mathbf{x}_i(t+1)=\mathbf{x}_i(t)+\mathbf{v}_i(t)$$  El algoritmo PSO se esboza a grandes rasgos en el siguente código: ```none Asignar posiciones y velocidades aleatorias iniciales a las partículas Repetir Para cada i en {1,...,N}: Actualizar vi haciendo uso de (1) Actualizar xi haciendo uso de (2) Calcular f(xi) Actualizar mejor personal Actualizar mejor global Devolver x^gb ```  Lo interesante de este modelo es que cada partícula solo hace operaciones vectoriales básicas (para actualizar las velocidades y posiciones basta realizar algunas sumas de vectores) y, como la experiencia muestra que hacen falta pocas partículas y el número de iteraciones es bajo, la complejidad del proceso se centra sobre todo en la evaluación del fitness de cada partícula en cada iteración, algo que no puede evitarse y que depende exclusivamente del problema específico que se quiera optimizar. En consecuencia, este método de optimización es especialmente adecuado cuando el coste de la función de fitness es muy elevado, pues requiere pocas evaluaciones para encontrar valores cercanos al óptimo. Como inconveniente, no podemos estar seguros de alcanzar el óptimo global, como pasa en todo este tipo de metaheurísticas (problema que comparten todos los métodos de optimización que trabajan con cajas negras). ## Variantes PSO Una primera posibilidad, que se implementa en algunos de los algoritmos que se engloban dentro de los PSO, y que es fácil de implementar en el modelo anterior, consiste en añadir una fuerza repulsiva entre las partículas para intentar prevenir que todas ellas converjan prematuramente a una pequeña zona del espacio de búsqueda (lo que supone acabar prematuramente en un máximo local, y con pocas opciones de escapar de él para encontrar mejores optimizaciones). Realmente, se puede enriquecer el modelo añadiendo comportamientos diversos a los individuos-partículas, ya sea inspirándose en comportamientos observados en la naturaleza o puramente abstractos. Otra opción es no considerar el máximo global que se va encontrando, sino dividir las partículas en familias y considerar máximos globales por familias. De esta forma, cada familia puede trabajar en paralelo y cada partícula solo ha de tener conocimiento acerca de lo que *sucede* en su familia, no en el conjunto global de individuos. Además, existen variantes en las que estas familias son dinámicas, de forma que las partículas pueden ir cambiando de familia a medida que el algoritmo se ejecuta (o incluso pertenecer a más de una familia, lo que permite que haya comunicaciones a larga distancia entre muchas partículas aunque no pertenezcan a la misma familia). Una variantes habitual de este último tipo es considerar que la familia de una partícula viene dada por las partículas que están dentro de un determinado entorno (por ejemplo, a menos de una determinada distancia). Por último, ¿qué pasa si la función que intenta ser optimizada cambia en el tiempo?, es decir, en el caso en que sea una búsqueda dinámica, en la que la variación de la función durante el tiempo de ejecución haga que los extremos se vayan desplazando por el espacio de búsqueda. No resulta difícil modificar el modelo anterior para que se genere una función cambiante en el tiempo y poder así experimentar bajo qué condiciones las partículas del enjambre siguen el movimiento de los máximos a medida que se trasladan por el espacio. Normalmente, funcionan bien en lo que se denominan **paisajes dinámicos**.