Algoritmo Gentico para resoluo do problema da Mochila

Algoritmo Gentico para resoluo do problema da MochilaUniversidade Federal de Uberlndia. Ps-graduao em Cincia da computao Disciplina: Tpicos especiais em I.A.: aprendizagem de mquinaAlunos: Franciny MedeirosReslley GabrielWalter Silva

PautaDefinio do ProblemaRepresentao do ProblemaFuno de AvaliaoPopulao InicialSeleoCrossover de um pontoCrossover de mltiplos pontosMutaoReinseroCritrio de ParadaResultados e ConsideraesRefernciasDefinio do problemaConjunto S com n itens para serem empacotados em uma mochila.

Cada item tem um peso wi e um valor vi.

A mochila tem uma capacidade W.

Definio do problemaDefinio do problema

Para este trabalho foi considerada uma mochila com capacidade W = 35, o conjunto de itens n = 8 com seus respectivos pesos e valores ilustrados na figura abaixo.Representao do problemaO indivduo representa a mochila a ser preenchida.

Um indivduo representado por um cromossomo e cada gene do cromossomo representa um determinado item.

O valor contido nesse gene representa a quantidade do item selecionadoRepresentao do problemaQuando o item no for selecionado, o valor do gene correspondente ser 0, sendo que pode haver mais de 1 item do mesmo tipo na mochila.O cromossomo tambm possui um gene a mais que define o fitness do indivduo.

Funo de avaliaoComo o objetivo do problema maximizar o valor de itens contido na mochila, a qualidade do cromossomo dada pelo somatrio do valor de cada item que faz parte da soluo:

No decorrer da evoluo do algoritmo gentico podem ser geradas solues invlidas, ou seja, que no respeitam o peso mximo da mochila

Funo de avaliaoExistem duas formas de tratar indivduos invlidos: penalizao e reparao.A penalizao consiste em retirar algum valor da fitness dos indivduos que representam uma soluo invlida, deste modo eles tero menor probabilidade de serem selecionados.A reparao consiste em retirar alguns objetos da mochila at que a capacidade mxima seja respeitada. Dentre os objetos que esto na mochila o escolhido para ser retirado ser o que tiver menor custo benefcio (estratgia gulosa).Populao InicialGerada aleatoriamente.

Cada um dos genes de cada cromossomo posto com o valor 1 com 50% de probabilidade ou com o valor 0, caso contrrio.SeleoSeleo por roleta ou por torneio estocstico.

O fitness usado para distino entre os melhores e o piores elementos da populao.

Os mais aptos tem mais chances de serem selecionados. Crossover de um ponto1100 01012100011100201101 110033000001018Crossover de mltiplos pontos1100 01012100011100201101 110136000001005MutaoMutao com 10% de probabilidade1100 0101211100 000116ReinseroElitismo Preserva parte da populao pai

Melhores Pais e Filhos Seleciona os melhores entre a populao pai e a populao filha

Substituio Total Despreza a populao pai e repassa somente a populao filhaCritrio de paradaFoi definido que o algoritmo terminar a evoluo de sua populao ao fim de um certo nmero de geraes, nmero este que pode ser livremente configurado.Resultados e ConsideraesResultados e ConsideraesResultados e ConsideraesResultados e ConsideraesO melhor indivduo encontrado pelo AG foi:

Fitness 22 e peso 340000201022.0Item 1Item 2Item 3Item 4Item 5Item 6Item 7Item 8Peso10181214131186Valor58769543RefernciasKleinberg, J. Tardos, E. Algorithm design. Primeira edio, Pearson Education, 2006.

Tanomaru, J. Motivao, Fundamentos e Aplicaes de Algoritmos Genticos. II Congresso Brasileiro de Redes Neurais. III Escola de Redes Neurais, Curitiba 1995.RefernciasSilva, R. G. O. Construo de Conhecimento de Alto Nvel a partir de Datasets Biolgicos com Alta Dimensionalidade Utilizando Seleo de Atributos e Algoritmos Genticos. Monografia, Cincias da Computao Universidade Federal de Gois, 2012.

Silva, R. G. O; Amaral, L. R. Anlise Projeto e Desenvolvimento de Ferramentas Computacionais Tradicionais e Inteligentes Voltadas para a Bioinformtica. 64 Reunio Anual da SBPC Jornada Nacional de Iniciao Cientfica, 2012, So Lus MA.