Algoritmos Genéticos

Riou · 26 de julho de 2004

Aí pessoal, estava sem ter o que fazer, então coletei alguns dados e escrevi uma pequenina introdução sobre esse assunto para colaborar um pouquinho com o fórum .

Quando vocês leram "Algoritmos genéticos" no título vocês devem ter feito uma cara assim:

Bem, digamos que os conceitos de seleção natural, mutação e herança genética podem ser empregados na programação. . . . . .

– Xiii! Oh brother, o maluco pirou de vez aí!

Calma, eu não fiquei louco não, eu tô falando sério! Utilizando os mesmos conceitos do mundo real é possível criar programas mais eficientes.

Num algoritmo genético, as variáveis são como se fossem os indivíduos na seleção natural, que são representados por strings binárias. Acontece do mesmo jeito que na natureza: as melhores strings sobrevivem e conseguem se reproduzir, mas as piores são eliminadas! Assim a população evolui e chegamos a um resultado final.

As strings vão ser as possíveis soluções de um certo problema. Se o algoritmo genético for bem construído, a população se transformará numa ótima solução para o problema proposto.

– Ih, isso aí tá muito confuso....

Vamos ver com um exemplo simples e prático como isso funciona:

Nosso objetivo é criar um programa que resolva a equação 3x + 1 = 13 . . . . .esse problema é muito simples para precisar de um algoritmo genético, mas esse conceito básico pode ser aplicado também em soluções de problemas complexos, como análise criptográfica.

O primeiro passo é criar a população inicial. Podemos ter qualquer intervalo numérico, como o conjunto dos números inteiros ou até mesmo os reais, mas é melhor ser mais específico. É só ter um pouquinho de bom senso para saber que o número solução está entre 0 e 100. . . . .nós sabemos que o resultado é 4, mas o computador não precisa saber disso .

Agora que definimos o intervalo, pedimos para o computador escolher alguns números. Vamos pedir para ele escolher 8 números aleatórios entre 0 e 100. Nosso algoritmo vai ficar assim:

Declarar variáveis inteiras: n1, n2, n3, n4, n5, n6, n7, n8

Variável de contagem: x

Estrutura de repetição:

Para x de 1 até 8 passo 1 faça

Enquanto n(x) = n1, n2, n3, n4, n5, n6, n7, n8

Atribua um valor aleatório para n(x)

Fim-enquanto

Fim-para

Agora, a gente precisa escolher os melhores valores, ou seja, aqueles mais próximos da resposta correta. Vamos supor que dois dos números aleatórios são 7 e 13. Substituindo na equação, temos:

3 . 7 + 1 = 13

21 + 1 = 13

22 = 13

3 . 13 + 1 = 13

39 + 1 = 13

40 = 13

Com certeza o primeiro é o mais próximo, então o algoritmo deve descartar a segunda opção e a primeira deve se reproduzir. Para testar os valores, geralmente usamos o valor absoluto 18:

Declarar variáveis numéricas: m1, m2, m3, m4, m5

m1 ? n1

Se (18 - 3 * n2 + 1) < (18 - 3 * m1 + 1) então m1 ? n2

Se (18 - 3 * n3 + 1) < (18 - 3 * m1 + 1) então m1 ? n3

.

Se (18 - 3 * n8 +1) < (18 - 3 * m1 + 1) então m1 ? n8

Assim, avaliamos toda a população, colocando o melhor número na variável m1, o segundo melhor na m2, e assim por diante, até m5. Conseguimos eliminar três números da nossa população de oito.

Agora, chegou a hora mais difícil: vamos ter que cruzar a população!

Só que como o computador só compreende o sistema binário, vamos ter que usar este sistema para cruzar os números. O binário será o código genético dos números. Vamos imaginar que os seguintes números sobreviveram: 2, 5, 8, 43, 89.

Transformando em binário, temos:

2 = 0000010

5 = 0000101

8 = 0001000

43 = 0101011

89 = 1011001

Agora, vamos cruzar o 8 com o 43.

– Hahaha, agora eu quero ver a sacanagem!

Não é isso que você tá pensando, mente suja! Vamos escolher um ponto de cruzamento, isto é, um número aleatório que vai definir onde os cromossomos, que são os números em binário, vão se dividir. Escolhemos o número aleatório 4.

Daí, pegamos os quatro primeiros números do pai, que é o número 8, e os três últimos números da mãe, que é o 43. Desse jeito, nós cruzamos os dois:

