ナップザック問題は例えば、遠足にお菓子を持って行く場合カバンに10kgまでしか入らないとした時、どのような組み合わせでお菓子を選択することがいいかを探求する問題です。
様々な解き方があるようですが、遺伝的アルゴリズムで解く練習問題として一般的なようです。
様々な条件を遺伝子として持っている個体を評価し、
評価値が高い個体は生き残り、評価値が低い個体は淘汰されていきます。
生き残った評価値の高い個体を交配させ、交叉や突然変異などを行い遺伝子を適応させていくやり方です。
pythonには遺伝的アルゴリズムのモジュールとしてDeapやPyePyevolve等があるようですが、今回はモジュールは使わずにやることにしました。
今回、お菓子を30種類用意し、遺伝子を30の要素を持つ配列にしました。
お菓子に0番から29番までの番号をつけ、遺伝子もそれに対応する０から29の番号をつける。
n番目の遺伝子が0の場合n番のお菓子をカバンに入れず、1の場合はカバンに持って行くこととしました。
お菓子には重さの要素と値段お要素を持たせ、
評価はカバンに入れたお菓子のトータルの値段としました。
また、カバンの最大容量を決め、重さが最大容量を超える場合は評価を0にしました。
# -+- coding: utf-8 -*-
import random #ランダムモジュール
import math
import copy
import numpy as np
def nimotu_init():
nimotu_list = np.array([(2,21),(10,22),(7,28),(2,21),(4,12),(9,24)])##,(10,15),(7,2),(8,25),(5,28),(3,4),(10,22),
## (9,36),(8,2),(8,7),(5,40),(7,14),(3,40),(9,33),(7,21),(2,28),(10,22),(7,14),(9,36),(7,28),
## (2,21),(10,18),(4,12),(9,24),(10,15)])
omosa = nimotu_list[:,0]
nedan = nimotu_list[:,1]
return [omosa,nedan]
##評価関数
def eval_func(gean):
omosa,nedan = nimotu_init()
## gean = [0,0,1,0,1,1,1,0,1,1]
vallue = sum(nedan * gean)
weight = sum(omosa * gean)
weightmax = 50
if weight< weightmax:
return vallue
else:
vallue = 0
return vallue
def geneticoptimize(maxiter = 1,maximize = True,popsize = 5,popnum = 6,elite = 0.2,mutprob =0.2):
"""
maxiter = 1, 繰り返し数
maximize = True, スコアを最大化
popsize = 50, 個体数
popnum = 10, 遺伝子数（長さ）
elite = 0.2, 生き残る遺伝子の割合
mutprob =0.2 突然変異のおこる確立
"""
# 突然変異
def mutate(vec):
i = random.SystemRandom().randint(0,popnum-1)
if vec[i] == 0:
return vec[:i] + [1]+vec[i+1:]
else:
return vec[:i] + [0]+vec[i+1:]
# 1点交叉 非推奨
def one_point_crossover(r1,r2):
i = random.SystemRandom().randint(1,popnum-2)
return random.SystemRandom().choice((r1[0:i] + r2[i:], r2[0:i] + r1[i:]))
# 2点交叉
def two_point_crossover(r1,r2):
i, j = sorted(random.SystemRandom().sample(range(popnum),2))
return random.SystemRandom().choice((r1[0:i] + r2[i:j] + r1[j:] , r2[0:i] + r1[i:j] + r2[j:]))
# 一様交叉
def uniform_crossover(r1, r2):
q1 = copy.copy(r1)
q2 = copy.copy(r2)
for i in range(len(r1)):
if random.SystemRandom().random() < 0.5:
q1[i], q2[i] = q2[i], q1[i]
return random.SystemRandom().choice([q1,q2])
#遺伝子の初期化
pop = []
for i in range(popsize):
vec = [random.SystemRandom().randint(0,1) for i in range(popnum)]
print vec
pop.append(vec)
#遺伝子の初期化
# 交叉アルゴリズムの選択
#crossover = two_point_crossover
crossover = uniform_crossover
#メインループ
topelite = int(elite * popsize)
for i in range(maxiter):
scores=[(eval_func(v),v) for v in pop]
scores.sort()
if maximize:
scores.reverse()
ranked = [v for (s,v) in scores]
# 弱い遺伝子は淘汰される
pop = ranked[0:topelite]
# 生き残った遺伝子同士で交叉したり突然変異したり
while len(pop) < popsize:
if random.SystemRandom().random() < mutprob:
# 突然変異
c = random.SystemRandom().randint(0,topelite)
pop.append(mutate(ranked[c]))
else:
# 交叉
c1 = random.SystemRandom().randint(0,topelite)
c2 = random.SystemRandom().randint(0,topelite)
pop.append(crossover(ranked[c1],ranked[c2]))
## # 暫定の値を出力
#print(scores[0][0])
print(scores[0])
return scores[0]
def main():
omosa,nedan = nimotu_init()
ans = geneticoptimize()
print("Ans:",ans)
if __name__ == '__main__':
main()
コード自体は評価、淘汰、交配を繰り返すだけでのでそんなに難しく無いと思います。
僕は最初の遺伝子を初期化するところや、評価関数を作るところが結構面倒でした。
結構参考にしたホームページまんまなのですが、最初なので猿真似でいいかなと。
参考
Pythonで遺伝的アルゴリズム
http://xaro.hatenablog.jp/entry/2013/12/28/011236
最適化アルゴリズム
http://sonoshou.hatenablog.jp/entry/20120927/1348757450
遺伝的アルゴリズムで遊ぶ1 http://moraprogramming.hateblo.jp/entry/2013/09/28/214613
遺伝的アルゴリズム的な...?
http://telracsmoratori.blog.fc2.com/blog-entry-129.html
人工生命特論－実習
http://www.sis.nagoya-u.ac.jp/~ari/stuff/al-lecture2.html
0 件のコメント:
コメントを投稿