Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I am trying to understand how genetic algorithms work. As with everything, I learn by attempting to write something on my own;however, my knowledge is very limited and I am not sure if I am doing this right.

The purpose of this algorithm is to see how long it will take half of a herd to be infected by a disease if half of that population are already infected. It is just an example I came up with in my head so I am not sure if this would even be a viable example.

Some feedback on how I can improve my knowledge would be nice.

Here is the code:

import random

def disease():
    herd = []
    generations = 0
    pos = 0
    for x in range(100):
        herd.append(random.choice('01'))
    print herd
    same = all(x == herd[0] for x in herd)
    while same == False:
        same = all(x == herd[0] for x in herd)
        for animal in herd:
            try:
                if pos != 0:
                    after = herd[pos+1]
                    before = herd[pos-1]
                    if after == before and after == '1' and before == '1' and animal == '0':
                        print "infection at", pos
                        herd[pos] = '1'
            #print herd
                pos += 1
            except IndexError:
                pass
        pos = 0
        generations += 1
        random.shuffle(herd)
        #print herd
    print "Took",generations,"generations to infect all members of herd."
if __name__ == "__main__":
    disease()

I am looking for comments based on the logic of this algorithm. What can be improved, and what has to be improved to make this a true genetic algorithm if it isn't one already.

share|improve this question
add comment

3 Answers 3

up vote 5 down vote accepted

your algorithm is not a genetic algorithm, it is a simple model of infection.

genetic algorithm normally uses at least the following concepts: inheritance, mutation, selection (or fitness).
see, e.g. here

if - for the sake of introductory understanding - you want to apply these concepts to your example:

  • inheritance:
    conceptual: you need a genetic identity of your unit (the animal).
    code: i.e. you need animals with state, different instances.
    how: each animal inherits this genetic identity to the next generation when it is reproduced.
  • mutation:
    conceptual: each generation is slightly different from the other.
    code: each animal in a new generation has slightly different values than its parent.
    how: apply some random modification.
  • selection of fitness:
    conceptual: you select which units are reproduced for the next generation by the differences between the units. choose the fittest.
    code: when assembling the new generation, choose only those units for reproduction that satisfy a certain fitness limit (e.g. the best 90%).
    how: define a fitness-function which returns a value indicating relative fitness for each unit.

to put it together, you could make e.g. different herds of animals that have different starting values for the 'genetic' attributes (e.g. preferred_proximity_to_next_animal, skin_color, height, aggressiveness, etc .).
Then, in your fitness function, you define how each of the attributes is connected to fitness, i.e. how they are related to the probability to get infected. then let the program run for a some of generations and see how at each iteration the global probability of infection decrease in relation to the genetic setup of your herd.

Like that you might find favourable combinations of attributes. Generally, genetic algorithms are used in search-related problems.

share|improve this answer
    
Thank you, this was a great response! –  Max00355 Feb 9 '13 at 14:44
add comment
import random

def disease():
    herd = []
    generations = 0
    pos = 0

Don't assign variables ahead of their use

    for x in range(100):
        herd.append(random.choice('01'))
    print herd
    same = all(x == herd[0] for x in herd)
    while same == False:
        same = all(x == herd[0] for x in herd)

Firstly, don't check for == False, use not. Also, there isn't any point in storing it in same, just test it:

 while not all(x == herd[0] for x in herd):

I'd suggest testing using:

while len(set(herd)) != 1:

Which will be more efficient.

        for animal in herd:
            try:
                if pos != 0:
                    after = herd[pos+1]
                    before = herd[pos-1]
                    if after == before and after == '1' and before == '1' and animal == '0':

There is no point in checking if after == before if you are already checking that after and before are both equal to '1'. I'd consider doing:

if (after, animal, before) == ('1','0','1'):

which in this case I think shows more clearly what's going on.

                        print "infection at", pos
                        herd[pos] = '1'
            #print herd
                pos += 1
            except IndexError:
                pass

Its generally not a good idea to catch an IndexError. Its too easy to get an accidental IndexError and then have your code miss the real problem. It also doesn't communicate why you are getting an index error.

Instead of updating pos, I suggest you use

for pos, animal in enumerate(herd):

However, since you don't want the first and last elements anyways, I'd suggest

 for pos in xrange(1, len(herd) - 1):
     before, animal, after = herd[pos-1,pos+2]

Back to your code:

        pos = 0

You should reset things just before a loop, not afterwards. That way its easier to follow. Although its even better if you can avoid the resting altogether

        generations += 1
        random.shuffle(herd)
        #print herd
    print "Took",generations,"generations to infect all members of herd."
if __name__ == "__main__":
    disease()
share|improve this answer
    
This was an amazing response. Thank you for breaking down my code, it was really informative. –  Max00355 Feb 10 '13 at 1:42
add comment

Extract methods initHerd, processGeneration and infect.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.