Programação genética [fechada]

Recentemente, eu estava navegando no Reddit e me deparei com uma postagem com um link para um exemplo de "algoritmo genético JavaScript". Eu realmente fiquei fascinado com os conceitos de algoritmos genéticos e programação, no entanto, mesmo depois de pesquisar no Google, ainda estou um pouco confuso. Como funciona?

Suponho que os termos do vocabulário estejam me confundindo mais do que qualquer outra coisa. Eu apreciaria breves exemplos e talvez explicações. Apenas o conceito de programação genética e como eu poderia implementá-lo em meus projetos e por quê?

Parece que você está falando mais sobre algoritmos genéticos do que sobre programação genética, mas aqui está minha contribuição para sua compreensão.

Pode ser útil pensar nos AGs em termos das partes em que são compostos.

Então, digamos que você tenha algum tipo de problema. A primeira coisa que você precisa é de uma maneira de expressar como será a solução. Se você teve um problema de vendedor ambulante nas cidades A, B, C, D, E, já sabe como seria uma solução, uma matriz de nomes das cidades [B, C, A, D, E].

Este é o gene .

Também conhecido como uma solução potencial para o problema. Como Steven A. Lowe menciona, cadeias de bits são uma maneira comum de codificar genes, mas não é necessário; apenas facilita certas coisas. A parte importante é que você tem uma maneira de representar uma solução dessa maneira semelhante a uma matriz.

Agora. Como você sabe se a solução é boa? Você precisa de uma função que possa lhe dizer e classifique a solução. Então, novamente no TSP, você pode ter uma função que mede a distância percorrida usando o caminho [B, C, A, D, E]. A "nota" que você atribuir pode ser simplesmente a distância percorrida, mas em problemas mais complicados, você pode incluir coisas como o custo da viagem e outras.

Esta é a função de condicionamento físico .

Então agora você pode pegar uma solução em potencial e descobrir se é alguma coisa boa. Qual é o próximo?

Em seguida, precisamos iniciar nossa primeira geração. Então, geramos um monte de soluções aleatórias. Não importa se eles são bons ou não. Essa é sua população inicial ou inicial. Você pode chamar isso de seu pool genético.

Então você toma seu pool genético inicial e aplica sua função de condicionamento físico a todos e atribui uma nota a todos. Agora você precisa pegar dois deles e formar uma nova população deles - para a próxima geração. Quem você seleciona? Bem, você não quer necessariamente selecionar apenas o mais apto, que pode levar a alguns problemas. Em vez disso, você precisa de uma função de seleção .

Uma maneira de selecionar que é fácil de visualizar é usar uma espécie de roda: cada gene é uma fatia de uma roda e sua pontuação de aptidão indica o tamanho da fatia (quanto melhor a aptidão, maior a fatia). Coloque um alfinete apontando para a roda e gire (ou seja, gere um número aleatório). O pino aponta para o primeiro pai. Faça isso novamente para o segundo pai.

Agora, você precisa criar novos filhos. Você quer combinar os pais para produzir uma nova população. Existem várias maneiras de fazer isso, mas todas elas são chamadas de função crossover . Você pode dividi-los ao meio e trocar as metades entre os pais, ou fazer algum tipo de intercalação. Isso é muito análogo aos pais mamíferos que produzem novos filhos - ambos contribuem com seus genes para o novo filho.

Depois de ter essa nova geração, você lança mutações aleatórias, mas raras , para cada criança. Eu tenho visto frequentemente taxas de mutação ocorrerem em menos de 1%. A função de mutação mudará aleatoriamente algo no seu gene codificado. Se o seu gene é uma sequência de bits, ele pode trocar um pouco, se for uma variedade de cidades, ele pode trocar duas cidades na lista. A parte importante é que é uma ocorrência relativamente rara e confunde tudo.

Repita esse processo até um número desejado de gerações ou até que sua função de condicionamento físico produza pais com pontuações consistentemente altas e você tenha uma solução que seja (espero que, se você fez tudo certo) seja ideal.

Isso foi um pouco prolixo, então deixe-me resumir com uma metáfora:

1. Genes são pessoas: pessoas resolvem problemas
2. Funções de condicionamento físico são notas: as pessoas obtêm uma nota com base em quão bem resolvem um problema
3. Você seleciona 2 pessoas para criar uma nova população: você dá às pessoas com melhores notas melhores chances de procriação
4. Quando os pais se reproduzem, eles combinam para produzir filhos.
5. Você raramente e aleatoriamente muda seus filhos
6. Você classifica os filhos da nova população
7. Enxague e repita

