c - 为什么一个配合函数可以更快地收敛到解决方案？

Question

我之前接触过两次遗传算法，一个hello world教程和一个 tsp 求解器。我试图在 haskell 中复制 hello world 教程，看看两者如何比较速度。 haskell 的实现是相当慢，但令我恼火的是 C 版本收敛了很多更快(大约 40 代)，没有任何突变。 haskell 版本有 AFAIK 更好的配合功能(倾向于更好的一面人口)并在大约 60 代内收敛，但前提是有涉及突变。如果没有突变，它很快就会停在局部最大值处。

haskell 版本有更好的 mate 功能，但需要 mutation 才能甚至收敛； C版没有突变，mate功能更差，但是收敛更快。

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++)
    {
        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;
}

编辑:注意到 C 版本的 parent 来自同一半。编辑 mateCopy 以反射(reflect)这一点

Answer 1

正如我在评论中指出的那样，当人口是同质的时候，而不是当你对最好的个体感到满意时，你的人口就会收敛。

您的 Haskell 版本可能收敛得太快了。适应度函数导致种群收敛的速度是“探索”和“利用”之间的权衡。当人口在“探索”时，您可以将其视为在适应性景观周围快速移动以寻找山丘。 “开发”包括攀登它已经找到的一座山。

如果您的适应度函数具有很强的选择性(我假设这就是您所说的“更好”的意思)，那么它就是在以探索为代价进行开发。您在 Haskell 中编写的解决方案可能过早地消除了它的多样性 - 如果没有突变，它就不能再创造了。