Algoritmos Genéticos são algoritmos de otimização
global, baseados nos mecanismos de seleção natural e da genética.
Eles empregam uma estratégia de busca paralela e estruturada, mas 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 caminhadas aleatórias
não direcionadas, pois exploram informações históricas
para encontrar novos pontos de busca onde são esperados melhores
desempenhos. Isto é feito através de processos iterativos,
onde cada interaçã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, se determina quais indivíduos conseguirão se reproduzir, gerando um número determinado de descendentes para a próxima geração, com uma probabilidade determinada pela seu índice de aptidão. Em outras palavras, os indivíduos com maior adaptação relativa têm maiores chances de se reproduzir.
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 Algoritmos Genéticos possam trabalhar adequadamente sobre eles. A maioria das representações são genotípicas, utilizam vetores de tamanho finito em um alfabeto finito.
Tradicionalmente, os indivíduos são representados genotípicamente por vetores binários, onde cada elemento de um vetor denota a presença (1) ou ausência (0) de uma determinada característica: o seu genótipo. Os elementos podem ser combinados formando as características reais do indivíduo, ou o seu fenótipo. Teoricamente, esta representação é independente do problema, pois uma vez encontrada a representação em vetores binários, as operações padrão podem ser utilizadas, facilitando o seu emprego em diferentes classes de problemas.
A utilização de representações em níveis de abstração mais altos tem sido investigada. Como estas representações são mais fenotípicas, facilitariam sua utilização em determinados ambientes, onde essa transformação "fenótipo - genótipo" é muito complexa. Neste caso, precisam ser criados os operadores específicos para utilizar estas representações.
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 notas de aptidão, embora não exclusivamente, a fim de manter a diversidade da população. Um método de seleção muito utilizado é o Método da Roleta, onde indivíduos de uma geração são escolhidos para fazer parte da próxima geração, através de um sorteio de roleta.
Neste método, cada indivíduo da população é representado na roleta proporcionalmente ao seu índice de aptidão. Assim, aos indivíduos com alta aptidão é dada uma porção maior da roleta, enquanto aos de aptidão mais baixa é dada uma porção relativamente menor da roleta. Finalmente, a roleta é girada um determinado número de vezes, dependendo do tamanho da população, e são escolhidos, como indivíduos que participarão da próxima geração, aqueles sorteados na roleta.
Indivíduos de uma população e a sua correspondente roleta
de seleção.
Um conjunto de operações é necessário para
que, dada uma população, se consiga gerar populações
sucessivas que (espera-se) melhorem sua aptidão com o tempo. Estes
operadores são: cruzamento (crossover) e mutação.
Eles são utilizados para assegurar que a nova geração
seja totalmente nova, mas possuí, de alguma forma, características
de seus pais, ou seja, a população se diversifica e mantém
características de adaptação adquiridas pelas gerações
anteriores. Para prevenir que os melhores indivíduos não
desapareçam da população pela manipulação
dos operadores genéticos, eles podem ser automaticamente colocados
na próxima geração, através da reprodução
elitista.
Esse ciclo é repetido um determinado número de vezes. Abaixo é mostrado um exemplo de algoritmo genético. Durante esse processo, os melhores indivíduos, assim como alguns dados estatísticos, podem ser coletados e armazenados para avaliação.
Buscas em problemas reais são repletos de descontinuidades, ruídos e outros problemas. Métodos que dependam fortemente de restrições de continuidade e existência de derivadas são adequados apenas para problemas em um domínio limitado.
onde:
t - tempo atual; d - tempo determinado para finalizar o algoritmo; P - populaçã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, se determina quais indivíduos conseguirão se reproduzir, gerando um número determinado de descendentes para a próxima geração, com uma probabilidade determinada pela seu índice de aptidão. Em outras palavras, os indivíduos com maior adaptação relativa têm maiores chances de se reproduzir.
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 Algoritmos Genéticos possam trabalhar adequadamente sobre eles. A maioria das representações são genotípicas, utilizam vetores de tamanho finito em um alfabeto finito.
Tradicionalmente, os indivíduos são representados genotípicamente por vetores binários, onde cada elemento de um vetor denota a presença (1) ou ausência (0) de uma determinada característica: o seu genótipo. Os elementos podem ser combinados formando as características reais do indivíduo, ou o seu fenótipo. Teoricamente, esta representação é independente do problema, pois uma vez encontrada a representação em vetores binários, as operações padrão podem ser utilizadas, facilitando o seu emprego em diferentes classes de problemas.
A utilização de representações em níveis de abstração mais altos tem sido investigada. Como estas representações são mais fenotípicas, facilitariam sua utilização em determinados ambientes, onde essa transformação "fenótipo - genótipo" é muito complexa. Neste caso, precisam ser criados os operadores específicos para utilizar estas representações.
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 notas de aptidão, embora não exclusivamente, a fim de manter a diversidade da população. Um método de seleção muito utilizado é o Método da Roleta, onde indivíduos de uma geração são escolhidos para fazer parte da próxima geração, através de um sorteio de roleta.
Neste método, cada indivíduo da população é representado na roleta proporcionalmente ao seu índice de aptidão. Assim, aos indivíduos com alta aptidão é dada uma porção maior da roleta, enquanto aos de aptidão mais baixa é dada uma porção relativamente menor da roleta. Finalmente, a roleta é girada um determinado número de vezes, dependendo do tamanho da população, e são escolhidos, como indivíduos que participarão da próxima geração, aqueles sorteados na roleta.
Esse ciclo é repetido um determinado número de vezes. Abaixo é mostrado um exemplo de algoritmo genético. Durante esse processo, os melhores indivíduos, assim como alguns dados estatísticos, podem ser coletados e armazenados para avaliação.
- Procedimento AG
- { t = 0;
- inicia_população (P, t)
- avaliação (P, t);
- repita até (t = d)
- { t = t +1;
- seleção_dos_pais (P,t);
- recombinação (P, t);
- mutação (P, t);
- avaliação (P, t);
- sobrevivem (P, t)
- }
- }
Buscas em problemas reais são repletos de descontinuidades, ruídos e outros problemas. Métodos que dependam fortemente de restrições de continuidade e existência de derivadas são adequados apenas para problemas em um domínio limitado.
Comentários
Postar um comentário