为什么一个配合函数能够更快地收敛到解决方案？

Question

我之前曾两次涉足遗传算法，这是一个 hello world 教程 和一个 tsp 求解器。我尝试在 haskell 中复制 hello world 教程， 看看两者的速度比较如何。 Haskell 的实现是 相当慢，但令我烦恼的是 C 版本收敛了很多 速度更快（大约 40 代），没有任何突变。哈斯克尔版本 AFAIK 有更好的配对功能（倾向于更好的一面） 人口）并在大约 60 代内收敛，但前提是存在 涉及突变。如果没有突变，它很快就会停止在局部最大值。

haskell版本有更好的mate功能，但需要突变 甚至收敛； 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版本的父母来自同一半。编辑 mateCopy 以反映这一点

Answer 1

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

你的 Haskell 版本可能收敛得太快了。你的适应度函数导致群体收敛的速度是“探索”和“利用”之间的权衡。当人群在“探索”时，你可以认为它是在健身景观中快速移动寻找山丘。 “利用”包括攀登已经发现的一座小山。

如果你的适应度函数是强选择性的（我认为这就是你所说的“更好”的意思），那么它就是以牺牲探索为代价的。您在 Haskell 中编写的解决方案可能过早地消除了其多样性 - 并且如果没有突变，它就无法创建更多的多样性。

Answer 2

更好/更差的配合功能是什么意思？

haskell版本有更好的mate功能，但是需要
突变甚至收敛

C版本没有突变，
配合功能较差，但收敛速度更快

人们可以使用的唯一客观事实是，当前一个版本没有突变，而另一个版本有突变。

如果我们谈论的是 GA，那么使用的语言是无关紧要的，如果我们谈论的是性能并且实现具有可比性（即您正在使用两种语言或其他语言中的数组），那么它就变得相关了。