Algoritmos genéticos

Introdução

Algoritmo

Características Gerais            

Operadores Genéticos

            População.              Cruzamento.
            Gerações                Mutação.

 

Introdução

As técnicas de busca e optimização tradicionais iniciam-se com um único candidato que, iterativamente, é manipulado utilizando algumas heurísticas (estáticas) directamente associadas ao problema a ser solucionado. Geralmente, estes processos heurísticos não são algorítmicos e a sua simulação em computadores pode ser muito complexa.

Por outro lado, as técnicas de computação evolucionária operam sobre uma população de candidatos em paralelo. Assim, elas podem fazer a busca em diferentes áreas no espaço das soluções das soluções possíveis.

"Quanto melhor um indivíduo se adaptar ao seu meio ambiente, maior será a hipótese de sobreviver e gerar descendentes": este é o conceito básico da evolução genética biológica.

voltar

Algoritmo

Antes de prosseguir na a análise das características destes algoritmos, são necessários alguns conceitos básicos; que podem ser naturalmente expostos explicando o funcionamento básico dos algoritmos.

Inicialmente, é gerada uma população formada por um conjunto aleatório de indivíduos que podem ser vistos como possíveis soluções do problema. Durante o processo evolutivo, esta população é avaliada e para cada indivíduo é dada uma classificação que reflecte a sua habilidade de adaptação a determinado ambiente. Uma percentagem dos mais adaptados são mantidos, enquanto os outros são eliminados (darwinismo). Os membros mantidos pela selecção podem sofrer modificações em que as suas características fundamentais, através da mutação e cruzamento (crossover) geram descendentes para a próxima geração. Este processo, chamado de reprodução, é repetido até que uma solução satisfatória seja encontrada.

Embora possam parecer simplistas do ponto de vista biológico, estes algoritmos são suficientemente complexos para fornecer mecanismos de busca adaptativos poderosos e robustos

voltar

Características Gerais

AGs são algoritmos de optimização global, baseados em mecanismos de selecção natural e de genética. Eles empregam uma estratégia de busca paralela e estruturada, mas aleatória, que é voltada em direcçã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 caminhadas aleatórias não direccionadas, 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 selecçã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 selecçã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 selecçã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 selecção são projectados 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ário para que, dada uma população, se consiga gerar populações sucessivas e que (espera-se) melhorem sua aptidão com o tempo. Estes operadores são: cruzamento (crossover) e mutação.

voltar

Operadores Genéticos

O princípio básico dos operadores genéticos é transformar a população através de sucessivas gerações, estendendo a busca até chegar a um resultado satisfatório. Os operadores genéticos são necessários para que a população se diversifique e mantenha características de adaptação adquiridas pelas gerações anteriores.

O operador mutação é considerado um operador secundário e consiste em inverter cada bit cromossoma com uma probabilidade de mutação, muito baixa. É aplicado depois do cruzamento, a todos os descententes nos quais cada bit poderá ser para o seu complementar. Necessário para a introdução e manutenção da diversidade genética da população, fornece assim, meios para introdução de novos elementos na população. Desta forma, a mutação assegura que a probabilidade de se chegar a qualquer ponto do espaço de busca nunca será zero, além de contornar o problema de mínimos locais, pois com este mecanismo, altera-se levemente a direcção da busca.

A probabilidade cruzamento é o parâmetro responsável pela recombinação de características dos pais durante a reprodução, permitindo que as próximas gerações herdem essas características. Ele deve ser muito maior que a probabilidade de mutação, ja que é considerado o parâmetro genético predominante.

Este parâmetro pode, ainda, ser utilizado de várias maneiras, as mais utilizadas são:

um-ponto: um ponto de cruzamento é escolhido e a partir deste ponto as informações genéticas dos pais serão trocadas. As informações anteriores a este ponto em um dos pais são ligadas às informações posteriores à este ponto no outro pai, como é mostrado no exemplo da figura abaixo:

multi-pontos: é uma generalização desta ideia de troca de material genético através de pontos, onde muitos pontos de cruzamento podem ser utilizados.

uniforme: não utiliza pontos de cruzamento, mas determina, através de um parâmetro global, qual a probabilidade de cada variável ser trocada entre os pais.

É importante também, analisar de que maneira alguns operadores influem no comportamento dos Algoritmos Genéticos, para que se possa estabelecê-los conforme as necessidades do problema e dos recursos disponíveis.

voltar

População.

O tamanho da população afecta 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.

voltar

Gerações.

O número de gerações contribui directamente no tempo de computação necessãrio para o fim da pesquisa. Não influênciado directamente a convergência do Ags, este operador é responsável pela coordenação de todos os parâmetros e evolução dos Ags.

voltar

Cruzamento.

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.

voltar

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.

voltar