Estás leyendo la publicación: Una visión general: hacia la IA
Publicado originalmente en Hacia la IA, la empresa líder mundial en noticias y medios de IA y tecnología. Si está creando un producto o servicio relacionado con la IA, lo invitamos a considerar convertirse en patrocinador de la IA. En Hacia la IA, ayudamos a escalar las empresas emergentes de IA y tecnología. Permítanos ayudarlo a dar rienda suelta a su tecnología a las masas.
algoritmo de optimización metaheurístico inspirado en la naturaleza basado en la población
“Es a la hormiga, no al león, a quien teme el elefante”.
― matshona dhliwayo
Un grupo de técnicas y enfoques únicos de resolución de problemas inspirados en procesos naturales se conocen como “algoritmos inspirados en la naturaleza”. El algoritmo de optimización de colonias de hormigas (COA), utilizada en Ciencias de la Computación y la investigación de operacioneses un método probabilístico para resolver problemas informáticos que puede simplificarse para encontrar rutas adecuadas a través de gráficos.
En este blog, analizaremos los siguientes temas:
- Hormigas de la vida real
- Comportamiento de búsqueda de alimento
- La inspiración detrás del algoritmo de optimización de colonias de hormigas
- ¿Qué está pasando realmente con las hormigas y la comida en la vida real?
- Pasos para la optimización de colonias de hormigas
Hormigas de la vida real
Junto con las avispas y las abejas estrechamente relacionadas, las hormigas son miembros eusociales de la familia Formicidae en el orden Hymenoptera. Las hormigas tienen un estimado 22.000 especiesy mas que 13,800 han sido clasificados. Una hormiga pasa por una metamorfosis completa, lo que significa que las hormigas tienen cuatro etapas: huevo, larva, pupa y adulto en el transcurso de su ciclo de vida. Esperanza de vida: Hormiga de jardín negra: 1–2 años, hormiga faraón: 4–12 meses. Las hormigas generalmente se dividen en tres tipos: hembras reproductoras, machos reproductores y hembras no reproductivas. Esto se traduce en reinas, machos y obreras.
Las colonias de hormigas y las sociedades sociales de insectos, en general, son sistemas distribuidos que, a pesar de la simplicidad de sus miembros individuales, muestran un sistema social altamente organizado. Las colonias de hormigas están organizadas de tal manera que pueden realizar tareas complicadas. que, en algunas situaciones, superan significativamente la capacidad de una hormiga individual. lo que sucede en los humanos y otras especies superiores cuyos sentidos primarios son auditivos o visuales. La feromona del rastro es particularmente significativa para el comportamiento social de algunas especies de hormigas. La raíz de ACO es esta actividad colectiva de trazar y seguir senderos, en la que una hormiga es influenciada por un camino químico dejado por otras hormigas.
Las hormigas no tienen orejas.. pueden sentir vibraciones. se comunican usando sus antenas y feromonas.
Problemas que involucran optimización discreta son particularmente adecuados para ACO. Por ejemplo, una ruta o ruta se codifica como una solución para problemas de enrutamiento. Cuando las hormigas toman caminos diferentes, los caminos que han recorrido se marcan con depósitos de feromonas que eventualmente desaparecen. La cantidad de feromona presente en un camino (o en una solución) se correlaciona con su aptitud o calidad. En un cruce, las rutas con mayores concentraciones de feromonas serán preferidas o seleccionadas con más frecuencia.
Comportamiento de búsqueda de alimento
ACO está inspirado en el comportamiento de forja de las hormigas que buscan un camino adecuado entre sus colonias y la fuente de alimento. Si desea llegar a la comida en un tiempo mínimo, debe encontrar el camino más cercano a una fuente de alimento. el camino más corto te dará comida en menos tiempo.
La inspiración detrás del algoritmo de optimización de colonias de hormigas
¿Cómo encuentran las hormigas el camino más corto entre su fuente de alimento y el nido?
Observa la figura anterior. Encerré en un círculo una hormiga, y esa será nuestra agente para buscar comida. Ahora puede haber numerosas formas en que las hormigas pueden buscar comida. de todos los caminos, resalté 4 caminos tentativos aleatorios llamados A, B, C, D. Como podemos ver en la figura, C es el camino más corto y A es el camino más largo. Al ir por cualquier camino en busca de comida, la hormiga libera una sustancia química conocida como feromona. Según esto, al pasar por todas las rutas, las hormigas liberarán feromonas.
cuando la hormiga llega a la comida, cada ruta tiene una cierta cantidad de feromona depositada, como se muestra en la figura anterior. el que encuentra comida o forraje marcará rastros en el camino usando feromonas mientras regresa a la colonia. la ruta más corta tendrá más cantidad de niveles de feromonas. Otras hormigas seguirán la ruta que tenga más feromonas como una señal que representa la ruta más corta para llegar a la comida. La feromona se actualiza en cada movimiento de una hormiga de un lugar a otro en base a Densidad de hormigas & Cantidad de hormigas.
la feromona tiene algo Tasa de evaporación. significa que la feromona depositada desaparecerá después de cierto tiempo. Entonces, como puede ver en la figura anterior, la ruta por la que la mayoría de las hormigas siguen la feromona de la hormiga líder tiene la mayor cantidad de feromona depositada, mientras que otras rutas más largas tienen menos feromona debido a la evaporación.
Cuando se termina la fuente de alimento, las hormigas que regresan no marcan nuevas marcas en el camino.
¿Qué está pasando realmente con las hormigas y la comida en la vida real?
1. Inicializar parámetros ACO
Podemos inicializar muchos parámetros iniciales como el tamaño de la población, el número máximo de iteraciones, el valor inicial de las feromonas, los pesos exponenciales de las feromonas, la tasa de evaporación de las feromonas, etc.
2. Construcción de soluciones
De forma correcta, se cuenta la formulación del enunciado del problema y la iteración.
3. Posición de cada agente/hormiga en el nodo inicial
También se conoce como probabilidad de transición.
Aquí, la hormiga k-ésima se moverá de a con esta probabilidad.
4. Cada hormiga seleccionará el siguiente nodo aplicando la regla de transición.
5. Repita hasta que la hormiga construya la mejor solución.
6. calcular el valor de aptitud
7. actualizar la mejor solución
8. Aplicar actualización de feromona externa
Incremento en los niveles de pruebas de feromonas =Para la mejor solución
Disminución en los niveles de rastros de feromonas = para la peor solución
La deposición de feromonas y el cálculo de la evaporación también son importantes.
9. mejor solución
Bucle hasta el máximo de iteraciones para concluir la mejor solución. eso puede ser de nuevo un hiperparámetro.
Un experimento interesante se dio en el libro. Optimización de colonias de hormigas por y
El puente en el primer experimento tenía dos ramas que tenían la misma longitud. Inicialmente, se permitió que las hormigas deambularan libremente entre el nido y el suministro de alimentos, y se midió la proporción de hormigas que preferían una de las dos ramas sobre la otra. con el tiempo, se notaron las hormigas. El resultado fue que, a pesar de que las elecciones iniciales se hicieron al azar, finalmente, todas las hormigas eligieron usar la misma rama. La siguiente explicación explica este resultado. No hay feromona en las dos ramas cuando comienza una prueba. Las hormigas eligen cualquier rama con la misma probabilidad ya que no tienen preferencia. Sin embargo, algunas hormigas más elegirán una rama sobre la otra debido a variaciones aleatorias. Dado que las hormigas depositan feromonas a medida que se mueven, una rama con más hormigas tendrá más feromonas allí.
Esta mayor cantidad de feromona animará a más hormigas a elegir esa rama nuevamente, y así sucesivamente, hasta que las hormigas finalmente se congreguen en una de las dos ramas.
Puedes obtener esta simulación. AQUÍ.
Nube Anylogic tiene muchas simulaciones diferentes e interesantes basadas en escenarios de la vida real, puedes comprobarlo AQUÍ.
Ultimas palabras:
Al incorporar el comportamiento de enjambre, la optimización de ACO y enjambre de partículas[PSO] Los algoritmos son ambos métodos de agrupación de datos. El ACO, sin embargo, es más relevante. abordar cuestiones en las que el origen y el destino están claramente identificados y predeterminados. Además, PSO es una técnica de agrupación de gestión de restricciones, optimización dinámica y multiobjetivo. ACO es más apropiado para problemas que requieren soluciones precisas. Los algoritmos de optimización de colonias de hormigas se han aplicado a muchos problemas de optimización combinatoria, que van desde la asignación cuadrática hasta proteínas plegables o vehículos de enrutamiento, y muchos métodos derivados se han adaptado a problemas dinámicos en variables reales, problemas estocásticos, objetivos múltiples e implementaciones paralelas. .
Esta fue solo una descripción general teórica de ACO, pero estoy planeando tomar un estudio de caso para implementar ACO en él. Ya escribí un blog sobre un algoritmo inspirado en la naturaleza enOPTIMIZACIÓN DE ALGORITMOS GENÉTICOS. Puedes leer eso.
Si has encontrado este artículo revelador
Si este artículo te ha resultado útil, sígueme en LinkedIn y medio. tú también puedes suscribir para recibir notificaciones cuando publique artículos. ¡Creemos una comunidad! ¡Gracias por su apoyo!
Si quieres apoyarme:
Como Tu seguimiento y aplausos es lo más importante, pero también puedes apoyarme comprando café. CAFÉ.
cerrar sesión,
Chinmay Bhalerao
Optimización de colonias de hormigas: una descripción general se publicó originalmente en Hacia la IA en Medium, donde las personas continúan la conversación resaltando y respondiendo a esta historia.
Publicado a través de Hacia la IA