Espero que isto ajude.

codificar uma solução para um problema como uma cadeia de bits

escreva uma função (chamada função "fitness") que avalie quão 'boa' é dada à solução codificada uma string de bits - o resultado geralmente é um número entre 0 e 1

gerar aleatoriamente um monte dessas strings de bits e avaliar sua adequação

escolha alguns dos cachos - normalmente os mais adequados - e corte-os ao meio e troque as metades para fazer algumas novas strings de bits (crossover)

às vezes, inverta aleatoriamente alguns bits em algumas das novas strings de bits (mutação)

repita até que uma boa solução evolua

por que fazer isso: alguns problemas têm enormes espaços de solução possíveis, tão grandes que avaliar todas as possibilidades é impraticável (cf. Problema do vendedor ambulante)

Eu recomendo o livro Algoritmos Genéticos em Pesquisa, Otimização e Aprendizado de Máquina

A programação genética é uma maneira de fazer o computador escrever programas para você!

Não pense em "programas" como o MS Word, pense em "programas" da seguinte maneira:

function(x){ return x*2; }

Esta função (ou programa), por si só, não tem um motivo para existir. Estamos à procura de soluções para problemas. Se você precisar encontrar a soma de dois números, basta abrir a calculadora e fazer as contas. E se alguém lhe desse a tabela a seguir e solicitasse que você descobrisse a relação entre resulte xe y:

x   y   result
99  1   (3.02)
79  88   2.01 
21  62   5.01 
84  52  (6.58)
12  70   5.54 
67  18   0.73 

Esses dados são seus dados de "treinamento". Seu computador usará esses dados para gerar algumas hipóteses, e você os testará em relação aos dados reais.

Digamos que você não conheça estatísticas e decida que esse problema é muito difícil de resolver por conta própria, para que você obtenha o computador.

Faça o computador gerar aleatoriamente palpites

Você faz com que o computador gere um milhão de respostas e veja se alguma delas permanece (acho ... um milhão de vezes!). A seguir, é apresentado um exemplo de algumas suposições:

function(x,y){ return x+y; } // wrong
function(x,y){ return x/1*1*1*1*1*1+y; } //wrong, silly

Você pode ou não saber disso, mas funções ou programas também podem ser representados como árvores, por exemplo, a segunda função seria:

