Vamos utilizar a Programacao Genetica para resolver o segundo problema apresentado na pagina anterior.Comecas por especificar a lista de "ingredientes" que podem fazer parte do teu programa. Neste caso seria logico incluir varias expressoes aritmeticas (+,-,*,/) e, obviamente, as variaveis de entrada do teu programa (x1,x2,x3). Com estes ingredientes, crias uma "populacao" inicial de programas aleatorios. Por exemplo:f1=x3+x3-x1x1f2=x3+x3+x1f3=x2x1/x1+x3+x2f4=x3+x1-x2-x3f5=x2*x2f6=x1+x2+x3Agora todos estes programas tem de ser avaliados, para garantir que os mais aptos se reproduzem mais do que os outros (nao esquecer a seleccao natural de Darwin!). Uma boa forma de avaliar estes programas e 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 diferencas absolutas entre o que e obtido e o que era esperado, e dizer que os programas mais aptos sao os que devolvem o erro menor. Vamos entao recordar os resultados esperados em cada exemplo:f(1,2,3)=5f(6,2,5)=14f(1,10,8)=7E agora calculamos os resultados obtidos por cada programa:f1(1,2,3)=5f1(6,2,5)=-26f1(1,10,8)=15f2(1,2,3)=7f2(6,2,5)=16f2(1,10,8)=17f3(1,2,3)=7f3(6,2,5)=9f3(1,10,8)=28f4(1,2,3)=-1f4(6,2,5)=4f4(1,10,8)=-9f5(1,2,3)=4f5(6,2,5)=4f5(1,10,8)=100f6(1,2,3)=6f6(6,2,5)=13f6(1,10,8)=19Somamos as diferencas absolutas, o que nos da uma medida de erro para cada programa:f1: 0+40+8=48f2: 2+2+10=14f3: 2+5+21=28f4: 6+10+16=32f5: 1+10+93=104f6: 1+1+12=14Se ordenarmos estes programas por aptidao (menor erro) obtemos: f2 e f6, f3, f4, f1, f5. Repara que programas diferentes (f1 e f6) podem ter a mesma aptidao (14). Agora os programas vao "acasalar" uns com os outros, e trocar material genetico entre si para produzir programas novos. Chama-se a isto recombinacao. Tambem podem ocorrer mutacoes, mas nem precisamos disso agora. Vamos escolher os "casais" ao acaso, atribuindo maior probabilidade de escolha aos programas mais aptos. Alguns podem ser escolhidos varias vezes, enquanto outros nunca sao escolhidos. Tudo isto e um processo aleatorio, uma das razoes porque o resultado pode ser uma verdadeira surpresa. Sem entrar em detalhes, vamos supor que escolhemos os casais:f2,f6f2,f4f6,f1Cada um destes casais vai produzir dois filhos, trocando partes (material genetico) entre si. Vamos ver como funciona para o primeiro casal, f2,f6. Mais uma vez o processo e em grande parte aleatorio.Progenitores:f2=x3+x3+x1f6=x1+x2+x3f2 vai trocar a sua parte "x1" com a parte "x2+x3" de f6, produzindo dois novos programas:Descendentes:f7=x3+x3+x2+x3f8=x1+x1Agora o casal f2,f4 vai tambem trocar algum material genetico (a troca e entre "x1" de f2 e "x1-x2" de f4):Progenitores:f2=x3+x3+x1f4=x3+x1-x2-x3Descendentes:f9=x3+x3+x1-x2f10=x3+x1-x3E finalmente o ultimo casal, f6,f1:Progenitores:f6=x1+x2+x3f1=x3+x3-x1*x1Descendentes:f11=x1+x2+x1*x1f12=x3+x3+x3(ve la se consegues descobrir que partes foram trocadas)E agora vamos avaliar a nova populacao de programas (podes fazer os passos todos, para confirmar que isto esta certo):f7: 6+3+27=36f8: 3+2+5=10f9: 0+0+0=0f10: 4+8+6=18f11: 1+30+5=36f12: 4+1+17=22E voila, temos uma solucao perfeita! Repara que a expressao f9 (x3+x3+x1-x2), que tem erro zero, e exactamente o mesmo que a expressao x1-x2+2*x3 que tinha sido indicada como solucao na pagina anterior. Repara tambem que, independentemente de termos ou nao encontrado uma solucao perfeita, o erro medio da populacao baixou de 40 na geracao inicial para 20.3 na geracao seguinte (e so fazer as contas).E assim que a Programacao Genetica funciona. Muitas vezes nao e possivel encontrar uma solucao 'exacta' para o problema, mas apenas uma aproximacao. O algoritmo de Programacao Genetica encontra solucoes iniciais que nao sao muito boas, mas que vao sendo melhoradas ao longo de sucessivas geracoes. A populacao