Sunday, April 30, 2017

Genetic algorithms


#!/usr/bin/env python

import numpy as np
import time, random

class GeneticALG():
    def __init__(self, chromosome_size, genetic_base, population_size, fitness_test, crossover=0.7, mutation=0.001, elite_pool=0.10):
        self.chromosome_size = chromosome_size
        self.genetic_base    = genetic_base
        self.crossover       = crossover
        self.mutation        = mutation
        self.elite_pool      = elite_pool
        self.population_size = population_size
        self.fitness_test    = fitness_test
        self.population      = list()
        self.generation      = 0
        np.random.seed([int(time.time() * 1e9) % 4294967296])
        random.seed(time.time())
        for i in xrange(population_size):
            self.population.append([
                np.random.choice([x for x in xrange(genetic_base)], size=(chromosome_size,)),
                0
             ])
    
    
    def test_fitness(self):
        # test fitness
        for c in self.population:
            c[1] = self.fitness_test(c[0])
    
    def breed(self):
        # choose two mates
        op = sorted(self.population, key=lambda x: x[1], reverse=True)
        for i in xrange(int(self.population_size * self.crossover)):
            male   = random.randint(0, self.population_size - 1)
            female = random.choice(op[:int(self.population_size * self.elite_pool)])
            splice = random.randint(0, self.chromosome_size - 1)
            
            for p in xrange(self.chromosome_size - splice):
                index = p + splice
                self.population[male][0][index] = female[0][index]
        
        # mutate
        for i in xrange(int(self.population_size * self.mutation)):
            cancer   = random.randint(0, self.chromosome_size - 1)
            victim   = random.randint(0, self.population_size - 1)
            self.population[victim][0][cancer] = random.randint(0, self.genetic_base)
                    
        # test fitness
        self.test_fitness()
        self.generation += 1

if __name__ == "__main__":
    from numpy import array_equal
    def fitness(x):
        r = 0
        if x[0] == 3:
            r += 1
        if x[1] == 2:
            r += 1
        if x[2] == 1:
            r += 1
        if x[3] == 1:
            r += 1
        if x[4] == 2:
            r += 1
        if x[5] == 3:
            r += 1
        if x[6] == 4:
            r += 1
        if x[7] == 5:
            r += 1
        if x[8] == 6:
            r += 1
        if x[9] == 7:
            r += 1
        
        
        if np.array_equal(x, np.array([3,2,1,1,2,3,4,5,6,7,8,9])):
            print "[!] YAY, only %i generations" % species.generation
            exit(0)
        return r
        
    species = GeneticALG(12, 10, 5000, fitness, elite_pool=0.60)
    
    print "[*] Starting population generated:"
    print "[*] Running until solution is found"
    
    while True:
        species.breed()