(+ (/ x (* 1 (* 1 (* 1 (* 1 (* 1 1)))) y)

Você pode fazer com que pareça mais com uma árvore recuando-a assim (veja a notação polonês reversa e a sintaxe lisp ... mas você entenderá por que representamos programas como esse em breve):

(+ 
    (/ x 
        (* 1 
            (* 1 
                (* 1 
                    (* 1 
                        (* 1 1)))) 
    y)

( +está no topo com duas "folhas" de /e y. /tem vários filhos etc.)

É por isso que você lê muito sobre "árvores" na programação genética. Em qualquer caso, nós ligar os valores de xe ypara esta função e nos dá a resposta errada. Não é surpreendente, uma vez que geramos isso aleatoriamente.

Agora você decide gerar um milhão de soluções desse tipo. Todos eles estão errados. No entanto, você percebe que algumas respostas estão mais próximas da resposta certa do que outras. Em outras palavras, algumas soluções são mais "adequadas" do que outras. Observe que o computador não sabe o que é "certo" e "errado"; portanto, você deve fornecer sua própria "função de condicionamento físico". Essa função recebe uma solução em potencial, os dados de treinamento e é responsável por informar ao sistema GP o quão "adequada" é essa solução. Como você pode imaginar, essa função é executada milhões e milhões de vezes.

O que faz GP diferente

Aqui está o que torna a programação genética diferente dos palpites. Você decide fazer outra rodada de milhões de palpites; no entanto, você faz isso de forma um pouco mais inteligente. Você pega os 10% principais das suposições (as que se aproximam dos valores reais) e as faz parte da segunda geração. Você também pega muitas dessas soluções (talvez os mesmos 10% ... não me lembro) e decide "misturá-las".

Você escolhe aleatoriamente duas soluções, escolhe subárvores aleatoriamente e começa a trocá-las. Portanto, parte da solução A termina na solução B e vice-versa - você apenas as "cruzou". Você também pega algumas soluções e simplesmente "as modifica" ... pega algumas subárvores e 'estraga tudo' (ei, se a solução é terrível, 'estragar tudo sem motivo' pode realmente melhorá-lo).

Uma boa maneira de pensar sobre isso é o seguinte: sua mãe e seu pai têm certos atributos - cor do cabelo, altura, probabilidade de doença, etc. Você, quando criança, herda atributos diferentes de seus pais. Se seus pais eram atletas olímpicos, você também será um super atleta, certo? Bem, biólogos, sociólogos e até historiadores podem discordar dessa idéia, mas os cientistas da computação não estão preocupados com a moralidade da eugenia aqui. Eles apenas viram um "sistema" fazendo um bom trabalho fornecendo soluções, então decidiram modelá-lo em software.

Se ele realmente não combina com a biologia, mas ainda fornece boas respostas ... muitos cientistas da computação coletivamente dizem "qualquer que seja, e obrigado pela terminologia". Observe também que todos os seus irmãos e irmãs e não exatamente o mesmo ... mesmo que tenham os mesmos pais. Cada pessoa tem genes que sofrem mutação por qualquer motivo (por favor, não mostre isso a um biólogo, o objetivo é entender a motivação por trás de grande parte da terminologia).

Então agora estamos conseguindo que o computador gere milhões de programas e avalie sua aptidão. As melhores soluções sobrevivem até a próxima geração. Também "mudamos" e cruzamos a "população" (observe como a linguagem da genética e da biologia está sendo usada). Depois que a segunda geração é criada, a aptidão é medida novamente. Como esta geração tem as melhores soluções da geração anterior E cruzamos e modificamos as melhores soluções (junto com a população medíocre - para manter a diversidade), essa geração deve ser pelo menos um pouco melhor que a geração anterior.

Continuamos isso por um número muito grande de gerações. Cada geração (esperançosamente) fornece soluções cada vez melhores, até obtermos a resposta certa. Por exemplo:

(+ (- 2.2 (/ x 11) (* 7 (cos y))))

Bem, veja isso, isso está correto!
(Copiei isso de http://en.wikipedia.org/wiki/Genetic_programming , que também possui uma representação gráfica dessa árvore)

Miudezas

Existem algumas questões importantes, como como você decide quais "terminais" ( +, -, *, /, cos, sin, tan) estão disponíveis para o seu sistema GP, como você escreve a função de condicionamento físico e como o sistema lida com programas não-sensoriais como (1 + cos)ou (2 / "hello")(entre muitos outros).

É muito chato evoluir equações. Fica mais interessante se o seu conjunto de terminais se parecer com o seguinte: (fogo, detectar inimigo, movimento, ...) e sua função de condicionamento físico medir sua saúde e o número de cadáveres de monstros marciais.

Escrevi a maior parte disso de memória, mas essa é a ideia básica. Eu fiz alguns GP nos meus anos de faculdade. Você definitivamente deveria brincar com isso. Não se preocupe em entender toda a terminologia, basta fazer o download de alguns sistemas GP gratuitos, executar alguns exemplos para ter uma ideia e criar seus próprios exemplos interessantes (encontrar relações entre diferentes conjuntos de dados, tente conectá-lo ao jogo APIs etc.)

A sobrevivência do mais apto: a seleção natural com o Windows Forms foi como fui apresentado à programação genética. É uma leitura fácil com o código disponível para download. A desvantagem é que o GP requer um meio de executar o código criado em tempo de execução e, no momento em que o artigo foi escrito, o C # não era adequado para essa tarefa. É por isso que o exemplo usa o CodeDOM para gerar, compilar e executar código em tempo de execução, o que por si só adiciona outra camada de complexidade a ele.

As coisas mudaram desde então, com o .NET agora tendo uma API ExpressionTree própria, o que provavelmente permitiria uma implementação de GP mais elegante em C # do que a descrita no artigo. Mas é bom o suficiente para entender como o GP funciona.

Aqui você pode baixar um e-book gratuito no GP, que também inclui um exemplo muito curto de código java que também pode ser interessante.

Algoritmos genéticos e programação genética estão relacionados, mas são conceitos diferentes.

Os algoritmos genéticos (GAs) são algoritmos de pesquisa para problemas complexos de otimização. Em um GA, você codifica os parâmetros de uma solução para algum problema em uma cadeia de bits de "DNA" e "reproduz" aleatoriamente essas cadeias de bits: faça com que elas se reproduzam combinando partes delas e aplique a "sobrevivência do mais apto", excluindo todas as cadeias de bits você tem, exceto os que são melhores para resolver seu problema.

A programação genética (GP) é ainda mais complicada: aqui, você não representa programas pelo DNA (cadeias de bits), mas analisa as árvores que você cria e seleciona.