Hey, what's going on?

A Little Example of Genetic Algorithm (GA) in Action

Posted by Syeilendra Pramuditya on August 4, 2008

You can read a brief explanation about GA here

The objective of this code is to solve a simple mathematical equation below, that is to find x1 and x2 :

You can press the START button on the code again and again, then you will always get different values of x1 and x2, but the correct solution are x1=1 and x2=0.5.

Download : here

The complete explanation about this code will (hopefully) be available soon🙂

Screenshot :

The Code

Keywords : genetic algorithm soft computing delphi


Update 2011/01/26

Note that the sorting algorithm employed in this code is not really correct, you can replace it by some typical sorting algorithms, for instance the Bubble Sort algorithm. I know how to do this, just don’t have time right now.

3 Responses to “A Little Example of Genetic Algorithm (GA) in Action”

  1. brucecortez said

    The sample code has some problems:

    1. Why recalculate the fitness of the whole population on every iteration
    when you only need to update the ones that changed?
    2. Why use fixed over-sized arrays when it is so easy to set the size
    dynamically?
    3. Why use a whole population data structure for the best when you only
    need a single vector?
    4. Why mutate the whole population on every iteration? You are only
    supposed to mutate the current offspring.
    5. Is 10 bits enough accuracy for the floating point numbers?
    6. Why iterate for the full number of iterations when you could exit
    once an answer is reached?
    7. Why store the decoded floating point numbers when they are not needed?
    8. The crossover point is not used because the assignments 0..cp and
    cp+1..ngen-1 are identical.

    Syeilendra said..
    Hello,

    Thanks for the comment, actually I’ve been waiting for this kind of response to my post.
    Well I admit that the code is not perfect, let say it is a quick-n-dirty example for the purpose of showing the general idea of what genetic algorithm is.
    And apparently it is not the most efficiently-written code either.
    Nevertheless, this is exactly the philosophy of open source code: anyone in the whole world can access, check, assess, debug, evaluate, and most importantly, modify for the sake of improvement.
    So why don’t you modify the code and demonstrate the improvement, and then please send to me (both the modified source code and detailed explanation of improvement) so that I can put it (with your name of course) here. In this way everybody visiting this article can benefit, thanks to your modification/improvement.

    So what do you say?

  2. Syeilendra said..
    Thanks for posting the code here, I’ve tested it and it works well.
    Hopefully people who are interested in GA and arrive here will find it useful.

    brucecortez said
    I have removed the X and Y histories and the additional last generation.

    Download: here

    { ----------------------------------------------------------------------------
      Genetic Algorithm Example
    
      The equation that I solve here is from Gandhi Manalu.
      f(x,y) = (2.8125-x*(1.0-y**4))**2+(2.25-x*(1.0-y**2))**2+(1.5-x*(1.0-y))**2
      Expected answer is f(3.0,0.5)=0.0
      http://gandhim.wordpress.com/2010/04/04/particle-swarm-optimization-pso-sample-code-using-java/
      He used it to demonstrate Particle Swarm Optimization but I am now using it to
      compare PSO to GA.
    
      GA example of Syeilendra Pramuditya used as a reference
      https://syeilendrapramuditya.wordpress.com/2008/08/04/a-little-example-of-genetic-algorithm-ga-in-action/
    
      These questions need to be addressed:
        1. Why recalculate the fitness of the whole population on every iteration
           when you only need to update the ones that changed?
        2. Why use fixed oversized arrays when it is so easy to set the size
           dynamically?
        3. Why use a whole population data structure for the best when you only
           need a single vector?
        4. Why mutate the whole population on every iteration?  You are only
           supposed to mutate the current offspring.
        5. Is 10 bits enough accuracy for the floating point numbers?
           resolution = range/2^nbit = 4/2^10 = 0.0039
           With 24-bits, 4.0/2^24 = 2.38e-07
        6. Why iterate for the full number of iterations when you could exit
           once an answer is reached?
        7. Why store the decoded floating point numbers when they are not needed?
        8. The crossover point is not used because the assignments 0..cp and
           cp+1..ngen-1 are identical.
    
      Outstanding problems:
        1. Fitness is called at every generation.  This is unnecessary, since only
           the new parents need to be updated.
        2. Actual variables (X and Y) dont need to be stored.
        3. I suspect that the copy of the generation G2 is redundant. I plan to
           remove it.
    
      History
        24 Oct 2012 [2], Remove X and Y arrays
        24 Oct 2012 [3], Remove the second generation
    
      Bruce Wernick
      24 October 2012
      ----------------------------------------------------------------------------}
    
    program GAProject3;
    
    {$apptype console}
    
    uses
      Math;
    
    type
      float = double;
      fvec = array of float; // float vector
      bvec = array of byte;  // bit vector
      bmat = array of bvec;  // population matrix
    
    const
      tol = 1e-3;
    
    var
      pMut: float;   // probability of mutation
      pCross: float; // probability of crossover
      nbit: integer; // number of bits needed per variable
      npop: integer; // population size
      ngen: integer; // gnome length
      nvar: integer; // number of variables
      G: bmat;       // current generation
      f: fvec;       // fitness history
      fProb: fvec;   // probability of chromosone being selected
      q: fvec;       // cumulative probability
      b, w: integer; // index of best and worst chromosone
      fmax: float;   // maximum fitness
      fsum: float;   // sum of fitness
      best: bvec;    // bit vector of best
      its: integer;  // iteration counter
      imax: integer; // iteration limit
    
    procedure Init;
    {-init generation with random bits}
    var
      p, k: integer;
    begin
      for p := 0 to npop-1 do
        for k := 0 to ngen-1 do
          if random > 0.5 then G[p,k] := 1 else G[p,k] := 0;
    end;
    
    procedure CopyVec(var a, b: bvec);
    {-copy vector a to b}
    var
      k: integer;
    begin
      for k := 0 to ngen-1 do
        b[k] := a[k];
    end;
    
    procedure CopyMat(var a, b: bmat);
    {-copy matrix a to b}
    var
      p: integer;
    begin
      for p := 0 to npop-1 do
        CopyVec(a[p], b[p]);
    end;
    
    function fxy(x, y: float): float;
    {-user defined function,
      f(x,y) = (2.8125-x*(1.0-y**4))**2+(2.25-x*(1.0-y**2))**2+(1.5-x*(1.0-y))**2
      zero at (3,0.5)}
    begin
      result := IntPower((2.8125 - x*(1 - IntPower(y, 4))), 2) +
                IntPower((2.2500 - x*(1 - IntPower(y, 2))), 2) +
                IntPower((1.5000 - x*(1 - y)), 2);
    end;
    
    function BinToFloat(b: bvec; n: integer; MinValue, MaxValue: float): float;
    {-convert bit vector to floating point number}
    var
      i, k: integer;
      x: float;
    begin
      x := 0;
      k := 1;
      for i := 0 to nbit-1 do begin
        x := x + b[i+n]/k;
        k := 2 * k;
      end;
      result := MinValue + (MaxValue-MinValue)*x;
    end;
    
    procedure Fitness;
    {-calculate fitness (when fxy=0 then result=1/tol}
    var
      p, j: integer;
      x, y: float;
    begin
      b := 0;
      w := 0;
      fsum := 0;
      for p := 0 to npop-1 do begin
        x := BinToFloat(G[p], 0, 2, 4);
        y := BinToFloat(G[p], nbit, -1, 1);
        f[p] := 1/(tol+fxy(x,y)); // fitness
        fsum := fsum + f[p];
        if f[p]>f[b] then b := p;
        if f[p]<f[w] then w := p;
      end;
      fmax := f[b];
      CopyVec(G[b], best);
    
      // probability
      for p := 0 to npop-1 do begin
        fProb[p] := f[p]/fsum;
        q[p] := 0;
        for j := 0 to p do
          q[p] := q[p] + fProb[j];
      end;
    end;
    
    function Select: integer;
    {roulette wheel method}
    var
      r: float;
      i: integer;
    begin
      r := random;
      for i := 0 to npop-1 do begin
        if (r<=q[i]) then begin
          result := i;
          exit;
        end;
      end;
    end;
    
    procedure CrossOver;
    {-crossover 1/3 of population}
    var
      p, j: integer;
      p1, p2: integer; // parents
      cp: integer; // random crossover point
      temp: byte;
    begin
      // select 2 unique parents
      for p := 0 to npop div 3 do begin
        p1 := Select;
        repeat
          p2 := Select;
        until p1<>p2;
    
        // new generation by single (random) point crossover
        if random < pCross then begin
          cp := RandomRange(2, ngen-5); // with limited range
          for j := cp to ngen-1 do begin
            temp := G[p1,j];
            G[p1,j] := G[p2,j];
            G[p2,j] := temp;
          end;
        end;
      end;
    end;
    
    procedure Mutate;
    {-mutate whole gene pool}
    var
      p, k: integer;
    begin
      for p := 0 to npop-1 do begin
        if p=b then continue; // not the best
        for k := 0 to ngen-1 do
          if random < pMut then
            if G[p,k] = 0 then G[p,k] := 1 else G[p,k] := 0;
      end;
    end;
    
    procedure Elitism;
    begin
      CopyVec(best, G[w]); // replace the worst
    end;
    
    procedure ShowResults;
    var
      p: integer;
      x, y: float;
    begin
      for p := 0 to npop-1 do begin
        x := BinToFloat(G[p], 0, 2, 4);
        y := BinToFloat(G[p], nbit, -1, 1);
        writeln(x:8:2, ' ', y:8:2, ' ', fxy(x,y):12:3);
      end;
      writeln('-------------------------------');
      x := BinToFloat(G[b], 0, 2, 4);
      y := BinToFloat(G[b], nbit, -1, 1);
      writeln(x:8:2, ' ', y:8:2, ' ', fxy(x,y):12:3);
      writeln(its:4, ' iterations');
      readln;
    end;
    
    begin
      randomize;
      imax := 800; // maximum number of generations
      npop := 25; // population size
      pMut := 0.01; // mutation probability
      pCross := 0.7; // crossover probability
      nvar := 2; // number of variables
      Nbit := 12; // number of bits per variable
      ngen := nvar*nbit; // genome size
    
      // make space for data
      SetLength(G, npop, ngen);
      SetLength(best, ngen);
      SetLength(f, npop);
      SetLength(fProb, npop);
      SetLength(q, npop);
    
      Init;
      for its := 0 to imax do begin
        Fitness; // calc fitness of whole population
        CrossOver;
        Mutate;
        Elitism;
        if f[b]>(0.95/tol) then break;
      end;
      ShowResults;
    end.
    

    Submitted on 2012/10/24 at 6:14 am by brucecortez.
    Pity that the formatting is lost but if you open in Delphi 2010, Right-Click and auto format.

    Submitted on 2012/10/24 at 5:39 am by brucecortez.
    Thanks

    When I re-read my earlier comments, it sounds like brutal criticism. But it wasn’t intended to be so, l am learning about GA and as I worked through your code, I made notes for myself. I believe the questions are valid but could be explained more. Actually, your code has given me some good ideas and helped me to understand the algorithm. The most important part I did was remove the plotting, NFL… and simplify the logic down to the bare bones of GA. I also wanted to experiment with Elitism and different crossover strategies. For equations like these, Elitism seems to be significant.

    I have written a simple Delphi console app and will be happy post it here.

    Submitted on 2012/10/24 at 6:10 am by brucecortez.

    { —————————————————————————-
    Genetic Algorithm Example
    
    The equation that I solve here is from Gandhi Manalu.
    f(x,y) = (2.8125-x*(1.0-y**4))**2+(2.25-x*(1.0-y**2))**2+(1.5-x*(1.0-y))**2
    Expected answer is f(3.0,0.5)=0.0
    http://gandhim.wordpress.com/2010/04/04/particle-swarm-optimization-pso-sample-code-using-java/
    He used it to demonstrate Particle Swarm Optimization but I am now using it to
    compare PSO to GA.
    
    GA example of Syeilendra Pramuditya used as a reference
    https://syeilendrapramuditya.wordpress.com/2008/08/04/a-little-example-of-genetic-algorithm-ga-in-action/
    
    These questions need to be addressed:
    1. Why recalculate the fitness of the whole population on every iteration
    when you only need to update the ones that changed?
    2. Why use fixed oversized arrays when it is so easy to set the size
    dynamically?
    3. Why use a whole population data structure for the best when you only
    need a single vector?
    4. Why mutate the whole population on every iteration? You are only
    supposed to mutate the current offspring.
    5. Is 10 bits enough accuracy for the floating point numbers?
    resolution = range/2^nbit = 4/2^10 = 0.0039
    With 24-bits, 4.0/2^24 = 2.38e-07
    6. Why iterate for the full number of iterations when you could exit
    once an answer is reached?
    7. Why store the decoded floating point numbers when they are not needed?
    8. The crossover point is not used because the assignments 0..cp and
    cp+1..ngen-1 are identical.
    
    Outstanding problems:
    1. Fitness is called at every generation. This is unnecessary, since only
    the new parents need to be updated.
    2. Actual variables (X and Y) dont need to be stored.
    3. I suspect that the copy of the generation G2 is redundant. I plan to
    remove it.
    
    Bruce Wernick
    24 October 2012
    —————————————————————————-}
    
    program GAProject;
    
    {$apptype console}
    
    uses
    Math;
    
    type
    float = double;
    fvec = array of float; // float vector
    bvec = array of byte; // bit vector
    bmat = array of bvec; // population matrix
    
    const
    tol = 1e-3;
    
    var
    pMut: float; // probability of mutation
    pCross: float; // probability of crossover
    nbit: integer; // number of bits needed per variable
    npop: integer; // population size
    ngen: integer; // gnome length
    nvar: integer; // number of variables
    G1, G2: bmat; // current and last generation
    x, y, f: fvec; // actual variables (x,y) and fitness value
    fProb: fvec; // probability of chromosone being selected
    q: fvec; // cumulative probability
    b, w: integer; // index of best and worst chromosone
    fmax: float; // maximum fitness
    fsum: float; // sum of fitness
    best: bvec; // bit vector of best
    its: integer; // iteration counter
    imax: integer; // iteration limit
    
    procedure Init;
    {-init generation with random bits}
    var
    p, k: integer;
    begin
    for p := 0 to npop-1 do
    for k := 0 to ngen-1 do
    if random > 0.5 then G1[p,k] := 1 else G1[p,k] := 0;
    end;
    
    procedure CopyVec(var a, b: bvec);
    {-copy vector a to b}
    var
    k: integer;
    begin
    for k := 0 to ngen-1 do
    b[k] := a[k];
    end;
    
    procedure CopyMat(var a, b: bmat);
    {-copy matrix a to b}
    var
    p: integer;
    begin
    for p := 0 to npop-1 do
    CopyVec(a[p], b[p]);
    end;
    
    function fxy(x, y: float): float;
    {-user defined function, zero at (3,0.5)}
    begin
    result := IntPower((2.8125 – x*(1 – IntPower(y, 4))), 2) +
    IntPower((2.2500 – x*(1 – IntPower(y, 2))), 2) +
    IntPower((1.5000 – x*(1 – y)), 2);
    end;
    
    function BinToFloat(b: bvec; n: integer; MinValue, MaxValue: float): float;
    {-convert bit vector to floating point number}
    var
    i, k: integer;
    x: float;
    begin
    x := 0;
    k := 1;
    for i := 0 to nbit-1 do begin
    x := x + b[i+n]/k;
    k := 2 * k;
    end;
    result := MinValue + (MaxValue-MinValue)*x;
    end;
    
    procedure Fitness;
    {-calculate fitness (when fxy=0 then result=1/tol}
    var
    p, j: integer;
    begin
    b := 0;
    w := 0;
    fsum := 0;
    for p := 0 to npop-1 do begin
    x[p] := BinToFloat(G1[p], 0, 2, 4);
    y[p] := BinToFloat(G1[p], nbit, -1, 1);
    f[p] := 1/(tol+fxy(x[p],y[p])); // fitness
    fsum := fsum + f[p];
    if f[p]>f[b] then b := p;
    if f[p]<f[w] then w := p;
    end;
    fmax := f[b];
    CopyVec(G1[b], best);
    
    // probability
    for p := 0 to npop-1 do begin
    fProb[p] := f[p]/fsum;
    q[p] := 0;
    for j := 0 to p do
    q[p] := q[p] + fProb[j];
    end;
    end;
    
    function Select: integer;
    {roulette wheel method}
    var
    r: float;
    i: integer;
    begin
    r := random;
    for i := 0 to npop-1 do begin
    if (r<=q[i]) then begin
    result := i;
    exit;
    end;
    end;
    end;
    
    procedure CrossOver;
    {-crossover 1/3 of population}
    var
    p, j: integer;
    p1, p2: integer; // parents
    cp: integer; // random crossover point
    begin
    // select 2 unique parents
    for p := 0 to npop div 3 do begin
    p1 := Select;
    repeat
    p2 := Select;
    until p1p2;
    
    // new generation by single (random) point crossover
    if random < pCross then begin
    cp := RandomRange(2, ngen-5); // with limited range
    for j := cp to ngen-1 do begin
    G2[p1,j] := G1[p2,j];
    G2[p2,j] := G1[p1,j];
    end;
    end;
    end;
    end;
    
    procedure Mutate;
    {-mutate whole gene pool}
    var
    p, k: integer;
    begin
    for p := 0 to npop-1 do begin
    if p=b then continue; // not the best
    for k := 0 to ngen-1 do
    if random (0.95/tol) then break;
    end;
    ShowResults;
    end.
    
  3. unique said

    thanks you really helped me with code and algorthims

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: