72 lines
2.0 KiB
Python
72 lines
2.0 KiB
Python
import numpy as np
|
|
|
|
# Obj. func
|
|
def onemax(x):
|
|
return -sum(x)
|
|
|
|
# Selection
|
|
def selection(pop, scores, k=3):
|
|
# Random selection
|
|
selected = np.random.randint(len(pop))
|
|
for idx in np.random.randint(0, len(pop), k-1):
|
|
if scores[idx] < scores[selected]:
|
|
selected = idx
|
|
return pop[idx]
|
|
|
|
# Crossover
|
|
def crossover(p1, p2, r_cross):
|
|
# Children copies of parents
|
|
c1, c2 = p1.copy(), p2.copy()
|
|
# Check and execute combination
|
|
if np.random.rand() < r_cross:
|
|
# Random crossover point
|
|
pt = np.random.randint(1, len(p1)-2)
|
|
c1 = p1[:pt] + p2[pt:]
|
|
c2 = p2[:pt] + p1[pt:]
|
|
return [c1, c2]
|
|
|
|
# Mutation
|
|
def mutation(bitstring, r_mut):
|
|
for i in range(len(bitstring)):
|
|
# Check for mutation happening
|
|
if np.random.rand() < r_mut:
|
|
# Flip
|
|
bitstring[i] = 1 - bitstring[i]
|
|
|
|
# GA
|
|
def ga(obj, n_bits, n_iter, n_pop, r_cross, r_mut):
|
|
# Init
|
|
pop = [np.random.randint(0,2,n_bits).tolist() for _ in range(n_pop)]
|
|
# Best solution
|
|
best, best_val = 0, obj(pop[0])
|
|
for gen in range(n_iter):
|
|
# Assign values
|
|
scores = [obj(c) for c in pop]
|
|
for i in range(n_pop):
|
|
if scores[i] < best_val:
|
|
best, best_val = pop[i], scores[i]
|
|
print("Found min {} in gen {}, val {}".format(pop[i], gen, scores[i]))
|
|
|
|
# Selection
|
|
selected = [selection(pop, scores) for _ in range(n_pop)]
|
|
# New generation
|
|
children = list()
|
|
for i in range(0, n_pop, 2):
|
|
# Select parents
|
|
p1, p2 = selected[i], selected[i+1]
|
|
# Crossover and mutation
|
|
for c in crossover(p1, p2, r_cross):
|
|
mutation(c, r_mut)
|
|
children.append(c)
|
|
pop = children
|
|
return[best, best_val]
|
|
|
|
if __name__ == "__main__":
|
|
n_iter = 200
|
|
n_bits = 20
|
|
n_pop = 100
|
|
r_cross = 0.9
|
|
r_mut = 1.0/float(n_bits)
|
|
best, score = ga(onemax, n_bits, n_iter, n_pop, r_cross, r_mut)
|
|
print(best, score)
|