{"id":7898,"date":"2020-03-18T11:45:18","date_gmt":"2020-03-18T10:45:18","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=7898"},"modified":"2022-12-03T23:03:47","modified_gmt":"2022-12-03T22:03:47","slug":"systeme-de-fourmis","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/algoritmos-desaims\/sistema-hormiga\/","title":{"rendered":"Sistema de hormigas"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"7898\" class=\"elementor elementor-7898\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2363c5c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2363c5c\" 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-a34ba72\" data-id=\"a34ba72\" 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-d0d5bdb elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"d0d5bdb\" 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-3453678\" data-id=\"3453678\" 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-7958a80 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"7958a80\" 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-6360d1f\" data-id=\"6360d1f\" 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-ca6a3f8 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"ca6a3f8\" 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-3bdff810 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"3bdff810\" 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-25a2229d\" data-id=\"25a2229d\" 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-64de44f0 elementor-widget elementor-widget-text-editor\" data-id=\"64de44f0\" 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<p><\/p>\n<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' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-desaims\/sistema-hormiga\/#Systeme-de-fourmis\" >Sistema de hormigas<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Systeme-de-fourmis\"><\/span>Sistema de hormigas<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>El algoritmo del sistema de hormigas est\u00e1 inspirado en el comportamiento de b\u00fasqueda de alimento de las hormigas, en particular la comunicaci\u00f3n de feromonas entre las hormigas con respecto a un buen camino entre la colonia y una fuente de alimento en un medio ambiente. Este mecanismo se llama estigmergia.<\/p>\n<p><\/p>\n<p>Las hormigas inicialmente deambulan al azar en su entorno. Una vez que se localiza la comida, una hormiga comenzar\u00e1 a depositar feromonas en el medio ambiente. Se realizan muchos viajes entre la comida y la colonia y si se sigue la misma ruta que lleva a la comida se depositan feromonas adicionales. Las feromonas se descomponen en el medio ambiente, por lo que es menos probable que se sigan las viejas formas. Otras hormigas pueden descubrir el mismo camino hacia la comida y a su vez pueden seguirlo y tambi\u00e9n depositar feromonas. Un proceso de retroalimentaci\u00f3n positiva dirige a m\u00e1s y m\u00e1s hormigas a caminos productivos que, a su vez, se refinan con el uso.<\/p>\n<p><\/p>\n<p>El objetivo de la estrategia del sistema de hormigas es explotar la informaci\u00f3n hist\u00f3rica y heur\u00edstica para construir soluciones candidatas y plegar la informaci\u00f3n obtenida de la construcci\u00f3n de soluciones en la historia. Las soluciones son discretas y construidas probabil\u00edsticamente para cada paso. La probabilidad de selecci\u00f3n de un componente est\u00e1 determinada por la contribuci\u00f3n <a href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/\">heur\u00edstico<\/a> del componente al costo total de la soluci\u00f3n y la calidad de las soluciones a partir de las cuales se sabe hist\u00f3ricamente que se incluy\u00f3 el componente. El historial se actualiza en proporci\u00f3n a la calidad de las soluciones candidatas y se reduce uniformemente, lo que garantiza que se conserve la informaci\u00f3n m\u00e1s reciente y \u00fatil.<\/p>\n<p><\/p>\n<p>El siguiente algoritmo proporciona una <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/pseudo-lenguaje-y-diagrama-de-flujo\/\">pseudoc\u00f3digo<\/a> del algoritmo del sistema hormiga principal para minimizar una funci\u00f3n de costo. El proceso de actualizaci\u00f3n de feromonas se describe mediante una sola ecuaci\u00f3n que combina las contribuciones de todas las soluciones candidatas con un coeficiente de decaimiento para determinar el nuevo valor de feromonas, de la siguiente manera:<\/p>\n<p><\/p>\n<figure><img decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/03\/ant1.png\" alt=\"sistema de hormigas\" width=\"316\" height=\"84\" title=\"\"><\/figure>\n<p><\/p>\n<p>donde \u03c4_i,j representa la feromona del componente (un borde en un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">grafico<\/a>) (i; j), \u03c1 es el factor de descomposici\u00f3n, m es el n\u00famero de hormigas y la suma de los deltas es la suma de 1\/S_cost (maximizaci\u00f3n del costo de la soluci\u00f3n) para soluciones que incluyen el componente i, j . El algoritmo muestra esta ecuaci\u00f3n como un equivalente de un proceso de descomposici\u00f3n de dos pasos seguido de una actualizaci\u00f3n por simplicidad.<\/p>\n<p><\/p>\n<p>La construcci\u00f3n probabil\u00edstica paso a paso de la soluci\u00f3n utiliza tanto el historial (feromonas) como la informaci\u00f3n heur\u00edstica espec\u00edfica del problema para construir gradualmente una soluci\u00f3n pieza por pieza. Cada componente solo puede seleccionarse si a\u00fan no se ha elegido (para la mayor\u00eda de los problemas combinatorios), y para los componentes que pueden seleccionarse (dado el componente i actual), su probabilidad de selecci\u00f3n se define de la siguiente manera:<\/p>\n<p><\/p>\n<figure><img decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/03\/ant2.png\" alt=\"sistema de hormigas\" width=\"253\" height=\"84\" title=\"\"><\/figure>\n<p><\/p>\n<p>donde \u03b7_i, j es la contribuci\u00f3n maximizadora al puntaje general de selecci\u00f3n de componentes (como 1 \/ distancia para el problema del viajante de comercio), \u03b1 es el coeficiente heur\u00edstico, \u03c4_i, j es el valor de feromonas para el componente, \u03b2 es el coeficiente de la historia, y es el conjunto de componentes utilizables.<\/p>\n<p><\/p>\n<figure><img fetchpriority=\"high\" decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/03\/ant3.png\" alt=\"sistema de hormigas\" width=\"699\" height=\"636\" title=\"\"><\/figure>\n<p><\/p>\n<p>El algoritmo del sistema hormiga fue dise\u00f1ado para su uso con problemas combinatorios como el TSP, el problema de la <a href=\"https:\/\/complex-systems-ai.com\/es\/problemas-industriales-y-reduccion-de-polinomios\/problema-de-la-mochila\/\">mochila<\/a>, problemas de asignaci\u00f3n cuadr\u00e1tica, <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/clic-y-coloracion-estable\/\">colorante<\/a> gr\u00e1ficos y muchos m\u00e1s.<\/p>\n<p><\/p>\n<p>El coeficiente de historial (\u03b1) controla la cantidad de historial de contribuci\u00f3n en la probabilidad de selecci\u00f3n de componentes y generalmente se establece en 1.0. El coeficiente heur\u00edstico (\u03b2) controla la cantidad de informaci\u00f3n heur\u00edstica espec\u00edfica del problema de contribuci\u00f3n jugado en la probabilidad de selecci\u00f3n de un componente y t\u00edpicamente est\u00e1 entre 2 y 5, como 2.5. El factor de desintegraci\u00f3n (\u03c1) controla la velocidad a la que se pierde la informaci\u00f3n hist\u00f3rica y, por lo general, se establece en 0,5. El n\u00famero total de hormigas (m) generalmente se define por el n\u00famero de componentes del problema, como el n\u00famero de ciudades en el TSP.<\/p>\n<p><\/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>Swarm Algorithms Wiki P\u00e1gina de inicio Sistema de hormigas El algoritmo del sistema de hormigas est\u00e1 inspirado en el comportamiento de b\u00fasqueda de alimento de las hormigas, en ... <\/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-7898","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/7898","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=7898"}],"version-history":[{"count":7,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/7898\/revisions"}],"predecessor-version":[{"id":18891,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/7898\/revisions\/18891"}],"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=7898"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}