遺伝的アルゴリズムPython実装
遺伝的アルゴリズムPython基本原理
遺伝的アルゴリズム（Genetic Algorithm：GA）は、ダーウィンの進化論にインスパイアされた強力な最適化手法です。自然界の生物が環境に適応するため遺伝的変異を通じて進化する過程を数学的にモデル化し、複雑な最適化問題を解決します。
参考）Pythonで入門 遺伝的アルゴリズム #Python3 -…
このアルゴリズムは以下の基本ステップで構成されています。
- 初期個体群の生成：ランダムに解の候補（個体）を複数作成
- 適応度評価：各個体の優劣を評価関数で数値化
- 選択操作：適応度の高い個体を親として選出
- 交叉操作：親個体の遺伝子を組み合わせて子個体を生成
- 突然変異：低確率で個体の一部をランダムに変更
- 世代交代：次世代の個体群を形成し、終了条件まで反復
遺伝的アルゴリズムの最大の特徴は、局所最適解に陥りにくく、大域的最適解を見つける可能性が高いことです。特に解空間が膨大で従来の数値計算手法では解けない組み合わせ最適化問題において威力を発揮します。
参考）遺伝的アルゴリズム（Genetic Algorithm, G…
遺伝的アルゴリズムPythonライブラリ活用
Pythonで遺伝的アルゴリズムを実装する際、複数の専用ライブラリが利用できます。代表的なライブラリとしてDEAP（Distributed Evolutionary Algorithms in Python）があり、柔軟性と高性能を両立しています。
参考）【Python DEAPライブラリの使い方】遺伝的アルゴリズ…
youtube
DEAPは以下の特徴を持ちます。
- 多様な選択・交叉・突然変異アルゴリズムを標準搭載
- 並列処理対応で大規模問題にも適用可能
- 高度なカスタマイズ性と拡張機能
- 充実したドキュメントとコミュニティサポート
PyGADも注目すべきライブラリで、直感的なインターフェースを提供します。初心者でも簡単に遺伝的アルゴリズムを実装でき、パラメータの細かな調整も可能です。
参考）[2106.06158] PyGAD: An Intuiti…
Pyevolveは基本的なPython文法を踏襲しており、遺伝的アルゴリズムだけでなくニューラルネットワークの実装にも対応しています。これらのライブラリを活用することで、効率的かつ高品質な最適化プログラムを短時間で開発できます。
遺伝的アルゴリズムPythonOneMax問題実装
OneMax問題は遺伝的アルゴリズムの学習に最適な基本問題です。この問題はのような0と1からなる数列において、1の数を最大化することを目標とします。
参考）https://dl.acm.org/doi/10.1145/3620665.3640366
以下にPythonでの基本実装例を示します。
import random
# パラメータ設定
POPULATION_SIZE = 100 # 個体数
GENOME_LENGTH = 50 # 遺伝子長
CROSSOVER_RATE = 0.8 # 交叉確率
MUTATION_RATE = 0.02 # 突然変異確率
MAX_GENERATIONS = 100 # 最大世代数
def fitness(individual):
"""適応度関数：1の数をカウント"""
return sum(individual)
def generate_population(size, length):
"""初期個体群をランダム生成"""
return [[random.randint(0, 1) for _ in range(length)] for _ in range(size)]
この実装では、適応度関数は単純に1の個数を数えることで評価値を算出します。初期個体群はランダムに0と1を配置して生成し、交叉・突然変異・選択操作を反復実行することで最適解に近づけていきます。
参考）遺伝的アルゴリズムについてわかりやすく解説！Pythonで実…
実験結果では、最初の世代でmax適応度が0.62程度だったものが、世代を重ねるにつれて徐々に向上し、最終的に1.0（全て1の状態）に到達することが確認されています。
参考）遺伝的アルゴリズムでOneMax問題を解いてみる #Pyth…
遺伝的アルゴリズムPython巡回セールスマン問題応用
巡回セールスマン問題（TSP）は、N個の都市をすべて1回ずつ訪問して出発地に戻る最短経路を求める古典的な組み合わせ最適化問題です。この問題はNP困難であり、都市数の増加に対して計算量が指数的に増加するため、遺伝的アルゴリズムが威力を発揮します。
参考）遺伝的アルゴリズムで巡回セールスマン問題を解いてみる(理論編…
TSPにおける個体表現は都市の訪問順序として定義されます。例えば、都市A,B,C,D,Eを持つ問題では、個体I₁=(1,2,3,4,5)として表現し、これはA→B→C→D→E→Aの経路を意味します。
参考）「pythonで遺伝的アルゴリズム（GA）を実装して巡回セー…
重要な実装ポイントは以下の通りです。
- 順序表現：都市の重複を避けるため、順列として個体を表現
- 順序交叉（OX）：親の部分経路を保持しながら子個体を生成
- 挿入突然変異：ランダムに選んだ都市を別の位置に移動
- 適応度関数：総移動距離の逆数で評価
この手法により、従来の全探索では不可能な大規模TSPでも実用的な時間内で近似最適解を得ることができます。実際の研究では100都市を超える問題でも良好な結果が報告されています。youtube
参考）遺伝的アルゴリズム(GA)とそのライブラリ(vcopt)で巡…
遺伝的アルゴリズムPython最適化パラメータ調整
遺伝的アルゴリズムの性能は、パラメータ設定に大きく依存します。適切なパラメータ調整により、収束速度と解の品質を大幅に改善できます。
参考）最適化アルゴリズムを実装していくぞ（遺伝的アルゴリズム） #…
個体数（Population Size）の設定は最も重要な要素の一つです。個体数が少なすぎると遺伝的多様性が不足し、局所最適解に陥りやすくなります。一方、個体数が多すぎると計算コストが増大し、収束が遅くなります。一般的に問題の複雑さに応じて50～200個程度が推奨されます。
参考）【初心者向け】遺伝的アルゴリズムについてわかりやすく解説
交叉確率は通常0.7～0.9の範囲で設定されます。高すぎると有用な遺伝子が破壊される可能性があり、低すぎると探索が停滞します。突然変異確率は1/遺伝子長を基準とし、0.01～0.1程度に設定するのが一般的です。
選択方法では、トーナメント選択やルーレット選択が広く使用されます。トーナメント選択は実装が簡単で安定した性能を示し、ルーレット選択は適応度に応じた確率的選択を行います。
動的パラメータ調整も注目される手法で、世代の進行に応じて突然変異確率を調整することで、初期の探索と後期の局所改善のバランスを最適化できます。