Upload
matheus-gomes
View
367
Download
1
Embed Size (px)
Citation preview
OCOMO UM PROBLEMA
RELATIVAMENTE
COMPLEXOPODE SER SOLUCIONADO
POR UM ALGORITMO DE
FÁCIL USOE BAIXO CUSTO
COMPUTACIONAL
DA
PROBL
MOCHI
EMA
LA
DO QUE SE
TRATA ESSA
APRESENTAÇÃO?
1
2
3
O Problema da Mochila, de Richard Karp
O Algoritmo Genético, desenvolvido por John Henry Holland
O desenvolvimento de um Algoritmo Genético Híbrido para o Problema da Mochila
PROBLEMA
DA
MOCHILA
Ocupar a mochila com o MAIOR VALOR POSSÍVEL,
não ultrapassando o seu PESO MÁXIMO.
TEMPO (s)
NÚMERO
DE ITENS
ENTÃO, QUAL A SOLUÇÃO
ALGORITMO
GENÉTICO
EVOLUÇ
EVOLUÇ
EVOLUÇ
EVOLUÇ
EVOLUÇ
EVOLUÇ
EVOLUÇ
EVOLUÇ
APTIDÃO
APTIDÃO
Indivíduos MAIS FORTES têm mais chances
de sobreviver e de GERAR DESCENDENTES
SELEÇÃO
SELEÇÃO
SELEÇÃO
SELEÇÃO
SELEÇÃO
SELEÇÃO
CRUZAMENTO
CRUZAMENTO
CRUZAMENTO
+
CRUZAMENTO
+
CRUZAMENTO
+ =
CRUZAMENTO
+ =
MUTAÇÃO
MUTAÇÃO
MUTAÇÃO
MUTAÇÃO
REPOSIÇÃO
REPOSIÇÃO
REPOSIÇÃO
REPOSIÇÃO
PSEUDO-CÓDIGO DE UM AG PADRÃO
PSEUDO-CÓDIGO DE UM AG PADRÃO
1 – GERAR UMA POPULAÇÃO DE SOLUÇÕES.
PSEUDO-CÓDIGO DE UM AG PADRÃO
2 – AVALIAR AS SOLUÇÕES GERADAS.
1 – GERAR UMA POPULAÇÃO DE SOLUÇÕES.
PSEUDO-CÓDIGO DE UM AG PADRÃO
2 – AVALIAR AS SOLUÇÕES GERADAS.
1 – GERAR UMA POPULAÇÃO DE SOLUÇÕES.
ENQUANTO UM CRITÉRIO DE PARADA NÃO FOR SATISFEITO, FAÇA
PSEUDO-CÓDIGO DE UM AG PADRÃO
2 – AVALIAR AS SOLUÇÕES GERADAS.
1 – GERAR UMA POPULAÇÃO DE SOLUÇÕES.
ENQUANTO UM CRITÉRIO DE PARADA NÃO FOR SATISFEITO, FAÇA
3 – SELECIONAR UM CONJUNTO K DE PAIS.
PSEUDO-CÓDIGO DE UM AG PADRÃO
2 – AVALIAR AS SOLUÇÕES GERADAS.
1 – GERAR UMA POPULAÇÃO DE SOLUÇÕES.
ENQUANTO UM CRITÉRIO DE PARADA NÃO FOR SATISFEITO, FAÇA
3 – SELECIONAR UM CONJUNTO K DE PAIS.
4 – REALIZAR O CRUZAMENTO DOS PAIS, DADA UMA PROBABILIDADE
PSEUDO-CÓDIGO DE UM AG PADRÃO
2 – AVALIAR AS SOLUÇÕES GERADAS.
1 – GERAR UMA POPULAÇÃO DE SOLUÇÕES.
ENQUANTO UM CRITÉRIO DE PARADA NÃO FOR SATISFEITO, FAÇA
3 – SELECIONAR UM CONJUNTO K DE PAIS.
4 – REALIZAR O CRUZAMENTO DOS PAIS, DADA UMA PROBABILIDADE
5 – REALIZAR A MUTAÇÃO DAS W SOLUÇÕES GERADAS,
COM UMA DADA PROBABILIDADE
PSEUDO-CÓDIGO DE UM AG PADRÃO
2 – AVALIAR AS SOLUÇÕES GERADAS.
1 – GERAR UMA POPULAÇÃO DE SOLUÇÕES.
ENQUANTO UM CRITÉRIO DE PARADA NÃO FOR SATISFEITO, FAÇA
3 – SELECIONAR UM CONJUNTO K DE PAIS.
4 – REALIZAR O CRUZAMENTO DOS PAIS, DADA UMA PROBABILIDADE
5 – REALIZAR A MUTAÇÃO DAS W SOLUÇÕES GERADAS,
COM UMA DADA PROBABILIDADE
6 – AVALIAR A APTIDÃO DAS SOLUÇÕES GERADAS
PSEUDO-CÓDIGO DE UM AG PADRÃO
2 – AVALIAR AS SOLUÇÕES GERADAS.
1 – GERAR UMA POPULAÇÃO DE SOLUÇÕES.
ENQUANTO UM CRITÉRIO DE PARADA NÃO FOR SATISFEITO, FAÇA
3 – SELECIONAR UM CONJUNTO K DE PAIS.
4 – REALIZAR O CRUZAMENTO DOS PAIS, DADA UMA PROBABILIDADE
5 – REALIZAR A MUTAÇÃO DAS W SOLUÇÕES GERADAS,
COM UMA DADA PROBABILIDADE
6 – AVALIAR A APTIDÃO DAS SOLUÇÕES GERADAS
7 – ATUALIZAR A POPULAÇÃO
PSEUDO-CÓDIGO DE UM AG PADRÃO
2 – AVALIAR AS SOLUÇÕES GERADAS.
1 – GERAR UMA POPULAÇÃO DE SOLUÇÕES.
ENQUANTO UM CRITÉRIO DE PARADA NÃO FOR SATISFEITO, FAÇA
3 – SELECIONAR UM CONJUNTO K DE PAIS.
4 – REALIZAR O CRUZAMENTO DOS PAIS, DADA UMA PROBABILIDADE
5 – REALIZAR A MUTAÇÃO DAS W SOLUÇÕES GERADAS,
COM UMA DADA PROBABILIDADE
6 – AVALIAR A APTIDÃO DAS SOLUÇÕES GERADAS
7 – ATUALIZAR A POPULAÇÃO
FIM DO ENQUANTO
PSEUDO-CÓDIGO DE UM AG PADRÃO
IMPRIMIR A MELHOR SOLUÇÃO OBTIDA
2 – AVALIAR AS SOLUÇÕES GERADAS.
1 – GERAR UMA POPULAÇÃO DE SOLUÇÕES.
ENQUANTO UM CRITÉRIO DE PARADA NÃO FOR SATISFEITO, FAÇA
3 – SELECIONAR UM CONJUNTO K DE PAIS.
4 – REALIZAR O CRUZAMENTO DOS PAIS, DADA UMA PROBABILIDADE
5 – REALIZAR A MUTAÇÃO DAS W SOLUÇÕES GERADAS,
COM UMA DADA PROBABILIDADE
6 – AVALIAR A APTIDÃO DAS SOLUÇÕES GERADAS
7 – ATUALIZAR A POPULAÇÃO
FIM DO ENQUANTO
DADOS
TAMANHO DA POPULAÇÃO:
TAMANHO DA POPULAÇÃO:
100
TAMANHO DA POPULAÇÃO:
PROBABILIDADE DE MUTAÇÃO:
100
TAMANHO DA POPULAÇÃO:
PROBABILIDADE DE MUTAÇÃO:
100
0,05
TAMANHO DA POPULAÇÃO:
PROBABILIDADE DE MUTAÇÃO:
NÚMERO DE GERAÇÕES:
100
0,05
TAMANHO DA POPULAÇÃO:
PROBABILIDADE DE MUTAÇÃO:
NÚMERO DE GERAÇÕES:
100
0,05
20n
TAMANHO DA POPULAÇÃO:
PROBABILIDADE DE MUTAÇÃO:
NÚMERO DE GERAÇÕES:
INSTÂNCIAS PARA CADA CAPACIDADE:
100
0,05
20n
TAMANHO DA POPULAÇÃO:
PROBABILIDADE DE MUTAÇÃO:
NÚMERO DE GERAÇÕES:
INSTÂNCIAS PARA CADA CAPACIDADE:
100
0,05
20n
5, ALEATÓRIAS
TAMANHO DA POPULAÇÃO:
PROBABILIDADE DE MUTAÇÃO:
NÚMERO DE GERAÇÕES:
ITENS A SEREM AVALIADOS:
INSTÂNCIAS PARA CADA CAPACIDADE:
100
0,05
20n
5, ALEATÓRIAS
TAMANHO DA POPULAÇÃO:
PROBABILIDADE DE MUTAÇÃO:
NÚMERO DE GERAÇÕES:
ITENS A SEREM AVALIADOS:
INSTÂNCIAS PARA CADA CAPACIDADE:
100
0,05
20n
5, ALEATÓRIAS
50, 100, 200 E 500 ITENS
RESULTADOS
GAP MELHOR SOLUÇÃO
50 ITENS:
GAP MELHOR SOLUÇÃO
0 %
50 ITENS:
100 ITENS:
GAP MELHOR SOLUÇÃO
0 %
0,8 %
50 ITENS:
100 ITENS:
200 ITENS:
GAP MELHOR SOLUÇÃO
0 %
0,8 %
1,2 %
50 ITENS:
100 ITENS:
200 ITENS:
500 ITENS:
GAP MELHOR SOLUÇÃO
0 %
0,8 %
1,2 %
2,8 %
50 ITENS:
100 ITENS:
200 ITENS:
500 ITENS:
MÉDIA GERAL:
GAP MELHOR SOLUÇÃO
0 %
0,8 %
1,2 %
2,8 %
1,2 %
CONCLUSÕES
COMPETITIVO
COMPETITIVO
DIVERSAS APLICAÇÕES
COMPETITIVO
DIVERSAS APLICAÇÕES
FÁCIL USO
COMPETITIVO
DIVERSAS APLICAÇÕES
FÁCIL USO
BAIXO CUSTO COMPUTACIONAL
COMPETITIVO
DIVERSAS APLICAÇÕES
FÁCIL USO
BAIXO CUSTO COMPUTACIONAL
GRANDE ADAPTABILIDADE
MATHEUS GOMES CORREIA
RAFAEL WENDELL BARROS FORTE DA SILVA
BRUNO DE ATHAYDE PRATA
WWW.LRI.UFC.BR