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
Erlend Hamberg <ehamberg@gmail.com> writes:
g <- getSplit let genome' = evalRand (mutate genome) g
Handling the random generator explicitly like this feels a bit ugly. Or is this okay?
I was working on a very similar problem and I used 'split' of RandomGen all the way down. It behaved well as far as I can tell, and if I recall correctly, 'split' was faster than 'next' for StdGen. So, I'd also appreciate any comment on the elegance issue myself. :-) Though, I didn't quite get why you are explicitly calling 'evalRand' instead of utilizing MonadRandom. Here's an example:
makePopulation :: (RandomGen g) => [(Genome, Fitness)] -> Rand g [Genome] makePopulation chms = do g <- getSplit return $ makePopulation' chms g [] where size = length chms makePopulation' c g' a = if length a == size -- if we have ‘size’ members, we are done then a -- if not, find two new parents and append a child else makePopulation' c g' newPop where parent1 = evalRand (rouletteSelect chms) g' parent2 = evalRand (rouletteSelect chms) g' c1 = evalRand (reproduce (parent1, parent2) mutationRate) g' newPop = c1:a
Here, you're generating both parents using the same random generator, hence, parents are always identical. Here's a variation that works within MonadRandom:
makePopulation :: (RandomGen g) => [(Genome, Fitness)] -> Rand g [Genome] makePopulation chms = makePopulation' [] where size = length chms makePopulation' a = if length a == size -- if we have ‘size’ members, we are done then return a -- if not, find two new parents and append a child else do parent1 <- rouletteSelect chms parent2 <- rouletteSelect chms c1 <- reproduce (parent1, parent2) mutationRate let newPop = c1:a makePopulation' newPop
I didn't check for bugs in the algorithm but now both parents and the offspring are generated independently, and resulting fitness values won't be identical. I think the idea is that you should be able to reduce the number of 'evalRand's in your module to one. -- Gökhan San
On Sunday 10. January 2010 21.58.02 Gökhan San wrote:
Though, I didn't quite get why you are explicitly calling 'evalRand' instead of utilizing MonadRandom.
Because of a misunderstanding on my part. I changed all the code as you suggested and now it's much nicer.
Here, you're generating both parents using the same random generator, hence, parents are always identical.
D'oh. That explains it. Thanks! :) -- 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
Erlend - see below... Erlend Hamberg wrote:
... 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?
If you replace the code above with just mutate genome then it will pass the random number generator 'through' mutate and on completion the RNG in the calling context will be changed to what 'mutate' returned. Since you're not using multiple threads, this should be correct for your application, but it's not quite equivalent to your code, because you're not actually splitting the RNG. If you really need to split it, you could write yourself a helper function like this: splitting :: RandomGen g => Rand g a -> Rand g a splitting code = do g <- getSplit return $ evalRand code g Then say splitting $ mutate genome
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.
Gokhan San answered this better than I was going to. Steve
participants (3)
-
Erlend Hamberg -
gsan＠stillpsycho.net -
Stephen Blackheath [to Haskell-Beginners]