Velocity Reviews > Re: Roulette wheel

# Re: Roulette wheel

Peter Otten
Guest
Posts: n/a

 03-04-2009
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

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

Peter Otten
Guest
Posts: n/a

 03-05-2009
mattia wrote:

>> Note how get_roulette_wheel() is now completeley independent of the
>> concrete problem you are using it for.

>
> Ok, but also a lot more memory consuming

I don't think so. Python references objects; therefore the list

[tiny_little_thing]*N

does not consume more memory than

[big_fat_beast]*N

Or did you have something else in mind?

Peter

Peter Otten
Guest
Posts: n/a

 03-05-2009
mattia wrote:

> Il Thu, 05 Mar 2009 10:46:58 +0100, Peter Otten ha scritto:
>
>> mattia wrote:
>>
>>>> Note how get_roulette_wheel() is now completeley independent of the
>>>> concrete problem you are using it for.
>>>
>>> Ok, but also a lot more memory consuming

>>
>> I don't think so. Python references objects; therefore the list
>>
>> [tiny_little_thing]*N
>>
>> does not consume more memory than

Oops, should have been less.

>>
>> [big_fat_beast]*N
>>
>> Or did you have something else in mind?
>>
>> Peter

>
> Ok, understood. So if I have e.g. [[200 elements]]*N, then I'll have N
> pointers to the same location of my seq, right?

Right. You can verify this with

>>> v = [0]
>>> items = [v]*5
>>> v[0] = 42
>>> items

[[42], [42], [42], [42], [42]]

which often surprises newbies.

Peter

Peter Otten
Guest
Posts: n/a

 03-05-2009
mattia wrote:

> 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]

I'd write that as

cpop.append(nchromosome1)
cpop.append(nchromosome2)

thus avoiding the intermediate lists.

> return cpop
>
> And with this one my example is complete!

Just for fun here's an alternative version of your function

def generate_crossover(pop, prob):
for a, b in zip(*[iter(pop)]*2):
if prob > random():
cut = randrange(len(a))
a, b = a[:cut] + b[cut:], b[:cut] + a[cut:]
yield a
yield b

def crossover(pop, prob=0.6):
return list(generate_crossover(pop, prob))

but as the original is a bit clearer I recommend that you stick with it.

Peter

Peter Pearson
Guest
Posts: n/a

 03-05-2009
On Thu, 05 Mar 2009 18:07:29 +0100, Peter Otten <(E-Mail Removed)> wrote:
[snip]
>
> Just for fun here's an alternative version of your function
>
> def generate_crossover(pop, prob):
> for a, b in zip(*[iter(pop)]*2):

.. . .

Good grief! That's devilishly obscure.

--
To email me, substitute nowhere->spamcop, invalid->net.

Peter Pearson
Guest
Posts: n/a

 03-06-2009
On 05 Mar 2009 20:43:41 GMT, mattia <(E-Mail Removed)> wrote:
>> for a, b in zip(*[iter(pop)]*2):

> In the python documentation there is a similar example, well, the obscure
> thing here is the usage of *[iter(pop)]! Then I believe that I can safely
> say that you iterate over the values 0 and 1, 2 and 3 etc. because the
> zip automatically updates the index, in this case using the same sequence
> the index counter is shared and the second sequence start from that
> shared counter. Am I right?

I don't think zip updates "the index"; rather, it merely
asks for the next element from each iterator in its argument
list. But that's probably what you meant. Just to be sure,
it might be helpful to point out the equivalence of these
two code snippets:

>>> x = [ 1, 2, 3, 4, 5, 6 ]

>>> zip(*[iter(x)]*2)

[(1, 2), (3, 4), (5, 6)]

>>> i = iter(x)
>>> zip(i, i)

[(1, 2), (3, 4), (5, 6)]

So the whole *[iter(x)]*2 construction (which parses as *([iter(x)]*2))
is a trick for getting an argument list comprising several
references to a single iterator.

--
To email me, substitute nowhere->spamcop, invalid->net.

Aahz
Guest
Posts: n/a

 03-18-2009
