Saturday, March 9, 2013

Crossover Algorithm

Crossover is an important and attractive biological function which is happen in natural environment with respect to animal's reproduction procedure. This will case to generate new child who has genes collection of parents plus totally new or extended features. Mutation is the process which specialize the uniqueness while the crossover process. 

Core of the genetic algorithm is containing this concept. but how to do the crossover in genetic algorithm. this is my way to do it.

assumption --> crossover probability = 0.7
Select float "n" below 1.00.
if  n>0.7 return any parent as child
     else do following 
       Select 2 parents randomly.
       Decode them to 10 bit binary codes.
 Eg:     parent A : 1  1  0  0  1  0  1  0  0  1
           parent B : 1  0  1  0  0  1  0  1  0  1

      loop "x" from 0 to length of the bit string (10) select the couple of bits from index "x" of each string.

  Eg:   zeroth element of parent A and zeroth element of parent B (1 1
     
     If both are same use the same as "x" index element of the child 
              else randomly select 0 or 1 as the "x" index element . do this until end of the loop 

  Eg:    parent A : 1  1  0  0  1  0  1  0  0  1
           parent B : 1  0  1  0   1  0  1  0  1
           Child      : 1  0  1  0  1  1  0  0  0  1

        Encode the child bit string 
        Return the children
   
This is the lisp codes that is following above algorithm.

(defun crossover(xA xB);;crossover and produce child
  (let ((b-xA (int-to-binary xA)) (b-xB (int-to-binary xB)) 
  (child (int-to-binary nil)) (random-gene '(#\0 #\1)))
  (loop for y from 0 to (- (length b-xA) 1) do
  (if (char/= (aref b-xA y) (aref b-xB y)) 
  (progn (setf (char child y) (random-item random-gene)))
  (setf (char child y) (char b-xB y))))
(parse-integer child :radix 2)))

No comments:

Post a Comment