Front page   Edit Freeze Diff Backup Upload Copy Rename Reload   New List of pages Search Recent changes   Help   RSS of recent changes

The Microbial Genetic Algorithm

Last-modified: 2012-08-20 (Mon) 00:29:30 (1915d)
Top / The Microbial Genetic Algorithm

Under Construction!

This page is just for my study. I've not finished editing yet. If you are interested in the Microbial GA, I recommend getting Prof. Harvey's papers, see References and Links section at the bottom of this page.

Description & Sample Program

This is a sample program of the Microbial Genetic Algorithm (the Microbial GA) proposed by Prof. Inman Harvey. The code was written by reference to [1].

The Microbial GA works for the population of genotypes, which are designed by a user to attain his/her goal. Two genotypes are picked up at random, and then their fitnesses are evaluated. The genotype that has a higher fitness is the winner, and the other is the loser (Rank-based Selection). By copying the segment of the winner genotype to the loser genotypes at the same locus, new offspring is generated, and the loser genotype is deleted from the population. Unlike basic GAs, in the Microbial GA, only one offspring is generated at a time, and then the loser genotype is replaced by the new one (Steady State Method). The following program code, which is found in [1], executes this procedure. It is so simple!

void microbial_tournament()
{
    int a, b, c, W, L;
    int i;

    a = (int)((POP-1) * drand01());
    do {
        b = (int)((POP-1) * drand01());
    } while (a == b);

    if (evaluate(a) > evaluate(b)){
        W = a;
        L = b;
    }
    else {
        W = b;
        L = a;
    }

    for (c = (int)(LEN * drand01()), i = 0; i < SEG; i++) {
        gene[L][(c+i)%LEN] = gene[W][(c+i)%LEN];
    }

    for (i = 0; i < LEN; i++) {
        if (drand01() < MUT) gene[L][i] ^= 1;
    }
}

Designing an appropriate function to evaluate the fitness of a genotype is significant to attain the goal of the designer. In the sample program, the aim of the Microbial GA is to make the genotype that is an alternate string of '1' and '0', ( 1, 0, 1, 0,... ). This is just a humble exercise. The evaluation function shown below was adopted to attain the desired genotype.

int evaluate(int pop)
{
    int fit = 0;
    int i;

    for (i = 0; i < LEN; i++) {
        if (i%2 == 0) fit += gene[pop][i];
        else fit -= gene[pop][i];
    }

    return fit;
}

In the sample program, the length of the genotype is 20, the size of the population is 80, and the mutation rate is 1/20.

The following graph shows the result, the history of the maximum and average evaluation values, and the average Hamming distance. The desired genotype has been obtained within less than 4000 steps.

MicrobialGATest_graph.jpg

References

You can find these papers at Prof. Harvey's website.

  1. I. Harvey, The Microbial Genetic Algorithm, 1996
  2. I. Harvey, Artificial Evolution: A Continuing SAGA, in Evolutionary Robotics. From Intelligent Robotics to Artificial Life, Lecture Notes in Computer Science, pp. 94-109, 2001

Links


Attach file: fileMicrobialGATest.cpp 1091 download [Information] fileMicrobialGATest_graph.jpg 1272 download [Information]