Einfaches Beispiel für die Minimierung genetischer Algen

7

Ich habe eine Weile nach Beispielen gesucht, wie ich mithilfe eines genetischen Algorithmus in Python die Punkte finden kann, an denen eine Funktion ihr Minimum erreicht. Ich habe mir die DEAP-Dokumentation angesehen, aber die Beispiele dort waren für mich ziemlich schwer zu befolgen. Zum Beispiel:

def  function(x,y):
     return x*y+3*x-x**2

Ich suche nach Referenzen, wie ich einen genetischen Algorithmus erstellen kann, mit dem ich einige anfängliche Zufallswerte für x und y eingeben kann (die nicht aus denselben Dimensionen stammen). Kann mir jemand mit Erfahrung in der Erstellung und Verwendung genetischer Algorithmen eine Anleitung dazu geben?

gm1
quelle
2
Dieses Problem ist mithilfe von Kalkül analytisch lösbar und erfordert kein statistisches Lernen. Angenommen, Sie möchten eine numerische Lösung, die mit stochastischem Gradientenabstieg leichter lösbar ist als mit einem genetischen Algorithmus. Beachten Sie außerdem, dass Sie eine Funktion definiert haben, die in y linear ist und der am schnellsten skalierende x-Term wie -x ^ 2 lautet. Für die meisten Parameterregime ist die Lösung daher uninteressant (xmax, ymin). Ich schlage vor, etwas mehr Zeit damit zu verbringen, ein aussagekräftigeres Beispiel zu finden und zwischen SGD und GA zu entscheiden. Hier ist ein echtes genetisches Algorithmusbeispiel
AN6U5
Hallo, in der Tat ist es nur ein Beispiel. In der Praxis ist meine Funktion eine Kombination aus 2 verschachtelten Funktionen, in denen ich nicht einmal einen Hessischen habe.
gm1
Aber sehen Sie die Beziehung zwischen stochastischem Gradientenabstieg und genetischen Algorithmen? Und dass das von Ihnen angegebene Beispiel so simpel ist, dass es keinen Unterschied zwischen den beiden gibt? Ich komme nur darauf an, dass Sie ein komplexeres Beispiel benötigen, um die Unterschiede zu beseitigen und letztere besser zu verstehen.
AN6U5
Ich suchte nach einem Beispiel, in dem ein triviales Beispiel wie das oben beschriebene beschrieben wird, um es zu verallgemeinern.
gm1

Antworten:

6

Hier ist ein triviales Beispiel , das die Essenz genetischer Algorithmen aussagekräftiger erfasst als das von Ihnen bereitgestellte Polynom. Das von Ihnen angegebene Polynom ist über lösbar stochastic gradient descent, was eine einfachere Minimierungstechnik darstellt. Aus diesem Grund schlage ich stattdessen diesen ausgezeichneten Artikel und das Beispiel von Will Larson vor.

Zitiert aus dem Originalartikel :

Definieren eines zu optimierenden Problems Nun werden wir ein einfaches Beispiel für die Verwendung eines genetischen Algorithmus in Python zusammenstellen. Wir werden ein sehr einfaches Problem optimieren: versuchen, eine Liste von N Zahlen zu erstellen, die zusammen X entsprechen.

Wenn wir N = 5 und X = 200 setzen, wären dies alles geeignete Lösungen.

lst = [40,40,40,40,40]
lst = [50,50,50,25,25]
lst = [200,0,0,0,0]

Schauen Sie sich den gesamten Artikel an , aber hier ist der vollständige Code :

# Example usage
from genetic import *
target = 371
p_count = 100
i_length = 6
i_min = 0
i_max = 100
p = population(p_count, i_length, i_min, i_max)
fitness_history = [grade(p, target),]
for i in xrange(100):
    p = evolve(p, target)
    fitness_history.append(grade(p, target))

for datum in fitness_history:
   print datum
"""
from random import randint, random
from operator import add

def individual(length, min, max):
    'Create a member of the population.'
    return [ randint(min,max) for x in xrange(length) ]

def population(count, length, min, max):
    """
    Create a number of individuals (i.e. a population).

    count: the number of individuals in the population
    length: the number of values per individual
    min: the minimum possible value in an individual's list of values
    max: the maximum possible value in an individual's list of values

    """
    return [ individual(length, min, max) for x in xrange(count) ]

def fitness(individual, target):
    """
    Determine the fitness of an individual. Higher is better.

    individual: the individual to evaluate
    target: the target number individuals are aiming for
    """
    sum = reduce(add, individual, 0)
    return abs(target-sum)

def grade(pop, target):
    'Find average fitness for a population.'
    summed = reduce(add, (fitness(x, target) for x in pop))
    return summed / (len(pop) * 1.0)

def evolve(pop, target, retain=0.2, random_select=0.05, mutate=0.01):
    graded = [ (fitness(x, target), x) for x in pop]
    graded = [ x[1] for x in sorted(graded)]
    retain_length = int(len(graded)*retain)
    parents = graded[:retain_length]
    # randomly add other individuals to
    # promote genetic diversity
    for individual in graded[retain_length:]:
        if random_select > random():
            parents.append(individual)
    # mutate some individuals
    for individual in parents:
        if mutate > random():
            pos_to_mutate = randint(0, len(individual)-1)
            # this mutation is not ideal, because it
            # restricts the range of possible values,
            # but the function is unaware of the min/max
            # values used to create the individuals,
            individual[pos_to_mutate] = randint(
                min(individual), max(individual))
    # crossover parents to create children
    parents_length = len(parents)
    desired_length = len(pop) - parents_length
    children = []
    while len(children) < desired_length:
        male = randint(0, parents_length-1)
        female = randint(0, parents_length-1)
        if male != female:
            male = parents[male]
            female = parents[female]
            half = len(male) / 2
            child = male[:half] + female[half:]
            children.append(child)
    parents.extend(children)
    return parents

Ich denke, es könnte sehr pädagogisch nützlich sein, auch Ihr ursprüngliches Problem mit diesem Algorithmus zu lösen und dann auch eine Lösung mit stochastic grid searchoder zu konstruieren, stochastic gradient descentund Sie werden ein tiefes Verständnis für das Nebeneinander dieser drei Algorithmen gewinnen.

Hoffe das hilft!

AN6U5
quelle
1
Wie ist SGD eine Teilmenge genetischer Algorithmen? SGD ist nicht bevölkerungsbasiert, verwendet keinen der genetischen Operatoren und genetische Algorithmen verwenden keine gradientenbasierte Optimierung.
Jérémie Clos
1
Hallo ANSU5, ausgezeichnete Referenz, warten Sie nur, um es in die Praxis morgen zu setzen
gm1
@ Jérémie Clos, du bist richtig. Ich habe die Antwort bearbeitet, um dies widerzuspiegeln. Ich war in die obige Diskussion verwickelt und habe versucht, einige Ähnlichkeiten bei verschiedenen Optimierungstechniken zu veranschaulichen. Aber dies ist wahrscheinlich mehr verschleiert als aufgeklärt.
AN6U5