問題タブ [traveling-salesman]

巡回セールスマン問題に取り組む遺伝的アルゴリズムを構築しています。残念ながら、突然変異してより良い結果を得る前に、1,000 世代以上持続できるピークに達しました。この場合、どの交叉演算子と突然変異演算子が一般的にうまく機能しますか?

私は巡回セールスマン問題全体とスタックオーバーフローに慣れていないので、正しくないことを言ったら教えてください。

イントロ：

複数の国（エリア）内の複数の都市（ノード）が関与するゲームの利益/時間最適化マルチトレードアルゴリズムをコーディングしようとしています。ここで、

• 接続された2つの都市間を移動するのにかかる物理的な時間は常に同じです。
• 都市は直線的に接続されていません（同時にいくつかの都市間でテレポートできます）。
• 一部の国（地域）には、他の国を経由する最短経路を利用できるテレポートルートがあります。
• 旅行者（またはトレーダー）は、小銭入れ、商品の重量、および特定の交易路で取引できる数量に制限があります。交易路は複数の都市にまたがることができます。

質問パラメータ：

メモリ内にデータベース（python：sqlite）がすでに存在し、ソース都市と宛先都市、配列と金額としての中間の最短パス都市、および総資本に対する％リターン（またはいずれの要因も制限されていない場合は、総資本に対して最大の利益をもたらす方法だけです）。

• 特定のプリセット時間（つまり30分）に対して最適な利益を見つけようとしています
• 新しい都市に渡るという行為は実際には同時です
• 通常、都市地図を移動するのに同じ定義された時間（つまり2分）かかります
• 最初の取引または新しい取引を開始する行為は、1つの都市地図を横断するのと同じ時間（つまり2分）かかります
• 私の出発点は実際には有効な取引がない可能性があります（最初/最も近い/最良のものに移動する必要があります）

これまでの疑似ソリューション

最適化

まず、所要時間に制限があり、各ホップにかかる時間（トレードを開始するための-1を含む）がわかっているため、ホップが。以下のすべてのトレードにグラフを制限できることに気付きましたmax_hops=int(max_time/route_time) -1。この制限時間内に収まらない貿易データベースの要素を切り取り、最短経路の長さが。より大きい都市を剪定しますmax_hops。

私は、現在の都市と、現在の都市ではないすべての既存の取引の開始都市との間の最短経路を含む取引データベースに別のエントリを作成し、それらに0％のリターンを与えます。これらをシティホップの数が、未満の場所に制限します。max_hopsまた、現在の都市から開始都市に加えて最短パスホップを取引する都市が超過するかどうかを計算し、max_hopsこの制限を超えた都市を削除します。

次に、そうでない残りの取引を(current_city->starting_city)取得し、ホップが超過しないすべての目的地と開始都市の間で0％のリターンで取引ルートを追加しますmax_hops

次に、取引データベースに開始都市、目的地都市、または最短経路都市配列の一部として含まれていないすべての都市について、最後の整理を行います。

グラフ検索 制限時間内（つまり30分）に実行可能な取引の（はるかに）小さいグラフが残ります。

接続されているすべてのノードが隣接しているため、接続はデフォルトですべて加重1になります。％returnをトレードのホップ数で割ってから、逆数を取り、+ 1を加算します（これは、 100％帰路）。リターンが0％の場合は…2？

その後、最も収益性の高いルートを返す必要があります...

質問：

多くの場合、

1. お金やスペースを残したときに複数のルートを取る機能を追加して、単一の貿易ルートに個別のパスを介してルートを検索し続けるにはどうすればよいですか？市内で複数の価格と数量で販売されている商品の性質上、重複するルートが多数あります。

2. 新しい交易路の開始にペナルティを課すにはどうすればよいですか？

3. この状況でグラフ検索はさらに役立ちますか？

ちなみに、

3. グラフに対してどのような種類の整理/最適化を行う必要がありますか（または行わないでください）？
4. 私の重み付け方法は正しいですか？私はそれが私に不釣り合いな重みを与えるだろうと感じています。パーセンテージリターンの代わりに実際のリターンを使用する必要がありますか？
5. Pythonでコーディングしている場合、 python-graphなどのライブラリは私のニーズに適していますか？それとも、特殊な関数を作成するためのオーバーヘッドを大幅に節約できますか（私が理解しているように、グラフ検索アルゴリズムは計算量が多くなる可能性があります）。
6. A *検索を使用するのが最善ですか？
7. トレードデータベースの最短経路ポイントを事前に計算して最適化を最大化する必要がありますか、それともすべてをグラフ検索に任せる必要がありますか？
8. 私が改善できることは何か気づきましたか？

