genetics.py

# -*- encoding: utf-8 -*-
"""Genetic algorithm base classes."""
import random
from collections import deque
from itertools import izip
import attr


@attr.s()
class Population(object):
    """This class is the controller for the population of Orgamisms."""

    gene_base = attr.ib(
        validator=attr.validators.instance_of(list), cmp=False, repr=False)
    population_count = attr.ib(default=20)
    population = attr.ib(default=attr.Factory(list), cmp=False)
    top_scores = attr.ib(default=deque(maxlen=200), repr=False)

    def gen_population(self):
        """Generate a population of organisms."""
        self.population = []
        for _ in range(self.population_count):
            org = Organism(genes=self.gene_base[:])
            org.generate_genes()
            self.population.append(org)

    def breed_population(self, pool_percentage=50):
        """"Cross breed the population with only the top percentage.

        :param pool_percentage: Percentage defines primary breeder cutoff.

        """
        # Create the breeding order. Those on top get more iterations.
        self.sort_population()
        breeders = self.population[
            :int(self.population_count * (float(pool_percentage) / 100))
        ]
        self.top_scores.append(breeders[0].points)
        i = 0
        while self.population_count > len(breeders):
            breeders.extend(
                [breeders[i]] * ((self.population_count - len(breeders)) / 2 + 1)
            )
            i += 1

        # Create a shuffled duplicate of the list to breed against
        shuffled = breeders[:]
        random.shuffle(shuffled)
        next_generation = [Organism(genes=breeders[0].genes[:])]  # boldly go!
        for org1, org2 in izip(breeders, shuffled):
            next_generation.append(self._breed_pair(org1, org2))
        self.population = next_generation[:self.population_count - 1]

    def _breed_pair(self, organism1, organism2):
        """Breed two organisms together.

        The first has a greater chance of passing their genes on.
        Random mutation is then given a chance to change the child.

        """
        new_gene_list = []
        gene_list1, gene_list2 = (organism1.genes, organism2.genes)
        for i in range(len(self.gene_base)):
            if random.random() <= 0.75:
                if gene_list1[i] not in new_gene_list:  # avoid duplicates
                    new_gene_list.append(gene_list1[i])
                elif gene_list2[i] not in new_gene_list:
                    new_gene_list.append(gene_list2[i])
            else:
                if gene_list2[i] not in new_gene_list:
                    new_gene_list.append(gene_list2[i])
                elif gene_list1[i] not in new_gene_list:
                    new_gene_list.append(gene_list1[i])

        # Add in any original genes that were removed in the process
        for gene in self.gene_base:
            if gene not in new_gene_list:
                new_gene_list.append(gene)

        org = Organism(genes=new_gene_list)

        # Randomly mutate the organism
        if random.random() <= 0.01:
            org.mutate()
        # If we have reached a local maximum, force some diversity
        if len(self.top_scores) == 200 and self.top_scores[0] == self.top_scores[-1]:
            if random.random() <= 0.9:
                org.generate_genes()
            else:
                org.mutate()

        return org

    def sort_population(self):
        """Sort the population by the number of points they have."""
        self.population = sorted(
            self.population, key=lambda org: org.points, reverse=True)


@attr.s(slots=True)
class Organism(object):
    """The is the actor class that is the target of evolution."""

    genes = attr.ib(validator=attr.validators.instance_of(list), cmp=False)
    points = attr.ib(default=0)

    def generate_genes(self):
        """Randomly sort the genes to provide different combinations."""
        random.shuffle(self.genes)

    def mutate(self):
        """Randomly mutate the list by swapping two genes around."""
        gene1 = random.randint(0, len(self.genes) - 1)
        gene2 = random.randint(0, len(self.genes) - 1)
        self.genes[gene1], self.genes[gene2] = (
            self.genes[gene2], self.genes[gene1])