Mathematical modeling analysis of genetic algorithms under schema theorem

Abstract

Genetic algorithm (GA) is a search algorithm for solving optimization problems and is an important part of evolutionary algorithms (EA). The main purpose of this research is to improve the mathematical modeling of GA, and to explore how to overcome the shortcomings of traditional algorithms under the Schema Theorem. The research results show that the improved GA can be more widely applied to the optimization problems and play an important role in solving practical problems.

Keywords

Genetic algorithm schema theorem mathematical modeling

1. Introduction

Genetic Algorithm (GA) is a computational model simulating the natural selection of Darwinian evolution and the biological evolution process of Genetic mechanism. It is a method to search for the optimal solution by simulating the natural evolution process. Its main characteristic is to operate directly on the structural object, and there is no limit of derivation and continuity of function. It has inherent implicit parallelism and better global optimization ability. By using probabilistic optimization method, the optimized search space can be acquired and guided automatically without definite rules, and the search direction can be adjusted adaptively. Genetic algorithm takes all individuals in a population as the object, and USES the randomization technique to search a encoded parameter space efficiently. Among them, selection, crossover and mutation constitute the genetic operation of genetic algorithm. Parameter coding, initial population setting, fitness function design, genetic operation design and control parameter setting constitute the core content of genetic algorithm.

The Schema Theorem is the basic theorem of GA. The principle is that a schema of lower order and has an average fitness higher than the population will also reflect deterministic differences under different schemas, for phenomenon such as prematurity that may occur in GA, mathematical modeling is required to make the algorithm more efficient.

Therefore, this paper will also conduct analysis in genetic operations, under the schema of same order, it analyzes the different forms, explains the mechanism of GA more effectively, so as to provide a mathematical basis for future researches.

2. Literature review

Li and Gao weakened the conditions needed by the schema theory of genetic algorithm, which made the schema theory further generalized. By studying the deception function of genetic algorithm, the conditions of building module assumption were determined. When it could be correctly recognized that a function was a deceptive function, the corresponding conditions of building block hypothesis could be obtained [1]. Bharathi et al. deduced another equivalent form of the model theorem by using more accurate expression of the average fitness of the population based on a single model of the population, which was verified by simulation experiments [2]. In the application of genetic algorithm, it is not difficult to find that genetic algorithm has a large number of random operations, which shows that genetic algorithm is a random search algorithm. In order to characterize the limit form of genetic algorithm, different Markov chain models have been used by scholars all over the world. Zhu et al. put forward the theory that the population sequence of genetic algorithm conformed to Markov chains could be used as a finite Markov chains to discuss. Some properties of transition probability matrix of finite Markov chains were used to study the convergence of genetic algorithm [3]. In the subsequent research work, French scholar Cerf regarded genetic algorithm as a special model of generalized simulated annealing algorithm on the basis of a series of previous studies on simulated annealing and generalized simulated annealing. Based on this understanding, further research was carried out [4]. In the Vose model, the state of the population is defined as a probability vector, whose length represents the population size. For example, the $i$ -th component represents the proportion of the i-th individual in the population. It is assumed that the population size tends to infinity, and the probability of each individual appearing in the population can be approximately replaced by using the ratio or frequency of the population [5]. The above three models have their advantages and disadvantages. The description of population Markov chain model is the simplest, intuitive and easy to understand, and the interpretation ability of genetic algorithm is the strongest. However, due to some defects in the interpretation of the transition probability of Markov chain, the characteristics of genetic algorithm are not integrated into the study of the model. Kalayci et al. thought that there was no essential difference between the ideological basis of the model construction and the random search method, resulting in the final proof was basically the same [6]. The further development of Vose model is hopeful to apply stochastic analysis method to the study of genetic algorithm, which is also an important direction to overcome. Cerf perturbed Markov chain model can obtain the most comprehensive convergence proof of genetic algorithm, but its assumptions are too harsh. Cerda et al. used genetic algorithm as a multi-level Markov chain to establish a strict mathematical model, and deduced the convergence results [7]. The premature convergence of genetic algorithm is a phenomenon that occurs in almost all group-based search methods in multi-mode search optimization. Multi-modal search refers to several local optima (or “peaks”) that may be understood as “gravitational centers” in search dynamics, i.e. the overall progress across iterations can point to one or more local optima, gradually making the solutions more similar and this process is called “diversity loss”. Consequently, maintaining diversity is the key to avoid premature convergence. Failure to increase and maintain diversity at population level is closely related to premature convergence. This premature phenomenon greatly limits the application of genetic algorithm. Yang et al. deeply explored the principle of population diversity reduction based on the understanding of crossover and mutation to maintain population diversity. They attributed the decline of diversity to the ripening effect of crossover operation, and put forward targeted preventive measures [8]. In Ramadan’s paper, frequency crossover strategy (FC) and nine different mutation strategies were applied to practice the idea of diversity preservation, and to travel salesman problem (TSP) to reduce the impact of premature convergence. Three sets of benchmark data were also used to test the effectiveness of the genetic algorithm [9]. Operator design of genetic algorithms, apart from those common ones, there are also some common ones in daily applications, such as deletion, dominance, inversion and so on. Up to now, the main types of selection operators are: reserving optimal individuals, uniform sorting, random sampling, steady-state replication, etc. Ghareb and Bakar discussed various crossover operators, and used evolutionary genetic algorithm to solve scheduling problems [10, 11].

