Darwinismo
Começando a resposta com a frase clássica de Charles Darwin, que pode ser encontrada em seu livro "A Origem das Espécies" (1859):
Quanto melhor um indivíduo se adaptar ao seu meio ambiente, maior será
sua chance de sobreviver e gerar descendentes.
Quando ouvimos falar em Darwinismo, já associamos logo a evolução, seleção natural, entre outras. A característica que mais distingue o darwinismo de todas as outras teorias é que a evolução é vista como uma função da mudança da população e não da mudança do indivíduo e é ai que entra o algoritmo genético, pois como o seu desenvolvimento, biólogos, físicos, matemáticos e cientista podem descrever processos evolucionários semelhantes à evolução da vida.
Pensando nas condições que um processo darwinista requer:
- Reprodução: os agentes devem ser capazes de produzir cópias de si próprios e essas cópias devem ter igualmente a capacidade de se reproduzirem;
- Hereditariedade: As cópias devem herdar as características dos originais;
- Variação: Ocasionalmente, as cópias têm que ser imperfeitas (diversidade no interior da população);
- Seleção Natural: Os indivíduos são selecionados pelo ambiente. A seleção natural destrói, e não cria. O problema da existência de um objetivo não surge da eliminação dos inaptos, e sim da origem dos aptos.
Em qualquer sistema onde ocorram essas características deverá ocorrer evolução.
Tendo essas conceitos em mente, podemos falar um pouco sobre o algoritmo genético em si.
Algoritmo genético
Definição:
Um algoritmo genético (AG) é uma técnica de busca utilizada na ciência
da computação para achar soluções aproximadas em problemas de
otimização e busca, fundamentado principalmente pelo americano John
Henry Holland. Algoritmos genéticos são uma classe particular de
algoritmos evolutivos que usam técnicas inspiradas pela biologia
evolutiva como hereditariedade, mutação, seleção natural e
recombinação (ou crossing over).
Fonte: Wikipédia
E o que isso quer dizer?
Pense nas "leis da natureza", os indivíduos de uma mesma população competem entre si, buscando principalmente a sobrevivência, seja na busca por alimentos ou reprodução. Os indivíduos mais aptos terão um maior número de descendentes. Os algoritmos genéticos simulam esses processos de sobrevivência e reprodução das populações.
Os algoritmos genéticos são métodos de otimização e busca, que foram inspirados nos mecanismos de evolução de populações de seres vivos. Eles seguem o princípio de seleção natural e sobrevivência do mais apto.
Otimização é a busca da melhor solução para um dado problema, consistindo em tentar várias soluções e utilizar a informação obtida neste processo de forma a encontrar soluções cada vez melhores.
Os algoritmos genéticos diferem dos métodos tradicionais de busca e otimização, principalmente em quatro aspectos:
Trabalham com uma codificação do conjunto de parâmetros e não com os próprios parâmetros.
Trabalham com uma população e não com um único ponto.
Utilizam informações de custo ou recompensa e não derivadas ou outro conhecimento auxiliar.
Utilizam regras de transição probabilísticas e não determinísticas.
função AlgoritmoGenético(população, função-objetivo) saídas: indivíduo
entradas: população→ uma lista de indivíduos
função-objetivo→ uma função que recebe um indivíduo e retorna um número real.
repetir
lista de pais := seleção(população, função-objetivo)
população := reprodução(lista de pais)
enquanto nenhuma condição de parada for atingida
retorna o melhor indivíduo da população de acordo com a função-objetivo
Código do Wikipédia.
Algoritmos genéticos são muito eficientes para busca de soluções ótimas, ou aproximadamente ótimas em uma grande variedade de problemas, pois não impõem muitas das limitações encontradas nos métodos de busca tradicionais.
Funcionamento
Em 1975, HOLLAND, decompôs o funcionamento dos algoritmos genéticos nas seguintes etapas: inicialização, avaliação, seleção, cruzamento, mutação, atualização e finalização.
Basicamente, o que um algoritmo genético faz é criar uma população de
possíveis respostas para o problema a ser tratado (inicialização) para depois submetê-la ao processo de evolução, constituído pelas seguintes etapas:
Avaliação: avalia-se a aptidão das soluções (indivíduos da população), é feita uma análise para que se estabeleça quão bem elas respondem ao problema proposto.
Seleção: indivíduos são selecionados para a reprodução. A probabilidade de uma dada solução i ser selecionada é proporcional à sua aptidão. Pode ser utilizado o método da roleta, elitismo, etc..
Cruzamento: características das soluções escolhidas são recombinadas, gerando novos indivíduos.
Mutação: características dos indivíduos resultantes do processo de reprodução são alteradas, acrescentando assim variedade à população.
Atualização: os indivíduos criados nesta geração são inseridos na população.
Finalização: verifica se as condições de encerramento da evolução foram atingidas, retornando para a etapa de avaliação em caso negativo e encerrando a execução em caso positivo.
Por se tratar de uma técnica bastante difundida e geralmente oferecer bons
resultados, os algoritmos genéticos são usados para solucionar diversos tipos de problemas, entre eles: Sistemas de classificação, escalonamento e grade horária.
Referências: