Program Modules

According to the modular programming concept, all executables are generated by linking together separate specialised modules (object files). A module without object file, thus merely containing definitions is called virtual. The following table lists all modules and shows their hierarchic dependencies. The files problem .c and problem .o refer to the source and object file of the problem definition (e.g. to enc.c and enc.o). For a more detailed description, please refer to the Makefile.

Module	File	Source	Using
Definitions	defs.o	defs.c defs.h
Sequential	seq.o	seq.c seq.h	defs.h
Parallel	par.o	par.c par.h	defs.h CS-Tools
Simulation	sim.o	sim.c sim.h	defs.h
Individual	virtual	ind.h	defs.h
Standard Net	stdnet.o	stdnet.c stdnet.h	defs.h ind.h
Problem Def.	problem .o	problem .c	defs.h ind.h stdnet.h
Genetic Alg.	gen.o	gen.c gen.h	defs.h ind.h gen.h
Backpropagation	back.o	back.c back.h	defs.h ind.h
Gen. Backprop.	genback.o	genback.c genback.h	defs.h ind.h back.h
Main Sequential	mainseq.o	mainseq.c	defs.h ind.h back.h seq.h gen.h genback.h
Main Parallel	mainpar.o	mainpar.c	defs.h ind.h back.h par.h gen.h genback.h
Main Backprop.	mainback.c	mainback.c	defs.h ind.h back.h sim.h

Parameter Handling and Initialisation

Most modules require an initialisation to allocate arrays, to setup local variables or hardware, or to process command line options passed to the program. For this purpose, the following functions and variables are declared in the interface (i.e. the header file):

• char * ModOptStr(); returns a pointer to the option string of the module.
• char * ModUsage(); returns a pointer to the usage message of the module.
• int handle ModOpt(char opt,char* arg); returns 0 if the option opt with the argument arg was successfully handled by the module.
• int init Mod(); returns 0 if the Module has been successfully initialised.
• char ModParamStr[256]; is set by init Mod() and contains a verbal description of the module parameters.

Mod stands for the module names Seq, Par, Sim, Ind, Net (also declared in ind.h for network initialisation), Std (declared in stdnet.h and implemented in the problem definition), Gen, Back and Out (defined by the main programs for output handling). These routines are either called directly form the main program or by the corresponding routines of the parent module reflecting the object oriented concept of inheritance.

In the following module descriptions, only variables and functions directly related to the implemented algorithms are mentioned. For auxiliary and system or hardware specific functions, please refer to the source code.

Module: Definitions

	Source:		defs.h		declarations of standard types and functions
			defc.c		implementation

	Programs:		all

	Options:		none

	Parent:		none

This module contains commonly used constants, type declaration and auxiliary functions for bit manipulation and random numbers.

Module: Sequential

	Source:		seq.h		declarations of sequential features
			seq.c		implementation

	Programs:		encseq		sequential genetic ENC/DEC problem
			cntseq		sequential genetic 1-norm problem
			cmpseq		sequential genetic comparator

	Options:		-p$p$		population size		p=100
			-g$N_{max}$		maximum number of generations		$N_{max}=100000$
			-e$E_{max}$		maximum error for success		$E_{max}=0.01$
			-s$s_{rnd}$		random seed value		$s_{rnd}=\mbox{time}$

	Parent:		none

This module contains all functions, specific to the sequential execution of the genetic and combined algorithm and is, like the module Simulation a mere placeholder, since no network functions or special initialisations have to be defined.

Variables and Functions

• int PopSize; population size $p$
• int MaxGen; maximum number $N_{max}$ of generations
• errtyp MaxErr; maximum error $E_{max}$ for success
• int SeedRand; random seed value $s_{rnd}$
• int initSeq; initialises the sequential parameters
• void errorexit(char *msg); prints the error message msg and aborts the program

Module: Parallel

	Source:		defs.h		declarations of parallel features
			sefc.c		implementation

	Programs:		encseq		parallel genetic ENC/DEC problem
			cntseq		parallel genetic 1-norm problem
			cmpseq		parallel genetic comparator

	Options:		-p$p$		population size		p=100
			-g$N_{max}$		maximum number of generations		$N_{max}=100000$
			-e$E_{max}$		maximum error for success		$E_{max}=0.01$
			-s$s_{rnd}$		random seed value		$s_{rnd}=\mbox{time}$
			-t$N_{tr}$		global selection every $N_{tr}$ generations		$N_{tr}=1$

	Parent:		none

This module contains all functions specific to the parallel execution of the genetic and combined algorithm on the transputer network and uses the Meiko CS-Tools library.

