{"id":29179,"date":"2013-05-25T15:05:31","date_gmt":"2013-05-25T09:35:31","guid":{"rendered":"http:\/\/www.kopykitab.com\/blog\/?p=29179"},"modified":"2013-05-25T15:05:31","modified_gmt":"2013-05-25T09:35:31","slug":"genetic-algorithm-fundamentals-basic-concepts-notes","status":"publish","type":"post","link":"https:\/\/www.kopykitab.com\/blog\/genetic-algorithm-fundamentals-basic-concepts-notes\/","title":{"rendered":"Genetic Algorithm Fundamentals Basic Concepts Notes"},"content":{"rendered":"<h1 style=\"text-align: center;\">Genetic Algorithm Fundamentals Basic Concepts Notes<\/h1>\n<h3><\/h3>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_47_1 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\">Table of 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=\"ez-toc-toggle-icon-1\"><label for=\"item-69da070379611\" aria-label=\"Table of Content\"><span style=\"display: flex;align-items: center;width: 35px;height: 30px;justify-content: center;direction:ltr;\"><svg style=\"fill: #000000;color:#000000\" 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: #000000;color:#000000\" 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><\/label><input  type=\"checkbox\" id=\"item-69da070379611\"><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 eztoc-visibility-hide-by-default' ><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.kopykitab.com\/blog\/genetic-algorithm-fundamentals-basic-concepts-notes\/#introduction\" title=\"Introduction\">Introduction<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.kopykitab.com\/blog\/genetic-algorithm-fundamentals-basic-concepts-notes\/#background\" title=\"Background\">Background<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.kopykitab.com\/blog\/genetic-algorithm-fundamentals-basic-concepts-notes\/#natural-selection\" title=\"Natural Selection\">Natural Selection<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.kopykitab.com\/blog\/genetic-algorithm-fundamentals-basic-concepts-notes\/#simulated-evolution\" title=\"Simulated Evolution\">Simulated Evolution<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.kopykitab.com\/blog\/genetic-algorithm-fundamentals-basic-concepts-notes\/#genetic-algorithm-vocabulary\" title=\"Genetic algorithm vocabulary\">Genetic algorithm vocabulary<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/www.kopykitab.com\/blog\/genetic-algorithm-fundamentals-basic-concepts-notes\/#concepts\" title=\"Concepts\">Concepts<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/www.kopykitab.com\/blog\/genetic-algorithm-fundamentals-basic-concepts-notes\/#basic-principle\" title=\"Basic Principle\">Basic Principle<\/a><\/li><\/ul><\/nav><\/div>\n<h3><span class=\"ez-toc-section\" id=\"introduction\"><\/span><b>Introduction<\/b><span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>Genetic Algorithms are a family of computational models inspired by evolution. These algorithms encode a potential solution to a specific problem on a simple chromosome-like data structure and apply recombination operators to these structures as as to preserve critical information. Genetic algorithms are often viewed as function optimizer, although the range of problems to which genetic algorithms have been applied are quite broad.<\/p>\n<p>&nbsp;<\/p>\n<p>An implementation of genetic algorithm begins with a population of (typically random) chromosomes. One then evaluates these structures and allocated reproductive opportunities in such a way that these chromosomes which represent a better solution to the target problem are given more chances to `reproduce&#8217; than those chromosomes which are poorer solutions. The &#8216;goodness&#8217; of a solution is typically defined with respect to the current population.<\/p>\n<h3><span class=\"ez-toc-section\" id=\"background\"><\/span>Background<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>Many human inventions were inspired by nature. Artificial neural networks is one example. Another example is Genetic Algorithms (GA). GAs search by simulating evolution, starting from an initial set of solutions or hypotheses, and generating successive &#8220;generations&#8221; of solutions. This particular branch of AI was inspired by the way living things evolved into more successful organisms in nature. The main idea is survival of the fittest, a.k.a. natural selection.<\/p>\n<p>A chromosome is a long, complicated thread of DNA (deoxyribonucleic acid). Hereditary factors that determine particular traits of an individual are strung along the length of these chromosomes, like beads on a necklace. Each trait is coded by some combination of DNA (there are four bases, A (Adenine), C (Cytosine), T (Thymine) and G (Guanine). Like an alphabet in a language, meaningful combinations of the bases produce specific instructions to the cell.<\/p>\n<p>Changes occur during reproduction. The chromosomes from the parents exchange randomly by a process called crossover. Therefore, the offspring exhibit some traits of the father and some traits of the mother. A rarer process called mutation also changes some traits. Sometimes an error may occur during copying of chromosomes (mitosis). The parent cell may have -A-C-G-C-T- but an accident may occur and changes the new cell to -A-C-T-C-T-. Much like a typist copying a book, sometimes a few mistakes are made. Usually this results in a nonsensical word and the cell does not survive. But over millions of years, sometimes the accidental mistake produces a more beautiful phrase for the book, thus producing a better species.<\/p>\n<p>&nbsp;<\/p>\n<h3><span class=\"ez-toc-section\" id=\"natural-selection\"><\/span>Natural Selection<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>In nature, the individual that has better survival traits will survive for a longer period of time. This in turn provides it a better chance to produce offspring with its genetic material. Therefore, after a long period of time, the entire population will consist of lots of genes from the superior individuals and less from the inferior individuals. In a sense, the fittest survived and the unfit died out. This force of nature is called natural selection.<\/p>\n<p>The existence of competition among individuals of a species was recognized certainly before Darwin. The mistake made by the older theorists (like Lamarck) was that the environment had an effect on an individual. That is, the environment will force an individual to adapt to it. The molecular explanation of evolution proves that this is biologically impossible. The species does not adapt to the environment, rather, only the fittest survive.<\/p>\n<p>&nbsp;<\/p>\n<h3><span class=\"ez-toc-section\" id=\"simulated-evolution\"><\/span>Simulated Evolution<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>To simulate the process of natural selection in a computer, we need to define the following: A representation of an individual At each point during the search process we maintain a &#8220;generation&#8221; of &#8220;individuals.&#8221; Each individual is a data structure representing the &#8220;genetic structure&#8221; of a possible solution or hypothesis. Like a chromosome, the genetic structure of an individual is described using a fixed, finite alphabet. In GAs, the alphabet 0, 1 is usually used. This string is interpreted as a solution to the problem we are trying to solve.<\/p>\n<p>For example, say we want to find the optimal quantity of the three major ingredients in a recipe (say, sugar, wine, and sesame oil). We can use the alphabet 1, 2, 3 &#8230;, 9 denoting the number of ounces of each ingredient. Some possible solutions are 1-1-1, 2-1-4, and 3-3-1<\/p>\n<p>As another example, the traveling salesperson problem is the problem of finding the optimal path to traverse, say, 10 cities. The salesperson may start in any city. A solution is a permutation of the 10 cities: 1-4-2-3-6-7-9-8-5-10.<\/p>\n<p>As another example, say we want to represent a rule-based system. Given a rule such as &#8220;If color=red and size=small and shape=round then object=apple&#8221; we can describe it as a bit string by first assuming each of the attributes can take on a fixed set of possible values. Say color=red, green, blue, size=small, big, shape=square, round, and fruit=orange, apple, banana, pear. Then we could represent the value for each attribute as a sub-string of length equal to the number of possible values of that attribute. For example, color=red could be represented by 100, color=green by 010, and color=blue by 001. Note also that we can represent color=red or blue by 101, and any color (i.e., a &#8220;don&#8217;t care&#8221;) by 111. Doing this for each attribute, the above rule might then look like: 100 10 01 0100. A set of rules is then represented by concatenating together each rule&#8217;s 11-bit string. For another example see page 620 in the textbook for a bit-string representation of a logical conjunction.<\/p>\n<p>&nbsp;<\/p>\n<h3><span class=\"ez-toc-section\" id=\"genetic-algorithm-vocabulary\"><\/span>Genetic algorithm vocabulary<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>Explanation of Genetic Algorithm terms:<\/p>\n<p>Genetic Algorithms\u00a0\u00a0\u00a0\u00a0\u00a0 Explanation<\/p>\n<p>Chromosome(string, individual)\u00a0\u00a0\u00a0 Solution (coding)<\/p>\n<p>Genes (bits)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Part of solution<\/p>\n<p>Locus\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Position of gene<\/p>\n<p>Alleles\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Values of gene<\/p>\n<p>Phenotype Decoded solution<\/p>\n<p>Genotype\u00a0\u00a0 Encoded solution<\/p>\n<p>The Canonical Genetic Algorithm<\/p>\n<h3><\/h3>\n<h3><span class=\"ez-toc-section\" id=\"concepts\"><\/span>Concepts<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>Genetic Algorithms are search algorithms that are based on concepts of natural selection and natural genetics.Genetic algorithm was developed to simulate some of the processes observed in natural evolution, a process that operates on chromosomes (organic devices for encoding the structure of living being). The genetic algorithm differs from other search methods in that it searches among a population of points, and works with a coding of parameter set, rather than the parameter values themselves. It also uses objective function information without any gradient information. The transition scheme of the genetic algorithm is probabilistic, whereas traditional methods use gradient information.Because of these features of genetic algorithm, they are used as general purpose optimization algorithm. They also provide means to search irregular space and hence are applied to a variety of function optimization, parameter estimation and machine learning applications.<\/p>\n<h3><span class=\"ez-toc-section\" id=\"basic-principle\"><\/span>Basic Principle<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>The working principle of a canonical GA is illustrated in Fig. 1. The major steps involved are the generation of a population of solutions, finding the objective function and fitness function and the application of genetic operators. These aspects are described briefly below. They are described in detail in the following subsection.<\/p>\n<p>&nbsp;<\/p>\n<p><img class=\"alignnone size-medium wp-image-29180\" alt=\"1\" src=\"http:\/\/www.kopykitab.com\/blog\/wp-content\/uploads\/2013\/05\/151-300x206.jpg\" width=\"300\" height=\"206\" srcset=\"https:\/\/www.kopykitab.com\/blog\/wp-content\/uploads\/2013\/05\/151-300x206.jpg 300w, https:\/\/www.kopykitab.com\/blog\/wp-content\/uploads\/2013\/05\/151-30x21.jpg 30w, https:\/\/www.kopykitab.com\/blog\/wp-content\/uploads\/2013\/05\/151.jpg 634w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>n important characteristic of genetic algorithm is the coding of variables that describes the problem. The most common coding method is to transform the variables to a binary string or vector; GAs perform best when solution vectors are binary.If the problem has more than one variable, a multi-variable coding is constructed by concatenating as many single variables coding as the number of variables in the problem. Genetic Algorithm processes a number of solutions simultaneously. Hence, in the first step a population having P individuals is generated by pseudo random generators whose individuals represent a feasible solution. This is a representation of solution vector in a solution space and is called initial solution. This ensures the search to be robust and unbiased, as it starts from wide range of points in the solution space.<\/p>\n<p>In the next step, individual members of the population are evaluated to find the objective function value. In this step, the exterior penalty function method is utilized to transform a constrained optimization problem to an unconstrained one. This is exclusively problem specific. In the third step, the objective function is mapped into a fitness function that computes a fitness value for each member of the population. This is followed by the application of GA operators.<\/p>\n<p><b>Working Principle<\/b><b><\/b><\/p>\n<p>To illustrate the working principles of GAs, an unconstrained optimization problem is considered. Let us consider following maximization problem,<\/p>\n<p>where,\u00a0\u00a0and\u00a0\u00a0are the lower and upper bound the variable\u00a0\u00a0can take. Although a maximization problem is considered here, a maximization problem can also be handled using GAs. The working of GAs is completed by performing the following tasks.<\/p>\n<p><b><br \/>\nCoding<\/b><\/p>\n<p>In order to use GAs to solve the above problem (equation 1), variables\u00a0&#8216;s are first coded in some string structures. It is important to mention here that the coding of the variables is not absolutely necessary. There exist some studies where GAs are directly used on the variables themselves, but here these exceptions are ignored and the working principles of a simple genetic algorithm is discussed.<\/p>\n<div style=\"text-align: left;\" align=\"center\"><img class=\"alignnone size-medium wp-image-29181\" alt=\"2\" src=\"http:\/\/www.kopykitab.com\/blog\/wp-content\/uploads\/2013\/05\/233-300x131.jpg\" width=\"300\" height=\"131\" srcset=\"https:\/\/www.kopykitab.com\/blog\/wp-content\/uploads\/2013\/05\/233-300x131.jpg 300w, https:\/\/www.kopykitab.com\/blog\/wp-content\/uploads\/2013\/05\/233-30x13.jpg 30w, https:\/\/www.kopykitab.com\/blog\/wp-content\/uploads\/2013\/05\/233.jpg 527w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Genetic Algorithm Fundamentals Basic Concepts Notes Introduction Genetic Algorithms are a family of computational models inspired by evolution. These algorithms encode a potential solution to a specific problem on a simple chromosome-like data structure and apply recombination operators to these structures as as to preserve critical information. Genetic algorithms are often viewed as function optimizer, &#8230; <a title=\"Genetic Algorithm Fundamentals Basic Concepts Notes\" class=\"read-more\" href=\"https:\/\/www.kopykitab.com\/blog\/genetic-algorithm-fundamentals-basic-concepts-notes\/\" aria-label=\"More on Genetic Algorithm Fundamentals Basic Concepts Notes\">Read more<\/a><\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":""},"categories":[4773],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/posts\/29179"}],"collection":[{"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/comments?post=29179"}],"version-history":[{"count":0,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/posts\/29179\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/media?parent=29179"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/categories?post=29179"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/tags?post=29179"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}