# The Algorithm for Algorithms: An Evolutionary Algorithm Based on Automatic Designing of Genetic Operators

Authors: Dazhi Jiang; Zhun Fan
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

At present there is a wide range of evolutionary algorithms available to researchers and practitioners. Despite the great diversity of these algorithms, virtually all of the algorithms share one feature: they have been manually designed. A fundamental question is “are there any algorithms that can design evolutionary algorithms automatically?” A more complete definition of the question is “can computer construct an algorithm which will generate algorithms according to the requirement of a problem?” In this paper, a novel evolutionary algorithm based on automatic designing of genetic operators is presented to address these questions. The resulting algorithm not only explores solutions in the problem space like most traditional evolutionary algorithms do, but also automatically generates genetic operators in the operator space. In order to verify the performance of the proposed algorithm, comprehensive experiments on 23 well-known benchmark optimization problems are conducted. The results show that the proposed algorithm can outperform standard differential evolution algorithm in terms of convergence speed and solution accuracy which shows that the algorithm designed automatically by computers can compete with the algorithms designed by human beings.


---

## Body

## 1. Introduction

At present there is a wide range of evolutionary algorithms available to researchers and practitioners. Despite the great diversity of these algorithms, virtually all of the algorithms share one feature: they have been manually designed. As a result, inevitably, current evolutionary algorithms in general incorporate human preconceptions in their designs. This situation encourages us to ask the following questions: are there any algorithms that can design evolutionary algorithms automatically? A more complete definition of the question is “can computer construct an algorithm which will generate algorithms according to the requirement of a problem?” In the 13th century, a French scientist, Villand de Honnecourt proposed a perpetual motion machine for the first time. However, the truth shows that it is impossible to make such kind of entity in the real world. But in the world of computer for the machine to automatically design algorithms, several automatic algorithm design techniques have been proposed in recent years to overcome this limitation. For example, hyperheuristics include search methods that automatically select and combine simpler heuristics, creating a generic heuristic that is used to solve more general instances of a given type of optimization problem. Hence, hyperheuristics search in the space of heuristics, instead of in the problem solution space [1], raising the level of generality of the solutions produced by the hyperheuristics. Ant Colony algorithms are population-based methods widely used in combinatorial optimization problems. Taveres and Pereira [2] proposed a grammatical evolution [3] approach to automatically design ant colony optimization algorithms. The grammar adopted by this framework has the ability to guide the learning of novel architectures, by rearranging components regularly found on human designed variants. Furthermore, Taveres and Pereira [4] proposed a strongly typed genetic programming [5] approach to automatically evolve the communication mechanism that allows ants to cooperatively solve a given problem. For these two applications, results obtained with several TSP instances show that the evolved pheromone update strategies are effective and exhibit a strong generalization capability and are competitive with human designed variants. For rule induction algorithms, Pappa and Freitas [6] proposed the use of grammar-based genetic programming (GGP) to automatically evolve rule induction algorithms. The experiments involving 11 data sets show that novel rule induction algorithms can be automatically generated using GGP. Oltean and Grosan [7] used multi expression programming (MEP) [8] technique to evolve evolutionary algorithm, in which each MEP chromosome encodes multiple EAs.Although the aforementioned automatic algorithms have different emphases on research objectives and contents, one thing in common is that they use automatic method to design algorithms, which shows that automatic programming method can build algorithms to solve problems automatically.As the core components of the evolutionary algorithms, the genetic operators, such as mutation and combination, are more variable and complicated compared with other components, such as initialization and selection, in the algorithm framework. Furthermore, in terms of the design of the new algorithms, the most difficult and important part of the previous work is focused on the design of genetic operators. In our work, we also focus on designing genetic operators. This paper proposes a novel approach to design genetic operators in evolutionary algorithm, namely, the evolutionary algorithm based on automatic designing of genetic operators (EA2DGO), which uses MEP with a new encoding scheme [9] to automatically generate genetic operators in the evolutionary algorithm to solve simulated problems.Organization of this paper is as follows. In Section2, the commonality of three classical evolutionary algorithms is introduced and discussed and then in Section 3, the general scheme of designing genetic operators is presented. In Section 4, the framework of EA2DGO is described, explaining the mechanism of automatically designing genetic operators. Experimental verifications are presented in Section 5. Section 6 gives conclusions and discussions.


## 2. Three Classical Evolutionary Algorithms

It is important to investigate what expressions of genetic operators are amenable to automatic design, for which we can get inspirations from analyzing the standard genetic algorithm (SGA) [10], particle swarm optimization (PSO) [11] and differential evolution (DE) [12, 13].In classical GA’s crossover arithmetic operator, the new vectors are generated by linear combination of two different individuals. PSO and DE can be considered extended algorithms of the SGA. In the operator of combination of PSO, the particle’s personal experiencep
b
e
s
t and population’s best experience g
b
e
s
t influence the movement of each particle. In the common operator of mutation in DE algorithm, the new vector is generated by the difference of two individuals in population and sum with another individual according to certain rules. These three algorithms are different but share some common characteristics. In the following subsections, the equations describing the operations of the operators of SGA, PSO, and DE algorithms are analyzed in detail.


### 2.1. Genetic Algorithm

GA with the real coding usually adopts arithmetic crossover as one of the genetic operators. Take total arithmetic crossover, for example, assumeN is a constant number which presents the size of population, and D is the dimension of parameter vectors. The population P is then expressed as P
=
{
X
i
(
t
)
,
i
=
1,2
,
…
,
N
} and t is the generation. Select two individuals X
j
(
t
), X
k
(
t
) from population according to certain rule, where j
,
k
∈
{
1,2
,
…
,
N
}, and j
≠
k, the child vector X
(
1
)
(
t
) and X
(
2
)
(
t
) could be generated and expressed, respectively, as the following:(1)
X
1
t
=
α
X
j
(
t
)
+
(
1
-
α
)
X
k
(
t
)
=
X
k
(
t
)
+
α
X
j
t
-
X
k
t
,
(2)
X
2
t
=
α
X
k
t
+
1
-
α
X
j
t
=
X
j
t
+
α
X
k
t
-
X
j
t
,where α
=
{
α
1
,
α
2
,
…
,
α
D
} and α
l
∈
[
0,1
],  l
=
1,2
,
…
,
D.


### 2.2. Particle Swarm Optimization

PSO, like other evolutionary algorithms, is also a population-based search algorithm and starts with an initial population of randomly generated solutions called particles. Each particle in PSO has a velocity and a position. PSO remembers both the best position found by all particles and the best positions found by each particle in the search process. For a search problem in aD dimensional space, a particle represents a potential solution. The velocity V
i
d and position X
i
d of the dth dimension of the ith particle are updated according to the following equations:(3)
V
i
d
t
+
1
=
V
i
d
(
t
)
+
c
1
∗
rand
1
i
d
∗
p
b
e
s
t
i
d
t
-
X
i
d
t
+
c
2
∗
rand
2
i
d
∗
g
b
e
s
t
d
-
X
i
d
t
,
(4)
X
i
d
t
+
1
=
X
i
d
t
+
V
i
d
t
+
1
,where i
=
1,2
,
…, is the particle’s index, X
i
=
(
X
i
1
,
X
i
1
,
…
,
X
i
D
) is the position of the ith particle, and V
i
=
(
V
i
1
,
V
i
1
,
…
,
V
i
D
) represents the velocity of ith particle. p
b
e
s
t
i
=
(
p
b
e
s
t
i
1
,
p
b
e
s
t
i
2
,
…
,
p
b
e
s
t
i
D
) represents the best previous position yielding the best fitness value for the ith particle. g
b
e
s
t
=
(
g
b
e
s
t
1
,
g
b
e
s
t
2
,
…
,
g
b
e
s
t
D
) is the best position discovered by the whole population. rand
1
i
d and rand
2
i
d are two random numbers independently generated within the range of [
0
,
1
], c
1 and c
2 are two learning factors reflecting the weights of stochastic acceleration terms that pull each particle toward p
b
e
s
t and g
b
e
s
t positions, respectively. t
=
1,2
,
…, indicates the iterations.


### 2.3. Differential Evolution

