//************************************************************** // 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