Inteligencia Artificial

Problema Da Mochila Utilizando Algoritmos
Genéticos Como Heurística Para Resolução Do
Problema
Fabrício Alves Rodrigues, André Bevilaqua, Lucas Costa
Cunha, Laurence Rodrigues do Amaral

Sumario
• Problema da Mochila;
• Algoritmos Genéticos;
• Descrição do Algoritmo Genético ao Problema;
• Resultados;
• Conclusões e Trabalhos Futuros;
• Grupo de I.A. Campus Jataí.

2

Problema da Mochila
• Dado um conjunto de itens Ci;
• Cada item tem associado um peso P e um valor
U que representa a utilidade;
• Subconjunto dos itens que aproveite ao máximo o peso suportado pela mochila;
• Maior valor de utilidade possível para os itens escolhidos. 3

Problema da Mochila
• O problema da mochila pertence a classe NPHard;
• Hochba descreve os NP-Hard são aqueles que não se pode encontrar um algoritmo em tempo polinomial ;
• Para resolução pode se usar algoritmos de otimização; • Neste trabalho usamos o Algoritmo Genético.

4

Algoritmos Genéticos
• Os AGs constituem um ramo da Computação
Evolutiva;
• São aplicados para obtenção de soluções otimizadas para diversos problemas;
• Algoritmo Genéticos são robustos e flexíveis.
5

Algoritmos Genéticos
• Criados Holland em 1975 - se adaptavam nos sistemas naturais e como era feito em termos computacionais; • Os algoritmos genéticos trabalham com os operadores crossover e mutação;
• Tem grande potencial para os problemas buscam soluções ótimas.

6

Algoritmos Genéticos

7

Descrição do Algoritmo
Genético ao Problema
• Cada item do problema da mochila será um gene do algoritmo genético.

8

Descrição do Algoritmo
Genético ao Problema
• Cada indivíduo do AG representa uma mochila;
• A mochila terá capacidade de M itens (M é um valor inteiro);
• População do AG terá 6 indivíduos (Mochilas);
• O AG utiliza um campo de fitness, mede o quão próximo o AG está do objetivo.

9

Descrição do Algoritmo
Genético ao Problema
• Para o Crossover, são selecionados