Algoritmos GenéticosAlgoritmos Genéticos

Taís Sineiro HerigLaboratório de Genômica e Expressão / UNICAMP

IntroduçãoIntrodução

• Métodos computacionais inspirados na biologia evolutiva

• Encontrar solução ótima

• São uma classe dos Algoritmos Evolutivos

HistóricoHistórico

• Década de 60

• John Holland, Universidade de

Michigan

• Otimização em sistemas complexos

• Simular matematicamente o

mecanismo da evolução biológica

ÓtimosÓtimos

• Métodos matemáticos• Métodos probabilísticos

Ótimo local

Ótimo global

Algoritmos GenéticosAlgoritmos Genéticos

• Codificação

• Função objetivo

• Espaço de soluções

EstruturaEstrutura

Cromossomo SoluçãoGene ParâmetroLocus Posição dos bitsGenótipo Configuração dos bitsGeração Ciclo (cada iteração)

Representação do Representação do CromossomoCromossomo

Binária

Real

Símbolos

Binária

Fluxograma do AlgoritmoFluxograma do Algoritmo

População InicialPopulação Inicial

• Inicialização– Aleatória– Determinística

• Espaço de Busca

• Número de Elementos

• Valor de aptidão (fitness)

SeleçãoSeleção

• Roleta

• Torneio

• Seleção proporcional

• Ranking

CruzamentoCruzamento

• Escolha das soluções

• Escolha da posição

• Novo indivíduo

MutaçãoMutação

• Baixa X Alta Taxa de Mutação

• Pmut

Condição de ParadaCondição de Parada

• Número máximo de gerações

• Tempo limite

• Estagnação

• Resposta máxima da função objetivo

VantagensVantagens

• Não requer informação auxiliar

• Ótimos locais não reduzem a eficiência

• Excelentes resultados para a otimização em grande escala

Exemplos de AplicaçãoExemplos de AplicaçãoCavalo do

Xadrez• Objetivo

Cavalo do XadrezCavalo do Xadrez

• Analogias• Fitness (0,1) posições• Gene ordem do passo• Cromossomo solução possível

• Processo• Definir parâmetros

Cavalo do XadrezCavalo do Xadrez

Cavalo do XadrezCavalo do Xadrez

• Seleção (Roleta)

• Cruzamento

• Mutação

• Solução de Parada

Cavalo do XadrezCavalo do Xadrez

Tabela de Resultados

Cavalo do XadrezCavalo do Xadrez

Exemplos de AplicaçãoExemplos de Aplicação

Aplicação à Bioinformática

• Objetivo• Separar seqüências pertencentes a um

organismo A de um organismo B

• Como fazer• Usar características relevantes de uma

seqüênciaSeqüência

% GC (a)Entropia

(b)

Aplicação à BioinformáticaAplicação à Bioinformática

a(1) + b(2) + c(3) + ..... = Taxa

Teste com seqüências conhecidas:Taxa 1 Taxa 2 Taxa 3

Taxa 4

CÁLCULOS

Valor de Aptidão da Solução

a b c1 2 3 ...

... cromossomo

Aplicação à BioinformáticaAplicação à Bioinformática

• Usar a solução que apresenta melhor valor de aptidão

• Calcular o percentual de acertos

• Aplicar a solução para resolver problemas com seqüências desconhecidas

ConclusãoConclusão

• Algoritmo genético

– Modelo matemático que aproveita a Biologia Evolutiva

– Pode ser usado para resolver qualquer problema

– Tem se mostrado eficaz na otimização de problemas

FIM