{"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\/en\/algorithms-desaims\/ant-system\/","title":{"rendered":"Ant system"},"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\/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-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\/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-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\">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' ><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\/en\/algorithms-desaims\/ant-system\/#Systeme-de-fourmis\" >Ant system<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Systeme-de-fourmis\"><\/span>Ant system<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The ant system algorithm is inspired by the foraging behavior of ants, in particular the pheromone communication between ants regarding a good path between the colony and a food source in an environment. This mechanism is called stigmergy.<\/p>\n<p><\/p>\n<p>Ants initially roam randomly in their environment. Once the food is located, an ant will begin to deposit pheromones in the environment. Many trips between the food and the colony are made and if the same route that leads to the food is followed, additional pheromones are deposited. Pheromones decay in the environment, so the old ways are less likely to be followed. Other ants can discover the same path to food and in turn can follow it and also deposit pheromones. A process of positive feedback directs more and more ants to productive pathways which in turn are refined by use.<\/p>\n<p><\/p>\n<p>The goal of ant system strategy is to exploit historical and heuristic information to construct candidate solutions and fold information gained from solution construction into history. The solutions are discrete and probabilistically constructed for each step. The probability of selection of a component is determined by the contribution <a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/\">heuristic<\/a> of the component to the overall cost of the solution and the quality of the solutions from which the component is historically known to have been included. The history is updated in proportion to the quality of the candidate solutions and is evenly diminished, ensuring that the most recent and useful information is retained.<\/p>\n<p><\/p>\n<p>The following algorithm provides a <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/pseudo-language-and-flowchart\/\">pseudocode<\/a> of the main ant system algorithm to minimize a cost function. The pheromone update process is described by a single equation that combines the contributions of all candidate solutions with a decay coefficient to determine the new pheromone value, as follows:<\/p>\n<p><\/p>\n<figure><img decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/03\/ant1.png\" alt=\"ant system\" width=\"316\" height=\"84\" title=\"\"><\/figure>\n<p><\/p>\n<p>where \u03c4_i,j represents the pheromone for the component (an edge in a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a>) (i; j), \u03c1 is the decay factor, m is the number of ants, and the sum of the deltas is the sum of 1\/S_cost (maximization of solution cost) for solutions that include component i,j . The algorithm shows this equation as an equivalent of a two-step decay process followed by an update for simplicity.<\/p>\n<p><\/p>\n<p>The step-by-step probabilistic construction of the solution uses both the history (pheromone) and heuristic information specific to the problem to gradually build a solution piece by piece. Each component can only be selected if it has not already been chosen (for most combinatorial problems), and for components that can be selected (given the current component i), their selection probability is defined as follows:<\/p>\n<p><\/p>\n<figure><img decoding=\"async\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/03\/ant2.png\" alt=\"ant system\" width=\"253\" height=\"84\" title=\"\"><\/figure>\n<p><\/p>\n<p>where \u03b7_i, j is the maximizing contribution to the overall component selection score (such as 1 \/ distance for the traveling salesman&#039;s problem), \u03b1 is the heuristic coefficient, \u03c4_i, j is the pheromone value for the component, \u03b2 is the coefficient of the history, and it is the set of usable components.<\/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=\"ant system\" width=\"699\" height=\"636\" title=\"\"><\/figure>\n<p><\/p>\n<p>The ant system algorithm was designed for use with combinatorial problems such as the TSP, the problem of the <a href=\"https:\/\/complex-systems-ai.com\/en\/industrial-problems-and-polynomial-reduction\/backpack-problem\/\">backpack<\/a>, quadratic assignment problems, <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/click-and-stable-coloring\/\">coloring<\/a> graphs and many more.<\/p>\n<p><\/p>\n<p>The history coefficient (\u03b1) controls the amount of contribution history in the component selection probability and is typically set to 1.0. The heuristic coefficient (\u03b2) controls the amount of heuristic information specific to the contribution problem played in a component selection probability and is typically between 2 and 5, such as 2.5. The decay factor (\u03c1) controls the rate at which historical information is lost and is usually set at 0.5. The total number of ants (m) is usually defined by the number of components of the problem, such as the number of cities in the 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 Home Page Ant System The ant system algorithm is inspired by the foraging behavior of ants, in \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-7898","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/7898","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=7898"}],"version-history":[{"count":7,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/7898\/revisions"}],"predecessor-version":[{"id":18891,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/7898\/revisions\/18891"}],"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=7898"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}