In [44]:
import random
In [45]:
def randomChromosome(length):
"""Generisi string duzine 'length' koji se sastoji od nasumicno odabranih slova iz skupa {A, T, G, C} """
return ''.join([ random.choice(['A', 'T', 'G', 'C']) for i in range(length) ])
2. Korak: Ukrštanje¶
In [46]:
def crossover(father, mother):
"""Ukrsti dvije jedinke, dobijajuci dva potomka"""
point = random.randint(1, len(father) - 1)
return (father[:point] + mother[point:], mother[:point] + father[point:])
3. Korak: Mutacija¶
In [47]:
def mutate(chromosome):
"""Mutiraj jedinku, stavljajuci jedno od slova iz skupa {A, T, G, C} na slucajno odabranu poziciju"""
point = random.randint(1, len(chromosome) - 1)
return chromosome[:point] + random.choice(['A', 'T', 'G', 'C']) + chromosome[point + 1:]
4. Korak: Prilagođenost¶
In [48]:
def fitness(chromosome):
"""Racuna prilagodjenost jedinke. Za nas zadatak, nek to bude broj ponavljanja stringa ATG """
# Iako to zavisi od metoda selekcije (sledeci korak), fitness 0 obicno znaci da ova jedinka
# nikad nece biti izabrana. Obicno nije lose da joj se da sansa, ko zna... (odatle +1)
return chromosome.count("ATG") + 1
5. Selekcija¶
In [49]:
def tournamentSelection(population, k = 2):
"""Nasumicno bira 'k' jedinki iz populacije i vraca onu sa najboljim fitnessom"""
# key argument funkcije max predstavlja drugu funkciju koja ce reci po cemu se porede (u nasem slucaju po fitnessu)
return max([random.choice(population) for i in range(k)], key = lambda c: fitness(c))
6. Generisanje nove generacije¶
In [50]:
def epoch(population, mutationRate = 0.05):
"""Pravimo novu populaciju, tako sto iz postojece biramo najbolje jednike, ukrstamo ih, mutiramo i nadamo se najboljem"""
nextGeneration = []
for i in range(len(population) // 2):
father, mother = tournamentSelection(population), tournamentSelection(population)
son, daughter = crossover(father, mother)
if random.random() < mutationRate: son = mutate(son)
if random.random() < mutationRate: daughter = mutate(daughter)
nextGeneration += [son, daughter]
return nextGeneration
7. Da vidimo ko je najbolji...¶
In [51]:
population = [randomChromosome(20) for i in range(100)]
for i in range(1000):
population = epoch(population)
max(population, key = lambda c: fitness(c))
Out[51]:
 |
 |
 |
 |
 |
 |
 |
