Tournament and Roulette Wheel Selection

There are many selection mechanisms available in GA literature, but the two most common seem to be roulette wheel and tournament selection. Roulette wheel involves (conceptually) creating a pie chart where the fitness value of each individual gives the size of the slice of the pie that that individual is assigned to. To create a new population, we can imagine a little arrow spinning around the middle of the chart, and the part of the chart it lands on is the individual that should be selected. Performing this computation n times for a population of n individuals yields a new population. In Heal, my Haskell Evolutionary Algorithm Library, roulette selection is implemented like this:
roulette :: (Linear p) => p (a, Double) -> EAMonad (p a) e
roulette pop = do
let sumfit = F.sum $ fmap snd pop
ds <- Tr.forM pop $ const (nextDouble sumfit)
return $ fmap (select pop) ds
select v !d | empty v = error $ "No selection, fitness remaining: " ++ show d
| remaining <= 0.00001 = i
| otherwise = select (rest v) remaining where
(i, f) = first v
remaining = d - f
where L is the qualified name of Data.Foldable, Tr is the qualified name of Data.Traversable, and Linear is a type class of finite linear structures (so the user can user whatever structure they like- I'm using the Seq sequence structure from Data.Sequence). EAMonad is basically the Random monad with some extra statefulness. Its second type argument e is the environment of the evolutionary algorithm, but in understanding the code one can safely ignore this.

Tournament selection on the other hand consists of small tournaments. To selection a single individual for the new population, we must selection k (normally k = 2. In fact, some definitions of tournaments selection describe it as having tournaments that are always size 2) and we have them compete against each other. The competition consists of choosing the more fitness individual (if k is greater than 2, chose the most fit) some percentage p (normally p = 75%) of the time, and the less fit otherwise. For k>2 this is slightly more complex, but basically the less fit the smaller chance of selection, and for the most part k=2, p=75%. Interestingly the fitness for tournament selection does not necessarily have to be a real number greater than 0 as with some other selection mechanisms, it just has to be of a type with a total order. In Heal, tournament selection is implemented like this:
tournament :: (Linear p, Ord b) => p (a, b) -> EAMonad (p a) e
tournament pop = do
pop' <- Tr.forM pop $ const $ selectPlayers pop >>= compete
return pop'
selectPlayers p = do
i <- nextInt $ count p
i' <- nextInt $ count p
return $ (index p i, index p i')
compete (a, a') = do
b <- test 0.75
return $ fst $ maxBy snd a a'
maxBy f a a' = if f a > f a' then a else a'
Notice the weaker condition on the second part of the pair, (the first part is the individual, the second the fitness) it is simply an Ord instance. Count gives the size of the linear structure (meaning that the structures should be finite) and index allows you to index into the structure. While roulette wheel is used in the original GEP, tournament selection is more common in GP literature, and apparently in GA literature as well. I personally prefer tournament selection and I've chosen it for RGEP.