Hybrid Genetic Algorithm for Heterogeneous Recurrent Neural Networks Construction

Presentation of the Continual Evolution Algorithm

Zdeněk Buk and Miroslav Šnorek
bukz1@fel.cvut.cz, http://cig.felk.cvut.cz

({{, }})

Department of Computer Science and Engineering, FEE
Czech Technical University in Prague

Introduction

Neural Networks

Adaptable, nature inspired, robust computational structures.

Ability to adapt (learn) to the specific problem (data).

Typical tasks:

Classification

Clustering

Regression

Rule Generation

Time Series Analysis, ...

({{, }})

Genetic Algorithms

Nature inspired optimization methods based on population of individuals evolution where each individual represents one solution of given problem.

Encoding of individuals

Representation of population

Crossover and mutation operators

Fitness function (quality of individuals)

Hybrid Genetic Algorithm

Combination of Evolutionary Algorithms and Local Search methods.

Local search - e.g. gradient - based optimization

Example : Genetic algorithm + backpropagation algorithm

Finding a structure and weight settings of neural networks

Complete network evolution

Continual Evolution Algorithm

Hybrid genetic algorithm with the sequential replacements of individual in population.

Variable population size - each individual has an age parameter

Separate Encoding of Structure and Behaviour

Structure encoding

Behavior encoding

Probability and Balancing Control Functions

Reproduction and Death probability (based on fitness and age)

({{, }})

Balancing functions (based on DP or RP and size of the population)

({{, }})

Algortihm

1. Initialization
2. Repeat until stop condition
	2.1. Evaluate all individuals
	2.2. Reproduction of individuals with respect to the RP((Subscript[(OverBar[x]), i]))
	2.3. Elimination of individuals with respect to the DP((Subscript[(OverBar[x]), i])) 
	2.4. Adaptation of the parametrical vector of each individual
	2.5. Update working parameters and age parameter of individuals
3. The result processing

Example of the population evolution

Large population

With and without elitism

Application Package - SoftCom.m

Mathematica Package

Implementation of CEA Algorithm

Implementation of Fully Recurrent Neural Networks

Probability and balancing functions

CEARawDP[a_, f_]
CEARawRP[a_, f_]

CEABalDP[n_, dp_]
CEABalRP[n_, rp_]

CEA Initialization

CEAInitialize[template_, opts___]

CEA Evolution Control

CEAReproduction[alg_, dataX_, dataY_, opts___]

CEAGetIndividualsOrderedByFitness[alg_]

CEA Evolution Internal Functions

CEACrossoverS1[ind1_, ind2_]  (* Simple-1 *)

This function is used for crossover the individuals (neural networks) with all the activation functions same.

CEACrossoverHN1[ind1_, ind2_] (* Heterogeneous-Neurons-1 *)

This function is used for individuals with heterogeneous units, it works with two individuals and returns their offspring - new individual to be added into the population.

CEA Debug

CEAPrintPopulation[alg_]

FRNNet Initialization

FRNNetInitialize[nInputs_, nNeurons_, opts___]
FRNNetInitializeFromCEAIndividual[cea_, index_]
FRNNetInitializeFromCEAIndividual[ind_]

FRNNet Training

FRNNetFit[model_, x_, y_, opts___]

FRNNet Settings

FRNNetImportWeightMatrix[net_, w_]

FRNNetExportWeightMatrix[net_]
FRNNetExportDynamicsMatrix[net_]

FRNNetGetActivationFunctions[net_]
FRNNetSetActivationFunctions[net_, {fn1, fn2, ...}]

FRNNet Visualization

FRNNetPlot[net_]

Example - SoftCom.m

Needs["SoftCom`"]

Initial Population

net=FRNNetInitialize[0, 3]

cea=CEAInitialize[net,PopulationSize->{4,5,20},HeterogeneousUnits->True,Elitism->4,ResetAgeOfBestIndividual->True]

CEAPrintPopulation[cea]

