CN105205535A - Improved gene expression programming method - Google Patents

Abstract

The invention discloses an improved gene expression programming method, which solves the technical problems of premature convergence, slow convergence process and easy falling into local optimal solution faced by the existing method. It includes the following steps: In the chromosome initialization stage, a mixed level uniform table is generated with the chromosome length as the level and the function set and the terminator set as the factors, and the adaptive multi-parent hybrid operator is applied to the initial population generated based on the mixed level uniform table. For generation p, the gene recombination operator and the Dc domain recombination operator are applied to the progeny for evolution processing to obtain the evolved offspring corresponding to the offspring P; the current optimal solution is selected according to the elite selection strategy, if the current optimal solution is When the global optimal solution or the preset maximum genetic algebra is reached, the genetic evolution process ends, the chromosome population is evenly initialized and the adaptive hybridization operator is used to achieve global convergence when solving complex problems, and the convergence speed is also greatly improved.

Description

An Improved Gene Expression Programming Method

technical field

The invention relates to the technical field of computer artificial intelligence, in particular to a gene expression programming method.

Background technique

GEP (Gene Expression Programming, Gene Expression Programming) is developed from GAs (Genetic Algorithms, Genetic Algorithms) and genetic programming. It absorbs the advantages of both and overcomes their shortcomings. The characteristic is that it can use simple coding to solve complex problems. The main difference between gene expression programming and GAs and genetic programming lies in the way chromosomes are encoded. In GEP, a genotype represents a chromosome (chromosome), and a genotype is composed of multiple genes. Chromosomes are linear entities that can undergo processes such as hybridization and mutation, and the separation of genotype and phenotype endows gene expression programming More flexible global space search capability.

The traditional gene expression uses a random method to generate the initial population, and uses the fitness function to evaluate the chromosomes of each generation, which is also a process of selection and mutation based on the fitness value. The resulting new chromosomes are cycled through this process until a preset number of hereditary generations is reached or a solution to the problem is found. The shackles of traditional GEP are premature convergence and late convergence slowdown. In the prior art, some measures have been taken to alleviate this disadvantage, such as: adopting the method of initializing chromosomes according to specific problems; such as: sampling from replicas for hybridization, adaptively controlling the genome size, such as: using hybridization operators to improve the algorithm For example, the parallel algorithm combined with simulated annealing algorithm and genetic mechanism obtains high stability and search ability.

However, the existing solutions have the problem that the population size is set too small or the population size is too large when the population is initialized. If the population size is set too small, important elements may be lost; if the population size is set too large, a large number of repeated elements may be generated. In the GEP algorithm, the diversity of genes at the time of population initialization will directly affect the diversity of subsequent chromosomes. Therefore, the existing solutions all have insufficient gene diversity at the time of population initialization, which leads to the premature convergence of the existing GEP and the slow convergence at the later stage. Slow and easy to fall into the technical problem of local optimal solution.

Contents of the invention

The embodiment of the present invention provides an improved gene expression programming method, which solves the technical problems that the existing GEP still has premature convergence, slow convergence in the later stage, and easy to fall into a local optimal solution.

An improved gene expression programming method provided by an embodiment of the present invention includes the following steps: generating a mixed level uniform table with the chromosome length as the level and the function set and the terminator set as factors, wherein the mixed level uniform table Constructed by g matrices, g is the number of genes on a chromosome, and each row value of the mixed horizontal uniform table represents a chromosome; offspring generation step: apply the automatic method to the initial population generated based on the mixed horizontal uniform table Adapt to the multi-parental hybridization operator to generate offspring p, p takes 1, 2, ..., P in turn, where P is the preset maximum genetic algebra; apply gene recombination operator and Dc domain recombination operator to the offspring p Evolutionary processing, to obtain the evolved offspring corresponding to the offspring p; select the chromosome with the highest fitness from the evolved offspring according to the elite selection strategy as the current optimal solution; the current optimal solution is When the global optimal solution or the preset maximum genetic algebra is reached, the genetic process ends; otherwise, set p=p+1 and return to the offspring generation step.