Variables and Functions

• int Procs; number of processors (determined automatically)
• int ProcId; process Id (0 is master)
• int PopGlobal; global population size $p$
• int PopLocal; local population size $p_{loc}$
• int MaxGen; maximum number $N_{max}$ of generations
• errtyp MaxErr; maximum error $E_{max}$ for succes
• int SeedRand; random seed value $s_{rnd}$
• int Ntrans; global selection every $N_{trans}$ generations
• int initPar(); initialises parallel parameters and communication network and communicates the random seed values.
• void initNetwork(); network setup
• send and receive functions for network communication
• void errorexit(char *msg); prints the error mesage msg and aborts all processes

Module: Simulation

	Source:		defs.h		declarations of sequential backpropagation features
			sefc.c		implementation

	Programs:		encback		backpropagation ENC/DEC problem
			cntback		backpropagation 1-norm problem
			cmpback		backpropagation comparator

	Options:		-g$N_{max}$		maximum number of iterations		$N_{max}=100000$
			-e$E_{max}$		maximum error for success		$E_{max}=0.01$
			-s$s_{rnd}$		random seed value		$s_{rnd}=\mbox{time}$

	Parent:		none

This module is the backpropagation equivalent to the module Sequential and is also merely a placeholder.

Variables and Functions

• int MaxIter; maximum number $N_{max}$ of iterations
• errtyp MaxErr; maximum error $E_{max}$ for success
• int SeedRand; random seed value $s_{rnd}$
• int initSim(); initialises parameters

Module: Individual

Source:

ind.h

declaration of individual and network features

	Programs:		all

	Options:		none

	Parent:		none

This virtual module contains variable and function declaration for the individual definition in the genetic algorithm including network topology and training sets, which are also used for backpropagation. The actual implementation are left to the derived modules. This allows to use the genetic programs for any kind of phenotypes.

The actual implementations for 2-layer neural networks is left to the derived module Standard Net.

Declarations

