機械学習と深層学習 Pythonによるシミュレーション の第3章の遺伝的アルゴリズムのコード kpga.py
について、 わかりやすく書き換えてみました。
環境
- Python 3.6.5 Anaconda
コード
変数・定数名をだいたい変えています。 そして、テスト用ファイルを作らなくても自動的に荷物を生成するように init_parcel
を変更しています。 また、 eval_fit
で重さの合計値も出力するよう変更しています。
eval_fit
は適合度を計算する関数という説明が 書籍 にありましたが、 適合度というのは合計価値のことですね。 それを下のコードでは合計重量と一緒に返しています。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 |
import math import random import copy from itertools import product MAX_VALUE = 100 N = 30 WEIGHT_LIMIT = N * MAX_VALUE / 4 POOL_SIZE = 30 LAST_GENERATION = 50 MUTATION_RATE = 0.01 SEED = 32767 parcel = [[0 for i in range(2)] for j in range(N)] def rndn(n): return random.randint(0, n - 1) def init_parcel(): global parcel parcel = [ [ random.randint(1, MAX_VALUE), random.randint(1, MAX_VALUE) ] for j in range(N) ] def mating(pool, ng_pool): roulette = [0 for i in range(POOL_SIZE)] total_fitness = 0 for i in range(POOL_SIZE): weight, roulette[i] = eval_fit(pool[i]) total_fitness += roulette[i] for i in range(POOL_SIZE): while True: mama = select_p(roulette, total_fitness) papa = select_p(roulette, total_fitness) if mama != papa: break crossing( pool[mama], pool[papa], ng_pool[i * 2], ng_pool[2 * i + 1]) def eval_fit(gene): """ Calculate total value. Return 0 for overweight. """ value = 0 weight = 0 for pos in range(N): weight += parcel[pos][0] * gene[pos] value += parcel[pos][1] * gene[pos] if weight >= WEIGHT_LIMIT: return weight, 0 return weight, value def select_p(roulette, total_fitness): acc = 0 ball = rndn(total_fitness) for i in range(POOL_SIZE): acc += roulette[i] if acc > ball: break return i def crossing(m, p, c1, c2): cp = rndn(N) for j in range(cp): c1[j] = m[j] c2[j] = p[j] for j in range(cp, N): c2[j] = m[j] c1[j] = p[j] def mutation(ng_pool): for i, j in product(range(POOL_SIZE * 2), range(N)): if random.random() < MUTATION_RATE: if ng_pool[i][j] == 0: ng_pool[i][j] = 1 else: ng_pool[i][j] = 0 def select_ng(ng_pool, pool): total_fitness = 0 roulette = [0 for i in range(POOL_SIZE * 2)] acc = 0 for i in range(POOL_SIZE): total_fitness = 0 for c in range(POOL_SIZE * 2): _, roulette[c] = eval_fit(ng_pool[c]) total_fitness += roulette[c] ball = rndn(total_fitness) acc = 0 for c in range(POOL_SIZE * 2): acc += roulette[c] if acc > ball: break pool[i] = copy.deepcopy(ng_pool[c]) def print_p(pool): total_fitness = 0 best_fit = 0 for i in range(POOL_SIZE): weight, fitness = eval_fit(pool[i]) if fitness > best_fit: best_fit = fitness elite = i print( pool[i], " fitness =", fitness, "weight =", weight) total_fitness += fitness print(elite, best_fit, total_fitness / POOL_SIZE) if __name__ == "__main__": random.seed(SEED) pool = [ [rndn(2) for i in range(N)] for j in range(POOL_SIZE) ] ng_pool = [ [0 for i in range(N)] for j in range(POOL_SIZE * 2) ] generation = 0 init_parcel() for generation in range(LAST_GENERATION): print(generation, 'generation') mating(pool, ng_pool) mutation(ng_pool) select_ng(ng_pool, pool) print_p(pool) |
荷物をクラスにするなどまだまだ変更できるところはありますが、とりあえずここまでです。
荷物の組み合わせは何度も作成されますが、前回よりも必ずスコアが良くなるというわけではないですね。 ただ、平均は上がっていきます。
計画的に計算するアルゴリズムではなく、乱数で進めていくアルゴリズムなので、 数値によっては ng_pool
の中に候補がひとつしかないこともあります。 その場合はエラー終了します。 候補がひとつもなければループから抜け出せなくなります。