Análise Comparativa dos Algoritmos, Genético e Busca em Feixe Local, Aplicado ao Problema da Mochila 0/1

Análise Comparativa dos Algoritmos, Genético e Busca em Feixe Local, Aplicado ao Problema da Mochila 0/1. Anderson Andrei De Bona¹, Alfredo Conceição Erdmann² 1

2

Universidade Tecnológica Federal do Paraná (UTFPR)-Curitiba Universidade Tecnológica Federal do Paraná (UTFPR)-Medianeira {debona}@inf.ufsc.br, {alfredo.erdmann}@gmail.com

Resumo – Este artigo descreve um estudo comparativo entre duas técnicas de otimização aplicadas ao problema da mochila 0/1. Tal problema consiste em encontrar um conjunto de itens nos quais a soma de seus pesos não exceda um valor dado e que a soma de seus valores seja a maior possível. São aplicados dois mecanismos de busca evolutiva, sendo que a primeira técnica utilizada é o algoritmo Genético, e a segunda é busca em feixe local. No decorrer do artigo discutiremos cada um destes. Palavras-chave: Algoritmo genético; Problema da mochila; Busca evolutiva. Abstract – This paper describes a comparative study between two optimization techniques applied to the knapsack problem 0/1. The problem consists in finding a set of items in which the sum of their weights does not exceed a given value and the sum of their values is the largest possible. Are applied two evolutionary search engines, and the first technique is a genetic algorithm, the second local beam search. Throughout the article will discuss each of these. Keywords: Genetic algorithm; Knapsack problem; Evolutionary searchs.

INTRODUÇÃO Atualmente são inúmeros os problemas que podem ser considerados como computacionalmente intratáveis, como por exemplo, problemas de roteamento, de empacotamento, de alocação, entre outros, Goldbarg (2000). De acordo com Toscani (2002) problemas intratáveis não podem ser resolvidos com algoritmos determinísticos em tempo polinomial. Isso significa que é inviável resolver um problema intratável pelo método de busca exaustiva, onde todas as soluções possíveis são analisadas, o que, para entradas suficientemente grandes, acarretaria em um tempo de execução inaceitável para gerar o resultado, Garey (1979). Existem outras formas para se buscar uma solução viável a estes problemas em tempo polinomial. Uma possível solução é o uso de algoritmos aproximativos Cormen (2002), que se constituem em encontrar soluções próximas da solução ótima, já que muitas aplicações não requerem uma solução exata, Toscani (2002). Outra alternativa para buscar soluções a problemas intratáveis é o uso de métodos heurísticos. De acordo com Toscani (2002) existem vários exemplos de métodos heurísticos, porém neste artigo foram escolhidos os algoritmos, Genético e Busca em Feixe Local, onde será aplicado para fins de estudos o problema da mochila, também conhecido como Knapsack problem que é um problema de optimização combinatória, classificado como NP-Completo, Garey (1979). PROBLEMA DA MOCHILA 0/1 O problema é caracterizado por este nome, devido ao modelo de uma situação em que é necessário carregar uma mochila com capacidade limitada (objetos de diferentes

pesos e valores). O objetivo é que se carregue a mochila com o maior valor possível, respeitando o limite de peso, Goldberg (2000). No problema da Mochila 0/1 (0/ 1 knapsack Problem), cada item pode ser escolhido no máximo uma vez, a forma mais geral é o problema da Mochila com multi-restrições (Multi-constrained Knapsack Problem) o qual é basicamente um problema de Programação Inteira Geral com Coeficientes Positivos, Caldas (2002). Todos os problemas da Mochila pertencem à família NP-Completo, significando que é muito improvável que possamos desenvolver algoritmos polinomiais para este problema. Diversos exemplos de grandes instâncias podem ser resolvidos de maneira ótima em fração de segundos. Estes resultados surpreendentes vêm de várias décadas de pesquisa que tem exposto as propriedades estruturais especiais do Problema da Mochila, que tornam o problema tão relativamente fácil de resolver, Caldas (2002). Neste trabalho os dois algoritmos apresentados resolvem o Problema da Mochila 0/1 proposto, o qual é solicitado uma mochila com capacidade máxima de 25 kg, com 14 objetos de diferentes pesos e valores, que consiste em escolher itens, tais que o somatório do valor é maximizado sem que o somatório dos pesos extrapole a capacidade da Mochila. ALGORITMO GENÉTICO Algoritmo Genético (GA) é uma variação da busca de feixe estocástica, especificados primeiramente por Holland (1975), em que os estados sucessores são gerados pela combinação de dois outros. A ideia do processo envolvido em GA é inspirada na teoria de seleção natural proposta por Darwin no livro “A Origem das Espécies”, que descreve uma dinâmica na natureza em que somente os mais aptos sobrevivem. Desta forma, a nomenclatura usada vem da biologia, como é o caso de cromossomos, genes, crossover e mutação, Russell e Norvig (2004). Os elementos de busca são chamados de indivíduos e são representados por uma estrutura que é chamada de cromossomo. Embora na natureza um indivíduo possa ter vários cromossomos, na representação desta estratégia de busca apenas um cromossomo identifica um indivíduo. Mantendo a analogia, pode-se pensar em indivíduos unicromossômicos. Esses cromossomos são estruturas de dados codificadas com informações do problema e representam uma cadeia de elementos, os genes. Os estados do gene são chamados de alelos, Linden (2008). Inicia-se o processo pela geração aleatória de k indivíduos, chamado esse conjunto de população. Uma relação avalia o grau de adequação de um indivíduo às necessidades do problema, e é denominada função de fitness. Uma nova geração de indivíduos é obtida por operações genéticas. O crossover é o processo, em que há o “cruzamento” entre indivíduos, selecionando os pares de acordo com seu valor de fitness, sendo um indivíduo criado por troca de material genético da estrutura dos cromossomos pais. Os k elementos de maior fitness são preservados e o processo se repete até estes começarem convergir, ou seja, os indivíduos começarem a se repetir ou a variação de fitness começar a não ser significativa. Outras condições de parada podem ser também estipuladas, como um número máximo de gerações, Linden (2008). As sucessivas gerações podem convergir para um máximo local no espectro de optimalidade. Isso pode ser evitado com o uso de uma operação genética chamada mutação, processo no qual se pode introduzir, a cada nova geração, mudanças aleatórias em genes de uma pequena porcentagem dos indivíduos, permitindo a possibilidade de novos pontos de convergência, Linden (2008). BUSCA EM FEIXE LOCAL

