はじめに
今回は遺伝的アルゴリズムを使用して工場の生産計画を、たててみます。
以前のナップサック問題と違って漸化式が立てづらいので動的計画法はなかなか使えませんが、遺伝的アルゴリズムなら何も考えなくてもそれっぽい計画を立ててくれると信じます。
それではやっていきましょう
生産計画問題の定義
だいぶ簡略化するので前提として以下のことを守ります
- 1生産ラインの5日分の計画をたてる。
- 生産ラインで仕掛けられる品番は5種類
- 1日に生産できる数は全品番同様で10ロット(10ロット毎日フルで生産する)
- 各品番は1ロット単位での生産
- 0日目の初期在庫あり
- 各品番毎日引取りの計画があるので納期厳守で生産
最適化の対象は下記です
- 一日に生産する品番種類の最小化
初期在庫および、日々の需要は以下です。
初期在庫：
| 品番 | 初期在庫[ロット] |
| 0 | 3 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 1 |
日々の需要：
| 品番 | 1日目の需要[ロット] | 2日目の需要[ロット] | 3日目の需要[ロット] | 4日目の需要[ロット] | 5日目の需要[ロット] |
| 0 | 3 | 3 | 3 | 3 | 3 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 2 | 2 | 2 |
| 3 | 3 | 3 | 3 | 3 | 3 |
| 4 | 1 | 1 | 1 | 1 | 1 |
簡単にするために毎日変動なしとしておきました。
初期在庫は1日目の分を事前に在庫として持っておくこととしています。
つまり、各品番において、初期在庫+n日目までの累積生産数-各n日目までの累積需要数がマイナスにならないようにする必要があります
ここで日数は全部で5日なのでnは1~5において成り立つ必要がありますね
遺伝的アルゴリズムでの実装
基本的には、過去作成した遺伝的アルゴリズムのプログラムのコピペでできます。
今回はコピペした部分は説明割愛しますので過去記事参考願います。
遺伝的アルゴリズムを適用するために遺伝子情報及び評価関数を決めます。
遺伝子情報の定義
今回は1日10ロット×5日間なので50個の数列を遺伝子情報として定義します。
各遺伝子はそのロットで生産する品番を数値で表したものとして表現することにします。
今回は品番数が5個なので、0~4までの数字の羅列が遺伝子情報になります。
評価関数の定義
まずは、各日の各品番の納期厳守なので、それぞれの日の終わりにすべての品番において初期在庫+その日までの累積生産数-その日までの累積需要数を計算し、
納期未達、つまり値が負となる品番があればその合計をペナルティとして与えます。
納期厳守なので日々の不足分を10倍にしてペナルティとしておきます。
また、最適化の対象は、一日に生産する品番種類の最小化ですので、日々の生産計画の品番点数-1に-1をかけたものをペナルティとします。
品番点数に-1する理由ですが、これは段取り回数を示したかったため、-1しました。
(1日のロットの順番は問わず、3種類生産するときは段取りが2回発生するのでそれをペナルティにしたという感じです)
個体クラスの作成
上記の定義を織り込んで作成した個体クラスは下記のとおりです。
import numpy as np def calc_prod(prod, baffar, dem): day_prod = np.array([np.sum(prod == i) for i in range(PRODUCTION_NUM)]) total = baffar + day_prod - dem to = -1 for i in range(PRODUCTION_NUM): to += int(np.any(prod == i)) return total, to 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に代入''' self.fitness = 0 day_prod = baffar prods = np.array([]) for i in range(DAYS): day_prod, to = calc_prod(self.genom[i * ROTS_PER_DAY:(i + 1) * ROTS_PER_DAY], day_prod, dem[i, :]) prods = np.concatenate([prods, day_prod]) self.fitness -= to for prod in prods: if prod < 0: self.fitness += prod * 10 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] = np.random.randint(0, PRODUCTION_NUM) self.genom = tmp self.set_fitness()
実装
ここまでくればあとはほぼコピペですので以下に全コード張っておきます。
import numpy as np import matplotlib.pyplot as plt def calc_prod(prod, baffar, dem): day_prod = np.array([np.sum(prod == i) for i in range(PRODUCTION_NUM)]) total = baffar + day_prod - dem to = -1 for i in range(PRODUCTION_NUM): to += int(np.any(prod == i)) return total, to 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に代入''' self.fitness = 0 day_prod = baffar prods = np.array([]) for i in range(DAYS): day_prod, to = calc_prod(self.genom[i * ROTS_PER_DAY:(i + 1) * ROTS_PER_DAY], day_prod, dem[i, :]) prods = np.concatenate([prods, day_prod]) self.fitness -= to for prod in prods: if prod < 0: self.fitness += prod * 10 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] = np.random.randint(0, PRODUCTION_NUM) self.genom = tmp self.set_fitness() def select_roulette(generation): '''選択の関数(ルーレット方式)''' selected = [] weights = [ind.get_fitness() for ind in generation] norm_weights = [ind.get_fitness() / sum(weights) for ind in generation] selected = np.random.choice(generation, size=len(generation), p=norm_weights) return selected def select_tournament(generation): '''選択の関数(トーナメント方式)''' selected = [] for i in range(len(generation)): tournament = np.random.choice(generation, 3, replace=False) max_genom = max(tournament, key=Individual.get_fitness).genom.copy() selected.append(Individual(max_genom)) return selected def crossover(selected): '''交叉の関数''' children = [] if POPURATIONS % 2: selected.append(selected[0]) for child1, child2 in zip(selected[::2], selected[1::2]): if np.random.rand() < CROSSOVER_PB: child1, child2 = cross_two_point_copy(child1, child2) children.append(child1) children.append(child2) children = children[:POPURATIONS] return children def cross_two_point_copy(child1, child2): '''二点交叉''' size = len(child1.genom) tmp1 = child1.genom.copy() tmp2 = child2.genom.copy() cxpoint1 = np.random.randint(1, size) cxpoint2 = np.random.randint(1, size - 1) if cxpoint2 >= cxpoint1: cxpoint2 += 1 else: cxpoint1, cxpoint2 = cxpoint2, cxpoint1 tmp1[cxpoint1:cxpoint2], tmp2[cxpoint1:cxpoint2] = tmp2[cxpoint1:cxpoint2].copy(), tmp1[cxpoint1:cxpoint2].copy() new_child1 = Individual(tmp1) new_child2 = Individual(tmp2) return new_child1, new_child2 def mutate(children): for child in children: if np.random.rand() < MUTATION_PB: child.mutate() return children def create_generation(POPURATIONS, GENOMS): '''初期世代の作成 return: 個体クラスのリスト''' generation = [] for i in range(POPURATIONS): individual = Individual(np.random.randint(0, PRODUCTION_NUM, GENOMS)) generation.append(individual) return generation def ga_solve(generation): '''遺伝的アルゴリズムのソルバー return: 最終世代の最高適応値の個体、最低適応値の個体''' best = [] worst = [] # --- Generation loop print('Generation loop start.') for i in range(GENERATIONS): # --- Step1. Print fitness in the generation best_ind = max(generation, key=Individual.get_fitness) best.append(best_ind.fitness) worst_ind = min(generation, key=Individual.get_fitness) worst.append(worst_ind.fitness) print("Generation: " + str(i) \ + ": Best fitness: " + str(best_ind.fitness) \ + ". Worst fitness: " + str(worst_ind.fitness)) # --- Step2. Selection (Roulette) # selected = select_roulette(generation) selected = select_tournament(generation) # --- Step3. Crossover (two_point_copy) children = crossover(selected) # --- Step4. Mutation generation = mutate(children) print("Generation loop ended. The best individual: ") print(best_ind.genom) return best, worst if __name__ == '__main__': np.random.seed(seed=64) # param POPURATIONS = 100 PRODUCTION_NUM = 5 DAYS = 5 ROTS_PER_DAY = 10 GENOMS = DAYS * ROTS_PER_DAY GENERATIONS = 50 CROSSOVER_PB = 0.8 MUTATION_PB = 0.1 # problem dem = np.array([[3, 1, 2, 3, 1], [3, 1, 2, 3, 1], [3, 1, 2, 3, 1], [3, 1, 2, 3, 1], [3, 1, 2, 3, 1]]) baffar = np.array([3, 1, 2, 3, 1]) # create first genetarion generation = create_generation(POPURATIONS, GENOMS) # solve best, worst = ga_solve(generation) # plot fig, ax = plt.subplots() ax.plot(best, label='max') ax.plot(worst, label='min') # ax.axhline(y=GENOMS, color='black', linestyle=':', label='true') 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: -19. Worst fitness: -317.0 Generation: 1: Best fitness: -17. Worst fitness: -190.0 Generation: 2: Best fitness: -14. Worst fitness: -188.0 Generation: 3: Best fitness: -15. Worst fitness: -155.0 Generation: 4: Best fitness: -15. Worst fitness: -149.0 Generation: 5: Best fitness: -14. Worst fitness: -116.0 Generation: 6: Best fitness: -14. Worst fitness: -116.0 Generation: 7: Best fitness: -14. Worst fitness: -117.0 Generation: 8: Best fitness: -14. Worst fitness: -86.0 Generation: 9: Best fitness: -14. Worst fitness: -55.0 Generation: 10: Best fitness: -13. Worst fitness: -96.0 Generation: 11: Best fitness: -13. Worst fitness: -55.0 Generation: 12: Best fitness: -13. Worst fitness: -34.0 Generation: 13: Best fitness: -12. Worst fitness: -33.0 Generation: 14: Best fitness: -12. Worst fitness: -24.0 Generation: 15: Best fitness: -12. Worst fitness: -33.0 Generation: 16: Best fitness: -12. Worst fitness: -23.0 Generation: 17: Best fitness: -12. Worst fitness: -24.0 Generation: 18: Best fitness: -11. Worst fitness: -53.0 Generation: 19: Best fitness: -11. Worst fitness: -41.0 Generation: 20: Best fitness: -11. Worst fitness: -31.0 Generation: 21: Best fitness: -11. Worst fitness: -32.0 Generation: 22: Best fitness: -10. Worst fitness: -22.0 Generation: 23: Best fitness: -10. Worst fitness: -33.0 Generation: 24: Best fitness: -10. Worst fitness: -12 Generation: 25: Best fitness: -10. Worst fitness: -20.0 Generation: 26: Best fitness: -10. Worst fitness: -21.0 Generation: 27: Best fitness: -10. Worst fitness: -21.0 Generation: 28: Best fitness: -10. Worst fitness: -30.0 Generation: 29: Best fitness: -10. Worst fitness: -21.0 Generation: 30: Best fitness: -10. Worst fitness: -21.0 Generation: 31: Best fitness: -10. Worst fitness: -21.0 Generation: 32: Best fitness: -10. Worst fitness: -11 Generation: 33: Best fitness: -10. Worst fitness: -21.0 Generation: 34: Best fitness: -9. Worst fitness: -21.0 Generation: 35: Best fitness: -9. Worst fitness: -11 Generation: 36: Best fitness: -9. Worst fitness: -20.0 Generation: 37: Best fitness: -9. Worst fitness: -20.0 Generation: 38: Best fitness: -9. Worst fitness: -20.0 Generation: 39: Best fitness: -9. Worst fitness: -18.0 Generation: 40: Best fitness: -9. Worst fitness: -20.0 Generation: 41: Best fitness: -9. Worst fitness: -19.0 Generation: 42: Best fitness: -9. Worst fitness: -19.0 Generation: 43: Best fitness: -9. Worst fitness: -20.0 Generation: 44: Best fitness: -9. Worst fitness: -20.0 Generation: 45: Best fitness: -9. Worst fitness: -19.0 Generation: 46: Best fitness: -9. Worst fitness: -20.0 Generation: 47: Best fitness: -9. Worst fitness: -19.0 Generation: 48: Best fitness: -9. Worst fitness: -19.0 Generation: 49: Best fitness: -9. Worst fitness: -18.0 Generation loop ended. The best individual: [0 0 0 0 3 0 3 0 0 3 4 3 2 2 3 4 4 1 2 4 3 3 1 2 2 2 3 2 3 1 0 3 3 1 1 1 0 3 0 3 0 2 2 0 0 0 0 2 0 0]
50世代目の評価点は-9点でした。
評価点数が-10以上なので納期遅れは1回も起きていないと言えます。
5日間で段取り回数が9回で納期遅れなく生産できるということですね。
割と手入力で生産計画を立てるのは時間がかかりますが、これならある程度の解が10秒以内で求まるので実用できそうですね。