PAI = 0001 | 000

MÃE = 0101 | 011

FILHO = 0001 | 011

O primeiro filho é o número 11. O segundo filho será com os quatro primeiros números da mãe e os três últimos números do pai:

PAI = 0001 | 000

MÃE = 0101 | 011

FILHO = 0101 | 000

O segundo filho é o número 40. Assim, o cruzamento entre os dois números pais gerou dois filhos, 11 e 40.

Como eles receberam uma parte do código genético de cada um, eles são diferentes, mas mesmo assim são parecidos com os pais.

– E aí, quando vamos ter evolução?

Fácil: os melhores números da seleção vão poder se reproduzir mais vezes do que os piores. Desse jeito, mais números vão ter suas características. . . . . como o 5 é o melhor número do nosso exemplo, porque é o mais perto do resultado, ele vai poder se reproduzir duas vezes, fazendo com que cada vez mais cheguemos perto do resultado correto. Se cruzarmos toda a nossa população usando o mesmo ponto de cruzamento, teremos os seguintes números:

5 com 8 = 0 e 13

5 com 43 = 3 e 45

2 com 43 = 3 e 42

8 com 89 = 9 e 88

Agora voltamos para oito números. . . . .mas desta vez os cinco melhores números estão mais próximos do resultado correto. . . . . .quanto mais os números vão evoluindo, mais próximos ficam do 4!

:palmas:

Agora que já definimos como evoluir a nossa população, só falta escolher quanto tempo eles vão fazer isso. . . . daí é só a gente por um loop! Por exemplo, se eu quiser que eles se evoluam durante 15 gerações, é só fazer um loop voltando para a seleção dos números 15 vezes e no final a maior parte da população vai ter o valor 4, que é o resultado do nosso problema!

– Aewz, olha só que da hora velho!

Bem pessoal, essas são as informações que eu consegui, espero que isso seja útil para vocês e que este tópico possa ser usado para continuar essa discussão sobre os algoritmos genéticos, que são muito interessantes!

Se alguém tiver algo legal aí, pode postá também, este tópico tá aqui para isso!

tabgal · 26 de julho de 2004

Parabéns pelo tópico!

Faz falta uns tópicos avançados como esses...

Já brinquei bastante com programação genética, e pretendo estudar ainda mais isso.

AzaZell · 27 de julho de 2004

Eu adorava a matéria de Inteligência Artificial na Faculdade... pena que nunca mais mexi com isso...

Bom, vou procurar uns programas de IA, que fiz na minha época de Facu... se der eu coloco aqui...

Me lembro bastante de ficar configurando Mutações, Número de Gerações, Número de indivíduos, População inicial e etc...

refagibson · 28 de julho de 2004

Eu também trabalhei com algoritmos genéticos na minha tese de doutorado. Aprendi muita coisa e ainda fiquei com um montão de dúvidas, pois na hora de aplicar em um problema da vida real, surgem inúmeras dificuldades.

Será interessante aprofundar a discussão.

xco · 28 de julho de 2004

Eu já implementei um algoritmo genetico de busca bidimensional, para tracking em imagens de vídeo....

Se alguém quiser:

www.ic.unicamp.br/~ra015988/lis/projeto/agb

AzaZell · 28 de julho de 2004

Postado Originalmente por refagibson@27 jul 2004, 21:18
Eu também trabalhei com algoritmos genéticos na minha tese de doutorado. Aprendi muita coisa e ainda fiquei com um montão de dúvidas, pois na hora de aplicar em um problema da vida real, surgem inúmeras dificuldades.

Será interessante aprofundar a discussão.

Caramba, tú já fez Doutorado? Então você deve manjar muito hein... dificilmente encontro pessoas com Doutorado em fóruns na Net... com exceção do Orkut...

Bom, eu andei procurando meus programas de Facu... até achei eles... mas não achei o enunciado... E sem o enunciado não dá para entender nada...

Mas o básico é que a resposta da problema evolue(otimiza) de acordo com as configurações de Gerações, mutações, Crossover, e etc... É parecido com algoritmo da mochila. Tem itens que devem se ajeitar com o custo mais baixo...

Se alguém quiser, é só pedir...

azazell(arr0ba)gmail.com

Obs: No windows 98 esse programa funciona normal... mas no 2000, percebi agora que a formatação fica estranha(mas legível). Acho que deu algum problema de portabilidade...