Algoritmo Genético Basado en Agentes — Búsqueda Evolutiva Distribuida mediante Agentes Autónomos
- Propuesto por
- Adamidis, P. & Petridis, V. (early formal treatment); broader community development in 1990s
- Año
- 1990s
- Tipo
- Hybrid evolutionary-agent simulation
- Familia
- Simulation / optimization
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
Un Algoritmo Genético Basado en Agentes (ABGA) particiona la población de un algoritmo genético en una red de agentes autónomos, cada uno manteniendo una subpoblación local y evolucionándola de forma independiente.
Los agentes intercambian individuos periódicamente (migración) basándose en reglas de proximidad o comunicación, permitiendo la exploración paralela del espacio de búsqueda mientras se preserva la diversidad poblacional y se evita la convergencia prematura.
La intuición detrás del método
Un algoritmo genético convencional trata a toda la población como un único conjunto, lo que puede causar una rápida convergencia a óptimos locales a medida que un genotipo dominante se impone. Un enfoque basado en agentes distribuye en su lugar subpoblaciones entre agentes semi-autónomos organizados en una topología de vecindad. Cada agente ejecuta su propia selección, cruce y mutación localmente, y luego comparte ocasionalmente individuos de alta aptitud con agentes vecinos. Esto imita cómo ocurre la especiación biológica en poblaciones geográficamente aisladas pero ocasionalmente conectadas, permitiendo que diversas presiones evolutivas actúen en paralelo y recombinen soluciones entre nichos.
Historia
Los algoritmos genéticos distribuidos y paralelos surgieron a principios de la década de 1990, cuando los investigadores buscaron superar la convergencia prematura y explotar el hardware paralelo. Adamidis y Petridis (1996) formalizaron poblaciones de agentes cooperantes con diferentes comportamientos evolutivos. El marco basado en agentes ganó impulso a finales de la década de 1990 y en la década de 2000, a medida que la modelización basada en agentes se extendió por la ciencia computacional, formalizando el modelo de interacción autónomo y gobernado por topología que ahora se aplica ampliamente en la optimización compleja.
Cuándo usarlo
Utilizar un ABGA cuando el paisaje de aptitud sea accidentado o multimodal y los AG estándar converjan prematuramente de forma consistente; cuando haya hardware paralelo o distribuido disponible que pueda alojar procesos de agentes concurrentes; o cuando la estructura del problema se mapee naturalmente a subproblemas semi-independientes (p. ej., cadenas de suministro regionales, políticas multisectoriales). También es apropiado al explorar el comportamiento del algoritmo bajo presiones evolutivas heterogéneas. NO utilizar cuando el problema tenga un único paisaje unimodal (un AG más simple es suficiente), cuando la sobrecarga de la comunicación inter-agente domine la computación, cuando los tamaños de población sean demasiado pequeños para particionarse significativamente, o cuando se requiera una población centralizada para una reproducibilidad exacta.
Limitaciones y consideraciones
- El ajuste de la política de migración (tasa, topología, frecuencia) añade hiperparámetros que requieren una calibración cuidadosa y dependen del problema.
- La sobrecarga de comunicación entre agentes puede anular los beneficios del paralelismo en entornos de computación de alta latencia o débilmente acoplados.
- Las garantías teóricas de convergencia son más débiles que para los AG estándar; el análisis formal de la dinámica de los ABGA sigue siendo un área de investigación abierta.
- La reproducción de resultados requiere fijar la topología de los agentes, el cronograma de migración y las semillas aleatorias en todos los agentes, lo que complica la replicación.
- Si los tamaños de las subpoblaciones son demasiado pequeños, los agentes individuales son propensos a la deriva genética independientemente de la migración.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Mantiene una mayor diversidad poblacional que los AG panmícticos, reduciendo la convergencia prematura en paisajes de aptitud accidentados.
- Explota de forma natural la infraestructura de computación paralela o distribuida para problemas de optimización a gran escala.
- Las configuraciones de operadores heterogéneas por agente permiten la exploración y explotación simultáneas a través de diferentes estrategias.
- La migración de individuos aptos entre agentes permite la recombinación entre nichos que puede descubrir nuevas soluciones de alta calidad.
- La arquitectura modular facilita la integración de heurísticas específicas del dominio dentro de los bucles de evolución de agentes individuales.
- Escala bien con la dimensionalidad del problema cuando las subpoblaciones pueden particionarse de manera significativa.
Aplicaciones
- Programación y logística: problemas distribuidos de taller o de enrutamiento de vehículos donde los subproblemas geográficos se mapean naturalmente a los agentes.
- Optimización de diseño de ingeniería: diseño estructural o aerodinámico con espacios de búsqueda multimodales que se benefician de la exploración de nichos paralelos.
- Simulación de políticas: optimización de parámetros de políticas en modelos de simulación social donde los agentes representan actores regionales o sectoriales.
- Búsqueda de hiperparámetros de aprendizaje automático: ajuste evolutivo paralelo de configuraciones de modelos en clústeres de computación distribuidos.
- Bioinformática: predicción de estructura de proteínas e inferencia de redes genéticas en paisajes de aptitud de alta dimensionalidad y accidentados.
- IA de juegos y robótica: evolución de estrategias de comportamiento de agentes en entornos multiagente con dinámicas coevolutivas.
Cómo funciona
Cómo funciona
Definir la topología de los agentes: especificar el número de agentes (subpoblaciones), su estructura de vecindad (anillo, rejilla, grafo de mundo pequeño o totalmente conectado) y el protocolo de comunicación que rige cuándo y cómo los agentes intercambian individuos. Cada agente es una entidad computacional autónoma con su propio conjunto de cromosomas.
Inicializar la subpoblación local de cada agente con cromosomas generados aleatoriamente (o soluciones sembradas). Establecer el tamaño de la población local, los operadores genéticos (tipo y tasa de cruce, tasa de mutación) y el mecanismo de selección (torneo, ruleta, basado en rango) de forma independiente para cada agente o uniformemente en todos los agentes.
Cada agente ejecuta de forma independiente varias generaciones de selección, cruce y mutación en su subpoblación local. Operando en paralelo (o pseudo-paralelo en simulación secuencial), los agentes exploran diferentes regiones del espacio de soluciones bajo configuraciones de operadores potencialmente diferentes, preservando la diversidad en todo el sistema.
En intervalos de migración definidos, los agentes comparten un subconjunto de sus individuos más aptos con agentes vecinos de acuerdo con la política de migración (p. ej., enviar los mejores, recibir-reemplazar los peores). La tasa de migración y la topología configuran el equilibrio entre la explotación local y la exploración global; una migración demasiado frecuente colapsa la diversidad, una migración demasiado rara desperdicia la arquitectura distribuida.
Todos los cromosomas importados y evolucionados localmente se evalúan según la función de aptitud compartida. Los agentes pueden aplicar presión de selección local después de la migración para integrar los individuos recibidos en su población, descartando potencialmente los elementos menos aptos. La evaluación de la aptitud es el costo computacional dominante.
Terminar cuando se cumple un criterio de parada global (máximo de generaciones, convergencia de la mejor aptitud entre agentes o tiempo transcurrido). Recopilar la mejor solución encontrada entre todos los agentes como resultado final. Informar curvas de convergencia por agente para diagnosticar la diversidad poblacional y la efectividad de la migración.
Errores comunes
- Establecer una tasa de migración demasiado alta colapsa la diversidad de las subpoblaciones en un único conjunto de facto, eliminando la principal ventaja de la arquitectura de agentes.
- Ignorar el diseño de la topología de vecindad: una topología totalmente conectada provoca una rápida convergencia; un anillo con una frecuencia de migración deficiente puede dejar a los agentes aislados y estancados.
- Evaluar la aptitud solo localmente sin una función de aptitud global compartida lleva a los agentes a optimizar objetivos incompatibles.
- Confundir ABGA con AG multiobjetivo: ABGA es una variante arquitectónica para la eficiencia de la búsqueda, no inherentemente un método multiobjetivo — un ABGA multiobjetivo requiere maquinaria de Pareto adicional.
- Detenerse en la convergencia de un agente individual en lugar de la convergencia global puede pasar por alto mejores soluciones que aún evolucionan en otros agentes.
Preguntas frecuentes
¿Cómo se diferencia un ABGA de un AG paralelo estándar?
Un AG paralelo estándar distribuye típicamente la evaluación de la aptitud de una única población centralizada entre procesadores. Un ABGA otorga a cada agente una subpoblación autónoma con su propio bucle evolutivo; la interacción ocurre solo a través de migración explícita, no a través de un conjunto compartido. Esta distinción preserva presiones selectivas independientes por agente.
¿Qué topología de migración debo elegir?
Las topologías de anillo y rejilla son puntos de partida estándar: limitan el flujo de migración y preservan la diversidad. Las topologías de mundo pequeño (unos pocos enlaces de largo alcance añadidos a un anillo) aceleran la propagación de buenas soluciones sin colapsar la diversidad. Las topologías totalmente conectadas generalmente deben evitarse a menos que se desee un comportamiento de convergencia rápida.
¿Cuántos agentes y qué tamaño de subpoblación es apropiado?
Una heurística común es de 4 a 16 agentes con tamaños de subpoblación de 20 a 50 individuos cada uno, para una población total comparable a la que usaría un AG estándar. Muy pocos agentes niegan la ventaja de diversidad de la arquitectura; demasiados agentes con subpoblaciones diminutas sufren deriva. Es necesaria una sintonización empírica sobre el problema específico.
¿Se puede usar ABGA para optimización multiobjetivo?
Sí, pero se debe añadir maquinaria de Pareto adicional (como la clasificación NSGA-II dentro de cada agente). La arquitectura de agentes ayuda entonces a mantener una aproximación más diversa del frente de Pareto. Esta es la base de las variantes ABGA multiobjetivo.
¿Está garantizado que un ABGA encuentre el óptimo global?
No. Como todos los AG, los ABGA son heurísticos y no proporcionan garantía de optimalidad global. La mejora en la preservación de la diversidad aumenta la probabilidad de evitar óptimos locales en la práctica, pero las garantías de convergencia no son más fuertes que para los AG estándar y son una cuestión de investigación teórica activa.
Métodos relacionados
Fuentes
Adamidis, P., & Petridis, V. (1996). Co-operating populations with different evolution behaviors. Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC 1996), 188-191. IEEE.
Abrir referencia de la publicaciónCopiado.Genetic algorithm. Wikipedia.
Abrir referencia de la publicaciónCopiado.