{"id":3383,"date":"2016-02-29T11:06:56","date_gmt":"2016-02-29T10:06:56","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=3383"},"modified":"2022-12-03T22:59:03","modified_gmt":"2022-12-03T21:59:03","slug":"algorithmes-genetiques","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/algorithms-devolution-2\/genetic-algorithms\/","title":{"rendered":"Genetic algorithms"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"3383\" class=\"elementor elementor-3383\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7e04ec0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7e04ec0\" 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-59e7a46\" data-id=\"59e7a46\" 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-79090fa elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"79090fa\" 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\/algorithmes-devolution\/\">\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\">Algorithmes d'\u00e9volution<\/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-0ec4bac\" data-id=\"0ec4bac\" 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-42fba94 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"42fba94\" 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\/\">\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\">Page d'accueil<\/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-30b59a2\" data-id=\"30b59a2\" 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-eca3afa elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"eca3afa\" 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_g%C3%A9n%C3%A9tique\" 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-7c08795c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7c08795c\" 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-3dd893e\" data-id=\"3dd893e\" 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-774ad5c6 elementor-widget elementor-widget-text-editor\" data-id=\"774ad5c6\" 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\">Contenus<\/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-devolution-2\/genetic-algorithms\/#Algorithmes-genetiques\" >Algorithmes g\u00e9n\u00e9tiques<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithms-devolution-2\/genetic-algorithms\/#Programmation-genetique-et-algorithmes-genetiques\" >Programmation g\u00e9n\u00e9tique et algorithmes g\u00e9n\u00e9tiques<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithms-devolution-2\/genetic-algorithms\/#Exemple\" >Exemple<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithmes-genetiques\"><\/span>Algorithmes g\u00e9n\u00e9tiques<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\">Les algorithmes g\u00e9n\u00e9tiques sont des <a href=\"https:\/\/complex-systems-ai.com\/en\/stochastic-algorithms-2\/\">algorithmes stochastiques<\/a> it\u00e9ratifs qui op\u00e8rent sur des individus \u00e0 partir d&rsquo;une population initiale.<\/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;\"><p>Dans les algorithmes g\u00e9n\u00e9tiques, la population \u00e9volue de la g\u00e9n\u00e9ration k \u00e0 la g\u00e9n\u00e9ration k+1 \u00e0 l&rsquo;aide de trois op\u00e9rateurs :<\/p><ul style=\"text-align: justify;\"><li>un op\u00e9rateur de S\u00e9lection<\/li><li>un op\u00e9rateur de Croisement<\/li><li>un op\u00e9rateur de Mutation.<\/li><\/ul><\/div><p style=\"text-align: justify;\">Le processus provient de l&rsquo;\u00e9volution g\u00e9n\u00e9tique. On part avec une population de solutions potentielles initiales arbitrairement choisies. On \u00e9value leur performance relative (fitness). Sur la base de ces performances, on cr\u00e9e une nouvelle population de solutions potentielles en utilisant les op\u00e9rateurs. On recommence ce cycle jusqu&rsquo;\u00e0 avec une solution satisfaisante.<\/p><h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Programmation-genetique-et-algorithmes-genetiques\"><\/span>Programmation g\u00e9n\u00e9tique et algorithmes g\u00e9n\u00e9tiques<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\"><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-3394 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/schema_simple_algorithme_genetique.png\" alt=\"algorithmes g\u00e9n\u00e9tiques\" width=\"279\" height=\"547\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/schema_simple_algorithme_genetique.png 279w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/schema_simple_algorithme_genetique-153x300.png 153w\" sizes=\"(max-width: 279px) 100vw, 279px\" \/><\/p><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><ol style=\"text-align: justify;\"><li>Population de base g\u00e9n\u00e9r\u00e9e al\u00e9atoirement : n vecteurs de solution (individus)<\/li><li>\u00c9valuation de chaque individu, cette \u00e9valuation retourne une valeur quantitative (fitness)<\/li><li>S\u00e9lection par tirage au sort d&rsquo;un sous-ensemble d&rsquo;individus par une roue biais\u00e9e, par rang, par tournoi ou par eug\u00e9nisme. Chaque individu a une probabilit\u00e9 d&rsquo;\u00eatre choisi proportionnelle \u00e0 son \u00e9valuation (ou adaptation au probl\u00e8me).<\/li><li>Croisements et Mutations des individus s\u00e9lectionn\u00e9s.<\/li><\/ol><\/div><p style=\"text-align: justify;\">Les croisements et mutations\u00a0 des algorithmes g\u00e9n\u00e9tiques ne donnent pas forc\u00e9ment des solutions admissibles au probl\u00e8me. Ils op\u00e8rent par alt\u00e9ration, copie, remplacement, etc, du vecteur de solution d&rsquo;un ou plusieurs individus pour en former un nouveau.<\/p><h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Exemple<span class=\"ez-toc-section-end\"><\/span><\/h2><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;\">Afin de pouvoir effectuer des croisements et des mutations le plus simplement possible, nous allons encoder les individus par une cha\u00eene binaire. Le croisement se fera alors par une sous-cha\u00eene, et la mutation par la modification d&rsquo;un bit. Ce processus s&rsquo;appelle encodage binaire.<\/div><p style=\"text-align: justify;\">Nous cherchons le maximum de f(x)=4x*(1-x) sur l&rsquo;intervalle [0,1]. Nous prenons une population initiale de 4 \u00e9l\u00e9ments cod\u00e9s sur 8 bits (qui seront convertis en une valeur entre 0 et 1). Les nouvelles g\u00e9n\u00e9rations comporteront toujours 4 individus. Le tableau de valeur de la g\u00e9n\u00e9ration initiale est le suivant :<\/p><div class=\"standard\" style=\"text-align: justify;\"><table><tbody><tr><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">\u00c9l\u00e9ment<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">f(x)<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">% \/ total<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">cumul<\/div><\/td><\/tr><tr><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">10111010<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">0.794678<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">0.79\/2.59=0.31<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">0.31<\/div><\/td><\/tr><tr><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">11011110<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">0.460693<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">0.18<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">0.49<\/div><\/td><\/tr><tr><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">00011010<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">0.364990<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">0.14<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">0.63<\/div><\/td><\/tr><tr><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">01101100<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">0.9775586<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">0.37<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">1.00<\/div><\/td><\/tr><tr><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">&#8211;<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">2.595947<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">&#8211;<\/div><\/td><td align=\"center\" valign=\"top\"><div class=\"plain_layout\">&#8211;<\/div><\/td><\/tr><\/tbody><\/table><\/div><p style=\"text-align: justify;\">\u00c9l\u00e9ment repr\u00e9sente les individus, f(x) la valeur de la fonction objectif, % \/ total est le pourcentage de la valeur de la fonction objectif d&rsquo;un \u00e9l\u00e9ment par rapport \u00e0 la somme des valeurs de la fonction objectif, cumul est la somme des pourcentages. Nous avons donc au final l&rsquo;importance de chaque individu compte tenu de la valeur de la fonction objectif.<\/p><p style=\"text-align: justify;\">Maintenant que l&rsquo;\u00e9valuation est faite, nous devons s\u00e9lectionner des individus pour le croisement. Puisque nous avons une \u00e9chelle d&rsquo;importance de chaque individu, nous pouvons tirer au sort des individus. En effet, plus la valeur objectif d&rsquo;un individu est grande, plus il a de chance d&rsquo;\u00eatre tir\u00e9 au sort. On tire quatre nombres al\u00e9atoires entre 0 et 1 : 0.34, 0.02, 0.64 et 0.77. Nous avons donc s\u00e9lectionn\u00e9 ces individus : 11011110, 10111010, 01101100, 01101100.<\/p><p style=\"text-align: justify;\">Nous avons s\u00e9lectionn\u00e9 les parents, il faut d\u00e9sormais effectuer le croisement. Pour cela, nous choisissons un marqueur al\u00e9atoire dans la chaine de bit, et nous permutons la partie droite de la cha\u00eene :<\/p><p style=\"text-align: justify;\"><img decoding=\"async\" class=\"alignnone wp-image-3509 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/gene.png\" alt=\"algorithmes g\u00e9n\u00e9tiques\" width=\"641\" height=\"437\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/gene.png 641w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/gene-300x205.png 300w\" sizes=\"(max-width: 641px) 100vw, 641px\" \/><\/p><p style=\"text-align: justify;\">La population de la prochaine g\u00e9n\u00e9ration est compos\u00e9e des quatre enfants ainsi cr\u00e9\u00e9s. En g\u00e9n\u00e9ral, nous \u00e9viterons d&rsquo;effectuer un croisement entre deux individus identiques.<\/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>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Evolution Algorithms Wiki Home Page Genetic Algorithms Genetic algorithms are iterative stochastic algorithms that operate on individuals from an initial population. \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":7110,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-3383","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3383","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=3383"}],"version-history":[{"count":7,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3383\/revisions"}],"predecessor-version":[{"id":18446,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3383\/revisions\/18446"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/7110"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=3383"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}