[Haskell-beginners] Randomness woes

Erlend Hamberg ehamberg at gmail.com
Sun Jan 10 12:25:20 EST 2010

Hello, everyone.

I'm experimenting with making a simple genetic algorithm test in Haskell and 
have some questions about how to “propagate” randomness to the various 
functions and about how to do the final iteration. I have used MonadRandom 
which already have simplified the program quite a bit. The main functions in 
my program are:

(Fitness is a Double, Genome is String of ones and zeros)


-- calculates the fitness of the given genome
fitness :: Genome -> Fitness

-- takes a genome and a list of booleans and flips the bits according to the
-- bool list
mutate :: Genome -> [Bool] -> Genome

-- takes two genomes and swap the genes after the given point
crossOver :: (Genome, Genome) -> Int -> Genome

-- takes two genoms and a mutation rate and returns a new genome
reproduce :: (RandomGen g) => (Genome, Genome) -> Double -> Rand g (Genome)

-- takes a list of genomes and their corresponding fitness and creates a new 
-- population by selecting two individuals by roulette wheel selection and 
-- create an offspring until the new population is the same size as the 
-- original
makePopulation :: (RandomGen g) => [(Genome, Fitness)] -> Rand g [Genome]

-- takes a list of genomes and creates the next generation by using makePop
nextGeneration :: (RandomGen g) => [Genome] -> Rand g [Genome]

-- returns a list of random genomes each with a given number of genes. used to 
-- create the initial population
randomGenomes :: (RandomGen g) => Int -> Int -> Rand g [Genome]

-- picks a random element from a list of (a, “score”). elements with a higher 
-- score are more likely to be picked
rouletteSelect :: (RandomGen g) => [(a, Double)] -> Rand g a


I have two concerns about my architecture. The first one is that I have 
several “layers” of randomness: The main function will call makePopulation 
which in turn will call rouletteSelect and reproduce. The latter will then 
call mutate, which also involves randomness. As can be seen above, I have 
rewritten mutate to take a list of booleans so that I can use getRandomRs in 
reproduce instead of having to have yet another layer of

  g <- getSplit
  let genome' = evalRand (mutate genome) g

Handling the random generator explicitly like this feels a bit ugly. Or is 
this okay?

Calling getSplit and then evalRand recursively is what I do in makePopulation, 
to make a new population. I would greatly appreciate comments on how this 
“should” be done. I realise that I could just get a list of random numbers in 
makePopulation and then use this as a source of randomness for the called 
functions, but I fear that this would just lead to inelegant code managing 
(chunks of) this list.

My second stumbling point is how to produce a list of successive generations. 
I made the following test function to try to achieve this:

generations :: (RandomGen g) => [Genome] -> g -> [[Genome]]
generations pop g =
    pop : generations (evalRand (nextGeneration pop) g1) g2
    where (g1,g2) = split g

However, it doesn't feel right at all to do it like this. It also seems that 
the fitness values of all generations except the first one are identical, 
which is a good indication that that approach won't work. :-)

The full program, as it is now, can be found here: 

The problem the algorithm is trying to solve can be found here:

I'm grateful for all comments and suggestions, but mainly the two 
aforementioned points.

Erlend Hamberg
“Everything will be ok in the end. If its not ok, its not the end.”
45C3 E2E7 86CA ADB7 8DAD 51E7 3A1A F085 AD3B CF19
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
Url : http://www.haskell.org/pipermail/beginners/attachments/20100110/fa9f57cb/attachment.bin

More information about the Beginners mailing list