Genetic algorithm: struggling with premature convergence
In the previous essay ( Choosing a population size for a genetic algorithm ) the minimum population size necessary for the efficiency of a genetic algorithm was determined:
N = 1 + LOG2 (1 / (1-P1 ^ (1 / L))), where
P1 - the required probability that a random set of chromosomes will contain all the necessary elements for each locus;
L is the length of the chromosome.
In reality, this population size will be necessary, but not sufficient for the efficient operation of the genetic algorithm.
This happens because of premature convergence - stopping the algorithm before reaching a global maximum (and often even reaching local maximums).
The reason for this lies in the very nature of the algorithm: the higher the chromosome's fitness, the more likely it is to take part in the crossing. Accordingly, the more times she will be able to take part in the crossing.
Thus, the genetic code of chromosomes, the fitness function of which significantly exceeds the average value for a population, gaining an advantage, displaces other sets of the genetic code from the population.
But if the adaptability of such chromosomes is significantly less than the global maximum of the fitness function (and this is natural for the initial stages), and the size of the population is not sufficient to maintain diversity, then premature convergence to values ​​far from optimal (or, at best, convergence to local maximums) guaranteed.
Since even if a chromosome with much greater fitness appears in further generations of the population, then by this time the previous leaders will have time to multiply strongly and there is a possibility that the new leader will simply be “squeezed out” of the population before it will “gain a foothold” .
')
Itself suggests an extensive way to combat this phenomenon - an increase in population size, but to find an intensive (not resource-intensive) way is much more interesting.
Immediately it should be noted that the probability of whether a local or global maximum of the fitness function will be reached strongly depends on its type.
Here is an example of the areas of local maxima of the fitness function of the problem considered below:
As an example, a traveling salesman-like problem is solved, the chromosome length is L = 25
- along the horizontal axis, all possible chromosome values ​​plotted in the decimal coordinate system (for example, chromosome 1010010101111111110001010 corresponds to x = 21692298);
- the vertical axis represents the values ​​of the fitness function.
(apparently, local maxima are quite strongly separated from each other - in this problem all the prerequisites for premature convergence are observed).
So, the initial set of chromosomes is strongly dispersed both by the genetic code and by the values ​​of fitness.
Then, as a result of the work of the genetic crossing operator, the possible combinations are searched. The selection mechanism for fitness is applied to these combinations: sets with greater fitness are more likely to participate in crossing. As a result, sets of successive generations begin to cluster around areas of highs.
But with a significant probability it may turn out that the descendants formed as a result of the crossing of chromosomes containing genetic material from the region located in the vicinity of the global maximum with the chromosomes from other regions will turn out to be less adapted and will be ousted.
Accordingly, their genetic material will be lost to the population.
Thus, for the first stage of the genetic algorithm, it becomes important, while conducting a selection for fitness, at the same time to reduce the possible losses of “promising” genetic material.
As a result, maintain maximum diversity, increasing the fitness of the population as a whole.
The experience of nature will be very useful here.
The crossing operator of a classical genetic algorithm is inherently consistent with meiosis - only in a genetic algorithm, the number of descendants is equal to the number of ancestors.
But in nature, there is also another type of reproduction - mitosis and we can also adapt it for use in the genetic algorithm.
As a basic principle, we establish that chromosomes with the highest values ​​of the function of fitness reproduce by mitosis, and chromosomes with the smallest values ​​of the function of fitness reproduce by meiosis.
The closest analogy of this mechanism is the reproduction of microorganisms that can use both one and the other pathways of reproduction. It is advantageous for microorganisms most adapted to the environment to launch their replication as quickly as possible in an unchanged form, for the least adapted it is advantageous to launch recombination of genetic material to search for variants with greater adaptability.
Each chromosome to which the mitosis operator is applied, deliberately produces at least one completely identical descendant itself.
In addition, the more the chromosome's fitness exceeds the average value of fitness over the entire population, the greater the likelihood that the chromosome will produce a second descendant.
With less adaptability, chromosomes form a pool for interbreeding. Pairwise crossing of chromosomes from the pool is carried out until the required total population size is reached (taking into account the chromosomes already created using the mitosis operator). The choice of chromosomes for crossing is made randomly by the roulette method (chromosomes with greater adaptability correspond to a larger sector on the roulette wheel). The population size remains constant throughout the operation of the genetic algorithm.
At the initial stage, it is beneficial for us to slow down convergence, having achieved through the use of a mitosis operator, a growth in the fitness of a population (and reducing the variation in the parameter of fitness), while simultaneously maintaining the maximum diversity of genetic material in a population.
At the final stage, when there is a population of chromosomes with a high average level of fitness and with a low variation on this indicator, but there is a wide variety of genetic material in the population (this gives a good coverage of the areas of local maxima of the fitness function), then it becomes advantageous for us to use the crossing operator for the whole population.
Thus, for each generation, we assume that the proportion of chromosomes to which the mitosis operator is applied is inversely proportional to the average size of the population’s fitness and directly proportional to the standard deviation of the population’s fitness.
Linear dependence on the ratio of standard deviation to average fitness can be used to determine the proportion of a population multiplying mitosis, but the best result is achieved if you use a logarithmic relationship (for logarithmic dependence, the proportion of chromosomes that reproduce by mitosis decreases more slowly). However, for both linear and logarithmic dependencies, the population exposed to the mitosis operator tends to zero in the second half of the algorithm.
For the first generation, we choose the proportion of the population that multiplies with mitosis equal to 1/2. Accordingly, since in the first stages the size of the population undergoing crossing is also equal to 1/2 of the total number, then, in order to ensure the sufficiency condition, we choose the population size equal to 2N.
Here is the distribution of chromosomes for the standard genetic algorithm (shades of blue) and the algorithm with mitosis (shades of red-brown). Population size in both cases: 2N.
Chromosomes are divided into 5 quintiles, depending on the generation to which they belong.
Earlier generations are shown in lighter shades.
- along the horizontal axis, all possible chromosome values ​​plotted in the decimal coordinate system (for example, chromosome 1010010101111111110001010 corresponds to x = 21692298);
- the vertical axis represents the values ​​of the fitness function.
As can be seen from the graph, for the standard genetic algorithm, already at the early stages, grouping around regions of local maxima is typical (including in the area of ​​the global maximum), then chromosome concentration around one region randomly occurs and genetic material from other regions is displaced .
At the same time, the algorithm with mitosis in the early stages is characterized by a large distribution of chromosomes throughout the region (with comparable fitness values), at later stages there is a systematic drift towards the region of the global maximum.
On this graph, you can compare the efficiency of the genetic algorithm with the use of both meiosis and mitosis (red graph) compared to the standard genetic algorithm (blue graph):
- on the horizontal axis, the population size values ​​are plotted, where 1 is the population size equal to N (the minimum required population size);
- the vertical axis represents the average values ​​of the fitness function of chromosomes obtained as a result of the genetic algorithm, where 1 is the value of the fitness function equal to the global maximum.
It is clearly seen that the use of the operator of mitosis, can significantly increase the effectiveness of the genetic algorithm.
So, the algorithm with mitosis for a population of 2N in size (for the calculated example N = 20) gives an average result of 0.9694 from the maximum possible. To achieve the same values ​​when applying the standard genetic algorithm will require a population of size 7N.
To achieve a result of 0.98 from the maximum algorithm with mitosis, a population of 3N will be required, and a standard algorithm will require a population of 11N
PS> when there is a little more time, I will lay out in the next article a more detailed analysis of the results - with a large number of cuts - which will allow us to come closer to assessing what the size of the population is optimal.
Update: thanks for the questions and interesting comments - I can only answer in the evening (unfortunately during the day there will be no possibility); also do a proofreading to facilitate the perception.
N = 1 + LOG2 (1 / (1-P1 ^ (1 / L))), where
P1 - the required probability that a random set of chromosomes will contain all the necessary elements for each locus;
L is the length of the chromosome.
In reality, this population size will be necessary, but not sufficient for the efficient operation of the genetic algorithm.
This happens because of premature convergence - stopping the algorithm before reaching a global maximum (and often even reaching local maximums).
The reason for this lies in the very nature of the algorithm: the higher the chromosome's fitness, the more likely it is to take part in the crossing. Accordingly, the more times she will be able to take part in the crossing.
Thus, the genetic code of chromosomes, the fitness function of which significantly exceeds the average value for a population, gaining an advantage, displaces other sets of the genetic code from the population.
But if the adaptability of such chromosomes is significantly less than the global maximum of the fitness function (and this is natural for the initial stages), and the size of the population is not sufficient to maintain diversity, then premature convergence to values ​​far from optimal (or, at best, convergence to local maximums) guaranteed.
Since even if a chromosome with much greater fitness appears in further generations of the population, then by this time the previous leaders will have time to multiply strongly and there is a possibility that the new leader will simply be “squeezed out” of the population before it will “gain a foothold” .
')
Itself suggests an extensive way to combat this phenomenon - an increase in population size, but to find an intensive (not resource-intensive) way is much more interesting.
Immediately it should be noted that the probability of whether a local or global maximum of the fitness function will be reached strongly depends on its type.
Here is an example of the areas of local maxima of the fitness function of the problem considered below:
As an example, a traveling salesman-like problem is solved, the chromosome length is L = 25
- along the horizontal axis, all possible chromosome values ​​plotted in the decimal coordinate system (for example, chromosome 1010010101111111110001010 corresponds to x = 21692298);
- the vertical axis represents the values ​​of the fitness function.
(apparently, local maxima are quite strongly separated from each other - in this problem all the prerequisites for premature convergence are observed).
So, the initial set of chromosomes is strongly dispersed both by the genetic code and by the values ​​of fitness.
Then, as a result of the work of the genetic crossing operator, the possible combinations are searched. The selection mechanism for fitness is applied to these combinations: sets with greater fitness are more likely to participate in crossing. As a result, sets of successive generations begin to cluster around areas of highs.
But with a significant probability it may turn out that the descendants formed as a result of the crossing of chromosomes containing genetic material from the region located in the vicinity of the global maximum with the chromosomes from other regions will turn out to be less adapted and will be ousted.
Accordingly, their genetic material will be lost to the population.
Thus, for the first stage of the genetic algorithm, it becomes important, while conducting a selection for fitness, at the same time to reduce the possible losses of “promising” genetic material.
As a result, maintain maximum diversity, increasing the fitness of the population as a whole.
The experience of nature will be very useful here.
The crossing operator of a classical genetic algorithm is inherently consistent with meiosis - only in a genetic algorithm, the number of descendants is equal to the number of ancestors.
But in nature, there is also another type of reproduction - mitosis and we can also adapt it for use in the genetic algorithm.
As a basic principle, we establish that chromosomes with the highest values ​​of the function of fitness reproduce by mitosis, and chromosomes with the smallest values ​​of the function of fitness reproduce by meiosis.
The closest analogy of this mechanism is the reproduction of microorganisms that can use both one and the other pathways of reproduction. It is advantageous for microorganisms most adapted to the environment to launch their replication as quickly as possible in an unchanged form, for the least adapted it is advantageous to launch recombination of genetic material to search for variants with greater adaptability.
Each chromosome to which the mitosis operator is applied, deliberately produces at least one completely identical descendant itself.
In addition, the more the chromosome's fitness exceeds the average value of fitness over the entire population, the greater the likelihood that the chromosome will produce a second descendant.
With less adaptability, chromosomes form a pool for interbreeding. Pairwise crossing of chromosomes from the pool is carried out until the required total population size is reached (taking into account the chromosomes already created using the mitosis operator). The choice of chromosomes for crossing is made randomly by the roulette method (chromosomes with greater adaptability correspond to a larger sector on the roulette wheel). The population size remains constant throughout the operation of the genetic algorithm.
At the initial stage, it is beneficial for us to slow down convergence, having achieved through the use of a mitosis operator, a growth in the fitness of a population (and reducing the variation in the parameter of fitness), while simultaneously maintaining the maximum diversity of genetic material in a population.
At the final stage, when there is a population of chromosomes with a high average level of fitness and with a low variation on this indicator, but there is a wide variety of genetic material in the population (this gives a good coverage of the areas of local maxima of the fitness function), then it becomes advantageous for us to use the crossing operator for the whole population.
Thus, for each generation, we assume that the proportion of chromosomes to which the mitosis operator is applied is inversely proportional to the average size of the population’s fitness and directly proportional to the standard deviation of the population’s fitness.
Linear dependence on the ratio of standard deviation to average fitness can be used to determine the proportion of a population multiplying mitosis, but the best result is achieved if you use a logarithmic relationship (for logarithmic dependence, the proportion of chromosomes that reproduce by mitosis decreases more slowly). However, for both linear and logarithmic dependencies, the population exposed to the mitosis operator tends to zero in the second half of the algorithm.
For the first generation, we choose the proportion of the population that multiplies with mitosis equal to 1/2. Accordingly, since in the first stages the size of the population undergoing crossing is also equal to 1/2 of the total number, then, in order to ensure the sufficiency condition, we choose the population size equal to 2N.
Here is the distribution of chromosomes for the standard genetic algorithm (shades of blue) and the algorithm with mitosis (shades of red-brown). Population size in both cases: 2N.
Chromosomes are divided into 5 quintiles, depending on the generation to which they belong.
Earlier generations are shown in lighter shades.
- along the horizontal axis, all possible chromosome values ​​plotted in the decimal coordinate system (for example, chromosome 1010010101111111110001010 corresponds to x = 21692298);
- the vertical axis represents the values ​​of the fitness function.
As can be seen from the graph, for the standard genetic algorithm, already at the early stages, grouping around regions of local maxima is typical (including in the area of ​​the global maximum), then chromosome concentration around one region randomly occurs and genetic material from other regions is displaced .
At the same time, the algorithm with mitosis in the early stages is characterized by a large distribution of chromosomes throughout the region (with comparable fitness values), at later stages there is a systematic drift towards the region of the global maximum.
On this graph, you can compare the efficiency of the genetic algorithm with the use of both meiosis and mitosis (red graph) compared to the standard genetic algorithm (blue graph):
- on the horizontal axis, the population size values ​​are plotted, where 1 is the population size equal to N (the minimum required population size);
- the vertical axis represents the average values ​​of the fitness function of chromosomes obtained as a result of the genetic algorithm, where 1 is the value of the fitness function equal to the global maximum.
It is clearly seen that the use of the operator of mitosis, can significantly increase the effectiveness of the genetic algorithm.
So, the algorithm with mitosis for a population of 2N in size (for the calculated example N = 20) gives an average result of 0.9694 from the maximum possible. To achieve the same values ​​when applying the standard genetic algorithm will require a population of size 7N.
To achieve a result of 0.98 from the maximum algorithm with mitosis, a population of 3N will be required, and a standard algorithm will require a population of 11N
PS> when there is a little more time, I will lay out in the next article a more detailed analysis of the results - with a large number of cuts - which will allow us to come closer to assessing what the size of the population is optimal.
Update: thanks for the questions and interesting comments - I can only answer in the evening (unfortunately during the day there will be no possibility); also do a proofreading to facilitate the perception.
Source: https://habr.com/ru/post/122222/
All Articles