• int CrBits; length $l$ of one chromosome string in bits
• int Nin, Nhid, Nout; network topology for a 2-layer $n$-$m$-$o$-network
• float **TrainIn, **TrainOut; input and output patters $I^{(k)}$ and $O^{(k)}$ of the training set ${\bf T}$.
• int Ntrain; number of patterns $t$
• int Nback; number of backpropagation steps $b$ for the combined genetic-backpropagation algorithm
• int NoTrain; number of training patters $t'$ used for error estimation (Section 3.4.3)
• float Estimate the initial information ratio $r_{est}$, which is defined as $r_{est}={t'(n+o) \over m(n+1)+o(m+1)}$ and used to calculate $t'$.
• int initInd(); and int initNet(); initialise the individual or the network parameters
• errtyp calcerr(ind x); returns the error (i.e. the negative fitness) $E(x)$ of the individual x.
• void printind(ind x); prints a description of the phenotype of x.

Module: Standard Network

	Source:		stdnet.h		declarations for 2-layer $n$-$m$-$o$-networks
			stdnet.c		implementation

	Programs:		all

	Options:		-B$B$		number of bits $B$ used for weight encoding		$B=8$
			-W$W$		weights in interval $[-W,W]$		$W=10$
			-E$r_{est}$		error estimation factor		$r_{est}=0$
			-b$b$		no. of backprop. steps for combined alg.		$b=0$

Parent:

Individual

This module contains the implementation for 2-layer networks of the functions declared in the module Individual. The actual topology, as well as the training set, is, however, determined by the problem definition via the ``virtual'' functions initStd and initTrain.

The individual options -B, -W, -E and -b are recognised by initInd and ignored, when only the backpropagation initNet is called.

Variables and Functions

• int Nbits; number of bits $B$ used for weight encoding
• float Width; range $W$ for weights in interval $[-W,W]$
• int initStd(); and void initTrain(); forward declarations for the actual problem definition. The interface variables Nin, Nhid, Nout and Ntrain must be set according to the problem.
• void initTrain(); forward declarations for the actual problem definition. The arrays TrainIn and TrainOut must be set to the training patters of the problem.
• various auxiliary constants, macros and functions for decoding chromosome strings

Module: Genetic Algorithm

	Source:		gen.h		declaration of the genetic algorithm
			gen.c		implementation

	Programs:		encseq, cntseq, cmpseq		sequential versions
			encpar, cntpar, cmppar		parallel versions

	Options:		-m$p_m$		percentage of mutations		$p_m=60 \%$
			-n$N_m$		perform $(1, \ldots N)$-point mutations		$N_m=\left\lfloor {l\over 50} \right\rfloor+1$
			-c$p_c$		percentage of reproduction (copies)		$p_c=0 \%$
			-u$u$		percentage of uniform selections		$u=0 \%$
			-d$d$		decimation factor		$d=0$
			-h$H$		size of internal hashtable		$H=0$

	Parent:		none

This modules contains the variables and functions for the genetic algorithm. The chromosome strings (type ind) are arrays of unsigned integers; all genetic operators work on this representation by directly manipulating the bits.

Variables and Functions

• int Ncopy, Nmutate, Ncrossover the numbers $r$, $m$ and $c$ of individuals on which to perform reproduction, mutation and crossover (Section 3.5.2)
• int Decimation; initial decimation factor $d$ (Section 3.3.2)
• ind *Pop; array of the chromosome strings $S_k$ of the population ${\bf P}$.
• errtyp *Err; array of the errors $E(S_k)$ of all individuals in ${\bf P}$
• int initGen(int popsize,int popmem); initialises parameters and generates ${\bf P}_0$ by randomising strings.
• void randomPop(int popsize); generates popsize random individuals.
• void mutate(ind x0,ind x1); perform $n$-point mutation on x0 where $n$ is a random number in $\{1, \ldots N_m\}$. The result is written to x1.
• void crossover(ind x0,ind y0,ind x1,ind y1); performs crossover of x0 and y0; the results are written to x1 and y1.
• void copy(ind x0,ind x1); copies x0 onto x1.
• void calcerrors(int popsize); calculates the error of all individuals using calcerr declared in the module Individual.
• void selection(int popsize); generates the next generation, using the rank selection mechanism defined in Section 3.5.1.

Module: Backpropagation

	Source:		back.h		declaration of the backpropagation algorithm
			back.c		implementation

	Programs:		all

	Options:		-o$O$		use online learning (0/1)		$O=1$
			-k$\gamma$		learn rate		$\gamma = 1$
			-a$\alpha$		impulse factor		$\alpha=0$
			-w$w$		range of initial weights $[-w,w]$		w=1

	Parent:		none

This module contains the backpropagation algorithm as described in Section 4.3.

Variables and Functions

• float NetErr; residual Error $E(W^{(1)},W^{(2)})$
• float LearnRate; learn rate $\gamma$
• float Impulse; impulse constant $\alpha$
• float InitWeight; initial weight range $w$
• float **Wih, **Who; weight matrices $W^{(1)}$ and $W^{(2)}$
• float **Dih,**Dho; first order updates $\Delta W^{(1)}$ and $\Delta W^{(2)}$
• float **DDih,**DDho; second order updates $\Delta^2 W^{(1)}$ and $\Delta^2 W^{(2)}$ (impulse term)
• int initBack(); initialise parameters and weights
• void randomNet(float w); randomise weights (interval $[-w,w]$)
• float calcNetErr(); calculates the average network error per pattern ( $E(W^{(1)},W^{(2)})$) and updates weights in case of online learning
• void updateNet(); updates weights in case of batch learning
• void printnet(); prints $W^{(1)}$ and $W^{(2)}$

Module: Genetic Backpropagation

	Source:		back.h		declarations for the combined algorithm
			back.c		implementation

	Programs:		encseq, cntseq, cmpseq		sequential versions
			encpar, cntpar, cmppar		parallel versions

	Options:		none

	Parent:		none

This module implements special function for the combined genetic backpropagation algorithm (Section 5.4).

Variables and Functions

• void randomNetPop(int popsize,float w); randomises a network population with initial weights in $[-w,w]$.
• void gen2back(ind x); decoding function $d'_{net}$
• void back2gen(ind x); encoding function $e'_{net}$
• void backsteps(ind x,int n); performs $n$ backpropagation steps on the individual x.

Main Modules

	Source:		mainseq.c		main program for the sequential genetic alg.
			mainpar.c		main program for the parallel genetic alg.
			mainback.c		main program for sequential backpropagation

	Programs:		encseq, cntseq, cmpseq		sequential versions ( mainseq.c)
			encpar, cntpar, cmppar		parallel versions ( mainpar.c)
			encback, cntback, cmpback		backpropagation ( mainback.c)

	Options:		-l$L$		frequency of log-output		automatic
			-f$F$		log momentarily best network		$F=0$
			-i$I$		show parameter info		$I=1$
			-r$R$		show calculation statistics		$R=1$

	Parent:		none

These modules contain the main-procedures for all executables. They mainly consist of a loop which performs the genetic or backpropagation iterations and produces log-output. The output options are the same for all three modules.