# GA_v4.sce

```//**************************************************************
// File:GA_v4.sce
// Authors: Gerd Doeben-Henisch
// Version Start: January-18, 2010
// Version Last: June-26, 2012
//***********************************************
// Function: Implements a simple GA
// References:  Goldberg (1989)
//******************************************************************
// Apri-l5, 2011 : Adding a mutation operator
// April-29-2012 : Adding some predefined populations to support
// the examples from the online script
// April-29-12 : Corr in rfitness(); division by zero
// April-29-12 : Corr if all values are zero then there is no crossover and no new member before mutation
// April-29-12 : Number n has to be equal (for crossover)
// June-26-12 : Some minor corrections in the comments
//****************************************************************
// SW-STRUCTURE
//
// All data are organized in a dynamical table. Left hand the actual genes, in the  middle
// supporting parameters and to the right intermediate modifications of the genes to the left.
//

// POP FORMAT
// length := length of strings
// Pos 0 until length-l := String (In scilab the matrix counts from '0' !)
// Pos length := Decimal Value of binary string
// Pos length+1 := Fitness
// Pos length+2 := Percentage of overall fitness
// Pos length+3 := Expected count according to fitness
// Pos length+4 := Realized count

//SOME PREDEFINED POPULATIONS

POP1=[0 0;0 1]

POP2=[0 1; 1 0]

POP3=[1 0; 1 1]

POP4=[0 0 0; 0 0 0]

POP5=[0 0 1; 0 1 1]

POP6=[1 0 0; 1 1 0]

POP7=[1 1 1; 1 1 1]

// Populatin use by Goldberg (1989) in his introductory example

POPX = [0 1 1 0 1 13 169 0 0 0; 1 1 0 0 0 24 576 0 0 0; 0 1 0 0 0  8 64 0 0 0; 1 0 0 1 1 19 361 0 0 0;]

// Variable for overall Fitness

FITNESS_ALL = 0

// Variable for average Fitness

AFITNESS = 0

//***************************************************
//Function to generate automatically a population with random values
// Input:
// l := length of strings
// n := size of population
// Output:
// A population according to the above defined format
//

function[POPX]=popgen(n,l)

//Generate a matrix with only '0's

POPX = zeros(n,l)
MaxCells = n*l

// Distribute randomly '1's

for i=1:n
for j=1:l
if( rand() < 0.5 ) then POPX(i,j) = 0, else POPX(i,j) = 1, end
end
end

endfunction

//***************************************************
//Function to compute the overall fitness of a matrix POP
// Sum up all the l+2-th positions
// l := length of fitness strings

function[FITNESS_ALL]=fitness(POP,l)

FITNESS_ALL=0;
[r,c]=size(POP);
for j=1:r
FITNESS_ALL=FITNESS_ALL+POP(j,l+2)
end

endfunction

//***************************************************
//Function to compute the maximal individual fitness of a matrix POP
// Compute all the l+2-th positions
// l := length of fitness strings

function[MFITNESS]=maxfitness(POP,l)

MFITNESS=0
[r,c]=size(POP);
for j=1:r
if POP(j,l+2) > MFITNESS then MFITNESS = POP(j,l+2)
end
end

endfunction

//***************************************************
//Function to compute the relative fitness of a string
// along with the average fitness
// Compute all the l+3-th positions
// l := length of fitness strings

function[POP,AFITNESS]=rfitness(POP,l, FITNESS_ALL)

[r,c]=size(POP);
for j=1:r
if FITNESS_ALL<> 0 then
POP(j,l+3)=POP(j,l+2)/FITNESS_ALL,
else POP(j,l+3)=0
end
end

AFITNESS=FITNESS_ALL/r

endfunction

//***************************************************
//Function to compute the relative count of a string
// along with the realized new count by 'rounding up'
// Compute all the l+4 and l+5-th positions
// l := length of fitness strings
// n :=  number of individuals in POP

function[POP]=newMember(POP,l,n)

[r,c]=size(POP);

for j=1:r
POP(j,l+4)=POP(j,l+3)*n
POP(j,l+5)=round(POP(j,l+4))
end

endfunction

//***************************************************
// Make a copy of a string from row_old to row_new: L --> R
// where the copy starts at position l+p+1
// l := length of string
// j := row_old
// k := row_new
// p := number of parameters (P=5)

function[POP]=strcpyLR(POP,l,p,j,k)

[r,c]=size(POP);

// Testing the boundaries

if (j < 1) then printf('ERROR: Position of old String outside of Matrix! r = %d, j = %d', r,j)
elseif  (j > r) then printf('ERROR: Position of old String outside of Matrix!, r = %d, j = %d', r,j)
elseif (k < 1) then printf('ERROR: Position of new String outside of Matrix!, r = %d, k = %d', r,k)
elseif (k > r) then printf('ERROR: Position of new String outside of Matrix!, r = %d, k = %d', r,k)
end

// Making a copy

for i=1:l
POP(k,l+p+i) = POP(j,i)
end

endfunction

//***************************************************
// Make a copy of a string from row_old to row_new: R --> L
// where the copy starts at position l+p+1
// l := length of string
// j := row_old
// k := row_new
// p := number of parameters (p=5)

function[POP]=strcpyRL(POP,l,p,j,k)

[r,c]=size(POP);

// Testing the boundaries

if (j < 1) then printf('ERROR: Position of old String outside of Matrix! r = %d, j = %d', r,j)
elseif  (j > r) then printf('ERROR: Position of old String outside of Matrix!, r = %d, j = %d', r,j)
elseif (k < 1) then printf('ERROR: Position of new String outside of Matrix!, r = %d, k = %d', r,k)
elseif (k > r) then printf('ERROR: Position of new String outside of Matrix!, r = %d, k = %d', r,k)
end

// Making a copy

for i=1:l
POP(j,i) = POP(k,l+p+i)
end

endfunction

//***************************************************
// Make a copy of all strings from the old rows to the new ones
// where the new copies will start at position l+p+1
// l := length of string
// j := row_old
// k := row_new
// p := number of parameters (p=5)
// r2 := memory of position for new strings

function[POP]= newPop(POP,l,p,n)

[r,c]=size(POP);
r2 = 1

for j=1:r

if POP(j,l+p) > 0 then r3 = POP(j,l+p)-1,

for k=r2:(r2+r3), //printf('\n k = %d\n', k)
[POP]=strcpyLR(POP,l,p,j,k)
end

r2=k+1

end
end

endfunction

//***************************************************
// Prepare the crossover operations within a population POP
// by randomly selecting the new strings and copy them onto the
// POP base area  [1,l]
//
// General Assumption: the number of members n is even!!!
//
// The strings are assumed to be in the area starting at l+p+1
// The parameter at l+p has been changed to a flag '1' := not yet mated
// j := target position in the base area for copy action

function[POP]= crossoverPrep(POP,l,p,n)

[r,c]=size(POP);

//Ckeck n is euqal numbered

if modulo(n,2) <> 0 then error('number n should be equal'), end

// Set a flag at position l+p with '1'

for j=1:r
POP(j,l+p)=1
end

// Select randomly the strings for transfer

j = 1 //:= Baseline for filling up with strings

while(j < n+1)

S = 1 //:= Flag for searching a string to be copied

while(S == 1)

k1 = round(n * rand())
if k1==0 then k1=1
end

if POP(k1,l+p) <> 0 then POP=strcpyRL(POP,l,p,j,k1)
//mshow(POP,n,l+p+l)
POP(k1,l+p) = 0,
S=0
else S=1
end //while == S

end // while == j

printf('k1 = %d\n',k1)
printf('j = %d\n',j)
j = j+1
// mshow(POP,n,l+p+l)

end

endfunction

//***************************************************
// Apply a crossover operation onto two adjacent strings at intersection x
// The strings are assumed to be randomly paired in the area at position 1
//
// p := number of parameters between strings left and right (actually  p=5)
// l := length of strings ( actually l=5)
// n := number of elements in POP (actually n=4)

function[POP]= crossover(POP,l,p,n)

// Take a first row
r=1
while(r < n)

// printf('r = %d\n',j)

// Select randomly a point in this row

x = round(l * rand()), if(x == 0) then x=1,end,

// printf('x = %d\n',x)

for i=x:l, m=POP(r+1,i)
POP(r+1,i) = POP(r,i)
POP(r,i) = m
end

r=r+2
end

endfunction

//***************************************************
// Apply a mutation operation onto one randomly selected string
// Select randomly a point in the string and replace it's
// value by it's inverse '1' --> '0', '0' --> '1'

function[POP]= mutation(POP,l,p,n)

// Find a point in a string

c = round(l * rand())
if c == 0 then c=1  // This does not change anything
end

// Find a row in the table

r = round(n * rand())
if r == 0 then r=1  // This does not change anything
end

// replce the value

if(POP(r,c) == 1) then POP(r,c) = 0,
else POP(r,c) = 1
end

printf('mutation point at = (%d, %d)\n',r,c)

endfunction

//***************************************************
// Print the content of a matrix
//
// d := depth of matrix 'downwards'
// w := width of  matrix from left to right

function[M]= mshow(M,d,w)

for j=1:d,// printf('\n j= %3.1d : ',j)
for i=1:w, //printf(' %3.1d ',M(j,i))
end
//printf('\n')
end

endfunction

//***************************************************
// Translate strings with binaries '0', '1' as decimal numbers
//
// v = vector of binaries from a POP-matrix (left part)
// l := length of string
// D := decimal computed out of binaries

function[D]= vec2dec(v,l)

str=string(v(1:l))
for i=2:l, str(1)=str(1)+str(i)
end
D=bin2dec(str(1))

endfunction

//***************************************************
//
//
// l := length of string
// MF := decimal computed out of binaries

function[MF]= maxfit01(l)

FitString=""
v=ones(1,l)
str=string(v)
for i=1:l, FitString = FitString + str(i)
end
MF=bin2dec(FitString)

endfunction

//***************************************************
//
//
// l := length of string
// MF := decimal computed out of binaries

function[MAXFIT]= maxfit02(l,n)

MAXFIT=n*(maxfit01(l)^2)

endfunction

//***************************************************
// Simple fitness-function f=(x^2)
//
// D := decimal computed out of binaries

function[F]= fitness1(D)

F=D^2

endfunction

//*************************************************************
// All Functions Unified
//
// p := number of parameters between strings left and right (actually  p=5)
// l := length of strings ( actually l=5)
// n := number of elements in POP (actually n=4)
// POP := a predefined population (can be done automatically)
// run := number of cycles
// MThreshold := number of cycles which have to be waited until the mutation operators will be applied

function[POP,FITNESS_ALLLOG]=gasimple(POP,l,p,n,run, MThreshold)

//Ckeck n is euqal numbered

if modulo(n,2) <> 0 then error('number n should be equal'), end

MutationCount = 0

FITNESS_ALLLOG=[]

for cyc = 1:run

[M]= mshow(POP,n,l+p)

for j=1:n, v=POP(j,:),  [POP(j,l+1)]= vec2dec(v,l)
end

for i=1:n,[POP(i,l+2)]= fitness1(POP(i,l+1))
end

[FITNESS_ALL]=fitness(POP,l)
FITNESS_ALLLOG(cyc)=FITNESS_ALL

[MFITNESS]=maxfitness(POP,l)

[POP,AFITNESS]=rfitness(POP,l,FITNESS_ALL)

if MFITNESS <> 0 then

[POP]=newMember(POP,l,n)
[POP]=newPop(POP,l,p,n)
[POP]= crossoverPrep(POP,l,p,n)
[POP]= crossover(POP,l,p,n)
end

printf('Mutationcount = %d\n', MutationCount)

if(MutationCount > MThreshold) then [M]= mshow(POP,n,l+p),
[POP]= mutation(POP,l,p,n),
[M]= mshow(POP,n,l+p),
MutationCount=0,
end

MutationCount = MutationCount + 1

end //for == run

// Compute the maximal value and the percentage of success

[MAXFIT]=maxfit02(l,n)
FITNESS_ALL_PERC=[]

for i=1:run, FITNESS_ALL_PERC(i) = FITNESS_ALLLOG(i)/(MAXFIT/100), end

// Show graphical results

clf(), xdel,
//plot2d([1:1:run], FITNESS_ALLLOG)
plot2d([1:1:run], FITNESS_ALL_PERC)

endfunction
```

Gerd Doeben-Henisch 2013-01-14