Roulette wheel

[mattia]

Il Thu, 05 Mar 2009 15:48:01 +0000, mattia ha scritto:

> Il Wed, 04 Mar 2009 21:30:54 +0100, Peter Otten ha scritto:
> 
>> mattia wrote:
>> 
>>> Hi everyone, I'm new to python and I want to create some simple code
>>> in order to code the classical genetic algorithm example: given a
>>> population of chromosomes, encoded using 1 and 0, find the chromosome
>>> with the maximum number of 1s. Now, despite all the code used to
>>> implement the solution, I'm wondering if there is a better way to use
>>> the so-called roulette wheel selection in this problem. Here I paste
>>> the code of my solution, any advice will be helpful:
>> 
>> Your code looks good to me.
>> 
>>> from random import randint, random
>>> 
>>> def create_chromosome(min, max, length):
>>>     chromosome = []
>>>     for i in range(length):
>>>         chromosome.append(randint(min, max))
>>>     return chromosome
>>> 
>>> def fitness(chrm, ffunc=sum):
>>>     return ffunc(chrm)
>> 
>> fitness = sum
>> 
>> has the same effect, without the extra indirection.
>>  
>>> def create_population(nelem, min, max, length):
>>>     return [create_chromosome(min, max, length) for i in range(nelem)]
>>> 
>>> def get_fitness_and_population(population):
>>>     return [(fitness(x), x) for x in population]
>>>     
>>> def get_roulette_wheel(population):
>>>     roulette_wheel = []
>>>     index = 0
>>>     
>>>     for x in get_fitness_and_population(population):
>>>         for j in range(x[0]):
>>>             roulette_wheel.append(index)
>>>         index += 1
>> 
>> Make that
>> 
>>       for index, x in
>>       enumerate(get_fitness_and_population(population)):
>>           ...
>> 
>> I'd also pass the the fitness function explicitly around instead of
>> making it a global.
>> 
>>>     return roulette_wheel
>>> 
>>> pop = create_population(5, 0, 1, 10)
>>> rw = get_roulette_wheel(pop)
>>> print(rw)
>>> print(len(rw))
>>> ri = randint(0, len(rw) - 1)
>>> print("Random index:", rw[ri], ", value:", pop[rw[ri]])
>> 
>> But these are minor nits :)
>> 
>> Here's a slightly different approach:
>> 
>> from random import randint, choice
>> 
>> def create_chromosome(min, max, length):
>>     return [randint(min, max) for i in range(length)]
>> 
>> def create_population(nelem, min, max, length):
>>     return [create_chromosome(min, max, length) for i in range(nelem)]
>> 
>> def get_fitness_and_population(population, fitness):
>>     return [(fitness(x), x) for x in population]
>> 
>> def get_roulette_wheel(weight_value_pairs):
>>     roulette_wheel = []
>>     for weight, value in weight_value_pairs:
>>         roulette_wheel += [value]*weight
>>     return roulette_wheel
>> 
>> if __name__ == "__main__":
>>     pop = create_population(5, 0, 1, 10)
>>     fap = get_fitness_and_population(pop, sum) rw =
>>     get_roulette_wheel(fap)
>>     print("Random value:", choice(rw))
>> 
>> Note how get_roulette_wheel() is now completeley independent of the
>> concrete problem you are using it for.
>> 
>> Peter
> 
> The last question: how can I improve readability in this piece of code?
> 
> def crossover(pop, prob=0.6):
>     """
>     With a crossover probability cross over the parents to form new
>     offspring. If no crossover was performed, offspring is the exact
>     copy of parents. """
>     cpop = []
>     for i in range(0, len(pop), 2):
>         # crossover
>         if prob > random():
>             crossover_point = randint(0, len(pop[i])-1) nchromosome1 =
>             pop[i][:crossover_point] + pop[i+1][crossover_point:]
>             nchromosome2 = pop[i+1][:crossover_point] +
>             pop[i][crossover_point:]
>         else:
>             nchromosome1 = pop[i][:]
>             nchromosome2 = pop[i+1][:]
>         cpop += [nchromosome1] + [nchromosome2]
>     return cpop
> 
> And with this one my example is complete!

Wow, lots of things to learn here (remember that I'm new to python). You 
both used zip and yield, I'll go check it out in the python 
documentation ;-)