Já que eu estou devendo duas semanas, vou aproveitar que ninguém está escrevendo aos sábados e vou postar “adiantado”.
Hoje é dia de misturar um pouco de ciência da computação com ciências biológicas. Mistura muito bonita e útil, por sinal. Antes, preciso apresentar uma palavra que pode ser nova para alguns dos leitores.
Um algoritmo é uma receita. Uma seqüência de passos e decisões que devem ser tomadas para que uma determinada tarefa seja completada. Assim como um delicioso prato de frango ao molho pardo, que tem um algoritmo para o arroz, outro para o angu e um mais complicado para o frango, os programas de computador são compostos por um ou vários algoritmos, com diferentes graus de complexidade. Genética todo mundo estudou no colégio, espero eu. Quando juntamos as duas palavras, o termo resultante não se mostra tão intuitivo assim, sendo incapaz de explicar o tema em questão, então vamos além.
Um algoritmo genético é uma técnica computacional que foi desenvolvida para resolver problemas de busca e otimização. Um problema clássico deste tipo é: um caixeiro viajante precisa visitar 10 cidades para entregar seus produtos. Qual o menor caminho que ele pode fazer passando por todas as cidades? Pois as técnicas que os algoritmos genéticos utilizam para resolver este problema são inspiradas na biologia evolutiva como hereditariedade, mutação, seleção natural e recombinação (crossing over).
Para o problema do caixeiro viajante, como funcionaria este processo? Explicação resumida: são criados vários “indivíduos”, cada uma representando um determinado caminho que o caixeiro pode seguir. Estes indivíduos são recombinados, resultando em caminhos diferentes, mistura dos originais (pais). Também sofrem mutações, o que pode ser positivo (gerar “atalhos”) ou negativo. Todos passam por uma seleção natural, onde somente os melhores (menores distâncias) são escolhidos para a próxima geração, onde o ciclo recomeça. O algoritmo termina quando um caminho satisfatório é encontrado. A figura abaixo ilustra o método.
Hoje é dia de misturar um pouco de ciência da computação com ciências biológicas. Mistura muito bonita e útil, por sinal. Antes, preciso apresentar uma palavra que pode ser nova para alguns dos leitores.
Um algoritmo é uma receita. Uma seqüência de passos e decisões que devem ser tomadas para que uma determinada tarefa seja completada. Assim como um delicioso prato de frango ao molho pardo, que tem um algoritmo para o arroz, outro para o angu e um mais complicado para o frango, os programas de computador são compostos por um ou vários algoritmos, com diferentes graus de complexidade. Genética todo mundo estudou no colégio, espero eu. Quando juntamos as duas palavras, o termo resultante não se mostra tão intuitivo assim, sendo incapaz de explicar o tema em questão, então vamos além.
Um algoritmo genético é uma técnica computacional que foi desenvolvida para resolver problemas de busca e otimização. Um problema clássico deste tipo é: um caixeiro viajante precisa visitar 10 cidades para entregar seus produtos. Qual o menor caminho que ele pode fazer passando por todas as cidades? Pois as técnicas que os algoritmos genéticos utilizam para resolver este problema são inspiradas na biologia evolutiva como hereditariedade, mutação, seleção natural e recombinação (crossing over).
Para o problema do caixeiro viajante, como funcionaria este processo? Explicação resumida: são criados vários “indivíduos”, cada uma representando um determinado caminho que o caixeiro pode seguir. Estes indivíduos são recombinados, resultando em caminhos diferentes, mistura dos originais (pais). Também sofrem mutações, o que pode ser positivo (gerar “atalhos”) ou negativo. Todos passam por uma seleção natural, onde somente os melhores (menores distâncias) são escolhidos para a próxima geração, onde o ciclo recomeça. O algoritmo termina quando um caminho satisfatório é encontrado. A figura abaixo ilustra o método.
Estes algoritmos são utilizados para resolver problemas demorados e de difícil resolução. Para se ter uma idéia do quão complicados são os problemas envolvidos, já ouvi de um professor a história da otimização do motor de um relógio de pulso que demorou 6 meses para encontrar um resultado aceitável.
Além da genética, o homem se inspirou em outras situações e comportamentos para criar modelos de algoritmos. Existe um baseado em colônia de formigas, nas revoadas dos pássaros e eu mesmo estou criando um modelo: ciclo de acasalamento das marmotas australianas. Brincadeira hein! Eu contei para um amigo e ele quase acreditou. Existem também as redes neurais, tema do próximo post...
Além da genética, o homem se inspirou em outras situações e comportamentos para criar modelos de algoritmos. Existe um baseado em colônia de formigas, nas revoadas dos pássaros e eu mesmo estou criando um modelo: ciclo de acasalamento das marmotas australianas. Brincadeira hein! Eu contei para um amigo e ele quase acreditou. Existem também as redes neurais, tema do próximo post...
5 comentários:
Fred, só queria comentar que adorei o texto... Ficou claro para os "leigos" como eu. Os exemplos metafóricos foram excelentes.
Nó... Agora fiquei ansiosa para ler sobre o modelo baseado nas redes neurais, que são uns dos meus principais objetos de estudo!
Concordo com o Lucas... Texto bem didático!
Kara muito bacana seu metodo mas de certa forma eh um tanto quanto ridiculo se passarmos do pressuposto q eh mecanico e lento.Creio eu q existam outras formas de fazer o mesmo sem q seja utilizando-se deste, talvez analise combinatoria seja mais eficiente.
Mas ta legal.
"Karo" anônimo,
eu não conheço nenhum programa de computador que não seja mecânico, isto é, executado por uma máquina. Caso contrário, teríamos um paradoxo.
Acho que você não captou ou nunca se deparou com o grau de complexidade dos problemas envolvidos (busca e otimização). Eles são muito, mas muito, mas muito mais complexos que qualquer problema de análise combinatória.
hahaha eu nunca disse q sou o dono da verdade.Axei q poderia sim existir alguma formula mais simples, sei la mas me parece q seja igual ao caso dos numeros primos, qm descobrir uma formula ou funcao alem de ganhar o premio nobel sai multimilionario.Nao se sinta ofendido por nenhum post e nem seja ironico e debochado ao falar dos outro todos merecem mais q isso.
Ass: anonimo,
bjinhos
Postar um comentário