Preferably, the generation of a mixed level uniform table with the chromosome length as the level and the function set and the terminator set as factors specifically includes the following steps: creating g adjusted equal level uniform tables U _n×k ((n×k ) ^h ·(v+1) ^t ), where h takes the length of the head of the chromosome, t takes the length of the tail of the chromosome, k∈(v+1, f+v+1), and v takes the value The number of elements of the terminator set, the value of f is the number of elements of the function set, and n is a constant integer; the adjusted equal level uniform table U _n×k ((n×k) ^h ( The elements in v+1) ^t ) are circularly copied to the corresponding blank table, and each blank table is filled to form a sub-mixed level uniform table; according to the formed g sub-mixed level uniform table, create as follows The mixed level uniform table expressed by the formula: U _n*(f+v+1) (g*(f+v+1) ^h (v+1) ^t ), wherein, the value of h is the head of the chromosome Length, t is the tail length of the chromosome, v is the number of elements in the terminator set, f is the number of elements in the function set, n is a constant integer, and g is the genetic composition on the chromosome number.

Preferably, the creation of g adjusted equal-level uniform tables U _n×k ((n×k) ^h ·(v+1) ^t ) includes the following steps: creating an original equal-level uniform table U _n*k (( n*k) ^h+t ), wherein, h+t represents the number of matrix columns, h takes the value of the head length of the chromosome, t takes the value of the tail length of the chromosome, n*k represents the number of matrix rows, k∈(v +1, f+v+1), the value of v is the number of elements of the terminator set, the value of f is the number of elements of the function set, and n is a constant integer; the original level is adjusted by quasi-level method Uniform table: limit the head length of chromosomes in the adjusted original iso-level uniform table, and virtualize partial levels of the adjusted original iso-level uniform table, and use the adjusted iso-level uniform table.

Preferably, applying an adaptive multi-parent hybridization operator to the initial population generated based on the mixed level uniform table to generate offspring p is specifically: performing m*n sub-segments of the male parent generated based on the initial population Uniform hybridization combination to generate the offspring p, wherein, m represents the number of chromosomes included in the male parent, and n represents the number of sub-segments divided by one chromosome in the male parent.

Preferably, after applying the genetic recombination operator and the Dc domain recombination operator to the progeny p to perform evolutionary processing to obtain an evolved progeny corresponding to the progeny p, the method further includes: The fitness function calculates the fitness value of each chromosome in the evolved offspring; according to the fitness value of each chromosome, a preset percentage of elite chromosomes is selected from the evolved offspring to be passed on to the next generation.

Preferably, the uniform cross-combination of the m*n sub-segments of the male parents generated based on the initial population to generate the offspring p includes: selecting m basic male parents from the male parents and putting them into Pairing pool; randomly select m-1 slave parents from the male parent to join the pairing pool; construct a hybrid operator uniform table U based on the m basic male parents and the m-1 secondary male parents _m (m ⁿ ), where each row of U _m (m ⁿ ) represents a chromosome in the offspring p.

One or more technical solutions provided by the embodiments of the present invention have at least the following technical effects or advantages:

Based on the idea of uniform design during population initialization, a mixed level uniform table is used to make the initial samples evenly distributed, and the initial population elements are uniformly sampled from the element set, neither losing important elements nor generating a large number of repeated elements, thus ensuring Chromosomal diversity of the initial population. Then, in the genetic process, an adaptive polyparental uniform crossover operator is used to generate offspring, taking into account the characteristics of crossover and mutation. The combination of these two technologies improves the initialization and genetic mutation process of gene expression programming, solves the technical problems of premature convergence, slow convergence process, and easy to fall into local optimal solutions faced by existing technologies, uniformly initializes chromosome populations and uses The adaptive hybridization operator enables global convergence when solving complex problems, and the convergence speed is also greatly improved.

Further, the embodiment of the present invention applies a variety of genetic operators and the use of the elimination mechanism, so that the algorithm is not easy to fall into the local extremum, and the probability of obtaining the global optimal solution is improved.

2. In the embodiment of the present invention, the improved gene expression programming method for generating a mixed-level uniform table based on the idea of uniform design also reduces the number of experiments compared with the orthogonal design.

Description of drawings

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only It is an embodiment of the present invention, and those skilled in the art can also obtain other drawings according to the provided drawings on the premise of not paying creative efforts.

Fig. 1 is the flowchart of the gene expression programming method improved in the embodiment of the present invention;

Fig. 2 is the flowchart of generating a mixing level uniform table in the embodiment of the present invention;

Fig. 3 is a flow chart of an adaptive multi-parent hybrid uniform operator in an embodiment of the present invention.

Detailed ways

In order to solve the technical problems that the existing GEP still has premature convergence, slow convergence in the later stage, and easy to fall into a local optimal solution, the embodiment of the present invention provides an improved gene expression programming method, the general idea is as follows:

A mixed-level uniform table is generated with the chromosome length as the level and the function set and terminator set as factors, and then in the genetic process, an adaptive polyparental uniform crossover operator is used to carry out multi-generation inheritance to generate offspring, and the offspring is used to eliminate the parent generation The poorer individuals get the current optimal solution, and the global optimal solution is obtained by cyclic inheritance, or the genetic process ends when the preset maximum genetic algebra is reached.

The uniform distribution of the initial samples is made by mixing the level uniform table, so that the genetic process is carried out according to the uniform distribution of the initial samples, so that each sampling is more representative, and the defects of premature convergence and late convergence are overcome. The elements of the initial population are uniformly sampled from the element set, neither losing important elements nor generating a large number of repeated elements, thus ensuring the diversity of the initial population chromosomes. The self-adaptive polyparental uniform crossover operator takes into account the characteristics of crossover and mutation. Through the combination of these two technologies, the initialization of gene expression programming and the genetic mutation process are improved, thereby solving the technical problems of premature convergence, slow convergence process, and easy to fall into local optimal solution faced by the existing technology, uniform initialization of chromosome population and The self-adaptive hybridization operator has global convergence when solving complex problems, and the convergence speed has also been greatly improved.

In order to make the purpose, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the drawings in the embodiments of the present invention. Obviously, the described embodiments It is a part of embodiments of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without creative efforts fall within the protection scope of the present invention.

An improved gene expression programming method provided by an embodiment of the present invention, as shown in FIG. 1 , includes the following steps:

S101. Taking the chromosome length as the level, the function set and the terminator set as factors to generate a mixed level uniform table, the mixed level uniform table is constructed by g matrices, g is the number of genes on a chromosome, and each of the mixed horizontal uniform table A row value represents a chromosome.

For example, there are 3186 genes on human chromosome 1, and then chromosome 1 is constructed by 3186 matrices; human X chromosome has 1529 genes, and then X chromosome is composed of 1529 matrices.

Specifically, the chromosome length includes the head length h of the chromosome and the tail length t of the chromosome. Each chromosome has a head and a tail. The head length h of the chromosome is specified by the user, and the tail length t of the chromosome is calculated by the following formula Obtain: t=h*(n-1)+1, n is a constant integer.

Specifically, the function set is f(x), and the terminator set is var(x). For example, the function set f(x) is {+, -, *, /, Q, E, S, T, C}; The character set var(x) is {a, b, c, d, e}.

S101 specifically includes steps 1 to 3:

Step 1. Create g adjusted equal-level uniform tables U _n×k ((n×k) ^h (v+1) ^t ), which are used to form corresponding g sub-mixed horizontal uniform tables, where h takes the value The head length of the chromosome, the value of t is the length of the tail of the chromosome, k∈(v+1, f+v+1), the value of v is the number of elements in the terminator set var(x), and the value of f is the function set The number of elements of f(x), where n is a constant integer.

Step 2. Circularly copy the elements in each adjusted equal-level uniform table to the corresponding blank table, and each blank table is filled to form a sub-mixed horizontal uniform table.

Step 3. Create a mixed level uniform table represented by the following formula according to the formed g sub-mixed level uniform tables:

U _n*(f+v+1) (g*(f+v+1) ^h ·(v+1) ^t ).

Specifically, in U _n*(f+v+1) (g*(f+v+1) ^h ·(v+1) ^t ), the value of h is the head length of the chromosome, and the value of t is the length of the chromosome Tail length, v is the number of elements in the terminator set var(x), f is the number of elements in the function set f(x), n is a constant integer, and g is the number of genes on the chromosome.

Specifically, as shown in FIG. 2, generating a mixed level uniform table is completed through the following cyclic steps:

