{"id":4252,"date":"2016-08-22T12:38:16","date_gmt":"2016-08-22T11:38:16","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=4252"},"modified":"2022-12-03T23:00:11","modified_gmt":"2022-12-03T22:00:11","slug":"colonie-de-fourmis","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/algoritmos-desaims\/colonia-de-hormigas\/","title":{"rendered":"Colonia de hormigas"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"4252\" class=\"elementor elementor-4252\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1fc7ac9 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1fc7ac9\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-cc8c703\" data-id=\"cc8c703\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-425ec74 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"425ec74\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-desaims\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Algoritmos de enjambre<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-2e8a66b\" data-id=\"2e8a66b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b0c2709 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"b0c2709\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Pagina de inicio<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-d77f112\" data-id=\"d77f112\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-93fcfcb elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"93fcfcb\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Algorithme_de_colonies_de_fourmis\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-42c6709a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"42c6709a\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-50b621a0\" data-id=\"50b621a0\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ba47182 elementor-widget elementor-widget-text-editor\" data-id=\"ba47182\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenido<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-desaims\/colonia-de-hormigas\/#Colonie-de-fourmis\" >Colonia de hormigas<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-desaims\/colonia-de-hormigas\/#Optimisation-de-colonie-de-fourmis\" >Optimizaci\u00f3n de colonias de hormigas<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-desaims\/colonia-de-hormigas\/#Initialisation-cas-du-TSP\" >Inicializaci\u00f3n (caso de TSP)<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-desaims\/colonia-de-hormigas\/#Construction-de-la-solution-et-recherche-locale\" >Construcci\u00f3n de la soluci\u00f3n y b\u00fasqueda local<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-desaims\/colonia-de-hormigas\/#Fin-dun-cycle\" >Fin de un ciclo<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-desaims\/colonia-de-hormigas\/#Variantes-de-lalgorithme-MMAS\" >Variantes de algoritmo: MMAS<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Colonie-de-fourmis\"><\/span>Colonia de hormigas<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\">Los algoritmos basados en colonias de hormigas resuelven problemas est\u00e1ticos y proporcionan un alto grado de flexibilidad y robustez en entornos din\u00e1micos. La colonia se adapta a cambios repentinos en el medio ambiente y contin\u00faa funcionando cuando ciertos individuos no logran completar su tarea.<\/p><div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">La colonia de hormigas describe agentes con un comportamiento colectivo autoorganizado.Hay emergencia de estructuras a nivel colectivo a partir de interacciones simples basadas en el principio de <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-desaims\/sistema-hormiga\/\">feromonas<\/a> dejado por los oficiales.<\/div><p style=\"text-align: justify;\">El principio de la colonia de hormigas es simple. Las hormigas pueden seleccionar el <a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/\">camino m\u00e1s corto<\/a> para ir del nido a una fuente de alimento depositando y siguiendo rastros de feromonas. Estos son depositados por las hormigas en su camino. Una hormiga tiende a seguir el rastro con el mayor impacto de feromonas. Las feromonas se disipan con el tiempo (no en todas las versiones del algoritmo). Por lo tanto, concluimos que despu\u00e9s de un tiempo, todas las hormigas elegir\u00e1n el camino m\u00e1s corto entre el nido y la comida.<\/p><div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">El algoritmo de la colonia de hormigas se basa en un fen\u00f3meno autocatal\u00edtico, es decir, el fen\u00f3meno se refuerza a s\u00ed mismo (retroalimentaci\u00f3n positiva). La pista m\u00e1s corta se ve favorecida gracias a su concentraci\u00f3n de feromonas. Entonces, m\u00e1s hormigas tomar\u00e1n este camino y, por lo tanto, fortalecer\u00e1n su concentraci\u00f3n de feromonas, etc. Luego hablamos de estigmergia. La optimizaci\u00f3n se realiza gracias a la propiedad emergente, aqu\u00ed el camino con mayor concentraci\u00f3n de feromonas. Se nota que los agentes act\u00faan sin contacto f\u00edsico ni centralizaci\u00f3n de datos.<\/div><h1><span class=\"ez-toc-section\" id=\"Optimisation-de-colonie-de-fourmis\"><\/span>Optimizaci\u00f3n de colonias de hormigas<span class=\"ez-toc-section-end\"><\/span><\/h1><p style=\"text-align: justify;\">El algoritmo fue introducido por el Sr. Dorigo en 1991, inicialmente destinado al TSP (viajero de comercio). Representamos el problema a resolver en la forma de la b\u00fasqueda de un camino m\u00e1s corto en un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">grafico<\/a>.<\/p><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><p>La estructura del algoritmo de la colonia de hormigas es la siguiente:<\/p><ol style=\"text-align: justify;\"><li>Inicializar<\/li><li>Repita hasta un m\u00e1ximo de ciclos<ol><li>Cada hormiga construye una soluci\u00f3n<\/li><li>Mejorar las soluciones por <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-estocasticos\/metodos-de-descenso\/\">busqueda local<\/a><\/li><li>Premie las mejores soluciones agregando feromonas<\/li><li>Evaporar trazas de feromonas<\/li><\/ol><\/li><\/ol><\/div><p style=\"text-align: justify;\">Los algoritmos de tipo ACO tienen pruebas de convergencia que no se mostrar\u00e1n en este curso.<\/p><h2><span class=\"ez-toc-section\" id=\"Initialisation-cas-du-TSP\"><\/span>Inicializaci\u00f3n (caso de TSP)<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\">los <em>metro<\/em> Las hormigas se distribuyen aleatoriamente en el <em>no<\/em> ciudades. Para cada hormiga, un <a href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/tabu-investigacion\/\">lista tab\u00fa<\/a> asignado a \u00e9l, contiene su lista de salida. Los rastros de feromonas se inicializan a un valor <em>vs <\/em>positivo no cero. Cada borde del gr\u00e1fico <em>ij<\/em> tiene su pista de feromonas anotada <em>T<sub>ij<\/sub>= c<\/em>.<\/p><h2><span class=\"ez-toc-section\" id=\"Construction-de-la-solution-et-recherche-locale\"><\/span>Construcci\u00f3n de la soluci\u00f3n y b\u00fasqueda local<span class=\"ez-toc-section-end\"><\/span><\/h2><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><p>Hormigas <em>k<\/em> colocado en una ciudad <em>I<\/em> En este momento <em>t<\/em> elige su ciudad de destino <em>j<\/em> en funci\u00f3n de :<\/p><ul style=\"text-align: justify;\"><li>La visibilidad de esta ciudad <em>no<sub>ij<\/sub><\/em> (distancia en el caso de TSP)<\/li><li>La cantidad de feromona <em>T<sub>ij<\/sub>(t)<\/em> depositado en la pista.<\/li><\/ul><\/div><p style=\"text-align: justify;\">La elecci\u00f3n es aleatoria seg\u00fan una probabilidad donde dos par\u00e1metros <em>Para<\/em> y <em>B<\/em> controlar la importancia relativa de la visibilidad y la cantidad de feromonas. s\u00ed <em>b = 0<\/em>, es m\u00e1s probable que se seleccionen las ciudades m\u00e1s cercanas, esta es una <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">algoritmo<\/a> glot\u00f3n. Ya sea <em>a = 0<\/em>, solo act\u00faa la amplificaci\u00f3n de las feromonas, hay convergencia prematura y resultados no \u00f3ptimos La nueva ciudad se suma a la lista tab\u00fa de las hormigas.<\/p><p style=\"text-align: justify;\">Cada hormiga procede de esta manera hasta que pasan por todos los pueblos.<\/p><h2><span class=\"ez-toc-section\" id=\"Fin-dun-cycle\"><\/span>Fin de un ciclo<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\">Para cada hormigas <em>k<\/em>, calculamos la duraci\u00f3n de su turno <em>LOS<sub>k<\/sub>(t)<\/em> luego vaciamos su lista tab\u00fa (excepto la inicializaci\u00f3n).<\/p><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><p>Luego se actualizan las pistas de feromonas:<\/p><p style=\"text-align: justify;\"><em>T<sub>ij<\/sub>(t + 1) = p * T<sub>ij<\/sub>(t) + feromonas<sub>ij<\/sub>(t)<\/em> con <em>pag<\/em> entre 0 y 1 y <em>feromonas<sub>ij<\/sub>(t)<\/em> la cantidad de feromona depositada por las hormigas en la cresta <em>ij<\/em> al ciclo <em>t<\/em>.<\/p><\/div><p style=\"text-align: justify;\">La evaporaci\u00f3n de la pista se calcula directamente en la f\u00f3rmula anterior. En efecto, p representa la persistencia de la huella, es decir, la memoria de la cantidad de feromonas que se conservan para el ciclo siguiente. s\u00ed <em>p = 1<\/em>, no hay evaporaci\u00f3n, por lo tanto, no hay limitaci\u00f3n del fen\u00f3meno autocatal\u00edtico. s\u00ed <em>p = 0<\/em>, el sistema no tiene memoria, solo se tiene en cuenta el \u00faltimo ciclo realizado.<\/p><p style=\"text-align: justify;\">Para cada hormigas <em>k<\/em> pasando por la cresta <em>ij<\/em>, aumenta la cantidad de feromona depositada seg\u00fan el siguiente c\u00e1lculo:<\/p><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><p style=\"text-align: justify;\"><em>feromonas<sub>ij<\/sub>(t) + = Q \/ L<sub>k<\/sub>(t)<\/em> o <em>Q<\/em> representa una cuota de feromonas asignadas a cada hormiga (a menudo <em>Q = 100<\/em>). La idea es suplir todo el trayecto recorrido por las hormigas de forma homog\u00e9nea con feromonas.<\/p><\/div><p style=\"text-align: justify;\">La vuelta m\u00e1s peque\u00f1a se guarda en la memoria si es mejor que la \u00faltima para memorizar. Las hormigas comienzan un ciclo nuevamente desde su ciudad inicial (mantenida en su lista de tab\u00fa).<\/p><h1><span class=\"ez-toc-section\" id=\"Variantes-de-lalgorithme-MMAS\"><\/span>Variantes de algoritmo: MMAS<span class=\"ez-toc-section-end\"><\/span><\/h1><p style=\"text-align: justify;\">El sistema de hormigas Max-min (MMAS) es una variante eficiente del algoritmo. Solo las mejores hormigas trazan senderos donde la deposici\u00f3n de feromonas est\u00e1 limitada por un l\u00edmite superior y un l\u00edmite inferior. As\u00ed evitamos que una pista est\u00e9 demasiado reforzada y dejamos la posibilidad de explorar cualquier pista. En particular, esto evita una convergencia prematura.<\/p><p><img fetchpriority=\"high\" decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/10.5923.j.eee_.20120204.09_001.png\" alt=\"colonia de hormigas\" width=\"589\" height=\"326\" title=\"\"><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Algoritmos de enjambre Ant Colony Wiki P\u00e1gina de inicio Los algoritmos basados en colonias de hormigas resuelven problemas est\u00e1ticos y proporcionan una... <\/p>","protected":false},"author":1,"featured_media":0,"parent":7135,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-4252","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/4252","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=4252"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/4252\/revisions"}],"predecessor-version":[{"id":18461,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/4252\/revisions\/18461"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/7135"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=4252"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}