遺伝的アルゴリズムによるナップサック問題の最適化
以前、 遺伝的アルゴリズムの入門的なOneMax問題を解いた。
今回は、これよりも少し複雑なナップサック問題を解く。
ナップサック問題とは
Wikipedia によると、ナップサック問題とは次のような問題である。
ナップサック問題は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、 「容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）が与えられたとき、 ナップサックの容量 Cを超えない範囲でいくつかの品物をナップサックに詰め、 ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。 同じ種類の品物を1つまでしか入れられない場合（xi ∈ {0, 1}）や、 同じ品物をいくつでも入れてよい場合（xi ∈ 0以上の整数）など、いくつかのバリエーションが存在する。
今回は容量Cは無視する。 いくらでも品物を詰め込めるが、価値を最大化しつつ、容積ではなく重さを最小化する。 また同じ品物をいくつでも入れて良いことにする。
個体生成、評価、エリート選出
品物が価値と重さという２つの変数を持つ。 まずはこれらを20個生成する。
# input for i in xrange(N_ITEMS): self.items[i] = (random.randint(0, 100), random.randint(1, 10)) # value, weight
# output {0: (90, 5), 1: (18, 5), 2: (25, 7), 3: (12, 7), 4: (52, 2), 5: (77, 10), 6: (72, 3), 7: (2, 10), 8: (89, 6), 9: (36, 10), 10: (22, 9), 11: (47, 6), 12: (45, 3), 13: (65, 6), 14: (25, 6), 15: (71, 5), 16: (81, 9), 17: (11, 6), 18: (90, 10), 19: (32, 5)}
20個の品物の中から5つずつランダムに選んだセットを20個用意する。
# input pop = [] for i in range(N_POP): ind = [self.items[k] for k in random.sample(range(N_ITEMS), 5)] pop.append(ind)
# output [(25, 7), (11, 6), (2, 10), (18, 5), (77, 10)] [(22, 9), (65, 6), (77, 10), (89, 6), (81, 9)] [(72, 3), (81, 9), (52, 2), (25, 6), (18, 5)] [(36, 10), (45, 3), (81, 9), (90, 5), (90, 10)] [(25, 6), (81, 9), (36, 10), (89, 6), (77, 10)] [(65, 6), (72, 3), (90, 5), (25, 6), (12, 7)] [(18, 5), (2, 10), (71, 5), (11, 6), (36, 10)] [(77, 10), (12, 7), (25, 6), (47, 6), (71, 5)] [(89, 6), (47, 6), (25, 7), (65, 6), (25, 6)] [(52, 2), (25, 6), (18, 5), (36, 10), (89, 6)] [(71, 5), (65, 6), (36, 10), (25, 6), (32, 5)] [(2, 10), (32, 5), (25, 6), (81, 9), (71, 5)] [(12, 7), (36, 10), (71, 5), (22, 9), (81, 9)] [(36, 10), (18, 5), (12, 7), (90, 10), (72, 3)] [(77, 10), (22, 9), (90, 5), (25, 6), (11, 6)] [(22, 9), (89, 6), (71, 5), (72, 3), (65, 6)] [(77, 10), (32, 5), (52, 2), (89, 6), (45, 3)] [(47, 6), (2, 10), (18, 5), (25, 6), (89, 6)] [(65, 6), (2, 10), (89, 6), (52, 2), (45, 3)] [(36, 10), (11, 6), (2, 10), (89, 6), (65, 6)]
これらの個体として、各々評価を行う。 と言っても、価格と重さを各々足し合わせるだけ。
# input def clac_score(self, indivisual): dic = {} dic['score0'] = 0 # value dic['score1'] = 0 # weight for ind in indivisual: dic['score0'] += ind[0] dic['score1'] += ind[1]
# output {'score0': 133, 'score1': 38, 'param': [(25, 7), (11, 6), (2, 10), (18, 5), (77, 10)]} {'score0': 334, 'score1': 40, 'param': [(22, 9), (65, 6), (77, 10), (89, 6), (81, 9)]} {'score0': 248, 'score1': 25, 'param': [(72, 3), (81, 9), (52, 2), (25, 6), (18, 5)]} {'score0': 342, 'score1': 37, 'param': [(36, 10), (45, 3), (81, 9), (90, 5), (90, 10)]} {'score0': 308, 'score1': 41, 'param': [(25, 6), (81, 9), (36, 10), (89, 6), (77, 10)]} {'score0': 264, 'score1': 27, 'param': [(65, 6), (72, 3), (90, 5), (25, 6), (12, 7)]} {'score0': 138, 'score1': 36, 'param': [(18, 5), (2, 10), (71, 5), (11, 6), (36, 10)]} {'score0': 232, 'score1': 34, 'param': [(77, 10), (12, 7), (25, 6), (47, 6), (71, 5)]} {'score0': 251, 'score1': 31, 'param': [(89, 6), (47, 6), (25, 7), (65, 6), (25, 6)]} {'score0': 220, 'score1': 29, 'param': [(52, 2), (25, 6), (18, 5), (36, 10), (89, 6)]} {'score0': 229, 'score1': 32, 'param': [(71, 5), (65, 6), (36, 10), (25, 6), (32, 5)]} {'score0': 211, 'score1': 35, 'param': [(2, 10), (32, 5), (25, 6), (81, 9), (71, 5)]} {'score0': 222, 'score1': 40, 'param': [(12, 7), (36, 10), (71, 5), (22, 9), (81, 9)]} {'score0': 228, 'score1': 35, 'param': [(36, 10), (18, 5), (12, 7), (90, 10), (72, 3)]} {'score0': 225, 'score1': 36, 'param': [(77, 10), (22, 9), (90, 5), (25, 6), (11, 6)]} {'score0': 319, 'score1': 29, 'param': [(22, 9), (89, 6), (71, 5), (72, 3), (65, 6)]} {'score0': 295, 'score1': 26, 'param': [(77, 10), (32, 5), (52, 2), (89, 6), (45, 3)]} {'score0': 181, 'score1': 33, 'param': [(47, 6), (2, 10), (18, 5), (25, 6), (89, 6)]} {'score0': 253, 'score1': 27, 'param': [(65, 6), (2, 10), (89, 6), (52, 2), (45, 3)]} {'score0': 203, 'score1': 38, 'param': [(36, 10), (11, 6), (2, 10), (89, 6), (65, 6)]}
価格を最大化して、重さを最小化するには、 価格を降順、重さを昇順にソートする。 pure pythonだとソートコードが複雑になりそうだったので、Pandasを利用した。
# input df = pd.DataFrame(fitness) df = df.sort(['score0', 'score1'], ascending=[False, True])
# output param score0 score1 3 [(36, 10), (45, 3), (81, 9), (90, 5), (90, 10)] 342 37 1 [(22, 9), (65, 6), (77, 10), (89, 6), (81, 9)] 334 40 15 [(22, 9), (89, 6), (71, 5), (72, 3), (65, 6)] 319 29 4 [(25, 6), (81, 9), (36, 10), (89, 6), (77, 10)] 308 41 16 [(77, 10), (32, 5), (52, 2), (89, 6), (45, 3)] 295 26 5 [(65, 6), (72, 3), (90, 5), (25, 6), (12, 7)] 264 27 18 [(65, 6), (2, 10), (89, 6), (52, 2), (45, 3)] 253 27 8 [(89, 6), (47, 6), (25, 7), (65, 6), (25, 6)] 251 31 2 [(72, 3), (81, 9), (52, 2), (25, 6), (18, 5)] 248 25 7 [(77, 10), (12, 7), (25, 6), (47, 6), (71, 5)] 232 34 10 [(71, 5), (65, 6), (36, 10), (25, 6), (32, 5)] 229 32 13 [(36, 10), (18, 5), (12, 7), (90, 10), (72, 3)] 228 35 14 [(77, 10), (22, 9), (90, 5), (25, 6), (11, 6)] 225 36 12 [(12, 7), (36, 10), (71, 5), (22, 9), (81, 9)] 222 40 9 [(52, 2), (25, 6), (18, 5), (36, 10), (89, 6)] 220 29 11 [(2, 10), (32, 5), (25, 6), (81, 9), (71, 5)] 211 35 19 [(36, 10), (11, 6), (2, 10), (89, 6), (65, 6)] 203 38 17 [(47, 6), (2, 10), (18, 5), (25, 6), (89, 6)] 181 33 6 [(18, 5), (2, 10), (71, 5), (11, 6), (36, 10)] 138 36 0 [(25, 7), (11, 6), (2, 10), (18, 5), (77, 10)] 133 38
ただし、populationはdict in listで扱いたいので、 DataFrameから再びdict in listに変換している。
# input fitness = df.to_dict('records')
# output {'score0': 342, 'score1': 37, 'param': [(36, 10), (45, 3), (81, 9), (90, 5), (90, 10)]} {'score0': 334, 'score1': 40, 'param': [(22, 9), (65, 6), (77, 10), (89, 6), (81, 9)]} {'score0': 319, 'score1': 29, 'param': [(22, 9), (89, 6), (71, 5), (72, 3), (65, 6)]} {'score0': 308, 'score1': 41, 'param': [(25, 6), (81, 9), (36, 10), (89, 6), (77, 10)]} {'score0': 295, 'score1': 26, 'param': [(77, 10), (32, 5), (52, 2), (89, 6), (45, 3)]} {'score0': 264, 'score1': 27, 'param': [(65, 6), (72, 3), (90, 5), (25, 6), (12, 7)]} {'score0': 253, 'score1': 27, 'param': [(65, 6), (2, 10), (89, 6), (52, 2), (45, 3)]} {'score0': 251, 'score1': 31, 'param': [(89, 6), (47, 6), (25, 7), (65, 6), (25, 6)]} {'score0': 248, 'score1': 25, 'param': [(72, 3), (81, 9), (52, 2), (25, 6), (18, 5)]} {'score0': 232, 'score1': 34, 'param': [(77, 10), (12, 7), (25, 6), (47, 6), (71, 5)]} {'score0': 229, 'score1': 32, 'param': [(71, 5), (65, 6), (36, 10), (25, 6), (32, 5)]} {'score0': 228, 'score1': 35, 'param': [(36, 10), (18, 5), (12, 7), (90, 10), (72, 3)]} {'score0': 225, 'score1': 36, 'param': [(77, 10), (22, 9), (90, 5), (25, 6), (11, 6)]} {'score0': 222, 'score1': 40, 'param': [(12, 7), (36, 10), (71, 5), (22, 9), (81, 9)]} {'score0': 220, 'score1': 29, 'param': [(52, 2), (25, 6), (18, 5), (36, 10), (89, 6)]} {'score0': 211, 'score1': 35, 'param': [(2, 10), (32, 5), (25, 6), (81, 9), (71, 5)]} {'score0': 203, 'score1': 38, 'param': [(36, 10), (11, 6), (2, 10), (89, 6), (65, 6)]} {'score0': 181, 'score1': 33, 'param': [(47, 6), (2, 10), (18, 5), (25, 6), (89, 6)]} {'score0': 138, 'score1': 36, 'param': [(18, 5), (2, 10), (71, 5), (11, 6), (36, 10)]} {'score0': 133, 'score1': 38, 'param': [(25, 7), (11, 6), (2, 10), (18, 5), (77, 10)]}
個体と評価を保存する
ナップサック問題の個体の評価は、各品物の価格と重さを各々足し合わせるだけなので高速だが、 遺伝的アルゴリズムが扱う問題によっては評価に時間がかかることがある。 世代を重ねるごとに各個体は評価が上がり類似した遺伝子になっていく。 そのため、交叉や突然変異により生成された個体と同じ遺伝子を持つ個体が過去に存在することも珍しくない。 今後の遺伝的アルゴリズムの拡張を考えて、過去の個体とその評価を保存し、各個体を評価する前に参照するようにしておく。
保存する形式もdict in listにするが、パラメーターがlistだと一致評価できないので、Stringに変換してから保存。
self.fitness_master = {}
for fit in fitness:
param = fit['param']
self.fitness_master[str(param)] = {k:v for k,v in fit.items() if k!='param'}
個体の評価では、次の３パターンに別れる。
- スコアはないけどパラメーターはある
- スコアもなくてパラメーターもない
- スコアもパラメーターもある
1がまさに今回のパターン。2は新たな個体が生まれたとき。 3は交叉または突然変異の前の評価のとき。 このアルゴリズム特有で無駄な処理だが、個体の評価を参照することで高速処理できる。
fitness = [] for p in pop: if not p.has_key('score0'): # The indivisual made by crossover or mutation existed before if self.fitness_master.has_key(str(p['param'])): p.update(self.fitness_master[str(p['param'])]) # The indivisual is the first else: p.update(self.clac_score(p['param'])) fitness.append(p) else: fitness.append(p)
まとめ
実行結果は、以下の通り。 世代数が少ない、突然変異率が低いなどが原因で、 必ずしも一番価値のある商品だけで構成するとはなっていない。
V W P Generation 0: 323 25 [(25, 1), (82, 3), (89, 6), (45, 10), (82, 5)] Generation 1: 323 25 [(25, 1), (82, 3), (89, 6), (45, 10), (82, 5)] Generation 2: 323 25 [(25, 1), (82, 3), (89, 6), (45, 10), (82, 5)] Generation 3: 365 22 [(89, 6), (65, 2), (65, 2), (82, 5), (64, 7)] Generation 4: 365 22 [(89, 6), (65, 2), (65, 2), (82, 5), (64, 7)] Generation 5: 365 22 [(89, 6), (65, 2), (65, 2), (82, 5), (64, 7)] Generation 6: 365 22 [(89, 6), (65, 2), (65, 2), (82, 5), (64, 7)] Generation 7: 389 26 [(89, 6), (65, 2), (89, 6), (82, 5), (64, 7)] Generation 8: 389 26 [(89, 6), (65, 2), (89, 6), (82, 5), (64, 7)] Generation 9: 389 26 [(89, 6), (65, 2), (89, 6), (82, 5), (64, 7)] Generation 10: 396 27 [(89, 6), (89, 6), (89, 6), (65, 2), (64, 7)] Generation 11: 396 27 [(89, 6), (89, 6), (89, 6), (65, 2), (64, 7)] Generation 12: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)] Generation 13: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)] Generation 14: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)] Generation 15: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)] Generation 16: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)] Generation 17: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)] Generation 18: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)] Generation 19: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)] Generation 20: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)] Generation 21: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)] Generation 22: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)] Generation 23: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)] Generation 24: 420 31 [(89, 6), (89, 6), (89, 6), (89, 6), (64, 7)]
全コードも載せておく。
# coding: utf-8 import random import math import copy import operator import pandas as pd N_ITEMS = 20 N_POP = 20 N_GEN = 25 MUTATE_PROB = 0.1 ELITE_RATE = 0.5 class GA: def __init__(self): self.items = {} self.fitness_master = {} def main(self): pop = [{'param': p} for p in self.get_population()] for g in range(N_GEN): print 'Generation%3s:' % str(g), # Get elites fitness = self.evaluate(pop) elites = fitness[:int(len(pop)*ELITE_RATE)] # Cross and mutate pop = elites[:] while len(pop) < N_POP: if random.random() < MUTATE_PROB: m = random.randint(0, len(elites)-1) child = self.mutate(elites[m]['param']) else: c1 = random.randint(0, len(elites)-1) c2 = random.randint(0, len(elites)-1) child = self.crossover(elites[c1]['param'], elites[c2]['param']) pop.append({'param': child}) # Evaluate indivisual fitness = self.evaluate(pop) pop = fitness[:] print pop[0]['score0'], pop[0]['score1'], pop[0]['param'] def get_population(self): # Make items for i in xrange(N_ITEMS): self.items[i] = (random.randint(0, 100), random.randint(1, 10)) # value, weight # Make population pop = [] for i in range(N_POP): ind = [self.items[k] for k in random.sample(range(N_ITEMS), 5)] pop.append(ind) return pop def clac_score(self, indivisual): dic = {} dic['score0'] = 0 # value dic['score1'] = 0 # weight for ind in indivisual: dic['score0'] += ind[0] dic['score1'] += ind[1] return dic def evaluate(self, pop): fitness = [] for p in pop: if not p.has_key('score0'): # The indivisual made by crossover or mutation existed before if self.fitness_master.has_key(str(p['param'])): p.update(self.fitness_master[str(p['param'])]) # The indivisual is the first else: p.update(self.clac_score(p['param'])) fitness.append(p) else: fitness.append(p) # Save fitness to all genaration dictinary for fit in fitness: param = fit['param'] self.fitness_master[str(param)] = {k:v for k,v in fit.items() if k!='param'} # This generation fitness df = pd.DataFrame(fitness) df = df.sort(['score0', 'score1'], ascending=[False, True]) fitness = df.to_dict('records') return fitness def mutate(self, parent): ind_idx = int(math.floor(random.random()*len(parent))) item_idx = random.choice(range(N_ITEMS)) child = copy.deepcopy(parent) child[ind_idx] = self.items[item_idx] return child def crossover(self, parent1, parent2): length = len(parent1) r1 = int(math.floor(random.random()*length)) r2 = r1 + int(math.floor(random.random()*(length-r1))) child = copy.deepcopy(parent1) child[r1:r2] = parent2[r1:r2] return child if __name__ == "__main__": GA().main()
追記： 第一世代の扱いについて
上記だと、for文の中にevaluate()が無駄に2つ入ってるが、 1つ目は第一世代の評価にしか使わないので、for文の外に出す方が適切。 for文の中では、交叉と突然変異で生まれた世代の評価を行う。
def main(self): print('Generation 1:'), pop = [{'param': p} for p in self.get_population()] fitness = self.evaluate(pop) print(fitness[0]['score0'], fitness[0]['score1'], fitness[0]['param']) for g in range(N_GEN-1): print('Generation %2s:' % str(g+2)), # Get elites elites = fitness[:int(len(pop)*ELITE_RATE)] # Cross and mutate pop = elites[:] while len(pop) < N_POP: if random.random() < MUTATE_PROB: m = random.randint(0, len(elites)-1) child = self.mutate(elites[m]['param']) else: c1 = random.randint(0, len(elites)-1) c2 = random.randint(0, len(elites)-1) child = self.crossover(elites[c1]['param'], elites[c2]['param']) pop.append({'param': child}) # Evaluate indivisual fitness = self.evaluate(pop) print(fitness[0]['score0'], fitness[0]['score1'], fitness[0]['param'])
