GA combine SA
unknown
python
2 years ago
6.4 kB
6
Indexable
import numpy as np
import matplotlib.pyplot as plt
from math import exp, cos, sin
import matplotlib
import random
from typing import List, Dict
from random import randint
from graycode import gray_code_to_tc
def f(x1, x2):
# f = f1 + f2 + f3
f1 = 4 * ((2 - x1) ** 2) * exp(-(x1 ** 2) - (x2 - 1)**2)
f2 = 10 * (x1 / 4 - x1 ** 3 - x2 ** 5) * exp(-(x1 ** 2) - (x2 ** 2))
f3 = 0.5 * exp(-(x1 + 2) ** 2 - x2 ** 2)
return f1 + f2 + f3
def binary_to_int_in_range(bits: List[int], range: int):
string_bits = "0b"
for bit in bits:
string_bits += f"{bit}"
num_out_of_range = gray_code_to_tc(int(string_bits, 2))
return (num_out_of_range - 128) * range / 128
def f_binary(bits: List[int]):
# separate x1 and x2 bits
x1_bits = bits[0:8]
x2_bits = bits[8:16]
# generate x1 , x2 from graycode to int to float
x1 = binary_to_int_in_range(x1_bits, 3)
x2 = binary_to_int_in_range(x2_bits, 4)
return f(x1, x2)
def get_x1_and_x2(pop: List[List[int]]):
x1 = []
x2 = []
for ind_bit in pop:
x1_bits = ind_bit[0:8]
x2_bits = ind_bit[8:16]
x1.append(binary_to_int_in_range(x1_bits, 3))
x2.append(binary_to_int_in_range(x2_bits, 4))
return x1, x2
def crossover(p1, p2, generations_number, temperature):
# crossover two parents to create two children
# select crossover point that is not on the end of the string
pt = randint(1, len(p1)-2)
# perform crossover
c1 = p1[:pt] + p2[pt:]
c2 = p2[:pt] + p1[pt:]
# calculate sum of parent fitness
curr_eval = f_binary(p1) + f_binary(p2)
# calculate sum of childeren fitness
candidate_eval = f_binary(c1) + f_binary(c2)
# difference between candidate and current point evaluation
diff = candidate_eval - curr_eval
# calculate temperature for current epoch
t = temperature / float(generations_number + 1)
# calculate metropolis acceptance criterion
metropolis = exp(-diff / t)
# check if we should keep the new point
if diff < 0 or np.random.rand() < metropolis:
# retrun the new current point
return [c1, c2]
else:
return [p1, p2]
# mutation operator
def mutation(bitstring, generations_number, temperature):
i = randint(0, len(bitstring) - 1)
# calculate bitstring fitness
curr_eval = f_binary(bitstring)
# flip the bit
bitstring[i] = 1 - bitstring[i]
# calculate new bitstring fitness
candidate_eval = f_binary(bitstring)
# difference between candidate and current point evaluation
diff = candidate_eval - curr_eval
# calculate temperature for current epoch
t = temperature / float(generations_number + 1)
# calculate metropolis acceptance criterion
metropolis = exp(-diff / t)
# check if we should keep the new point
if not (diff < 0 or np.random.rand() < metropolis):
# flip back the bit
bitstring[i] = 1 - bitstring[i]
def selection(pop, scores, k=3):
# first random selection
selection_ix = randint(0, len(pop) - 1)
for ix in [randint(0, len(pop) - 1) for _ in range(k)]:
# check if better (e.g. perform a tournament)
if scores[ix] > scores[selection_ix]:
selection_ix = ix
return pop[selection_ix]
def genetic_algorithm(generations, population_size, crossover_temperature, mutation_temperature, n_bits=16):
average_fitness = []
best_fitness = []
worst_fitness = []
# initial population of random bitstring
pop = [[randint(0, 1)for bit in range(n_bits)]
for _ in range(population_size)]
ind_max_f, max_f = 0, f_binary(pop[0])
# enumerate generations
for gen in range(generations + 1):
# plot pop if gen == 0 , 5 ,10 , 50
if gen in [0, 5, 10, 50]:
x1, x2 = get_x1_and_x2(pop)
plot_fx_and_points_gen(x1, x2, gen)
scores = [f_binary(c) for c in pop]
average_fitness.append(sum(scores) / len(scores))
best_fitness.append(max(scores))
worst_fitness.append(min(scores))
# check for new best solution
for i in range(population_size):
if scores[i] > max_f:
ind_max_f, max_f = pop[i], scores[i]
# select parents
selected = [selection(pop, scores)
for _ in range(population_size)]
# create the next generation
children = list()
for i in range(0, population_size, 2):
# get selected parents in pairs
p1, p2 = selected[i], selected[i+1]
# crossover and mutation
for c in crossover(p1, p2, i, crossover_temperature):
# mutation
mutation(c, i, mutation_temperature)
# store for next generation
children.append(c)
# replace population
pop = children
fig, ax = plt.subplots()
gen_list = [i for i in range(generations + 1)]
plt.plot(gen_list, best_fitness, color='green', marker="*")
plt.plot(gen_list, worst_fitness, color='red', marker="o")
plt.plot(gen_list, average_fitness, color='blue', marker="+")
plt.legend(["best_fitness", "worst_fitness", "average_fitness"])
ax.set_xlabel('generation number', fontsize=16)
ax.set_xlabel('fitness', fontsize=16)
plt.show()
# print(best_fitness, worst_fitness, average_fitness)
return [ind_max_f, max_f]
def plot_fx_and_points_gen(x1, x2, gen):
x1_list = np.arange(-3, 3.2, 0.2)
x2_list = np.arange(-4, 4.2, 0.2)
X1, X2 = np.meshgrid(x1_list, x2_list)
F = np.vectorize(f)
Z = F(X1, X2)
fig, ax = plt.subplots()
cnt = ax.contour(Z, cmap=matplotlib.cm.jet, vmin=abs(
Z).min(), vmax=abs(Z).max(), extent=[-3, 3, -4, 4], alpha=0.5)
ax.set_xlabel('x1', labelpad=20, fontsize=16)
ax.set_ylabel('x2', labelpad=20, fontsize=16)
ax.set_title(f'Generation number {gen}', fontsize=20)
im = ax.imshow(Z, cmap=matplotlib.cm.jet, vmin=abs(
Z).min(), vmax=abs(Z).max(), extent=[-3, 3, 4, -4], alpha=0.4)
im.set_interpolation('bilinear')
plt.plot(x1, x2, 'bo', color="black")
plt.show()
population_size = 20
generations = 50
temperature = 10
mutation_temperature = 10
crossover_temperature = 1
print(genetic_algorithm(
generations, population_size, crossover_temperature, mutation_temperature))
Editor is loading...