**SVRAI** Metaheurísticas Segunda Parte Como hemos visto en entradas anteriores, las **metaheurísticas de búsqueda** proporcionan estrategias para resolver un problema realizando una búsqueda sobre un espacio cuyos elementos representan las soluciones candidatas alternativas, y que se denomina **Espacio de Soluciones** posibles del problema. La representación de las soluciones se realiza a través de una codificación que debe incluir toda la información necesaria para su identificación y evaluación, un problema íntimamente relacionado con la [Representación del Conocimiento](http://www.cs.us.es/~fsancho/?e=172). Una **búsqueda** sobre un espacio consiste en generar una sucesión de puntos del espacio en el que cada punto se obtiene del anterior por medio de una serie de transformaciones o movimientos. Un procedimiento de búsqueda para resolver un **problema de optimización** realiza recorridos sobre el espacio de posibles soluciones y selecciona la mejor solución encontrada en el recorrido. El objetivo de las metaheurísticas de búsqueda es proporcionar pautas para obtener recorridos que proporcionen soluciones de alta calidad atendiendo también una eficiencia adecuada.  La descripción general de un proceso de resolución de un problema suele seguir una serie de pasos comunes: partiendo de una situación inicial, aplicar iterativamente una operación para modificar la situación actual, hasta que se alcance la situación buscada. En este sentido, un proceso de búsqueda basado en transformaciones o movimientos sobre un espacio de soluciones posibles consiste en la selección iterativa de movimientos para transformar una solución hasta que se cumpla cierto criterio de parada. El criterio de parada determina cuándo se considera resuelto el problema sin que sea necesario disponer, en una situación intermedia, de información de lo cerca que se está de solucionarlo. Sin embargo, las búsquedas inteligentes deben utilizar este y otro tipo de información en el criterio de parada y en la selección de los movimientos. En los **problemas de optimización**, la selección de movimientos y el criterio de parada se realizan teniendo en cuenta uno, o más, indicadores de la calidad de las soluciones encontradas en el recorrido. La evaluación de la calidad de las soluciones se realiza a través de una o varias funciones objetivo, teniendo en cuenta las restricciones del problema (si es más de una, se denomina **optimización multiobjetivo**). Los objetivos se formalizan por una o varias funciones que hay que maximizar o minimizar (supondremos, en la descripción de los métodos de solución, que se trata de maximizar). La estrategia de búsqueda establece los criterios y mecanismos que guiarán el recorrido, y puede incorporar herramientas de una o varias metaheurísticas junto a heurísticas específicas para el problema. Los problemas de optimización aparecen de forma habitual en muchísimos campos científicos y su solución es de crucial importancia para el éxito de multitud de tareas de Inteligencia Artificial. El problema se formaliza por medio de un espacio de soluciones $S$ y la función objetivo $f$. Resolver el problema de optimización $(S,f)$ consiste en **determinar una solución óptima**, es decir, una solución factible $x_o \in S$ tal que $f(x) \leq f(x_o)$, para cualquier $x \in S$.  Las soluciones alternativas se pueden expresar por la asignación de valores a algún conjunto finito de variables $X = \{X_i : i = 1,2,\dots,n\}$. Si por $U_i$ se denota al **dominio** (conjunto de los valores posibles) de cada una de estas $n$ variables, el problema consiste en seleccionar el valor $x_i$ asignado a cada variable $X_i$ del dominio $U_i$ que, sometido a ciertas restricciones, optimiza la función objetivo $f$. El universo de soluciones se identifica con el conjunto $U = U_1 \times U_n = \{x = (x_i : i = 1,2,\dots,n) : x_i \in U_i\}$. Las restricciones del problema reducen el universo de soluciones a un subconjunto de soluciones $S \subseteq U$, denominado **espacio factible**. Los **procedimientos de búsqueda por entornos** recorren el espacio de soluciones mediante un conjunto de transformaciones o movimientos. Las soluciones que se obtienen de otra mediante uno de los movimientos posibles se denominan **vecinas** de ésta y constituyen su **entorno**. El conjunto de movimientos posibles da lugar a una relación de vecindad y una estructura de entornos en el espacio de soluciones cuya elección es un aspecto trascendental en el éxito de los procesos de búsqueda. Además de una implementación y evaluación eficiente de los movimientos, las propiedades de la estructura de entorno resultante intervienen en esta elección.  El entorno de una solución está constituido por las soluciones a las que se puede acceder desde ella por uno de los movimientos posibles. Formalmente, una estructura de entornos sobre un espacio o universo de búsqueda $U$ es una función $E : U \rightarrow P(U)$ que asocia a cada solución $x \in U$ un entorno $E(x) \subseteq U$ de soluciones vecinas a $x$. El esquema general de un procedimiento de búsqueda por entornos consiste en una ligera variante del esquema general de búsqueda anotado anteriormente: generar una solución inicial y, hasta que se cumpla el criterio de parada, seleccionar iterativamente un movimiento para modificar la solución. Las soluciones son evaluadas mientras se recorren y se propone la mejor solución encontrada del problema. En el proceso de creación de los movimientos se debe tener en cuenta que, aunque movimientos más complejos suponen un enriquecimiento de los entornos, con lo que se puede mejorar el acercamiento al óptimo, se corre el riesgo de perjudicar la eficiencia del algoritmo al tener que contemplar un número mayor de movimientos posibles en el proceso de selección. Otra característica importante de los movimientos es la factibilidad de las soluciones aportadas. Los **movimientos factibles** son aquellos que siempre proporcionan una solución factible, aquellas que tienen sentido en el problema, que están en $S$. Esto puede estar ligado o no al hecho de que se aplique sólo a soluciones factibles. En muchos casos, aplicar movimientos más simples, pero no necesariamente factibles, y descartar las soluciones producidas que no sean factibles, es menos eficiente que adaptar el diseño de los movimientos para que sean factibles, sobre todo cuando dicha comprobación es costosa o cuando la probabilidad de que resulte factible es baja. Formalmente, los procedimientos que sólo consideran movimientos factibles están asociados al concepto, algo más restrictivo, de estructura de entornos como una función $E : S \rightarrow P(S)$ que asocia a cada solución factible $x\in S$ un entorno $E(x) \subseteq S$ de soluciones factibles vecinas a $x$. Existen otras cuestiones relevantes en el éxito del procedimiento de búsqueda por entornos. Aparte de la selección de la propia estructura de entornos sobre la que articular la búsqueda, hay que valorar: la evaluación de la función objetivo, el procedimiento de generación de la solución inicial, y el criterio de parada. La posibilidad de realizar una evaluación eficiente de la solución obtenida tras el movimiento es especialmente importante en aquellos problemas en los que la evaluación de la función objetivo sea costosa. Se pueden aplicar técnicas de **metaheurísticas con relajación** para evitar cómputos excesivos en la obtención de valoraciones exactas que no son imprescindibles en la conducción de la búsqueda. Además, se puede contar con procedimientos que evalúan la calidad de los movimientos sin tener que realizar una evaluación completa de la nueva solución desde cero. Para ello se utilizan procedimientos que actualizan rápidamente el valor de la función objetivo tras el movimiento, utilizando el valor anterior y los cambios producidos por el movimiento. Las pautas de las **metaheurísticas constructivas** se utilizan para el diseño del procedimiento de generación de la solución inicial. En este sentido, las características fundamentales son la calidad y dispersión de las soluciones iniciales desde la que iniciar la búsqueda. Por último, otra cuestión importante que afecta a cualquier procedimiento de solución de un problema emanado de una metaheurística de búsqueda por entornos es la condición de parada. Los criterios más corrientes suelen estar relacionados con limitar el número de iteraciones, de movimientos, de operaciones elementales o del tiempo de cómputo total o sin que se produzca alguna mejora.  Dos características fundamentales en el procedimiento de búsqueda por entornos son las capacidades de **exploración** y de **explotación**. La exploración se refiere a la capacidad del método para explorar las diferentes regiones del espacio de búsqueda para encontrar la zona en la que se encuentra la solución del problema. La explotación de la búsqueda se refleja en el esfuerzo y capacidad por mejorar las soluciones con las que trabaja el procedimiento. Existe un amplio consenso en que estas dos características deben modularse adecuadamente para conseguir el éxito práctico de las aplicaciones de las metaheurísticas, que deben conseguir un equilibrio entre ellas.  # Búsquedas Locales El término local se emplea con bastante frecuencia en los estudios teóricos y prácticos del campo de las metaheurísticas de búsqueda. Las estructuras de entorno suelen reflejar algún concepto de proximidad o vecindad entre las posibles soluciones del problema. Por tanto, el análisis del entorno de la solución actual en el recorrido de búsqueda para decidir cómo continuarla representa un estudio local del espacio de búsqueda. Así pues, una **búsqueda local** es un proceso que, dada la solución actual en la que se encuentra el recorrido, selecciona iterativamente una solución de su entorno. Las metaheurísticas de búsqueda local establecen pautas de selección de esta solución del entorno de la solución actual dando lugar a búsquedas locales heurísticas con alto rendimiento. Las **búsquedas locales no informadas** sólo tienen en cuenta la estructura de entornos para guiar la búsqueda. Las **búsquedas monótonas** utilizan la evaluación de la función objetivo para admitir sólo cambios en la solución actual que supongan una mejora. Por tanto, las búsquedas locales monótonas quedan atrapadas al llegar a una solución que no admite mejora dentro de su entorno. Las **búsquedas globales** emplean diversos métodos para escapar de esta situación. A continuación analizamos los aspectos más relevantes de las metaheurísticas para estos procedimientos. ## Búsquedas No Informadas Las estrategias de **búsqueda por entornos no informadas** son aquellas búsquedas locales que sólo prestan atención a la estructura de entornos en el espacio de búsqueda y no utilizan información acerca del valor de la función objetivo en las soluciones encontradas. Las metaheurísticas de búsqueda por entornos **exhaustiva**, **parcial** y **aleatoria** son las metaheurísticas de búsqueda no informadas más usuales. Un **recorrido exhaustivo** de un espacio de búsqueda es el que incluye todos y cada uno de los elementos del espacio. Si el espacio de búsqueda es finito y no excesivamente grande, un procedimiento rudimentario para resolver el problema consiste en implementar un recorrido exhaustivo hasta encontrar la solución. En un problema de optimización, la búsqueda exhaustiva consiste en realizar un recorrido exhaustivo del espacio de soluciones del problema y tomar la mejor de ellas. Un recorrido exhaustivo del espacio se consigue empleando una ordenación (implícita o explícita) de todas las soluciones del espacio y utilizando una transformación que obtenga en cada iteración la solución siguiente en dicha ordenación. El procedimiento de generación de la solución inicial debe proporcionar la primera solución de dicha ordenación y el criterio de parada detectar cuándo se ha completado todo el espacio de búsqueda. La ordenación puede comprender sólo las soluciones factibles o un conjunto que las contenga. En este caso sólo habrá que considerar las soluciones factibles para elegir la mejor. A partir de la representación de las soluciones del espacio se determina la ordenación natural consistente en ir modificando sucesivamente los elementos que componen la solución. Dada una estructura de entornos para un problema, la **búsqueda por entornos exhaustiva** recorrerá sucesivamente y de forma exhaustiva los entornos de las soluciones visitadas. Si la estructura de entornos enlaza todas las soluciones del espacio, la búsqueda será exhaustiva, pero será necesario evitar o controlar las repeticiones para impedir que se entre en un ciclo indefinidamente. En algunas circunstancias puede ser suficiente examinar sólo una parte del espacio de búsqueda para obtener una visión global de todo el espacio. Las **metaheurísticas de búsqueda parcial** establecen las pautas para organizar la selección de las soluciones a examinar. Para un problema de optimización, la búsqueda parcial aportará la mejor entre las soluciones examinadas como propuesta de solución. Si las soluciones a examinar se seleccionan de forma completamente al azar se trata de una búsqueda parcial aleatoria pura, conocida como **método de Monte Carlo**. La **metaheurística de búsqueda por entornos aleatoria** consiste en seleccionar iterativamente al azar una solución del entorno de la solución actual. ## Búsquedas Locales Monótonas Las metaheurísticas de búsqueda anteriores no utilizan la información proporcionada por la evaluación de la función objetivo en la conducción de la búsqueda. Las estrategias de búsqueda pueden incorporar esta información al método de búsqueda para guiar los movimientos aplicados. Las **búsquedas informadas** son aquellas que, explícita o implícitamente, utilizan información de la evaluación de la función objetivo. Las **búsquedas locales (o por entornos) informadas** son las que utilizan información de la función objetivo sólo en el entorno de la solución actual. Las **búsquedas monótonas** sólo aceptan mejoras de la solución que realiza el recorrido. Las **búsquedas locales monótonas** son las búsquedas locales que sólo aplican movimientos que mejoren la solución actual del recorrido. Las **búsquedas monótonas no estrictas** aceptan también nuevas soluciones que igualan a la solución actual. Estas estrategias presentan la ventaja de que pueden escaparse de las mesetas o zonas llanas del espacio de búsqueda, pero tienen el inconveniente de que podría caer en un ciclo indefinidamente dentro de una de tales mesetas. La metaheurística básica de búsqueda por entorno monótona aleatoria consiste en seleccionar iterativamente una solución al azar del entorno de la solución actual que es sustituida por ésta si se produce una mejora. La solución de partida se puede obtener por cualquier procedimiento arbitrario y el criterio de parada reflejará el estancamiento de la búsqueda en un mínimo local presumible cuando en un cierto número de intentos no se pueda mejorar la solución actual. Las metaheurísticas intensifican la búsqueda en torno a cada solución actual seleccionando la mejor de entre una serie de soluciones del entorno obtenidas por un procedimiento del mismo tipo. La **intensidad de la búsqueda** viene dada por el número o la proporción de soluciones vecinas de la solución actual entre las que se toma la mejor. La **metaheurística de intensificación oscilante** consiste en hacer oscilar sistemáticamente entre dos valores extremos la intensidad de la búsqueda. La **metaheurística de intensificación oscilante dinámica** regula dinámicamente la intensidad de la búsqueda para intensificarla, hasta hacerla exhaustiva al acercarse al óptimo local, pero sin necesidad de encontrar la mejor solución vecina al comenzar los ascensos. Una estrategia autónoma para esta regulación dinámica es, por ejemplo, aumentarla cada vez que no se mejore la solución, hasta alcanzar el tamaño del entorno, y disminuirla mientras se produzcan esas mejoras, sin llegar a anularla. Las **metaheurísticas de búsqueda local exhaustiva** maximizan el poder de explotación de la búsqueda local al examinar, si es necesario, todo el entorno de la solución actual. Las metaheurísticas voraz y ansiosa aparecen al aplicar las dos reglas fundamentales de selección de esta solución. La **metaheurística voraz** (**Greedy**) con la regla de selección de *el mejor primero* y la **metaheurística ansiosa** (**Anxious**) con la regla de selección de *el primero mejor*. En la primera de ellas se selecciona siempre la mejor solución del entorno de la solución actual y en la segunda se selecciona la primera solución del entorno que mejore la solución actual. En la metaheurística por entornos voraz se recorren siempre todas las soluciones del entorno para seleccionar la mejor, mientras que en la metaheurística por entornos ansiosa se detiene el recorrido cuando se encuentre una solución del entorno mejor que la actual, pero el recorrido se continúa de forma exhaustiva si no se encuentra tal mejora. # Búsquedas Globales El principal inconveniente de las búsquedas locales es que si se aproximan a una solución localmente óptima (una solución que es mejor que cualquiera de las de su entorno) la solución actual queda atrapada en su entorno. La regla de parada en las búsquedas monótonas implica detectar los mínimos locales analizando cuándo no se mejora la solución actual. Una búsqueda con una perspectiva global del espacio de soluciones debe buscar herramientas para escapar de estas situaciones. Las principales **metaheurísticas de búsqueda global** surgen de las tres formas principales de escapar de esta situación: - volver a comenzar la búsqueda desde otra solución inicial, - modificar la estructura de entornos, y - permitir movimientos de empeoramiento de la solución actual. Estas tres opciones dan lugar, respectivamente, a la **metaheurística con arranque múltiple**, a la **metaheurística de entorno variable** y a la **metaheurística de búsqueda no monótona**: - Los procedimientos de **búsqueda con arranque múltiple** (**Multi-Start**) realizan varias búsquedas monótonas partiendo de diferentes soluciones iniciales. La búsqueda monótona implicada puede ser cualquiera de las anteriormente descritas. Una de las formas más simples de llevar esto a cabo consiste en generar una muestra de soluciones iniciales. Esto es equivalente a generar al azar una nueva solución de partida cada vez que la búsqueda queda estancada en el entorno de una solución óptima local. - La **Búsqueda por Entornos Variables** (**Variable Neighborhood Search**, **VNS**) es una metaheurística que consiste en cambiar de forma sistemática la estructura de entorno. La idea original fue considerar distintas estructuras de entornos y cambiarlas sistemáticamente para escapar de los mínimos locales. El algoritmo básico obtiene una solución del entorno de la solución actual, ejecuta una búsqueda monótona local desde ella hasta alcanzar un óptimo local, que reemplaza a la solución actual si ha habido una mejora y modifica la estructura de entorno en caso contrario. ![](img/vns.png width="75%") - Con las **metaheurísticas de búsqueda probabilísticas** se selecciona aleatoriamente un vecino de la solución actual que la reemplaza con cierta probabilidad, por ejemplo, con probabilidad 1 si tiene mejor valor objetivo, y con una probabilidad menor que 1 si su valor objetivo es peor. Si el número de iteraciones es elevado, la búsqueda puede escapar de cualquier óptimo local si la probabilidad de aceptar peores soluciones va decreciendo. Generalmente la probabilidad de aceptar una solución peor es función del empeoramiento de forma que, a menor diferencia en el valor objetivo, hay mayor probabilidad de ser aceptada. El **Templado Simulado** es el caso más importante de las metaheurísticas de búsqueda global con criterio de aceptación probabilístico. Se usa una probabilidad de aceptación de nuevas soluciones peores que es función exponencial de la modificación de la función objetivo. Otras metaheurísticas simplemente reducen o incrementan esta probabilidad para modular la exploración y explotación de la búsqueda. Las **metaheurísticas de umbrales de aceptación** (**Threshold Accepting**) aceptan las nuevas soluciones peores que no sobrepasen el umbral y modulan este umbral con el mismo propósito.  - Las **metaheurísticas de búsqueda con memoria**, representada por la **Búsqueda Tabú**, comprenden las estrategias que tratan de utilizar la memoria del proceso de búsqueda para mejorar su rendimiento. Está fundamentada en las ideas expuestas por F. Glover en 1986, y en el origen del método el propósito era sólo evitar la reiteración en una misma zona de búsqueda recordando las últimas soluciones recorridas. Sin embargo, posteriormente se han realizado diversas propuestas para rentabilizar la memoria a medio o largo plazo. La forma más directa de introducir la memoria en el procedimiento de búsqueda no monótona es considerar una función de aceptación que tenga en cuenta la historia de la búsqueda. El procedimiento elemental de búsqueda tabú evita la repetición prematura de las mismas soluciones en el recorrido, para lo que prohíbe que las últimas soluciones vuelvan a utilizarse en el recorrido de búsqueda. Estas estrategias se pueden aplicar dentro de la estructura de la búsqueda general de dos formas: introduciendo una función de aceptación que determine cuándo se acepta la nueva solución generada o modificando el procedimiento de generación del movimiento a aplicar a la solución actual. Con la primera de estas alternativas la función de aceptación puede incluir en sus parámetros información referente a la historia y el estado de la búsqueda, y a la solución generada. En el segundo caso, el procedimiento de generación de movimiento debe tener un diseño en el que se generan las soluciones vecinas de acuerdo con algún criterio que tenga en cuenta información de la historia y el estado de la búsqueda. La **Búsqueda Reactiva** (**Reactive Search**) es una metaheurística que propone usar, dentro de la búsqueda tabú, la información a largo plazo obtenida del recorrido. Se persigue detectar indicios de que la búsqueda necesita incrementar su exploración, por la repetición de ciertas estructuras o patrones en las soluciones recientemente visitadas. Esta información se almacena y se accede a ellas utilizando técnicas eficientes de dispersión (hashing) o de árboles de búsqueda usuales en gestión de grandes cantidades de datos. Según la información que se tenga almacenada en cada iteración se activa un proceso reactivo para alejarse de la zona de estancamiento.  # Búsquedas Basadas en Poblaciones En una **búsqueda en grupo o basada en poblaciones** se sustituye la solución actual que recorre el espacio de soluciones por un conjunto de soluciones que lo recorren conjuntamente interactuando entre ellas. Además de los movimientos aplicables a las soluciones que forman parte de este conjunto, denominado *grupo o población de búsqueda*, se contemplan otros operadores para generar nuevas soluciones a partir de las ya existentes. Las estrategias de búsqueda en grupo se iniciaron con el famoso **Algoritmo Genético**. En la actualidad adoptan diversas características, como se puede observar en la gran cantidad de trabajos publicados sobre este tipo de procedimientos. Las cuestiones fundamentales de su implementación para la solución de problemas de optimización son:  En primer lugar, se establece una codificación apropiada de las soluciones del espacio de búsqueda y una forma de evaluar la función objetivo para cada una de estas codificaciones. Las soluciones se identifican con individuos que pueden formar parte de la población de búsqueda. La codificación de una solución se interpreta como el cromosoma del individuo compuesto de un cierto número de genes a los que les corresponden ciertos alelos. Se consideran dos operaciones básicas: la mutación y el cruce. La mutación de un individuo consiste en modificar un gen cambiando, al azar, el alelo correspondiente. El cruce de dos individuos (llamados padres) produce un individuo hijo tomando un número $k$ (elegido al azar) de genes de uno de los padres y el resto del otro. La población evoluciona de acuerdo a las estrategias de selección de individuos, tanto para las operaciones como para la supervivencia. La selección se puede hacer simulando una lucha entre los individuos de la población con un procedimiento que, dados dos individuos selecciona uno de ellos teniendo en cuenta su valoración (la función objetivo) y la adaptación al ambiente y a la población (criterios de diversidad, representatividad). La lucha por la supervivencia tiene por objeto mantener controlado el tamaño de la población. La selección de los luchadores se puede hacer de diferentes maneras: dos individuos seleccionados al azar, cada nuevo individuo con otro seleccionado al azar o con el peor de los existentes, etc. Entre las metaheurísticas derivadas de los algoritmos genéticos destacan los Algoritmos meméticos, que surgen de combinar los algoritmos genéticos con búsquedas locales. Los **Algoritmos de Estimación de Distribuciones** (**EDA**) son algoritmos evolutivos que usan una colección de soluciones candidatas para realizar trayectorias de búsqueda evitando mínimos locales. Estos algoritmos usan la estimación y simulación de la distribución de probabilidad conjunta como un mecanismo de evolución, en lugar de manipular directamente a los individuos que representan soluciones del problema. Un algoritmo EDA comienza generando aleatoriamente una población de individuos. Se realizan iterativamente tres tipos de operaciones sobre la población. El primer tipo de operación consiste en la generación de un subconjunto de los mejores individuos de la población. En segundo lugar se realiza un proceso de aprendizaje de un modelo de distribución de probabilidad a partir de los individuos seleccionados. En tercer lugar se generan nuevos individuos simulando el modelo de distribución obtenido. El algoritmo se detiene cuando se alcanza un cierto número de generaciones o cuando el rendimiento de la población deja de mejorar significativamente. El enfoque de la **metaheurística de Búsqueda Dispersa** (o **Scatter Search**) contempla el uso de un conjunto de referencia de buenas soluciones dispersas que sirve tanto para conducir la búsqueda, mejorando las herramientas para combinarlas adecuadamente, como para mantener un grado satisfactorio de diversidad. La propuesta inicial se originó en estrategias para crear reglas de decisión compuestas. La Búsqueda Dispersa se distingue de otros procedimientos en los mecanismos de intensificación y diversificación que explotan la memoria adaptada recurriendo a los fundamentos que unen el Scatter Search a la Búsqueda Tabú. El **reencadenamiento de caminos** (**Path Relinking**) es una metaheurística asociada a la búsqueda dispersa que utiliza la información que se obtiene de las mejores soluciones. Básicamente, se trata de generar soluciones explorando las trayectorias que conectan soluciones de alta calidad. Partiendo de una de estas soluciones se genera un camino de soluciones hacia la otra solución incorporando a la primera atributos de la segunda. Este camino se construye tomando cada vez el atributo de la segunda solución que lo hace más cercano a ella. A continuación se toman, como puntos de arranque para nuevas fases de mejora, una o varias de las soluciones del recorrido anterior. # Otras Metaheurísticas de Búsqueda y Optimización Se han propuesto otras metaheurísticas de relevancia, algunas de las cuales presentan como novedad estar inspiradas en distintos fenómenos de la naturaleza. Entre ellas destacan las redes neuronales, las colonias de hormigas, las bandadas de aves o bancos de peces. Otras metaheurísticas tienen el mérito de aplicar herramientas muy exitosas en otros campos de la IA, como la metaheurística FANS o los métodos inteligentes de realizar búsqueda locales. Las **redes neuronales artificiales** surgieron como modelos abstractos de sistemas nerviosos naturales formados por unidades de cómputo, llamadas neuronas, interconectadas. Estos modelos tienen la capacidad de ajustar sus parámetros en respuesta a unas entradas y salidas mejorando alguna función. Asociando los estados de la red a soluciones de un problema y utilizando el objetivo como referente, consiguen aproximarse al estado que corresponde con la solución óptima. Otros modelos basados en redes neuronales aplicados con éxito a problemas de optimización combinatoria son las **máquinas de Boltzman** y las **redes competitivas WTA**. ![](img/nn.jpeg width="50%") La **metaheurística de sistemas de hormigas** (**Ant Systems**) emplea estrategias inspiradas en el comportamiento de las colonias de hormigas para descubrir fuentes de alimentación, al establecer el camino más corto entre éstas y el hormiguero y transmitir esta información al resto de sus compañeras.  La **optimización extrema o extremal** (**EO**, **Extreme Optimization**) es una metaheurística inspirada en procesos auto-organizativos frecuentemente encontrados en la naturaleza. La idea central es utilizar modelos de evolución de ecosistemas que, en lugar de seleccionar los mejores elementos, llevan a la extinción a las componentes mal adaptadas del sistema. La idea básica del método es eliminar sucesivamente las componentes extremadamente indeseables de las soluciones subóptimas. El método actúa sobre una única solución, y no sobre un conjunto de soluciones o población como los algoritmos genéticos, modificando el atributo de menor nivel de adaptación (y aquellos afectados por este cambio) aplicando algún tipo de transformación o movimiento. La **optimización por enjambres de partículas** (**PSO**, **Particle Swarm Optimization**) es una metaheurística evolutiva inspirada en el comportamiento social de las bandadas de pájaros, bancos de peces, o colonias de abejas. Las soluciones, llamadas partículas, se desplazan en el espacio de búsqueda guiadas por la partícula que mejor solución ha encontrado hasta el momento y que hace de líder de la bandada. Cada partícula evoluciona teniendo en cuenta la mejor solución encontrada en su recorrido y al líder. En cada iteración, las partículas modifican su velocidad hacia la mejor solución de su entorno teniendo en cuenta la información del líder.  Otras metaheurísticas son la **Búsqueda Local Iterada**, la **metaheurística de concentración**, la **metaheurística de búsqueda local guiada**, la **metaheurística con ruido** (**Noising Methods heuristics**), la **metaheurística de perturbación**, o la **metaheurística de búsqueda fuzzy**. La **programación por restricciones** (**Constraint Programming**) puede considerarse una metaheurística muy general que constituye un paradigma propio dentro de las metaheurísticas, donde lo más relevante es la atención que se le presta al tratamiento de las restricciones que surgen en un problema y cómo afecta a los procedimientos de búsqueda de soluciones.