Differential evolution (DE) is a population-based, direct, robust, and efficient search method. Like other evolutionary algorithms, DE starts with an initial population vector randomly generated in the solution space. Assume thatN is a constant number which presents the size of population, and D is the dimension of parameter vectors, and the population is expressed as X
i
(
t
), where i
=
1,2
,
…
,
N, and t is the generation. The main difference between DE and other evolutionary algorithms, such as GA and PSO, is its new generating method to generate new population vectors. In order to generate a new population vector, three vectors in population are randomly selected and weighted difference of two of them is added to the third one. After crossover, the new vector is compared with a predetermined vector in the population. If the new vector is better than the predetermined one, it replaces it; otherwise, the predetermined vector is copied to the next generation’s population. For a traditional DE, the mutation procedure is illustrated as the following.For theith vector from generation t, a mutant vector X
i
(
t
+
1
) is defined by(5)
X
i
t
+
1
=
X
r
1
t
+
F
X
r
2
t
-
X
r
3
t
,where ∈
{
1,2
,
…
,
N
}, r
1
,
r
2
,
r
3
∈
[
0
,
N
],  i, and  r
1,  r
2 and r
3 are different. The differential mutation parameter F, known as scale factor, is a positive real normally between 0 and 1 but can also take values greater than 1. Generally speaking, larger values for F result in higher diversity in the generated population and the lower values lead to faster convergence.


## 2.1. Genetic Algorithm

GA with the real coding usually adopts arithmetic crossover as one of the genetic operators. Take total arithmetic crossover, for example, assumeN is a constant number which presents the size of population, and D is the dimension of parameter vectors. The population P is then expressed as P
=
{
X
i
(
t
)
,
i
=
1,2
,
…
,
N
} and t is the generation. Select two individuals X
j
(
t
), X
k
(
t
) from population according to certain rule, where j
,
k
∈
{
1,2
,
…
,
N
}, and j
≠
k, the child vector X
(
1
)
(
t
) and X
(
2
)
(
t
) could be generated and expressed, respectively, as the following:(1)
X
1
t
=
α
X
j
(
t
)
+
(
1
-
α
)
X
k
(
t
)
=
X
k
(
t
)
+
α
X
j
t
-
X
k
t
,
(2)
X
2
t
=
α
X
k
t
+
1
-
α
X
j
t
=
X
j
t
+
α
X
k
t
-
X
j
t
,where α
=
{
α
1
,
α
2
,
…
,
α
D
} and α
l
∈
[
0,1
],  l
=
1,2
,
…
,
D.


## 2.2. Particle Swarm Optimization

PSO, like other evolutionary algorithms, is also a population-based search algorithm and starts with an initial population of randomly generated solutions called particles. Each particle in PSO has a velocity and a position. PSO remembers both the best position found by all particles and the best positions found by each particle in the search process. For a search problem in aD dimensional space, a particle represents a potential solution. The velocity V
i
d and position X
i
d of the dth dimension of the ith particle are updated according to the following equations:(3)
V
i
d
t
+
1
=
V
i
d
(
t
)
+
c
1
∗
rand
1
i
d
∗
p
b
e
s
t
i
d
t
-
X
i
d
t
+
c
2
∗
rand
2
i
d
∗
g
b
e
s
t
d
-
X
i
d
t
,
(4)
X
i
d
t
+
1
=
X
i
d
t
+
V
i
d
t
+
1
,where i
=
1,2
,
…, is the particle’s index, X
i
=
(
X
i
1
,
X
i
1
,
…
,
X
i
D
) is the position of the ith particle, and V
i
=
(
V
i
1
,
V
i
1
,
…
,
V
i
D
) represents the velocity of ith particle. p
b
e
s
t
i
=
(
p
b
e
s
t
i
1
,
p
b
e
s
t
i
2
,
…
,
p
b
e
s
t
i
D
) represents the best previous position yielding the best fitness value for the ith particle. g
b
e
s
t
=
(
g
b
e
s
t
1
,
g
b
e
s
t
2
,
…
,
g
b
e
s
t
D
) is the best position discovered by the whole population. rand
1
i
d and rand
2
i
d are two random numbers independently generated within the range of [
0
,
1
], c
1 and c
2 are two learning factors reflecting the weights of stochastic acceleration terms that pull each particle toward p
b
e
s
t and g
b
e
s
t positions, respectively. t
=
1,2
,
…, indicates the iterations.


## 2.3. Differential Evolution

Differential evolution (DE) is a population-based, direct, robust, and efficient search method. Like other evolutionary algorithms, DE starts with an initial population vector randomly generated in the solution space. Assume thatN is a constant number which presents the size of population, and D is the dimension of parameter vectors, and the population is expressed as X
i
(
t
), where i
=
1,2
,
…
,
N, and t is the generation. The main difference between DE and other evolutionary algorithms, such as GA and PSO, is its new generating method to generate new population vectors. In order to generate a new population vector, three vectors in population are randomly selected and weighted difference of two of them is added to the third one. After crossover, the new vector is compared with a predetermined vector in the population. If the new vector is better than the predetermined one, it replaces it; otherwise, the predetermined vector is copied to the next generation’s population. For a traditional DE, the mutation procedure is illustrated as the following.For theith vector from generation t, a mutant vector X
i
(
t
+
1
) is defined by(5)
X
i
t
+
1
=
X
r
1
t
+
F
X
r
2
t
-
X
r
3
t
,where ∈
{
1,2
,
…
,
N
}, r
1
,
r
2
,
r
3
∈
[
0
,
N
],  i, and  r
1,  r
2 and r
3 are different. The differential mutation parameter F, known as scale factor, is a positive real normally between 0 and 1 but can also take values greater than 1. Generally speaking, larger values for F result in higher diversity in the generated population and the lower values lead to faster convergence.


## 3. General Scheme of Designing Genetic Operators

### 3.1. The General Characteristics of Genetic Operators

Through the analysis above, the following observations are made.(i)
A genetic operator is a formula which is composed of a group of objects (such asX
j
(
t
) and X
k
(
t
)), arithmetic operators (such as +, −, ∗), and parameters (such as α, c
1, c
2, F).
(ii)
A formula representing a genetic operator can have many variants. For example, DE and PSO have similar but different formulas, which is again different from the formula of SGA.
(iii)
While existing evolutionary algorithms (including SGA, PSO, and DE) have different formulas, their genetic operators actually share characteristics (i) and (ii).According to the observations (i), (ii), and (iii), we could design a scheme to represent the genetic operator for automatic design.


### 3.2. The Scheme of Genetic Operators

#### 3.2.1. The Encoding Scheme of Genetic Operator Chromosome

Firstly, we need an entity to express the genetic operators which can be distinguished and manipulated by a computer. Genetic programming (GP), gene expression programming (GEP), and multiexpression programming (MEP) are three kinds of methods with focus of generating computer programs automatically for given problems. According to this, a similar chromosome structureO
(
i
,
C
,
t
), like MEP, is presented to express genetic operators. Where i
=
1,2
,
…
,
N is the chromosome’s index, t is the generation, and C is the genetic operator chromosome which is composed of a head and a tail. The head contains symbols that represent both functions (elements from the function set F) and terminals (elements from the terminal Set T), whereas the tail contains only terminals. Generally, F is composed of arithmetic operators, and T is composed of objects and parameters.Each gene inC encodes a terminal or a function symbol. A gene that encodes a function includes pointers towards the function arguments. Function arguments always have indices of higher values than the position of the function itself in the chromosome.There is little difference compared with chromosome represented by MEP. In MEP chromosome, the function arguments have indices of lower values than the position of function itself. However, both of them are essentially the same. MEP chromosome presented in this way is similar to the GEP chromosome where the tail is constructed with terminal symbol. Further information about relationships between chromosomes of GEP and MEP can be seen in [14].


#### 3.2.2. The Decoding Scheme of Genetic Operator Chromosome

Chromosome translation is obtained by parsing the chromosome right-left. A terminal symbol specifies a simple expression. A function symbol specifies a complex expression obtained by connecting the operands specified by the argument positions with the current function symbol. As MEP chromosome encodes more than one problem solution, and there is neither practical nor theoretical evidence that one of these expressions is better than the others before fitness calculation. For simplicity, the expression tree expressed by the first symbol is chosen as the chromosome’s final representation.After decoding, a genotype ofO
(
i
,
C
,
t
) could be translated into a phenotype O
-
(
i
,
C
,
t
) which can be further processed by a computer.


#### 3.2.3. The Characteristics of the Scheme of Designing Genetic Operators

According to the encoding and decoding scheme of genetic operators, two characteristics are essential for automatically designing genetic operators.(i)
Changeability: the most different characteristic compared with traditional genetic operators is that its structure could be reconstructed by a computer, which means that the genetic operators could be generated and changed according to the requirements of problem. For example, every gene could be changed into another terminal or function symbol; every function arguments could be changed into another function argument; when the gene or function arguments are changed, the genotype and phenotype of chromosome are transformed.
(ii)
Adaptability: an automatic way of generating novel formula (using the existing objects, arithmetic operators, and parameters) may lead to a very novel design of evolutionary algorithm which can adapt itself to address problems with dynamict, which means genetic operators are simultaneously searched and designed in the process of problem solving. In the following, we take a snapshot of the chromosomes used to represent the genetic operators of the three classic evolutionary algorithms.


