Genetic Algorithm - random sort

random sort

from random import randrange, uniform, shuffle
from numpy import mean
from functools import reduce

CHILD_SIZE = 100
DNA_SIZE = 16
SORTED = range(DNA_SIZE)
MUTATION_RATE = 0.3
SELECT_BEST_RATE = 0.3

def shufflize(l):
	shuffle(l)
	return l

def breeding(mother, father):
	point = randrange(0, DNA_SIZE)
	sperm = father.gene[:point]
	fetus = [x for x in mother.gene if x not in sperm]
	offspring = sperm + fetus

	if uniform(0.0, 1.0) < MUTATION_RATE:
		x = randrange(0, DNA_SIZE)
		y = randrange(0, DNA_SIZE)
		offspring[x], offspring[y] = offspring[y], offspring[x]

	return offspring

class DNA:
	def __init__(self, gene):
		self.gene = gene
	
	def __repr__(self):
		return "[DNA %s |FIT %f]\n" % (self.gene, self.fitness)

	@property
	def fitness(self) -> int:
		return reduce(lambda x, y: x+y, list(map(lambda x, y: DNA_SIZE-abs(x-y), SORTED, self.gene)))

class Generation:
	def __init__(self, DNA_list):
		self.DNA_list = DNA_list

	def __repr__(self):
		return "%s%d" % (self.DNA_list, self.fitness())

	def fitness(self):
		return mean([dna.fitness for dna in self.DNA_list])

	def evolution(self):
		print(self.best())
		childs = [self.best() if uniform(0.0, 1.0) < SELECT_BEST_RATE else self.child() for _ in range(CHILD_SIZE)]
		return Generation(childs)

	def best(self):
		return sorted(self.DNA_list, key=lambda dna: dna.fitness)[-1]

	def child(self):
		father = self.findParents()
		mother = self.findParents()
		return DNA(breeding(mother, father))

	def findParents(self):
		p = uniform(0.0, sum([x.fitness for x in self.DNA_list]))
		c = 0
		for dna in self.DNA_list:
			c += dna.fitness
			if c>p:
				return dna


generations = []
if __name__ == '__main__':
	generations.append(Generation([DNA(shufflize(list(range(DNA_SIZE)))) for _ in range(CHILD_SIZE)]))

	while generations[-1].best().fitness < DNA_SIZE * DNA_SIZE:
		generations.append(generations[-1].evolution())

	print("Finish")