Day 151-Q3 | 遺伝的アルゴリズム（Genetic Algorithm）

問題

$N$個の品物（重さ$w_i$、価値$v_i$）と容量$C$のナップサック問題を、以下の決定的な遺伝的アルゴリズムで近似的に解く。個体は長さ$N$の0/1ビット列。適応度は重さ合計$\le C$なら価値合計、超えるなら$0$。

個体数は常に4で固定。初期集団$b_1,b_2,b_3,b_4$が与えられ、以下を$G$世代繰り返す。

1世代の手続き

集団4個体を適応度降順でランキング（同点は元のインデックス昇順）。
上位2個体を親1・親2とし、そのまま次世代にも残す（エリート選択）。
固定交叉点$\mathrm{mid}=\lfloor N/2\rfloor$で一点交叉し子1・子2を作る。
世代番号$g$（1始まり）として位置$(g-1)\bmod N$のビットを子1・子2両方で反転。
次世代を[親1,親2,子1,子2]の順で確定。

入力形式

N C G
w_1 ... w_N
v_1 ... v_N
b_1
b_2
b_3
b_4

制約

$2 \le N \le 12$

$1 \le C \le 10^4$

$1 \le G \le 50$

$b_i$ は長さ$N$の0/1文字列

$1 \le w_i,v_i \le 1000$

入出力例

入力例1

出力例1

概念図：3世代の系譜と早期収束

ヒント（段階的開示）

ヒント1（方向性）

交叉・突然変異はどちらも「決まった位置」で機械的に行われる。乱数が無いので、初期集団とパラメータが決まれば全世代の系譜を完全に手計算で追跡できる。

ヒント2（アプローチ）

ランキングは「適応度降順、同点は元インデックス昇順」の2段階キーで安定に決まる。エリート選択で親2個体が残り続けるため、集団の多様性は交叉と固定位置の突然変異だけに依存する。

ヒント3（誘導）

def fitness(bits, w, v, c, n):
    wt = sum(w[i] for i in range(n) if bits[i] == '1')
    val = sum(v[i] for i in range(n) if bits[i] == '1')
    return val if wt <= c else 0

ranked = sorted(range(4), key=lambda i: (-fitness(pop[i], w, v, c, n), i))
p1, p2 = pop[ranked[0]], pop[ranked[1]]
mid = n // 2
c1 = p1[:mid] + p2[mid:]
c2 = p2[:mid] + p1[mid:]
mp = (gen - 1) % n

模範解答 (Python)

import sys

def main():
    data = sys.stdin.read().split()
    ptr = 0
    n = int(data[ptr]); ptr += 1
    c = int(data[ptr]); ptr += 1
    g = int(data[ptr]); ptr += 1
    w = [int(data[ptr + i]) for i in range(n)]; ptr += n
    v = [int(data[ptr + i]) for i in range(n)]; ptr += n
    pop = [data[ptr + i] for i in range(4)]; ptr += 4

    def fitness(bits):
        wt = sum(w[i] for i in range(n) if bits[i] == '1')
        val = sum(v[i] for i in range(n) if bits[i] == '1')
        return val if wt <= c else 0

    mid = n // 2

    def flip(bits, pos):
        bl = list(bits)
        bl[pos] = '1' if bl[pos] == '0' else '0'
        return ''.join(bl)

    for gen in range(1, g + 1):
        ranked = sorted(range(4), key=lambda i: (-fitness(pop[i]), i))
        p1 = pop[ranked[0]]
        p2 = pop[ranked[1]]
        c1 = p1[:mid] + p2[mid:]
        c2 = p2[:mid] + p1[mid:]
        mp = (gen - 1) % n
        c1 = flip(c1, mp)
        c2 = flip(c2, mp)
        pop = [p1, p2, c1, c2]

    for x in pop:
        print(x)
    best_idx = min(range(4), key=lambda i: (-fitness(pop[i]), i))
    print(pop[best_idx], fitness(pop[best_idx]))

main()

Step-by-Step 解説

1初期集団の適応度
$w=[2,3,4,5,9],v=[3,4,5,8,10],C=10$。`11000`(品物0,1:重5,価7)のみ適応度7、他3個体は重さ超過で0。

2世代1
親1=`11000`,親2=`10101`。$\mathrm{mid}=2$。子1(前)`11101`→反転pos0→`01101`。子2(前)`10000`→反転pos0→`00000`。新集団`[11000,10101,01101,00000]`、適応度`[7,0,0,0]`。

3世代2・3で多様性喪失
世代2で`[11000,10101,10101,11000]`(適応度[7,0,0,7])。世代3ではランキング上位2つがどちらも`11000`となり、子はビット2反転で`11100`(価値12)。最終集団`[11000,11000,11100,11100]`。

4最適解との乖離
真の最適解は品物0,1,3(重10,価値15)だが、このGAが見つけた最良は`11100`(価値12)。エリート選択+1ビット変異だけでは早期に均質化し、探索範囲が狭まる。

よくあるミス

ミス	原因	正しい書き方
ランキングの同点判定を無視	`key`に`-fitness`のみ	`(-fitness, index)`の2段階キー
交叉点を毎世代変える	一般的なGA像に引きずられる	本問は$\mathrm{mid}=N//2$に固定
突然変異位置をリセット	$(g-1)\bmod N$の計算誤り	世代は1始まり、位置は$(g-1)\bmod N$
適応度0同士で価値の高さを優先	ペナルティ処理の誤解	重さ超過は問答無用で0。同点は元インデックスのみ
GAが必ず最適解を見つけると思い込む	限界を軽視	早期収束の実例あり。全探索との照合を習慣化する

次のステップ

発展: 突然変異位置を複数ビットにする、エリート数を1に減らすなどで、3世代で価値15に到達できるか試す。
次回予告: アトキンの篩（Sieve of Atkin）

自己評価

完全理解おおむね理解要復習

Day 151-Q3 — 遺伝的アルゴリズム（Genetic Algorithm）

問題