Re: Roulette wheel

Discussion in 'Python' started by Peter Otten, Mar 4, 2009.

  1. Peter Otten

    Peter Otten Guest

    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
    Peter Otten, Mar 4, 2009
    #1
    1. Advertising

  2. Peter Otten

    Peter Otten Guest

    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, Mar 5, 2009
    #2
    1. Advertising

  3. Peter Otten

    Peter Otten Guest

    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, Mar 5, 2009
    #3
  4. Peter Otten

    Peter Otten Guest

    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)-1)
    > nchromosome1 = pop[:crossover_point] +
    > pop[i+1][crossover_point:] nchromosome2 =
    > pop[i+1][:crossover_point] + pop[crossover_point:]
    > else:
    > nchromosome1 = pop[:]
    > 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 Otten, Mar 5, 2009
    #4
  5. On Thu, 05 Mar 2009 18:07:29 +0100, Peter Otten <> 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, Mar 5, 2009
    #5
  6. On 05 Mar 2009 20:43:41 GMT, mattia <> 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.
    Peter Pearson, Mar 6, 2009
    #6
  7. Peter Otten

    Aahz Guest

    In article <gop0se$7hu$01$-online.com>,
    Peter Otten <> 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 () <*> 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, Mar 18, 2009
    #7
  8. Peter Otten

    Aahz Guest

    In article <49c1562a$0$1115$>,
    mattia <> 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 () <*> 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, Mar 18, 2009
    #8
  9. En Wed, 18 Mar 2009 18:49:19 -0200, mattia <> escribió:
    > Il Wed, 18 Mar 2009 13:20:14 -0700, Aahz ha scritto:
    >> In article <49c1562a$0$1115$>, mattia
    >> <> 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, Mar 19, 2009
    #9
  10. En Thu, 19 Mar 2009 08:06:35 -0200, mattia <> 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
    Gabriel Genellina, Mar 19, 2009
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Wes Groleau

    Reinventing a square wheel

    Wes Groleau, Aug 21, 2003, in forum: Perl
    Replies:
    0
    Views:
    975
    Wes Groleau
    Aug 21, 2003
  2. nicholas
    Replies:
    1
    Views:
    5,050
    Kevin Spencer
    Dec 16, 2004
  3. Ronald Fischer
    Replies:
    1
    Views:
    15,245
    Jacob
    Jul 22, 2003
  4. Guest
    Replies:
    0
    Views:
    491
    Guest
    Sep 26, 2003
  5. Semih Ozkoseoglu

    Roulette & rand

    Semih Ozkoseoglu, Sep 25, 2009, in forum: Ruby
    Replies:
    21
    Views:
    314
    Semih Ozkoseoglu
    Sep 27, 2009
Loading...

Share This Page