2

私は現在、Cでキーボードレイアウト最適化アルゴリズム（Peter Klauslerによって設計されたものなど）を書いています。ここで説明するように、フィットネスに比例した選択を実装したいと思います（PDFリンク）。

ルーレットの選択では、ルーレットのホイールモデルに基づいて母集団のメンバーを選択します。円グラフを作成します。ここで、円全体に対するメンバーのスライスの面積は、総人口に対するメンバーのフィットネスの比率です。円周上のポイントがランダムに選択されているかどうかを確認できるように、適合度の高い母集団のメンバーは、選択される可能性が高くなります。これにより、自然淘汰が確実に行われます。

問題は、それを効率的に実装する方法がわからないことです。私は2つの方法を考えました。1つは信頼性が低く、もう1つは遅い方法です。

まず、遅いもの：

長さNのキーボードプールの場合、長さNの配列を作成します。配列の各要素には、実際には最小値と最大値の2つの要素が含まれています。各キーボードには対応する最小値と最大値があり、範囲はキーボードの適合性に基づいています。たとえば、キーボード0の適合度が10、キーボード1の適合度が20、キーボード2の適合度が25の場合、次のようになります。コード：

array[0][0] = 0; // minimum
array[0][1] = 9; // maximum
array[1][0] = 10;
array[1][1] = 30;
array[2][0] = 31;
array[2][1] = 55;

（この場合、必要な労力が少ないことを意味するため、適応度は低い方が良いです。）

次に、乱数を生成します。その番号がどの範囲に該当する場合でも、対応するキーボードは「強制終了」され、別のキーボードの子孫に置き換えられます。これを必要な回数繰り返します。

これに伴う問題は、それが非常に遅いことです。完了するにはO（N ^ 2）操作が必要です。

次に速いもの：

まず、キーボードの最低および最高の適合性を把握します。次に、（最低の適合度）と（最高の適合度）の間の乱数を生成し、生成された数よりも高い適合度ですべてのキーボードを強制終了します。これは効率的ですが、キーボードの半分だけを殺すことが保証されているわけではありません。また、「ルーレットホイール」の選択とは多少異なるメカニズムを備えているため、適用できない場合もあります。

だから問題は、効率的な実装とは何ですか？

この本の36ページ（リンク）にはやや効率的なアルゴリズムがありますが、問題は、ルーレットの選択を1回または数回だけ行う場合にのみ効率的であるということです。多くのルーレットの選択を並行して行う効率的な方法はありますか？

4

1 に答える 1

1

一つには、選択を「抹​​殺」したい場合、不適合スコアについて話しているように聞こえます（これは、スコアの高いキーボードである可能性が高いです）。

2 つの配列を維持する必要はないと思います。最も簡単な方法は、スコアの単一の配列を維持し、それを繰り返して選択することだと思います。

/* These will need to be populated at the outset */
int scores[100];
int totalScore;

for (gen = 0; gen < nGenerations; ++gen) {
    /* Perform a selection and update */
    int r = rand() % totalScore;        /* HACK: using % introduces bias */
    int t = 0;
    for (i = 0; i < 100; ++i) {
        t += scores[i];
        if (r < t) {
            /* Bingo! */
            totalScore -= scores[i];
            keyboards[i] = generate_new_keyboard_somehow();
            scores[i] = score_keyboard(keyboards[i]);
            totalScore += scores[i];    /* Now totalScore is correct again */
        }
    }
}

各選択/更新には、n 個のキーボードに対して O(n) 時間がかかります。

于 2009-08-14T06:50:15.450 に答える