Genetic Algorithms used often in computer science and operations research is a metaheuristic inspired by Darwinian natural selection. They tend to fall under the larger family of evolutionary algorithms (EA). Genetic Algorithms are great at traversing a solution space quickly. Genetic Algorithm generates a candidate solution and then tests it against a metric. GA are stochastic and population based utilizing variation operators (recombination and mutation) to create the necessary variety and to bring up novelty. Selection reduces the diversity and acts as a force pushing quality.
We will easily apply these techniques to guessing a sentence example.
Begin with a sequence of letters and then we will continue to mutate one random letter at a time until the sequence turns into the target "Genetic Algorithm!"
gene_set = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."
target = "Genetic Algorithm!"
Generate a random string from the gene set.
def generate_parent(length, geneSet):
genes = []
while len(genes) < length:
sampleSize = min(length - len(genes), len(geneSet))
genes.extend(random.sample(geneSet, sampleSize))
genes = ''.join(genes)
return genes
The creates a feedback mechanicism to guide the algorithm toward a solution.
def get_fitness(guess):
return sum(1 for expected, actual in zip(target,guess)
if expected ==actual)
def mutate(parent):
index = random.randrange(0,len(parent))
childGenes = list(parent)
newGene, alternate = random.sample(gene_set,2)
childGenes[index] = alternate if newGene ==childGenes[index] else newGene
return ''.join(childGenes)
def display(guess):
timeDiff = datetime.datetime.now() - startTime
fitness = get_fitness(guess)
print('{}\t{}\t{}'.format(guess,fitness,timeDiff)
random.seed()
startTime=datetime.datetime.now()
bestParent = generate_parent(len(target),gene_set)
bestFitness = get_fitness(bestParent)
display(bestParent)
while True:
child = mutate(bestParent)
childFitness = get_fitness(child)
if bestFitness >= childFitness:
continue
display(child)
if childFitness >= len(bestParent):
break
bestFitness = childFitness
bestParent = child
Result:
u. LSVJFIlzmWqGHft 1 0:00:00.300956
u. LSVJFIlzmWqGhft 2 0:00:00.303305
u. LSVJ IlzmWqGhft 3 0:00:00.303852
u. LSVJ IlzmWqthft 4 0:00:00.305289
u. LSVJ AlzmWqthft 5 0:00:00.305701
u. LSVJ AlzmWithft 6 0:00:00.305891
u. LSVJ AlgmWithft 7 0:00:00.307354
G. LSVJ AlgmWithft 8 0:00:00.308935
G. LSiJ AlgmWithft 9 0:00:00.309484
G. LSiJ AlgmWithmt 10 0:00:00.309966
G. LtiJ AlgmWithmt 11 0:00:00.311926
G. LtiJ AlgmWithm! 12 0:00:00.316447
G. Ltic AlgmWithm! 13 0:00:00.317495
G. Ltic AlgoWithm! 14 0:00:00.325253
Ge Ltic AlgoWithm! 15 0:00:00.328090
Ge etic AlgoWithm! 16 0:00:00.331757
Ge etic Algorithm! 17 0:00:00.336659
Genetic Algorithm! 18 0:00:00.340102
References:
http://bl.ocks.org/syntagmatic/raw/3150059/nutrients.csv