はじめに
以前作成した遺伝的アルゴリズムをつかって、最適化問題でよくあるナップサック問題を解いてみようと思います。
ナップサック問題とは、wikiによると下記のとおりです。
種類の品物（各々、価値
、重量
）が与えられたとき、重量の合計が
を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題である。
それではさっそくやってみましょう。
ナップサック問題
今回やってみる問題は下記の通りとします。
品物は以下の10種類で、重量が120を超えないように価値を最大化することとします。
| 品物 | 価値 |
重量 |
| バナナ | 100 | 30 |
| リンゴ | 140 | 20 |
| 納豆 | 200 | 15 |
| 飴 | 10 | 10 |
| ブドウ | 180 | 35 |
| ガム | 80 | 18 |
| おにぎり | 220 | 40 |
| チョコ | 400 | 45 |
| 大根 | 50 | 8 |
| ビール | 300 | 30 |
動的計画法で解いてみる
この問題はきっちりと最適解が求められます。
遺伝的アルゴリズムとの対比を行うために、最適化問題の解法としてよく使われる動的計画法で解いてみましょう。
動的計画法では最適化問題を複数の部分問題に分けて最適解を導いていく手法です。
漸化式を立てて順次解いていきます。
この問題だと以下のように漸化式を立てられます。
コードで実装してみます。
import numpy as np # 問題 n = 10 w = np.array([30, 20, 15, 10, 35, 18, 40, 45, 8, 30]) v = np.array([100, 140, 200, 10, 180, 80, 220, 400, 50, 300]) maxw = 120 # DP dp = np.zeros([n + 1, maxw + 1]) for i in range(n): for j in range(maxw + 1): if j < w[i]: dp[i + 1, j] = dp[i, j] else: dp[i + 1, j] = max(dp[i, j], dp[i, j - w[i]] + v[i]) print(dp[-1][-1])
結果は1090でした。
これより1090が最適解であることがわかります。
遺伝的アルゴリズムでの実装
過去の記事にて遺伝的アルゴリズムの基本的なつくり方を説明してますので、今回はそのコードをほとんどそのまま使用します。
個体クラスの変更
変えるのは、個体クラスのみです。
遺伝子は前回同様0,1で表現します。今回は、10個の品物をそれぞれ入れるか入れないかを0,1で表したものとします。
遺伝子に関しては変更はないですが、評価関数の計算の方法のみ変わってます。
class Individual: '''各個体のクラス args: 個体の持つ遺伝子情報(np.array)''' def __init__(self, genom): self.genom = genom self.fitness = 0 # 個体の適応度(set_fitness関数で設定) self.set_fitness() def set_fitness(self): '''個体に対する目的関数(OneMax)の値をself.fitnessに代入''' if np.dot(self.genom, w) > maxw: self.fitness = maxw - np.dot(self.genom, w) else: self.fitness = np.dot(self.genom, v) def get_fitness(self): '''self.fitnessを出力''' return self.fitness def mutate(self): '''遺伝子の突然変異''' tmp = self.genom.copy() i = np.random.randint(0, len(self.genom) - 1) tmp[i] = float(not self.genom[i]) self.genom = tmp self.set_fitness()
遺伝的アルゴリズムの実行
それではさっそく実行してみましょう。
以前書いた関数等は省略してます。
import numpy as np import matplotlib.pyplot as plt class Individual: '''各個体のクラス args: 個体の持つ遺伝子情報(np.array)''' def __init__(self, genom): self.genom = genom self.fitness = 0 # 個体の適応度(set_fitness関数で設定) self.set_fitness() def set_fitness(self): '''個体に対する目的関数(OneMax)の値をself.fitnessに代入''' if np.dot(self.genom, w) > maxw: self.fitness = maxw - np.dot(self.genom, w) else: self.fitness = np.dot(self.genom, v) def get_fitness(self): '''self.fitnessを出力''' return self.fitness def mutate(self): '''遺伝子の突然変異''' tmp = self.genom.copy() i = np.random.randint(0, len(self.genom) - 1) tmp[i] = float(not self.genom[i]) self.genom = tmp self.set_fitness() if __name__ == '__main__': np.random.seed(seed=64) # param POPURATIONS = 100 GENOMS = 10 GENERATIONS = 20 CROSSOVER_PB = 0.8 MUTATION_PB = 0.1 # problem w = np.array([30, 20, 15, 10, 35, 18, 40, 45, 8, 30]) v = np.array([100, 140, 200, 10, 180, 80, 220, 400, 50, 300]) maxw = 120 # create first genetarion generation = create_generation(POPURATIONS, GENOMS) # solve best, worst = ga_solve(generation) # DP dp = np.zeros([n + 1, maxw + 1]) for i in range(n): for j in range(maxw + 1): if j < w[i]: dp[i + 1, j] = dp[i, j] else: dp[i + 1, j] = max(dp[i, j], dp[i, j - w[i]] + v[i]) print(dp[-1][-1]) # plot fig, ax = plt.subplots() ax.plot(best, label='max') ax.plot(worst, label='min') ax.set_xlim([0, GENERATIONS - 1]) ax.legend(loc='best') ax.set_xlabel('Generations') ax.set_ylabel('Fitness') ax.set_title('Tournament Select') plt.show()
結果は以下です。
Generation loop start. Generation: 0: Best fitness: 1030. Worst fitness: -105 Generation: 1: Best fitness: 1040. Worst fitness: -61 Generation: 2: Best fitness: 1040. Worst fitness: -46 Generation: 3: Best fitness: 1040. Worst fitness: -45 Generation: 4: Best fitness: 1050. Worst fitness: -48 Generation: 5: Best fitness: 1050. Worst fitness: -43 Generation: 6: Best fitness: 1090. Worst fitness: -38 Generation: 7: Best fitness: 1090. Worst fitness: -36 Generation: 8: Best fitness: 1090. Worst fitness: -48 Generation: 9: Best fitness: 1090. Worst fitness: -56 Generation: 10: Best fitness: 1090. Worst fitness: -28 Generation: 11: Best fitness: 1090. Worst fitness: -28 Generation: 12: Best fitness: 1090. Worst fitness: -33 Generation: 13: Best fitness: 1090. Worst fitness: -33 Generation: 14: Best fitness: 1090. Worst fitness: -38 Generation: 15: Best fitness: 1090. Worst fitness: -38 Generation: 16: Best fitness: 1090. Worst fitness: -28 Generation: 17: Best fitness: 1090. Worst fitness: -33 Generation: 18: Best fitness: 1090. Worst fitness: -38 Generation: 19: Best fitness: 1090. Worst fitness: -38 Generation loop ended. The best individual: [0 1 1 0 0 0 0 1 1 1] 1090.0
6世代目くらいで最適解にたどり着きましたね。
今回の問題では、リンゴ、納豆、チョコ、大根、ビールを入れたパターンが最適でしたね。
個体のクラスを少し変えただけですが、簡単に解くことができました！
