Genetic algorithm

genetic.py

# refer: https://www.geeksforgeeks.org/genetic-algorithms/

import random

POPULATION_SIZE = 100

# Valid genes 
GENES = """abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP 
QRSTUVWXYZ 1234567890, .-;:_!"#%&/()=?@${[]}"""

TARGET = "The meaning of life and universe is 42"


def gene():
	return random.choice(GENES)

def create_gnome():
	return [gene() for _ in range(len(TARGET))] 



class Individual(object):
	def __init__(self, chromosome):
		self.chromosome = chromosome
		self.fitness  = self.cal_fitness()


	def cal_fitness(self):
		return sum(
			map(lambda t: t[0] != t[1], zip(self.chromosome, TARGET)))



def mate(par1, par2):
	child_chromosome = []
	for gp1, gp2 in zip(par1.chromosome, par2.chromosome):
		prob = random.random()

		if prob < 0.45:
			child_chromosome.append(gp1)

		elif prob < 0.9:
			child_chromosome.append(gp2)
		else:
			child_chromosome.append(gene())

	return Individual(child_chromosome)



if __name__ == '__main__':
	generation = 1

	found = False
	population = []

	# initial population
	for _ in range(POPULATION_SIZE):
		gnome = create_gnome()
		population.append(Individual(gnome))

	# population = sorted(population, key=lambda x:x.fitness)
	# print(population[0].fitness)
	while not found:
		population = sorted(population, key=lambda x:x.fitness)

		if population[0].fitness <= 0:
			found = True
			break

		# Elitism, 10% of fittest population goes to next generation
		s = int(0.1 * POPULATION_SIZE)
		new_generation = population[:s]

		# mate for diversity in the other 90%
		h = int(0.5 * POPULATION_SIZE)
		for _ in range(int(0.9*POPULATION_SIZE)):
			parent1 = random.choice(population[:h])
			parent2 = random.choice(population[:h])
			child = mate(parent1, parent2)
			new_generation.append(child)

		population = new_generation

		print("Generation: {}\tString: {}\tFitness: {}".format(generation, 
              	"".join(population[0].chromosome), 
              	population[0].fitness)) 

		generation += 1

	print("Generation: {}\tString: {}\tFitness: {}".format(generation, 
          	"".join(population[0].chromosome), 
          	population[0].fitness))