In summary, the above research mainly discusses the establishment condition of genetic algorithm, mode comparison and the analysis of advantages and disadvantages among different modes. The local interference of multi-mode search on diversity when genetic algorithm converged too early is analysed, the measures to reduce diversity are put forward, and the scheduling problem is discussed. However, there are few researches on how to overcome the shortcomings of traditional algorithm under schema theorem. Based on the above research status, in the analysis of the genetic operation, in the same order mode, how to analyse its different forms, more effectively explain the mechanism of genetic algorithm, and provide a mathematical basis for future research is discussed.

3. Method

3.1 GA modeling and optimization

The optimization problem is a relatively new branch of mathematics. Due to the wide application of electronic computers, the optimization problem has rapidly developed in the early 1950s, making it a subject that is still very active until now. The optimization problem has a wide range of applications, such as structural optimal design, chemical engineering optimal design, electronic device optimal design, transportation scheme design, oilfield development program, etc., which are widely used in social and economic construction, as well as industrial and agricultural production. According to the principle of survival of the fittest, evolutionary generation produces better and better approximate solutions. In each generation, individuals are selected according to the size of individual fitness in the problem domain, crossover and mutation are conducted by means of genetic operators of natural genetics, resulting in populations representing new sets of solutions. This process will result in the population of the offspring being more adapted to the environment than the previous generation, like natural evolution. After decoding, the optimal individual in the last population can be used as the approximate optimal solution to the problem. The operation flow of the traditional GA is shown in Fig. 1.

Figure 1.

Flow of traditional GA.

GA dynamically adjusts the search process by using the crossover probability and the mutation probability, so that the solution approximates the optimal solution. What is GA dealing with is not the parameter itself, but the encoded gene individual, so GA can directly manipulate some structural objects, which makes the application of GA more extensive. GA can process multiple individuals, that is, it can evaluate multiple solutions. This avoids traditional algorithms from falling into local extreme points when searching for multi-peak distribution search space. Therefore, GA has higher global search ability.

3.2 Improvement under schema theorem

The crossover operator is the most important component of the genetic operators. It not only plays a crucial role in the convergence of the genetic operator, but also has a great influence on the convergence speed of GA. The operation of the traditional crossover operator is often blind. The offspring generation formed by the cross-interchange of the parental chromosomes is likely to discard or destroy the excellent genetic schemas possessed by the parental individuals. The standard intersection formula is shown in Eq. (1).

$\displaystyle\text{K}=\left({\text{G}+2\sqrt{g}}\right)/3\text{G}$ (1)

Where G is the total number of evolutionary generations pre-set by this population, and $g$ is the number of generations of the algorithm has run so far. From the formula, it’s obvious that the value of the standard intersection K is dynamically changing, and its value increases with the number of evolutionary generations of current population, and the pre-set number of evolutionary generations also has a large influence on the change of the standard intersection K. In the early stage of GA operation, the coding similarity between randomly generated population individuals is lower. In order to control the crossover probability, the K value should be relatively small in order to ensure that the population is fully evolved without destroying the excellent genetic schema in individuals. On the contrary, in the later stage of GA operation, the difference between individuals is smaller, and the coding similarity is higher, so the value K of the standard intersection should also be increased. Therefore, dynamic control of the value of standard intersection is especially important.

3.3 Model construction of a new GA

Generally, for population initialization, GA is completely random. The randomness of the initial population tends to make each individual unevenly distributed in the solution space, so it is easy to lead to unbalanced evolution results in the iterative process, and finally lead to local optimal solutions. To overcome this problem, we use a new method to evenly distribute the initial individuals in the solution space. The specific scheme is shown in Fig. 2.

Figure 2.

Population initialization schemas.

According to the Schema Theorem, the essence of GA should be to replace the original schema and form an excellent schema. In the operation of GA, the new schema should keep the early population evolution schema as much as possible so as to maintain the diversity of the population. In the later stages of population evolution, appropriate schemas should be maintained so as to prevent damages, thereby reducing the possibility of prematurity. Formula of the evolutionary algorithm is shown in Eq. (2).

$\displaystyle{x}=\left[{\left({1-\frac{\textit{gen}}{\textit{gen}_{\textit{max% }}}}\right)\cdot\frac{\pi}{2}}\right]$ (2)

