I SBAI - UNESP - Rio Claro/SP - Brasil

ALGORITMOS GENÉTICOS E SUA APLICAÇÃO AO PROBLEMA DO CORTE DE BARRAS

Alex Alves Freitas! Júnia Coutinho Anacleto 1

Reinaldo Morábito Neto 2

Claudio Kirner 1

RESUMO

Este trabalho introduz os conceitos básicos da teoria de Algoritmos Gené­ticos, uma técnica de busca baseada na seleção natural de Darwin, cujas principais vantagens são a simplicidade e a generalidade. São descritos os principais conceitos relacionados ao método e definidos os três princi­pais operadores genéticos - reprodução, cruzamento e mutação. É discu­tida também uma experiência de implementação de Algoritmos Genéticos para solução do problema do corte de barras - uma versão do problema da mochila, rico em aplicações industriais importantes do ponto de vista técnico e econômico. Por fim, são apresentados e discutidos os resultados computa­cionais obtidos com a aplicação da técnica, comparando com os resultados computacionais obtidos com a aplicação de uma técnica mais tradicional para resolução do problema.

1 Introdução

Nos últimos anos, a necessidade de se resolverem problemas que envolvem um grande número de variáveis, mal definidos e de natureza adaptativa, tem impulsionado a pes­quisa e utilização de novas formas de sistemas de processamento. Tais sistemas têm por objetivo a resolução de problemas intratáveis, ou tratados de forma ineficiente, por sistemas "tradicionais" de computação. Uma das áreas da Ciência da Computação que tem grande interesse na resolução desse tipo de problema é a área de Inteligência Ar­tificial. As técnicas de Inteligência Artificial podem ser divididas em duas abordagens: a simbólica e a não-simbólica.

Na abordagem simbólica (baseada na hipótese do sistema de símbolos físicos [Rich-88]), o conhecimento é armazenado na máquina explicitamente. O programador deve especificar, para cada problema a ser resolvido, a forma de representação do co­nhecimento (determinando as estruturas de dados, suas propriedades e interrelaciona­mento) e as regras de inferência. Isso exige um estudo, às vezes bastante profundo, sobre as peculiaridades do problema a ser resolvido.

IDC - UFSCar - Caixa Postal 676 - S. Carlos-SP 2DEP - UFSCar - Caixa Postal 676 - S. Carlos-SP

- 38-

I SBAI - UNESP - Rio Claro/SP - Brasil

N a abordagem não-simbólica o conhecimento é armazenado na máquina im­plicitamente, e o programador não precisa elaborar um programa diferente para cada tipo de problema. As técnicas usadas para essa abordagem confiam em simulações e re­gras probabilísticas, de aplicação geral, independente do domínio do problema. Deve-se apenas dispor de uma forma de avaliar (numericamente) as soluções candidatas pro­duzidas pelo sistema. Assim, o sistema, trabalhando na .base de tentativa e erro e utilizando alguma forma de retroalimentação do erro, gradativamente "aprende" a pro­duzir soluções cada vez melhores, analogamente ao conceito de "experiência" associado aos seres humanos.

Nesse contexto, Algoritmos Genéticos (AG) podem ser vistos como uma técni­ca da abordagem não-simbólica de Inteligência Artificial, sendo aplicados na resolução de problemas em duas grandes áreas: otimização e aprendizado de máquina.

Este artigo apresenta os princípios básicos dos AG, bem como uma aplicação ao problema da mochila unidimensional irrestrito. Além disso, os resultados computa­cionais obtidos são apresentados, comparados e discutidos.

2 Algoritmos Genéticos

AG constituem uma técnica de busca inspirada no processo de evolução dos seres vivos, baseado na seleção natural de Darwin. Nesta seção, é apresentada uma breve descrição das principais características dos AG. Mais detalhes podem ser encontrados em [Davies-91] e [Goldberg-89].