S1011, setting related parameters of chromosomes and genes. Including: head length of chromosome: h, function set: f(x), number of elements of f(x): f, terminator set: var(x), number of elements of var(x): v, tail of chromosome Length: t=h*(n-1)+1, number of genes: g, number of chromosomes: n*(f+v+1), constant integer: n. When encoding a chromosome, the chromosome is a fixed-length string consisting of elements in the function set f(x) and the terminator set var(x).

S1012. Assign label numbers to elements in the function set f(x) and the terminator set var(x). as the initial member of the matrix.

S1013. Create an original equal-level uniform table U _n*k ((n*k) ^h+t ), wherein, h+t represents the number of matrix columns, h is the head length of the chromosome, and t is the length of the chromosome Tail length, n*k represents the number of matrix rows, k∈(v+1, f+v+1), n is a constant integer.

Specifically, to create the original equal-level uniform table U _n*k ((n*k) ^h+t ), it is first necessary to construct a matrix U _n*k ((n*k) ^h+t ), and use generation-vectors (vectors Generation) method fills the elements of the matrix U _n*k ((n*k) ^h+t ) to obtain the original equal-level uniform table. For example, for the example of the created original equal-level uniform table, the original equal-level uniform table is given as U ₆ (6 ³ ) as shown in Table 1 below:

Table 1. The original equal level uniform table U ₆ (6 ³ )

Column A Column B Column C 1 line 1 2 3 2 lines 2 4 6 3 lines 3 6 2 4 lines 4 1 5 5 lines 5 3 1 6 lines 6 5 4

From Table 1, the same number appears only once in column A, column B, and column C, that is, it is guaranteed that each factor is only tested once at each level; the test points of any two factors are on the grid of the plane, and each row , each column has one and only one test point.

S1014. Adjust the original equal-level uniform table by the quasi-level method, limit the head length of the chromosome in the adjusted original equal-level uniform table, and virtualize partial levels of the adjusted original equal-level uniform table, so as to form the adjusted original equal-level uniform table. Equal level uniform table: U _n×k ((n×k) ^h ·(v+1) ^t ).

Specifically, limit the value of the head of the original equal-level uniform table, specifically through the following formula:

$\mathrm{<span\; class="notranslate">\; u</span>}{<span\; class="notranslate">\; *</span>}_{\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{ccc}{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; j</span>}}& \mathrm{<span\; class="notranslate">\; mod</span>}& <span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \{</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&Element;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; \&Element;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \}</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&LeftArrow;</span>\mathrm{<span\; class="notranslate">\; u</span>}{<span\; class="notranslate">\; *</span>}_{\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; j</span>}}\\ {\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; j</span>}}& \mathrm{<span\; class="notranslate">\; mod</span>}& <span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \{</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&Element;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; \&Element;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \}</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&LeftArrow;</span>\mathrm{<span\; class="notranslate">\; u</span>}{<span\; class="notranslate">\; *</span>}_{\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; j</span>}}\end{array}\right.$

Among them, k∈(v+1, f+v+1), n is a constant integer, v takes the value of the number of elements in the terminator set var(x), and f takes the value of the number of elements in the function set f(x).

S1015. Circularly copy the elements in the adjusted equal-level uniform table to a blank table, and the blank table is filled to form a sub-mixed horizontal uniform table.

S1016. Determine whether g=0 after setting g=g-1, if yes, execute S1017, otherwise return to step S1013. until the corresponding submixture levels of all genes are created uniformly.

S1017, process the g sub-mixed horizontal uniform tables generated by the loop steps S1011～S1016 by direct-product (direct product) method, and create a matrix U _n*(f+v+1) (g*(f+v+1 ) ^h ·(v+1) ^t ), to form a mixed level uniform table U _n*(f+v+1) (g*(f+v+1) ^h ·(v+1) ^t ).

S102. Progeny generation step: apply an adaptive multi-parent hybridization operator to the initial population generated based on the mixed level uniform table to generate offspring p, where p is 1, 2, ..., P in turn, where P is the preset maximum genetic algebra .

