ノードのネットワークがある場合、遺伝的アルゴリズムを使用して任意の 2 つのノード間の最短経路を計算するにはどうすればよいですか?
5290 次
1 に答える
3
TSP問題を解決するためにGAを使用してはどうですか？
TSP は NP 完全問題です。つまり、多項式時間で TSP 問題の解を見つけることはできません。ただし、与えられた解が多項式時間の解であるかどうかは検証できます。
遺伝的アルゴリズムなどのメタヒューリスティックな方法は、TSP 問題を解決するためのツールとして調査できます。これは、それらが動作する人口ベースのアプローチのためです。このようにして、アルゴリズムの実行中に膨大な数のソリューションを「処理」できます。GA を使用して問題を解決するには、以下を定義する必要があります。
- フィットネス機能
- 個々の染色体
- クロスオーバーオペレーター
- 突然変異
フィットネス関数: ここでは、フィットネス関数を簡単に定義できます。これは、可能な都市の特定のツアーのためにセールスマンが横断しなければならない距離であるべきです. TSP ではこれを最小限に抑えようとしています。
染色体: 染色体は次のように簡単に定義できます.5つの都市A、B、C、D、Eがあるとします.次に、染色体の各「スロット」が5つの都市のいずれかを含む、長さ5の染色体を想像してください. たとえば、A、C、D、B、E はこの場合有効な染色体です。
クロスオーバー オペレーター: クロスオーバー オペレーターは、GA で 2 つの親を "混合" して、より適切な子を取得するために使用されます。さまざまな交差演算子が GA 文献で利用可能であり、それぞれが同じことを達成するための異なる方法を持っています。たとえば、一点交差を考えてみましょう。クロスオーバー ポイントをランダムに選択し、2 つの間でビットを交換します。他の特殊なクロスオーバー オペレーターには立ち入らずに、適切なクロスオーバー オペレーターが何であるかを見てみましょう。この場合、2 つの親染色体はそれぞれ A、B、C、D、E の順列を持ちます。どの交叉方法を選択する場合でも、ここで 1 つの事実に注意する必要があります。交叉演算子は、1 つの都市が複数回存在する子を作成してはなりません。これは無効な染色体です。そのようなクロスオーバー オペレーターの 1 つが「オーダー クロスオーバー」です。
突然変異: 突然変異は、単一の染色体の 2 つの位置を交換するだけの単純なものです。
全体として、これは GA を使用する TSP がどのように機能するかを示しています。
それぞれのサイズが 5 で、A、B、C、D、E の順列を含む個体の集団を作成します (同じ順列が何度も繰り返されます)。
GA を開始し、すべての実行で、与えられた距離パラメーターを使用して距離を計算することにより、フィットネス関数に基づいて各個人を評価します
クロスオーバー、ミューテーションは個人を改善し、最終的に最良の解決策は、最高のツアーを持つ個人になります。A、B、C、D、E の最適順列。
それが役立つことを願っています!
于 2009-12-16T04:31:18.643 に答える