Algoritmos genéticos

Prévia do material em texto

1 ALGORITMOS GENÉTICOS
1.1 Conceitos e definições
Algoritmos Genéticos são inspirados no princípio Darwiniano da evolução das espécies e na genética. São algoritmos probabilísticos que fornecem um mecanismo de busca paralela e adaptativa baseado no princípio de sobrevivência dos mais aptos e na reprodução.
Algoritmos Genéticos (GAs: Genetic Algorithms) são algoritmos matemáticos inspirados nos mecanismos de evolução natural e recombinação genética. A técnica de Algoritmos Genéticos fornece um mecanismo de busca adaptativa que se baseia no princípio Darwiniano de reprodução e sobrevivência dos mais aptos.
Os Algoritmos Genéticos são aplicados como uma técnica de procura e vem ganhando popularidade com inúmeros trabalhos de pesquisadores em aplicações diversas.
1.2 Características de operação e funcionamento
AGs são algoritmos de otimização global, baseados em mecanismos de seleção natural e de genética. Eles empregam uma estratégia de busca paralela e estruturada, porém aleatória, que é voltada em direção ao reforço da busca de pontos de "alta aptidão", ou seja, pontos nos quais a função a ser minimizada (ou maximizada) tem valores relativamente baixos (ou altos).
Apesar de aleatórios, eles não são caminhados aleatórios não direcionadas, pois exploram informação histórica para encontrar novos pontos de busca onde são esperados melhores desempenhos. Isto é feito através de processos iterativos, onde cada iteração é chamada de geração.
Durante cada iteração, os princípios de seleção e reprodução são aplicados a uma população de candidatos que pode variar, dependendo da complexidade do problema e dos recursos computacionais disponíveis. Através da seleção, determina-se quais os indivíduos que conseguirão reproduzir-se, gerando um número determinado de descendentes para a próxima geração, com uma probabilidade determinada pelo índice de aptidão. Por outras palavras, os indivíduos com maior adaptação relativa têm maiores probabilidades de reproduzir-se.
O ponto de partida para a utilização de Algoritmos Genéticos, como ferramenta para solução de problemas, é a representação destes problemas de maneira que os AGs possam trabalhar adequadamente sobre eles.
O princípio básico do funcionamento dos AGs é que um critério de seleção vai fazer com que, depois de muitas gerações, o conjunto inicial de indivíduos gere indivíduos mais aptos. A maioria dos métodos de seleção são projetados para escolher preferencialmente indivíduos com maiores índices de aptidão, embora não exclusivamente, a fim de manter a diversidade da população.
Há conjunto de operadores que são necessários para que, dada uma população, se consiga gerar populações sucessivas e que é esperado uma melhoria de sua aptidão com o tempo. Estes operadores são: cruzamento (crossover) e mutação.
1.2.1 População
O tamanho da população afeta o desempenho global e a eficiência dos AGs. Com uma população pequena o desempenho pode diminuir, pois deste modo a população fornece uma pequena cobertura do espaço de busca do problema. Uma grande população geralmente fornece uma cobertura representativa do domínio do problema, além de prevenir convergências prematuras para soluções locais ao invés de globais. No entanto, para se trabalhar com grandes populações, são necessários maiores recursos computacionais, ou que o algoritmo trabalhe por um período de tempo muito maior.
1.2.2 Gerações
O número de gerações contribui diretamente no tempo de computação necessário para o fim da pesquisa. Não influenciado diretamente a convergência do Ags, este operador é responsável pela coordenação de todos os parâmetros e evolução dos Ags.
1.2.3 Cruzamento (Crossover)
Quanto maior for esta probabilidade, mais rapidamente novas estruturas serão introduzidas na população. Mas se esta for muito alta as estruturas com boas aptidões poderão ser retiradas e a maior parte da população será substituída. Com um valor baixo, o algoritmo pode tornar-se muito lento.
1.2.4 Mutação
Uma baixa probabilidade de mutação previne que uma dada posição fique estagnada num valor, além de possibilitar que se chegue em qualquer ponto do espaço de busca. Com uma probabilidade muito alta a busca torna-se essencialmente aleatória.
1.3 Estrutura básica
Em GAs um cromossoma é uma estrutura de dados que representa uma das possíveis soluções do espaço de busca do problema. Cromossomas são então submetidos a um processo evolucionário que envolve avaliação, seleção, recombinação sexual (crossover) e mutação. Após vários ciclos de evolução a população deverá conter indivíduos mais aptos. A analogia entre Algoritmos Genéticos e o sistema natural é representada através da tabela abaixo:
	Natureza
	Algoritmos Genéticos
	Cromossoma
	Palavra binária, vetor, etc.
	Gene
	Característica do problema
	Alelo
	Valor da característica
	Loco
	Posição na palavra, vetor
	Genótipo
	Estrutura
	Fenótipo
	Estrutura submetida ao problema
	Indivíduo
	Solução
	Geração
	Ciclo
A estrutura básica do Algoritmo Genético é mostrada abaixo:
Início
Inicialização da população
Cálculo da aptidão
Solução encontrada?
Fim
Sim
	Reprodução
Não
Mutação
Seleção
Referências bibliográficas
https://paginas.fe.up.pt/~ee98221/paginas/algo.htm
http://www.nce.ufrj.br/GINAPE/VIDA/alggenet.htm
http://www2.ica.ele.puc-rio.br/Downloads%5C38/CE-Apostila-Comp-Evol.pdf