0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@SciencePlayer(SciencePlayer)

遺伝的アルゴリズムの初歩 in python

Last updated at Posted at 2025-12-13

概要

複数の重さの異なる荷物を以下の条件でリュックに最大どれくらいの重さの荷物を入れることができるのか、を遺伝的アルゴリズムで検証する。いわゆるナップザック問題 である。

  1. 荷物の重さがリュックの耐久度[kg]を超えない
  2. リュックには10個の荷物を入れる

ネットでは基本的なアルゴリズムの使用例として多くで紹介されている。

  • 他の方が掲載した記事を引用させていただきます
    • わかりやすい

実装

  • ソースコード
import random

# ===== 設定 =====
# 全品物数
ITEM_MAX = 15
# 個体の遺伝子長（選ぶ品物の数）
GENE_LENGTH = 10
# 全個体数(人口)
POPULATION_SIZE = 100
# 何世代先まで子孫を残すか
GENERATIONS = 100
# リュックサックの耐久力の最大値[kg]
WEIGHT_MAX = 300
# 荷物の重さの最大値[kg]
ITEM_WEIGHT_MAX = 30
# 交配率
CROSS_RATE = 0.95
# 突然変異が発生する確率
MUTA_RATE = 0.05

##### 関数の定義 #####

# ===== (f-1) 初期個体群を生成 =====
def createIndividual():
    # ランダムに品物番号を選ぶ
    # 遺伝子配列に格納するのは品物の番号(配列のindex)であり品物自体の重さではない
    return [random.randint(0, ITEM_MAX - 1) for _ in range(GENE_LENGTH)]

# ===== (f-2) 評価関数 =====
# 配列"individual"の要素番号g番目の数値のインデックスの重さを抽出して足していく
def fitness(individual):
    total = sum(weights[g] for g in individual)
    return total if total <= WEIGHT_MAX else 0

# ===== (f-3) ルーレット選択 =====
def selectPopulation(pop):
    # 各個体の評価点を要素とした配列を生成する
    fits = [fitness(ind) for ind in pop]
    # 配列の合計を計算する
    total_fit = sum(fits)
    # 全個体の評価点が0ならば完全にランダムでk=POPULATION_SIZE個の個体を選ぶ
    if total_fit == 0:
        return random.choices(pop, k=POPULATION_SIZE)
    # 適応度比例選択
    # pop(population)からfit(各個体の評価点)に応じてk=POPULATION_SIZE個の個体を選ぶ
    # 評価点が高いほど選ばれやすい
    # なお選択により1つの個体が2次元配列popにおいて2か所以上に格納されることがある(分身の術)
    return random.choices(pop, weights=fits, k=POPULATION_SIZE)

# ===== (f-4) 一点交叉 =====
# 親2人の遺伝子を掛け合わせて子を生成
def crossover(parent1, parent2):
    if random.random() < CROSS_RATE:
        point = random.randint(1, GENE_LENGTH - 1)
        child1 = parent1[:point] + parent2[point:]
        child2 = parent2[:point] + parent1[point:]
        return child1, child2
    else:
        return parent1[:], parent2[:]

# ===== (f-5) 突然変異 =====
# 個体の遺伝子配列indのどれかの要素を低確率で変異させる
def mutate(ind):
    for i in range(GENE_LENGTH):
        if random.random() < MUTA_RATE:
            ind[i] = random.randint(0, ITEM_MAX - 1)

##### 関数の定義ここまで #####

# (0)
# ITEM_MAX個の品物の重さを乱数で設定する
weights = [random.randint(1, ITEM_WEIGHT_MAX) for _ in range(ITEM_MAX)]
print("weight of items:", weights)

# (1)
# POPULATION_SIZE個の遺伝子配列を格納する配列(2次元配列)を作成する
# (f-1)を呼び出す
population = [createIndividual() for _ in range(POPULATION_SIZE)]