In the specific implementation process, since the generation of offspring is a multi-generational genetic process, when the offspring is generated for the first time, that is, p=1, the value of each row in the mixed level uniform table generated by S101 is directly used to generate the initial population. chromosome. Apply the adaptive multi-parent cross operator to the initial population to produce offspring 1. The quality of the chromosomes of the initial population greatly affects the entire convergence process, and the diversity of the chromosomes also determines the efficiency of the search space. The invention uses a mixed level uniform table to make the initial samples evenly distributed, and the initial population elements are evenly sampled from the element set to ensure Chromosomal diversity in the initial population. Apply the adaptive multi-parent hybridization operator to the second-generation male parent to generate offspring 2; the second-generation male parent is the offspring 1 generated from the initial population, and apply the adaptive multi-parental hybridization operator to the third-generation male parent to generate Offspring 3, the father of the third generation comes from offspring 2, and so on.

Specifically, the m*n sub-segments of the male parent generated based on the initial population are uniformly crossed and combined to generate the offspring p, where m represents the number of paternal chromosomes included in the male parent, and n represents the number of sub-segments divided into one chromosome . In different generations of heredity, the paternal parents are different based on the initial population. Specifically, in the first-generation heredity, the paternal parent is the chromosome in the initial population. In the second-generation heredity, the male parent comes from the offspring 1 chromosomes, and so on. For example, there are 200 chromosomes in a population of a certain generation, each chromosome is divided into 1000 sub-segments, and a uniform table is designed to uniformly cross-combine these 200*1000 sub-segments to generate the next generation of offspring.

Referring to Figure 3, the design of the self-adaptive multi-parent hybridization uniform operator is described in detail:

S1021. Divide each chromosome L _p into n mutually disjoint subsets, L _p ∈ (t ∈ (1,P)), where p ∈ 1,2,...,P, p represents the current inheritance algebra.

S1022. Select m basic male parents to be crossed from the male parents and put them into the matching pool.

Specifically, the basic parent is the chromosome that hybridizes, and the chromosome that assists in hybridization is called the secondary parent. The self-adaptive multi-parent hybrid operator has the characteristics of crossover and mutation, which can search for new solutions around the basic parent and complete the information exchange between the basic parent and the secondary parent. Since the hybridization scale of the self-adaptive multi-parent hybridization operator is controlled by the current state of the basic parent, if the basic parent's fitness value f _p is greatly different from the current optimal fitness value f _max , a large-scale mixed level uniform table is constructed to guide the hybridization , to strengthen the information exchange between the male parents; if the difference is not large, reduce the size of the mixed level uniform table to prevent large mutations from destroying excellent gene segments. In the specific implementation process, the basic number m of the mixed level uniform table can be determined according to the following empirical formula:

Among them, δ∈(0,1), p is the current genetic algebra, p∈1,2,...P.

S1023. Randomly select m-1 male parents from the male parents to join the matching pool.

S1024. Construct a crossover operator uniform table U _m (m ⁿ ) based on the m basic fathers and m-1 slave fathers, where each row of U _m (m ⁿ ) represents a chromosome of the offspring p.

After S102, execute S103, apply the gene recombination operator and the Dc domain recombination operator to the offspring p to perform evolution processing, so as to obtain an evolved offspring corresponding to the offspring.

Among them, Dc domain is a constant domain in gene coding, usually including chromosome head, chromosome tail and additional constant domain.

S104. Select the chromosome with the highest fitness from the evolved offspring according to the elite selection strategy as the current optimal solution;

In the specific implementation process, the fitness value of each chromosome in the evolved offspring is calculated according to the fitness function, the chromosomes are sorted according to the fitness value, and the chromosome with the largest fitness value is selected from the evolved offspring to keep, that is, the most contemporary chromosome. optimal solution to see if it is the global optimal solution.

S105. End the genetic process when the current optimal solution is the global optimal solution, or the preset maximum genetic algebra is reached; otherwise, set p=p+1 and return to the step of generating offspring.

In the specific implementation process, the elite selection strategy is applied to the genetic process, and the selected preset percentage of elite chromosomes is passed on to the next generation. The so-called elite selection strategy is: in the process of group evolution, the elite chromosomes (the so-called elite chromosomes are the best individuals that have appeared so far) are directly inherited to the next generation without paired crossover. This selection operation is also called replication. For example: when the genetic evolution reaches the pth generation, a(p) in the population is the elite chromosome. Then a(p) is added to the p+1th generation as the N+1th chromosome of the p+1th generation, and N is the size of the p-th generation population.

