Genetski algoritam

1. Korak: Random jedinke

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]:
'ATGATGATGAATGCATGATG'

Index