Como foi definido em [Grefenstette-86], um AG é um procedimento iterativo que mantém uma população de estruturas (chamadas indivíduos ou "strings"), que representam possíveis soluções de um determinado problema. A cada incremento tem­poral (chamado geração), os indivíduos na população at~al são avaliados de acordo com o valor de sua aptidão para solução do problema. Tendo como base essa avaliação, uma nova população de soluções candidatas é formada utilizando operadores genéticos específicos, tais como reprodução, cruzamento e mutação.

Basicamente, esses operadores combinam a sobrevivência dos mais aptos den­tre a população de indivíduos com uma troca aleatória, porém estruturada, de in­formações entre esses indivíduos, de modo que, a cada geração, um novo conjunto de indivíduos é criado usando partes dos indivíduos mais aptos da geração anterior.

Após um grande número de gerações - critério de parada do algoritmo genético - o indivíduo mais apto da última geração é a solução encontrada para o problema. Para resolver um problema através de AG deve-se considerar dois pontos fundamentais:

1. cada solução candidata é representada por um indivíduo, que é uma "string" definida usando um alfabeto finito, de modo que cada "string" represente um conjunto de valores para o conjunto de parâmetros do problema. Um exemplo de alfabeto é o conjunto {O, I}, ou o conjunto de números inteiros. Cada posição da "string" representa um gene.

11. a aptidão de um indivíduo, ou seja, a capacidade de adaptação ao-meio, é um valor não-negativo da qualidade da solução representada pelo in­divíduo. Quanto maior o valor da sua aptidão, melhor é a solução repre-

- 39-

I SBAI - UNESP - Rio Claro/SP - Brasil

sentada por esse indivíduo. Assim, a aptidão, na terminologia de AG, corresponde ao valor da função objetivo, na terminologia de Pesquisa Operacional (referente a problemas de maximização). A aptidão de um indivíduo pode ser vista como o desempenho que esse indivíduo apre­senta na resolução do problema. O sucesso do AG depende da escolha adequada da medida de aptidão.

Reprodução e cruzamento podem ser considerados como os principais ope­radores genéticos, devido a sua ampla utilização e importância para os fundamentos teóricos dos AG. A mutação tem uma importância menor em relação a reprodução e cruzamento, mas também é bastante utilizada . . Esses três operadores são descritos a seguir.

2.1 Reprodução

A reprodução é um processo no qual os indivíduos da população atual são copiados para a população da geração posterior, em quantidades proporcionais à aptidão de cada um, ou seja, ao valor da função objetivo associado a cada indivíduo. As cópias produzidas são submetidas à ação de outros operadores genéticos, para a geração de novos indivíduos. Uma das formas de reprodução mais simples e mais usada é a seleção pela regra da roleta. Essa seleção simula o procedimento de girar uma roleta viciada, onde cada indivíduo da geração atual tem uma fatia da roleta cujo tamanho é propor­cional à sua aptidão. Assim, a probabilidade de que um indivíduo seja selecionado para reprodução, P selecti, é:

p

Pselecti = fi! L fi i=l

onde:

fi = aptidão do indivíduo i

p = número total de indivíduos na população

2.2 Cruzamento

A aplicação do operador de cruzamento consiste em, sendo 1 o comprimento de um indivíduo, selecionar aleatoriamente uma posição inteira k entre 1 e 1-1 (inclusive), e criar dois novos indivíduos, trocando entre os dois indivíduos antigos os caracteres entre a posição k+1 e 1 (inclusive). Por exemplo, considere os indivíduos Sl e S2 abaixo:

Sl = Xl X2 X3 X4 X5 X6

- 40-

I SBAI - UNESP - Rio Claro/SP - Brasil

S2 = Y1 Y2 Y3 Y4 Y5 Y6

Seja escolhido aleatoriamente o ponto de cruzamento k gera dois novos indivíduos SI' e S2':

SI' = Xl X2 X3 Y 4 Y5 Y6

S2' = Y1 Y2 Y3 X4 X5 X6

3, o. cruzamento

o cruzamento pode ser realizado sobre apenas alguns indivíduos, quando se especifica uma probabilidade de cruzamento. São formados aleatoriamente os pares de indivíduos, que são os possíveis "pais" da nova geração. Em seguida, é verificado sobre cada par se eles vão sofrer cruzamento, analogamente ao lançamento de uma moeda viciada que resulta em cara (sucesso) com o valor de probabilidade estabelecido. Se o cruzamento for determinado sobre o par em questão, então a operação é realizada.

2.3 Mutação

A mutação é um operador que modifica o valor de algum gene (escolhido aleatoriamente) de um indivíduo, podendo ser vista como uma política de proteção contra a perda de material genético, ou seja, contra a não exploração de alguma região do espaço de busca. Assim, a mutação tende a aumentar a diversidade genética da população.

Note que nem a reprodução nem o cruzamento criam novos valores de genes. Assim, se uma geração não possui um certo valor de gene em uma determinada posição, e esse valor é essencial para se obter uma boa solução, somente o operador mutação pode produzir esse valor de gene nessa posição [Karr-91]. Tipicamente, a probabilidade de mutação é bastante baixa, na ordem de uma mutação a cada mil genes.

2.4 Principais Diferenças entre Algoritmos Genéticos e Métodos de Busca Convencionais

Os AG diferem das técnicas de busca convencionais em alguns pontos fundamentais, que são:

J. com os AG, a busca da melhor solução para o problema é feita sobre uma população de pontos, e não sobre um único ponto, reduzindo sen­sivelmente o risco da solução recair sobre um máximo (ou minimo) local.

11. AG realizam uma busca cega. A única exigência é o conhecimento do valor da função objetivo de cada indivíduo. Não há necessidade de qualquer outra informação ou heurística dependente do problema.

lll. AG usam operadores estocásticos, e não regras determinísticas, para guiar um busca altamente exploratória e estruturada, onde informações acumuladas nas iterações (gerações) anteriores são usadas para dire­cionar essa busca.

- 41 -

I SBAI - UNESP - Rio Claro/SP - Brasil

Apesar de sua simplicidade, os resultados obtidos com a aplicação do método, segundo [Goldberg-89], permitem concluir que AG são um método de busca robusto -'eficiente e eficaz em uma grande variedade de problemas.

3 O Problema da Mochila Unidimensional Irrestrito

Considere o seguinte problema:

Seja um conjunto de objetos de peso e valor conhecidos. Um alpinista pre­tende carregar sua mochila com a combinação mais valiosa desses objetos, de maneira a não exceder o peso máximo admissível da mochila.

Este problema se enquadra na definição do clássico Problema da Mochila ("Knapsack Problem"). Se a mochila for vista como uma barra, e os objetos como peças, tem-se o Problema do Corte e Empacotamento. Em Pesquisa Operacional, o Problema do Empacotamento (e Corte), genericamente, consiste em empacotar (cor­tar) unidades menores dentro de (a partir de) unidades maiores, de maneira a otimizar certos objetivos [Morábito-92]. Considere, por exemplo, uma barra (unidade maior) e um conjunto de peças (unidades menores), sendo que a combinação mais valiosa de peças devem ser escolhidas e combinadas para formar a barra, ou o processo inverso, onde deseja-se cortar a barra para produzir as peças, maximizando o valor das peças produzidas. No caso do corte de barras, onde uma única dimensão (comprimento) é considerada, esse problema é classificado corno Problema do Corte e Empacotamento Unidimensional. Nesse contexto, tem-se:

ai = número de peças (objetos) i, alocadas na barra (mochila) Vi = valor de utilidade da peça (objeto) i li = comprimento (peso) da peça (objeto) i L = comprimento (peso admissivel) da barra (mochila) Si = densidade da peça (objeto) i, dada por Si = v;/ li

Supondo que as quantidades das peças (objetos) são suficientemente grandes, tal que não restrinja o problema, ou seja, bi 2: lL/ld, i = 1,2, ... ,m, tem-se o Problema da Mochila Unidimensional Irrestrito, dado por:

maXImIzar

sujeito a m

~l 'a' < L ~ I 1_

i=l

- 42-

I SBAI - UNESP - Rio Claro/SP - Brasil

com ai ~ O e inteiro i = 1, ... ,m

