10

巡回セールスマン問題 (TSP) を解決するために遺伝的アルゴリズムを実装しました。ミューテーションのみを使用すると、クロスオーバーを追加する場合よりも優れたソリューションが見つかります。通常のクロスオーバー メソッドが TSP で機能しないことはわかっているので、Ordered Crossover メソッドとPMX Crossoverメソッドの両方を実装しましたが、どちらも悪い結果に悩まされました。

私が使用している他のパラメータは次のとおりです。

変異: シングル スワップ変異または反転サブシーケンス変異 (ここで Tiendil が説明したように) で、変異率は 1% から 25% の間でテストされています。

選択: ルーレット盤の選択

フィットネス関数: 1 / ツアーの距離

母集団のサイズ: 100、200、500 をテストしました。GA も 5 回実行して、さまざまな開始母集団を用意しました。

停止条件：2500世代

同じ 26 ポイントのデータセットを使用すると、突然変異率の高い純粋な突然変異を使用して、通常、約 500 ～ 600 距離の結果が得られます。クロスオーバーを追加すると、結果は通常 800 距離の範囲になります。もう1つの紛らわしいことは、問題を解決するために非常に単純な山登りアルゴリズムも実装したことです.1000回実行すると（GAを5回実行するよりも高速です）、約410〜450の距離で結果が得られます. GAを使用してより良い結果を得るために。

クロスオーバーを追加すると GA のパフォーマンスが低下する理由について何か考えはありますか? そして、ローカル最大値を見つけたら探索する方法がないため、ローカル最大値に固執する単純なヒルクライムアルゴリズムよりもパフォーマンスがはるかに悪いのはなぜですか?

4

5 に答える 5

3

ルーレットホイールの選択では、悪い親をミックスに導入しています。どういうわけか、より良い親を選択するためにホイールに重みを付けたい場合は、これが役立つ場合があります。

あなたの人口の多くは不適格な親かもしれないことを覚えておいてください。親の選択にまったく重みを付けていない場合は、プールをオーバーランする一貫して悪いソリューションを繁殖させる可能性が高くなります。選択に重みを付けて、より適切な親をより頻繁に選択し、突然変異を使用して、ランダム性を追加することにより、類似しすぎたプールを修正します。

于 2010-05-03T14:32:10.533 に答える
3

クロスオーバー演算子が新しい世代にあまりにも多くのランダム性を導入しているように見えるため、悪い解を改善しようとする計算労力が失われています。Hill-Climb アルゴリズムは与えられた解をその近傍の最良のものに改善できますが、遺伝的アルゴリズムはほぼランダムな母集団 (解) に対して限定的な改善しかできないと想像してください。

GA は TSP を解決するための最良のツールではないことも言う価値があります。とにかく、それを実装する方法のいくつかの例のように見えるはずです。例http://www.lalena.com/AI/Tsp/

于 2010-03-13T18:13:32.830 に答える
2

選択プロセスにエリート主義を導入してみてください。エリート主義とは、集団内で最も適応度の高い 2 つの個人が保持され、選択が行われる前に新しい集団にコピーされることを意味します。エリート主義が完了した後、選択は通常どおり続行されます。これを行うと、ルーレット ホイールでどちらの親が選択されても、クロスオーバー中にそれらが何を生成しても、2 つの最良の個体が常に保持されます。これにより、新しい母集団のフィットネスが失われるのを防ぐことができます。これは、その 2 つの最適な解が前の世代よりも悪くなることはあり得ないためです。

于 2010-06-10T16:11:27.000 に答える
1

「革新的な」戦略を考え出すために、遺伝的アルゴリズムは通常、クロスオーバーを使用してさまざまな候補ソリューションの偉業を組み合わせ、検索スペースを非常に迅速に探索し、より高い適応度の新しい戦略を見つけます-人間の知性の内部の仕組みとはまったく異なります（これが、私たちが実際に何かを「発明」することは決してなく、すでに知っているものを単に混同するだけであるという議論の余地がある理由です）。

そうすることで（異なる個体をランダムに組み合わせる）、クロスオーバーは対称性や順序を維持しません。問題が何らかの対称性または染色体内の遺伝子の順序に大きく依存している場合（特定の場合のように）、それは確かに可能性がありますクロスオーバーを採用すると、結果が悪化します。ご存知のように、巡回セールスマンにはクロスオーバーが機能しないことはよく知られています。

クロスオーバー遺伝的アルゴリズムのこの対称性の破れの偉業がなければ、進化の「ニッチ」（対称性の欠如がしばしば必要とされる）を埋めることができないことを強調する価値があります-そしてそれがクロスオーバー（そのすべてのバリアントで）が大多数で本質的に重要である理由ですケースの。

于 2010-05-03T14:24:01.287 に答える
1

クロスオーバーが追加されたときに結果が悪化する理由の 1 つは、本来あるべきことを行っていない可能性があるためです。つまり、2 人の最高の機能を組み合わせることです。交差確率を低くしてみてはいかがでしょうか？ここでは、人口の多様性が問題になる可能性があります。Morrison と De Jong は、彼らの作品Measurement of Population Diversityで、多様性の新しい尺度を提案しています。その尺度を使用すると、人口の多様性が世代間でどのように変化しているかを確認できます。クロスオーバーを使用する場合と使用しない場合の違いを確認してください。

また、OX や PMX の実装に軽微なミスや詳細の欠落がある可能性があります。多分あなたは何かを見落としましたか？ところで、Edge Recombination クロスオーバー オペレーターを試してみませんか? ( Pyevolveには実装があります)。

于 2010-03-17T11:44:27.480 に答える