'Using a Genetic algorithm to evolve to a specified string
so im working on a genetic algorithm that is meant to converge on a specific string, this string is a flattened asccii art, im using a sequenceMatcher to find the ratio of how similar a given chromosone is to the answer as my fitness, the code is as below:
import random
from difflib import SequenceMatcher
GA="0001111000001100000100001000101100010000000010001100010011100111111000011101001000010"
print(len(GA))
# Hyper-parameter
no_pop = 10 # population size
no_sel = 5 # slect the best no_sel idnividuals
no_gen = 10
p_xo = .8 # crossover probabilty/rate
p_m = 0.05 # mutation probabilty/rate per bit
# 1 Step: Select representation
no_bit = 85 # number of bits
# Create the pop
pop = [] # population
for i in range(no_pop):
pop.append(''.join(random.choice('01') for j in range(no_bit)))
pop
# convert bitstring into decimal number
def dec(chromosome):
d = 0
for i in range(len(chromosome)):
if chromosome[i] == '1':
d += 2**i
return d
def fitness(chromosome):
return SequenceMatcher(None,str(dec(chromosome)),str(dec(GA))).ratio() #check similarity to answer
def one_point_crossover(chromosome_1, chromosome_2):
cut = random.randint(1, no_bit-1) # randomy select cut point
offspring = chromosome_1[0:cut] + chromosome_2[cut:]
return offspring
def bit_flip_mutation(chromosome):
mutation = ''
for i in range(len(chromosome)):
if random.random() < p_m:
if chromosome[i] == '0':
mutation += '1'
else:
mutation += '0'
else:
mutation += chromosome[i]
return chromosome
for g in range(no_gen):
fit = []
for i in range(no_pop):
fit.append(fitness(pop[i]))
print('Gen' + str(g))
print(pop)
print(fit)
index = sorted(range(len(fit)), key=lambda k: fit[k], reverse=True)
pop_new = []
for i in index[:no_sel]:
pop_new.append(pop[i])
for i in range(no_sel, no_pop):
parent_1 = random.randint(0, no_sel-1)
parent_2 = random.randint(0, no_sel-1)
offspring = one_point_crossover(pop_new[parent_1], pop_new[parent_2])
offspring = bit_flip_mutation(offspring)
pop_new.append(offspring)
pop = pop_new
fit = []
for i in range(no_pop):
fit.append(fitness(pop[i]))
print('Gen' + str(g))
print(pop)
print(fit)
currently the algorthim doesnt achieve mpore than around 57% simmilarity to the actual answer. im confused as to why this is, any siggesttions on how to improve this would be great.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