### 3.3. The Chromosome for Three Classic Evolutionary Algorithms

#### 3.3.1. SGA

If we consider (1) and take an example of X
k
(
t
)
=
a, X
j
(
t
)
=
b, α
=
c, and T
=
{
a
,
b
,
c
} and O
=
{
+
,
-
,
∗
}, then (1) could be expressed by an expression tree (phenotype) as shown in Figure 1.Figure 1
The expression tree of genetic operator (1) in SGA.Take an example with the length of a chromosome as 7,T
=
{
a
,
b
,
c
} and O
=
{
+
,
-
,
∗
}, the expression tree in Figure 1 could be expressed as a genotype as shown in Table 1.Table 1
The equivalent genotype of (1) in SGA.
1
2
3
4
5
6
7
+
a
∗
c
−
b
a
2, 3
4, 5
6, 7


#### 3.3.2. PSO

For PSO, an example ofX
i
(
t
)
=
a, V
i
(
t
)
=
b, V
i
(
t
+
1
)
=
c, p
b
e
s
t
i
(
t
)
=
d, g
b
e
s
t
(
t
)
=
e, T
=
{
a
,
b
,
c
,
d
,
e
,
c
1
,
c
2
,
r
1
,
r
2
}, and O
=
{
+
,
-
,
∗
} is used. The PSO’s particle updating equation X
i
(
t
+
1
) can be expressed by an expression tree (phenotype) as shown in Figure 2.Figure 2
The expression tree of genetic operators (3) and (4) in PSO.Since (3) and (4) are more complicated equations compared with SGA operators, they need a longer chromosome to express the equivalent genotype. For this example, the length of chromosome is 18, T
=
{
a
,
b
,
c
,
d
,
e
,
c
1
,
c
2
,
r
1
,
r
2
} and O
=
{
+
,
-
,
∗
}, a kind of equivalent genotype for phenotype can be expressed as shown in Table 2.Table 2
The equivalent genotype of (3) and (4) in PSO.
1
2
3
4
5
6
7
8
9
+
+
+
*
*
*
*
−
−
18, 2
17, 3
4, 5
10, 6
11, 7
8, 12
9, 13
16, 18
14, 18
10
11
12
13
14
15
16
17
18
c
1
c
2
r
1
r
2
e
c
d
b
a


#### 3.3.3. DE

For the mutation operator of DE, if we take an example ofX
r
1
(
t
)
=
a, X
r
2
(
t
)
=
b, X
r
3
(
t
)
=
c, T
=
{
a
,
b
,
c
,
F
}, and O
=
{
+
,
-
,
∗
}, the DE’s mutation equation X
i
(
t
+
1
) could be expressed by an expression tree (phenotype) shown in Figure 3.Figure 3
The expression tree of genetic operator (5) in DE.Here the length of chromosome is 7,T
=
{
a
,
b
,
c
,
F
} and O
=
{
+
,
-
,
∗
}. A kind of equivalent genotype for phenotype could be expressed as shown in Table 3.Table 3
The equivalent genotype of (5) in DE.
1
2
3
4
5
6
7
+
a
∗
F
−
b
c
2, 3
4, 5
6, 7By analysis above, it is evident that for SGA, PSO, and DE, their genetic operators can be expressed by a specific chromosome, respectively. But thestructures of the chromosomes are not changed, orstatic through the whole process of evolutionary run for the three classic evolutionary algorithms. This is generally true also for many other variants of evolutionary algorithms.Now the question is “can automatic programming method automatically construct genetic operators of evolutionary algorithms, where operators were automatically generated in the running process of problem solving, rather than predefined?” As we know, the evolutionary algorithms generally have capabilities of self-organizing, self-adapting, and self-regulating, but their genetic operators are normally predetermined. While the algorithms construed by predetermined operators are effective in certain aspects of problem solving, their performances in addressing other issues may not be so competitive. This phenomenon can be explained to some extent by the famous “No Free Lunch” theory [15]. If there is an algorithm framework, in which the genetic operators can automatically adjust themselves during the problem-solving process with the change of the nature of the problems to be solved, the capabilities of self-organizing, self-adapting, and self-regulating of the algorithms can be further enhanced, and the limit imposed by the “NO Free Lunch” theory may be broken. Peng et al. proposed a population-based algorithm portfolio (PAP) [16], which distributes the time among multiple different algorithms, to decrease the inherent risk associated with the selection of algorithms. However, the algorithms are still predefined in PAP, which is very different compared with our method. In the following, the details of a framework that can automatically design genetic operators in the running process of problem solving will be introduced.


## 3.1. The General Characteristics of Genetic Operators

Through the analysis above, the following observations are made.(i)
A genetic operator is a formula which is composed of a group of objects (such asX
j
(
t
) and X
k
(
t
)), arithmetic operators (such as +, −, ∗), and parameters (such as α, c
1, c
2, F).
(ii)
A formula representing a genetic operator can have many variants. For example, DE and PSO have similar but different formulas, which is again different from the formula of SGA.
(iii)
While existing evolutionary algorithms (including SGA, PSO, and DE) have different formulas, their genetic operators actually share characteristics (i) and (ii).According to the observations (i), (ii), and (iii), we could design a scheme to represent the genetic operator for automatic design.


## 3.2. The Scheme of Genetic Operators

### 3.2.1. The Encoding Scheme of Genetic Operator Chromosome

Firstly, we need an entity to express the genetic operators which can be distinguished and manipulated by a computer. Genetic programming (GP), gene expression programming (GEP), and multiexpression programming (MEP) are three kinds of methods with focus of generating computer programs automatically for given problems. According to this, a similar chromosome structureO
(
i
,
C
,
t
), like MEP, is presented to express genetic operators. Where i
=
1,2
,
…
,
N is the chromosome’s index, t is the generation, and C is the genetic operator chromosome which is composed of a head and a tail. The head contains symbols that represent both functions (elements from the function set F) and terminals (elements from the terminal Set T), whereas the tail contains only terminals. Generally, F is composed of arithmetic operators, and T is composed of objects and parameters.Each gene inC encodes a terminal or a function symbol. A gene that encodes a function includes pointers towards the function arguments. Function arguments always have indices of higher values than the position of the function itself in the chromosome.There is little difference compared with chromosome represented by MEP. In MEP chromosome, the function arguments have indices of lower values than the position of function itself. However, both of them are essentially the same. MEP chromosome presented in this way is similar to the GEP chromosome where the tail is constructed with terminal symbol. Further information about relationships between chromosomes of GEP and MEP can be seen in [14].


### 3.2.2. The Decoding Scheme of Genetic Operator Chromosome

Chromosome translation is obtained by parsing the chromosome right-left. A terminal symbol specifies a simple expression. A function symbol specifies a complex expression obtained by connecting the operands specified by the argument positions with the current function symbol. As MEP chromosome encodes more than one problem solution, and there is neither practical nor theoretical evidence that one of these expressions is better than the others before fitness calculation. For simplicity, the expression tree expressed by the first symbol is chosen as the chromosome’s final representation.After decoding, a genotype ofO
(
i
,
C
,
t
) could be translated into a phenotype O
-
(
i
,
C
,
t
) which can be further processed by a computer.


### 3.2.3. The Characteristics of the Scheme of Designing Genetic Operators

According to the encoding and decoding scheme of genetic operators, two characteristics are essential for automatically designing genetic operators.(i)
Changeability: the most different characteristic compared with traditional genetic operators is that its structure could be reconstructed by a computer, which means that the genetic operators could be generated and changed according to the requirements of problem. For example, every gene could be changed into another terminal or function symbol; every function arguments could be changed into another function argument; when the gene or function arguments are changed, the genotype and phenotype of chromosome are transformed.
(ii)
Adaptability: an automatic way of generating novel formula (using the existing objects, arithmetic operators, and parameters) may lead to a very novel design of evolutionary algorithm which can adapt itself to address problems with dynamict, which means genetic operators are simultaneously searched and designed in the process of problem solving. In the following, we take a snapshot of the chromosomes used to represent the genetic operators of the three classic evolutionary algorithms.


## 3.2.1. The Encoding Scheme of Genetic Operator Chromosome