FRNNetPlot[FRNNetInitializeFromCEAIndividual[#]]&/@cea[[1]]

Training Data Set

len=10;
xx=Table[{},{len}]
yy=Table[{Mod[i+1,2]},{i,len}]

nety=First/@net[xx];

Show[ListLinePlot[{nety,#[[1]]&/@yy},PlotRange->All,Frame->True,Axes->False],ListPlot[{nety,#[[1]]&/@yy},AxesOrigin->{0,0},Axes->False,PlotRange->All,Filling->Axis,Frame->True,PlotStyle->PointSize[0.02]],ImageSize->400]

Evolution Process

AbsoluteTiming[cea2=CEAReproduction[cea,xx,yy]]

CEAPrintPopulation[cea2]

best={};
worst={};
iter=0;
numIter=50;
ProgressIndicator[Dynamic[iter],{0,numIter},ImageSize->{300,20}]
AbsoluteTiming[
cea3=Nest[
(iter++;list=CEAGetIndividualsOrderedByFitness[#];
best=Append[best,First[list][[5]]];
worst=Append[worst,Last[list][[5]]];
CEAReproduction[#,xx,yy])&,cea,numIter];
]
best=Drop[best,1];worst=Drop[worst,1];

CEAPrintPopulation[cea3]

ListLinePlot[best,PlotStyle->Thick,Frame->True,PlotRange->All]

net2=FRNNetInitializeFromCEAIndividual[CEAGetIndividualsOrderedByFitness[cea3][[1]]]

nety2=First/@net2[xx];

Show[ListLinePlot[{nety2,#[[1]]&/@yy},PlotRange->All,Frame->True,Axes->False],ListPlot[{nety2,#[[1]]&/@yy},AxesOrigin->{0,0},Axes->False,PlotRange->All,Filling->Axis,Frame->True,PlotStyle->PointSize[0.02]],ImageSize->400]

FRNNetPlot[net2]

Current and future work

Looking for an effective encoding of neural networks.

Encoding of topology

Encoding of activation functions

Effective with respect to the mutation and crossover operator

Scalability - encoding of large networks

Direct encoding

Adjacency matrix for topology encoding

Parametrized Λ-functions for activation functions encoding

activationFunctions = {
{ (*Sigmoid*)
1/(1+Exp[-l*#])&,
{{l,Real,{0.1,10},1}}
},
{ (* Periodic Sin-Sigmoid *)
1 / (1 + Exp[-s(Sin[r*#])])&,
{{s, Real, {1, 10}, 5},
{r, Real, {0, 10}, 1}}
} (* , .... *)
} (* end of function prototypes list *)

setParameters[f_]:=f[[1]]/.(#[[1]]->Random@@#[[2;;3]]&/@f[[2]])

setParameters/@activationFunctions

Compositional Pattern-Producing Networks (CPPN)

Kenneth O. Stanley (2007). "Compositional Pattern Producing Networks: A Novel Abstraction of Development". Genetic Programming and Evolvable Machines Special Issue on Developmental Systems 8 (2): 131-162.

Neural networks for encoding topology of neural networks.

Hyper NEAT

Genetic programming for CPPN

Direct encoding of expressions for generating the topology of networks.

2-dimensional networks topology encoded using 4-dimensional functions.

(Parts of code from: C. Jacob, Illustrating Evolutionary Computation with Mathematica. Morgan Kaufmann Publishers, San Fancisco, 2001)

randomExpression[depth_?Positive,pat_Blank,patterns_,atoms_]:=
Module[{p},
p=RandomChoice[Cases[patterns,pat]];
If[AtomQ[p],
p,
Map[randomExpression[depth-1,#,patterns,atoms]&,p]
]
]
randomExpression[0,pat_Blank,patterns_,atoms_]:=
RandomChoice[Cases[atoms,pat]]
randomExpression[depth_?Positive,pat_BlankSequence,patterns_,atoms_]:=
Sequence@@Table[randomExpression[depth-1,_,patterns,atoms],{RandomInteger[{1,5}]}]
randomExpression[0,pat_BlankSequence,patterns_,atoms_]:=
Sequence@@Table[RandomChoice[Cases[atoms,_]],{RandomInteger[{1,5}]}]
randomExpression[depth_?Positive,pat_BlankNullSequence,patterns_,atoms_]:=
Sequence@@Table[randomExpression[depth-1,_,patterns,atoms],{RandomInteger[{0,5}]}]
randomExpression[0,pat_BlankNullSequence,patterns_,atoms_]:=
Sequence@@Table[RandomChoice[Cases[atoms,_]],{RandomInteger[{0,5}]}]
SetAttributes[randomExpression,HoldRest]

net1[f_,n_,t_]:=Module[{d,p},
d=Table[N[f[i,j,k,l]],{i,-1,1,2/(n-1)},{j,-1,1,2/(n-1)},{k,-1,1,2/(n-1)},{l,-1,1,2/(n-1)}];
Grid[Table[ArrayPlot[d[[i,j]],ColorFunction->Function[{a},ColorData["TemperatureMap"][(a+1)/2]],ColorFunctionScaling->False(*,ImageSize->30*)],{i,n},{j,n}]]
]

net2[f_,n_,t_]:=Module[{d,d2,g1,g2,p,p2,v},
d=Table[N[f[i,j,k,l]],{i,-1,1,2/(n-1)},{j,-1,1,2/(n-1)},{k,-1,1,2/(n-1)},{l,-1,1,2/(n-1)}];
p2=Flatten[Table[{{"s",i,j}->{"t",k,l},d[[i,j]][[k,l]]},{i,n},{j,n},{k,n},{l,n}],3];
v=Join[
Flatten[Table[{{"s",i,j}->{i,0,j}},{i,n},{j,n}],3],
Flatten[Table[{{"t",i,j}->{i,2n/3,j}},{i,n},{j,n}],3]
];
p=DeleteCases[p2,{__->__,_?(Abs[#]<t&)}];
GraphPlot3D[p,MultiedgeStyle->True,VertexCoordinateRules->v,EdgeRenderingFunction->({(*GrayLevel[1-(#3+1)/2]*)(*Directive[Opacity[1-(#3+1)/2]],*)Black,Line[#1]}&),VertexRenderingFunction->(({If[#1[[2]]==0,Orange,Blue],Sphere[#1,.15]})&),ImageSize->300]
]

functions:={plus[__],power[_,_],times[__],sin[_],cos[_]};
terminals:={x1,x2,y1,y2,RandomReal[{-1,1}]};
functionsAndTerminals=functions~Join~terminals

e=randomExpression[7,_,functionsAndTerminals,terminals];
expr=e/.{plus->Plus,power->Power,times->Times,sin->Sin,cos->Cos}

TreeForm[e]

f[x1a_,y1a_,x2a_,y2a_]:=Evaluate[expr/.{x1->x1a,x2->x2a,y1->y1a,y2->y2a}]

GraphicsGrid[List@@net1[f,8,0.5][[1]],ImageSize->300]

Grid[{Table[Show[net2[f,n,0.5],ImageSize->160],{n,{2,4,6,8}}]}]

Cellular encoding

High dimensional Cellular Automatons generating the the topology

Scalability, repeating structures, ...

References

http://evolution.felk.cvut.cz/recurrent/

http://cig.felk.cvut.cz/

BUK Z., SNOREK M., Continual Evolution Algorithm for Building of ANN - based Models, In Proceedings of the 6 th EUROSIM Congress on Modelling and Simulation, Ljubljana, 2007, vol.2, ISBN 978 - 3 - 901608 - 32 - 2.

BUK Z., SNOREK M., Probability Control Functions Settings in Continual Evolution Algorithm, In Proceeding of International Workshop on Inductive Modelling. Prague: Czech Technical University, 2007, vol.1, ISBN 978 - 80 - 01 - 03881 - 9.

BUK Z., Recurrent Neural Networks optimization using Continual Evolution Algorithm in Mathematica Environment, In Wolfram Technology Conference 2007 Presentations.Champaign, Illinois : Wolfram Reasearch, Inc., 2007.

BUK Z., SNOREK M., Hybrid Evolution of Heterogeneous Neural Networks , In Artificial Neural Networks - ICANN 2008, 18 th International Conference Proceedings.Heidelberg : Springer, 2008, vol.1, p.426 - 434. ISBN 978 - 3 - 540 - 87535 - 2.