Das deutsche Python-Forum

Code: Alles auswählen

#! /usr/bin/python
# -*- coding: utf-8 -*-

#Erstes Programm zur Genetischen Programmierung
from string import uppercase
from random import random

TARGET     = "DUHASTESGESCHAFFT"
LETTERS    = uppercase
POPULATION = 200
p_dict     = {}
c_dict	   = {}
fittness   = {}
list_pop   = []
count      = 0
generation = 1
mother     = 0
father     = 0
ERB_VALUE  = 0.40
MUT_VALUE  = 0.45
stri       = ""
cache      = ""
cache2     = ""

#Parent-Generation erstellen
for i in range(POPULATION):
    for c in range(len(TARGET)):
        stri += LETTERS[int(random() * 26)]
    p_dict[i] = stri
    stri = ""

while True:
    #Fitness zu der Parent-Generation
    for c in p_dict:
        for i in range(len(TARGET)):
            if p_dict[c][i] == TARGET[i]:
                count += 1
        fittness[c] = count
        count = 0

    #Liste für Zufallsauswahl
    list_pop += p_dict.keys()
    for i in fittness:
        list_pop += list(str(i)) * fittness[i]

    #Child-Generation erstellen
    for i in range(POPULATION):
        mother = int(list_pop[int(random() * len(list_pop))])
        father = int(list_pop[int(random() * len(list_pop))])
        cache  = p_dict[mother]
        cache2 = p_dict[father]
        if random() > 0.5:
            c_dict[i] = cache[0:int(ERB_VALUE * len(TARGET))] + cache2[int(ERB_VALUE * len(TARGET)):]
        elif random() < 0.5:
            c_dict[i] = cache2[0:int(ERB_VALUE * len(p_dict[father]))] + cache[int(ERB_VALUE * len(p_dict[mother])):]

    #Mutationen
    for c in c_dict:
        for s in range(len(c_dict[c])):
            if random() > MUT_VALUE:
                c_dict[c] = c_dict[c][:s - 1] + LETTERS[int(random() * 26)] + c_dict[c][s:]
            if c_dict[c] == TARGET:
                print "Lösung gefunden in der %dten Generation: %s" % (generation, c_dict[c])
                break

    generation += 1
    p_dict      = c_dict
    c_dict      = {}

print "End"

Code: Alles auswählen

    
for i in range(POPULATION):
        mother = int(list_pop[int(random() * len(list_pop))])
        father = int(list_pop[int(random() * len(list_pop))])
        cache  = p_dict[mother]                            #Dieser Umweg muss nicht genommen werden, wollte aber gucken, ob da der Fehler liegt.
        cache2 = p_dict[father]
        if random() > 0.5:
            c_dict[i] = cache[0:int(ERB_VALUE * len(TARGET))] + cache2[int(ERB_VALUE * len(TARGET)):]
        elif random() < 0.5:
            c_dict[i] = cache2[0:int(ERB_VALUE * len(p_dict[father]))] + cache[int(ERB_VALUE * len(p_dict[mother])):]

Code: Alles auswählen

#!/usr/bin/env python
from __future__ import absolute_import, division, print_function
from bisect import bisect
from functools import partial
from itertools import imap, izip
from random import choice, random, randrange
from string import ascii_uppercase as LETTERS


random_gene = partial(choice, LETTERS)


def fitness(target, chromosome):
    return sum(t == c for t, c in izip(target, chromosome))