O algoritmo de busca em feixe é caracterizado por ser um algoritmo heurístico de busca que tem como característica expandir nós mais promissores em um número limitado de expansão para então se gerar sucessores a fim de encontrar o resultado desejado O algoritmo de busca em feixe (beam search), pode ser considerado uma variante do algoritmo de subida de encosta, onde se mantém o controle de k estados, em vez de apenas um, o algoritmo inicia com k estados gerados aleatoriamente, onde em cada passo são gerados todos os sucessores de todos os k estados, sendo que qualquer um deles for um objetivo, o algoritmo deve parar, caso contrário, o mesmo selecionará os k melhores sucessores a partir da lista completa e repetirá a ação novamente, Russell e Norvig (2004). METODOLOGIA O problema será tratado da seguinte maneira: os pesos e os valores que serão utilizados são os que estão apresentados na Tabela 1 e a Capacidade da mochila C=25 kg. Tabela 1. Parâmetros para realização dos testes da Mochila 0/1 Obj(i=1,...n) 1 2 3 4 5 6 7 8 9 Peso (kg) 3 5 7 2 8 4 4 3 7 Valor 5 2 3 8 9 3 2 4 5

10 2 1

11 3 2

12 5 6

13 4 3

14 3 2

Para o algoritmo genético, utilizamos a quantidade de cromossomos da população, ou seja, a quantidade das possíveis soluções para o problema. Conforme Linden (2008), para cada gene será gerado 30 e 60 cromossomos. Em cada cromossomo é feito de forma aleatória a escolha dos itens que irão participar da possível solução. Em seguida será inserido os valores dos itens e os pesos dos itens da mochila, e uma possível quantia de gerações. Em cada geração é feito os operadores de crossover com uma porcentagem de 0.04% e o operador de mutação com uma taxa de 0.002%, que determina as melhores soluções da população gerada. A quantidade de população a ser utilizada será de 10, 100, 1.000, 10.000 e 100.000 os quais serão executados 10 vezes. Para o algoritmo de busca em feixe local, será informada a quantidade de nós e a profundidade a ser expandida utilizando a mesma quantidade de população utilizada no algoritmo genético. Os algoritmos foram implementados em linguagem C# e Java. RESULTADOS

População Peso Médio Peso Máximo Valor Médio Melhor Solução Valor/Peso Encontrada Solução Ideal

