Exemplo simples de minimização de algas genéticas

7

Há algum tempo, procuro exemplos de como eu poderia encontrar os pontos nos quais uma função atinge o mínimo usando uma abordagem de algoritmo genético em Python. Eu olhei para a documentação do DEAP, mas os exemplos eram muito difíceis de seguir. Por exemplo:

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

Eu estou procurando algumas referências sobre como eu posso criar um algoritmo genético no qual eu possa alimentar alguns valores aleatórios iniciais para xey (não provenientes das mesmas dimensões). Alguém com experiência na criação e uso de algoritmos genéticos pode me dar alguma orientação sobre isso?

gm1
fonte
2
Esse problema é solucionável analiticamente usando cálculo e não requer aprendizado estatístico. Supondo que você queira uma solução numérica, é mais facilmente solucionável usando a descida do gradiente estocástico em vez de um algoritmo genético. Além disso, observe que você definiu uma função que é linear em ye o termo x que escala mais rápido é igual a -x ^ 2; portanto, para a maioria dos regimes de parâmetros, a solução é desinteressante (xmax, ymin). Sugiro que dedique um pouco mais de tempo a encontrar um exemplo mais significativo e decisivo entre SGD e GA. Aqui está um verdadeiro exemplo algoritmo genético
AN6U5
Oi, na verdade, é apenas um exemplo. Na prática, minha função é uma combinação de 2 funções aninhadas nas quais eu nem tenho um hessian.
Gm1
Mas você vê a relação entre a descida do gradiente estocástico e os algoritmos genéticos? E que o exemplo que você forneceu é tão simplista que não há diferença entre os dois? Tudo o que eu entendo é que você precisa de um exemplo mais complexo para ilicitar as diferenças e, portanto, entender melhor as últimas.
AN6U5
Eu estava procurando por um exemplo em que é descrito um exemplo trivial como o exemplo acima para generalizar a partir dele.
Gm1

Respostas:

6

Aqui está um exemplo trivial , que captura a essência dos algoritmos genéticos com mais significado do que o polinômio que você forneceu. O polinômio que você forneceu é stochastic gradient descentpassível de solução , o que é uma técnica de minimização mais simples. Por esse motivo, estou sugerindo este excelente artigo e exemplo de Will Larson.

Citado no artigo original :

Definindo um problema para otimizar Agora, vamos montar um exemplo simples de uso de um algoritmo genético em Python. Vamos otimizar um problema muito simples: tentar criar uma lista de N números iguais a X quando somados.

Se definirmos N = 5 e X = 200, todas essas serão soluções apropriadas.

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

Dê uma olhada no artigo inteiro , mas aqui está o código completo :

# 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

Eu acho que poderia ser bastante pedagogicamente útil também resolver seu problema original usando esse algoritmo e, em seguida, também construir uma solução usando stochastic grid searchor stochastic gradient descente você obterá um entendimento profundo da justaposição desses três algoritmos.

Espero que isto ajude!

AN6U5
fonte
11
Como o SGD é um subconjunto de algoritmos genéticos? O SGD não é baseado em população, não usa nenhum dos operadores genéticos, e algoritmos genéticos não usam otimização baseada em gradiente.
Jérémie Clos 5/16
11
Oi ANSU5, excelente referência, apenas espere para colocá-lo em prática amanhã
gm1
@ Jérémie Clos, você está correto. Eu editei a resposta para refletir isso. Fui pego na discussão acima e estava tentando ilustrar algumas semelhanças em várias técnicas de otimização. Mas isso provavelmente ofuscou mais do que elucidou.
AN6U5