遺伝的アルゴリズム - 私は過去の試験紙を通過していると私は、次の質問を理解しようとしているセールスマン

Question

旅行：

を使用すると、N個の都市を持っていると仮定します。各都市から他の都市に行くことができます。都市間の距離についての完全な情報が表形式であるとします。都市番号kと都市番号lとの間の距離は、d（k、l）で与えられる。例えば、 第3都市から第9都市への距離は、d（3,9）によって与えられる。 d（k、l）= d（l、k）であることに留意されたい。

旅行のセールスマンは、すべてのN都市を訪れる必要があり、すべての都市を結ぶ最短ルートを探したいとします。この問題を解決するには、遺伝的アルゴリズムを使用します。

質問：この問題の適切なフィットネス機能を定義して、 とし、高いか低い適応度が良いかどうかを言う。

誰でも私がこの質問のために必要なことを知っていますか？私はどこから始めるべきか、何か方向性が必要なのか本当に苦労しています。

Answer 1

TSPを使用すると、移動距離を最小限に抑えます。さまざまな都市の方法があります。nN!/2が正確です。

N = 4がある場合、それぞれが1回だけ出現する整数の配列1-4が必要です。だから、いくつかの可能なオプションは次のようになります。

[1,4,2,3] 
[4,1,2,3] 
[3,1,4,2] 

あなたはその後、距離を計算し、リスト内の都市iからi+1に行くことによってスコアを評価します。リストの中のすべての都市i（これは最後です）でこれを行い、総距離があります。これはあなたのスコアです！スコアは上記の例のためにそう

は次のようになります。

// Please note that the integers 1-4 represent cities 
score([1,4,2,3]) = d(1,4) + d(4,2) + d(2,3) 
score([4,1,2,3]) = d(4,1) + d(1,2) + d(2,3) 
score([3,1,4,2]) = d(3,1) + d(1,4) + d(4,2) 

あなたはスコアを最小限に抑えるため、距離を最小限にしたいです。

---

あなたは、たとえばリスト内の2都市を交換突然変異関数を作成することによってこれを行うことができます：

[1,4,2,3] -> [4,1,2,3] 
[1,2,3,4] -> [1,3,2,4] 

This videoは、遺伝的アルゴリズムによって距離を最適化するのJavaScript実装の優れた例を示しています。