Firstly, we need an entity to express the genetic operators which can be distinguished and manipulated by a computer. Genetic programming (GP), gene expression programming (GEP), and multiexpression programming (MEP) are three kinds of methods with focus of generating computer programs automatically for given problems. According to this, a similar chromosome structureO
(
i
,
C
,
t
), like MEP, is presented to express genetic operators. Where i
=
1,2
,
…
,
N is the chromosome’s index, t is the generation, and C is the genetic operator chromosome which is composed of a head and a tail. The head contains symbols that represent both functions (elements from the function set F) and terminals (elements from the terminal Set T), whereas the tail contains only terminals. Generally, F is composed of arithmetic operators, and T is composed of objects and parameters.Each gene inC encodes a terminal or a function symbol. A gene that encodes a function includes pointers towards the function arguments. Function arguments always have indices of higher values than the position of the function itself in the chromosome.There is little difference compared with chromosome represented by MEP. In MEP chromosome, the function arguments have indices of lower values than the position of function itself. However, both of them are essentially the same. MEP chromosome presented in this way is similar to the GEP chromosome where the tail is constructed with terminal symbol. Further information about relationships between chromosomes of GEP and MEP can be seen in [14].


## 3.2.2. The Decoding Scheme of Genetic Operator Chromosome

Chromosome translation is obtained by parsing the chromosome right-left. A terminal symbol specifies a simple expression. A function symbol specifies a complex expression obtained by connecting the operands specified by the argument positions with the current function symbol. As MEP chromosome encodes more than one problem solution, and there is neither practical nor theoretical evidence that one of these expressions is better than the others before fitness calculation. For simplicity, the expression tree expressed by the first symbol is chosen as the chromosome’s final representation.After decoding, a genotype ofO
(
i
,
C
,
t
) could be translated into a phenotype O
-
(
i
,
C
,
t
) which can be further processed by a computer.


## 3.2.3. The Characteristics of the Scheme of Designing Genetic Operators

According to the encoding and decoding scheme of genetic operators, two characteristics are essential for automatically designing genetic operators.(i)
Changeability: the most different characteristic compared with traditional genetic operators is that its structure could be reconstructed by a computer, which means that the genetic operators could be generated and changed according to the requirements of problem. For example, every gene could be changed into another terminal or function symbol; every function arguments could be changed into another function argument; when the gene or function arguments are changed, the genotype and phenotype of chromosome are transformed.
(ii)
Adaptability: an automatic way of generating novel formula (using the existing objects, arithmetic operators, and parameters) may lead to a very novel design of evolutionary algorithm which can adapt itself to address problems with dynamict, which means genetic operators are simultaneously searched and designed in the process of problem solving. In the following, we take a snapshot of the chromosomes used to represent the genetic operators of the three classic evolutionary algorithms.


## 3.3. The Chromosome for Three Classic Evolutionary Algorithms

### 3.3.1. SGA

If we consider (1) and take an example of X
k
(
t
)
=
a, X
j
(
t
)
=
b, α
=
c, and T
=
{
a
,
b
,
c
} and O
=
{
+
,
-
,
∗
}, then (1) could be expressed by an expression tree (phenotype) as shown in Figure 1.Figure 1
The expression tree of genetic operator (1) in SGA.Take an example with the length of a chromosome as 7,T
=
{
a
,
b
,
c
} and O
=
{
+
,
-
,
∗
}, the expression tree in Figure 1 could be expressed as a genotype as shown in Table 1.Table 1
The equivalent genotype of (1) in SGA.
1
2
3
4
5
6
7
+
a
∗
c
−
b
a
2, 3
4, 5
6, 7


### 3.3.2. PSO

For PSO, an example ofX
i
(
t
)
=
a, V
i
(
t
)
=
b, V
i
(
t
+
1
)
=
c, p
b
e
s
t
i
(
t
)
=
d, g
b
e
s
t
(
t
)
=
e, T
=
{
a
,
b
,
c
,
d
,
e
,
c
1
,
c
2
,
r
1
,
r
2
}, and O
=
{
+
,
-
,
∗
} is used. The PSO’s particle updating equation X
i
(
t
+
1
) can be expressed by an expression tree (phenotype) as shown in Figure 2.Figure 2
The expression tree of genetic operators (3) and (4) in PSO.Since (3) and (4) are more complicated equations compared with SGA operators, they need a longer chromosome to express the equivalent genotype. For this example, the length of chromosome is 18, T
=
{
a
,
b
,
c
,
d
,
e
,
c
1
,
c
2
,
r
1
,
r
2
} and O
=
{
+
,
-
,
∗
}, a kind of equivalent genotype for phenotype can be expressed as shown in Table 2.Table 2
The equivalent genotype of (3) and (4) in PSO.
1
2
3
4
5
6
7
8
9
+
+
+
*
*
*
*
−
−
18, 2
17, 3
4, 5
10, 6
11, 7
8, 12
9, 13
16, 18
14, 18
10
11
12
13
14
15
16
17
18
c
1
c
2
r
1
r
2
e
c
d
b
a


### 3.3.3. DE

For the mutation operator of DE, if we take an example ofX
r
1
(
t
)
=
a, X
r
2
(
t
)
=
b, X
r
3
(
t
)
=
c, T
=
{
a
,
b
,
c
,
F
}, and O
=
{
+
,
-
,
∗
}, the DE’s mutation equation X
i
(
t
+
1
) could be expressed by an expression tree (phenotype) shown in Figure 3.Figure 3
The expression tree of genetic operator (5) in DE.Here the length of chromosome is 7,T
=
{
a
,
b
,
c
,
F
} and O
=
{
+
,
-
,
∗
}. A kind of equivalent genotype for phenotype could be expressed as shown in Table 3.Table 3
The equivalent genotype of (5) in DE.
1
2
3
4
5
6
7
+
a
∗
F
−
b
c
2, 3
4, 5
6, 7By analysis above, it is evident that for SGA, PSO, and DE, their genetic operators can be expressed by a specific chromosome, respectively. But thestructures of the chromosomes are not changed, orstatic through the whole process of evolutionary run for the three classic evolutionary algorithms. This is generally true also for many other variants of evolutionary algorithms.Now the question is “can automatic programming method automatically construct genetic operators of evolutionary algorithms, where operators were automatically generated in the running process of problem solving, rather than predefined?” As we know, the evolutionary algorithms generally have capabilities of self-organizing, self-adapting, and self-regulating, but their genetic operators are normally predetermined. While the algorithms construed by predetermined operators are effective in certain aspects of problem solving, their performances in addressing other issues may not be so competitive. This phenomenon can be explained to some extent by the famous “No Free Lunch” theory [15]. If there is an algorithm framework, in which the genetic operators can automatically adjust themselves during the problem-solving process with the change of the nature of the problems to be solved, the capabilities of self-organizing, self-adapting, and self-regulating of the algorithms can be further enhanced, and the limit imposed by the “NO Free Lunch” theory may be broken. Peng et al. proposed a population-based algorithm portfolio (PAP) [16], which distributes the time among multiple different algorithms, to decrease the inherent risk associated with the selection of algorithms. However, the algorithms are still predefined in PAP, which is very different compared with our method. In the following, the details of a framework that can automatically design genetic operators in the running process of problem solving will be introduced.


## 3.3.1. SGA

If we consider (1) and take an example of X
k
(
t
)
=
a, X
j
(
t
)
=
b, α
=
c, and T
=
{
a
,
b
,
c
} and O
=
{
+
,
-
,
∗
}, then (1) could be expressed by an expression tree (phenotype) as shown in Figure 1.Figure 1
The expression tree of genetic operator (1) in SGA.Take an example with the length of a chromosome as 7,T
=
{
a
,
b
,
c
} and O
=
{
+
,
-
,
∗
}, the expression tree in Figure 1 could be expressed as a genotype as shown in Table 1.Table 1
The equivalent genotype of (1) in SGA.
1
2
3
4
5
6
7
+
a
∗
c
−
b
a
2, 3
4, 5
6, 7


## 3.3.2. PSO

For PSO, an example ofX
i
(
t
)
=
a, V
i
(
t
)
=
b, V
i
(
t
+
1
)
=
c, p
b
e
s
t
i
(
t
)
=
d, g
b
e
s
t
(
t
)
=
e, T
=
{
a
,
b
,
c
,
d
,
e
,
c
1
,
c
2
,
r
1
,
r
2
}, and O
=
{
+
,
-
,
∗
} is used. The PSO’s particle updating equation X
i
(
t
+
1
) can be expressed by an expression tree (phenotype) as shown in Figure 2.Figure 2
The expression tree of genetic operators (3) and (4) in PSO.Since (3) and (4) are more complicated equations compared with SGA operators, they need a longer chromosome to express the equivalent genotype. For this example, the length of chromosome is 18, T
=
{
a
,
b
,
c
,
d
,
e
,
c
1
,
c
2
,
r
1
,
r
2
} and O
=
{
+
,
-
,
∗
}, a kind of equivalent genotype for phenotype can be expressed as shown in Table 2.Table 2
The equivalent genotype of (3) and (4) in PSO.
1
2
3
4
5
6
7
8
9
+
+
+
*
*
*
*
−
−
18, 2
17, 3
4, 5
10, 6
11, 7
8, 12
9, 13
16, 18
14, 18
10
11
12
13
14
15
16
17
18
c
1
c
2
r
1
r
2
e
c
d
b
a


