Dictionary löscht Daten

[TheNew3000]

Hallo,
Ich wollte den Algorithmus von http://scienceblogs.de/diaxs-rake/2010/ ... in-python/ selber programmieren und habe folgendes geschrieben:

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"

Nun habe ich jedoch das Problem, dass ein KeyError ausgegeben wird.
Bis jetzt weiß ich nur, dass nach ein paar Runden die die For-Schleife gemacht hat, ein Eintrag in dem Dictionary gelöscht wird.

Soweit ich weiß, ist die Anzahl dieser Runden immer unterschiedlich.
Sieht da jemand einen Fehler?

Schonmal Danke im vorraus.

[BlackJack]

@TheNew3000: Ich glaube ich bin nicht der einzige der keine Lust hat irgendwo in 70 Zeilen nach einem Fehler zu suchen. Woher weisst Du das da Daten *gelöscht* werden? Welcher Schlüssel ist das der nicht gefunden wird und erkläre mal warum Du sicher bist, dass der überhaupt jemals vorhanden war!?

Noch ein kleiner Tipp: Im `random`-Modul gibt es nicht nur die `random()`-Funktion.

[TheNew3000]

Erstmal Danke für die schnelle Antwort.

Ich meinte das Dictionary p_dict, welches die Parent-Generation beinhält.

Ich weiß, dass es bei folgendem Code passiert:

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])):]

Herausgefunden habe ich das, indem ich den generierten p_dict direkt nach der Generierung in eine andere Variable verschoben habe und dann immer verglichen habe.

Falls noch etwas unklar ist, bitte sagen, bin noch relativ neu was das Programmieren in Python angeht

[BlackJack]

@TheNew3000: Wie genau hast Du herausgefunden das Werte gelöscht werden. Ich sehe das hier nämlich nirgends. Warum sollten die Werte die Du abfragst vorhanden sein? Da sind ja *Zufallswerte* beteiligt bei dem was da letztendlich gespeichert wird.

Beschreib mal in Worten was in den Zeilen 7 bis 10 passiert. Vielleicht reicht es auch schon wenn Du beschreibst was die beiden ``if``-Bedingungen bedeuten und warum Du einmal ``>`` und einmal ``<`` verwendest. Dir ist klar das `random()` bei *jedem* Aufruf einen *zufälligen* Wert liefert?

[TheNew3000]

@TheNew3000: Wie genau hast Du herausgefunden das Werte gelöscht werden. Ich sehe das hier nämlich nirgends. Warum sollten die Werte die Du abfragst vorhanden sein? Da sind ja *Zufallswerte* beteiligt bei dem was da letztendlich gespeichert wird.

Ich habe bei jedem Durchlauf der Schleife das p_dict mit dem ursprünglichen p_dict.
Nachher ist mir dann aufgefallen, dass zB der Key 6 nicht mehr da war und somit ein KeyError entstand.

Beschreib mal in Worten was in den Zeilen 7 bis 10 passiert. Vielleicht reicht es auch schon wenn Du beschreibst was die beiden ``if``-Bedingungen bedeuten und warum Du einmal ``>`` und einmal ``<`` verwendest. Dir ist klar das `random()` bei *jedem* Aufruf einen *zufälligen* Wert liefert?

Es soll einfach entscheiden, ob die Mutter oder der Vater mehr weitergibt.
Beispiel: random() > 0.5 ---> Mutter 0,4 | Vater 0,6

[BlackJack]

@TheNew3000: Die Zeilen 7 bis 10 solltest Du noch mal *genauer* beschreiben. Nur die beiden ``if``s. Dir ist klar das da nicht entweder der eine oder der andere Zweig genommen wird, sondern es auch passieren kann das *beide* ausgeführt werden und sogar das *keiner* ausgeführt wird‽ Und *dann* würdest Du einen Eintrag verlieren, oder?

[TheNew3000]

Stimmt, danke

Aber das würde doch nicht das Dictionary verändern

EDIT: Gibt bis jetzt keine Fehlermeldung zurück, lädt nur ziemlich langsam, aber ich glaube das ist normal. Danke für die Hilfe

[BlackJack]

@TheNew3000: Was meinst Du mit „das würde doch nicht das Dictionary verändern”? Da fehlt dann ein `i` als Schlüssel in dem Dictionary was sonst da wäre. Und das fehlt Dir im nächsten Schleifendurchlauf dann. Wobei ich mich gerade frage warum das überhaupt Dictionaries sind, Du hast da ja von 0 an aufsteigende, ganze Zahlen als Schlüssel und die Elemente werden auch in dieser Reihenfolge hinzugefügt. Dafür nimmt man Listen und keine Dictionaries. Womit wir bei Namen wären: Solchen Datentypen haben im Namen eigentlich nichts zu suchen, denn wenn man den Typ ändert, muss man auch den Namen überall ändern. Namen sollten aber die *Bedeutung* des Objekts im Programm widerspiegeln und die ändert sich ja nicht wenn man eine Liste daraus macht, somit sollte sich der Name auch nicht ändern müssen.

[BlackJack]

@TheNew3000: Dein Crossover weicht von der Beschreibung in dem Artikel und dem Quelltext dort ab. `ERB_VALUE` bestimmt dort nicht den Anteil von Vater und Mutter in den beiden Kindern sondern die Wahrscheinlichkeit ob ein Crossover stattfindet oder nicht. Der Anteil von Vater und Mutter wird zufällig ausgewählt (`iCutpoint` im Quelltext aus dem Blog).

Ein Versuch den Blogtext in Python umzusetzen:

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()

Wobei die `iter_generations()`-Funktion zu viel macht. Ich würde das ganze im nächsten Schritt auf zwei Klassen `Chromosome` und `Chromosomes` verteilen.

[BlackJack]

Die OOP-Variante:

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()