機械学習と深層学習 Python によるシミュレーション kpga.py

機械学習と深層学習 Pythonによるシミュレーションの第3章の遺伝的アルゴリズムのコード kpga.pyについて、わかりやすく書き換えてみました。

環境

Python 3.6.5 Anaconda

コード

変数・定数名をだいたい変えています。そして、テスト用ファイルを作らなくても自動的に荷物を生成するように init_parcel を変更しています。また、 eval_fit で重さの合計値も出力するよう変更しています。

eval_fit は適合度を計算する関数という説明が書籍にありましたが、適合度というのは合計価値のことですね。それを下のコードでは合計重量と一緒に返しています。

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)

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 の中に候補がひとつしかないこともあります。その場合はエラー終了します。候補がひとつもなければループから抜け出せなくなります。

The Life

機械学習と深層学習 Python によるシミュレーション kpga.py

環境

コード

関連記事

A Life Summary of an Gypsy