# What is wrong with my Genetic Algorithm?

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.

-

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.

-
Thank you, this was a great response! –  Max00355 Feb 9 '13 at 14:44
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]


        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()

-
This was an amazing response. Thank you for breaking down my code, it was really informative. –  Max00355 Feb 10 '13 at 1:42

Extract methods initHerd, processGeneration and infect.

-