Was ist grammatikalische Evolution + einfache Implementierung

    Zuletzt schrieb ich einen Artikel, in dem ohne Erklärung gezeigt wurde, wozu die grammatische Evolutionsmethode in der Lage ist. Ich stimme vollkommen zu, dass dies nicht möglich ist, aber ich wollte die Ergebnisse einer interessanten Methode zeigen. Ich dachte: "Was wird besser sein: Übersetzen Sie die Quelle oder geben Sie Ihre eigene Erklärung." Faulheit herrschte.

    Wenn sich jemand für evolutionäre Methoden und die Aufgabe der symbolischen Regression interessiert (und nicht nur), dann lesen Sie bitte.

    Bakus-Naur-Form



    Zunächst muss gesagt werden, welche kontextunabhängige Grammatik in Form von Bakus-Naur (kurz BNF) vorliegt. Über formale Sprachen und Grammatiken auf Habré gibt es bereits einen interessanten Artikel . Sehr zu empfehlen zu lesen. Unser Ziel ist es jedoch zu verstehen, was BPF ist, und zu lernen, wie man dieses Formular verwendet.

    Wikipedia gibt eine völlig angemessene Definition:
    BNF ist ein formales Syntaxbeschreibungssystem, in dem einige syntaktische Kategorien nacheinander durch andere Kategorien definiert werden. BNF wird verwendet, um kontextfreie formale Grammatiken zu beschreiben.

    BNF hat terminale und nicht terminale Symbole. Terminals sind Konstanten. Wir haben sie eingerichtet und das wars auch schon, aber mit Nichtterminalsymbolen ist alles viel interessanter: Sie können nach den Regeln ineinander ausgetauscht werden.

    Betrachten Sie ein Beispiel. Wir haben das folgende formale System zur Beschreibung der Syntax der kontextfreien Grammatik:

    <sntnce> :: = <sntnce> |  <Nomen><Verb> |  <Adverb><Verb>

    <Nomen> :: = Peter \, |  Ball

    <verb> :: = lief \, | \, fiel

    <Adverb> :: = schnell

    In unserem Beispiel viele nicht terminale Zeichen

    N = \ {<sntnce>, <noun>, <verb>, <adverb> \}.

    Viele Terminalsymbole werden wie folgt dargestellt

    T = \ {Peter, \, Ball, \, schnell, \, rannte, \, fiel \}

    Die Menge S enthält ein Element.

    S = \ {<sntnce> \}

    Dieses Element ist der Einstiegspunkt für das Erstellen und Arbeiten mit den Regeln.

    Mit einem nichtterminalen Element können wir nun Konstruktionen erstellen, die unserer Grammatik entsprechen.

    Wir folgen den Ketten

    1) => => schnell => lief schnell

    2) => => Peter => Peter ist gefallen

    Es stellt sich die Frage, auf welcher Basis diese Substitutionen stattfinden. Ich werde diese Frage etwas später beantworten.

    Genetischer Algorithmus



    Es scheint mir, dass dieser Algorithmus in evolutionären Kreisen kanonisch ist. Es ist einfach zu implementieren und funktioniert gut. Die Berücksichtigung dieses Algorithmus ist notwendig, um zu verstehen, welche Art von Mechanismus als „Motor“ in der Methode der grammatikalischen Evolution fungiert. Aber (!!) an seiner Stelle kann jeder andere für Sie geeignete Evolutionsalgorithmus sein.

    Also nutzt GA das Verhalten der Natur. Tatsächlich wurde nichts Neues erfunden. Dieser Algorithmus läuft seit Millionen von Jahren. Danke an ihn. Immerhin, wenn nicht für ihn, dann wären wir nicht gewesen.

    GA besteht aus mehreren Stufen.

    (1) Erstellung einer Anfangspopulation (wir erstellen ein Chromosom für jedes Individuum)

    (2) Berechnung der Fitnessfunktion für jedes Individuum (es zeigt genau, wer für diese Population am besten geeignet ist)

    (3) Auswahl der besten Vertreter für die Bildung weiterer Nachkommen

    (4) Kreuzung

    (5) Mutation

    (6) Nach (4) bekommen wir Kinder, von denen einige durchlaufen (5). Am Ausgang erhalten wir Nachkommen

    (7) Die Auswahl der Väter und Kinder in einer neuen Generation

    (8) kehren zu Schritt (2) zurück, wenn die Werte, die uns die Kinder geben, mit dem

    Chromosom nicht zufrieden sind - eine codierte Darstellung der benötigten Informationen. Die primäre Quelle verwendet eine binäre Darstellung. Das heißt Wenn wir 4 Parameter finden müssen (jeder von ihnen liegt im Bereich von 0 bis 15), benötigen wir für jeden Parameter 4 Bits (null oder eins). Und das Chromosom selbst wird eine Länge von 16 haben. Alles ist ziemlich primitiv.

    Wichtig : Sie können eine Dezimaldarstellung verwenden. Ich werde dies für die grammatikalische Evolution tun.

    Jetzt ein wenig über die Betreiber in GA und allerlei Fitnessfunktionen.

    Fitnessfunktion - Funktionalität, die wir optimieren müssen. Es variiert von Aufgabe zu Aufgabe. Wenn es darum geht, die Funktionalität zu minimieren, werden Eltern mit möglichst geringer Fitnessfunktion für die Auswahl benötigt.

    Crossover ist eine coole Sache. Übrigens, in der genetischen Programmierung ist dieser Operator fast der einzige, der Nachkommen mit den besten Eigenschaften hervorbringt. Das Fazit ist, dass wir zwei Eltern nehmen (oder vielmehr ihren Genotyp). Teilen Sie es in zwei Hälften. Und tauschen. Ich werde es dir jetzt zeigen.

    Es gibt zwei Listen:

    first \, parent = [1,2,3,4, -5, -6, -7, -8,]

    Zweiter \, Elternteil = [-1, -2, -3, -4,5,6,7,8]

    Ergebnis:

    Kind \, 1 = [1,2,3,4,5,6,7,8]

    Kind \, 2 = [-1, -2, -3, -4, -5, -6, -7, -8]

    Dies war ein Beispiel für eine Punktüberschneidung. Es gibt andere Variationen zu diesem Thema, aber wir werden nicht darüber sprechen.

    Mutation ist der Vorgang, bei dem ein bestimmtes Gen versehentlich ersetzt wird.

    war = [1,2,3,4]

    be = [1, -5,3,4]

    Eine häufig angewandte Auswahlmethode für eine neue Generation ist elitär. Wir nehmen nur die n besten Personen aus der Liste der Kinder + Eltern. Und dann ergänzen wir die Bevölkerung nach dem Zufallsprinzip auf die richtige Menge.

    Wichtig: Die Größe des Chromosoms kann entweder fest oder willkürlich sein. Gleiches gilt für die Bevölkerungszahl.

    Grammatische Evolution



    Und nun zum Wichtigsten. Was für eine Methode ist das und womit isst es?
    Im Endeffekt müssen Sie ein Problem lösen. Sie bauen eine Grammatik in Form von Bakus-Naur auf. Erstellen Sie eine Anfangspopulation, in der jedes Individuum sein eigenes Chromosom hat, das beschreibt, welche Regeln wann wo zu ersetzen sind. Die Bedeutung ist, dass Sie dank dieser Regeln eine Funktion erhalten, die Sie für Berechnungen verwenden können. Der Wert dieser Funktion mit den vordefinierten (oder nicht substituierten) Parametern kann als funktionale Funktion (Fitnessfunktion) fungieren. Je besser die Funktion, desto besser die Funktion und damit das Individuum mit seinem Chromosom.

    Mehr zum Chromosom.

    Lassen Sie uns die folgende Grammatik haben

    :: = |

    :: = x | 3 | 2

    :: = + | - | * | /

    Als nächstes haben wir so ein Chromosom

    chromo = [2,1,6,4,5,1]

    Anfänglich enthält die symbolische Darstellung der Funktion ein nicht-terminales Symbol: H = (allgemein).

    Wir nehmen das erste Element aus chromo: 2. Wir überlegen, in wie viele Regeln die Konvertierung erfolgt: 2. Dividiere 2% 2 (modulo !!) = 0. Also statt wir ersetzen . Somit ist H =. Wir werfen einen Deuce aus Chromo raus. Sie wird nicht mehr gebraucht.

    Als nächstes kommt eins. und schau nochmal zu. 1% 2 (Anzahl der Substitutionsregeln) = 1. Also statt wir ersetzen . Wir bekommen H =.

    Wenn Sie diese einfachen Manipulationen weiter ausführen, erhalten Sie eine solche Kette

    <val><op><e> (6 \% 3 = 0) -> x <op><e>

    x <op><e> (4 \% 4 = 0) -> x + <e>

    x + <e> (5 \% 2 = 1) -> x + <val>

    x + <val> (1 \% 3 = 1) -> x + 3

    H = x + 3.

    Dann verwenden wir diese Funktion, um das Funktionale zu berechnen und zu bestimmen, wie gut ein Individuum mit einem bestimmten Phänotyp (wie die Funktion genannt wird) und Genotyp (Chromosom) zu uns passt.

    Das ist alles. Ja, es gibt verschiedene Möglichkeiten der Substitution: in der Tiefe (berücksichtigt), in der Breite, die sogenannte \ piSubstitution. Dies ist jedoch Material für einen separaten Artikel.

    Und jetzt ein Beispiel.

    Es gibt ein Zeitintervall t \ in [-5,5]. Es gibt eine Funktion y (x) = 1 + x + x ^ 2 + x ^ 3. Wir müssen eine Funktion finden, die den kleinsten quadratischen Fehler ergibt - die Funktion dieses Problems.

    Schauen wir uns den Code des

    Hauptmoduls an
    # -*- coding: utf-8 -*-
    import GE
    def foo(x):
      return 1+x+x**2+x**3
    interval = [-5, 5]
    values =[foo(e) for e in range(interval[0], interval[1])]
    if __name__ == "__main__":
      result = GE.GA(
        chromo_len=12,
        pop_len=100,
        count=20
      )[0]
      print(result)
    

    Die Funktion foo generiert Werte, die wir mit denen vergleichen, die aus den von jedem einzelnen erstellten Funktionen erhalten werden.

    Chromosomenlänge = 15;

    Bevölkerungslänge = 100;

    Die Anzahl der Iterationen (Evolutionen) = 20;

    Parser-Modul
    # -*- coding: utf-8 -*-
    import random
    import re
    def rand(num):
        return int(random.random()*num)
    def parse(chromo):
      l = len(chromo)
      j = 0
      h = ""
      grammar = {
        "": ["", ""],
        "": ["+", "-", "*", "/"],
        "": ["x", "1"]
      }
      s = r"<+["+('|'.join(list(map(lambda x: x[1:-1], grammar.keys()))))+"]+>"
      pattern = re.compile(s)
      while j < l:
        elems = pattern.findall(h)
        if not elems:
          break
        el = elems[0]
        h = h.replace(el, grammar[el][(chromo[j] % int(len(grammar[el])))], 1)
        j += 1
      while True:
        elems = pattern.findall(h)
        if elems:
          for elem in elems:
            el = elem
            if elem == "":
              el = ""
            h = h.replace(elem, grammar[el][rand(len(grammar[el]))], 1)
        else:
          break
      return h
    

    Das Grammatikwörterbuch enthält Regeln für die Grammatik. Weiter der Substitutionsalgorithmus, den ich oben beschrieben habe. Nach dem Block wird While benötigt, um die Funktion abzuschließen. Es gibt Zeiten, in denen das Chromosom fertig ist, aber nicht terminale Symbole verbleiben. Hier ist der letzte Zyklus und wird benötigt, um alle Nicht-Terminals durch Terminals zu ersetzen.
    Wichtig : Es ist keine Tatsache, dass die endgültige Funktion unter semantischen Gesichtspunkten gültig ist (sie kann durch Null und so weiter dividiert werden).


    GE-Modul
    # -*- coding: utf-8 -*-
    import random
    import math
    from parser import parse
    def rand(num):
      return int(random.random() * num)
    class Individ:
      def __init__(self, genotype):
        self.genotype = genotype
        self.phenotype = self.get_phenotype()
        self.fitness = self.get_mistake()
      def __eq__(self, other):
        return self.fitness == other.fitness
      def __ne__(self, other):
         return not self.__eq__(other)
      def __lt__(self, other):
        return self.fitness < other.fitness
      def __ge__(self, other):
        return not self.__lt__(other)
      def __str__(self):
        return "chromosome : {0}\nphenotype = {2}\nfitness = {1}\n".format(self.genotype, self.fitness, self.phenotype)
      def get_phenotype(self):
        return parse(self.genotype)
      def get_mistake(self):
        import main
        intr = main.interval
        vals = main.values
        f = eval("lambda x: {0}".format(self.phenotype))
        f_vals = []
        for i in range(intr[0], intr[1]):
          try:
            f_vals.append(f(i))
          except:
            return 10000
        return sum(list(map(lambda e: (e[0] - e[1]) ** 2, list(zip(vals, f_vals)))))
    def GA(chromo_len, pop_len, count):
      population = get_population(pop_len, chromo_len)
      while count > 0:
        childrn_chromos = get_children_chromose(population)
        mutation(childrn_chromos, 0.8)
        children = get_children(childrn_chromos)
        population = get_new_population(population, children)
        count -= 1
      return population
    def get_genotype(gen_length):
      return [rand(200) for _ in range(gen_length)]
    def get_population(length, chromo_len):
      return [Individ(get_genotype(chromo_len)) for _ in range(length)]
    def get_children_chromose(parents):
      def tournament():
        return [min([parents[rand(len(parents)-1)] for _1 in range(7)]) for _2 in range(2)]
      children_chromo = []
      for _3 in range(int(len(parents)/2)):
        children_chromo += crossover(tournament())
      return children_chromo
    def get_children(childrn_chromos):
      return [Individ(childrn_chromos[i]) for i in range(len(childrn_chromos))]
    def crossover(pair):
      p1 = pair[0]
      p2 = pair[1]
      d = random.randint(1, len(p1.genotype) - 2)
      return [p1.genotype[:d] + p2.genotype[d:], p2.genotype[:d] + p1.genotype[d:]]
    def mutation(chldrn_chromo, p):
      for j in range(len(chldrn_chromo)):
        if p > random.random():
          i = random.randint(1, len(chldrn_chromo[j]) - 1)
          chldrn_chromo[j][i] = rand(200)
      return chldrn_chromo
    def get_new_population(population, children):
      l = len(population)
      buf = population+children
      buf.sort()
      c = math.trunc(0.2*l)
      new_population = buf[:c]
      tmp = buf[c:]
      ll = len(tmp)
      new_population += [tmp[random.randint(1, ll - 1)] for _ in range(c, l)]
      return new_population
    

    Die übliche Implementierung eines genetischen Algorithmus.

    Die GA-Funktion ist ein Einstiegspunkt in den Evolutionszyklus.

    Im Allgemeinen sprechen die Funktionen für sich selbst, und die Implementierung jeder Funktion ist nicht sehr lang. Ich stelle fest, dass die Auswahl für die Frequenzweiche nicht Standard ist. Ich störe nur meine Eltern und wähle die erste Hälfte des gemischten Stapels. Dies ist für diese Aufgabe nicht sehr schädlich, aber es ist besser, dies nicht zu tun. Es gibt ein Dutzend (oder noch mehr) Methoden, mit denen Sie die besten Kandidaten für die Frequenzweiche auswählen können.

    Jedes Individuum hat drei Felder: Genotyp, Phänotyp, Fitnessfunktionswert.

    Dadurch

    bekomme ich die Funktion

    x + x / 1 * x + x * x * 1 * x + 1/1


    das ist identisch

    1+ x + x ^ 2 + x ^ 3


    Ich stelle fest, dass das Erstellen einer optimalen Grammatik eine nicht triviale und sehr wichtige Aufgabe ist.

    Ich hoffe, dass jetzt klar geworden ist, was für eine Art „grammatikalische Evolution“ diese Methode ist und wie sie zur Lösung von Problemen eingesetzt werden kann. Interessant ist, dass die symbolische Regression nicht nur für Funktionen gilt. Wir können Anweisungen für Roboter erstellen, die Struktur eines neuronalen Netzwerks aufbauen und Parameter darin konfigurieren. Wir brauchen nicht länger die Methode der Rückübertragung des Fehlers, um das Netzwerk zu trainieren. Zusammen damit kann man mit einer kontinuierlichen ersten Ableitung auch die Aktivierungsfunktionen aufgeben. Dies ist die sogenannte "neuroevolutionäre Programmierung".

    Ich gebe noch einmal einen Link zur Quelle . Wenn jemand die Methode tiefer verstehen will.

    Jetzt auch beliebt: