How come one mate function converges to solution a lot faster?

I've dabbled with genetic algorithms twice before, a hello world tutorial and a tsp solver. I tried to replicate the hello world tutorial in haskell, and see how the two compare speed wise. The haskell implementation is considerably slower, but what irks me is that the C version converges a lot faster (around 40 generations) without any mutation. The haskell version has AFAIK a better mate function (leans to the better side of the population) and converges in around 60 generations but only if there is mutation involved. Without mutation it stops at a local maxima very soon.

The haskell version has a better mate function, but requires mutation to even converge; The C version has no mutation and worse mate function but converges faster.

randomSt :: (RandomGen g, Random a) => State g a
randomSt = state random
randomRSt :: (RandomGen g, Random a) => (a, a) -> State g a
randomRSt = state . randomR
wrandomRSt :: (RandomGen g) => Int -> State g Int
wrandomRSt n =
  let s = liftM2 (+) (randomRSt (0.0, 1.0)) (randomRSt (0.0, 1.0)) :: (RandomGen g) => State g Float
      n' = fromIntegral n
  in liftM (flip div 2 . floor . abs . subtract (n' / 2) . (n' *)) s

mateCopy :: (RandomGen g) => StringVector -> State g (StringVector)
mateCopy xs = V.replicateM population (step xs)
  where
    step :: RandomGen g => StringVector -> State g (Vector Char)
    step xs =
      let mom = liftM (xs !) (randomRSt (0,population `div` 2))
          dad = liftM (xs !) (randomRSt (0,population `div` 2))
          split = randomRSt (0, V.length target - 1)
      in do
        m <- mom
        d <- dad
        s <- split
        return (V.take s m V.++ V.drop s d)

mate :: (RandomGen g) => StringVector -> State g (StringVector)
mate xs = V.replicateM population (step xs)
  where
    step :: RandomGen g => StringVector -> State g (Vector Char)
    step xs =
      let mom = liftM (xs !) (wrandomRSt population)
          dad = liftM (xs !) (wrandomRSt population)
          split = randomRSt (0, V.length target - 1)
      in do
        m <- mom
        d <- dad
        s <- split
        return (V.take s m V.++ V.drop s d)

elite = population `div` 10
elitism :: (RandomGen g) => StringVector -> State g StringVector
elitism xs = let
  a = V.take (elite) xs
  children = (V.take (population - elite)) `fmap` mate xs
  in do
    b' <- children >>= mutate
    let xs' = (a V.++ b')
    return xs'


unit_t *mate(unit_t *population)
{
    int i;
    size_t half_population = POPULATION >> 1;
    size_t orig_size = strlen(TARGET);
    int mum, dad, chromosomes;
    char *child;
    char *rest;
    unit_t *children = malloc(sizeof(unit_t) * POPULATION);
    elitism(population, children);
    for(i = ELITE; i < POPULATION; i++)
    {
      开发者_Go百科  mum = rand() % half_population;
        dad = rand() % half_population;
        chromosomes = rand() % orig_size;
        child = malloc(sizeof(char) * (orig_size+1));
        rest = population[dad].text + chromosomes;
        sprintf(child, "%.*s%s", chromosomes, population[mum].text, rest);
        children[i].text = strdup(child);
        children[i].dist = -1;
        if(will_mutate())
            mutate(&children[i], orig_size);
        free(child);
    }
    free_population(population);
    population = children;
    return population;
}

edit: Noticed that the C-version takes the parents from the same half. Edited the mateCopy to reflect this

---

As I pointed out in my comment, your population is converged when it is homogeneous, not when you're happy with the best individual.

Your Haskell version is probably converging too fast. The speed at which your fitness function causes your population to converge is a trade-off between "exploring" and "exploiting". When the population is "exploring", you can think of it as moving rapidly around the fitness landscape looking for hills. "Exploiting" consists of climbing a hill that it's already found.

If your fitness function is strongly selective (which I assume is what you mean by "better"), then it is exploiting at the expense of exploring. The solution you coded in Haskell is probably wiping out its diversity too early - and with no mutation it can't create any more.

---

What do you mean by better/worse mate function?

the haskell version has a better mate function, but requires mutation to even converge

The C version has no mutation and worse mate function but converges faster

The only objective facts people can work with are at the moment that the one version has no mutation and the other version has it.

The language used is irrelevant if we are talking about GAs, it becomes relevant if we are talking about performance and the implementation is comparable (i.e. you're using arrays in both languages or whatever).