組み合せ最適化問題を効率的に解くための手法で、生命の進化に似せた手法で解を探索する。解の候補を個体と言い、個体の集合を集団という。これらを以下の順序で処理し、最も目的を達成する解を見付ける。
- 初期の集団の生成する
- 評価
- 終了判定
- 選択
- 交叉、突然変異、コピーによる次世代の生成
ナップザック問題を解く
ナップザック問題は、品物の合計金額が大きくなるように品物をナップザックに入れる問題だ。品物には値段と重量がある。ナップザックには重量制限があり、中に入れた品物の総重量が、ナップザックの重量制限を越えてはならない。この時の品物の組み合わせが探索する解となる。これを遺伝的アルゴリズムで解いてみる事にする。品物とナップザックの重量制限は以下と決める事にする。
− ナップザックの重量制限 :: 1000g以内
| 品物名 | 値段(円) | 重量(g) |
|---|---|---|
| A | 10 | 3 |
| B | 34 | 41 |
問題を単純にするため、品物はAとBの2つだけを用意した。今回の場合は値段と重量のみを考えれば良いため、ナップザックに入れる順序は、容積は関係ない。単純にどの品物を個数ずつ入れると重量制限以内で値段が高くなるかを探せばいい。
最も目的を達成しているかという値を適応度と言うことにする。今回の適応度は、金額が高ければ高いほど適応度が高くなれば良いため、品物の合計金額を適応度に使うことにする。ただし重量がオーバーしている場合、全く目的を達成できていないため、適応度は0になるようにする。
import copy
import functools
import itertools
import random
# 品物 = (価値, 重量)
A = {"value": 10, "weight": 3}
B = {"value": 34, "weight": 41}
# ナップザックの重量制限
weight_limit = 1000
population = [
{ # 最初の個数ははランダムで生成する
"A": random.randint(0, 30),
"B": random.randint(0, 30),
"fitness": None, # どれだけ目的を達成しているか
} for i in range(10) # 初期集団の個体数は10とする
]
def eval_fitness(elm):
val = elm["A"] * A["value"] + elm["B"] * B["value"]
if val > weight_limit:
return 0
return val
for i in itertools.count():
# 評価する
for elm in population:
elm["fitness"] = eval_fitness(elm)
if i > 10: # 終了判定
break
# 操作: どれかの操作を行う
for elm in population:
action = random.randint(0, 3)
if action == 0: # コピー
new_elm = copy.deepcopy(elm)
population.append(new_elm)
elif action == 1: # 交叉
new_elm = copy.deepcopy(elm)
other_elm = random.choice(population) # 交叉の相手はランダムで選出
target = random.choice(("A", "B")) # 1点交叉
new_elm[target] = other_elm[target]
population.append(new_elm)
elif action == 2: # 突然変異
new_elm = copy.deepcopy(elm)
target = random.choice(("A", "B"))
new_elm[target] = elm[target] + random.randint(-3, 4)
population.append(new_elm)
# 選択: ランキング方式(上位30個体のみ次世代に移行)
ranking = sorted(population, key=lambda x: x["fitness"], reverse=True)
population = ranking[:30]
ranking = sorted(population, key=lambda x: x["fitness"], reverse=True)
print(ranking[0])厳密にはちらほら間違っている所はあると思うけれど、おおざっぱな流れとしては間違っていないと思う。