1

免責事項

まず第一に、これは宿題なので、なぜそんなに不自然なのかと聞かないでください。（「何か変えたらどうですか？」とよく言われます）すみません… できません。

また、進化的アルゴリズムを使用する必要があります。つまり、親には子供がいて、突然変異/再結合し、新しい世代を形成し、最終的に解決策につながる可能性があります。

/免責事項

n*2長さ n の単語があります。n^2これらすべての単語を含むマトリックスを作成する必要があります。言葉は意味不明かもしれませんが、このマトリックスに収まる必要があります (これはユーザー側の要件です)。

したがってAGE,AGO,BEG,CAB,CAD,DOG、この結果が得られます（少なくとも2つのうち1つ）：

C A B
A G E
D O G

進化的アルゴリズムを使用する必要があります。したがって、自分の情報を染色体にコード化する方法を見つける必要があります。

私が思いついたこと：

各単語は必ず表示され、マトリックス内の開始位置と向き (左右または上下) があります。したがって[Word][Orientation][StartPosition]、開始位置が[0][0]/ [0][1]/ [1][0]etc (左の列と一番上の行) です。ただし、制限があります。向きが開始位置に合っていることを検証する必要があります。

問題:

染色体は可能な解決策でなければなりませんが、これは解決策の一部にすぎません。

私の解決策は、「適合」するようにすべての単語を含む行列でなければならないため、染色体も何らかの方法で行列全体を表す必要があります。しかし、それにはいくつかの問題があります。1 つの方向で 1 つの開始位置から 1 つの単語しか持つことができません (最初の 2 つの単語を除いて、それらは異なる方向で同じ開始位置を共有します)。これが進化的アルゴリズムを試みる有効な方法とは思えません。特に突然変異/組換えなど、どの段階も機能しているとは思えません。

私はそれを完全に間違っていると考えていますか？もしそうなら...なぜですか？そして、大量のデータを持たずに、すべての段階 (生殖、突然変異/組換え、自然選択 ... 適応度を計算して新しい世代を開始できるようにする) を通過できるように、データをコーディングするにはどうすればよいでしょうか?ガベージ データ (単語が 2 回表示される、単語が失われる、開始位置と比較して単語の方向が間違っている) ?

編集

この表現を使用して、他の多くの自然にインスパイアされたアルゴリズムを実装するため、「適切な」データ表現が必要です。後で私を傷つける可能性のあるその場しのぎは何もありません。

正直いい方法が思いつきません。私には多くの制限があるからです (おそらく、これについて考えすぎて、それらを乗り越えることができず、実際には存在しない可能性があります)。バイナリ表現が本当に欲しいのですが、それは不可能に思えます。

4

2 に答える 2

1

Winston Ewert の回答に問題があるようです。長さとフォーマットの理由からこれを別の回答にしていますが、ウィンストンが提案しているのは合理的なアプローチです。

あなたは「文字の配列」と、あなたの両親と子孫が何であるか、クロスオーバーや突然変異などをどのように行うかについて尋ねます。おそらく、その文字の配列ビットに混乱していると思います. 文字の配列と考えないでください。これは単語の配列です。これは重要です。なぜなら、単語の境界をまたがったり、突然変異によって単語内の文字を変更したりしたくないからです。あなたは言葉をシャッフルしたい。そのため、単語を扱う代わりに、少し異なる (ただし同等の) アプローチを取りましょう。

2n 個の単語のそれぞれに 1 から 2n までの番号を付けましょう。解の候補を生成するには、1 から 2n の間の n 個の乱数を (置換なしで) 選択するだけです。ランダムに選択された単語は、マトリックスの行になります。したがって、単語が の場合、AGE,AGO,BEG,CAB,CAD,DOG無作為に 3 つを選び、最終的には、たとえば 2、3、および 5 (の染色体を与える235) またはになりAGO,BEG,CADます。

これにより、次の行列が得られます。

AGO
BEG
CAD

ここで、合計 2n 個の入力単語のうち、行列に出現する単語の数を数えます。この場合、有効な単語を構成する列がないため、3 つだけです。入力に対するあなたの適合度235は 3 です。入力は416機能しますが、適合度は 6 です。

母集団を生成するには、1 から 2n までの 3 つの数値の N 個のランダムなセット (繰り返しなし) を生成するだけです。母集団サイズが 4 の場合、次のようになります。

142
354
624
241

これらにより、次の 4 つの異なる解決策が得られます。

142 = AGE
      CAB
      AGO

354 = BEG
      CAD
      CAB

624 = DOG
      AGO
      CAB

241 = AGO
      CAB
      AGE

クロスオーバーを行うには、子孫の重複番号を回避する方法を設計する必要があります。私は過去に順列用に設計された Cycle Crossover メソッドを、これと同様の状況を処理するように適応させましたが、妥当と思われる任意のメソッドを設計できます。たとえば、単純な均一クロスオーバーを実行してから、重複する値のいずれかを別のものに変更して修正することができます。

ミューテーションとは、ある数値を別の数値に変更したり、エンコーディングで 2 つの数値の位置を入れ替えたりすることです。

GA を使用する必要があると言うので、ここで停止して、そのようなことを試すことができます。いくつかの理由から、非常にうまく機能する可能性は低いです。まず、フィットネス関数には多くの停滞期があります。ほぼすべての考えられる答えが同じように間違っているため、GA が従う勾配はあまりありません。干し草の山探索問題の針です。これをいくらか軽減するために、フィットネス値をスコアリングする方法を変更することができます。たとえばD、あなたの例セットでは で始まる単語は 1 つしかないことがわかっているのでDOG、最初の行の で始まるソリューションは自動的に間違っています。より「もっともらしい」間違った答えを与えるソリューションにポイントを与えることができました。ただし、一般に、これは GA が効率的に解決するのが難しい問題になります。

第 2 に、このような制約充足の問題は、GA をどれだけうまく構築したとしても、特殊な手法を使用するとはるかに効率的に解決できます。これはバックトラッキングで簡単に解決できます。

于 2013-05-16T16:09:51.960 に答える
1

いくつかのオプション:

あなたの表現として文字の行列を持ってください。したがって、例からの最適なソリューションは次のようになります。

CABAGEDOG

次に、フィットネスのために、実際にソリューションに含まれている要求された単語ごとにポイントを与えます.

または、表現を各行に 1 つずつ、3 つの単語で構成します。

   CAB
   AGE
   DOG

あなたのフィットネスは、列で正しい単語に報酬を与えます。突然変異はある単語を別の単語に入れ替えます。

于 2013-05-16T15:12:29.050 に答える