Individuals with high fitness are likely to have excellent schemas, so they can better adapt to the relatively small crossover and mutation probabilities in the evolutionary process. Conversely, individuals with low fitness not only do not contain good schemas, but when they intersect with individuals with good schemas, they may instead destroy good schemas. Therefore, individuals with low fitness are more suitable for smaller crossover probabilities. Therefore, it is possible to increase the probabilities of crossover and mutation among individuals whose fitness level is close to the average to explore potential good schemas. In the formula, gen represents the current evolutionary generation, and max means the maximum evolutionary generation.

3.4 Improvement of crossover operation

The crossover operator has a great influence on the convergence effect of GA. However, traditional crossover operation tends to be blind. Offspring individuals are formed by crossover of male parent and female parent discarding or self-destructing some of the excellent genetic schemas present in their own chromosomes. Therefore, in addition to studying the adjustable crossover and mutation probabilities, a crossover strategy has been proposed based on recent studies. As a result, the excellent genetic schemas existing in the male parent and female parent should be protected as much as possible so that they can be continued in future generations. Its definition is shown in Fig. 3.

Figure 3.

Crossover strategy description.

4. Results and analysis

According to the crossover operation definition schema shown in Fig. 4.

Figure 4.

Crossover operation definition methods.

The coding similarity between individuals is quite small in the early stage of SCAGA. So, in order to ensure that significant genetic schemas are not destroyed by the evolution of the genome, the scp value used to control the crossover operation should be quite small. On the contrary, in the later stage of SCAGA, the difference between individuals is small, but the value of scp will increase. According to the formula, dynamic control of standard intersection can improve the convergence and convergence speed of the algorithm. The Schema Theorem is an effective method for analyzing GA. It has a good effect in predicting the growth rate in the algorithm process. It can analyze the schemas of crossover and mutation affecting genetic propagation in the algorithm process. In the analysis of the research results, a new evolutionary algorithm SCAGA is proposed based on the improved GA. This algorithm uses dynamic methods to adjust the crossover and mutation probabilities. The solution of GA is usually affected by random initial populations and genetic parameters. The specific improvement is to make SCAGA get better optimization performance and convergence performance. At the same time, a new crossover strategy was proposed to decide whether to take the crossover operation or not. Therefore, it can be concluded that SCAGA has been greatly improved and can effectively solve the problem.

5. Conclusion

This study analyzed mathematical modeling of improved GA under the Schema Theorem, that is, parallel GA based on small population strategy and adaptive GA based on improved genetic operator and crossover strategy. Aiming at some problems in practical applications, this paper made several improvements to the genetic operators of traditional GA, and proposed to use multiple small populations in parallel operation under the same total amount of individuals, namely the SGPGA. The results of the example prove that SGPGA not only guaranteed the simplicity of calculation, but also improved the effectiveness of traditional GA. In future researches, we can still use the method of adjusting the crossover probability and the mutation probability to optimize the adaptive GA of the evolution process, which has faster convergence and wider applicability than traditional GA.

References

and Gao

, An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem, International Journal of Production Economics174 (2016), 93–110.

Bharathi

Rekha

and Vijayakumar

, Genetic algorithm based demand side management for smart grid, Wireless Personal Communications93(2) (2017), 481–502.

Anand

Afreen

and Yazdani

, A novel and efficient selection method in genetic algorithm, International Journal of Computer Applications129(15) (2015), 7–12.

Cerf

, The quasispecies regime for the simple genetic algorithm with ranking selection, Transactions of the American Mathematical Society369(9) (2014).

Koehler

G.J.

Bhattacharyya

and Vose

M.D.

, General cardinality genetic algorithms, Evolutionary Computation5(4) (2014), 439–459.

Kalayci

C.B.

Polat

and Gupta

S.M.

, A hybrid genetic algorithm for sequence-dependent disassembly line balancing problem, Annals of Operations Research242(2) (2016), 321–354.

Cerda

and Genvigir

F.D.

, Leptin receptor gene polymorphisms are associated with adiposity and metabolic alterations in Brazilian individuals, Arquivos Brasileiros De Endocrinologia E Metabologia57(9) (2013), 677–84.

Yang

and Jin

, A hybrid approach based on stochastic competitive Hopfield neural network and efficient genetic algorithm for frequency assignment problem, Applied Soft Computing39(C) (2016), 104–116.

Ramadan

S.Z.

, Reducing premature convergence problem in genetic algorithm: application on travel salesman problem, Computer & Information Science6(1) (2016), 47–57.

10.

Ghareb

A.S.

Bakar

A.A.

and Hamdan

A.R.

, Hybrid feature selection based on enhanced genetic algorithm for text categorization, Expert Systems with Applications49 (2016), 31–47.

11.

Duan

H.Y.

, Research on Collaboration in Innovative Methods of Manufacturing Innovation Chain, Revista Iberica de Sistemas e Tecnologias de Informacao (E11) (2016), 292–303.