Pythonで学ぶ遺伝的アルゴリズム：生物の進化をプログラムで再現する

【Yuki】 Hirokiくん、こんにちは。今日は「遺伝的アルゴリズム（Genetic Algorithm, GA）」についてお話ししようと思います。少し難しそうな名前に聞こえるかもしれませんが、実は私たちの身近な「生物の進化」をヒントにした、とても興味深いアルゴリズムなんです...。

【Hiroki】 Yukiさん、よろしくお願いします！「遺伝的アルゴリズム」って、なんだかSF映画に出てきそうな響きですね。生物の進化をヒントにしているということは、プログラムが勝手に進化していくっていうことですか？

【Yuki】 ふふ、そうですね。大まかに言えばその通りです。ダーウィンの進化論にある「適者生存」という言葉を聞いたことはありませんか？環境に適応した個体が生き残り、次の世代に子孫を残していく...。この仕組みをコンピュータ上の計算に応用して、複雑な問題の「正解に近い答え」を探し出すのが遺伝的アルゴリズムなんです。わたしも、誰かの役に立つために作られた小さなツールが、こうして自然の摂理を取り入れているのを見ると、なんだか少しだけ温かい気持ちになります...。

【Hiroki】 なるほど。具体的にはどんな仕組みで動いているのか、すごく気になります。

【Yuki】 では、まずは遺伝的アルゴリズムで使われる基本的な用語と、その流れについて説明しますね。

遺伝的アルゴリズムの基本用語

【Yuki】 遺伝的アルゴリズムでは、問題を解くための候補を「個体」と呼びます。そして、その個体が持つ情報のことを「染色体」や「遺伝子」と呼ぶんです。

• 遺伝子 (Gene)：個体を構成する最小単位のデータです。例えば「0」か「1」の数値だったり、文字だったりします。
• 染色体 (Chromosome)：遺伝子が集まったものです。これが一つの「解の候補」を表します。
• 個体 (Individual)：染色体を持つ一つの存在です。
• 集団 (Population)：複数の個体が集まったグループのことです。

【Hiroki】 本当に生物学の用語そのものなんですね。この「集団」の中で、進化が起こっていくということでしょうか。

【Yuki】 はい、そうです。遺伝的アルゴリズムは、大きく分けて次の5つのステップを繰り返すことで進化をシミュレーションします。

1. 初期化：ランダムに最初の集団を作ります。
2. 適応度評価：それぞれの個体がどれくらい「優秀か」を計算します。
3. 選択：優秀な個体を優先的に選び、次の世代の親にします。
4. 交叉（こうさ）：親同士の遺伝子を組み合わせて、新しい子を作ります。
5. 突然変異：ごく稀に、遺伝子の一部をランダムに書き換えます。

【Hiroki】 「適応度」というので、どれだけ正解に近いかを判断するんですね。「交叉」や「突然変異」があることで、色々なパターンが試されるわけだ。

【Yuki】 その通りです。特に「突然変異」は大切なんです。これがないと、集団が似たような個体ばかりになってしまって、より良い答えを見つけるための多様性が失われてしまうかもしれませんから...。

適応度関数：進化の指標を決める

【Yuki】 次に、とても重要な「適応度関数」についてお話ししますね。遺伝的アルゴリズムにおいて、何をもって「優秀」とするかを定義するのがこの関数です。

【Hiroki】 例えば、迷路を解くプログラムなら、「ゴールに近いほど適応度が高い」という感じですか？

【Yuki】 ええ、まさにそうです。もし「特定の文字列を当てる」という問題なら、「正解の文字と一致している数」を適応度にすればいいと思います。この適応度関数の作り方次第で、アルゴリズムがどこに向かって進化していくかが決まってしまうんです。設計者の腕の見せ所かもしれませんね。

選択・交叉・突然変異の仕組み

【Yuki】 もう少し詳しく、進化のステップを見ていきましょう。

選択 (Selection) 適応度の高い個体ほど、次の世代に遺伝子を残せる確率が高くなります。代表的な方法には、適応度に比例して選ばれやすくする「ルーレット選択」や、ランダムに選んだ数個の中で一番優秀なものを選ぶ「トーナメント選択」などがあります。

