{"id":7653,"date":"2020-03-09T10:21:33","date_gmt":"2020-03-09T09:21:33","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=7653"},"modified":"2022-12-03T23:03:45","modified_gmt":"2022-12-03T22:03:45","slug":"evolution-grammaticale-pour-lalgorithme-genetique","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/algorithms-devolution-2\/grammatical-evolution-for-the-genetic-algorithm\/","title":{"rendered":"Grammatical evolution for the genetic algorithm"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"7653\" class=\"elementor elementor-7653\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-da5e6a2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"da5e6a2\" 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-0e9b72d\" data-id=\"0e9b72d\" 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-109c264 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"109c264\" 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-devolution-2\/\">\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\">Evolution 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-9b819c7\" data-id=\"9b819c7\" 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-e3f608d elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"e3f608d\" 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-adb4b0f\" data-id=\"adb4b0f\" 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-966db4c elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"966db4c\" 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:\/\/en.wikipedia.org\/wiki\/Grammatical_evolution\" 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-7f8b6bc3 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7f8b6bc3\" 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-64b6a1a4\" data-id=\"64b6a1a4\" 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-7de3524f elementor-widget elementor-widget-text-editor\" data-id=\"7de3524f\" 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\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-devolution-2\/grammatical-evolution-for-the-genetic-algorithm\/#Algorithme-evolution-grammaticale\" >Grammatical evolution algorithm<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-evolution-grammaticale\"><\/span>Grammatical evolution algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p class=\"has-text-align-justify\">The grammatical evolution algorithm is inspired by the biological process used to generate a protein from genetic material as well as the larger genetic evolutionary process. The genome is made up of DNA like a chain of building blocks that are transcribed into RNA. The RNA codons are in turn translated into amino acid sequences and used in the protein. The resulting protein in its environment is the phenotype.<\/p>\n\n<p class=\"has-text-align-justify\">The phenotype is a computer program created from a genome based on binary chains. The genome is decoded into a sequence of integers which in turn are mapped to pre-defined rules that make up the program. Mapping from genotype to phenotype is a one-to-many process that uses a packaging function.<\/p>\n<p class=\"has-text-align-justify\">It is like the biological process seen in many bacteria, viruses and mitochondria, where the same genetic material is used in the expression of different genes. Mapping adds robustness to the process both in the ability to adopt genetic operators used during the evolutionary process on the sub-symbolic representation and the transcription of well-formed executable programs from the representation.<\/p>\n\n<p class=\"has-text-align-justify\">The goal of the grammatical evolution algorithm is to adapt an executable program to a problem-specific objective function. This is achieved through an iterative process with surrogates of evolutionary mechanisms such as descent with variation, genetic mutation and recombination, genetic transcription and gene expression. A population of programs is expanded in subsymbolic form as variable-length binary strings and mapped to symbolic and well-structured form as <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/types-of-grammars\/\">grammar<\/a> without context for execution.<\/p>\n\n<p class=\"has-text-align-justify\">A grammar is defined in Backus Normal Form (BNF), which is a contextless grammar expressed as a series of production rules comprising terminals and non-terminals. A variable length binary string representation is used for the optimization process. Bits are read from the genome of candidate solutions in blocks of 8 called codons and decoded into an integer (between 0 and 2 ^ 8 - 1).<\/p>\n<p class=\"has-text-align-justify\">If the end of the binary string is reached while reading integers, the reading process loops back to the beginning of the string, creating a circular genome. Integers are mapped to expressions in the BNF until a complete syntactically correct expression is formed. This may not use an entire genome of solutions, or use the decoded genome more than once given its circular nature.<\/p>\n\n<p class=\"has-text-align-justify\">The grammatical evolution was designed to optimize the programs (such as the equations <a href=\"https:\/\/complex-systems-ai.com\/en\/logic-math-27\/\">math<\/a>) for specific cost functions. The classical genetic operators used by the<a href=\"https:\/\/complex-systems-ai.com\/en\/algorithms-devolution-2\/genetic-algorithms\/\">genetic algorithm<\/a> can be used in the grammatical evolution algorithm, such as point mutations and one-point crossover. Additional genetic operators can be used with variable length representations such as codon segments, duplication (append to end), number of randomly selected codons, and deletion.<\/p>\n\n<figure class=\"wp-block-image size-large\"><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-7655 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/03\/gramevo.png\" alt=\"grammatical evolution algorithm\" width=\"453\" height=\"555\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/03\/gramevo.png 453w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/03\/gramevo-245x300.png 245w\" sizes=\"(max-width: 453px) 100vw, 453px\" \/><\/figure>\n\n<p>\u00a0<\/p>\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<\/div>","protected":false},"excerpt":{"rendered":"<p>Evolution Algorithms Wiki Home Page Grammar Evolution Algorithm The grammar evolution algorithm is inspired by the biological process used to generate a protein from genetic material\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-7653","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/7653","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=7653"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/7653\/revisions"}],"predecessor-version":[{"id":18873,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/7653\/revisions\/18873"}],"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=7653"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}