Começas por especificar a lista de "ingredientes" que podem fazer parte do teu programa. Neste caso seria lógico incluir várias expressões aritméticas (+,-,*,/) e, obviamente, as variáveis de entrada do teu programa (x1,x2,x3). Com estes ingredientes, crias uma "população" inicial de programas aleatórios.
Por exemplo:
f1=x3+x3-x1x1
f2=x3+x3+x1
f3=x2x1/x1+x3+x2
f4=x3+x1-x2-x3
f5=x2*x2
f6=x1+x2+x3
Agora todos estes programas têm de ser avaliados, para garantir que os mais aptos se reproduzem mais do que os outros (não esquecer a selecção natural de Darwin!). Uma boa forma de avaliar estes programas é calcular os resultados que eles produzem para cada um dos exemplos, e comparar com os resultados que sabemos serem correctos. Podemos, por exemplo, somar as diferenças absolutas entre o que é obtido e o que era esperado, e dizer que os programas mais aptos são os que devolvem o erro menor. Vamos então recordar os resultados esperados em cada exemplo:
f(1,2,3)=5
f(6,2,5)=14
f(1,10,8)=7
E agora calculamos os resultados obtidos por cada programa:
f1(1,2,3)=5
f1(6,2,5)=-26
f1(1,10,8)=15
f2(1,2,3)=7
f2(6,2,5)=16
f2(1,10,8)=17
f3(1,2,3)=7
f3(6,2,5)=9
f3(1,10,8)=28
f4(1,2,3)=-1
f4(6,2,5)=4
f4(1,10,8)=-9
f5(1,2,3)=4
f5(6,2,5)=4
f5(1,10,8)=100
f6(1,2,3)=6
f6(6,2,5)=13
f6(1,10,8)=19
Somamos as diferenças absolutas, o que nos dá uma medida de erro para cada programa:
f1: 0+40+8=48
f2: 2+2+10=14
f3: 2+5+21=28
f4: 6+10+16=32
f5: 1+10+93=104
f6: 1+1+12=14
Se ordenarmos estes programas por aptidão (menor erro) obtemos: f2 e f6, f3, f4, f1, f5. Repara que programas diferentes (f1 e f6) podem ter a mesma aptidão (14). Agora os programas vão "acasalar" uns com os outros, e trocar material genético entre si para produzir programas novos. Chama-se a isto recombinação. Também podem ocorrer mutações, mas nem precisamos disso agora. Vamos escolher os "casais" ao acaso, atribuindo maior probabilidade de escolha aos programas mais aptos. Alguns podem ser escolhidos várias vezes, enquanto outros nunca são escolhidos. Tudo isto é um processo aleatório, uma das razões porque o resultado pode ser uma verdadeira surpresa. Sem entrar em detalhes, vamos supor que escolhemos os casais:
f2,f6
f2,f4
f6,f1
Cada um destes casais vai produzir dois filhos, trocando partes (material genético) entre si. Vamos ver como funciona para o primeiro casal, f2,f6. Mais uma vez o processo é em grande parte aleatório.
Progenitores:
f2=x3+x3+x1
f6=x1+x2+x3
f2 vai trocar a sua parte "x1" com a parte "x2+x3" de f6, produzindo dois novos programas:
Descendentes:
f7=x3+x3+x2+x3
f8=x1+x1
Agora o casal f2,f4 vai também trocar algum material genético (a troca é entre "x1" de f2 e "x1-x2" de f4):
Progenitores:
f2=x3+x3+x1
f4=x3+x1-x2-x3
Descendentes:
f9=x3+x3+x1-x2
f10=x3+x1-x3
E finalmente o último casal, f6,f1:
Progenitores:
f6=x1+x2+x3
f1=x3+x3-x1*x1
Descendentes:
f11=x1+x2+x1*x1
f12=x3+x3+x3
(vê lá se consegues descobrir que partes foram trocadas)
E agora vamos avaliar a nova população de programas (podes fazer os passos todos, para confirmar que isto está certo):
f7: 6+3+27=36
f8: 3+2+5=10
f9: 0+0+0=0
f10: 4+8+6=18
f11: 1+30+5=36
f12: 4+1+17=22
E voilà, temos uma solução perfeita! Repara que a expressão f9 (x3+x3+x1-x2), que tem erro zero, é exactamente o mesmo que a expressão x1-x2+2*x3 que tinha sido indicada como solução na
página anterior. Repara também que, independentemente de termos ou não encontrado uma solução perfeita, o erro médio da população baixou de 40 na geração inicial para 20.3 na geração seguinte (é só fazer as contas).
É assim que a Programação Genética funciona. Muitas vezes não é possível encontrar uma solução 'exacta' para o problema, mas apenas uma aproximação. O algoritmo de Programação Genética encontra soluções iniciais que não são muito boas, mas que vão sendo melhoradas ao longo de sucessivas gerações.
A população melhora como um todo ao longo do tempo. É um processo que pode demorar um bocado. Mas então, a mãe natureza não demorou também milhões de anos a fazer um ser humano, que mesmo assim está (muuuuito) longe de ser perfeito? :-)
Fonte: (Site academy)
tags: genetic programming, learnning machines, genetic programming, learnning machines, , learnning machines, , learnning machines)
Viagem fantástica foi também a que Darwin fez à volta do mundo durante quase 5 anos, a bordo do navio
Hmmm... afinal vamos começar com uma coisa simples. Queres encontrar a expressão (f) que transforma um par de números (x1,x2) num resultado. Tens como exemplos: f(2,3)=5, f(4,6)=10, f(5,1)=6. Não é preciso continuar, pois não? É óbvio que a expressão que procuras é f(x1,x2)=x1+x2. Para este problema não precisas da Programação Genética para nada!