10 24,2 25 27,9 31/23 Não

Tabela 2. Análise dos resultados Algoritmos Genéticos 30 Cromossomos 60 Cromossomos 100 1.000 10.000 100.000 10 100 1.000 10.000 24,2 24,9 24,7 25 24,7 24,6 24,7 25 25 25 25 25 25 25 25 25 30,7 31,5 33,5 35 30,9 32,9 33,5 35 33/25 35/25 35/25 35/25 35/25 35/25 35/25 35/25 Não

Sim

Sim

Sim

Sim

Sim

Sim

Sim

100.000 25 25 35 35/25 Sim

Após análise dos testes realizados, (ver Tabela 2), fica evidente que a quantidade da população e a quantidade de cromossomos influenciam diretamente no resultado da solução. O objetivo atingido pelo algoritmo genético foi satisfatório, obtendo o maior valor do problema proposto, com valor de 35 e peso 25 (limite da mochila), encontrando a melhor solução somente quando a população a partir de 1.000 quando utilizando 30 cromossomos, e com 60 cromossomos a partir de uma população de 10, demonstrando que quanto maior a quantidade de cromossomos menor será a necessidade de utilizar

populações maiores, e a probabilidade de encontrar a solução será maior, ou seja, quanto menor a população mais rápida a execução do algoritmo. Tabela 3. Análise dos resultados Busca em Feixe Local Profundidade 10 100 1.000 10.000 Peso Médio 21,3 23,3 24,5 25 Peso Máximo 25 25 25 25 Valor Médio 26,8 30,6 32/8 35 Melhor Solução Valor/Peso 31/22 34/24 34/24 35/25 Encontrou a Solução Ideal Não Não Não Sim

100.000 25 25 35 35/25 Sim

A busca em feixe local obteve resultado satisfatório somente quando a profundidade foi superior a 10.000, sendo que a partir desta quantidade os resultados sempre são satisfatórios em todas as suas execuções, obtendo o melhor valor 35 e peso 25. CONCLUSÃO Após implementação dos algoritmos e realização dos testes com a quantidade de população para o algoritmo genético e a quantidade de nós expandida para a busca em feixe com números iguais, observou-se que os dois algoritmos apresentaram resultados que demonstram a diferença entre os dois métodos heurísticos. Nos testes ambos os algoritmos encontraram solução ideal, porém o algoritmo de busca em feixe local precisou de maior quantidade de nós para encontrar a solução, e na média encontrou soluções piores do que quando comparada ao algoritmo genético tanto com 30 quanto com 60 cromossomos. Destacamos que os melhores resultados na média para o algoritmo genético demonstram uma possível superioridade com os parâmetros testados para este problema da Mochila 0/1 e que sua capacidade pode ser superior ao do método de busca em feixe local, porém é interessante realizar testes com parâmetros diferentes para o mesmo problema ou em outros problemas de natureza NP-completo, para se concluir realmente que o algoritmo genético é superior na execução de problemas pertencente a esta classe. REFERÊNCIAS Caldas, B.R. (2004) Projeto e Análise de Algoritmos, UFMG - Instituto de Ciência Exatas - Departamento de Ciência da Computação, Belo Horizonte-MG, 2004 disponível em (http://homepages.dcc.ufmg.br/~nivio/cursos/pa04/tp2/tp22/tp22.pdf). Cormen, Thomas H. (2004) et al. Algoritmos: teoria e prática: Tradução da 2º edição Souza, V.D. Rio de Janeiro Ed. Campus. Garey, M. R.; Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of Np-Completeness. W.H Freeman & Co. Goldberg, M.C.; Luna, H.P.L. (2000) Otimização Combinatória e Programação Linear: Modelos e Algoritmos, Editora Campos, Rio de Janeiro. Holland, J. H. (1975) Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence (Complex Adaptive Systems S.). Cambridge, MA, USA: MIT Press. Linden, R., (2008) Algoritmos Genéticos – Uma importante ferramenta de Inteligência Computacional 2º Edição – Rio de Janeiro – Editora Brasport. Russel, S. e Norvig, P.(2004) Inteligência Artificial: Um enfoque moderno. Tradução da 2ª. ed. São Paulo: Prentice Hall. 1021 p. Toscani, L; Veloso P. (2002) Complexidade de Algoritmo. Editora Sagra Luzzato. Porto Alegre - Rio Grande do Sul.