3

TSP を解決する GA アルゴリズムを構築しました。

Norvig の本 (AIAMA) の練習問題です。彼は、表現などの問題に関するララニャガの見解を読むことを提案しました。そこでいくつかのクロスオーバー演算子とミューテーションを学び、それらのいくつかを試して、どちらが自分に適しているかを確認しました. また、各パスのコストに基づいてフィットネス関数を詳しく説明しました。

アルゴリズムの設計について疑問があるにもかかわらず、これまで AI を扱ったことがなかったので、私のアプローチが GA に有効かどうかはわかりません。

これが私がしたことです：

パスのベクトルを取得しました (初期母集団)

次に、各ループで、コストの順序を上げてこのベクトルを編成し、このベクトルで最適な X パスを取得して、他のパスを削除しました。

次に、XOver と Mutation を (一定の割合で) 適用し、それらをベクターの古い削除済みの値の位置に配置します。

次に、同じことを行います（順序ベクトル - 最良の抽出など）

そして安定するまで続けます。

それは良いアプローチですか？そうでない場合は、北をください。最良のものを選択してそれらを保持しなかった場合 (Xover と突然変異を介してそれらからまったく新しいポップを作成しただけ)、良い結果が得られませんでした。このようにして（最良のものを維持する - いくつかの実験では最良のものだけを維持した）、より良い結果が得られ、結果は常に収束し、非常に高速になります

州の表現 : 州の表現について、私はパス表現を使用することにしました (私はすでに最初からそれを使用していましたが、ララニャガなどをすべて読んだ後、それを使い続けることにしました)、それは次のとおりです: たとえば、5 つの都市と最初の都市を訪れ、次に 2 番目、3 番目の都市を訪れます ... パスの表現は (1, 2, 3, 4, 5) になります

初期人口生成：実際には、私は都市を表すためにランダムポイントを生成しています（これは、本が私に求めたものであり、閉じた正方形でランダムポイントを生成します）-しかし、比較のために、人口を生成し、比較するときにそれに固執します結果 - 特定の母集団に固執しなければ、自分の改善について知ることはあまりないと思います

最適な個人: 最適な個人とは、移動コストが最も低い個人です。(この問題では、別のものをパラメーターとして使用する必要があるかどうかはわかりません

crossover : 私はいくつかの crossover 演算子を試し、自分の結果を本に示されているものと比較し、最終的に Order CrossOvers (Larrañaga et al(1999) ) の 1 つを使用しました:親パスを作成し、残りのパス (そのサブパス内でまだ訪れていない都市) を他の親からコピーします (位置 '0' ではなく、2 番目のカットから開始) - 他の親パスに表示される都市を追加します親。

例: パス (1 2 3 4 5) (3 4 2 1 5) 子 (5 |2 3 4| 1) (5 |4 2 1| 3) <- | の内側の部分 | | 一方の親から来て、もう一方の親からの他の部分

突然変異 : 突然変異には、IVM (Inversion Mutation) アプローチを選択しました。元のパスからサブパスを取得し、ランダムなポイントに挿入 (反転) します。

例: パス (1 2 3 4 5) サブパス (2 3 4 ) および 5 の後にランダムに挿入

生成: ( 1 5 | 4 3 2 )

4

1 に答える 1

1

まず、これらすべての略語（GA、TSP、XOver）を避けてください。読みづらく、何を話しているのかわからない人もいるかもしれません。遺伝的アルゴリズムの最初の問題は、初期母集団の選択方法、クロスオーバーの実行方法、突然変異の実行方法です。2番目の問題は、説明の素朴な理解がひどいものかもしれないということです。

あなたにとって最適な個人は、すでにより良いコストを持っている人です。最も多様な個人、つまり問題空間のさまざまな部分を探索する可能性が高い個人を採用する方がよいと主張することができます。次の操作をどのように行うか説明してください。

  • 状態表現：念のため
  • 初期の人口生成：本当に重要です。ローカル検索アルゴリズムで一般的であるため、このステップで利用できる資料があるかもしれません。
  • 最適な個人：ここでもっとプレイしてみることをお勧めします。さまざまな戦略を試してください。問題の全体的な解決策ではなく、再現に最適なものを探しています。
  • クロスオーバー：どうやってやるの？
  • 突然変異：突然変異の目標は、問題空間の現在の領域を回避することであり、非常に高いコストで個人を作成できます。次のステップでの現在のアルゴリズムでは、ソート時に彼は捨てられます

また、実行時間とともにソリューションがどのように改善されるかを評価する必要があります。たとえば、n提供する反復ではなく100n、ソリューションはどの程度改善されますか？アルゴリズムが停止したときの最後の世代の個人などは、互いにどの程度類似していますか。

別の質問ですが、固定トポロジまたは可変トポロジのどちらで解決しようとしていますか？

編集：公開されているアルゴリズムを使用しているため、特定の操作に問題があるとは思われません。フィットネスのために、あなたはパスコストに固執しています。あなたは言う

私が最高のものを選択し、それらを保持しなかったとき（Xoverとミューテーションを介してそれらからまったく新しいポップを作成しただけ）、私は良い結果を得ることができませんでした。このように（最高のものを維持する-いくつかの実験では、最高のものだけを維持しました）、より良い結果が得られ、結果は常に収束し、非常に高速になります。

最適な個人とその子供を維持する必要があります。それは自然の邪悪な原則に従います、最高のものだけが複製する権利を持っています。交換しなければならないのは、最も体に合わない個人です。

調整できるパラメーターは3つあります。子を持つ最適な個体の割合（個体の数も除外されます）、突然変異の確率、および実行の数です。

アルゴリズムのパフォーマンスをテストするには、反復ごとに最適なソリューションをサンプリングできます。つまり、反復ごとtに低コストを節約できます。プロットすると、次のようになります。

x=反復; f（x）=コスト

于 2012-02-02T09:32:24.847 に答える