どのようにして1つのメイト関数がソリューションに収束するのでしょうか？

Question

私は以前に遺伝的アルゴリズムを2回使いました。こんにちはワールドチュートリアル とtspソルバーです。私はhaskellのhello worldチュートリアルを複製しようとしました。 と2つのスピードを比較する方法を見てください。 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; 
} 

編集：はC-バージョンが同じ半分から両親を取ることに気づきました。これを反映するようにmateCopyを編集しました

Answer 1

私がコメントしたところで指摘したように、あなたの人口は同質であるときに収束します。あなたが最良の個人に満足しているときではなく、収束します。

あなたのHaskellバージョンはおそらく非常に収束しています。フィットネス機能があなたの人口を収束させる速度は、「探索する」と「悪用する」の間のトレードオフです。人口が「探検」しているとき、それを丘を探しているフィットネスの風景の周りを急速に動くと考えることができます。 「搾取する」とは、すでに発見されている丘を登ることです。

あなたのフィットネス機能が強く選択されている場合（私が「より良い」ということを前提としています）、の探索でを利用しています。あなたがHaskellでコード化した解決策はおそらく早すぎるとその多様性を払拭することになります。そして、それ以上変異を作成することはできません。

Answer 2

より良い/悪いメイト関数はどういう意味ですか？

Haskellのバージョンは、より良いチームメイトの機能を持っているが、それでもCバージョンは何の変異と 悪化しメイト機能を持っていない

収束に 突然変異が必要ですが、より高速

だけ客観的な事実を収束します人々は作業することができますが、その時点では、1つのバージョンには変異がなく、もう1つのバージョンにはそれがあります。

私たちがGAについて話している場合、使用する言語は無関係です。パフォーマンスについて言えば実装が似ています（つまり、両方の言語で配列を使用しているなど）。