Machine Learning and Deep Learning: Simulation with Python

I’ve rewritten the code for genetic algorithms in Chapter 3 of “Machine Learning and Deep Learning: Simulation with Python” (kpga.py) to make it more understandable.

Environment

Python 3.6.5 Anaconda

Code

I’ve changed variable and constant names significantly. Additionally, I’ve modified the init_parcel function to automatically generate items without needing a test file. Furthermore, in the eval_fit function, I’ve added output for the total weight along with the fitness.

The explanation of the eval_fit function in the book referred to it as the fitness calculation function, but fitness here refers to the total value. In the following code, I return both the total weight and the value as fitness.

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)

There are still areas where further changes can be made, such as encapsulating the items into a class, but this is a basic implementation.

Keep in mind that the combinations of items are generated multiple times, and there’s no guarantee that the score will always improve from the previous generation. However, the average score tends to increase over generations.

Since this algorithm progresses randomly rather than in a planned manner, there may be cases where the ng_pool contains only one candidate due to specific numeric conditions. In such cases, it may lead to an error termination. If there are no candidates at all, it will be impossible to exit the loop.