Comparative Languages Fall 2005-2006
Genetic Programming Application, Part 1
Try this in 3 Languages

  • Try this in 3 different styles of languages: Python/Ruby/Perl, Scheme/Lisp, Smalltalk, ML, C/Fortran/Java, Prolog

    1. Overview of Genetic Algorithms (GA)
      1. Initialize a population
      2. Calculate a fitness for each individual in the population
      3. Reproduce selected individuals to form a new population
      4. Perform crossover and mutation on the population
      5. Loop to step 2 until some condition is met

    2. Example GA problem (from Swarm Intelligence by James Kennedy and Russell Eberhart:

        Find the value of x that maximizes the function f(x)=sin(pi x/256) where values of x
        are restricted to integers between 0 and 255.

        The values between 0 and 255 can be represented as 8-bit binary numbers for the population of individuals.
        Use this population for testing - 8 individuals with 8 bits each. (a better version would randomly generate
        these 8-bit strings.

        1 0 1 1 1 1 0 1
        1 1 0 1 1 0 0 0
        0 1 1 0 0 0 1 1
        1 1 1 0 1 1 0 0
        1 0 1 0 1 1 1 0
        0 1 0 0 1 0 1 0
        0 0 1 0 0 0 1 1
        0 0 1 1 0 1 0 1

        Here's example Scheme code to do this initialization: 

            (define teststring
      '((1 0 1 1 1 1 0 1)
        (1 1 0 1 1 0 0 0)
        (0 1 1 0 0 0 1 1)
        (1 1 1 0 1 1 0 0)
        (1 0 1 0 1 1 1 0)
        (0 1 0 0 1 0 1 0)
        (0 0 1 0 0 0 1 1)
        (0 0 1 1 0 1 0 1)))
        Same example in Smalltalk: 
        
      ! Object methodsFor: 'algorithms' !

      testString
           "(FileStream oldFileNamed: 'gaprogram.st') fileIn."

	 ^#((1 0 1 1 1 1 0 1)
           #(1 1 0 1 1 0 0 0)
           #(0 1 1 0 0 0 1 1)
           #(1 1 1 0 1 1 0 0)
           #(1 0 1 0 1 1 1 0)
           #(0 1 0 0 1 0 1 0)
           #(0 0 1 0 0 0 1 1)
           #(0 0 1 1 0 1 0 1)).
        Same example in Prolog 
            testString([[1,0,1,1,1,1,0,1], [1,1,0,1,1,0,0,0],
                [0,1,1,0,0,0,1,1], [1,1,1,0,1,1,0,0],
                [1,0,1,0,1,1,1,0], [0,1,0,0,1,0,1,0],
                [0,0,1,0,0,0,1,1], [0,0,1,1,0,1,0,1]]).

     /* ?-consult(gaprogram).
        ?-testString(X).   
	  X = [[1,0,1,1,1,1,0,1], [1,1,0,1,1,0,0,0],[0,1,1,0,0,0,1,1], [1,1,1,0,1,1,0,0],
                [1,0,1,0,1,1,1,0], [0,1,0,0,1,0,1,0], [0,0,1,0,0,0,1,1], [0,0,1,1,0,1,0,1]]
        Same example in ML (SML): 
        	val testString = [[1,0,1,1,1,1,0,1], [1,1,0,1,1,0,0,0],
			[0,1,1,0,0,0,1,1], [1,1,1,0,1,1,0,0],
			[1,0,1,0,1,1,1,0], [0,1,0,0,1,0,1,0],
			[0,0,1,0,0,0,1,1], [0,0,1,1,0,1,0,1]];  

	(*
	- use "gaprogram.sml";
	- testString;
	val it =
	  [[1,0,1,1,1,1,0,1],[1,1,0,1,1,0,0,0],[0,1,1,0,0,0,1,1],[1,1,1,0,1,1,0,0],
	   [1,0,1,0,1,1,1,0],[0,1,0,0,1,0,1,0],[0,0,1,0,0,0,1,1],[0,0,1,1,0,1,0,1]]
	  : int list list
	*)

    3. Write a function to evaluate each of these individuals to a number between 0 and 255: 
            Individuals           x
    
    1 0 1 1 1 1 0 1      189
    1 1 0 1 1 0 0 0      216
    0 1 1 0 0 0 1 1       99
    1 1 1 0 1 1 0 0      236
    1 0 1 0 1 1 1 0      174
    0 1 0 0 1 0 1 0       74
    0 0 1 0 0 0 1 1       35
    0 0 1 1 0 1 0 1       53
        Example Scheme code to do this (using an iterative loop to evaluate): 
            (define (evalstring str)
      (do ((str2 (reverse str) (cdr str2))
           (ans 0)
           (mult 1 (* 2 mult))    ;; Use a 2 because these are binary, base 2, numbers
           (count (length str))
           (i 0 (+ i 1)))
        ((= i count) ans)
        (set! ans (+ ans (* mult (car str2))))))
        Same example in Smalltalk (using an iterative loop to evaluate and build answer list): 
             !
       evalString
		"Object new testString first evalString. Evaluates the first bit string.
		 #(1 0 1 1 1 1 0 1) evalString. 189  Evaluates to 189."

		| ans mult i str2 count |
 		ans := 0.
		mult := 1.
		i := 0.
		str2 := self reversed.
		count := str2 size.
	
		[i < count] whileTrue: [                 OR USE  count timesRepeat: 
		 	ans := ans + (mult * str2 first).
			str2 := str2 allButFirst.
			mult := mult*2.
			i := i + 1.
			]. 
		^ans.
	!

	evaluateStrings
		" Object new testString evaluateStrings 
		#(189 216 99 236 174 74 35 53)"
	
		|ans count tempStr|
		ans := Array new: 8.
		count := ans size.
		tempStr := self.
		1 to: count do: [:index|
			ans at: index put: ((tempStr first) evalString).
			tempStr := tempStr allButFirst.
			].
		^ans.
	!
        Same example in Prolog (using recursion to evaluate and build answer list): 
        	evalList(EvalList) :-
		testString(X),
		reverse(X,Y),
	/*	write('Y='),write(Y),nl, */
		getEvalList(Y,[],EvalList).
		
	getEvalList([], EvalList, EvalList).
	getEvalList([X|Y],EvalList,Ans) :-
		evalString(X, Eval),
		getEvalList(Y,[Eval|EvalList],Ans).
		
	evalString(X, Eval) :- 
		reverse(X,Y),
		evalStringAux(Y, 0, 1,Eval).
	
	evalStringAux([],Eval, _,Eval).
	evalStringAux([X|Y], Eval, Mult,Evaluate) :-
		Eval1 is Eval + X*Mult,
		Mult1 is Mult*2,
		evalStringAux(Y,Eval1,Mult1,Evaluate).
		
	?- consult(gaprogram).
	?- evalList(X).
		X = [189, 216, 99, 236, 174, 74, 35, 53]
        Recursive version in Scheme (as opposed to the iterative version above): 
        	(define (evalstringRec str)
		(evalstringRecAux (reverse str) 0 1))

	(define (evalstringRecAux str sum mult)
	    (if (empty? str)
	        sum
	       (evalstringRecAux (cdr str) (+ sum (* mult (car str))) (* mult 2))))

	(define (evalList)
	    (getevalList teststring '()))

	(define (getevalList lis answerlist)
	    (if (empty? lis)
	         answerlist
	         (cons (evalstringRec (car lis))
		        (getevalList (cdr lis) answerlist))))
	
	SAMPLE RUN:
	> (evalList)
		(189 216 99 236 174 74 35 53)
        Recursive version in Smalltalk (as opposed to the iterative Smalltalk above):
        To load the file: (FileStream oldFileNamed: 'gaprogram.st') fileIn. 
        	evalStringRec 
		"#(1 0 1 1 1 1 0 1) evalStringRec. 189   Evaluates to 189."
	 
		 ^(self reversed) evalStringRecAux: 0 multiplier: 1.
	!	

	evalStringRecAux: sum multiplier: mult
		| localsum |
	
		self size = 0 ifTrue: [^sum].
		localsum := mult*(self first).
		^(self allButFirst) evalStringRecAux: (sum + localsum)
						multiplier: (mult * 2).					
	!

	evalList
		"Recursive version of evalList
		Object new evalList. (189 216 99 236 174 74 35 53 ) "
	
		| tester |
		tester := Object new testString.
		^tester getEvalList: (Array new: 8) counter: 1.
	!

	getEvalList: ans counter: index
		self size = 0 ifTrue:[^ans].
		ans at: index put: (self first evalStringRec).
		^(self allButFirst) getEvalList: ans counter: (index+1).
	!
        Example using SML:
        NOTE THAT FUNCTION DEFINITIONS APPEAR BEFORE THEY ARE CALLED IN THE CODE 
        	fun reverse(L) =
		if L = nil then nil
		else reverse(tl(L)) @ [hd(L)];

	fun evalStringAux(str:int list, sum:int, mult:int):int =
		if str = nil then sum
		else evalStringAux(tl(str), sum+mult*hd(str), mult*2);

	fun evalString(str:int list) : int =
		evalStringAux(reverse(str), 0, 1);

	fun getEvalList(strings: int list list, ans: int list):int list =
		if strings = nil then ans
		else evalString(hd(strings)) :: getEvalList(tl(strings),ans);

	fun evalList(strings: int list list): int list =
		getEvalList(strings,[]);
	
	(*
	- use "gaprogram.sml";

	- evalList(testString);
		val it = [189,216,99,236,174,74,35,53] : int list
	*)

    4. Write a function to evaluate f(x)=sin(pi x/256) (the function to be optimized by the GA) for each
      individual. 
            Individuals           x      f(x)            
    
    1 0 1 1 1 1 0 1      189     0.733
    1 1 0 1 1 0 0 0      216     0.471
    0 1 1 0 0 0 1 1       99     0.937
    1 1 1 0 1 1 0 0      236     0.243
    1 0 1 0 1 1 1 0      174     0.845
    0 1 0 0 1 0 1 0       74     0.788
    0 0 1 0 0 0 1 1       35     0.416
    0 0 1 1 0 1 0 1       53     0.650
        Example Scheme code to evaluate f(x) for a list of these individuals
        (using an iterative loop to build lists): 
        
  (define (fstrings strlis)
     (do ((ans '())
          (templis (reverse strlis) (cdr templis)))
        ((= (length templis) 0) ans)
        (set! ans (cons (sin (* pi (/ (car templis) 256))) ans))))
        Same example in Smalltalk (using an iterative loop to build lists): 
        	!		
	fstrings
		"Object new testString evaluateStrings fstrings 
		 #(0.732654271672413 0.471396736825998 0.937339011912575 
		 0.242980179903264 0.844853565249707 0.788346427626606 
		 0.416429560097637 0.6055110414043255)"
		| ans count tempString |

		ans := Array new: 8.
		tempString := self.
		count := tempString size.
		1 to: count do: [:index |
			ans at: index put: (((tempString first) * Float pi / 256.0) sin).
			tempString := tempString allButFirst.
			].
		^ans.
        Same example in Prolog (using recursion to build lists): 
        	f(X,Y) :- Y is sin(pi*X/256).

	flist(FList) :-
		evalList(EvalList),
		reverse(EvalList,RevList),
		evalFList(RevList,[],FList).
	
	evalFList([],FList,FList).
	evalFList([X|Rest], EvalList, FList) :-
		f(X,Y), 
		evalFList(Rest,[Y|EvalList],FList).

	?- consult(gaprogram).
	?- flist(X).
		X = [0.732654, 0.471397, 0.937339, 0.24298, 0.844854, 0.788346, 0.41643, 0.605511]
        
	?-halt.
        Recursive version in Scheme (as opposed to the Scheme iterative version above): 
        	   (define (fstringsRec)
		  (evalFList (evalList) '()))

	   (define (evalFList lis answerlist)
		  (if (empty? lis)
		      answerlist
		      (cons (f (car lis)) (evalFList (cdr lis) '()))))

	   (define (f x)
		  (sin (* pi (/ x 256))))
	
	SAMPLE RUN:
	> (fstringsRec)
		(0.7326542716724128  0.47139673682599786  0.937339011912575
		 0.24298017990326407  0.8448535652497072  0.7883464276266062
		 0.41642956009763715  0.6055110414043256)
        Recursive version in Smalltalk (as opposed to the iterative Smalltalk version above): 
        	flistRec
		" Object new flistRec. (0.732654271672413 0.471396736825998 
		 0.937339011912575 0.242980179903264 0.844853565249707 
		 0.788346427626606 0.416429560097637 0.6055110414043255 ) "
	 
		| tester |
		tester := self evalList.
		^tester evalFList: (Array new:8) counter: 1
	!

	evalFList: ans counter: index
		self size = 0 ifTrue:[^ans].
		ans at:index put: (self first func).
		^(self allButFirst) evalFList: ans counter: (index+1).
	!

	func
		^(self * Float pi/256) sin.
	!
        Same example using SML:
        NOTE THAT FUNCTION DEFINITIONS APPEAR BEFORE THEY ARE CALLED IN THE CODE 
        	fun f(x:real):real = 
		Math.sin(Math.pi * x / 256.0); 
	
	fun evalFList(lis: int list, ans:real list) : real list =
		if lis = nil then ans
		else f(real(hd(lis))) :: evalFList(tl(lis),ans);

	fun flist(strings: int list list): real list =
		evalFList(evalList(strings), []);
	 (*
	- use "gaprogram.sml";

	- flist(testString);
	val it =
		[0.732654271672,0.471396736826,0.937339011913,0.242980179903,0.84485356525,
		   0.788346427627,0.416429560098,0.605511041404] : real list
	*)
    5. Write a function to normalize each of these f(x) values. Normalization is accomplished by dividing each
      f(x) value by the sum of all the f(x) values. The resulting list of normalized values adds to 1. 
            Individuals           x      f(x)     fnorm            
    
    1 0 1 1 1 1 0 1      189     0.733     0.144
    1 1 0 1 1 0 0 0      216     0.471     0.093
    0 1 1 0 0 0 1 1       99     0.937     0.184
    1 1 1 0 1 1 0 0      236     0.243     0.048
    1 0 1 0 1 1 1 0      174     0.845     0.166
    0 1 0 0 1 0 1 0       74     0.788     0.155
    0 0 1 0 0 0 1 1       35     0.416     0.082
    0 0 1 1 0 1 0 1       53     0.650     0.128

    6. Generate a cumulative list of these normalized values. 
            Individuals           x      f(x)     fnorm     Cumulative fnorm            
    
    1 0 1 1 1 1 0 1      189     0.733     0.144         0.144
    1 1 0 1 1 0 0 0      216     0.471     0.093         0.237
    0 1 1 0 0 0 1 1       99     0.937     0.184         0.421
    1 1 1 0 1 1 0 0      236     0.243     0.048         0.469
    1 0 1 0 1 1 1 0      174     0.845     0.166         0.635
    0 1 0 0 1 0 1 0       74     0.788     0.155         0.790
    0 0 1 0 0 0 1 1       35     0.416     0.082         0.872
    0 0 1 1 0 1 0 1       53     0.650     0.128         1.000

    7. Now, in order to pick 8 better (more evolved) individuals for the next population, generate 8 random
      numbers. So we all agree, use these 8 "random" numbers: 
              0.293   0.971   0.160   0.469   0.664   0.568   0.371   0.109
        Correlate each random number with the Cumulative fnorm list above to choose corresponding individuals to live on.
        For example, if the random number is between 0.144 and 0.237, individual 1 is picked. If the random
        number is between 0.237 and 0.421, individual 2 is picked.

        Using the random numbers above, the following individuals are picked to live on: individuals 3, 8, 2, 5, 6, 5, 3

    8. Use these 8 individuals as the population for the next generation. Program this part of the algorithm.
      In Part 2, we'll introduce crossover and mutation in order to introduce an element of change
      to the individuals in this next generation.