def iter_generations(
    target, population_size, crossover_probability, mutation_rate, copy_count=2
):
    fitness_for_target = partial(fitness, target)
    chromosomes = [
        ''.join(random_gene() for _ in xrange(len(target)))
        for _ in xrange(population_size)
    ]

    while True:
        chromosomes.sort(key=fitness_for_target, reverse=True)
        yield chromosomes

        next_generation = chromosomes[:copy_count]

        cumulative_fitness = list()
        running_weight = 0
        for weight in imap(fitness_for_target, chromosomes):
            running_weight += weight
            cumulative_fitness.append(running_weight)

        for _ in xrange((population_size - len(next_generation)) // 2):
            parent_indices = set()
            while len(parent_indices) < 2:
                parent_indices.add(
                    bisect(
                        cumulative_fitness, random() * cumulative_fitness[-1]
                    )
                )
            child_a, child_b = (chromosomes[i] for i in parent_indices)

            if random() <= crossover_probability:
                cutpoint = randrange(len(target))
                child_a, child_b = (
                    child_a[:cutpoint] + child_b[cutpoint:],
                    child_b[:cutpoint] + child_a[cutpoint:]
                )

            next_generation.extend(
                ''.join(
                    (random_gene() if random() <= mutation_rate else gene)
                    for gene in chromosome
                )
                for chromosome in [child_a, child_b]
            )

        chromosomes = next_generation


def main():
    target = 'INTELLIGENTLYDESIGNED'
    generations = iter_generations(target, 500, 0.65, 0.035)
    for i, chromosomes in enumerate(generations):
        fittest_chromosome = chromosomes[0]
        print('Gen {0:>4d}: {1}'.format(i, fittest_chromosome))
        if fittest_chromosome == target:
            break


if __name__ == '__main__':
    main()

Code: Alles auswählen

#!/usr/bin/env python
from __future__ import absolute_import, division, print_function
from bisect import bisect
from functools import partial
from itertools import izip
from random import choice, random, randrange
from string import ascii_uppercase as LETTERS


random_gene = partial(choice, LETTERS)


class Chromosome(object):

    def __init__(self, genes, target=None):
        self.genes = genes
        self.target = genes if target is None else target
        assert len(self.genes) == len(self.target)
        self.fitness = sum(t == c for t, c in izip(self.target, self))

    def __str__(self):
        return '{0.genes} ({0.fitness}/{1})'.format(self, len(self.target))

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

    def __iter__(self):
        return iter(self.genes)

    def __cmp__(self, other):
        return cmp((self.fitness, self.genes), (other.fitness, other.genes))

    def crossover(self, other):
        cutpoint = randrange(len(self))
        return [
            Chromosome(
                self.genes[:cutpoint] + other.genes[cutpoint:], self.target
            ),
            Chromosome(
                other.genes[:cutpoint] + self.genes[cutpoint:], self.target
            ),
        ]

    def mutated(self, rate):
        return Chromosome(
            ''.join(
                (random_gene() if random() <= rate else gene) for gene in self
            ),
            self.target
        )

    @classmethod
    def random(cls, target):
        return cls(''.join(random_gene() for _ in xrange(len(target))), target)


class Chromosomes(object):

    def __init__(self, chromosomes):
        self.chromosomes = sorted(chromosomes, reverse=True)
        self.cumulative_fitness = list()
        running_weight = 0
        for chromosome in self:
            running_weight += chromosome.fitness
            self.cumulative_fitness.append(running_weight)

    def __getitem__(self, index):
        return self.chromosomes[index]

    def get_n_fittest(self, count):
        return self[:count]

    def get_random_parents(self):
        parent_indices = set()
        while len(parent_indices) < 2:
            parent_indices.add(
                bisect(
                    self.cumulative_fitness,
                    random() * self.cumulative_fitness[-1]
                )
            )
        return (self[i] for i in parent_indices)

    @classmethod
    def random(cls, population_size, target):
        return cls(Chromosome.random(target) for _ in xrange(population_size))


def iter_generations(
    target, population_size, crossover_probability, mutation_rate, copy_count=2
):
    chromosomes = Chromosomes.random(population_size, target)

    while True:
        yield chromosomes

        next_generation = chromosomes.get_n_fittest(copy_count)

        for _ in xrange((population_size - len(next_generation)) // 2):
            
            child_a, child_b = chromosomes.get_random_parents()

            if random() <= crossover_probability:
                child_a, child_b = child_a.crossover(child_b)

            next_generation.extend(
                chromosome.mutated(mutation_rate)
                for chromosome in [child_a, child_b]
            )

        chromosomes = Chromosomes(next_generation)


def main():
    target = Chromosome('INTELLIGENTLYDESIGNED')
    generations = iter_generations(target, 500, 0.65, 0.035)
    for i, chromosomes in enumerate(generations):
        fittest_chromosome = chromosomes[0]
        print('Gen {0:>4d}: {1}'.format(i, fittest_chromosome))
        if fittest_chromosome == target:
            break


if __name__ == '__main__':
    main()