## 3.3.3. DE

For the mutation operator of DE, if we take an example ofX
r
1
(
t
)
=
a, X
r
2
(
t
)
=
b, X
r
3
(
t
)
=
c, T
=
{
a
,
b
,
c
,
F
}, and O
=
{
+
,
-
,
∗
}, the DE’s mutation equation X
i
(
t
+
1
) could be expressed by an expression tree (phenotype) shown in Figure 3.Figure 3
The expression tree of genetic operator (5) in DE.Here the length of chromosome is 7,T
=
{
a
,
b
,
c
,
F
} and O
=
{
+
,
-
,
∗
}. A kind of equivalent genotype for phenotype could be expressed as shown in Table 3.Table 3
The equivalent genotype of (5) in DE.
1
2
3
4
5
6
7
+
a
∗
F
−
b
c
2, 3
4, 5
6, 7By analysis above, it is evident that for SGA, PSO, and DE, their genetic operators can be expressed by a specific chromosome, respectively. But thestructures of the chromosomes are not changed, orstatic through the whole process of evolutionary run for the three classic evolutionary algorithms. This is generally true also for many other variants of evolutionary algorithms.Now the question is “can automatic programming method automatically construct genetic operators of evolutionary algorithms, where operators were automatically generated in the running process of problem solving, rather than predefined?” As we know, the evolutionary algorithms generally have capabilities of self-organizing, self-adapting, and self-regulating, but their genetic operators are normally predetermined. While the algorithms construed by predetermined operators are effective in certain aspects of problem solving, their performances in addressing other issues may not be so competitive. This phenomenon can be explained to some extent by the famous “No Free Lunch” theory [15]. If there is an algorithm framework, in which the genetic operators can automatically adjust themselves during the problem-solving process with the change of the nature of the problems to be solved, the capabilities of self-organizing, self-adapting, and self-regulating of the algorithms can be further enhanced, and the limit imposed by the “NO Free Lunch” theory may be broken. Peng et al. proposed a population-based algorithm portfolio (PAP) [16], which distributes the time among multiple different algorithms, to decrease the inherent risk associated with the selection of algorithms. However, the algorithms are still predefined in PAP, which is very different compared with our method. In the following, the details of a framework that can automatically design genetic operators in the running process of problem solving will be introduced.


## 4. Evolutionary Algorithm Based on Automatic Designing of Genetic Operators (EA2DGO)