As dificuldades para solução do problema são devidas à presença da restrição de integralidade das variáveis. Se não houvesse essa restrição, a solução ótima seria trivial: alocar lL/ljJ unidades da peça j (peça de máxima densidade).

Devido à complexidade dos algoritmos apresentados para a solução desses problemas e a diversidade de casos particulares, autores têm-se preocupado na busca de métodos de solução genéricos e eficientes. Em geral esses problemas têm sido resolvidos utilizando Programação Dinâmica e "Backtracking" [Martello-80].

O estudo do Problema da Mochila Unidimensional é de grande importância, visto que qualquer problema de Programação Linear Inteira pode ser transformado em um Problema da Mochila [Taha-75]. Além disso, esse problema pode ser usado para modelagem de várias aplicações industriais [Morábito-92], tais como:

J. Problema do Carregamento de Veículos

11. Problema de Programação de Veículos

111. Problema de Alocação de Arquivos

4 Aplicando Algoritmos Genéticos ao Problema do Corte de Barras

São descritas aqui as características específicas da implementação do AG para solu­cionar o problema do corte de barras.

4.1 Codificação Genética

Para representar um indivíduo, foi utilizada codificação genética com números inteiros. Cada indivíduo tem m posições, sendo m o número total de peças, e a i-ésima posição do indivíduo (i = 1,2, ... ,m) contém o número representando a quantidade de peças do tipo i que serão cortadas. Esse número varia de O até l L / liJ, que é a quantidade máxima de peças de tamanho li que pode ser cortada a partir do tamanho total L da barra.

4.2 Função Objetivo

Na avaliação da aptidão de cada indivíduo, deve-se determinar uma forma de penalizar o indivíduo que violou o comprimento da barra. Em [Goldberg-89] é sugerido que se use uma penalização, cujo valor é calculado considerando o quanto o indivíduo excedeu no comprimento da barra. Essa penalização é aplicada sobre o valor da função objetivo obtido por aquele indivíduo:

m

li = I>iai - P i=l

- 43 -

I SBAI - UNESP - Rio Claro/SP - Brasil

onde:

p = termo da pen alização

Em [Goldberg-86], foi adotada a seguinte penalização:

p = 50(.,fê)

onde:

e = L~lliai - L se a solução representada pelo indivíduo ultrapassa o comprimento L

e = ° caso con trário

Entretanto, essa formulação ignora a diferença de unidades nos dois termos da equação da função objetivo, pois o primeiro termo (valor total) é dado em unidades monetárias e o termo p em unidades de comprimento. Como resultado, os autores são obrigados a multiplicar o valor do termo p da penalização por uma constante, esco­lhida naquele trabalho como 50, antes de subtraí-la do valor total. Essa constante é dependente da relação entre os valores absolutos das unidades de valor e das unidades de comprimento, que por sua vez, é dependente das instâncias do problema. Para mostrar efetivamente a desvantagem dessa abordagem, considere, como exemplo, que todos os valores das unidades monetárias são multiplicados por 100, e os comprimentos permanecem inalterados. Isso não altera a solução do problema (quantidade de cada peça i,i = 1,2, ... ,m, que deve ser produzida em uma solução ótima). Entretanto, seria necessário adaptar o valor dessa constante aos novos valores (essa constante teria que ser aumentada, caso contrário a magnitude do termo p seria muito pequena em relação à do valor total).

Neste trabalho, a fim de evitar esse inconveniente, definiu-se o termo da pe­nalização p como sendo uma percentagem do valor total obtido pelo indivíduo:

Cabe ressaltar que o valor p da penalização é calculado em função de Vi e li, mantendo a equivalência entre as unidades trabalhadas.

4.3 Reprod ução Elitista

Utilizando uma estratégia de reprodução simples (como a regra da roleta), os processos de cruzamento e mutação podem resultar em um comportamento não-monotônico de aptidão, isto é, pode acontecer que todos os indivíduos de uma geração recém-criada tenham valores de aptidão menores que os valores de aptidão dos melhores indi víduos

- 44-

I SBAI - UNESP - Rio Claro/SP - Brasil

