未経験から挑む！遺伝的アルゴリズムプログラミング入門：巡回セールスマン問題への挑戦
未経験から挑む！遺伝的アルゴリズムプログラミング入門：巡回セールスマン問題への挑戦
この記事では、未経験から遺伝的アルゴリズム（GA）を用いたプログラミングに挑戦し、巡回セールスマン問題を解決しようとしている方を対象に、具体的な疑問点に寄り添いながら、そのプロセスを分かりやすく解説します。数学やプログラミングの知識がなくても、GAの基礎を理解し、実際にコードを動かすためのヒントを提供します。
巡回セールスマン問題を遺伝的アルゴリズムで解くプログラムを作っていますが、初めての事なので、基礎的な事も分かっていない素人のままなので作成途中で困っています。専門用語もネットの記事を読んで昨日今日でうろ覚えの状態です。
私は数学もほとんど出来ませんしプログラムの授業をまともに受けた事が無いですが、分からない所だけ作り方のフワッとした概要だけでも説明して頂けないでしょうか?
プログラム自体は自分で上手く解釈して作成するつもりです。
とりあえず60個体作って20個体淘汰する方式にしようかなと思います。
今回は12都市を巡回するだけと少ないので、性能が良くないと聞いた順序交叉でも構わないと思っています。
順序交叉で重複を排除しようと思っています。順序交叉と突然変異のやり方はイラストを見て学びました。
最適解に近づけなくても、初めて作る遺伝的アルゴリズムがきちんと動作できればよいと考えています。
12都市を巡回して最後にスタートした都市に戻ってくる距離の総合計は作りました。距離の総合計は配列に入れて保存しています。
次に12都市を巡回して最後にスタートした都市に戻ってくる配列はこんな感じにしました。 5、7、3、1、8、13、7、10、9、11、9、2 同じ所を通らない都市間の距離12個を1個体として60個体分作りました。
距離の総合計を使って適合度の計算も問題無く作れました。
とりあえずルーレット選択でやろうと思っていますが、交配の説明がよく分からない所があるので質問させて下さい。
適合度が優れている(距離の総合計が短い)ほうが交配する親遺伝子として選ばれる確率が高くなる方式にしようと思っています。
ルーレットは自分流で適当に作れそうです。
初期にランダムで60個体作り出したら、40個残して20個淘汰したいです。
親同士を交配させて子を作った後親遺伝子はそのまま次世代に残すのでしょうか?
後、適合度の優れた同じ親が何度もルーレットで選ばれてしまったらどうするのでしょうか? 一度交配に使った親は二度以上選ばれないように消去するのでしょうか?
遺伝的アルゴリズム（GA）の基礎：巡回セールスマン問題への適用
まず、遺伝的アルゴリズム（GA）と巡回セールスマン問題の関係について簡単に説明しましょう。GAは、生物の進化の過程を模倣したアルゴリズムで、最適解を探索する手法です。巡回セールスマン問題は、複数の都市を巡回し、すべての都市を一度ずつ訪れて出発点に戻る最短経路を見つける問題です。GAは、この問題に対して、個体群（都市の巡回経路）を生成し、評価（総移動距離）を行い、淘汰と選択、交叉（交配）、突然変異を繰り返すことで、より良い解（短い経路）を見つけ出します。
ステップ1：初期個体の生成
最初のステップは、初期個体群を生成することです。これは、ランダムに都市の巡回経路を作成することに相当します。質問者様は、12都市を巡回する経路を表現するために、都市番号の配列を使用しているようです。これは非常に良いアプローチです。60個体を作成するという計画も、GAの多様性を確保する上で重要です。
- ランダムな経路生成: 都市の順番をランダムに並べ替えることで、初期個体群を生成します。例えば、[5, 7, 3, 1, 8, 13, 7, 10, 9, 11, 9, 2]のような配列が、ある個体の巡回経路を表します。
- 重複の排除: 各都市を一度だけ訪れるように、巡回経路を生成することが重要です。都市の重複がないことを確認してください。
- 距離計算: 各個体の巡回経路について、都市間の距離を計算し、総移動距離を求めます。この総移動距離が、各個体の評価値となります。
ステップ2：適合度の計算
次に、各個体の適合度を計算します。適合度とは、その個体がどれだけ「良い」解であるかを示す指標です。巡回セールスマン問題の場合、総移動距離が短いほど、適合度が高くなります。質問者様は、距離の総合計を使って適合度を計算しているとのことですので、この点は問題ありません。適合度の計算方法としては、以下のような方法があります。
- 単純な反転: 総移動距離の逆数を適合度とします。距離が短いほど、適合度は大きくなります。
- ランキング: 個体群を総移動距離の短い順に並べ、順位に応じて適合度を割り当てます。
- スケーリング: 適合度の範囲を調整し、個体間の差を強調したり、平滑化したりします。
ステップ3：選択（ルーレット選択）
ルーレット選択は、適合度に基づいて個体を選択する方法です。適合度が高い個体ほど、選択される確率が高くなります。質問者様が「ルーレットは自分流で適当に作れそう」とおっしゃっているように、ルーレット選択の実装は比較的簡単です。以下に、ルーレット選択の基本的な手順を示します。
- 適合度の合計: すべての個体の適合度の合計を計算します。
- 選択確率の計算: 各個体の適合度を、適合度の合計で割って、選択確率を計算します。
- 累積確率の計算: 各個体の選択確率を累積して、累積確率を計算します。
- ルーレットの回転: 0から1までの乱数を生成し、その乱数が累積確率のどの範囲に含まれるかを調べます。含まれる範囲の個体が、選択されます。
質問者様が「適合度の優れた同じ親が何度もルーレットで選ばれてしまったらどうするのでしょうか? 一度交配に使った親は二度以上選ばれないように消去するのでしょうか?」という疑問を持たれています。この点について、いくつかのアプローチがあります。
- エリート戦略: 最も適合度の高い個体を、次世代に無条件に引き継ぐ方法です。これにより、最適解への収束を早めることができます。
- 重複の許可: 同じ親が複数回選択されることを許可します。これにより、遺伝的多様性が失われる可能性がありますが、探索の効率を高めることができます。
- 選択後の調整: 選択された親を、何らかの方法で調整します。例えば、選択された親の適合度を少し下げることで、同じ親が何度も選択されることを防ぐことができます。
どの方法を選択するかは、問題の性質や、GAのパラメータによって異なります。最初は、重複を許可し、エリート戦略を組み合わせるのが良いかもしれません。これにより、最適解への収束をある程度確保しつつ、遺伝的多様性を維持することができます。
ステップ4：交叉（交配）
交叉は、選択された親から新しい個体（子）を生成する過程です。質問者様は、順序交叉について学習されているようです。順序交叉は、巡回セールスマン問題に適した交叉方法の一つです。以下に、順序交叉の手順を説明します。
- 親の選択: 2つの親を選択します。
- 交叉点の選択: ランダムに2つの交叉点を選択します。
- 中間部分のコピー: 一方の親の、選択された2つの交叉点の間にある都市を、子の同じ位置にコピーします。
- 残りの都市の追加: もう一方の親の、中間部分に含まれていない都市を、子の残りの位置に、元の順序で追加します。
- 重複の排除: 必要に応じて、子の重複を取り除きます。
例えば、親1が[5, 7, 3, 1, 8, 13, 7, 10, 9, 11, 9, 2]、親2が[2, 9, 11, 1, 5, 8, 3, 7, 13, 10, 6, 4]で、交叉点が3と8の場合、子の生成は以下のようになります。
- 中間部分のコピー: 子は[_, _, _, 1, 8, 13, 7, 10, _, _, _, _]となります。
- 残りの都市の追加: 親2の残りの都市を、元の順序で追加すると、子は[2, 9, 11, 1, 8, 13, 7, 10, 5, 3, 6, 4]となります。
この例では、重複はありません。もし重複が発生した場合は、何らかの方法で重複を排除する必要があります。例えば、重複している都市を削除し、欠けている都市をランダムに挿入する方法があります。
ステップ5：突然変異
突然変異は、個体の遺伝子をランダムに変更する過程です。突然変異は、GAの多様性を維持し、局所最適解からの脱出を助ける役割を果たします。突然変異の頻度（突然変異率）は、GAの性能に大きな影響を与えます。突然変異率が高すぎると、GAはランダム探索に近づき、低すぎると、局所最適解に陥りやすくなります。
巡回セールスマン問題の場合、突然変異の方法としては、以下のようなものが考えられます。
- 2点交換: ランダムに2つの都市を選択し、その都市の順序を入れ替えます。
- シフト: ランダムに都市を選択し、その都市を他の位置に移動させます。
- 反転: ランダムに2つの都市を選択し、その間の都市の順序を反転させます。
質問者様がイラストで学ばれたように、突然変異は、GAの理解を深める上で非常に重要です。
ステップ6：次世代の生成と淘汰
交叉と突然変異によって新しい個体が生成されたら、次世代を生成し、古い世代の個体を淘汰します。質問者様は、60個体から20個体を淘汰する計画を立てています。これは、適切な淘汰率です。淘汰の方法としては、以下のようなものが考えられます。
- 適合度の低い個体の淘汰: 適合度の低い個体から順に淘汰します。
- ランダムな淘汰: ランダムに個体を淘汰します。
- 世代交代モデル: 一部の親を次世代に残し、残りの個体を新しい個体で置き換えます。
質問者様が「親同士を交配させて子を作った後親遺伝子はそのまま次世代に残すのでしょうか?」という疑問を持たれています。これは、世代交代モデルの一種である「エリート戦略」に関連しています。エリート戦略では、最も適合度の高い個体を次世代に残すため、親遺伝子がそのまま次世代に残ることがあります。これにより、最適解への収束を早めることができます。
ステップ7：繰り返しと終了条件
上記のステップを繰り返し行い、世代を重ねるごとに、個体の適合度が向上していきます。GAの終了条件としては、以下のようなものが考えられます。
- 最大世代数: あらかじめ設定した世代数に達したら終了します。
- 適合度の変化: 最良の個体の適合度が一定期間変化しなくなったら終了します。
- 目標適合度: あらかじめ設定した目標適合度に達したら終了します。
これらの終了条件を満たしたら、GAは終了し、最良の個体が最適解として出力されます。
実装のヒントと注意点
GAの実装において、いくつか注意すべき点があります。
- パラメータの調整: GAの性能は、パラメータ（個体数、淘汰率、交叉率、突然変異率など）に大きく依存します。これらのパラメータを適切に調整することが重要です。
- 計算時間の考慮: 巡回セールスマン問題の規模が大きくなると、計算時間も長くなります。計算時間を短縮するために、様々な工夫が必要になる場合があります。
- デバッグ: GAの実装は複雑になりがちです。デバッグを行い、問題が発生した場合は、原因を特定し、修正する必要があります。
まとめ
未経験から遺伝的アルゴリズム（GA）を用いたプログラミングに挑戦し、巡回セールスマン問題を解決することは、非常にやりがいのある挑戦です。この記事では、GAの基本的な概念と、巡回セールスマン問題への適用方法について解説しました。質問者様が抱える疑問点に寄り添いながら、具体的なステップと実装のヒントを提供しました。GAは、様々な問題に応用できる強力な手法です。この記事が、質問者様のプログラミング学習の一助となれば幸いです。頑張ってください！
もっとパーソナルなアドバイスが必要なあなたへ
この記事では一般的な解決策を提示しましたが、あなたの悩みは唯一無二です。
AIキャリアパートナー「あかりちゃん」が、LINEであなたの悩みをリアルタイムに聞き、具体的な求人探しまでサポートします。
無理な勧誘は一切ありません。まずは話を聞いてもらうだけでも、心が軽くなるはずです。