0

与えられたデータセットに対して、ある人が賛成票を投じるか反対票を投じるかを予測するルールを学習する遺伝的アルゴリズムを設計するタスクを与えられたとき、私は遺伝的アルゴリズムについて学んでいます。

私は 2 日間連続で GA と GP について本とインターネットで読んでいます。これで、人口管理、遺伝演算子、フィットネス関数、およびさまざまなタイプのクロスオーバー マスクを使用したクロスオーバーに関する GA の概念をある程度理解できました。しかし、特定のデータセットに対して独自の GA を作成するにはまだほど遠い状態です。どうやって始めればいいのか、何から始めればいいのかわからず、自分がバカだと感じて必死になっています。

したがって、ヒント、ヒント、疑似コードなど、あらゆる種類のヘルプをいただければ幸いです。

指定されたデータ セットは次のとおりです (グループ)。

G1 | G1 | G2 | G3 | G4

A1 | B1 | C1 | なし

A2 | B2 | C2 | D2

A3 | B3 | C3 | D3

A4 | B4 | C4 | D4

A5 | - | - | D5

まあ、データはa、b、cではありません。それらはもっと長いものですが、私はちょっと怠け者なので、そうです:P - は、これ以上属性がないことを意味します。none は属性であることに注意してください。助けてくれてありがとう！

4

2 に答える 2

1

何よりもまず、データ セットを使用して何を解決しようとしているのかを最初に判断する必要があります。通常、遺伝的アルゴリズムを使用して、非決定論的問題 (解決に時間がかかるが、その答えは簡単に検証できる問題) に取り組みます。

最初の質問は、データセットが何を表しているかです。

2 番目の質問: 何を解決しようとしているのか、遺伝的アルゴリズムは問題を解決するための適切な方法ですか?

とにかく、遺伝的アルゴリズムの作成は、次の手順で行われます。

  1. 問題の可変ドメインを固定長の染色体として表し、母集団のサイズN、交差確率p(c)、突然変異確率を選択しますp(m)
  2. 問題領域内の個々の染色体の性能または適合度を測定する適合度関数f(x)を定義します。適応度関数は、生殖時に交配する染色体を選択するための基礎を確立します
  3. サイズ N の染色体の初期集団をランダムに生成します: x1 , x2 , ..., xn
  4. 個々の染色体の適合度を計算します: f(x1)、f(x2)、...、f(xn)
  5. 現在の母集団から交配用の染色体のペアを選択します。親染色体は、適合度に関連する確率で選択されます。適合度の高い染色体は、適合度の低い染色体よりも交配のために選択される可能性が高くなります。
  6. 交叉と突然変異の遺伝的演算子を適用して、子孫染色体のペアを作成します
  7. 作成された子孫染色体を新しい集団に配置します
  8. 新しい染色体集団のサイズが初期集団Nのサイズと等しくなるまで、手順 5 を繰り返します。
  9. 最初の (親) 染色体集団を新しい (子孫) 集団に置き換える
  10. ステップ 4 に進み、終了基準が満たされるまでプロセスを繰り返します。

そのため、染色体の一部を簡単に交換できるソリューションの表記法 (ビット配列や文字列など) を見つける必要があります。次に、交差操作と突然変異操作を特定する必要があります。順序付けられた染色体を扱っている場合、適用されるクロスオーバー戦略によっては、後で染色体を修復する必要がある場合があります。順序付けられた染色体は、順序または遺伝子が重要な染色体です。巡回セールスマンが訪問しなければならない都市を表す 2 つの解について標準的な交叉を実行すると、最終的に、いくつかの都市に 2 回以上訪問し、いくつかの都市にはまったく訪問しないという染色体になる可能性があります。

遺伝的アルゴリズムで各問題をどのように変換するかについては、問題ごとに異なるため、明確な説明はありません。上記の手順は変更されませんが、時期尚早の収束を防ぐために、いくつかの異なるクロスオーバーおよびミューテーション操作を導入する必要がある場合があります。

于 2013-06-01T18:58:25.207 に答える
0

さて、私はデータセットの説明を完全には理解していません。そのため、私の答えは次の仮定に基づいています。属性のセットがあり、n 個の異なる属性があるとします。各属性には、可能な記号 (= 非数値) 値のセットがあり、m(i) 個の異なる可能性があります。各人は同じ属性を持っていますが、一部が欠落しているか、またはなしである可能性があります。

これらの仮定が正しく、属性と可能な値のセットが高すぎない場合は、次のいずれかが機能する可能性があります。

  • これらの 2 つのセットが非常に小さい場合は、n 次元配列を個体/遺伝子型として持つことができます。各次元にはサイズ m(i) があり、この構造の各値は yes/no の答えになります。これは、固定サイズ (ビット) ベクトルの一般化 (= より多くの次元) になります。ランダム/変異/クロスオーバーの作成方法は簡単です。フィットネスは、適切な予測を行う頻度です。

  • それらが大きい場合は、より複雑なものが必要になります。1 つの可能性は、ルールのリストを持つことです。各ルールは、長さ n + yes/no フラグを持つベクトルである可能性があります。ベクトルの各位置には、関連する属性の可能な値があります。また、すべてを受け入れるジョリー ジョーカー属性を設定することもできます。ルールの解釈 (p:person, r:rule) : p1=r1 and p2=r2 and ... pn=rn の場合、結果はルールのフラグです。一致するルールが見つかるまで、ルールを評価する必要があります。デフォルトも必要です。この場合、遺伝的演算子はもう少しトリッキーですが、可変長エンコーディングを検索すると何かが見つかると思います。私は（別の問題のために）同様のエンコーディングを使用しましたが、うまくいきました。

  • より一般的に (しかしより複雑に) するために、内部ノードが and/or/not であり、場合によっては他の論理演算子であるツリーとしてルールを表すことができます。葉は pi=ri のような述語です。これは一種の遺伝的プログラミングです。このソリューションが気に入ったら、グーグルで検索してください。

正直なところ、特に値がシンボリックではなく数値である場合、遺伝的アルゴリズムがこの問題に最適な選択であるかどうかは 100% わかりません。これはパターン マッチングの問題のようであり、それにはもっと優れた解決策があります。数値の場合のニューラルネットワークなど、いくつかの代替手段を探します。

于 2013-05-15T19:15:49.313 に答える