da geração anterior. Para evitar essa situação, implementou-se um operador reprodução que utiliza uma estratégia de seleção elitista, na qual se garante a sobrevivência dos melhores indivíduos da geração atual fazendo-se uma cópia desses indivíduos, que passa inalterada (sem sofrer cruzamento ou mutação) para a próxima geração. Os outros indivíduos da próxima geração são selecionados através da clássica seleção da roleta, e sofrem cruzamento e mutação de acordo com os respectivos fatores de probabilidade.

5 Resultados Computacionais

Nesta seção, são apresentados e comparados os resultados computacionais preliminares, obtidos com a aplicação do AG ao problema do corte de barras.

Para estudar o problema, foram gerados vários exemplos, considerando o comprimento da barra L = 100, o comprimento li das peças gerado no intervalo [0.25L, 0.75L], o valor das peças igual ao comprimento (Vi = li), e o número de gerações igual a 100 e 200. Para cada quantidade m de peças, foram considerados lotes com 80 exemplos cada, gerados aleatoriamente.

Para os valores dos parâmetros do AG, foi utilizada uma população de 65 indivíduos, e a taxa de mutação foi fixada em 0.001 (1 gene a cada 1000).

A qualidade das soluções encontradas pelo AG é definida como uma percenta­gem do valor da solução encontrada, em relação ao valor da solução ótima. A solução ótima foi obtida atravé de Programação Dinâmica. Esses valores são vistos na tabela abaixo:

número de peça$ 10 20 30 40 50

(m) número

de 100 200 100 200 100 200 100 200 100 200 gerações

qualidade $o/ução 97% 98% 90% 93% 90% 91% 88% 95% 87% 94% AG (%)

Tabela 1: Qualidade da Solução Encontrada pelo AG

Os resultados preliminares indicam que a qualidade da solução encontrada pelo AG pode ser melhorada significativamente (especialmente para grandes quantidades de peças), aumentando-se o número de gerações, como era esperado.

Note que a qualidade da solução encontrada pelo AG é reduzida significativa­mente, em problemas com grandes quantidades de peças. Isso pode ser explicado pelo fato de que, como as peças têm comprimento no intervalo [0.25L,0.75L], apenas um número pequeno de peças pode ser cortado a partir da barra. Assim, durante a busca, o AG deve manter indivíduos que possuem poucos genes com valor "útil" (diferente de zero), pois a maioria dos genes deve ter valor zero, a fim de impedir que o indivíduo ultrapasse o comprimento da barra. Note também que no AG descrito anteriormente, o tamanho da população e o número de genes de um indivíduo são fixos, de modo que uma população pode ser vista como uma matriz, de tamanho fixo. Como a maior parte

- 45-

I SBAI - UNESP - Rio Claro/SP - Brasil

dos elementos da matriz (valores de genes) tem valor zero, pode-se ver essa matriz como uma matriz esparsa (no caso específico deste problema).

Assim, uma possível alternativa para melhorar a eficiência do AG neste pro­blema seria utilizar técnicas de codificação genética mais avançadas, nas quais utiliza-se indivíduos com número de genes variável, armazenando-se apenas os genes com valor "útil" (diferente de zero). Essa nova forma de implementação de AG é denominada AG "messy" [Goldberg-93], [Goldberg-90].

Além disso, acredita-se que esses resultados também podem ser melhorados introduzindo-se um pouco de conhecimento sobre o domínio do problema em alguns operadores genéticos, o que tem produzido bons resultados em outros problemas de otimização combinatorial [Grefenstette-85], [Suh-87], [Freitas-93].

6 Conclusões

Neste trabalho, são apresentadas uma introdução à técnica de Algoritmos Genéticos (AG) e a implementação de AG para resolução do problema do corte de barras.

Os resultados preliminares obtidos com AG foram comparados com resultados obtidos com a aplicação de outra técnica de busca exata. A qualidade das soluções encontradas pelo AG foi satisfatória, assumindo-se que é aceitável uma solução quase ótima. Foram apresentadas também duas alternativas para melhorar a qualidade das soluções apresentadas pelo AG para o problema do corte de barras. Essas alternativas serão objetos de pesquisas futuras.

Apesar de AG nem sempre encontrar a solução ótima para o problema, na maioria das vezes ele encontra uma solução quase ótima, o que é aceitável quando se considera um problema complexo. Para esse tipo de problema, onde existe um grande número de restrições matemáticas, muitas vezes os métodos convencionais não se aplicam, devido à dificuldade em tratar essas restrições, aumentando a complexidade da implementação. Utilizando AG, a cada restrição do problema, apenas o cálculo da aptidão de cada indivíduo é modificado, sem que a implementação da técnica se torne mais complexa, pois o funcionamento dos operadores genéticos continua inalterado, mantendo sua simplicidade. Portanto, pode-se verificar a generalidade e a aplicabilidade do AG para modelar problemas complexos, e ainda obter uma solução ótima ou quase ótima para o problema, o que nem sempre é possível com métodos exatos, devido à explosão com binatorial.

Referências

[Davies-91]

[Frei tas-93]

Davies, L. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, 1991.

Freitas, A.A.; Anacleto, J.C.; Kirner, C. Applying Genetic Algo­rithms to the Load-Balancing Problem. Submitted to the XIII ln­ternational Conference of the Chilean Computer Society, Oct. 1983.

- 46-

I SBAI - UNESP - Rio Claro/SP - Brasil

[Goldberg-86]

[Goldberg-89]

[Goldberg-90]

[ Goldberg-93]

(

[Grefenstette-85]

[Grefenstette-86]

[Karr-91]

[Martello-80]

[Morábito-92]

[Rich-88]

[Suh-87]

[Taha-75]

Goldberg, D.E.; Smith, R.E. AI Meets OR: Blind Inferential Search Using Genetic Algorithms. TCGA Report no. 86002, Univ . of Al­abama, Tusca.loosa, U.S.A, 17 p., Oct. 1986.

Goldberg, D.E. Genetic Algorithm in search, optimization, and ma­chine learning. Addison- Wesley Publishing Company Inc., 412p, 1989.

Goldberg, D.E.; Deb, K.; Korb, B. Messy Genetlc Algorithm Revis­ited: Studies in Mixed Size and Scale. Complex Systems Publcations Inc., vol. 4, pp. 415-444, 1990.

Goldberg, D.E.; Deb, K.; Kargupta, H.; Harik, G . Rapid Accurate Optimization of Difficult Problems Using Fast Messy Genetic Algo­rithm. llliGAL Report no. 93004, Univ . of lllinois, Urbana, U.S.A., 16p., Feb. 1993.

Grefenstette,J.J; Gopal, R.; Rosma.ita, B.J.; Van Gutch, D . Genetic Algorithms for The Traveling Salesman Problem. Proc. Int . Conf. Genetic Algorithms and their Applications, pp. 160-168, 1985.

Grefenstette,J .J . Optimization of Contro1 Parameters for Genetic Al­gorithms. IEEE Transaction Systems, Man, and Cybernetics, voI. SMC-16, no. 1, pp. 122-128, 1986.

Karr, C. Genetic Algorithms for Fuzzy Controllers. AI EXPERT, San Francisco, U.S.A., vol. 6, no . 2, pp . 26-33, Feb. 1991.

Martello, S.; Toth, P. Optimal and Canonical Solutions ofthe Change Making Problem. European Journal of Operational Research, vol. 4, pp. 322-329, 1980.

Morábito Neto, R. Uma Abordagem em Grafo E-OU para o Pro­blema do Empacotamento: Aplicação ao Carregamento de Paletes e Contêiners. Tese de Doutorado, EESC- USP, São Carlos, 212p., 1992.

Rich, E. Inteligência Artificial. McGraw-Hill, São Paulo, 503p, 1988.

Suh, J.Y.; Van Gutch, D. Incorporating Heuristic Information into Genetic Search. Proc. 2nd Int. Conf. Genetic AIgorithms, pp. 100-107, 1987.

Taha, H. Integer Programming - Theory, Applications and Compu­tations. Academic Press, New Tork, 1975.

- 47-