CODEWITHSUNDEEP
pythongenetic-algorithm
Nick
Nick

Reputation: 9373

Python genetic algorithm for binary number

I'm asked to make a genetic algorithm with the goal to determine an 8 bit string with the the most 1's and 0's. The eval function should return the number of changes plus 1. So for example 00000000 returns 1, 00011100 returns 3, and 01100101 returns 6. This is what I have:

def random_population():
    from random import choice

    pop = ''.join(choice(('0','1')) for _ in range(8))
    return pop   

def mutate(dna):   
    """   For each gene in the DNA, there is a 1/mutation_chance chance 
    that it will be   switched out with a random character. This ensures 
    diversity in the   population, and ensures that is difficult to get stuck in 
    local minima.   """   
    dna_out = ""   
    mutation_chance = 100   
    for c in xrange(DNA_SIZE):
        if int(random.random()*mutation_chance) == 1:
            dna_out += random_char()
        else:
            dna_out += dna[c]   return dna_out

def crossover(dna1, dna2):   
    """   Slices both dna1 and dna2 into two parts at a random index within their   
    length and merges them. Both keep their initial sublist up to the crossover   
    index, but their ends are swapped.   """   
    pos = int(random.random()*DNA_SIZE)
    return (dna1[:pos]+dna2[pos:], dna2[:pos]+dna1[pos:])

def eval(dna):
    changes = 0
    for index, bit in enumerate(dna):
        if(index == 0):
            prev = bit
        else:
            if(bit != prev):
                changes += 1
        prev = bit
    return changes+1


#============== End Functions =======================#


#============== Main ================# changes = 0

prev = 0
dna = random_population()
print "dna: "
print dna
print eval(dna)

I am having trouble actually figuring out the genetic algorithm part (cross over / mutation). I should randomly pair the numbers and then randomly select a pair leaving one pair untouched and then cross over at a random point. Then it will end by randomly mutating one bit out of the entire population. The current code for crossover and mutate was just taken from a genetic algorithm example I found and was trying to understand. Any fhelp is welcome.

Upvotes: 2

Views: 4236

Answers (2)

Jeff H.
Jeff H.

Reputation: 1

One thing that I have found that I like to do is this:

  1. Select the top candidates of your last batch lets say 5.
  2. Have 1 mate with 2, 3, 4, 5.
  3. Have 2 mate with 3, 4, 5
  4. Have 3 mate with 4 and 5
  5. Have 4 mate with 5. Generally your population will already be full before you reach this point if you let the original 5 into the next gen and each mating results in 2 offspring. One mating and its opposite twin.
  6. As far as the actual crossing I like to randomly cut the chromosomes at a point between 40% and 60% of the length, then at the next mating I pick another random point in the range.
  7. After I have mated them I go over every bit in my chromosome and give it roughly a !5% chance of flipping or mutating
  8. Sometimes I also let some of the worst two mate as well to lower my chance of a local maxima or minima

I hope this was a little helpful to you.

-Jeff

EDIT: Oh my this was asked in April. Sorry for grave digging.

Upvotes: 0

User
User

Reputation: 14853

Part of what I would suggest:

The code is not working but maybe it transports information.

# a population consists of many individuals
def random_population(population_size = 10):
    from random import choice

    pop = [''.join(choice(('0','1')) for _ in range(8)) for i in range(population_size)]
    return pop   

# you need a fitness function
def fitness(individual):
    return # a value from 0 up

def algorithm():
    # a simple algorithm somehow alike
    # create population
    population = random_population()
    # this loop must stop after some rounds because the best result may never be reached
    while goal_not_reached(population) and not time_is_up():
        # create the roulette wheel
        roulette_wheel = map(fitness, population)
        # highest value of roulette wheel
        max_value = sum(roulette_wheel)
        # the new generation
        new_population = []
        for i in range(len(population) - len(new_population)):
             # create children from the population
                 # choose 2 random values from 0 to max_value and find the individuals
                 # for it in the roulette wheel, combine them to new individuals 
             new_population.append(new_individual)
        # mutate the population
        population = map(mutate, new_population)             # a new generation is created

Upvotes: 1

Related Questions