7

I have to solve the Travelling Salesman Problem using a genetic algorithm that I will have to write for homework.

The problem consists of 52 cities. Therefore, the search space is 52!. I need to randomly sample (say) 1000 permutations of range(1, 53) as individuals for the initial population of my genetic algorithm.

In order to do this, I tried:

>>> random.sample(itertools.permutations(range(1, 53)), 1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python2.6/random.py", line 314, in sample
    n = len(population)
TypeError: object of type 'itertools.permutations' has no len()

So I tried

>>> random.sample(list(itertools.permutations(range(1, 53))), 1000)

However, given that 52! is VERY large, the list operation is maxing out the memory and swap space on my computer. I can't just pick the first 1000 permutations generated by itertools.permutations because it's very deterministic and that would bias my genetic algorithm.

Is there a better way to achieve this sampling?

Community
  • 1
  • 1
inspectorG4dget
  • 110,290
  • 27
  • 149
  • 241

1 Answers1

7

You don't need to permute at all. Call random.sample(range(52), 52) 1000 times.

P.S.: You really should use zero-based indexing (range(52) as opposed to range(1, 53)) in all your work. Things generally work out better that way.

Marcelo Cantos
  • 181,030
  • 38
  • 327
  • 365
  • I totally agree with your zero based indexing, but the indeces here represent the City IDs and my Prof decided that he wants to start from 1... So I'm trying to stay true to his convention – inspectorG4dget Jan 28 '12 at 23:56
  • 7
    It's been my experience that you should just do it your own way and convert it to your professor's shitty conventions in your output statements. – machine yearning Jan 29 '12 at 00:01
  • 1
    Wait, for a random _permutation_ shouldn't this be `p = range(10); random.shuffle(p)`? `random.sample` will duplicate some values and omit others. But perhaps you're saying that these don't actually have to be permutations... – senderle Jan 29 '12 at 00:06
  • 3
    @senderle random.sample works *without* replacement do it does indeed produce a permutation. When the sample size is the same as the population size, it is equivalent to random.shuffle() on the population (except that shuffle with shuffle in-place and sample will leave the original unchanged). – Raymond Hettinger Jan 29 '12 at 00:21