Utilizando Algoritmo Genético no Problema do Corte de Estoque Bidimensional Guilhotinado Restrito ^[1]

OLIVEIRA, Jorge Alexandre de

ALVES, Marcus Vinícius Resende Costa

OLIVEIRA, Jorge Alexandre de; ALVES, Marcus Vinícius Resende Costa. Utilizando Algoritmo Genético no Problema do Corte de Estoque Bidimensional Guilhotinado Restrito. Revista Científica Multidisciplinar Núcleo do Conhecimento. Edição 06. Ano 02, Vol. 01. pp 161-227, Setembro de 2017. ISSN:2448-0959

RESUMO

Este trabalho tem como objetivo apresentar uma comparação entre duas implementações avaliando a performance e o desempenho entre o algoritmo exato de Wang e Algoritmo Genético, tendo como parâmetros de comparação a estrutura e os métodos utilizados para  garantir a exatidão apresentada pelo algoritmo de Wang contra os métodos evolutivos do algoritmo genético explicando  detalhadamente a estrutura de seu funcionamento e apresentando de forma clara a sua representação na natureza em seus processos de seleção, cruzamento, mutação e geração de uma nova população, sendo aplicado para a otimização de corte guilhotinado bidimensionais restrito. O problema a ser resolvido pode ser determinado como: dado um número finito de peças retangulares m, de largura w_i e altura h_i a serem obtidos de retângulos maiores de dimensão WxH denominados chapas, encontrar padrões de corte da chapa que atendam a demanda de peças solicitada com o menor desperdício possível. Mesmo tratando-se de uma abordagem heurística, os resultados da aplicação do Algoritmo Genético mostraram-se muito satisfatório quando comparados à solução apresentada por um método exato para o processo de corte bidimensional guilhotinado restrito, como é o caso do algoritmo de Wang.

Palavras-Chave: Corte Guilhotinado Bidimensional Restrito, Algoritmo Genético, Algoritmo de Wang.

1. INTRODUÇÃO

Os problemas de corte começaram a serem pesquisados por volta de 1940, embora os principais estudos tenham surgido nos anos 60. Observa-se que as pesquisas nesta área têm caminhado no sentido de desenvolver técnicas heurísticas adaptadas para a resolução de tais problemas, pois são da classe Não Polinomial – Complexos, e técnicas exatas, que até o momento, não podem ser utilizadas para resolver problemas práticos, caso bidimensional, por questões de eficiência. Na década de 60 surgiram vários trabalhos importantes publicados na área.

As modelagens e métodos de resolução de maior repercussão na literatura foram os publicados por Gilmore e Gomory (1965). Christofides e Withlock (1977) propuseram um método de solução que incorpora programação dinâmica e uma rotina de transporte em uma árvore de busca, para o problema de corte bidimensionxal restrito. O método de solução proposto por Wang (1983) encontra padrões de corte guilhotinado adicionando retângulos sucessivamente. Para reduzir o número de combinações Wang (1983) incluiu parâmetros que tornam possível a rejeição de padrões indesejáveis.

Neste trabalho será utilizado o algoritmo genético para desenvolver uma proposta de solução para o problema de corte de estoque bidimensional guilhotinado restrito. A proposta para solucionar o problema de corte parte da idéia dos problemas enfrentados por empresas que usam esse processo de corte, para isso usou algoritmo genético para poder chegar a uma solução para tal problema. Os algoritmos genéticos são uma família de modelos computacionais inspirados na evolução, que incorporam uma solução potencial para um problema específico numa estrutura semelhante à de um cromossomo e aplicam operadores de seleção e cruzamento a essas estruturas de forma a preservar informações críticas relativas à solução do problema. Normalmente os algoritmos genéticos são vistos como otimizadores de funções, embora a quantidade de problemas para o qual os algoritmos genéticos se aplicam seja bastante abrangente. Nesse trabalho o algoritmo genético é uma busca de subida de encosta estocástica em que é mantida uma grande população de estados. Novos estados são gerados por mutação e por cruzamento, que combina pares de estados da população.

1.1. Objetivo Geral

Propor uma alternativa para garantir o mínimo possível de desperdício em um de cortes em usando como exemplo o beneficiamento em chapas de vidro em uma fábrica de vidros temperados e tendo como base os métodos e funcionamento de algoritmo genético.

1.2. Problema

O presente trabalho inicia-se colocando em foco uma das grandes dificuldades das empresas na gestão de compras e na logística de materiais que possuem processos de corte de estoque bidimensional restrito, dificuldade como a previsão da demanda de material a ser adquirido e a perda do material depois do corte. Otimizar as compras não é algo trivial e requer grande esforço e integração dos departamentos para obtenção de ganhos reais. Estoques desnecessários ou falta de chapas resultam em custos desnecessários ou menor poder de negociação junto aos fornecedores.

O objetivo do presente trabalho é apresentar uma aplicação do algoritmo genético para gerar soluções de maneira eficiente e rápida para o problema de corte. Problema esse que consiste na resolução de padrões de corte de unidades de chapas de maneira a determinar um conjunto de unidades menores, satisfazendo determinadas restrições e minimizando ou limitando a perda.

Em grande parte das indústrias, ainda não é possível prever quanto de chapas será consumida para atender uma determinada ordem de produção. A falta de ferramentas de apoio ao departamento de PCP (Planejamento e Controle da Produção) e aos operadores das máquinas é uma das principais causas. Somente após todo o processo de corte ser realizado é que será possível saber a perda da chapa, que é o material que não será usado depois do corte.

Durante a etapa de corte de estoque bidimensional guilhotinado restrito, a sequência em que as peças serão cortadas a partir das chapas irá determinar o grau de aproveitamento do material. Com grandes quantidades de peças fica impraticável se obter um alto índice de aproveitamento, sem auxílio de ferramentas de apoio.

1.3. Hipótese

Será utilizada uma aplicação do algoritmo genético para a resolução do problema gastando-se menos tempo e com uma perda considerável e com isso compará-lo ao método exato de Wang (1983), como o objetivo de apresentar uma aplicação satisfatória.

1.4. Visão geral do trabalho

No capítulo 2 será feito um levantamento bibliográfico do problema de corte de estoque bidimensional restrito, a utilização do método de busca local, uma explicação do que é o algoritmo genético e sobre o algoritmo de Wang (1983) no qual será feito uma comparação. No capítulo 3 será apresentado o desenvolvimento do trabalho, a representação do problema utilizando algoritmo genético, as partes que envolvem o algoritmo genético, como cromossomos, cruzamento, mutação e seleção. Na seqüência no capítulo 5 serão feitos os testes e apresentação dos resultados e as comparações com o algoritmo de Wang (1983). Finalizando o trabalho, serão apresentadas as conclusões.

2. LEVANTAMENTO BIBLIOGRÁFICO

2.1. O Problema de Corte de Estoque Bidimensional Guilhotinado Restrito

O problema de corte de estoque bidimensional guilhotinado restrito além de ser um problema de difícil solução exata, ele é importante em diversos processos industriais de corte de chapas retangulares. Como é apresentado no artigo (Cláudia Maria, Celso Junior e Marcelo Rocha (2004)) que as indústrias deparam-se frequentemente com o problema de se cortar chapas inteiras em pedaços menores geralmente solicitados por clientes ou setores internos. É necessário planejar os cortes para minimizar gastos que levam a utilização de um maior número de peças grandes, aumentando os custos de produção. O problema de corte de estoque bidimensional guilhotinado restrito é um problema tipicamente presente em indústrias como vidro, aço, madeira, alumínio, placas de circuito impresso dentre outras. O problema é de estoque porque utiliza peças presentes no estoque da empresa para serem colocados na chapa, é bidimensional porque envolve duas dimensões relevantes para a solução, a altura e a largura das chapas, é guilhotinado devido às restrições impostas pelos equipamentos, os cortes ao serem realizados sobre um retângulo, corta de uma extremidade a outra produzindo dois retângulos, e é restrito porque há uma restrição dada pelo tamanho da chapa, ou seja, sua altura e largura. O problema consiste em obter geometricamente peças em chapas inteiras de modo a atender à demanda, acelerando a produção e minimizando as perdas. Essa obtenção das peças é chamada padrão de corte. Associadas ao problema estão às restrições físicas, relativas às duas dimensões das chapas, e as restrições encontradas nas situações práticas, relativas aos tipos de corte, que definem a disposição das peças sobre a chapa. Ao tratar desse problema e analisando métodos chegamos a alguns exemplos de autores como Wang (1983), que propôs um método heurístico que combina peças em arranjos horizontais e verticais para formar padrões de corte; em Vasko (1989) e Oliveira e Ferreira (1990), que apresentaram refinamentos do algoritmo de Wang (1983); Christofides e Whitlock (1977), que apresentaram um algoritmo de busca em árvore que utiliza uma rotina baseada no problema de transporte para obter limitantes durante a busca.

2.1.1. Conceito e Definições

• Demanda:

Demanda representa a quantidade de itens que devem ser obtidos dos objetos maiores, como por exemplo, as peças que deverão ser cortadas em uma chapa de aço.

• Peças:

Como visto na tese de Franceschette (Franceschette (2008)), chama-se de peças pequenos retângulos (Fritsch, 1995) que são itens de uma demanda de pedidos em uma linha de produção, que devem ser projetados sobre uma lâmina (Daza, 1995) (Oliveira, 1990) denominada aqui de chapa. No caso deste trabalho, as peças e as chapas são regulares, formadas por retângulos ortogonais (Morabito, 1995). As peças não regulares possuem formas não convexas, não simétricas, ângulos diferentes, quantidade de lados variados podendo ter retas ou curvas (Fritsch, 1995).

• Padrão de Corte:

O arranjo das peças na chapa é denominado de “plano de corte” e, quando este plano é utilizado mais de uma vez, é denominado de “padrão de corte”. Neste trabalho usam-se tais conceitos como sinônimos.

• Corte Guilhotina:

O tipo de corte é considerado guilhotina quando este percorre a placa de um lado ao outro, ou seja, após o corte são produzidos dois retângulos como está representado na Figura 1 (Farney, 1990) (Morabito, 1997) (Morabito, 1995) (Morabito, 1996). Quando o corte é do tipo guilhotina, diz-se que o padrão de corte é do tipo guilhotina.

Na Figura 2 o padrão gera cinco retângulos e neste caso o corte é considerado não guilhotina, isso porque, cada um dos cortes não pode percorrer a chapa de um lado outro.

No padrão de corte guilhotina, o primeiro corte normalmente é paralelo ao lado mais curto da chapa, para isso, deve-se observar a estrutura da guilhotina. O segundo corte é feito no sentido oposto ao primeiro, representando assim, uma seqüência de estágios sucessivos (Silva, 2005). Dois fatores definem a prioridade de cada corte, um deles é a largura da guilhotina, o outro é a dimensão das peças que deve ser respeitada de forma que estas não sejam danificadas durante utilização da guilhotina. Na Figura 3 os números representam os estágios de corte e as setas à incisão da guilhotina.

O corte pode ser restrito ou irrestrito. Restrito é em relação a restrição dada pelo tamanho da chapa a ser cortada, e é irrestrito quando não existe este limite. À medida que as peças são combinadas na chapa, entre elas pode haver um espaço não aproveitado, que se chama desperdício interno (Vasko, 1989). Isso ocorre normalmente em função das dimensões das peças serem diferentes. Caso as peças tenham dimensões iguais, e/ou os lados de uma peça toquem os lados de outras peças de forma a não deixar espaço entre elas, então, o desperdício interno não existe. O desperdício externo ocorre quando o espaço está além do conjunto de peças já projetadas e nele não cabe mais nenhuma outra peça na parte externa da chapa. Observa-se na Figura 4.

Segundo Christofides (Christofides, 1995) o corte pode ser normalizado ou corte não normalizado. O corte é normalizado quando uma peça é projetada ao lado da outra e tem um de seus lados encostado a esta, ou seja, entre as peças não tem área de desperdício interno, como mostrado na Figura 5.

Para a utilização de guilhotina, o corte deve ser ortogonal, ou seja, quando as peças regulares são projetadas, um de seus lados é paralelo a um dos lados da chapa. O corte ainda pode ser classificado como homogêneo, quando peças a serem projetadas têm as mesmas dimensões e não homogêneo, quando tais peças possuem dimensões diferentes (Araujo,2006). Também é preciso que se faça um controle para que a soma da área da próxima peça projetada mais a área das peças já projetadas, não ultrapassem a largura e a altura da chapa, e dessa forma o corte seja possível.

• Restrito:

É quando a uma restrição dada pelo tamanho da chapa a ser cortada.

• Objetivos da resolução de um problema de corte guilhotina:

Os objetivos de um problema de corte guilhotina estão relacionados ao que se deseja otimizar no problema, dessa forma, o objetivo pode ser maximizar o total da área ocupada, o que é o equivalente a minimizar áreas em desperdício, ou então pode ser maximizar o valor total de pedaços cortados independente da área. Dessa maneira, um problema de corte guilhotinado consiste em um conjunto de peças retangulares, cada uma com um dado valor e tamanho que devem ser cortadas em uma chapa retangular principal, no qual o objetivo pode ser:

• Maximizar o valor de peças cortadas;
• Minimizar o desperdício nos padrões;
• Determinar a melhor sequência de cortes;
• Determinar soluções exatas;
• Determinar soluções aproximadas;

Qualquer um destes objetivos pode estar sujeito a restrições quanto ao número de peças, demanda número de guilhotinas e tempo disponível para o trabalho. Ainda pode-se ter a combinação de dois ou mais objetivos. Este trabalho está concentrado em encontrar padrões de corte de modo a minimizar o desperdício e atender à demanda.

2.2. Algoritmo Exato de Wang

Para este problema, Wang (1983) descreveu dois algoritmos construtivos que geram os padrões de corte combinando retângulos de R. O método utilizado emprega a seguinte terminologia: Uma Construção horizontal de dois retângulos A₁ = p₁ x  q₁ e A₂ = p₂ x q₂ é um retângulo S_u que tem dimensões Max(p₁, p₂) x (q₁ + q₂) e contém A₁ e A₂. Uma Construção vertical de A₁ e A₂ é o retângulo S_v de dimensões (p₁ + p₂) x Max(q₁, q₂). Um exemplo de S_u e S_v é dado na Figura 6. Nenhuma dimensão de S_u ou de S_v deve ultrapassar H ou W.

Wang utiliza dois parâmetros b₁ e b₂ para determinar a perda máxima aceitável em um retângulo T gerado no algoritmo. O primeiro algoritmo utiliza b₁ que é calculado a partir da placa de estoque H x W, e o segundo algoritmo utiliza b₂ que é calculado a partir da área a(T) de T. O procedimento combina os pares de retângulo R₁, R₂, …, R_n em construções horizontais e verticais. O algoritmo adiciona o retângulo gerado ao retângulo original R_i para formar um retângulo de corte guilhotinado maior. O processo é repetido e cada nova construção horizontal ou vertical forma-se um novo retângulo guilhotinado maior a partir de dois retângulos guilhotinados menores.

• Algoritmo 1

 

Passo 1.           a. Escolha um valor parab₁, 0 £ b₁ £ 1.

1. Defina L⁽⁰⁾ = F⁽⁰⁾ = {R₁, R₂, …, R_n}, e faça k = 1.

Passo 2.           a. Compute F^(k) com o conjunto de todos os retângulos T que satisfaçam

• T é formado por uma construção horizontal ou vertical de dois retângulos de
  L^(k-1),
• A perda acumulada em T não excede a b₁HW, e
• Os retângulos R_i não aparecem em T não violam a restrição de demanda b_i.

1. Faça L^(k) = L^(k-1) È F^(k). Remova padrões repetitivos de L^(k).

Passo 3   Se F^(k) não estiver vazio, faça k = k – 1 e vá para o Passo 2, caso contrário,

Passo 4   a.  Faça M = k – 1.

1. Escolha o retângulo de L^(M) que possua a menor perda total quando colocado na folha de estoque H x W.

• Algoritmo 2

Para o Algoritmo 2, faz-se a seguinte modificação: troca-se b₁ do Algoritmo 1 por b₂ no Passo 1. a. e troque o Passo 2.a.(ii) por: A perda acumulada em T não excede a b₂a(T).

Em todas as implementações apresentadas aqui, a entrada de dados é feita através de um arquivo que contém as o número de retângulos, as dimensões da placa, o percentual de perda aceitável, o número de cada retângulo (peça) a ser cortado, suas dimensões e sua demanda, a estrutura deste arquivo é apresentada na Figura 7 e a extensão do arquivo deve ser um documento .txt.

2.3. Método de Busca Local

Como visto no livro de Russel (2004), o método de busca local opera usando um conjunto de estados corrente (em vez de vários caminhos) e em geral se movem apenas para os vizinhos dos estados pertencentes ao conjunto. Normalmente, os caminhos seguidos pela busca não são guardados. Embora os algoritmos de busca local não serem sistemáticos, eles têm duas vantagens: usam pouquíssima memória que quase sempre um valor constante e frequentemente pode encontrar soluções razoáveis em grandes ou infinitos espaços (contínuos) de estados para os quais os algoritmos sistemáticos são inadequados.

Além de encontrar objetivos, os algoritmos de busca local são úteis para resolver problemas de otimização que seria o caso abordado nesse trabalho, esses problemas que nos quais o objetivo é encontrar o melhor estado, ou seja, a melhor otimização para que não haja perda de material, de acordo com uma função objetivo. Para entender a busca local, é muito útil considerar a topologia de espaço de estados. Uma topologia tem ao mesmo tempo “posição” (definida pelo estado) e “elevação” (definida pelo valor da função objetivo). Se a elevação corresponder ao custo, o objetivo será encontrar o vale mais baixo, ou seja, a perda considerável, um mínimo global; se a elevação corresponder a uma função objetivo, que seria a menor perda possível para tal distribuição das chapas, então o objetivo será encontrar o pico mais alto, um máximo global. Os algoritmos de busca local exploram essa topologia. Um algoritmo de busca local completo sempre encontra um objetivo, caso ele exista. Nesse trabalho iremos utilizar esse método para poder chegar a uma solução para que não haja perda da chapa inteira a ser cortada a partir dos tamanhos das peças desejadas, se houver perda, que seja no limite aceitável para tal.

2.4. Algoritmo Genético

Como descrito no artigo de Miranda (Miranda (2009)), os Algoritmos Genéticos (Goldberg, 1989) são métodos de otimização e busca inspirados nos mecanismos de evolução de população de seres vivos. Os algoritmos baseados nesta técnica seguem o princípio da seleção natural e sobrevivência do mais apto. De acordo com Charles Darwin, “Quanto melhor um indivíduo se adaptar ao seu meio ambiente, melhor será sua chance de sobreviver e gerar descendentes”. As técnicas de busca e otimização geralmente apresentam:

– um espaço de busca, onde estão todas as possíveis soluções do problema;

– uma função objetiva, que é utilizada para avaliar as soluções produzidas, associando a cada uma delas uma nota.

Miranda (Miranda (2009)) ainda diz que a otimização consiste em achar uma solução que corresponda ao ponto de máximo ou mínimo da função objetivo. Se a função for de maximizar, deseja-se encontrar o ponto de máximo, caso contrário, deseja-se encontrar o ponto de mínimo. Como se deseja a minimização do desperdício que é gerado no encaixe das peças na chapa retangular, espera-se encontrar o ponto de mínimo da função objetivo. Os algoritmos genéticos simples normalmente trabalham com descrições de entrada formadas por cadeias de bits de tamanho fixo. Outros tipos de algoritmos genéticos podem trabalhar com cadeias de bits de tamanho variável, como por exemplo, algoritmos genéticos usados para Programação Genética. Os algoritmos genéticos possuem um paralelismo implícito decorrente da avaliação independente de cada uma dessas cadeias de bits, ou seja, pode-se avaliar a viabilidade de um conjunto de parâmetros para a solução do problema de otimização em questão. O algoritmo genético é indicado para a solução de problemas de otimização complexos, NP – Complexos, como o “caixeiro viajante”, que envolvem um grande número de variáveis e, consequentemente, espaços de soluções de dimensões elevadas. Além disso, em muitos casos onde outras estratégias de otimização falham na busca de uma solução, os algoritmos genéticos convergem. Os algoritmos genéticos são numericamente robustos, ou seja, não são sensíveis a erros de arredondamento no que se refere aos seus resultados finais.

Existem três tipos de representação possíveis para os cromossomos: binário, inteiro ou real. A essa representação se dá o nome de alfabeto do algoritmo genético. De acordo com a classe de problema que se deseje resolver pode-se usar qualquer um dos três tipos. Uma implementação de um algoritmo genético começa com uma população aleatória de cromossomos. Essas estruturas são, então, avaliadas e associadas a uma probabilidade de reprodução de tal forma que as maiores probabilidades são associadas aos cromossomos que representam uma melhor solução para o problema de otimização do que àqueles que representam uma solução pior. Figura 8 ilustra dois cromossomos em forma binária.

O fitness da solução é tipicamente definido com relação à população corrente. A função objetivo de um problema de otimização é construída a partir dos parâmetros envolvidos no problema. Ela fornece uma medida da proximidade da solução em relação a um conjunto de parâmetros. Os parâmetros podem ser conflitantes, ou seja, quando um aumenta o outro diminui. O objetivo é encontrar o ponto ótimo. A função objetivo permite o cálculo do fitness de cada indivíduo, que fornecerá o valor a ser usado para o cálculo de sua probabilidade de ser selecionada a próxima geração.

Com referência a Figura 9, observa-se que cada iteração do algoritmo genético corresponde à aplicação de um conjunto de quatro operações básicas: cálculo do fitness, seleção, cruzamento e mutação. Ao fim destas operações cria-se uma nova população, chamada de geração que, espera-se, representa uma melhor aproximação da solução do problema de otimização que a população anterior. A população inicial é gerada atribuindo-se aleatoriamente valores aos genes de cada cromossomo. O fitness bruto de um indivíduo da população é medida por uma função de erro, também chamada de função objetivo do problema de otimização. O fitness bruto é em seguida normalizado (fitness normalizado), para permitir um melhor controle do processo de seleção. Como critérios de parada do algoritmo em geral são usados o fitness do melhor indivíduo em conjunto com a limitação do número de gerações. Outros critérios podem envolver, por exemplo, um erro abaixo de um valor especificado pelo projetista para um determinado parâmetro do problema.

A estrutura básica do algoritmo genético é mostrada na Figura 9 abaixo:

O inicio é com uma população de n indivíduos são gerados aleatoriamente. Cada um dos indivíduos da população representa uma possível solução para o problema, ou seja, um ponto no espaço de soluções. Geralmente o fitness do indivíduo é determinado através do cálculo da função objetivo, que depende das especificações de projeto. Nesta explicação, cada indivíduo é uma entrada para uma ferramenta de análise de desempenho, cuja saída fornece medidas que permitem ao algoritmo genético o cálculo do fitness do indivíduo.

• Seleção

Na fase de seleção os indivíduos mais aptos da geração atual são selecionados. Esses indivíduos são utilizados para gerar uma nova população por cruzamento. Cada indivíduo tem uma probabilidade de ser selecionado proporcional ao seu fitness. Para visualizar este método considere um círculo dividido em n regiões (tamanho da população), onde a área de cada região é proporcional ao fitness do indivíduo. Colocam-se sobre este círculo uma “roleta” com n cursores, igualmente espaçados. Após um giro da roleta a posição dos cursores indica os indivíduos selecionados. Este método é denominado amostragem universal estocástica. Evidentemente, os indivíduos cujas regiões possuem maior área terão maior probabilidade de serem selecionados várias vezes. Como consequência, a seleção de indivíduos pode conter várias cópias de um mesmo indivíduo enquanto outros podem desaparecer.

• Cruzamento

O cruzamento opera em determinados genes dos cromossomos dos pais e cria novas descendências. A maneira mais simples de fazer isso é escolher aleatoriamente alguns pontos de cruzamento e copiar tudo o que vem antes desse ponto de um dos pais e então copiar tudo o que vem depois desse ponto do outro pai. Um novo cromossomo é gerado permutando-se a metade final de um cromossomo com a metade final do outro. Deve-se notar que se o cromossomo for representado por uma cadeia de bits, o ponto de corte pode incidir em qualquer posição (bit) no interior de um gene, não importando os limites do gene. No caso de genes representados por números reais, a menor unidade do cromossomo que pode ser permutada é o gene. Há outras maneiras de fazer cruzamento. Por exemplo, pode escolher mais pontos de cruzamento. O cruzamento pode ser um pouco complicado e depender principalmente da codificação dos cromossomos. Cruzamentos específicos feitos para problemas específicos podem melhorar o desempenho dos algoritmos genéticos.

• Mutação

Depois que um cruzamento é realizado, acontece à mutação. A mutação tem a intenção de prevenir que todas as soluções do problema dessa população caiam em um ponto ótimo local. A operação de mutação muda aleatoriamente a descendência criada pelo cruzamento. No caso de uma codificação binária, podemos mudar aleatoriamente alguns bits escolhidos de 1 para 0, ou de 0 para 1. A técnica da mutação, da mesma forma que a do cruzamento, depende muito da codificação dos cromossomos. Por exemplo, quando codificamos permutações, mutações podem ser realizadas como uma troca de dois genes.

3. DESENVOLVIMENTO

Nesse capítulo será descrito um algoritmo genético moldado ao problema de corte de estoque bidimensional guilhotinado restrito. Serão colocadas as restrições que foram consideradas e as técnicas usadas.

Foi utilizada a linguagem C# junto com o programa Visual Studio 2010 para o desenvolvimento dos algoritmos.

3.1. Representação do Problema Utilizando Algoritmos Genéticos

Considere o caso da minimização de perda de material, quando se deseja cortar a partir de chapas retangulares, um conjunto de peças menores, com forma e quantidades máximas pré-estabelecidas, de maneira a minimizar a perda de material envolvida e o número de peças grandes utilizadas no processo. Devido à geometria das peças e do tipo de corte envolvidos, limitaremos a classe de cortes de estoque bidimensional guilhotinado restrito. Uma proposta para a solução do problema descrito é um padrão de corte, ou seja, uma combinação de retângulos, retirados do conjunto de retângulos pedidos, que pode ser cortada da uma chapa onde o número de vezes que um retângulo pode aparecer é limitado. Um padrão de corte estará então completamente definido pela sua altura, largura e pelo número de vezes que cada retângulo aparece.

Considere-se então a seguinte notação:

W – largura da chapa;

H – altura da chapa;

m – número de retângulos diferentes a cortar;

w_p – largura do padrão de corte;

h_p – altura do padrão de corte;

w_i – largura do retângulo i;

h_i – altura do retângulo i;

b_i – número máximo de vezes que o retângulo i pode ser usado;

x_i – número de vezes que o retângulo i é efetivamente usado num padrão de corte.

Os dados de corte, placa, padrões a serem cortados, demanda e percentual de perda permitida, vem do arquivo de padrão de corte. A Figura 10 apresenta um padrão de corte com as restrições consideradas, e ilustra parte da notação definida.

A solução ótima deste problema é um padrão de corte, como foi acima definido, que minimiza a perda, isto é, que é a solução do seguinte modelo:

 

Foram utilizadas para a construção de um padrão de corte arquivos de texto separado por tabulação, onde a primeira linha representa a chapa e as demais linhas representam as peças. A Tabela 1 representa o arquivo G0101 que será usado como exemplo. Esse arquivo contém a chapa inteira com dimensões H = 40 que é a altura por H = 70 que é a largura, considerando 10% de perda, sendo que se houver um padrão que ultrapasse esse valor ele é eliminado na pré-seleção. Nesta chapa pretende-se cortar 2 peças com as dimensões h₁ = 4 (altura) por w₁ = 11 (largura), 4 peças com h₂ = 39 (altura) por w₂ = 37 (largura), 5 peças com h₃ = 11 (altura) por w₃ = 44 (largura), 4 peças com h₄ = 35 (altura) por w₄ = 9 (largura) e 2 peças com h₅ = 28 (altura) por w₅ = 7 (largura).

CHAPA
QTD DE PEÇAS m	ALTURA H	LARGURA W	% DE PERDA
5	40	70	10
PEÇAS
Nº	ALTURA hi	LARGURA wi	QTD bi
1	4	11	2
2	39	37	4
3	11	44	5
4	35	9	4
5	28	7	2

Tabela 1 – Dimensões e demandas

A Figura 11 mostra um exemplo com um padrão de corte com uma peça de 4 por 11, três peças de 35 por 9 e duas peças de 4 por 11. A área em vermelho é o desperdício gerado nesse padrão.

3.1.1. Cromossomos

Cromossomo (genótipo) é uma cadeia de bits que representa uma solução possível para o problema. Deve ser observado que cada cromossomo, chamado de indivíduo no algoritmo genético, corresponde a um ponto no espaço de soluções do problema de otimização. Quando se faz um conjunto dessas peças, assim gerando um padrão de corte, esse padrão de corte é o cromossomo. Para gerar a população inicial é utilizado o um método randômico. Nesse trabalho foram desenvolvidos utilizando a codificação binária, em que cada cromossomo é um vetor, composto por zeros e uns, com cada bit representando um gene. Gerado o padrão de corte, esse receberá um número inteiro correspondente aos números binários contido nele. Os números binários significam que determinada peça está ou não contida no padrão gerado, ou seja, o um significa que está contida e o zero que não está contida. Após a geração da população inicial, será feito uma pré-seleção, que elimina os padrões que já estouraram o tamanho da placa, essa pré-seleção foi adaptada no algoritmo que os padrões de corte que estourassem a placa não fossem usados no cruzamento e na mutação, ou seja, um filtro.

O fitness total é calculado depois da obtenção de todos os cromossomos, esse valor é a média das áreas de todos os padrões que foram gerados na população inicial. Essa média é guardada para ser comparada ao fitness gerado depois do cruzamento e mutação, para que possa observar se houve ou não evolução. Na Figura 12 ilustra um exemplo da geração da população inicial.

3.1.2. Seleção

Depois de gerado a população inicial, calcula-se o fitness dessa população, logo após há uma pré-seleção para ver se houve padrões que ultrapassaram a área total da chapa, se sim, estes serão eliminados, se não, eles seguirão para os operadores genéticos de cruzamento e mutação. Com o conjunto gerado depois das operações genéticas, faz-se a seleção dos melhores padrões, ou seja, aqueles que tiverem as maiores áreas.  Com isso têm-se dois conjuntos: o que foi gerado na interação anterior (ou no estado inicial) e o que obteve aplicando as operações genéticas. Para determinar os novos indivíduos dessa nova população, primeiramente são listados todos os cromossomos por ordem decrescente de suas áreas. Quanto maior o a área, melhor é aquele padrão de corte. Concateno essa nova população com a anterior (ou do estado inicial) e escolho os melhores indivíduos, essa nova população terá o mesmo número de indivíduos que a população inicial. Com essa nova população, calcula-se o valor do fitness (média da área do conjunto). Espera-se conseguir uma população com valores de fitness melhores a cada geração, com isso chegando cada vez mais perto da solução do problema. O critério de parada do algoritmo genético é quando não houver mais evolução, ou seja, comparando-se o fitness deste novo conjunto com o fitness do conjunto anterior, se for melhor, retorna na operação de cruzamento fazendo todas as operações novamente, senão, chegasse ao critério de parada. Contudo isso não significa chegar à melhor solução, mas sim apresentar uma melhora nos valores de fitness a cada nova geração, apresentando os melhores indivíduos para a solução do problema.

3.1.3. Cruzamento

Para a aplicação do operador cruzamento, há uma conversão do número inteiro dos padrões gerados para sua representação em binário. Com isso, os cromossomos são reunidos em duplas e determina-se por sorteio um ponto de cruzamento entre os padrões selecionados, realiza-se então, a troca de informações genéticas (genes). Se caso houver um conjunto de padrões ímpar, o último é cruzado com o primeiro para garantir que todos serão cruzados. Nas Figuras 13 e 14 mostra o processo de cruzamento.

A partir do cruzamento o cromossomo 1 é escrito novamente utilizando-se a informação contida no cromossomo 2, o mesmo acontece com o cromossomo 2. Como resultado desses cruzamentos obtém-se dois cromossomos, cada um com seu fitness recalculado. O resultado do é uma população do mesmo tamanho da população de anterior e o algoritmo só conclui uma geração quando esta estiver do tamanho da geração anterior. Nessa nova população ocorrerá o processo de mutação

3.1.4. Mutação

O operador de mutação é necessário para a introdução e manutenção da diversidade genética da população. No presente trabalho foram mutados 5% da população nova gerada após o cruzamento. A mutação pode ocorrer dentro de um cromossomo em qualquer dos seus genes. No ponto escolhido aleatoriamente, o gene é trocado, se caso for 1, ele passa a ser 0, se for 0 passa a ser 1. Na Figura 15 mostra o gene sendo mutado.

Logo depois da aplicação desse operador, é feito uma nova pré-seleção para eliminar os padrões ultrapassaram o tamanho da placa.

Terminado o operador de mutação, retorno para o operador de seleção. Quando obtenho um conjunto que possuem os melhores indivíduos, verifico se existem padrões que atendam as exigências de perda pela heurística (área da placa), caso tenha um padrão, verifico se um este pode ser guilhotinado, senão, verifico outro, assim por diante, até achar um que atenda as exigências e que seja guilhotinado. Na Figura 16 mostra um fluxograma representando passo a passo do nosso algoritmo.

4. TESTES E RESULTADOS

Para os testes o software Visual Studio 2010 gera um executável, este por sua vez precisa do framework .Net Fx40 Full para ser executado e assim gerando os testes. Foi utilizado um notebook com processador Intel Core2Duo T7300, com memória de 2Gb e com o sistema operacional Windows Seven Profissional Edition 32Bits.

Observa-se a seguir alguns testes e resultados aplicando-se as mesmas operações genéticas, levando-se em consideração algumas variações:

• Variação no número de iterações do algoritmo genético.
• Variação na demanda e no número de peças;
• Variação no percentual de perda de cada padrão;

O Algoritmo de Wang e o Algoritmo Genético foram testados em dois grupos diferentes de padrões. Cada grupo com cinco instâncias diferente. Cada padrão (arquivo) contém na primeira linha, o número de quantos cortes diferente, a altura e a largura da chapa que deverá ser cortada e a porcentagem de perda aceitável. Nas demais linhas mostram o primeiro corte, com sua altura, largura e quantidade a ser cortada e assim por diante.

Teste 1:

No teste 1, utilizou-se os padrões de corte do Grupo 01. A Tabela 2 mostra seus resultados.

Padrão	HxW da Chapa (Área)	% Aceitável de Perda	Nº Cortes	Área Ocupada		Tempo Médio de Execução (milisegundos)
				Algoritmo Genético	Wang	Algoritmo Genético	Wang
G0101	53×65 (3445)	10%	12	3378	3392	250,0143	21484,608
G0102	40×70 (2800)	10%	15	2532	2640	803,453	1142,048
G0103	40×70 (2800)	10%	16	2645	2760	2036,285	5110,111
G0104	50×100 (5000)	8%	12	4917	5000	254,013	1890,021
G0105	50×100 (5000)	8%	15	4730	4900	301,014	7263,415

Tabela 2 – Resultados do Padrão de Corte do Grupo 01

Foram observadas nestes testes que o tempo e a área ocupada pelos dois algoritmos são as mais relevantes para serem comparados. Mesmo que o Algoritmo de Wang ocupe uma maior área na chapa, ele gasta maior tempo para se chegar a solução, já o Algoritmo Genético, levando em consideração a porcentagem de perda aceitável, traz a resolução do problema de forma mais rápida.

Nas Figuras 17 e 18 mostram um exemplo de como as peças foram cortadas na chapa no padrão G0102, no Algoritmo de Wang e no Algoritmo Genético respectivamente.

Teste 2:

Já no teste 2, utilizou-se os padrões de corte do Grupo 02. A Tabela 3 mostra seus resultados.

Padrão	HxW da Chapa (Área)	% Aceitável de Perda	Nº Cortes	Área Ocupada		Tempo Médio de Execução (milisegundos)
				Algoritmo Genético	Wang	Algoritmo Genético	Wang
G0201	15×10 (150)	6%	18	148	150	424,024	48165,914
G0202	50×40 (2000)	10%	14	1922	2000	6249,908	21448,606
G0203	40×60 (2400)	10%	12	2304	2304	252,675	1053,637
G0204	50×70 (3500)	9%	18	3264	3264	335,0191	1481,087
G0205	50×95 (4750)	8%	13	4601	4555	234,097	1745,987

Tabela 3 – Resultados do Padrão de Corte do Grupo 01

Com a geração destes testes acima descritos, foram observadas uma diferença considerável da média de tempo entre o Algoritmo de Wang e o Algoritmo Genético, principalmente nos dois primeiros padrões. Há de observar também que no padrão G0203 e G0204 os dois algoritmos obtiveram áreas iguais ocupadas, mas com a diferença de o Algoritmo Genético ter sido mais rápido para a solução do problema. Devemos levar em consideração por parte dos testes, que o Algoritmo Genético, como ele testa se o padrão de corte é guilhotinado ou não somente no final, alguns resultados deram como insuficientes para a solução do problema, tendo assim ter sido executado novamente até a obtenção do resultado requerido.

CONCLUSÃO

Com base nos teste realizados pudemos  observar que que nos testes realizados pelo algoritmo genético obtivemos um resultado satisfatório levando em consideração o tempo , pois nos deu uma resposta dentro dos  parâmetros desejados de maneira rápida comparada ao algoritmo de Wang, dá-se pelo motivo do algoritmo genético ter como função principal o seu  pico de evolução  parado de fazer novas tentativas no momento  em que não há evolução apresentando assim a ultima evolução e  verificando se  o resultado pode satisfazer a condição  de guilhotinado ou não, já o algoritmo de Wang nos apresentou um resultado exto, pois em seu processo todas as  tentativas(combinações ) são realizadas  e consequentemente tomando muito tempo e tendo alto consumo de memória, em alguns dos testes realizados tivemos uma diferença de no  valor obtido pelo Wang contra o genético de 113 vezes maior  ou seja o em um cálculo de 18 cortes que demorou 5 segundos no genético, no Wang  durou 565 segundos ( 9 minutos e 42″), uma diferença  muito grande, cabendo assim a escolha do algoritmo de acordo com o ramo de atividade em que deveria ser pesado em uma balança todos os testes possíveis contra  o tempo.

 REFERÊNCIAS 

ALVARENGA, Arlindo Gomes; PARADA Victor, CARNEIRO, Sebastião A. Problema de Corte via Algoritmo Genético. Universidad de Concepición- Concepición-Chile.1990.

ARAUJO, Olinto César Bassi. Problema de Corte e Empacotamento Tridimensional e Integração com Roteamento de Veículos. Tese de Doutorado. Campinas, SP, 2006.

BARCELLOS, J.C.H., Algoritmos Genéticos Adaptativos: um estudo comparativo.

BARROS, CLÁUDIA M. P., JUNIOR, CELSO L., ROCHA, MARCELO L. (2004) Uma Metaheurística Grasp Aplicada Ao Problema De Corte Guilhotinado Bi-Dimensiona.2: 2-4.l

CHAVES, A. A. et al., Modelagens Exata e Heurística para Resolução do Problema do Caixeiro Viajante com Coleta de Prêmios. XXIV Encontro Nacional de Engenharia de Produção, p.3151-3158, 2004.

CHRISTOFIDES, N., WHITLOCK C., An algorithm for Two-dimensional cutting problems. Operacional Reserarch 25 (1977), 30 – 44.

DARREL WHITLEY, “A Genetic Algorithm Tutorial”, Computer Science Department, Colorado State University Dissertação de Mestrado. São Paulo, EPUSP, 2000.

DAZA, V.P; ALVARENGA, A. G.;DIEGO J. Exact Solutions For Constraint Two – dimensional cutting Problems European Journal of Operational Research 83, 633-644. 1995.

FARLEY, Alan A. Selection of Stockplate characteristics and cutting style for two dimensional Cutting style for two dimensional cutting stock situations. European Journal of Operation Research 44 239-246. Alemanha. 1990.

FRANCESCHETTE, Cláudia. Uma Abordagem Heurística Para O Problema De Corte Guilhotinado Bidimensional Aplicado A Uma Situação De Canibalização. UFP, 2008. 

FRITSCH, Andreas; VORNBERGER, Oliver. Cutting Stock by Iterated Matching. University of Osnabrück.1995.

GILMORE, P.C., GOMORY, R.E.(1963), Multistage cutting stock problems of two and more dimensions, Operations Research, Vol. 13, pp. 94-120.

GOLDENBERG, D. E., Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison Wesley Publishing Company, 1989.

HERZ, J.C. Recursive Computational Procedure for Two-Dimensional Stock Cutting, IBM Journal of Research and Development 16, pp. 462-469. 1972.

1996 –MITCHELL, An Introduction to Genetic Algorithms. MIT Press, 1996.

MIRANDA, Márcio Nunes. Algoritmo Genético: Fundamentos e Aplicações. UFRJ, 2009.

MORABITO, R; ARENALES, M. An and/Or-Graph approach to the solution of two dimensional non-guillotine cutting problems, European Journal of Operational Research 84, 599-617. 1995

MORABITO, R; ARENALES, M.  Stage and Constrainted two – dimensional guillotine cutting problems: an AND/OR-graph approach, European Journal Of Operational Research 94, 548-560.1997.

NIX, A. AND VOSE, M. (1992) Modeling Genetic Algorithms with Markov Chains. Annals of Mathematics and Artificial Intelligence. 5:79-88. 

OBITKO, MAREK, Introdução aos Algoritmos Genéticos. (1998),  Universidade Tcheca Técnica em Praga.

OLIVEIRA, J. F., FERREIRA, J. S., An improved version of Wang’s algorithm for Two-dimensional cutting problems. European Journal of Operacional Reserarch 44 (1990), 256-266.

RUSSEL, STUART J. (STUART JONATHAN), Inteligência Artificial: Stuart Russel, Peter Norvig; Tradução de Artificial Intelligence, 2^nd ed., (2004), 108-115.

SILVA, Rodrigo T.  Algoritmos Genéticos e Programação Linear Inteira

Aplicados ao Problema de Corte Unidimensional. Monografia de conclusão de curso. Curitiba, PR, 2005.

VASKO, Francis J. (1989),  An Computational Improvement to Wang’s two dimensional Cutting Stock Algorithm, Computers ind. Engng 16 109-115. 1989.

WANG, P. Y. ,Two algorithms for constrained two-dimensional cutting stock problems. Operacional Reserarch 31 (1983), 573 – 586.

ANEXOS

ANEXO 1 – ALGORITMO GENÉTICO

[code language=”bash”]

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Drawing;

using System.IO;

using System.Configuration;

namespace Cortes.Tester

{

static class Program

{

private const string STR_CROSS = “{0}{1}”;

private const float FLOAT_MUTATION_PERCENTUAL = 0.05f;

static long max;

static Random random;

static Single oldFit, newFit;

static int pop;

static StringBuilder builder = new StringBuilder();

static StringBuilder crossBuilderA = new StringBuilder();

static StringBuilder crossBuilderB = new StringBuilder();

static StringBuilder muteBuilder = new StringBuilder();

static SortedDictionary<long, int> selectDic = new SortedDictionary<long, int>();

 

#region Documentation

///<summary>

/// Utilizada para definir o correto funcionamento de <see cref=”ToBase2String”/>.

///</summary>

#endregion

static int bits;

 

static void Main(string[] args)

{

string fileName = ConfigurationManager.AppSettings[“file”].ToString();

 

TextReader reader = File.OpenText(fileName);

string text = reader.ReadToEnd();

reader.Close();

string[] lines = text.Split(“\r\n”.ToArray());

List<string> values = new List<string>(lines.Where(s => s != string.Empty));

 

bool first = true;

 

Plate plate = null;

 

int j = 1;

List<long> keys = new List<long>();

foreach (string s in values)

{

string[] elements = s.Split(“\t”.ToArray());

if (first)

{

plate = new Plate(Convert.ToInt32(elements[1]),

Convert.ToInt32(elements[2]),

Convert.ToDecimal(elements[3]));

first = false;

}

else

{

for (int i = 0; i < Convert.ToInt32(elements[3]); i++)

{

Cut c = new Cut(Convert.ToInt32(elements[1]), Convert.ToInt32(elements[2]));

plate.Add(c, false);

keys.Add(j);

j = j << 1;

}

}

}

 

//definição da quantidade de bits para converção de base10 para base2 em ToBase2String.

bits = plate.Count;

 

DateTime now = DateTime.Now;

 

if (plate.Count > 64)

{

Console.WriteLine(“Quantidade inválida de chapas. Até 64 cortes por chapa.”);

}

else

{

max = (long)Math.Pow(2, plate.Count);

int limit = (plate.Count * Convert.ToInt32(ConfigurationManager.AppSettings[“pop”]));

for (int i = 0; i < limit; i++)

{

try

{

keys.Add(CreateRandom(keys, max));

}

catch { i–; }

}

}

 

 

//realizo a primeira preseleção.

List<long> preselected = PreSelect(plate, keys, out newFit);

//definio o tamanho da população em relação à preseleção anterior.

pop = preselected.Count;

 

//Criando a lista de trabalho, por definição, cópia da preseleção, convertida para strings binárias.

List<string> work = new List<string>();

long interactions = 0;

//loop principal

while (oldFit < newFit)

{

//preparo a lista de trabalho

work.Clear();

work.AddRange(preselected.ConvertAll<string>(s => s.ToBase2String()));

//redefino os fitness.

oldFit = newFit;

Cross(ref work);

Mute(ref work);

//preseleciona o resultado adicionando-o à lista preselecionada.

preselected.AddRange(PreSelect(plate, work.ConvertAll<long>(s => Convert.ToInt64(s,2))));

newFit = Select(plate, ref preselected);

interactions++;

}

 

//expressão que avalia se houve algum resultado satisfatório e retorna o primeiro.

long result = preselected.FirstOrDefault(s => plate.IsResult(s)); && plate.IsGuillotine(s,0));

 

DateTime end = DateTime.Now;

Console.WriteLine(“Interações : {0}\n”, interactions);

Console.Write(“Duração em milisegundos: {0}”, (end – now).Duration().TotalMilliseconds);

 

 

if (result == 0)

{

Console.WriteLine(“\n Sem resultado satisfatório.”);

}

else

{

plate.Power(result);

Console.WriteLine(“Resultado satisfatório encontrado:”);

Console.WriteLine(Convert.ToString(result,2));

Console.WriteLine(“\nChapa de : {0}x{1}”,plate.Height,plate.Width);

Console.WriteLine(“Area total: {0}”, plate.Value);

Console.WriteLine(“Area Ocupada: {0}”, plate.EngagedArea);

Console.WriteLine(“Percentual aceitável de perda {0}%”, plate.Percentual);

Console.WriteLine(“\n\nCortes—“);

 

foreach(Cut c in plate.SelectedCuts)

{

Console.WriteLine(“Corte: {0}x{1}”,c.Height,c.Width);

}

}

 

Console.ReadLine();

}

 

#region Documentation

///<summary>

/// Seleciona os padrões, repreenche a lista e retorna o novo fitness.

///</summary>

#endregion

private static Single Select(Plate chapa, ref List<long> list)

{

selectDic.Clear();

Single fitness = 0;

foreach (long item in list)

{

chapa.Power(item);

if (!selectDic.ContainsKey(item))

{

selectDic.Add(item, chapa.EngagedArea);

}

}

 

list.Clear();

for (int i = 0; i < pop; i++)

{

int old = 0;

KeyValuePair<long, int> selected = new KeyValuePair<long, int>(0, 0);

foreach (KeyValuePair<long, int> item in selectDic)

{

if (item.Value > old)

{

selected = item;

old = item.Value;

}

}

fitness += selected.Value;

list.Add(selected.Key);

selectDic.Remove(selected.Key);

}

 

return fitness / (Single)pop;

}

 

#region Documentation

///<summary>

/// Realiza a mutação

///</summary>

#endregion

private static void Mute(ref List<string> work)

{

Random random = new Random();

int count = 0;

try

{

count = Convert.ToInt32(work.Count * FLOAT_MUTATION_PERCENTUAL);

}

catch { }

 

List<int> rows = new List<int>();

for (int i = 0; i < count; i++)

{

try

{

rows.Add(CreateRandom(rows, work.Count – 1));

}

catch{i–;}

}

 

List<int> columns = new List<int>();

for (int i = 0; i < count; i++)

{

try

{

columns.Add(CreateRandom(columns, bits – 1));

}

catch{i–;}

}

 

/*

* Trabalha os valores binários selecionados pelo índice ‘row’ pegando o elemento definido por column indice j onde

* 1 é substituído por 0 e vice-versa.

*/

int j =0;

foreach(int index in rows)

{

muteBuilder.Clear();

 

muteBuilder.Append(work[index]);

muteBuilder.Replace(work[index][columns[j]], work[index][columns[j]] == ‘0’ ? ‘1’ : ‘0’, columns[j], 1);

work[index] = muteBuilder.ToString();

j++;

}

}

 

#region Documentation

///<summary>

/// Método de cruzamento binário.

///</summary>

#endregion

private static void Cross(ref List<string> work)

{

if (work.Count > 1)

{

int cut = random.Next(0, (work.Count – 1));

 

bool pair = (work.Count % 2) == 0;

 

for (int i = 0; i < work.Count; i++)

{

string a = string.Empty;

string b = string.Empty;

if (pair || (!pair && i < work.Count – 1))

{

Cross(work[i], work[i + 1], cut, out a, out b);

work[i] = a;

work[i + 1] = b;

i++;

}

else

{

Cross(work[i], work[0], cut, out a, out b);

work[i] = a;

work[0] = b;

}

}

}

}

 

#region Documentation

///<summary>

/// Consumido internalmente para operações de <see cref=”Cross(ref List_long work)”/>.

///</summary>

#endregion

private static void Cross(string a, string b, int cut, out string newA, out string newB)

{

crossBuilderA.Clear();

crossBuilderB.Clear();

 

newA = ToBase2String(0);

newB = ToBase2String(0);

 

string[] partsA, partsB;

int split = cut + 1;

if ((split) < a.Length && (split) < b.Length)

{

partsA = new string[] { a.Substring(0, (split)), a.Substring((split), a.Length – (split)) };

partsB = new string[] { b.Substring(0, (split)), b.Substring((split), b.Length – (split)) };

 

crossBuilderA.AppendFormat(STR_CROSS, partsA[0], partsB[1]);

crossBuilderB.AppendFormat(STR_CROSS, partsB[0], partsA[1]);

 

newA = crossBuilderA.ToString();

newB = crossBuilderB.ToString();

}

else

{

newA = a;

newB = b;

}

}

 

#region Documentation

///<summary>

/// Converte e nomarliza um valor, com zeros a esquerda, um valor para sua representação string base 2.

///</summary>

#endregion

private static string ToBase2String(this long val)

{

builder.Clear();

 

builder.Append(Convert.ToString(val, 2));

while (builder.Length < bits)

{

builder.Insert(0, ‘0’);

}

 

return builder.ToString();

}

 

#region Documentation

///<summary>

/// Cria sequencias randomicas Int64.

///</summary>

#endregion

private static long CreateRandom(List<long> keys, long max)

{

random = new Random();

long rand;

if (max <= int.MaxValue)

{

rand = random.Next(1, (int)(max-1));

}

else

{

int a, b;

a = random.Next(1, int.MaxValue);

long dif = max – int.MaxValue;

b = random.Next(0, (int)dif);

 

string binA = Convert.ToString(a, 2);

string binB = Convert.ToString(b, 2);

 

rand = Convert.ToInt64(binB + binA, 2);

if (rand > max)

{

rand = CreateRandom(keys, max);

}

}

 

if (keys.Contains(rand))

{

return  CreateRandom(keys, max);

}

else

{

return rand;

}

}

 

#region Documentation

///<summary>

/// Cria sequencias randomicas Int32.

///</summary>

#endregion

private static int CreateRandom(List<int> keys, int max)

{

random = new Random();

int rand = random.Next(0, max);

if (keys.Contains(rand))

{

return CreateRandom(keys, max);

}

else

{

return rand;

}

}

 

private static List<long> PreSelect(Plate plate, List<long> keys, out Single fitness)

{

fitness = 0;

Single div = 0;

List<long> preselect = new List<long>();

foreach(long val in keys)

{

plate.Power(val);

if (plate.FreeArea >= 0)

{

preselect.Add(val);

fitness += plate.EngagedArea;

div++;

}

}

 

fitness = fitness / div;

return preselect;

}

 

private static List<long> PreSelect(Plate chapa, List<long> keys)

{

List<long> preselect = new List<long>();

foreach (long val in keys)

{

chapa.Power(val);

if (chapa.FreeArea >= 0)

{

preselect.Add(val);

}

}

return preselect;

}

}

}

 

 

ANEXO 1 – CÓDIGO GUILHOTINADO

 

public bool IsGuillotine(long key)

{

this.Power(key);

List<Wang> L = new List<Wang>();

List<Wang> F = new List<Wang>();

int tamAtu, tamProx;

int j = 0;

this.demand.Clear();

foreach (Cut c in this.SelectedCuts)

{

this.demand.Add(1);

L.Add(new Wang(c, this, j));

L[j].Num = j;

j++;

}

F.AddRange(L);

tamAtu = F.Count;

do

{

tamProx = tamAtu;

List<Wang> atual = new List<Wang>();

for (int i = 0; i < F.Count; ++i)

{

for (int h = 0; h < L.Count; ++h)

{

Wang trab = new Wang(F[i], L[h], “Horizontal”);

if (trab.possivel(this)) atual.Add(trab);

trab = new Wang(F[i], L[h], “Vertical”);

if (trab.possivel(this)) atual.Add(trab);

}

}

for (int i = 0; i < atual.Count; ++i)

{

bool flag = false;

for (int h = 0; h < L.Count; ++h)

{

if (IsEquals(atual[i], L[h]))

{

flag = true;

break;

}

}

if (!flag)

{

L.Add(atual[i]);

L[L.Count – 1].Num = L.Count – 1;

}

}

tamAtu = L.Count;

F.Clear();

F.AddRange(atual);

io++;

} while (tamProx == tamAtu);

 

return L.Count == this.SelectedCuts.Count();

}

ANEXO 1 – CÓDIGO WANG

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Drawing;

using System.IO;

namespace Cortes.Tester

{

class Program

{

static List<long> keys = new List<long>();

static Random random = new Random();

 

static void Main(string[] args)

{

string fileName = @”G:\TCC\corte\src\arquivo\padroes\g0101.txt”;

 

TextReader reader = File.OpenText(fileName);

string text = reader.ReadToEnd();

reader.Close();

string[] lines = text.Split(“\r\n”.ToArray());

List<string> values = new List<string>(lines.Where(s => s != string.Empty));

List<Wang> L = new List<Wang>();

List<Wang> F = new List<Wang>();

int tamAtu = 0, tamProx = 0;

 

bool first = true;

 

Chapa chapa = null;

///// Inicie a marcação de tempo aqui!!!!

 

DateTime now = DateTime.Now;

 

foreach (string s in values)

{

string[] elements = s.Split(“\t”.ToArray());

if (first)

{

chapa = new Chapa(Convert.ToInt32(elements[1]),

Convert.ToInt32(elements[2]),

Convert.ToDecimal(elements[3]));

first = false;

}

else

{

Corte c = new Corte(Convert.ToInt32(elements[1]), Convert.ToInt32(elements[2]));

int ins = Convert.ToInt32(elements[3]);

chapa.Add(c,false);

chapa.Demanda.Add(ins);

}

}

 

if (chapa.Count > 64)

{

Console.WriteLine(“Quantidade inválida de chapas. Até 64 cortes por chapa.”);

}

else

{

int j=0;

foreach(Corte c in chapa.Keys)

{

L.Add(new Wang(c,chapa,j));

L[j].Num = j;

j++;

}

}

F.AddRange(L);

tamAtu = F.Count;

do {

tamProx = tamAtu;

List<Wang> atual = new List<Wang>();

for (int i = 0; i < F.Count; ++i)

{

for (int j = 0; j < L.Count; ++j)

{

Wang trab = new Wang(F[i], L[j], “Horizontal”);

if (trab.possivel(chapa)) atual.Add(trab);

trab = new Wang(F[i], L[j], “Vertical”);

if (trab.possivel(chapa)) atual.Add(trab);

}

}

for(int i=0; i<atual.Count;++i) {

bool flag = false;

for (int j = 0; j < L.Count; ++j)

{

if (iguais(atual[i], L[j]))

{

flag=true;

break;

}

}

if (!flag)

{

L.Add(atual[i]);

L[L.Count – 1].Num = L.Count – 1;

}

}

tamAtu = L.Count;

F.Clear();

F.AddRange(atual);

} while(tamProx!=tamAtu);

 

DateTime end = DateTime.Now;

Console.Write(“Duração em milisegundos: {0}”, (end – now).Duration().TotalMilliseconds);

//////////// Finalize a marcação de tempo aqui!!!!!

 

for (int i = 0; i < L.Count; ++i)

{

if (L[i].PerdaTotal(chapa) < chapa.Valor * chapa.Percentual / 100)

{

mostraPadrao(L[i],” “);

Console.WriteLine();

Console.WriteLine();

}

}

Console.ReadLine();

}

public static Boolean iguais(Wang x, Wang y)

{

if (x.Largura != y.Largura || x.Altura != y.Altura || x.Valor != y.Valor || x.PerdaInterna != y.PerdaInterna ||

x.Pecas.Count != y.Pecas.Count || !pecasIguais(x, y)) return false;

return true;

}

public static Boolean pecasIguais(Wang x, Wang y)

{

Boolean flag = true;

for (int i = 0; i < x.Pecas.Count; ++i)

{

if (x.Pecas[i] != y.Pecas[i])

{

flag = false;

break;

}

}

return flag;

}

 

public static void mostraPadrao(Wang w, String s)

{

if (w != null)

{

Console.Write(w.Num + ” – ” + w.Altura + ” – ” + w.Largura + ” – ” + w.Valor+” – “+w.Construcao+” – “+s+” — “);

if (w.P1 != null)

{

Console.Write(” p1 ” + w.P1.Num + ” — “);

}

if (w.P2 != null)

{

Console.Write(” p2 ” + w.P2.Num );

}

Console.WriteLine();

 

mostraPadrao(w.P1, s+” *”);

mostraPadrao(w.P2, s+” *”);

}

}

}

}

Testes Adicionais

Algoritmo Genético

O G0107 DEMOROU MAIS DE 20 MIN

Algoritmo de Wang

O G0107 DEMOROU EM TORNO DE 20 MINUTOS

G0109 –DEMOROU EM TORNO DE 3,42 MINUTOS

[/code]
[1] Trabalho apresentado na conclusão do curso de ciências da computação no Centro Universitário de Barra Mansa em 2010