# Genetic Algorithm in Python

I'm a new programmer, so any help is welcome. Preferably to make it faster, avoid heavy memory usage, and so on.

#! /usr/bin/env python
"""
This module is a frame work for a Genetic Algorithm.

:param GenePool: See this documentation for how to use this module..
:type GenePool: GenePool

Author: Fernando Rodrigues dos Santos
"""
import random
import math
import pickle
import itertools
import sys

class GenePool():
""""
Place a gene in the  desired program using GenePool.nextGene().
Place the genes variables(Gene.dna[id]) in the desired program.
Reward good choices.

Call GenePool.return_result() and pass the gene and the result to start the GA.

After this the Genetic Algorithm will:
- Save the top genes without modification and duplicate them(the amount is set by the elitism).

- Remove the random genes to fit the population(the amount is set by the elitism).

- Randomly choose genes based on their rank(roulette-wheel selection).

- Cross-over the selected genes using the two-points cut method.(the amount of genes crossed is set by the
cross_coefficient).

- Finally it will apply the mutation to each gene(expect the top-rated).

- It will repeat until find a convergence or stop if maxIteration is set.

:param sample: The pattern of genes to be created.
:type sample: list
:param population: How many genes will be in the gene_pool.
:type population: int
:param cross_coefficient: The percentage of genes to do a random cross-over.
:type cross_coefficient: float
:param elitism: The amount of best-fitted genes to remain intact.
:type elitism: float
:param mutation: The chance that a dna will randomly mutate.
:type mutation: float
:param max_iterations: How many times it will try to find a convergence, if -1 it will run indefinitely(default).
:type max_iterations: int
:param save: File to save the pool.
:type save: str
"""

def __init__(self, sample, population, cross_coefficient=0.1, elitism=0.05, mutation=0.05, max_iterations=-1,
save="oldDNA.txt"):
"""
The generated genes will be based on the sample;
- bool, True or False
- int, random number between 0 and1024
- float, random number between 0.0 and 1.0

- str, a combination of one letter(a-z) and one number(0-9). E.gene: "a1", "b2", "c2"..."z9".

Population is the size of the gene_pool.

See more in the class documentation.
"""

self.sample = sample
self.population = population
self.genes = {}
self.new_gene_pool = []
self.cross_coefficient = cross_coefficient
self.elitism = elitism
self.mutation = mutation
self.max_iterations = max_iterations
self.current_iteration = 0
self.total_result = 0
self.calls = -1
self.save = save
self.convergence = False
self.new_genes()

def new_genes(self):
while len(self) != self.population:
dna = []
for chromosome in self.sample:
if chromosome == bool:
dna.append(bool(random.getrandbits(1)))
elif chromosome == int:
dna.append(random.randint(0, 2 ** 10))
elif chromosome == float:
dna.append(random.random())
gene = Genes(self, '%i' % (len(self) + 1), dna)
self[gene.name] = gene

def next_gene(self):
"""
:returns: A gene to be used.
:rtype: Genes

"""
self.calls += 1
if self.calls >= self.population:
self.calls = 0
self.start_genetic_algorithm()

return self[self.calls]

def replace_gene(self, old_gene, new_dna, result, rank):
new_gene = Genes(self, old_gene.name, new_dna, result=result, rank=rank)
self[old_gene.name] = new_gene
self.new_gene_pool.append(new_gene)

def rated_list(self, cut):
rated_list = sorted([(gene.rank, gene) for _, gene in self.genes.iteritems()])[::-1]

selected = int(math.ceil(len(self) * self.elitism))
top_genes = rated_list[0:selected]
mid_genes = rated_list[selected:len(self) - selected]

genes = None
if cut == 'top':
genes = top_genes
elif cut == 'mid':
genes = mid_genes

return genes

def duplicate_top(self):
top_genes = self.rated_list('top')
for gene in top_genes:
gene = gene
gene.rank /= 2
gene.result /= 2
new_gene = Genes(self, "%i" % (len(self) + 1), gene.dna, gene.result, gene.rank)
self[new_gene.name] = new_gene
self.new_gene_pool.append(new_gene)
gene.lock = True
self.new_gene_pool.append(gene)

def mutate_mid_genes(self):
for gene in self:
new_dna = []
for chromosome in gene.dna:
rand = random.random()
if rand <= self.mutation:
if type(chromosome) == bool:
new_dna.append(bool(random.getrandbits(1)))
if type(chromosome) == int:
new_dna.append(random.randint(0, 2 ** 10))
if type(chromosome) == float:
new_dna.append(random.random())
else:
new_dna.append(chromosome)
gene.dna = new_dna

def cross_genes(self):
ranks = [gene.rank for gene in self.genes.itervalues()]
min_rank = min(ranks)
max_rank = max(ranks)
max_tries = 0
while len(self.new_gene_pool) < self.population or max_tries == 100:
max_tries += 1
gene1 = None
gene2 = None
while gene1 is None or gene2 is None:
rand = random.uniform(min_rank, max_rank)
gene1 = [gene for gene in self.genes.itervalues() if gene.rank >= rand and not gene.lock and gene
.rank != 1]
if gene1:
gene1 = random.choice(gene1)
pass
else:
gene1 = None
rand = random.uniform(min_rank, max_rank)
gene2 = [gene for gene in self.genes.itervalues() if gene.rank >= rand and not gene.lock and gene !=
gene1 and gene.rank != 1]
if gene2:
gene2 = random.choice(gene2)
else:
gene2 = None
self.crossover(gene1, gene2)
for gene in self:
gene.lock = False