Specifically, the preset percentage can be set to 5%, 6%, etc., and those skilled in the art can customize the value of the preset percentage in the specific application process. For example, if the preset percentage is set to 5%, then according to the contemporary The fitness value of chromosomes from large to small selects 5% of chromosomes as elite chromosomes to be directly copied to the next generation. It can be seen that the fitness values of selected elite chromosomes are greater than those of unselected chromosomes.

After S103, the self-adaptive polyparental hybridization uniform operator also includes the following design: Calculate the fitness value G ^P (L ₁ ,L ₂ ,…,L _n ),p of each chromosome in the offspring after evolution according to the fitness function is the current genetic algebra, p∈1,2,...P, that is to calculate the maximum fitness value of each row in the uniform table U _m (m ⁿ ) of the hybridization operator, and select the chromosome with the maximum fitness value in the offspring after evolution as The basic male parent is passed on to the next generation after crossing.

The inventors of the present invention have verified the effectiveness of the application of the technical solutions in the embodiments of the present invention in mining related rules through experiments.

Use the Iris data set to verify the effectiveness of the algorithm. Iris is a data set in the UCI (University of California Irvine, University of California) machine learning knowledge base. During the experiment, we selected 2/3 of the data in the Iris dataset for training, and the remaining 1/3 of the data in the Iris dataset for testing. In the test, the prior art SA-MGEP was used as a test comparison. Both the present invention and SA-MGEP run 100 times, and quantify and analyze the diversity of rule sets by the following formula:

${\mathrm{<span\; class="notranslate">\; DIV</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}\mathrm{<span\; class="notranslate">\; o</span>}\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; =</span>\frac{\underset{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}}\underset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}}{{\mathrm{<span\; class="notranslate">\; N</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}$

Among them, N represents the population size, m represents the number of chromosomes, n represents the number of sub-segments of a chromosome, and d _m,n represents the Hamming distance between individuals m and n.

The present invention compares with prior art SA-MGEP test result as shown in table 2 below, and in table 2, accuracy rate represents the average value of each round of experimental accuracy, and the prediction rate of test set represents the average value of each round of test experiment prediction accuracy rate .

Table 2. The present invention compares with prior art SA-MGEP test result

time(s) number of rules Accuracy(%) Prediction rate on test set (%) this invention 16.8 36 62.4 51.2 current technology 22.4 28 48.7 38.3

As can be seen from the comparison between the present invention and the prior art shown in table 2, the application of the technical solutions in the embodiments of the present invention has obtained higher accuracy and lower time consumption, and the improved gene expression algorithm can be obtained from The Iris dataset gets more association rules.

One or more embodiments provided by the above embodiments of the present invention have at least the following technical effects or advantages:

Through the embodiment of the present invention, based on the idea of uniform design when the population is initialized, a mixed level uniform table is used to make the initial samples uniformly distributed, and the initial population elements are uniformly sampled from the element set, neither losing important elements nor generating a large number of repetitions elements, thus ensuring the diversity of the initial population chromosomes. Then, in the genetic process, an adaptive polyparental uniform crossover operator is used to generate offspring, taking into account the characteristics of crossover and mutation. Through the combination of these two technologies, the initialization of gene expression programming and the genetic mutation process are improved, thereby solving the technical problems of premature convergence, slow convergence process, and easy to fall into local optimal solution faced by the existing technology, uniform initialization of chromosome population and The self-adaptive hybridization operator has global convergence when solving complex problems, and the convergence speed has also been greatly improved.

Further, the embodiment of the present invention applies a variety of genetic operators and the use of the elimination mechanism, so that the algorithm is not easy to fall into the local extremum, and the probability of obtaining the global optimal solution is improved.

2. In the embodiment of the present invention, the improved gene expression programming method for generating a mixed-level uniform table based on the idea of uniform design also reduces the number of experiments compared with the orthogonal design.

While preferred embodiments of the invention have been described, additional changes and modifications to these embodiments can be made by those skilled in the art once the basic inventive concept is appreciated. Therefore, it is intended that the appended claims be construed to cover the preferred embodiment as well as all changes and modifications which fall within the scope of the invention.

Obviously, those skilled in the art can make various changes and modifications to the present invention without departing from the spirit and scope of the present invention. Thus, if these modifications and variations of the present invention fall within the scope of the claims of the present invention and equivalent technologies thereof, the present invention also intends to include these modifications and variations.

Claims (6)

1. an improved gene expression programming method, is characterized in that, comprises the steps: A mixed level uniform table is generated with the chromosome length as the level and the function set and the terminator set as factors, wherein the mixed level uniform table is constructed by g matrices, g is the number of genes on a chromosome, and the mixed Each row value of the horizontal uniform table represents a chromosome; Progeny generation step: apply an adaptive multi-parental hybridization operator to the initial population generated based on the mixed level uniform table to generate offspring p, where p is 1, 2, ..., P in turn, where P is the preset maximum genetic algebra ; Applying a gene recombination operator and a Dc domain recombination operator to the offspring p to perform evolution processing, so as to obtain an evolved offspring corresponding to the offspring p; Select the chromosome with the highest fitness from the evolved offspring according to the elite selection strategy as the current optimal solution; When the current optimal solution is the global optimal solution or reaches the preset maximum genetic algebra, end the genetic process; otherwise set p=p+1 and return to the offspring generation step. 2. the improved gene expression programming method as claimed in claim 1, is characterized in that, described take chromosome length as level, by function set and terminator set as factor generation a mixed level uniform table, specifically comprises the steps: Create g adjusted equal-level uniform tables U _n×k ((n×k) ^h (v+1) ^t ), where h is the length of the head of the chromosome, and t is the length of the tail of the chromosome. k∈(v+1, f+v+1), v is the number of elements of the terminator set, f is the number of elements of the function set, and n is a constant integer; Copy the elements in each of the adjusted equal-level uniform tables U _n×k ((n×k) ^h ·(v+1) ^t ) to the corresponding blank table, and each of the blank tables is filled After full, a submixed horizontal uniform table is formed; Create the mixed level uniform table represented by the following formula according to the formed g sub-mixed level uniform tables: U _n*(f+v+1) (g*(f+v+1) ^h (v+1) ^t ) Wherein, the value of h is the head length of the chromosome, the value of t is the tail length of the chromosome, the value of v is the number of elements of the terminator set, the value of f is the number of elements of the function set, and n is a constant integer , and the value of g is the number of genes on the chromosome. 3. the improved gene expression programming method as claimed in claim 2, is characterized in that, the equal level uniform table U _n×k ((n×k) ^h (v+1) ^t after the described creation g adjustments ), including the following steps: Create the original equal-level uniform table U _n*k ((n*k) ^h+t ), wherein, h+t represents the number of matrix columns, h takes the value of the head length of the chromosome, and t takes the value of the tail length of the chromosome, n*k represents the number of matrix rows, k∈(v+1, f+v+1), v is the number of elements of the terminator set, f is the number of elements of the function set, and n is a constant integer; Adjust the original equal level uniform table by quasi-level method; The head length of the chromosome in the adjusted original equal-level uniform table is limited, and partial levels of the adjusted original equal-level uniform table are virtualized to form the adjusted equal-level uniform table. 4. the improved gene expression programming method as claimed in claim 1, is characterized in that, described initial population application self-adaptive multi-parent hybridization operator is produced child p to the initial population that produces based on described mixing level uniform table, specifically is : The m*n sub-segments of the male parent generated based on the initial population are uniformly hybridized and combined to generate the offspring p, where m represents the number of chromosomes included in the male parent, and n represents one of the male parents The number of subsegments the chromosome is divided into. 5. The improved gene expression programming method as claimed in claim 4, characterized in that, applying gene recombination operator and Dc domain recombination operator to said progeny p to carry out evolutionary processing, to obtain the After the evolved offspring corresponding to the offspring p, the method also includes: Calculate the fitness value of each chromosome in the offspring after evolution according to the fitness function; According to the fitness value of each chromosome, a preset percentage of elite chromosomes is selected from the evolved offspring and passed on to the next generation. 6. The improved gene expression programming method according to claim 5, wherein, the m*n sub-segments of the male parent produced based on the initial population are uniformly hybridized to generate the offspring p ,include: Select m basic fathers from the fathers and put them into the matching pool; Randomly select m-1 from the male parent to join the paired pool from the male parent; A hybrid operator uniform table U _m (m ⁿ ) is constructed based on the m basic male parents and the m-1 secondary male parents, where each row of U _m (m ⁿ ) represents the of a chromosome.