任意の開始ノードから最短の歩行距離を見つけて、すべてのノードが重みのある無向グラフで訪問されるようにするアルゴリズムまたはアルゴリズムのセットはありますか？ノードが複数回訪問されてもかまわないので、巡回セールスマンではありません。（最初に戻っても問題ありません。すべてのノードを訪問するのに最後に必要なノードである限り、ウォーカーは遠くのノードに到達する可能性があります。）これは最小スパニングツリーではありません。 A-> B-> C-> A-> Dに行くことは、A、B、C、およびDを訪問するための（一意ではない）最短経路である可能性があるためです。私の直感では、これはそうではないと言っています。 NP問題をそれほどトリッキーにする制限がないため、かなりNP問題です。もちろん、私は完全に間違っている可能性があります。

Standard ML で巡回セールスマンの問題を解決できる人はいますか?教えてください。

私はたくさん試しましたが、成功していません。

巡回セールスマン問題 (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 のパフォーマンスが低下する理由について何か考えはありますか? そして、ローカル最大値を見つけたら探索する方法がないため、ローカル最大値に固執する単純なヒルクライムアルゴリズムよりもパフォーマンスがはるかに悪いのはなぜですか?

私はこれについてさまざまなものを読み、関連する原理と概念を理解していますが、直接接続されていない隣接する都市 (染色体内) を含む染色体 (ルートを表す) の適合度を計算する方法の詳細について言及している論文はありません。 (グラフ内の) エッジによって。

たとえば、各遺伝子がグラフ/マップ上の都市のインデックスを表す染色体 1|3|2|8|4|5|6|7 が与えられた場合、その適合度 (つまり、たとえば、都市 2 と 8 の間に直接のエッジ/リンクがない場合。2 と 8 の間のルートを計算し、このルートの距離を合計に追加するために、ある種の貪欲なアルゴリズムに従いますか?

この問題は、GA を TSP に適用する場合によく見られます。やったことがある方、感想を教えてください。ありがとう。

遺伝的アルゴリズムや蟻コロニー最適化などを使用してTSPを解決する方法について、いくつかの記事とサンプルコードを読みました。しかし、見つけたものにはすべて、時間（ウィンドウ）の制約が含まれていませんでした。「私は午前12時前に顧客xにいる必要があります）」そして対称性を仮定しました。

TSPに制約を追加する方法と、それらをコードで表現する方法を説明するサンプルコードまたは記事の方向性を誰かに教えてもらえますか。

ありがとう！

2 つの単語リストの関数に興味があります。これは、それらの間の順序にとらわれない編集距離を返します。

つまり、引数は (たとえばスペースで区切られた) 単語の 2 つのリストになり、戻り値はリスト内の単語の編集 (またはレーベンシュタイン) 距離の最小合計になります。

"cat rat bat"との間の"rat bat cat"距離は 0 になります。 と の間の距離は"cat rat bat"と"fat had bad"の間の距離と"rat bat cat"同じ"had fat bad"になります。

私の直感 (コンピューター サイエンスの授業で育まれていない) では、ブルート フォースを使用する以外に解決策は見つかりません。

最初の行から始めて、列を選択し、既にアクセスした列に再度アクセスすることなく、次の行に移動します。すべての組み合わせを試すまで、これを何度も繰り返します。

私には、これは巡回セールスマンの問題に少し似ているように思えます。そうですか、どうすれば私の特定の問題を解決できますか?

このようなグリッドがあるとしましょう (ランダムに作成):

では、白いボックスの 1 つからランダムに出発する車があるとします。白いボックスのそれぞれを通過する最短経路は何でしょうか? 各ホワイト ボックスには何度でもアクセスできますが、ブラック ボックスを飛び越えることはできません。ブラックボックスは壁のようなものです。簡単に言えば、ホワイト ボックスからホワイト ボックスにのみ移動できます。

斜めにも、どの方向にも移動できます。

2 つのサブ質問:

1. 移動する前に、すべてのブラック ボックスの位置がわかっていると仮定します。
2. ブラック ボックスに隣接するホワイト ボックス内にいる場合にのみ、ブラック ボックスの位置を知っていると仮定します。

巡回セールスマン問題のための2オプトアルゴリズムのコードサンプルを誰かに教えてもらえますか？今のところ、パスを見つけるために最も近い隣人を使用していますが、この方法は完璧にはほど遠いです。いくつかの調査の結果、そのパスを許容レベルに修正する2-optアルゴリズムを見つけました。サンプルアプリをいくつか見つけましたが、ソースコードはありません。