def crossover(self, gene1, gene2):
"""Two-Point cross-over"""
cross_point1, cross_point2 = None, None
while not cross_point2 and not cross_point1:
cross_point1 = random.randint(0, len(gene1))
cross_point2 = random.randint(0, len(gene1))
if cross_point1 == cross_point2 or cross_point1 > cross_point2:
cross_point1, cross_point2 = None, None
new_dna1 = gene1[:cross_point1] + gene2[cross_point1:cross_point2] + gene1[cross_point2:]
new_dna2 = gene2[:cross_point1] + gene1[cross_point1:cross_point2] + gene2[cross_point2:]
result = (gene1.result + gene2.result) / 2
rank = (gene1.rank + gene2.rank) / 2
self.replace_gene(gene1, new_dna1, result, rank)
self.replace_gene(gene2, new_dna2, result, rank)

def return_result(self, gene, result):
"""Return here the gene, it's fitness result. Set force to True to run the GA in the gene_pool
:param gene: The gene which was run.
:type gene: Genes
:param result: The fitness result.
:type result: int
"""
gene.result += result
self.total_result += gene.result

def test_convergence(self, print_result=False):
if print_result:
pro = 0
con = 0
for gene1, gene2 in itertools.combinations(self.genes.itervalues(), 2):
if gene1.dna == gene2.dna:
pro += 1
else:
con += 1
cc = (con + 1) / (pro + 1)
print "Converged rate: 1:%i" % cc

if self.convergence or self.current_iteration == self.max_iterations:
for gene in self:
print "Convergence Found: \nGene: %s\nDNA: %s" % (gene.name, gene.dna)
sys.exit("End of the line")

def reset_genes(self):
for gene in self:
gene.rank = 0
gene.result = 0
gene.lock = False
self.total_result = 0

def save_results(self):
f = open(self.save, 'w')
pickle.dump(self, f)
f.close()

def update_result(self):
self.total_result = 0
self.genes = {}
for gene in self.new_gene_pool:
new_gene = Genes(self, '%i' % (len(self.genes) + 1), gene.dna)
self.genes[new_gene.name] = new_gene
self.new_gene_pool = []

def start_genetic_algorithm(self):
[gene.update_rank() for gene in self.genes.itervalues()]
self.current_iteration += 1
self.duplicate_top()
self.cross_genes()
self.update_result()
self.test_convergence(print_result=True)
self.mutate_mid_genes()
# self.saveResults()
return self.convergence

def __getitem__(self, item):
if type(item) == str:
return self.genes[item]
if type(item) == int:
return self[sorted(self.genes)[item]]

def __setitem__(self, key, value):
self.genes[key] = value

def __len__(self):
return len(self.genes)

class Genes():
"""
A gene which mutates based on it's gene_pool settings

:param gene_pool: Where all genes are stored and the GA will run
:type gene_pool: GenePool
:param dna: The core of the gene, it's based on the sample set on the gene_pool.
:type dna: list
:param result: The current fitness result of the gene.
:type result: int
:param rank: The result from 0.0 to 1.0 of the gene in the gene_pool.
:type rank: float
"""

def __init__(self, gene_pool, name, dna, result=0, rank=0):
"""should be instantiated by genePool.newGenes()"""
self.name = name
self.gene_pool = gene_pool
self.dna = dna
self.result = result
self.rank = rank
self.lock = False

def update_rank(self):
self.rank = self.result / float(self.gene_pool.total_result)
return self.rank

def __len__(self):
return len(self.dna)

def __getitem__(self, item):
return self.dna[item]

gene_pool = GenePool([int] * 3, 100)

while True:
gene = gene_pool.next_gene()
dna = gene.dna
result = 1
if dna <= 100:
result += 10
if dna == 100:
result += 100
if dna >= 200:
result += 10
if dna == 200:
result += 100
if 100 <= dna <= 200:
result += 10
if dna == 150:
result += 100

if dna == 100 and dna == 200 and dna == 150:
gene_pool.convergence = True

gene_pool.return_result(gene, result)

• Is there a specific performance issue you've noticed? Have you tried anything to make it faster and/or reduce memory footprint? Any profiling? Do you have an example we can run? – jonrsharpe Jun 25 '14 at 9:56
• If I use a population of 100 and my the lenght of the dna is 10 it takes around 30 seconds for a calculation. I'm trying to shrink uses of for loops and the like, but I'm not very used to any other ways of reducing performance hits. Haven't done any test on memory. I don't know how to do it. – f.rodrigues Jun 25 '14 at 10:20
• You should start by profiling to determine where exactly the time is being taken: see the profile module. You can also do memory profiling, although not from the standard library; see e.g. memory_profiler. – jonrsharpe Jun 25 '14 at 10:25
• As a side note: Your code doesn't follow PEP 8. You can use pep8.py (and autopep8.py), which is also included in PyDev, to check where you don't conform. – Joschua Jun 25 '14 at 15:09
• Sorry about that. I removed the commented out remove_to_fit method but had forgot to remove when I I was calling. It's working now. – f.rodrigues Jun 26 '14 at 13:12

One thing you should do is not place code you always want run at the lowest level in the file, you should place it in a function called main() and call main() with if __name__ == "__main__":. This will help you when you start creating modules and importing them, and is discussed here.