1. Description
In order to construct the neural network using grammatical evolution, the network itself has to be expressed using the BNF grammar. A two-layer network can be expressed as
where H is the total number of processing units (hidden nodes) of the neural network and and d stands for the dimension of the objective problem which are the number of elements of vector x . Also we define as w the weight vector of the neural network. The sigmoid function σ(x) is defined as: σ(x)=1/(1+exp(-x))
Grammatical evolution is an evolutionary algorithm that can produce code in any programming language. The algorithm requires as inputs the BNF grammar definition of the target language and the appropriate fitness function. Chromosomes in grammatical evolution, in contrast to classical genetic programming [2], are not expressed as parse trees, but as vectors of integers. Each integer denotes a production rule from the BNF grammar. The algorithm starts from the start symbol of the grammar and gradually creates the program string, by replacing non terminal symbols with the right hand of the selected production rule. The selection is performed in two steps:
• We read an element from the chromosome (with value V).
• We select the rule according to the scheme
Rule=V mod NR
where NR is the number of rules for the specific non-terminal symbol. The process of replacing non terminal symbols with the right hand of production rules is continued until either a full program has been generated or the end of chromosome has been reached. In the latter case we can reject the entire chromosome or we can start over (wrapping event) from the first element of the chromosome. In our approach we allow at most two wrapping events to occur.
Each neural network N(x) is constructed from a chromosome through the grammar displayed in the following figure
The numbers in parentheses denote the sequence number of the corresponding production rule to be used in the selection procedure described above.
The main steps of the algorithm are:
- Initialization step.
(a) Set g as the maximum number of generations and c as the number of chromosomes in the population.
(b) Set Ps as the selection rate and Pm as the mutation rate. (d) Set Li the number of generations that should pass before the local search procedure is applied.
(e) Set Lc the number of chromosomes that will participate in local search procedure
(f) Set iter=0
(g) Initialize the chromosomes as random vectors of integers.
- Genetic step
(a) For i=1,...,g do
i. Create for every chromosome a neural network C(i) with grammatical evolution.
ii. Calculate the fitness f(i) for every chromosome using the procedure described in Section 5. iii. Apply the genetic operations of crossover and mutation: The chromosomes are sorted in descending order according to their fitness value. The first (1-Ps)c chromosomes are copied intact to the next generations. The rest of the chromosomes are produced using tournament selection, one - point crossover and mutation. During mutation for every element in each chromosome a random number r in range [0,1] is produced. If r<=Pm then the corresponding element is randomly changed.
(b) EndFor 3. Local Search Step
(a) If iters mod Li=0 Then
i. Select randomly Lc chromosomes from the genetic population and create the set LS from these chromosomes
ii. For every X(i) in LS
- Select randomly a Y from the population 2)Create an offspring Z of X(i) and Y using one point crossover.
- If f(z)<f(x(i)) then X(i)=Z, f(x(i))=f(Z)
-
- set iter=iter+1. If iter>itermax terminate else goto Genetic step.
-
Evaluation step
(a) Create a neural network for the best chromosome.
(b) Evaluate the neural network either in some classification/regression dataset either in some Differential Equation and report the results