Почему одна функция сопряжения намного быстрее сходится к решению?

Question

Я уже два раза баловался с генетическими алгоритмами, учебником "Здравствуй, мир!" И решающим tsp.Я попытался скопировать учебник hello world в haskell и посмотреть, как они сравнивают скорость.Реализация на haskell значительно медленнее, но меня раздражает то, что версия C сходится намного быстрее (около 40 поколений) без каких-либо мутаций.Версия на Haskell имеет AFAIK лучшую функцию спаривания (склоняется к лучшей части населения) и сходится примерно через 60 поколений, но только при наличии мутации.Без мутации он очень скоро останавливается на локальных максимумах.

Версия на haskell имеет лучшую функцию сопряжения, но требует, чтобы мутация даже сходилась;Версия C не имеет мутаций и имеет худшую функцию помощника, но сходится быстрее.

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;
}

edit: Заметил, что C-версия берет родителей из той же половины.Отредактировал mateCopy, чтобы отразить это

Answer 1

Как я указывал в своем комментарии, ваше население сходится, когда оно однородно, а не когда вы довольны лучшим человеком.

Ваша версия на Haskell, вероятно, сходится слишком быстро. Скорость, с которой ваша функция пригодности заставляет ваше население сходиться, является компромиссом между «исследованием» и «эксплуатацией». Когда население «исследует», вы можете думать, что оно быстро перемещается по фитнес-ландшафту в поисках холмов. «Эксплуатация» состоит из восхождения на холм, который уже найден.

Если ваша фитнес-функция строго избирательна (что, я полагаю, означает «лучше»), то она использует за счет исследования. Решение, которое вы написали в Haskell, вероятно, слишком рано стирает его разнообразие - и без мутаций оно уже не может создать.

Answer 2

Что вы подразумеваете под лучшей / худшей матовой функцией?

версия haskell имеет лучшую матовую функцию, но требует, чтобы мутация даже сходилась

В версии C нет мутациии, что еще хуже, функция сопряжения, но сходится быстрее

Единственные объективные факты, с которыми могут работать люди, - это то, что в одной версии нет мутации, а в другой -

Языкused не имеет значения, если мы говорим о GA, это становится уместным, если мы говорим о производительности, а реализация сопоставима (т. е. вы используете массивы на обоих языках или как угодно).