交叉 (Crossover) 2つの親の遺伝子を入れ替えて、新しい個体を作る操作です。例えば、親Aの半分と親Bの半分をくっつける「一点交叉」などがあります。これによって、親たちの良いところを受け継いだ子が生まれることを期待するんです。

突然変異 (Mutation) 一定の低い確率で、遺伝子の値を書き換えます。これによって、親の世代には存在しなかった新しい特徴が生まれ、探索の範囲が広がります。

【Hiroki】 なるほど。良いものを残しつつ、たまに新しいことに挑戦する...。なんだか人間の成長や学習にも似ている気がします。

【Yuki】 そうかもしれませんね。完璧な答えをすぐに見つけるのは難しいけれど、少しずつ改善していくという姿勢は、わたしも大切だと思います...。

Pythonによる実装例：ターゲット文字列の探索

【Yuki】 それでは、実際にPythonコードを書いてみましょう。今回は、ランダムな文字列から始めて、目標とする文字列（ターゲット）に進化させていく簡単なプログラムを作ってみます。

【Hiroki】 面白そうです！実際に動くところを見てみたいです。

【Yuki】 まずは、必要な設定と適応度関数を準備しますね。

import random

# 設定
TARGET = "GENETIC ALGORITHM"  # 目標とする文字列
GENES = " ABCDEFGHIJKLMNOPQRSTUVWXYZ"  # 使用する遺伝子（文字）
POPULATION_SIZE = 100  # 1世代の個体数
MUTATION_RATE = 0.01  # 突然変異率

class Individual:
    def __init__(self, chromosome):
        self.chromosome = chromosome
        self.fitness = self.calculate_fitness()

    def calculate_fitness(self):
        # ターゲット文字列と一致している文字数を適応度とする
        score = 0
        for i in range(len(TARGET)):
            if self.chromosome[i] == TARGET[i]:
                score += 1
        return score

def create_gnome():
    # ランダムな染色体（文字列）を生成
    return [random.choice(GENES) for _ in range(len(TARGET))]

【Hiroki】 Individualクラスで、個体の染色体と適応度を管理しているんですね。

【Yuki】 はい。次に、メインとなる進化のループを書いていきます。少し長くなりますが、先ほど説明したステップを順番に実装しているだけですよ。

def main():
    generation = 1
    population = []

    # 初期集団の生成
    for _ in range(POPULATION_SIZE):
        population.append(Individual(create_gnome()))

    while True:
        # 適応度順にソート（高い方が前）
        population = sorted(population, key=lambda x: x.fitness, reverse=True)

        # ターゲットに到達したら終了
        if population[0].fitness == len(TARGET):
            print(f"第{generation}世代: {''.join(population[0].chromosome)} (適応度: {population[0].fitness})")
            break

        print(f"第{generation}世代: {''.join(population[0].chromosome)} (適応度: {population[0].fitness})")

        new_generation = []

        # エリート保存（上位10%はそのまま次世代へ）
        s = int((10 * POPULATION_SIZE) / 100)
        new_generation.extend(population[:s])

        # 残りの個体を生成
        s = int((90 * POPULATION_SIZE) / 100)
        for _ in range(s):
            parent1 = random.choice(population[:50]) # 上位50個体から親を選択
            parent2 = random.choice(population[:50])
            child_chromosome = mate(parent1, parent2)
            new_generation.append(Individual(child_chromosome))

        population = new_generation
        generation += 1

def mate(parent1, parent2):
    # 交叉と突然変異を行って子を作る
    child_chromosome = []
    for p1, p2 in zip(parent1.chromosome, parent2.chromosome):
        prob = random.random()

        if prob < 0.45:
            child_chromosome.append(p1)
        elif prob < 0.90:
            child_chromosome.append(p2)
        else:
            # 突然変異
            child_chromosome.append(random.choice(GENES))

    return child_chromosome

if __name__ == '__main__':
    main()