In the framework of Evolutionary Algorithm based on Automatic designing of genetic operators (EA2DGO), the genetic operators are not predefined by a designer before problem solving but are searched and designed in the process of problem solving. Thus, the framework of the EA2DGO consists of two core components: one is the unit of problem solving (e.g., function optimization), which relates to operations in the problem solution space. The object of this unit is set to find global optimal solutions; and the other is the unit of automatically designing genetic operators, which relates to exploration in the space of genetic operators. The object of this unit is set to find the optimal genetic operators according to the requirement of the problem (see Figures 4(a), 4(b), and 4(c)). The unit of function optimization and the unit of automatically designing genetic operators are not isolated. Actually, they work together in a closely related way. In the unit of function optimization, the genetic operators for mutation are selected from the unit of automatically designing genetic operators in the process of problem solving. And in the unit of automatically designing genetic operators, individuals are selected from the function optimization population in the unit of function optimization for evaluating the performance of genetic operators.Figure 4
The components of EA2DGO. (a) The general framework of EA2DGO. (b) The flowchart of the function optimization unit. (c) The flowchart of the unit of automatically designing genetic operators. (d) The interaction relationship between two units.
(a)
(b)
(c)
(d)The general framework of EA2DGO is given in Algorithm 1.Algorithm 1:The general framework of EA2DGO.
(1)
Begin
(2)
Input: NP, NOP, F, CR, OMR, Max_Fes, hl, tl, times, T, and O; where NP denotes the size
of function optimization population; NOP denotes the size of operator generating
population; F denotes scaling factor; CR denotes the probability of crossover; OMR denotes
the probability of Mutation for operators in operator generating population; Max_FEs
denotes the max number of function calls; hl is the of head length of chromosome in new
encoding scheme MEP; tl is the tail length; times denotes the number of repeat times which
randomly select individuals for mutation manipulation from population in unit of function
optimization; T is the terminal symbol set; O is the function symbol set.
(3)  G
=
0
(4)  Create the function optimization population x
→
G
i, ∀
i, i
=
1
,
…
,
NP
(5)  Create the genetic operators population o
→
G
k, ∀
k, k
=
1
,
…
,
NOP
(6)  f
(
o
→
G
k
)
=
0, ∀
k, k
=
1
,
…
,
NOP
(7)  Evaluate f
(
x
→
G
i
), ∀
i, i
=
1
,
…
,
NP
(8)  For  G
=
1 to Max_FES Do
(9)   Find the best x
→
G
best in the function optimization population
(10)     Callthe unit of function optimization
(11)   If  (
rand
[
0,1
)
<
OMR
)  Then
(12)    Call the unit of automatically designing genetic operators
(13)   End If
(14)   G
=
G
+
1
(15)  End For
(16)   Output x
→
G
best
(17)
EndThe unit of function optimization focuses on the finding of global optimal solution, and the framework is given in Algorithm2. According to the framework, we can see that the unit of function optimization is very similar with standard differential evolution, including the population initialization, crossover manipulation, individual fitness assessment, and individual selection. For mutation operator, an individual o
→
G
k, k
∈
[
1
,
NOP
] is selected from the population of operator automatic generating unit according to the Roulette Wheel Selection algorithm, and the selected individual will be used as mutation operator in the unit of function optimization.Algorithm 2:The framework of the unit function optimization.
(1)
Begin
(2)  Suppose the function optimization population is x
→
G
i, ∀
i, i
=
1
,
…
,
NP
(3)  Suppose the operator generating population is o
→
G
k, ∀
k, k
=
1
,
…
,
NOP
(4)  For
i
=
1 to NPDo
(5)    Select randomly r
1
≠
r
2
≠
r
3
≠
i, r
1
,
r
2
,
r
3
∈
[
1
,
NP
]:
(6)    Select o
→
G
k, k
∈
1
,
NOP by Roulette Wheel Selection algorithm
(7)    j
rand
=
randint
1
,
D
(8)    For
j
=
1 to D
Do
(9)       If
(
rand
j
[
0,1
)
<
CR or j
=
j
rand
)
Then
(10)u
j
,
G
+
1
i
=
GeneCalculate
x
→
j
,
G
r
1
,
x
→
j
,
G
r
2
,
x
→
j
,
G
r
3
,
x
→
j
,
G
best
,
o
→
G
k
(11)      Else
(12)
u
→
j
,
G
+
1
i
=
x
→
j
,
G
i
(13)      End If
(14)    End For
(15)    If
(
better(u
→
j
,
G
+
1
i
x
→
j
,
G
i
)
)
Then
(16)      x
→
G
+
1
i
=
u
→
G
+
1
i
(17)      f
o
→
G
k
+
+
(18)    Else
(19)      x
→
G
+
1
i
=
x
→
G
i
(20)    End If
(21)  End For
(22)
EndIn the EA2DGO, the mutation operator is a function model. The functionality of a function model is to provide a corresponding output (result) given a certain input parameters (terminals). The input parameters include x
→
j
,
G
r
1, x
→
j
,
G
r
2, x
→
j
,
G
r
3, x
→
j
,
G
best, and o
→
G
k. x
→
j
,
G
r
1, x
→
j
,
G
r
2, and x
→
j
,
G
r
3 are three individuals selected from the population of function optimization unit randomly. x
→
j
,
G
best is the best individual in the current population. Suppose all the function symbols in set O are binary operators, the calculation of the result of the function model is expressed as shown in Algorithm 3.Algorithm 3:The framework of gene calculation.
(1)
Begin
(2)  Input: x
→
j
,
G
r
1, x
→
j
,
G
r
2, x
→
j
,
G
r
3, x
→
j
,
G
best, o
→
G
k
=
{
o
→
1
,
G
k
,
…
,
o
→
m
,
G
k
}, m is the length of Chromosome, k
=
1
,
…
,
NOP.
(3)  EL
=
1
(4)  For  i
=
1 to m  Do
(5)    If  (o
→
i
,
G
k
∈
O)  Then
(6)      EL
=
EL
+
2
(7)    End If
(8)  End For
(9)  For  i
=
EL to 1  Do
(10)fitnes
s
i
(
o
→
i
,
G
k
)
=
{
x
→
j
,
G
r
1
,
if
(
o
→
i
,
G
k
=
=
x
→
r
1
)
x
→
j
,
G
r
2
,
if
(
o
→
i
,
G
k
=
=
x
→
r
2
)
x
→
j
,
G
r
3
,
if
(
o
→
i
,
G
k
=
=
x
→
r
3
)
x
→
j
,
G
r
best
,
if
(
o
→
i
,
G
k
=
=
x
→
best
)
rand
[
0,1
)
,
if
(
o
→
i
,
G
k
=
=
F
)
(11)  End For
(12)  Calculate the last o
→
i
,
G
l
∈
O, l
∈
[
1
,
EL
]
(13)  For  i
=
EL to 1  Do
(14)    If  (o
→
i
,
G
k
∈
O)  Then
(15)      fitnes
s
i
(
o
→
i
,
G
k
)
=
fitnes
s
i
(
o
→
i
,
G
EL
-
1
)
Θ
o
→
i
,
G
k
fitnes
s
i
(
o
→
i
,
G
EL
), Θ
o
→
i
,
G
k
∈
O
(16)      EL
=
EL
-
2
(17)    End If
(18)  End For
(19)  Return fitnes
s
1
(
o
→
1
,
G
k
)
(20)
EndIn the unit of function optimization, when the selected chromosomeo
→
G
k, namely, the genetic operator, can help function optimization unit generate a better candidate individual, the fitness value of chromosome o
→
G
k will be increased by one. In other words, the fitness of a chromosome in the unit of automatically designing genetic operators is measured by the times it has made positive effect for the unit of function optimization. With this measurement, in the next generation, the chromosomes with higher fitness will with a higher probability be selected as the genetic operators according to the Roulette Wheel Selection method (see Algorithm 4).Algorithm 4:Roulette Wheel selection algorithm.
(1)
Begin
(2)  Calculate probability for each chromosome p
(
o
→
G
k
)
=
f
(
o
→
G
k
)
/
∑
k
=
1
NOP
f
(
o
→
G
k
), k
∈
[
1
,
NOP
]
(3)  For  k
=
1 to NOP
-
1  Do
(4)     P
(
o
→
G
k
+
1
)
=
p
(
o
→
G
k
)
+
p
(
o
→
G
k
-
1
)
(5)  End For
(6)  If  (P
(
o
→
G
k
)
≤
rand
[
0,1
)
≤
P
(
o
→
G
k
+
1
))  Then
(6)  o
→
G
k is selected for FunctionOptimization
(8)  End If
(9)  Return  o
→
G
k
(10)EndThe evolution of chromosome in the unit of automatically designing genetic operators presents challenges in the general framework of the automation of EA. The proposed method is for the individualo
→
G
k as well as its offspring o
→
G
′
k in the unit of automatically designing genetic operators, within a certain time (which is a parameter that can be set by the user); we repeatedly select individuals for mutation manipulation from the population of the unit of function optimization then count the times that the fitness of child becomes better than its parent, denoted by ST
(
o
→
G
k
) and ST
(
o
→
G
′
k
), respectively. A Boolean function better is defined as the fitness for evolution of genetic operators:(6)
Better
(
o
→
G
k
,
o
→
G
′
k
)
=
true
,
if
ST
o
→
G
k
<
ST
o
→
G
′
k
,
false
,
else
.IfBetter
(
o
→
G
k
,
o
→
G
′
k
) is true, we think that the candidate o
→
G
′
k is better than o
→
G
k, and o
→
G
k is replaced by o
→
G
′
k.The offspringo
→
G
′
k is generated by MEP genetic manipulations [8]. While the traditional MEP has both crossover and mutation operators, only the mutation operator is used in EA2DGO for simplicity and saving computing time. Each symbol (terminal, function, and function pointer) in the chromosome may be a target of the mutation operator. When a symbol is changed, a new offspring is generated.Although the evolution method motioned above can get access to the genetic operators before and after MEP genetic manipulation, an unavoidable disadvantage of this method is that it costs more computing resources compared with traditional optimization algorithms. The reason is that the genetic operators need to be evolved in the process of problem solving. The cost of time is influenced by two parameters times and OMR. Setting proper parameter values will reduce the cost of time and will be researched in the future work.It is worthwhile to point out that even though there is a mutation operator, respectively, in both the unit of automatically designing genetic operator and the unit of function optimization, their operations are very different. In the unit of automatically designing genetic operator, the operand/chromosome of the mutation operator is literally an expression tree. In contrast, the operand/chromosome of the mutation operator in the unit of function optimization is a vector of real values used as variables for the function optimization.The general framework of the unit of automatically designing genetic operators is given in Algorithm5.Algorithm 5:The framework of the unit of automatically designing genetic operators.
(1)
Begin
(2)  Input: o
→
G
k = {
o
→
1
,
G
k
,
…
,
o
→
m
,
G
k
}, k
∈
[
1
,
NOP
];
(3)  Select randomly t, t
∈
[
1
,
m
]:
(4)  Select a new operator to o
→
t
,
G
k which will generate a new chromosome o
→
G
′
k by MEP genetic operators.
(5)  For
i
=
1 to timesDo
(6)    Select randomly r
1
≠
r
2
≠
r
3
≠
r, r
,
r
1
,
r
2
,
r
3
∈
[
1
,
NP
]:
(7)    j
rand
=
randint
1
,
D
(8)    For
j
=
1 to D
Do
(9)       If(rand
j
[
0,1
)
<
CR or j
=
j
rand)Then
(10)u
→
j
,
G
r
=
GeneCalculate
x
→
j
,
G
r
1
,
x
→
j
,
G
r
2
,
x
→
j
,
G
r
3
,
x
→
j
,
G
best
,
o
→
G
k
(11)ν
→
j
,
G
r
=
GeneCalculate
x
→
j
,
G
r
1
,
x
→
j
,
G
r
2
,
x
→
j
,
G
r
3
,
x
→
j
,
G
best
,
o
→
G
′
k
(12)       Else
(13)        u
→
j
,
G
r
=
ν
→
j
,
G
r
=
x
→
j
,
G
r
(14)       End If
(15)    End For
(16)    If
u
→
j
,
G
r is better than x
→
j
,
G
r
Then
(17)       ST
o
→
G
k
+
+
(18)    End If
(19)    If
ν
→
j
,
G
r is better than x
→
j
,
G
r
Then
(20)       ST
o
→
G
′
k
+
+
(21)    End If
(22)  End For
(22)  If
(Better
(
o
→
G
k
,
o
→
G
′
k
)
)  Then
(24)  o
→
G
+
1
k
=
o
→
G
′
k
(25)  Else
(26)  o
→
G
+
1
k
=
o
→
G
k
(27)  End If
(28)
End


## 5. Experimental Verification

Single-objective optimization problems are adopted to verify the validity of the EA2DGO algorithm. This means that the genetic operators represented by the above scheme are used to manipulate the individuals in the population in the problem space, and the goal is to find the global optimal solutions of the problems. All the following functions listed in Table 4 are well-known benchmark functions which have been frequently used in literature [17]. All of these functions used in this paper are minimization problems. In order to verify the effectiveness and efficiency of EA2DGO algorithm, we carried out experiments based on the 23 benchmark functions list in Table 4.Table 4
The 23 test functions used in the experiments,X is the definition domain and f
min
⁡ is the minimum values of the function.
Number
Test functions
n
X
f
min
⁡
F1
f
(
x
)
=
∑
i
=
1
D
x
i
2
30
[
-
100,100
]
0
F2
f
(
x
)
=
∑
i
=
1
D
|
x
i
|
+
∏
i
=
1
D
|
x
i
|
30
[
-
10,10
]
0
F3
f
(
x
)
=
∑
i
=
1
D
(
∑
j
=
1
i
x
j
)
2
30
[
-
100,100
]
0
F4
f
(
x
)
=
max
⁡
{
|
x
i
|
,
1
≤
i
≤
D
}
30
[
-
100,100
]
0
F5
f
(
x
)
=
∑
i
=
1
D
-
1
[
100
(
x
i
+
1
-
x
i
2
)
2
+
(
1
-
x
i
)
2
]
30
[
-
30,30
]
0
F6
f
(
x
)
=
∑
i
=
1
D
(
⌊
x
i
+
0.5
⌋
)
2
30
[
-
100,100
]
0
F7
f
(
x
)
=
∑
i
=
1
D
i
x
i
4
+
random
[
0,1
)
30
[
-
1.28,1.28
]
0
F8
f
(
x
)
=
-
∑
i
=
1
D
(
x
i
sin
⁡
⁡
|
x
i
|
)
30
[
-
500,500
]
−12569.5
F9
f
(
x
)
=
∑
i
=
1
D
[
x
i
2
-
10
cos
⁡
(
2
π
x
i
)
+
10
]
30
[
-
5.12,5.12
]
0
F10
f
(
x
)
=
-
20
exp
⁡
(
-
0.2
1
n
∑
i
=
1
D
x
i
2
)
-
exp
⁡
(
1
n
∑
i
=
1
D
cos
⁡
(
2
π
x
i
)
)
+
20
+
e
30
[
-
32,32
]
0
F11
f
(
x
)
=
∑
i
=
1
D
x
i
2
4000
-
∏
i
=
1
D
cos
⁡
(
x
i
i
)
+
1
30
[
-
600,600
]
0
F12
f
(
x
)
=
π
n
{
10
sin
⁡
2
⁡
(
π
y
i
)
+
∑
i
=
1
D
-
1
(
y
i
-
1
)
2
[
1
+
10
sin
⁡
2
⁡
(
π
y
i
+
1
)
]
+
(
y
n
-
1
)
2
}    +
∑
i
=
1
D
u
(
x
i
,
10,100,4
), y
i
=
1
+
1
4
(
x
i
+
1
)
u
(
x
i
,
a
,
k
,
m
)
=
{
k
(
x
i
-
a
)
m
,
x
i
>
a
0
,
-
a
≤
x
i
≤
a
,
k
(
-
x
i
-
a
)
m
,
x
i
<
-
a
30
[
-
50,50
]
0
F13
f
(
x
)
=
0.1
{
sin
⁡
⁡
2
(
3
π
x
1
)
+
∑
i
=
1
D
-
1
(
x
i
-
1
)
2
[
1
+
sin
⁡
⁡
2
(
3
π
x
i
+
1
)
]
+(
x
n
-
1
)
2
[
1
+
sin
⁡
⁡
2
(
2
π
x
D
)
]
}
+
∑
i
=
1
D
u
(
x
i
,
5,100,4
)
30
[
-
50,50
]
0
F14
f
(
x
)
=
[
1
500
+
∑
j
=
1
25
1
j
+
∑
i
=
1
2
(
x
i
-
a
i
j
)
6
]
2
[
-
65.536,65.536
]
1
F15
f
(
x
)
=
∑
i
=
1
11
[
a
i
-
x
1
(
b
i
2
+
b
i
x
2
)
b
i
2
+
b
i
x
3
+
x
4
]
2
4
[
-
5,5
]
0.0003075
F16
f
(
x
)
=
4
x
1
2
-
2.1
x
1
4
+
1
3
x
1
6
+
x
1
x
2
-
4
x
2
2
+
4
2
4
2
[
-
5,5
]
−1.0316285
F17
f
(
x
)
=
(
x
2
-
5.1
4
π
2
x
1
2
+
5
π
x
1
-
6
)
2
+
10
(
1
-
1
8
π
)
cos
⁡
x
1
+
10
2
[
-
5,10
]
×
[
0,15
]
0.398
F18
f
(
x
)
=
[
1
+
(
x
1
+
x
2
+
1
)
2
(
19
-
14
x
1
+
3
x
1
2
-
14
x
2
+
6
x
1
x
2
+
3
x
2
2
)
]
×
[
30
+
(
2
x
1
-
3
x
2
)
2
(
18
-
32
x
1
+
12
x
1
2
+
48
x
2
-
36
x
1
x
2
+
27
x
2
2
)
]
2
[
-
2,2
]
3
F19
f
(
x
)
=
-
∑
i
=
1
4
c
i
exp
⁡
[
-
∑
j
=
1
4
a
i
j
(
x
j
-
p
i
j
)
2
]
4
[
0,1
]
−3.86
F20
f
(
x
)
=
-
∑
i
=
1
4
c
i
exp
⁡
[
-
∑
j
=
1
6
a
i
j
(
x
j
-
p
i
j
)
2
]
6
[
0,1
]
−3.32
F21
f
(
x
)
=
-
∑
i
=
1
5
[
(
x
-
a
i
)
(
x
-
a
i
)
T
+
c
i
]
-
1
4
[
0,10
]
−10
F22
f
(
x
)
=
-
∑
i
=
1
7
[
(
x
-
a
i
)
(
x
-
a
i
)
T
+
c
i
]
-
1
4
[
0,10
]
−10
F23
f
(
x
)
=
-
∑
i
=
1
10
[
(
x
-
a
i
)
(
x
-
a
i
)
T
+
c
i
]
-
1
4
[
0,10
]
−10In our experiment, the parameters are set as in Table5. Especially in T, a is x
→
j
,
G
r
1, b is x
→
j
,
G
r
2, c is x
→
j
,
G
r
3, d is x
→
j
,
G
best, and F
=
Random
(
0,1
). In order to verify the performance of the proposed algorithm, standard DE algorithm is conducted. In DE algorithm, NP
=
100, F
=
0.7, CR
=
0.8, and Max
⁡
_
FEs
=
250000. The obtained results are presented in Table 5. Simulation was carried out in Eclipse and run on an AMD laptop with 2 G RAM under Windows XP platform. For each test problem, 25 independent runs were conducted with different random initializations.Table 5
Parameters setting used in EA2DGO algorithm
The unit of function optimization
NP
100
CR
0.8
Max_FEs
250000
The unit of automatically designing genetic operators
NOP
5
h
5
t
6
L
11
Times
50
T
{a, b, c, d, F}
O
{
+, −, *}The results on functions F1 to F23 are summarized in Table6. For functions F1–F5, F7, and F9–F11, the EA2DGO achieved better mean results than DE. For functions F6, F12–F14, and F16–F23, both algorithms obtain exactly the same mean results. DE achieved better mean results in function F8 and F15. For F15, while the mean result of the EA2DGO is close to that of DE, both algorithms have the ability to achieve the best solution. The biggest difficulty of EA2DGO is from the function F8, for which DE can easily obtain the global minima but the new algorithm presented in this paper frequently falls into the local minima. The reason for this needs further investigation.Table 6
The results achieved for F1 to F23 using the EA2DGO algorithm and DE algorithm.
EA2DGO
DE
Best
Median
Worst
Mean
Standard
F1
0.0
0.0
0.0
0.0
0.0
2.3
8
E
-
90
7.5
8
E
-
89
3
.
90
E
-
88
1.0
7
E
-
88
9.2
2
E
-
89
F2
0.0
0.0
0.0
0.0
0.0
3.07
E
-
52
1.0
E
-
51
6.34
E
-
51
1.3
6
E
-
51
1.17
E
-
51
F3
0.0
0.0
0.0
0.0
0.0
9.84
E
-
87
1
.
8
E
-
85
6.8
E
-
85
2.23
E
-
85
1
.
7
E
-
85
F4
0.0
0.0
0.0
0.0
0.0
1.349
9.494
13.075
8.293
2.836
F5
0.0
22.117
29.0
13.001
10.839
1.810
18.356
71.343
23.886
14.486
F6
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
F7
3.7
4
E
-
5
8.61
E
-
5
1
.
78
E
-
3
8.82E−4
4.26
E
-
4
2.1
E
-
3
3.3
E
-
3
4.76
E
-
3
3.3
E
-
3
5.8
1
E
-
4
F8
-
12569.48
7
-
11858.85
6
-
5897.496
-
10864.79
1755.355
−12569.487
−12451.048
−12095.733
−12419.463
118.28
F9
0.0
0.0
0.0
0.0
0.0
0.0
1.99
6.96
2.12
1.32
F10
4.44
1
E
-
16
4.44
1
E
-
16
4.44
1
E
-
16
4.441E−16
0.0
4.0
E
-
15
7.55
E
-
15
7.55
E
-
15
5.89
E
-
15
1.37
E
-
15
F11
0.0
0.0
0.0
0.0
0.0
0.0
0.0
7.4
E
-
3
4.93
E
-
4
1.43
E
-
3
F12
1.57
1
E
-
32
1.57
1
E
-
32
1.57
1
E
-
32
1.571E − 32
0.0
1.57
1
E
-
32
1.57
1
E
-
32
1.57
1
E
-
32
1.571E − 32
0.0
F13
1
.
35
E
-
32
1
.
35
E
-
32
1
.
35
E
-
32
1.35E − 32
0.0
1
.
35
E
-
32
1
.
35
E
-
32
1
.
35
E
-
32
1.35E − 32
0.0
F14
0.998
0.998
0.998
0.998
3.2
E
-
8
0.998
0.998
0.998
0.998
8.6
E
-
17
F15
3.07
5
E
-
4
3.07
5
E
-
4
1.791
E
-
3
4.496
E
-
4
1.024
E
-
4
3.07
5
E
-
4
3.07
5
E
-
4
1.22
E
-
3
3.69E − 4
1.77
E
-
4
F16
-
1.0316
3
-
1.0316
3
-
1.0316
3
−1.03163
0.0
−1.03163
−1.03163
−1.03163
−1.03163
0.0
F17
0.398
0.398
0.398
0.398
1
.
715
E
-
4
0.398
0.398
0.398
0.398
0.0
F18
3
3
3
3
2.045
E
-
14
3
3
3
3
6
.
88
E
-
16
F19
-
3.86
-
3.86
-
3.86
−3.86
2.66
E
-
9
−3.86
−3.86
−3.86
−3.86
9.25
E
-
13
F20
-
3.32
-
3.32
-
3.32
−3.32
4.79
E
-
7
−3.32
−3.32
−3.32
−3.32
6.27
E
-
12
F21
-
10.153
-
10.153
-
10.153
−10.153
1.01
E
-
9
−10.153
−10.153
−10.153
−10.153
1.38
E
-
15
F22
-
10.40
3
-
10.40
3
-
10.40
3
−10.403
2.59
E
-
9
−10.403
−10.403
−10.403
−10.403
1.38
E
-
15
F23
-
10.536
-
10.536
-
10.536
−10.536
1.03
E
-
9
−10.536
−10.536
−10.536
−10.536
1.85
E
-
15For the best results, the EA2DGO achieved better results than DE in 8 functions and obtained the same best results in the reminded 15 functions. For the median results, the EA2DGO achieved better results than DE in 7 functions and obtained the same median results in 14 functions. DE achieved better median results in functions F5 and F8. For the worst results, the EA2DGO achieved better results than DE in 9 functions and obtained the same median results in 12 functions. DE achieved better median results in 2 functions, which are F8 and F15.The convergence comparisons between the EA2DGO and DE are shown in Algorithm 5. For simplicity, each Figure shows the result of a random trial. Because of space limitation, just some samples (F1~F10) are selected and presented. According to Figure 5, we can find that EA2DGO converges more quickly than DE in every trail, except for F8 when the two algorithms converge almost through the same curve.Figure 5
Convergence curves of the EA2DGO and DE for partial test functions. x-axis represents number of function calls and y-axis represents the best fitness. (a) F1. (b) F2. (c) F3. (d) F4. (e) F5. (f) F6. (g) F7. (h) F8. (i) F9. (j) F10.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)In order to better understand the internal operating mechanism of EA2DGO, the following experiment is designed. Take F7 for example, the 50,000 function calls are shown in Figure 6, wherein the horizontal axis represents the number of calls, and the vertical axis represents the optimal solutions found so far. The 50,000 calls are divided into five stages of assessment (Phase I~V). Phase I represents the 0~50 calls, Phase II represents the 51~12,500 calls, Phase III represents 12,501~25,000 calls, Phase IV represents 25,001~37,500 calls, and Phase V is the last 37,501~50,000 calls. After 50,000 evaluations, the best optimal solution we found for F7 is 1.50
E
-
6. In Phase I, totally 39 effective evaluations are obtained, which means 39 new child candidates replace the parents.Figure 6
Phases I~V in one run for F7.For each stage we use a pie chart to represent the success rate of every genetic operator in the population of genetic operators in the unit of automatically designing genetic operators (such as in Table7, for first genetic operator in Phase I, the success rate is 5% and the totally effective evaluations are 39, which means that there are two useful candidates are generated by first genetic operator and then go into the population in the unit of function optimization).Table 7
The detail information in Phases I~V.
Phase
Formula
Success rate
Totally effective evaluations
I
U
G
+
1
i
=
X
→
G
best
X
→
G
r
1
-
X
→
G
r
1
5%
39
U
G
+
1
i
=
X
→
G
r
2
(
F
+
X
→
G
r
2
)
72%
U
G
+
1
i
=
X
→
G
r
2
8%
U
G
+
1
i
=
(
X
→
G
r
1
X
→
G
r
1
-
2
X
→
G
best
)
(
X
→
G
best
-
X
→
G
r
1
)
2%
U
G
+
1
i
=
X
→
G
r
2
(
X
→
G
r
1
-
X
→
G
r
2
)
13%
II
U
G
+
1
i
=
X
→
G
r
1
X
→
G
r
1
+
X
→
G
best
X
→
G
best
X
→
G
r
1
-
X
→
G
r
1
X
→
G
best
20%
434
U
G
+
1
i
=
X
→
G
r
1
+
X
→
G
r
2
X
→
G
r
2
26%
U
G
+
1
i
=
X
→
G
r
2
X
→
G
r
2
X
→
G
r
2
X
→
G
r
2
18%
U
G
+
1
i
=
6
X
→
G
r
2
X
→
G
r
2
X
→
G
r
2
17%
U
G
+
1
i
=
F
X
→
G
r
2
+
X
→
G
r
1
-
X
→
G
r
1
X
→
G
r
1
19%
III
U
G
+
1
i
=
X
→
G
r
1
-
X
→
G
r
2
X
→
G
r
2
6%
194
U
G
+
1
i
=
F
X
→
G
r
2
+
X
→
G
best
70%
U
G
+
1
i
=
X
→
G
best
-
X
→
G
r
1
16%
U
G
+
1
i
=
6
X
→
G
r
2
X
→
G
r
2
X
→
G
r
2
4%
U
G
+
1
i
=
X
→
G
best
+
X
→
G
r
1
-
X
→
G
r
1
X
→
G
r
1
4%
IV
U
G
+
1
i
=
X
→
G
r
1
-
X
→
G
r
2
X
→
G
r
2
4%
57
U
G
+
1
i
=
-
X
→
G
r
2
X
→
G
r
2
26%
U
G
+
1
i
=
X
→
G
best
-
X
→
G
best
X
→
G
best
60%
U
G
+
1
i
=
F
X
→
G
best
5%
U
G
+
1
i
=
X
→
G
r
1
X
→
G
r
1
5%
V
U
G
+
1
i
=
X
→
G
r
1
-
X
→
G
r
2
X
→
G
r
2
12%
41
U
G
+
1
i
=
X
→
G
best
X
→
G
r
2
44%
U
G
+
1
i
=
X
→
G
r
3
-
X
→
G
best
42%
U
G
+
1
i
=
F
X
→
G
best
2%
U
G
+
1
i
=
X
→
G
r
1
X
→
G
r
1
0%In Phase I, it is obvious that the second genetic operator, which isU
G
+
1
i
=
X
→
G
r
2
(
F
+
X
→
G
r
2
) in operator generating population, produces more new candidates. In the beginning of evolution, the algorithm generates the new candidates easily and quickly, so we set a small number of function calls in Phase I. In Phase II, all the genetic operators have achieved comparable performance. In Phase III, the second operator demonstrates a stronger genetic capability; the phenotype of this genotype is  U
G
+
1
i
=
F
X
→
G
r
2
+
X
→
G
best (see Table 7). In Phase VI, the best performance genotype is U
G
+
1
i
=
X
→
G
best
-
X
→
G
best
X
→
G
best. The common characteristics of these two formulas are that they both apply the current best individual in the population X
→
G
best, which indicates that searching in vicinity of the best individual can improve the convergence efficiency. In Phase V, only 41 effective evaluations are achieved in 12,500 function calls, and the 4th and 5th genetic operators only produce one and zero effective candidate, respectively. This means that the searching of operators in the unit of automatically designing genetic operators gradually converges to those genetic operators that are hard to be further improved. The reason for that is, as mentioned above, the unit of function optimization and the unit of automatically designing genetic operators work together. When the function optimization population gradually converges to the global optimal solutions, the evolution of the genetic operator population is also led to a convergence.According to the experiment, the genetic operator that produces more effective individuals does not necessarily produce the best individual. In this experiment, the first genetic operator in Phase V obtains the best performance in the 50,000 calls, whose phenotype isU
G
+
1
i
=
X
→
G
r
1
-
X
→
G
r
2
X
→
G
r
2.


## 6. Conclusions

A novel evolutionary algorithm based on automatic designing of genetic operators is presented to tentatively solve algorithm designed problem automatically. EA2DGO does not only search in the problem solution space, but also explore in the space of genetic operators, which means that the genetic operators are not predefined by a designer before problem solving but searched and designed automatically in the process of problem solving.Experimental results have shown that the EA2DGO can achieve comparable performance with the state-of-art algorithm such as DE. However, many more issues deserve to be investigated for this potential algorithm. For example, at this stage, there are still quite a few parameters involved in the algorithm framework. As a result, parameter analysis becomes naturally a next step of study. Meanwhile, how to set up these parameters optimally (or even reduce some parameters) is an issue worth to be further studied. In addition, it is very interesting and desirable to investigate methods to define some important metrics for this new algorithm, such as evolvability, adaptability, and computational complexity.



---

*Source: 474805-2015-04-21.xml*