{"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\/en\/algorithms-desaims\/ant-colony\/","title":{"rendered":"Ant colony"},"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\/en\/algorithms-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\">Swarm algorithms<\/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\/en\/\">\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\">Home page<\/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\">Contents<\/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=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/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\/en\/algorithms-desaims\/ant-colony\/#Colonie-de-fourmis\" >Ant colony<\/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\/en\/algorithms-desaims\/ant-colony\/#Optimisation-de-colonie-de-fourmis\" >Ant colony optimization<\/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\/en\/algorithms-desaims\/ant-colony\/#Initialisation-cas-du-TSP\" >Initialization (case of 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\/en\/algorithms-desaims\/ant-colony\/#Construction-de-la-solution-et-recherche-locale\" >Construction of the solution and local search<\/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\/en\/algorithms-desaims\/ant-colony\/#Fin-dun-cycle\" >End of a cycle<\/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\/en\/algorithms-desaims\/ant-colony\/#Variantes-de-lalgorithme-MMAS\" >Algorithm variants: MMAS<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Colonie-de-fourmis\"><\/span>Ant colony<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\">Ant colony-based algorithms solve static problems and provide a high degree of flexibility and robustness in dynamic environments. The colony adapts to sudden changes in the environment and continues to function when certain individuals fail to complete their task.<\/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;\">The ant colony describes agents with self-organized collective behavior. There is emergence of structures at the collective level from simple interactions based on the principle of <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithms-desaims\/ant-system\/\">pheromones<\/a> left by officers.<\/div><p style=\"text-align: justify;\">The principle of ant colony is simple. Ants are able to select the <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/\">shortest way<\/a> to get from the nest to a food source by depositing and following pheromone trails. These are deposited by ants on their way. An ant tends to follow the trail with the highest pheromone impact. Pheromones dissipate over time (not in all versions of the algorithm). We therefore conclude that after a time, the ants will all choose the shortest path between the nest and the food.<\/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;\">The ant colony algorithm is based on an autocatalytic phenomenon, i.e. the phenomenon reinforces itself (positive feedback). The shortest track is favored thanks to its concentration of pheromones. So more ants will take this trail and therefore strengthen its concentration of pheromones, etc. We then speak of stigmergy. The optimization is made thanks to the emergent property, here the path with the greatest concentration of pheromones. It is noted that the agents act without physical contact or centralization of data.<\/div><h1><span class=\"ez-toc-section\" id=\"Optimisation-de-colonie-de-fourmis\"><\/span>Ant colony optimization<span class=\"ez-toc-section-end\"><\/span><\/h1><p style=\"text-align: justify;\">The algorithm was introduced by Mr. Dorigo in 1991, initially intended for the TSP (travelling salesman). We represent the problem to be solved in the form of the search for a shortest path in a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a>.<\/p><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><p>The structure of the ant colony algorithm is as follows:<\/p><ol style=\"text-align: justify;\"><li>Initialize<\/li><li>Repeat up to max cycles<ol><li>Every ant builds a solution<\/li><li>Improving solutions by <a href=\"https:\/\/complex-systems-ai.com\/en\/stochastic-algorithms-2\/descent-methods\/\">local search<\/a><\/li><li>Reward the best solutions by adding pheromone<\/li><li>Evaporate traces of pheromone<\/li><\/ol><\/li><\/ol><\/div><p style=\"text-align: justify;\">ACO type algorithms have proofs of convergence that will not be shown in this course.<\/p><h2><span class=\"ez-toc-section\" id=\"Initialisation-cas-du-TSP\"><\/span>Initialization (case of TSP)<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\">The <em>m<\/em> ants are distributed randomly on the <em>not<\/em> cities. For each ant, a <a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/taboo-research\/\">taboo list<\/a> assigned to him, it contains his start list. Pheromone trails are initialized to a value <em>vs <\/em>positive not zero. Each edge of the graph <em>ij<\/em> has its pheromone track noted <em>T<sub>ij<\/sub>= c<\/em>.<\/p><h2><span class=\"ez-toc-section\" id=\"Construction-de-la-solution-et-recherche-locale\"><\/span>Construction of the solution and local search<span class=\"ez-toc-section-end\"><\/span><\/h2><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><p>An ants <em>k<\/em> placed on a city <em>i<\/em> just now <em>t<\/em> chooses his destination city <em>j<\/em> in terms of :<\/p><ul style=\"text-align: justify;\"><li>The visibility of this city <em>not<sub>ij<\/sub><\/em> (distance in the case of TSP)<\/li><li>The amount of pheromone <em>T<sub>ij<\/sub>(t)<\/em> deposited on the runway.<\/li><\/ul><\/div><p style=\"text-align: justify;\">The choice is random according to a probability where two parameters <em>To<\/em> and <em>b<\/em> control the relative importance of visibility and the amount of pheromones. Yes <em>b = 0<\/em>, the nearest cities are more likely to be selected, this is a <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithm<\/a> gluttonous. Whether <em>a = 0<\/em>, only the amplification of the pheromones acts, there is premature convergence and non-optimal results. The new city is added to the taboo list of the ants.<\/p><p style=\"text-align: justify;\">Each ants proceeds in this way until they go through all the towns.<\/p><h2><span class=\"ez-toc-section\" id=\"Fin-dun-cycle\"><\/span>End of a cycle<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\">For each ants <em>k<\/em>, we calculate the length of his turn <em>THE<sub>k<\/sub>(t)<\/em> then we empty its taboo-list (except initialization).<\/p><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><p>Then the pheromone tracks are updated:<\/p><p style=\"text-align: justify;\"><em>T<sub>ij<\/sub>(t + 1) = p * T<sub>ij<\/sub>(t) + pheromones<sub>ij<\/sub>(t)<\/em> with <em>p<\/em> between 0 and 1 and <em>pheromones<sub>ij<\/sub>(t)<\/em> the amount of pheromone deposited by the ants on the ridge <em>ij<\/em> to cycle <em>t<\/em>.<\/p><\/div><p style=\"text-align: justify;\">Evaporation from the track is calculated directly in the previous formula. Indeed p represents the persistence of the track, that is to say the memory of the quantity of pheromones which one keeps for the following cycle. Yes <em>p = 1<\/em>, there is no evaporation therefore no limitation of the autocatalytic phenomenon. Yes <em>p = 0<\/em>, the system has no memory, only the last cycle performed is taken into account.<\/p><p style=\"text-align: justify;\">For each ants <em>k<\/em> passing through the ridge <em>ij<\/em>, it increases the quantity of pheromone deposited according to the following calculation:<\/p><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><p style=\"text-align: justify;\"><em>pheromones<sub>ij<\/sub>(t) + = Q \/ L<sub>k<\/sub>(t)<\/em> or <em>Q<\/em> represents a quota of pheromones allocated to each ants (often <em>Q = 100<\/em>). The idea is to supply all the way traveled by an ants homogeneously with pheromones.<\/p><\/div><p style=\"text-align: justify;\">The smallest lap is kept in memory if it is better than the last one to memorize. The ants start a cycle again from their initial city (kept in their taboo list).<\/p><h1><span class=\"ez-toc-section\" id=\"Variantes-de-lalgorithme-MMAS\"><\/span>Algorithm variants: MMAS<span class=\"ez-toc-section-end\"><\/span><\/h1><p style=\"text-align: justify;\">The Max-min ant system (MMAS) is an efficient variant of the algorithm. Only the best ants trace trails where the deposition of pheromones is limited by an upper bound and a lower bound. Thus we prevent a track from being too reinforced and we leave the possibility of exploring any track. In particular, this prevents premature convergence.<\/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=\"ant colony\" 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>Swarm Algorithms Ant Colony Wiki Home Page Ant colony-based algorithms solve static problems and provide a \u2026 <\/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\/en\/wp-json\/wp\/v2\/pages\/4252","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=4252"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/4252\/revisions"}],"predecessor-version":[{"id":18461,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/4252\/revisions\/18461"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/7135"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=4252"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}