【Hiroki】 動かしてみると、最初はめちゃくちゃな文字列だったのが、だんだん「GENETIC ALGORITHM」に近づいていくのがわかります！すごい、本当に進化しているみたいだ。

【Yuki】 そう言ってもらえると嬉しいです。mate関数の中で、親1から引き継ぐか、親2から引き継ぐか、あるいは突然変異させるかをランダムに決めています。これが「交叉」と「突然変異」を同時に行っている部分ですね。

遺伝的アルゴリズムが得意なこと

【Hiroki】 でも、これって普通に1文字ずつ正解と比較して変えていけば、もっと早く正解にたどり着けませんか？

【Yuki】 ふふ、Hirokiくん、鋭いですね。今回の例はとてもシンプルなので、そう感じるかもしれません。でも、遺伝的アルゴリズムの真価は「どうすれば正解になるか全くわからないけれど、良し悪しだけは評価できる」という複雑な問題で発揮されるんです。

【Hiroki】 例えばどんな問題ですか？

【Yuki】 有名なのは「ナップサック問題」や「巡回セールスマン問題」ですね。 - ナップサック問題：容量が決まっているバッグに、価値が最大になるように荷物を詰め込む組み合わせを探す問題。 - 巡回セールスマン問題：複数の都市を一番短い距離ですべて回る順番を探す問題。

これらの問題は、選択肢が膨大すぎて、全ての組み合わせを力ずくで計算（全探索）しようとすると、スパコンを使っても何年もかかってしまうことがあります。そんな時に、遺伝的アルゴリズムを使えば、「完璧な正解」ではないかもしれないけれど、「十分に実用的な良い答え」を短時間で見つけることができるんです。

【Hiroki】 なるほど、「完璧」よりも「現実的な解」を素早く見つけるための手法なんですね。

【Yuki】 はい。工場の生産スケジュールを組んだり、航空機の翼の形を最適化したりといった、実社会の様々な最適化問題でも使われています。少し専門的な分野になりますが、もし興味があれば、より高度なライブラリを調べてみるのもいいかもしれません...。

便利なPythonライブラリ

【Yuki】 自分でイチから実装するのも勉強になりますが、実際に複雑な問題を解くときは、便利なライブラリを使うのが一般的です。

• DEAP - Distributed Evolutionary Algorithms in Python
  • 非常に柔軟性が高く、本格的な研究や開発でよく使われるライブラリです。
• PyGAD - Python Genetic Algorithm
  • 初心者の方でも扱いやすく、機械学習のモデル最適化などにも使えます。

【Hiroki】 ライブラリがあるなら、もっと複雑なことにも挑戦できそうですね。

【Yuki】 ええ。まずは自分で仕組みを理解して、それから便利なツールに頼る。その順番で学んでいくのが、遠回りのようでいて一番の近道だと思います。わたしも、Hirokiくんが新しい技術を学んでいくのを、これからも陰ながら応援していますね。

【Hiroki】 ありがとうございます、Yukiさん！遺伝的アルゴリズムのこと、すごくよくわかりました。次はもっと難しい問題に挑戦してみたいです。

【Yuki】 その意気ですよ。でも、あまり根を詰めすぎないでくださいね。時には休憩も大切です...。お疲れ様でした。

まとめ

【Yuki】 最後に、今回のポイントを振り返っておきましょう。

• 遺伝的アルゴリズム(GA)は、生物の進化（適者生存、交叉、突然変異）を模した最適化手法。
• 適応度関数によって、どの個体が優秀かを評価する。
• 選択・交叉・突然変異のループを繰り返すことで、解を改善していく。
• 全探索が困難な複雑な問題に対して、実用的な解を素早く見つけるのが得意。

【Hiroki】 はい！まずは自分で書いたコードを少し書き換えて、ターゲットの文字列を変えたり、突然変異の確率を変えたりして遊んでみます！

【Yuki】 いいですね。パラメータを少し変えるだけで、進化のスピードが劇的に変わることもあります。ぜひ、色々と試してみてください...。

---

参考文献・リンク - Pythonで始める遺伝的アルゴリズム (Qiita) - Genetic Algorithm - Wikipedia (English) - DEAP公式ドキュメント