# ===== GA ループ =====
for gen in range(GENERATIONS):
    # (2)
    # 子孫を残す個体を同じ人口だけ選別する
    # 同じ個体(選別された比較的優秀な個体)が分身しているようにはなりうる
    # (f-3)を呼び出す
    selected = selectPopulation(population)
    
    # (3)
    # ランダムにペアを作る
    random.shuffle(selected)
    # 交配
    next_generation = []
    for i in range(0, POPULATION_SIZE - 1, 2):
        # (f-4)を呼び出す
        child1, child2 = crossover(selected[i], selected[i+1])
        next_generation.extend([child1, child2])
    # 奇数の場合は最後の個体をコピー
    if POPULATION_SIZE % 2 == 1:
        next_generation.append(selected[-1][:])
    
    # (4)
    # 突然変異
    # (f-5)を呼び出す
    for ind in next_generation:
        mutate(ind)
    
    # (5)
    # エリート保存（最良個体を次世代にコピー）
    best_ind = max(population, key=fitness)
    next_generation[0] = best_ind[:]
    
    # (6)
    # 世代更新
    population = next_generation
    
    # 10世代ごとに表示
    if gen % 10 == 0:
        best_fit = fitness(best_ind)
        print(f"Generation {gen+1}, best score: {best_fit}, best items: {best_ind}")

# 最終結果を表示
best_ind = max(population, key=fitness)
best_fit = fitness(best_ind)
print(f"Generation {GENERATIONS}, best score: {best_fit}, best items: {best_ind}")

結果

  • 乱数で決定した15個の品の重さ
weight of items: [22, 18, 15, 10, 10, 16, 10, 19, 17, 21, 14, 2, 28, 4, 26]
  • 各世代で最も優秀な個体
    • best itemsのリストは荷物の重さではなく上記の荷物の重さのリストweight of itemsのインデックスである
    • best scoreはもっとも重い荷物の重さである
Generation 1, best score: 209, best items: [0, 10, 9, 9, 2, 0, 12, 8, 9, 12]
Generation 11, best score: 257, best items: [14, 12, 14, 14, 14, 9, 12, 14, 0, 12]
Generation 21, best score: 258, best items: [0, 12, 14, 14, 14, 14, 12, 14, 0, 12]
Generation 31, best score: 260, best items: [12, 12, 0, 14, 14, 14, 12, 14, 0, 12]
Generation 41, best score: 260, best items: [12, 12, 0, 14, 14, 14, 12, 14, 0, 12]
Generation 51, best score: 263, best items: [12, 12, 14, 14, 12, 9, 12, 12, 0, 12]
Generation 61, best score: 263, best items: [12, 12, 14, 14, 12, 9, 12, 12, 0, 12]
Generation 71, best score: 267, best items: [12, 12, 14, 14, 12, 9, 12, 12, 14, 12]
Generation 81, best score: 269, best items: [12, 12, 14, 14, 12, 9, 12, 12, 12, 12]
Generation 91, best score: 274, best items: [12, 12, 14, 14, 12, 12, 14, 12, 12, 12]
Generation 100, best score: 276, best items: [12, 12, 14, 14, 12, 12, 12, 12, 12, 12]
  • このコードは私の中で違和感を感じるところが何か所かある
    • (2)選別(selectPopulation)
      • 100個の個体(遺伝子配列)から一部を選別して100個を2次元配列に格納している。つまり一部の個体は重複して配列に格納されている(分身の術をしている)
        →分身の術をせずに1つの個体につき2次元配列に1つだけ格納する
        例えば、80個を選別(あらかじめ80個の遺伝子配列を格納する2次元配列を用意する)し、その80個(親)から新たに次世代の個体(子)100個作り出すようなコードを書いてみたい
    • (5)エリート保存
      • 新たな世代の100個の個体にインデックス0(2次元配列の最初の行)にエリート個体を代入することで、もともと0番目にあった子の個体が上書きされている。
        →次世代の個体の上書きを防ぐためには、100個の個体であれば、交叉のときにインデックス0から順に新しい個体を入れていき、インデックス99は子を入れずにエリート個体を入れる、つまりエリート用の枠を確保するコードを実装する
    • 一番最初に荷物の重さをランダムに設定するときに重複をOKとしているため重量の同じ品物が複数出てくることがある。重複せずにすべてがユニークな重量になる仕様としたい
      →同じ重さの品物がたくさんあると単調になりそうなため
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?