{"id":1617,"date":"2025-10-19T22:39:14","date_gmt":"2025-10-19T20:39:14","guid":{"rendered":"https:\/\/xeddixx.cluster029.hosting.ovh.net\/?page_id=1617"},"modified":"2025-10-27T10:05:34","modified_gmt":"2025-10-27T09:05:34","slug":"ga","status":"publish","type":"page","link":"https:\/\/www.francq.info\/index.php\/ga\/","title":{"rendered":"Genetic Algorithms"},"content":{"rendered":"\n

Abstract<\/h4>\n\n\n\n

Genetic Algorithms (GA) are a kind of meta-heuristics applicable to solve\u00a0optimization problems<\/a>.<\/p>\n\n\n\n

Table of Contents<\/h5>\n\n\n\n

1. Definition of Genetic Algorithms<\/a><\/p>\n\n\n\n

2. Origin of Genetic Algorithms<\/a><\/p>\n\n\n\n

3. Genetic Algorithms and other Methods<\/a><\/p>\n\n\n\n

4. The Structure of Genetic Algorithms<\/a><\/p>\n\n\n\n

5. Initial Construction and Evaluation<\/a><\/p>\n\n\n\n

6. Reproduction<\/a><\/p>\n\n\n\n

6.1. Proportional Selection<\/a><\/p>\n\n\n\n

6.2. Tournament<\/a><\/p>\n\n\n\n

7. Crossover<\/a><\/p>\n\n\n\n

8. Mutation<\/a><\/p>\n\n\n\n

9. Inversion<\/a><\/p>\n\n\n\n

10. Mutation and Inversion Frequencies<\/a><\/p>\n\n\n\n

11. Genetic Algorithms for Multiple Objective Optimization Problems<\/a><\/p>\n\n\n\n

11.1. Philosophy<\/a><\/p>\n\n\n\n

11.2. Control Strategy<\/a><\/p>\n\n\n\n

11.3. Branching on Populations<\/a><\/p>\n\n\n\n

11.4. Verification of the Best Solutions<\/a><\/p>\n\n\n\n

Section 12. Related<\/a><\/p>\n\n\n\n

References<\/a><\/p>\n\n\n\n

Notes<\/a><\/p>\n\n\n\n

1. Definition of Genetic Algorithms\u2191<\/a><\/h5>\n\n\n\n

Before studying the different elements of Genetic Algorithms (GA) introduced by\u00a0John H. Holland\u00a0[1<\/a>], it may be interesting first of all to define what GA are. GA can be defined as an exploration algorithm based on the mechanisms of natural selection and the genetic science\u00a0[2<\/a>].<\/p>\n\n\n\n

GA use the survival of the best adapted structure and an exchange of pseudo-random information to search the solution space. At each generation a new set of artificial artifacts is constructed by using parts of the best elements of the previous generation and, sometimes, by adding new characteristics. <\/p>\n\n\n\n

GA are not only based on random exploration but also use information obtained from the past to evaluate the best position to explore in the future. The population is evaluated at each generation against an\u00a0objective function<\/em>\u00a0to determine its adaptation.<\/p>\n\n\n\n

2. Origin of Genetic Algorithms\u2191<\/a><\/h5>\n\n\n\n

GA are based of the natural evolution of species as described by\u00a0Charles Darwin\u00a0[3<\/a>]: in any population, the best adapted (fitted) individuals have a greater chance of reproducing than less adapted ones; this is called\u00a0natural selection<\/em>.<\/p>\n\n\n\n

In nature, new characteristics are transmitted to offsprings by crossing two individual genes. This process is not deterministic, and some uncertainty in these characteristics is introduced. Furthermore mutations may occur as genes are passed from parents to children implying that a small modification occurs in the copy, i.e. the child will have a characteristic not present in the parents. If this mutation has a positive influence on the child, the child will be better adapted than its fellows without this mutation; this newly introduced characteristic may thus be present in the next generation as the result of natural selection. Natural selection is thus based on the fact that some characteristics in a population reflects the specifications of the strongest (best adapted) individuals and thus should lead generally speaking to a better adapted population.<\/p>\n\n\n\n

As in nature, where individuals may be represented by their chromosomes alone, GA work with a population of abstract representations of solutions called\u00a0chromosomes<\/em>. At each iteration, a\u00a0generation<\/em>, the chromosomes representing the best solutions1<\/a><\/sup>\u200a\u00a0are selected and used for a\u00a0crossover<\/em>\u00a0to produce new solutions. Their children replace the less adapted ones. By exchanging \u201cgood information\u201d between chromosomes, GA try to create new chromosomes with a better value with respect to the fitness function.<\/p>\n\n\n\n

Note that the \u201cbad\u201d genes are not taken into account by GA<\/p>\n\n\n\n

3. Genetic Algorithms and other Methods\u2191<\/a><\/h5>\n\n\n\n

They are four major differences between a GA and traditional approaches to solving optimization problems:<\/p>\n\n\n\n

    \n
  1. GA use a parameter coding rather than the parameters themselves, i.e. GA do not have to know the meaning of the parameters.<\/li>\n\n\n\n
  2. GA work on a population of solutions and not on a single one, and so explore a larger portion of the search space.<\/li>\n\n\n\n
  3. GA use a value of the function to be optimized and not another form of this function. The function does not need to have any special analytical properties.<\/li>\n\n\n\n
  4. GA use probabilistic transitions and not deterministic ones. For the same instance of a problem (same initial conditions and data), the results may be different after two different runs\u200a2<\/a><\/sup>.<\/li>\n<\/ol>\n\n\n\n
    4. The Structure of Genetic Algorithms\u2191<\/a><\/h5>\n\n\n\n

    The generic structure of a GA is shown in Figure\u00a01.<\/p>\n\n\n

    \n
    \"\"<\/figure>\n<\/div>\n\n\n

    Figure 1. Structure of a genetic algorithm.<\/p>\n\n\n\n

    The different steps are:<\/p>\n\n\n\n

      \n
    1. A population is constructed which is made up of a fixed number of solutions, known as chromosomes. Each chromosome is evaluated through a cost function describing the optimum targeted.<\/li>\n\n\n\n
    2. GA reproduce some of the statistically best chromosomes. These chromosomes replace others, statistically the worst since the size of the population has to remain static3<\/a><\/sup>\u200a.<\/li>\n\n\n\n
    3. GA construct new chromosomes by making a crossover between existing ones.<\/li>\n\n\n\n
    4. There is a level of given probability that some of the chromosomes will be affected by a\u00a0mutation<\/em>.<\/li>\n\n\n\n
    5. There is a level of given probability that some of the chromosomes will be affected by an\u00a0inversion<\/em>.<\/li>\n\n\n\n
    6. Each newly created chromosome is evaluated by means of the cost function.<\/li>\n\n\n\n
    7. GA stop if and when a final condition is reached that indicates that an acceptable solution exists; otherwise GA make a new generation by repeating step 2.<\/li>\n<\/ol>\n\n\n\n

      All modern GA hold a separate copy of the best chromosome ever computed so as to avoid its accidental destruction when it forms part of the population.<\/p>\n\n\n\n

      Both the operators and the encoding scheme are equally important.\u00a0<\/p>\n\n\n\n

      The remainder of this article is devoted to a brief introduction to each operator. To illustrate each of them, a well-known example will be developed progressively to help the reader to master the concepts : the optimization of the function\u00a0\\(\u00a0f(x)=x^2\\)<\/mathml>, where\u00a0x\u00a0is a coded number using five bits (\\(\u00a0x\u2208[0,31]\\)<\/mathml>, with each bit\u00a0{0,1}\u00a0representing a gene of the chromosome\u00a0[2<\/a>]. In this particular case the function,\u00a0\\(f(x)\\), can, of course, be used as a cost function which is maximum for the number 31, i.e. when all the bits coding the chromosome are set to 1. For the example, the size of population is fixed as 4.<\/p>\n\n\n\n

      Remark:<\/strong>\u00a0The reader should note that the operators have to be chosen so that they reach the optimal solution, i.e. the operators described in the next sections cannot be used to solve every optimization problem.<\/p>\n\n\n\n

      5. Initial Construction and Evaluation\u2191<\/a><\/h5>\n\n\n\n

      The first step is to construct and evaluate an initial population. The easiest way to construct this population is to randomly create the different chromosomes. But, when the initial population is of poor quality, GA need many more generations to reach the end condition. The initialization is therefore a crucial step in GA. In general, problem-dependent heuristics are used to initialize these solutions.<\/p>\n\n\n\n

      For our example, random initialization is acceptable. Table\u00a01\u00a0shows the initial population and the value of the cost function for each chromosome.<\/p>\n\n\n\n

      Chromosome<\/td>Coding<\/td>\\(x\\)<\/td>\\(f(x)=x^2\\)<\/td>ranking<\/td><\/tr>
      \\(C_1\\)<\/td>01101<\/td>13<\/td>169<\/td>3<\/td><\/tr>
      \\(C_2\\)<\/td>11000<\/td>24<\/td>576<\/td>1<\/td><\/tr>
      \\(C_3\\)<\/td>01000<\/td>8<\/td>64<\/td>4<\/td><\/tr>
      \\(C_4\\)<\/td>10011<\/td>19<\/td>361<\/td>2<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

      Table 1. Initial Population for\u00a0\\(f(x)=x^2\\).<\/p>\n\n\n\n

      6. Reproduction\u2191<\/a><\/h5>\n\n\n\n

      Historically, the reproduction step is the re-creation of a simple copy of a set of selected chromosomes that will replace a set of other selected chromosomes. In fact, no modern GA does the reproduction step by really copying chromosomes. Moreover, the role of reproduction is to select the way in which the different chromosomes will be treated by the crossover.\u00a0<\/p>\n\n\n\n

      Different methods exist for the construction of these sets, but only two of them will be dealt with here: the\u00a0proportional selection<\/em>\u00a0and\u00a0the tournament<\/em>.<\/p>\n\n\n\n

      6.1. Proportional Selection\u2191<\/a><\/h6>\n\n\n\n

      Proportional selection is based on the idea that an individual who is twice as good as another should have double the chance of being reproduced\u00a0[1<\/a>]. This selection is usually implemented using the \u201croulette wheel\u201d strategy. The wheel is divided into\u00a0\\(n\\)\u00a0sections,\u00a0n\u00a0being the number of chromosomes. Each section is labeled from\u00a01\u00a0through\u00a0\\(n\\), and has an arc length directly proportional to the fitness value of the corresponding individual. This is demonstrated in Figure\u00a02\u00a0for a population of\u00a04\u00a0chromosomes.<\/p>\n\n\n

      \n
      \"\"<\/figure>\n<\/div>\n\n\n

      Figure 2. \u201cRoulette wheel\u201d strategy.<\/p>\n\n\n\n

      A ball is run around the wheel and will stop at a random point, so determining the section selected. When this method is applied\u00a0t\u00a0times, this method selects\u00a0t\u00a0individuals that will be used as parents in the crossover. The individuals with high fitness values will naturally have more chance of being selected, and those with low fitness values have more chance of disappear in the next generation. The chromosomes selected are then randomly regrouped to form\u00a0\\(t\/2\\)\u00a0pairs, which are used as the parents for the crossovers. The number,\u00a0\\(t\\), of chromosomes to be selected for the crossover can be obtained by the crossover probability. For example, in a population of 10 chromosomes and a crossover probability of 0.6, 6 chromosomes will be selected as parents.<\/p>\n\n\n\n

      Let us apply proportional selection to our example (Table\u00a02). The length of the arc for each chromosome is computed with\u00a0\\(f(x)\/\\sum f(x)\\). By multiplying this length by the size of the population, it is possible to compute the number of copies expected for each chromosome.<\/p>\n\n\n\n

      Chromosome<\/td>\\(f(x)=x^2\\)<\/td>\\(f(x)\/\\sum f(x)\\)<\/td>\\(4\\cdot\\frac{f(x)}{\\sum f(x)}\\)<\/td>Copies<\/td><\/tr>
      \\(C_1\\)<\/td>169<\/td>0.1444<\/td>0.5776<\/td>1<\/td><\/tr>
      \\(C_2\\)<\/td>576<\/td>0.4923<\/td>1.9692<\/td>2<\/td><\/tr>
      \\(C_3\\)<\/td>64<\/td>0.0547<\/td>0.2188<\/td>0<\/td><\/tr>
      \\(C_4\\)<\/td>361<\/td>0.3085<\/td>1.234<\/td>1<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

      Table 2. Proportional selection using the example.<\/p>\n\n\n\n

      As expected, the result of the selection is that the chromosome with the highest cost value function is copied twice while the chromosome with the lowest cost value function is not copied at all. So, after the proportional selection, there are\u00a02\u00a0copies of the chromosome stored in\u00a0\\(C_2\\)\u00a0and no copy of the chromosome which was stored in\u00a0\\(C_3\\). This means that a copy of the chromosome stored in\u00a0\\(C_2\\)\u00a0is stored in\u00a0\\(C_3\\), i.e. at this stage chromosomes stored in\u00a0\\(C_2\\)\u00a0and\u00a0\\(C_3\\)\u00a0are identical. The two pairs forming the parents for the potential random crossovers are\u00a0\\((C_1,C_2)\\)\u00a0and\u00a0\\((C_3,C_4)\\).<\/p>\n\n\n\n

      A disadvantage of this method is the fact that there are no guarantees that the best individual will be reproduced because proportional selection uses a probabilistic approach. Also, if the best chromosome ever computed is stored outside the population, it will not change the problem for the best chromosome in the population, which may be different from the best ever computed. The advantage is that the best solution is not always the parent of a global optimum, but sometimes of a local one. This strategy enables the local optimum to be overcome.<\/p>\n\n\n\n

      6.2. Tournament\u2191<\/a><\/h6>\n\n\n\n

      The tournament strategy is illustrated in Figure\u00a03. The idea is to create an ordered list of the individuals with the best solution always at the top, and the others ordered according to a specific method described below\u00a0[4<\/a>]. The upper part of the list will further be used when \u201cgood\u201d chromosomes are needed, while the lower part for \u201cbad\u201d chromosomes.<\/p>\n\n\n

      \n
      \"\"<\/figure>\n<\/div>\n\n\n

      Figure 3. Tournament selection.<\/p>\n\n\n\n

      An initial set of all the individual identifiers is established. Two identifiers of this set are chosen randomly (step\u00a01), and their fitness values are compared (step\u00a02). The best of the two \u2014 the one corresponding to the individual with the best fitness value \u2014 is reinserted into the set, while the other is pushed into the list (step\u00a03). This method is repeated until all the identifiers in the set are in the list; this process leads to the construction of an ordered list of individuals, with the best one at the top of the list. The operator can then presume that the chromosomes ranked in the top half will be used as parents for the crossovers and the resulting children will replace the chromosomes in the bottom half.<\/p>\n\n\n\n

      Let us apply this strategy to the example in Table 3. Initially, the set contains all the chromosomes of the population and the list is empty.<\/p>\n\n\n\n

      Set<\/td>Test<\/td>Put in the list<\/td>List<\/td><\/tr>
      \\({C_1,C_2,C_3,C_4}\\)<\/td><\/td><\/td>\\(\u2205\\)<\/td><\/tr>
      \\({C_2,C_3,C_4}\\)<\/td>\\((C_1,C_4)\\)<\/td>\\(C_1\\)<\/td>\\({C_1}\\)<\/td><\/tr>
      \\({C_2,C_4}\\)<\/td>\\((C_2,C_3)\\)<\/td>\\(C_3\\)<\/td>\\({C_1,C_3}\\)<\/td><\/tr>
      \\({C_2}\\)<\/td>\\((C_2,C_4)\\)<\/td>\\(C_4\\)<\/td>\\({C_1,C_3,C_4}\\)<\/td><\/tr>
      \\((C_1,C_4)\\)<\/td><\/td>\\(C_2\\)<\/td>\\({C_1,C_3,C_4,C_2}\\)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

      Table 3. An example of a tournament.<\/p>\n\n\n\n

      The first two randomly compared chromosomes are\u00a0\\(C_1\\)\u00a0and\u00a0\\(C_4\\). Chromosome\u00a0\\(C_4\\)\u00a0has a better fitness value than\u00a0\\(C_1\\), so\u00a0\\(C_1\\)\u00a0goes in the list while\u00a0\\(C4\\)\u00a0goes back into the set. The next two randomly compared chromosomes are\u00a0\\(C_2\\)\u00a0and\u00a0\\(C_3\\). Because\u00a0\\(C_3\\)\u00a0has the lower fitness value it goes into the list and\u00a0\\(C_2\\)\u00a0stays in the set. Finally, the chromosomes are ordered as\u00a0\\({C_1,C_3,C_4,C_2}\\), where the last inserted chromosomes represents the best individual. The parents chosen for the crossovers are\u00a0\\(C_4\\) and\u00a0\\(C_2\\), and chromosomes\u00a0\\(C_1\\)\u00a0and\u00a0\\(C_3\\)\u00a0will contain the results of these crossovers.\u00a0<\/p>\n\n\n\n

      In comparison with proportional selection, with the tournament strategy:<\/p>\n\n\n\n

        \n
      1. The chromosomes are not copied but just ordered, i.e. there is always only one copy of each chromosome. In fact, for well-designed operators the population must be as diversified as possible.\u00a0<\/li>\n\n\n\n
      2. The last inserted chromosome in the list is the best chromosome of the population, i.e. in comparison with proportional selection the best individual is always reproduced.<\/li>\n<\/ol>\n\n\n\n
        7. Crossover\u2191<\/a><\/h5>\n\n\n\n

        The role of a crossover operator is to create new chromosomes in the population by using characteristics of parent chromosomes. If the crossover operator copies interesting characteristics, the corresponding new chromosomes should enjoy a better potential of adaptation, i.e. their fitness values should increase. The basic idea is that information, known as\u00a0genes<\/em>, is exchanged between two selected chromosomes to create two new chromosomes. An example of such an exchange is shown in Figure\u00a04. A position called the\u00a0crossing site<\/em>\u00a0is selected randomly from the string. The new chromosomes are constructed by mixing the left- and the right-hand sides of each parent\u2019s crossing site.<\/p>\n\n\n

        \n
        \"\"<\/figure>\n<\/div>\n\n\n

        Figure 4. A simple crossover.<\/p>\n\n\n\n

        Let us apply this crossover operator to our example by choosing as parents the result of the tournament where the randomly selected crossing site is\u00a02\u00a0(Table\u00a04).<\/p>\n\n\n\n

        Parent<\/td>Children<\/td>Chromosome Replaced<\/td>\\(x\\)<\/td>\\(f(x)=x^2\\)<\/td><\/tr>
        11\u2223000<\/td>11011<\/td>\\(C_1\\)<\/td>27<\/td>729<\/td><\/tr>
        10\u2223011<\/td>10000<\/td>\\(C_3\\)<\/td>1<\/td>1<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

        Table 4. Crossover on the example.<\/p>\n\n\n\n

        The result of the crossover shows that the newly created chromosome,\u00a0\\(C_1\\), has a better fitness value than the parents. In the example, chromosome\u00a0\\(C_3\\)\u00a0however has a very low fitness value and will probably be destroyed during the next reproduction step.<\/p>\n\n\n\n

        8. Mutation\u2191<\/a><\/h5>\n\n\n\n

        If the crossover was the only existing operator, it would be impossible for GA to scan the whole search space. Indeed, if we assume that, in the initial population in our example no chromosomes has the third bit set to\u00a01, the best solution for the problem \u2014 corresponding to a chromosome with all the bits set to 1 \u2014 would never be found. The role of the mutation operator is to randomly insert new characteristics in the population to diversify it. An example of a mutation is shown in Figure\u00a05, where a gene is randomly chosen and modified.<\/p>\n\n\n

        \n
        \"\"<\/figure>\n<\/div>\n\n\n

        Figure 5. A simple mutation.<\/p>\n\n\n\n

        In our example, this modification could consist in transforming a bit from 1 to 0 or from 0 to 1. If chromosome\u00a0\\(C_1\\)\u00a0in our example is chosen and the randomly selected bit is the third,\u00a0\\(C_1\\)\u00a0will be modified as\u00a011111, and the best solution to the problem will have been found (Table\u00a05).<\/p>\n\n\n\n

        Before Mutation<\/td>After Mutation<\/td>\\(x\\)<\/td>\\(f(x)=x^2\\)<\/td><\/tr>
        11\u22230\u222311<\/td>11111<\/td>32<\/td>1024<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

        Table 5. Mutation on the example.<\/p>\n\n\n\n

        Even if the interest of such an operator is clear in certain cases, the probability that a mutation occurs is very low because too many mutations would destroy the effects of the reproduction and the crossover. So it is necessary to adopt a method to choose the chromosome and, eventually, the gene on which the mutation must be carried out. Section\u00a010<\/a>\u00a0discusses some strategies that can be used.<\/p>\n\n\n\n

        9. Inversion\u2191<\/a><\/h5>\n\n\n\n

        The crossover and the mutation operators affect the information contained in the chromosomes. The inversion operator does not change the information, but will change its presentation. Again, to understand this point, it is important to know that the position of a given gene in a chromosome has an influence on whether this gene will, or will not, be used by the different operators. For example, in the basic crossover presented at Figure\u00a04, a gene which is in the middle of a chromosome has more chance of being involved in a crossover than the first or last gene. It is therefore sometimes interesting to change the way information is presented. Figure\u00a06\u00a0shows a simple inversion operator if it is assumed that the value of the corresponding fitness function is not changed: two genes have been randomly chosen, here\u00a0D<\/em>\u00a0and\u00a0E<\/em>, and their information exchanged.<\/p>\n\n\n

        \n
        \"\"<\/figure>\n<\/div>\n\n\n

        Figure 6. A simple inversion.<\/p>\n\n\n\n

        The pertinence of this operator strongly depends on the problem studied because an operator may not affect the information contained in a chromosome. This means that this operator is not always applied in real situations. In our example, the inversion of two bits in the chromosome will automatically change the number represented if the two bits are set to different values. In the\u00a0Grouping Genetic Algorithms (GGA), the inversion operator is applied.<\/p>\n\n\n\n

        10. Mutation and Inversion Frequencies\u2191<\/a><\/h5>\n\n\n\n

        The mutation and inversion operators must not be used in each generation and on each chromosome. It is therefore necessary to develop a method to choose when and where to apply these operators.<\/p>\n\n\n\n

        A first strategy widely used in GA is to assign to each operator a probability,\u00a0pcross\u00a0and\u00a0pinv; values of 0.0333 are often found in the literature. In each generation, each chromosome has a probability of\u00a0pcross\u00a0and\u00a0pinv\u00a0of being chosen for a mutation or an inversion.<\/p>\n\n\n\n

        Another strategy is to apply such operators only when it \u201cseems necessary\u201d. Because the mutation is used to insert diversity into the population and the inversion to facilitate the work of the other operators, these operators are needed when GA seem to be stagnating. Two situations can indicate that GA do not longer evolute:<\/p>\n\n\n\n