4

巡回セールスマン問題（TSP）を最適化するために、遺伝的アルゴリズム（GA）を使用しています。私の問題は、個人の健康状態をどのように計算するかです。明らかに、より短いルートのソリューションの方が適していますが、ソリューションがその範囲のどこに適合するかを判断するために、可能な最短ルートと可能な最長ルートを知らずに、どのように正確に適応度値を割り当てるのですか？

4

3 に答える 3

5

フィットネスがパスの長さに等しいことは問題ありません。遺伝的アルゴリズムでは、適応度は個人の選択にのみ使用されることに注意してください。したがって、通常の選択手順では、スケールは重要ではなく、ランクのみが重要です。

実装例：

その他の微妙な点（2001-群知能-ケネディ＆エバーハート-249ページ）：

Pablo Moscatoは、ミームアルゴリズムの研究を開拓した南米の研究者です（例、Moscato、1989）。彼と現在エジンバラ大学でスコットランドにいるマイケル・ノーマンは、1980年代にカリフォルニア工科大学で一緒に働き始めました。最近の論文では、巡回セールスマン問題（TSP）を最適化するためのミームアルゴリズムの使用について説明しています（Moscato and Norman、1992）。TSPでは、各都市を1回だけ通過する、多数の都市を通る最短経路を見つける必要があることを思い出してください。特に都市の数が多い場合、解決が非常に難しいため、この問題には応用数学の豊富な歴史があります。TSPはNP困難な問題であり、それを解決する方法が見つかった場合、他の多くの問題も解決されていることを示唆しています。

個人の母集団（これらの研究者は通常16の母集団サイズを使用します）は、「ツアー」と呼ばれる都市の順列によって定義される問題空間を検索します。個体群はリングとして概念化されており、各個体は、検索で競合する2つの隣接する隣接個体に接続されています。個人はまた、彼らが協力しているリングの向こう側で他の人とつながっています。人口の各個人は、都市のツアーを構成します。競争は、個人のペア間の「挑戦」と「戦い」と見なされ、個人とその隣人のツアーの長さが比較され、その差に基づいて確率のしきい値が設定されます。ツアーの長さの違いは、形のあるカーブの急勾配に影響します。差が小さいときや温度が低いときは、

協力は、より成功した個人を、人口のあまり適していないメンバーとではなく、互いに「交配」させるために使用されます。競合する相互作用の決定に使用されるのと同じルールが、クロスオーバーに対するパートナーの望ましさを評価するために使用されます。これは、GAの場合と同じように実装されます。ある個人が別の個人に「提案」し、提案が受け入れられた場合、つまり確率的決定が彼らの相互作用を支持する場合、クロスオーバー演算子が実装されます。このようにして、次世代が生まれます。

于 2012-07-31T20:35:16.490 に答える
2

これまでに見た最短経路がフィットネススコア1.0（または10、42、または3.14 ...好きなもの）になるように、すべての候補ソリューションを正規化してから、すべての経路をこれよりも比較的長くスケーリングすることができます。最長のパスと同じです-あなたが観察した最長のパスは、可能な限り最悪のスコアと見なされます。

トリックは、さらに短いパスを見つけたときに行うことです（1.0など、可能な限り高いスコアを割り当てた場合）。次に、正規化関数の上限を上げる必要があります。たとえば、フィットネス2.0（または1.1、またはその他の任意に大きいフィットネススコア）の割り当てを開始します。

于 2012-07-31T20:08:04.337 に答える
0

プログラムが適応度値を最大化している場合は、適応度関数を最大化する必要があります

f=-ツアーの長さ

編集済み：フィットネスをポジティブにするために、フィットネスに任意の数である1000000000000を追加しました。いくつかのコメントを読んだところ、それは必要ないことがわかりました。

プログラムが適応度値を最小化している場合は、適応度関数を最小化する必要があります

f=ツアーの長さ

于 2012-07-31T21:41:38.123 に答える