[Haskell-beginners] Randomness woes

[Erlend Hamberg]

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: 
http://hpaste.org/fastcgi/hpaste.fcgi/view?id=15782

The problem the algorithm is trying to solve can be found here:
http://www.ai-junkie.com/ga/intro/gat3.html

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.”
GPG/PGP:  0xAD3BCF19
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