In article <gop0se\$7hu\$01\$(E-Mail Removed)-online.com>,
Peter Otten <(E-Mail Removed)> wrote:
>mattia wrote:
>>
>> cpop += [nchromosome1] + [nchromosome2]

>
>I'd write that as
>
>cpop.append(nchromosome1)
>cpop.append(nchromosome2)
>
>thus avoiding the intermediate lists.

You could also write it as

cpop += [nchromosome1, nchromosome2]

which may or may not be faster, substituting one attribute lookup, one
list creation, and one method call for two attribute lookups and two
method calls. I shan't bother running timeit to check, but I certainly
agree that either your version or mine should be substituted for the
original, depending on one's esthetics (meaning that I doubt there's
enough performance difference either way to make that the reason for
choosing one).
--
Aahz ((E-Mail Removed)) <*> http://www.pythoncraft.com/

"Programming language design is not a rational science. Most reasoning
about it is at best rationalization of gut feelings, and at worst plain
wrong." --GvR, python-ideas, 2009-3-1

Aahz
Guest
Posts: n/a

 03-18-2009
In article <49c1562a\$0\$1115\$(E-Mail Removed)>,
mattia <(E-Mail Removed)> wrote:
>
>Yeah, and I believe that we can say the same for:
>1 - t = [x*2 for x in range(10)]
>2 - t = list(x*2 for x in range(10))
>or not?

The latter requires generator expressions, which means it only works with
Python 2.4 or higher. Personally, I think that if the intent is to
create a list you should just use a listcomp instead of list() on a
genexp.
--
Aahz ((E-Mail Removed)) <*> http://www.pythoncraft.com/

"Programming language design is not a rational science. Most reasoning
about it is at best rationalization of gut feelings, and at worst plain
wrong." --GvR, python-ideas, 2009-3-1

Gabriel Genellina
Guest
Posts: n/a

 03-19-2009
En Wed, 18 Mar 2009 18:49:19 -0200, mattia <(E-Mail Removed)> escribió:
> Il Wed, 18 Mar 2009 13:20:14 -0700, Aahz ha scritto:
>> In article <49c1562a\$0\$1115\$(E-Mail Removed)>, mattia
>> <(E-Mail Removed)> wrote:
>>>
>>> Yeah, and I believe that we can say the same for: 1 - t = [x*2 for x in
>>> range(10)]
>>> 2 - t = list(x*2 for x in range(10))
>>> or not?

>> The latter requires generator expressions, which means it only works
>> with Python 2.4 or higher. Personally, I think that if the intent is to
>> create a list you should just use a listcomp instead of list() on a
>> genexp.

> Ok, so list(x*2 for x in range(10)) actually means: list((x*2 for x in
> range(10)) --> so a generator is created and then the list function is
> called?

Exactly. The (()) were considered redundant in this case.

> Also, dealing with memory, [...] will be deleted when the
> reference will be no longer needed and with list(...)... well, I don't
> know? I'm new to python so sorry if this are nonsense.

I don't completely understand your question, but *any* object is destroyed
when the last reference to it is gone (in CPython, the destructor is
called at the very moment the reference count reaches zero; other
implementations may behave differently).

--
Gabriel Genellina

Gabriel Genellina
Guest
Posts: n/a

 03-19-2009
En Thu, 19 Mar 2009 08:06:35 -0200, mattia <(E-Mail Removed)> escribió:

> OK, understood. Now, as a general rule, is it correct to say:
> - use generator expression when I just need to iterate over the list or
> call a function that involve an iterator (e.g. sum) and get the result,
> so the list is not necessary anymore
> - use list comprehensions when I actually have to use the list (e.g. I
> need to swap some values or I need to use sorted() etc.)
> Am I right?

Yes, at least that's how I use them: a generator expression when the
elements are consumed one by one in
the same moment, and a list comprehension when I actually want the list as
a whole.

(Note that sorted() has to return a new list anyway, its argument may be a
gen.expr. but sorted() starts by making a list out of it; you may be
thinking of the list.sort() method)

--
Gabriel Genellina