UNIVERSIDADE DO VALE DO ITAJAÍ
CENTRO DE CIÊNCIAS TECNOLÓGICAS DA TERRA E DO MAR
CURSO DE CIÊNCIA DA COMPUTAÇÃO
ALGORITMOS GENÉTICOS E SIMULATED ANNEALING APLICADOS
NO ENCAIXE DE FIGURAS IRREGULARES
Pesquisa Operacional
por
Leonardo Vitor da Silva
Edson Tadeu Bez, Dr.
Orientador
São José (SC), dezembro de 2007
i
UNIVERSIDADE DO VALE DO ITAJAÍ
CENTRO DE CIÊNCIAS TECNOLÓGICAS DA TERRA E DO MAR
CURSO DE CIÊNCIA DA COMPUTAÇÃO
ALGORITMOS GENÉTICOS E SIMULATED ANNEALING APLICADOS
NO ENCAIXE DE FIGURAS IRREGULARES
Pesquisa Operacional
por
Leonardo Vitor da Silva
Relatório apresentado à Banca Examinadora do
Trabalho de Conclusão do Curso de Ciência da
Computação para análise e aprovação.
Orientador: Edson Tadeu Bez, Dr.
São José (SC), dezembro de 2007
ii
DEDICATÓRIA
Aos meus pais Vitor Teófilo da Silva e
Laura Maria de Souza da Silva
iii
AGRADECIMENTOS
Registro nesta pesquisa um especial agradecimento:
•
ao professor Edson Tadeu Bez pelo conhecimento passado e por toda a disponibilidade e
colaboração durante a execução desta pesquisa;
•
a professora Anita Maria da Rocha Fernandes que esteve sempre disponível para
qualquer esclarecimento; e
•
aos meus pais pelo apoio.
iv
SUMÁRIO
LISTA DE ABREVIATURAS................................................................. vii
LISTA DE FIGURAS ..............................................................................viii
LISTA DE TABELAS ............................................................................... ix
LISTA DE EQUAÇÕES ............................................................................ x
RESUMO .................................................................................................... xi
ABSTRACT ............................................................................................... xii
I INTRODUÇÃO ...................................................................................... 13
1.1 PROBLEMATIZAÇÃO ................................................................................... 14
1.1.1 Formulação do Problema ............................................................................... 14
1.1.2 Solução Proposta ............................................................................................. 15
1.2 OBJETIVOS ...................................................................................................... 15
1.2.1 Objetivo Geral ................................................................................................. 15
1.2.2 Objetivos Específicos ...................................................................................... 15
1.3 METODOLOGIA.............................................................................................. 16
1.4 ESTRUTURA DO TRABALHO ..................................................................... 16
2 FUNDAMENTAÇÃO TEÓRICA ...................................................... 18
2.1 PROBLEMAS DE CORTE E EMPACOTAMENTO................................... 18
2.1.1 Problemas de Corte e Empacotamento......................................................... 20
2.2 PROBLEMAS DE CORTE INDUSTRIAL .................................................... 23
2.3 PROBLEMA DE ENCAIXE DE FIGURAS IRREGULARES .................... 24
2.3.1 Definição do problema .................................................................................... 25
3 DESENVOLVIMENTO ...................................................................... 28
3.1 MÉTODOS UTILIZADOS PARA RESOLUÇÃO DOS PROBLEMAS DE
ENCAIXE................................................................................................................... 28
3.1.1 Ordenação das figuras .................................................................................... 28
3.1.2 Encaixe das Figuras ........................................................................................ 42
3.1.3 Tratamento de Sobreposição das Figuras .................................................... 43
3.2 MODELAGEM ALGORÍTMICA .................................................................. 48
3.3 ENSAIOS NUMÉRICOS .................................................................................. 50
3.3.1 Ensaios realizados com Algoritmo Genético ................................................ 51
3.3.2 Ensaios realizados com Simulated Annealing ............................................... 54
3.3.3 Comparativo entre os resultados ................................................................... 56
4 CONCLUSÕES .................................................................................... 60
5 Trabalhos futuros ................................................................................. 62
REFERÊNCIAS BIBLIOGRÁFICAS ................................................... 63
v
TIPOS DE FIGURAS UTILIZADAS NOS TESTES ........................... 66
Exemplos de encaixes de figuras ............................................................. 67
Exemplo 1 de encaixe de figuras .............................................................................. 67
Exemplo 2 de encaixe de figuras .............................................................................. 68
vi
LISTA DE ABREVIATURAS
AGs
CX
ENIAC
NP-HARD
OX
PMX
PNP
SICUP
TCC
UNIVALI
Algoritmos Genéticos
Cycle Crossover
Electronic Numerical Integrator And Computer
Nondeterministic Polynomial-time Hard
Order Crossover
Partially Mapped Crossover.
Ponto no Polígono
Special Interest Group on Cutting and Packing
Trabalho de Conclusão de Curso
Universidade do Vale do Itajaí
vii
LISTA DE FIGURAS
Figura 1. Tipos de Polígonos: (a) Polígono convexo; (b) Polígono não convexo ............................. 25
Figura 2. Tipos de Preenchimento...................................................................................................... 26
Figura 3. Estrutura do algoritmo genético .......................................................................................... 30
Figura 4. Método da roleta ................................................................................................................. 33
Figura 5. Cruzamento simples ............................................................................................................ 34
Figura 6. Cruzamento de dois pontos ................................................................................................. 34
Figura 7. Cruzamento uniforme ......................................................................................................... 34
Figura 8. Tratamento de Inconsistência por PMX ............................................................................. 35
Figura 9. Tratamento de Inconsistência por OX ................................................................................ 36
Figura 10. Mutação ............................................................................................................................ 36
Figura 11. Mutação com mudança na ordem dos genes .................................................................... 37
Figura 12. Algoritmo genético genérico ............................................................................................ 38
Figura 13. Estado desordenado das moléculas da matéria em fusão ................................................. 39
Figura 14. Estado desordenado das moléculas após a um resfriamento rápido ................................. 40
Figura 15. Estado ordenado das moléculas após a um resfriamento lento ......................................... 40
Figura 16. Simulated Annealing ......................................................................................................... 41
Figura 17. Simulated Annealing ......................................................................................................... 42
Figura 18. Left-Bottom ....................................................................................................................... 43
Figura 19. Ponto interno ao polígono ................................................................................................. 44
Figura 20. Quantidade de cruzamentos nos segmentos do polígono ................................................. 45
Figura 21. Representação de uma figura em matriz de bits ............................................................... 46
Figura 22. Exemplificação de Ponto e Reta ....................................................................................... 47
Figura 23. Intersecção das Retas AB e CD ........................................................................................ 48
Figura 24. Intersecção de segmentos de reta ...................................................................................... 50
Figura 25. Figuras utilizadas no encaixe ............................................................................................ 51
Figura 26. Definição da Taxa de Cruzamentos .................................................................................. 52
Figura 27. Definição da Taxa de Mutação ......................................................................................... 52
Figura 28. Definição do Tamanho da População ............................................................................... 53
Figura 29. Temperatura Inicial ........................................................................................................... 55
Figura 30. Decremento da Temperatura ............................................................................................. 55
Figura 31. Quantidade de Iterações .................................................................................................... 56
Figura 32. Resultado do Algoritmo Genético e Simulated Annealing ............................................... 57
Figura 33. Melhor solução com Algoritmo Genético ........................................................................ 57
Figura 34. Melhor solução com Simulated Annealing ....................................................................... 58
Figura 35. Resultado do encaixe com Algoritmo Genético ............................................................... 58
Figura 36. Resultado do encaixe com Simulated Annealing .............................................................. 59
Figura 37. Figuras utilizadas no encaixe ............................................................................................ 66
Figura 38. Exemplo 1 de encaixe de figuras ...................................................................................... 67
Figura 39. Exemplo 2 de encaixe de figuras ...................................................................................... 68
viii
LISTA DE TABELAS
Tabela 1. Problemas de Corte e Empacotamento ............................................................................... 20
Tabela 2. Características do problema de corte da indústria tecido ................................................... 24
Tabela 3. Variação da Quantidade de Gerações ................................................................................. 53
ix
LISTA DE EQUAÇÕES
Equação 1 ........................................................................................................................................... 26
Equação 2 ........................................................................................................................................... 26
Equação 3 ........................................................................................................................................... 26
Equação 4 ........................................................................................................................................... 42
Equação 5 ........................................................................................................................................... 47
Equação 6 ........................................................................................................................................... 47
x
RESUMO
SILVA, Leonardo Vitor. Algoritmos Genéticos e Simulated Annealing aplicados no encaixe de
figuras irregulares. São José, 2007. 68f. Trabalho de Conclusão de Curso (Graduação em Ciência
da Computação) – Centro de Ciências Tecnológicas da Terra e do Mar, Universidade do Vale do
Itajaí, São José, 2007.
O problema de corte e empacotamento vem sendo estudado por diversos pesquisadores que desde a
metade do século passado iniciaram seus estudos em problemas de corte de retângulos. O rápido
crescimento de estudos tratando do problema de corte e empacotamento aconteceu na década de 60,
período onde foram publicados os três trabalhos de Gilmore e Gomory. Estes trabalhos tratavam o
problema de corte industrial e se tornaram clássicos para este tipo de estudo. Os trabalhos
subseqüentes focavam no estudo do problema de corte de retângulos e gradativamente alguns outros
trabalhos surgiram para o encaixe de figuras irregulares, podendo citar entre estes, a solução
proposta por Dias no ano de 1991 que trata o encaixe de figuras irregulares em um retângulo maior.
O presente estudo apresenta um algoritmo para o encaixe de figuras irregulares em um retângulo
maior. Propõe-se um modelo matemático para este problema. O problema do encaixe de figuras
irregulares abordado nesta pesquisa é baseado no problema de corte da indústria têxtil, que possui
em sua complexidade, figuras com formas geométricas não convexas e variáveis que permitem a
manipulação destas figuras durante o processo de encaixe para se obter um melhor aproveitamento.
Este trabalho considera a forma geométrica do objeto delimitador como sendo um retângulo de
comprimento variável e figuras convexas e não convexas.
Palavras-chave: Encaixe de figuras irregulares. Algoritmos Genéticos. Simulated Annealing.
xi
ABSTRACT
The cutting and packing problem has been studied for many researchers which have already been
studying the problems of cutting rectangles since the mid of the twenty century. The fast growing
number of articles related to cutting and packing started in the 60’s, period where the articles from
Gilmore and Gomony were published. These articles talked about the industrial cutting problem,
and became a reference for this kind of studies. The subsequent projects were focus on the study of
cutting and packing, and gradually there were some studies about the nesting of irregular shapes in
a rectangle. Between these projects we can mention the solution proposed by Dias in 1991, that
shows about the nesting of irregular object in a rectangle. This study presents an algorithm for the
nesting of irregular object in a rectangle. A mathematical method has been proposed for this
problem. The nesting of irregular shape problem in this research was based on the cutting problem
in the textile industry. This problem from the textile industry has got objects with non-convex
geometrical forms and many other variables which allow the manipulation of these objects during
the nesting for a better progress. This research will consider the geometrical form of the object
delimiter, which in this case, is a rectangle with a variable length and the objects in this research
will have a geometric convex and non-convex form.
Keywords: Nesting of irregular shapes, Genetic Algorithms, Simulated Annealing.
xii
I INTRODUÇÃO
Ao longo da história é possível observar a busca por meios para se tentar diminuir esforços,
obtendo mais conforto. Esta busca pela diminuição de esforços trouxe consigo várias inovações e
avanços na tecnologia. A utilização de robôs na linha de montagem de automóveis ou mesmo a
execução de uma folha de pagamento utilizando-se de um computador, apesar de serem trabalhos
bem distintos, sofreram mudanças significativas durante os tempos e são exemplos práticos dos
avanços tecnológicos. Estes avanços já se tornaram comuns à sociedade. É importante enfatizar que
tudo isso se iniciou com a Revolução Industrial a partir do século XVIII. “Este provavelmente foi o
mais importante acontecimento na história do mundo, pelo menos desde a invenção da agricultura e
das cidades” (HOBSBAWM, 1982, p. 45).
O surgimento dos computadores foi uma grande inovação e também contribui em muito para
os avanços tecnológicos. Segundo Monteiro (1996, p. 09): “O primeiro computador eletrônico e
digital, [...], foi denominado ENIAC (Electronic Numerical Integrator And Computer).”.
As inovações tecnológicas trouxeram consigo uma mudança no processo de trabalho em
muitas empresas. Trabalhos de alto risco ou de alta complexidade puderam ter soluções
automatizadas. As novas tecnologias trouxeram consigo uma difusão do conhecimento, onde é
possível comprar tecnologia e se tornar uma empresa atuante no mercado. Surge então, a
necessidade de diminuir custos e aumentar a produtividade.
Indústrias de couro, plástico, vidro, papel, metal, tecido, dentre outras, possuem em comum
a necessidade pela redução do desperdício de matéria-prima (FRITSCH; VORNBERGER, 1995).
Trata-se de um problema em que se faz necessário o ajuste das peças em uma área maior, área esta,
referente à matéria-prima. Estes tipos de problemas denominam-se problemas de corte e
empacotamento. No caso da indústria têxtil, o problema envolve o encaixe dos moldes de roupas no
tecido.
Análogo ao problema do corte do tecido há o problema do corte de chapas. Este problema
trata peças retangulares que devem ser ajustadas em uma determinada área. O corte de peças
retangulares considera a largura e altura da área onde as peças serão ajustadas. É um problema que
ocorre, por exemplo, em indústrias que necessitam do corte de vidro, metal ou madeira. Outro
13
problema é o ajuste de peças em contêineres1, neste caso, considera-se a largura, a altura e a
profundidade da área onde as peças serão ajustadas, é um tipo de problema tridimensional
(DYCKHOFF, 1990). Todos estes problemas industriais possuem diversas variáveis que tornam as
soluções bem complexas.
Nesta mesma linha de estudo, este TCC (trabalho de conclusão de curso) apresentará um
algoritmo para o encaixe de polígonos irregulares, baseando-se no problema do encaixe de peças no
tecido. O algoritmo irá processar peças de 2 dimensões considerando a largura e a altura do
polígono e ajustando-o para obter um melhor aproveitamento da área (LIU, 2005).
O algoritmo que será apresentado não é uma proposta de solução para o problema da
indústria têxtil. Este considera, conforme o problema do encaixe de peças no tecido, apenas a
restrição de largura do tecido, sem se importar com o comprimento e outras restrições existentes da
indústria têxtil. Ao considerar a largura do tecido, o algoritmo limitará sua área de encaixe em um
retângulo de largura fixa e um comprimento que varia conforme a necessidade de espaço para o
encaixe de todas as figuras.
As demais restrições presentes no problema de encaixe da indústria têxtil podem ser
exemplificadas como o fato de um molde poder ser girado, ficando fora do sentido do fio do tecido.
Outras restrições presentes no problema têxtil é o fato dos moldes poderem ou não ser espelhados e
ainda se estes poderão estar em qualquer posição do tecido e em posições específicas, pois alguns
moldes podem ser encaixados dobrados e estes devem ficar sempre na borda do tecido.
1.1 PROBLEMATIZAÇÃO
1.1.1 Formulação do Problema
O problema de encaixe de figuras irregulares é uma classe dos problemas de corte e
empacotamento. É um tipo de problema de análise combinatória e computacionalmente de difícil
resolução, as soluções devem ser procuradas num espaço grande de possíveis soluções, sendo
enquadrado na classe de problemas NP-Hard (Nondeterministic Polynomial-time Hard) (ARAUJO,
2004).
1
Grande caixa, de dimensões e outras características padronizadas, para acondicionamento da carga geral a transportar,
com a finalidade de facilitar o seu embarque, desembarque e transbordo entre diferentes meios de transporte.
14
A forma geométrica das figuras que serão encaixadas faz com que os resultados de
aproveitamento do encaixe variem bastante, visto que estas figuras possuem formas irregulares.
Assim ordem das figuras torna-se importante na definição da qualidade do resultado. A obtenção de
um algoritmo eficiente ocorre através de um bom processo de encaixe das figuras e ordenamento
das mesmas.
1.1.2 Solução Proposta
Para formulação do problema serão enfatizados nesta pesquisa dois processos de
fundamental importância para o encaixe. Nascimento (2006) destaca a utilização de heurísticas e
metaheurísticas nas soluções recentes para o tipo problema em questão. Seguindo esta linha, esta
solução propõe a utilização de metaheurísticas para a ordenação das figuras que serão encaixadas,
utilizando-se para isso, Algoritmos Genéticos e Simulated Annealing.
A utilização das metaheurísticas foi uma das partes importantes do processo. Outro processo
de fundamental importância foi o posicionamento das figuras que utilizou left-bottom. Em conjunto
com o posicionamento das figuras foi necessária a garantia de não sobreposição das figuras.
1.2 OBJETIVOS
1.2.1 Objetivo Geral
O objeto principal deste estudo foi de aplicar as metaheurísticas: Algoritmos Genéticos e
Simulated Annealing no encaixe de figuras irregulares, através do desenvolvimento de um
algoritmo que efetuasse o mesmo, simulando assim, o problema de encaixe de peças de roupa da
indústria têxtil. A restrição de problema foi a utilização de uma largura pré-fixada da área de
encaixe, não se importando com o comprimento necessário para o encaixe de todas as figuras.
1.2.2 Objetivos Específicos
Os objetivos específicos desta pesquisa foram:
•
Estudar os problemas de corte;
•
Estudar algoritmos propostos para resolução do problema de corte;
•
Selecionar os algoritmos de suporte ao problema proposto;
15
•
Modelar os algoritmos selecionados para o problema, neste caso, Algoritmos Genéticos
e Simulated Annealing;
•
Implementar computacionalmente os algoritmos selecionados para o estudo;
•
Realizar os testes computacionais com os algoritmos selecionados; e
•
Realizar uma análise comparativa dos resultados obtidos.
1.3 Metodologia
A fundamentação teórica envolveu a leitura de trabalhos relacionados aos problemas de
corte e empacotamento geral. Foram analisados materiais de pesquisadores que envolviam a
utilização de metaheurísticas para o problema de corte e trabalhos referentes aos Algoritmos
Genéticos e Simulated Annealing.
A escolha do tema de pesquisa levou em consideração a maneira que o problema poderia ser
tratado, neste caso, utilizando-se de metaheurísticas como parte fundamental da ordem das figuras e
também a utilização da geometria analítica para o encaixe das figuras.
A utilização dos Algoritmos Genéticos e do Simulated Annealing levou em consideração
trabalhos recentes que utilizavam diferentes metaheurísticas. Sendo que muitos destes trabalhos não
utilizavam em específico os Algoritmos Genéticos e o Simulated Annealing, o que motivou a idéia
de utilizar essas metaheurísticas e então poder comprovar, ou não, a eficiência dos mesmos.
O resultado desta pesquisa foi um algoritmo para o encaixe das figuras, sendo que sua
implementação computacional foi necessária para testes e obtenção dos resultados para diversos
tipos de figuras. A implementação ocorrida na segunda parte do projeto utilizou a linguagem C++
para programação. A escolha desta linguagem é pela familiaridade com a mesma. Esta pesquisa tem
como produto final o modelo algorítmico, não um software.
1.4 Estrutura do trabalho
Este documento está estruturado em quatro capítulos. O primeiro capítulo foi referente à
Introdução do TCC e apresentou uma contextualização e uma visão geral do problema. O segundo
capítulo refere-se à Fundamentação Teórica, é apresentada uma revisão bibliográfica dos problemas
de corte e empacotamento e corte industrial, referenciando alguns trabalhos realizados na área. A
Fundamentação Teórica descreveu de forma geral os problemas de corte e empacotamento,
16
problemas de corte industrial e o encaixe de figuras irregulares. O terceiro capítulo apresenta o
desenvolvimento do problema proposto, descrevendo as metaheurísticas que serão utilizadas para o
problema, os métodos que deram o suporte para o encaixe das figuras e os resultados obtidos com
os ensaios numéricos. O quarto capítulo apresenta a conclusão desta pesquisa.
17
2 FUNDAMENTAÇÃO TEÓRICA
2.1 Problemas de Corte e Empacotamento
O problema de corte e empacotamento vem sendo estudado desde a metade do século
passado e durante este período, diversos pesquisadores trouxeram importantes contribuições para
este tipo de problema. O problema de corte e empacotamento é conhecido na literatura inglesa
como problema de Cutting and Packing (CUNHA, 1998). Este é um tipo de problema de análise
combinatória e computacionalmente de difícil resolução, as soluções devem ser encontradas num
espaço grande de possíveis soluções, sendo enquadrado na classe dos NP-Hard (ARAUJO, 2004).
O problema de corte e empacotamento teve a primeira formulação apresentada em 1939 por
Kantorovitch, um artigo escrito em russo que tratou o problema de encaixe unidimensional. Na
década de 50, mais precisamente nos anos de 1955, 1956 e 1958, Paul, Walter e Vadja apresentaram
formulações para problema de encaixe de retângulos (CUNHA, 1998).
Segundo Dias (1991), o problema de encaixe de retângulos num retângulo maior começou a
ser estudado na década de 50. Mas as maiores contribuições foram apresentadas em três artigos
clássicos de Gilmore e Gomory em 1961, 1963 e 1965. E a partir desta década, vários pesquisadores
têm publicado trabalhos sobre o assunto, apresentando variações tanto na formulação, como nas
ferramentas usadas para solucionar o problema.
Os três artigos de Gilmore e Gomory descrevem a primeira técnica que foi empregada e
aplicada para problemas de tamanho médio, a clássica Técnica de Geração de Colunas (Delayed
Column Generation Technique) (CUNHA, 1998). Em problemas de tamanho médio do tipo
1/V/I/R 2, a lista de pedidos possui em torno de 50 itens e a quantidade para cada item diferente fica
em torno de centenas ou milhares de peças. Os autores também utilizaram o processo de
Programação Dinâmica para otimização de padrões de corte multidimensionais do tipo guilhotina.
Gilmore e Gomory também ressaltaram a importância do Problema de Knapsack (PISINGER,
1995) como um subproblema que ocorre em variantes do problema de corte industrial (CUNHA,
1998).
2
Segundo Dyckhoff (1990), um problema do tipo 1/V/I/R (problema de corte industrial) possui respectivamente: uma
dimensão (1), tratamento de objetos selecionados de todos os itens (V), os objetos maiores são idênticos (I) e são muitos
objetos com pouca diferença (R).
18
Em 1968, Haesler abordou Problemas de Corte Industrial usando uma formulação
semelhante ao Problema de Knapsack. Em 1974, Dyson e Gregory trataram o problema de encaixe
das indústrias de vidros usando programação linear e regras heurísticas. Em 1976, Stoyan e Gil
publicaram um livro descrevendo métodos e algoritmos para o encaixe de figuras planas. Em 1997,
Christofides e Whitlock utilizaram um algoritmo de enumeração para problemas de corte
bidimensional, tipo guilhotina com limitação do número de vezes que uma peça entra no padrão de
corte (VINADÉ, 1997; CUNHA, 1998).
Segundo Cunha (1998), um passo muito importante para colaborar com a pesquisa
internacional envolvendo os problemas de corte e empacotamento, foi a criação do Special Interest
Group on Cutting and Packing (SICUP) por Dyckhoff e Wäscher em 1988. Um número
considerável de documentos sobre problemas de corte e empacotamento foram lançados pelo
SICUP em conferências internacionais. O SICUP tem uma publicação própria publicada duas vezes
ao ano.
Dyckhoff (1990) desenvolveu uma classificação dos problemas de corte e empacotamento
com base nas características de geometria e lógica destes problemas. Seu trabalho teve como
finalidade integrar os vários tipos de problema existentes na literatura, propiciando uma unificação
do uso de terminologias para os mesmos. Seu trabalho considerava alguns critérios como: a
dimensionalidade, a forma geométrica, o sortimento, os tipos de objetos (matérias-primas do
problema estudado), a quantidade e disponibilidade das peças. A Tabela 1 mostra alguns trabalhos
com aspectos especiais sobre o problema de corte e empacotamento.
19
Tabela 1. Problemas de Corte e Empacotamento
Autores
Brown
Salkin / de Kluyver
Golden
Hinxman
Garey / Johnson
Israni / Sanders
Rayward-Smith / Shing
Coffman et al.
Dowsland
Dyckhoff et al.
Israni / Sanders
Berkey / Wang
Dudzinski / Walukiewicz
Martello / Toth
Rode / Rosenberg
Dyckhoff et al.
Ano
1971
1975
1976
1980
1981
1982
1983
1984
1985
1985
1985
1987
1987
1987
1987
1988
Assunto
Empacotamento
Knapsack
Corte
Redução de sobras
Empilhamento de caixas
Leiaute
Empilhamento de caixas
Empilhamento de caixas
Empacotamento
Redução de sobras
Encaixe de peças
Empilhamento de caixas
Knapsack
Knapsack
Redução de sobras
Corte
Área
Ciência da Computação
Logística
Engenharia Industrial
Pesquisa Operacional
Otimização
Fabricação
Matemática
Ciência da Computação
Pesquisa Operacional
Administração
Produção
Pesquisa Operacional
Pesquisa Operacional
Matemática
Engenharia / Produção
Produção
Fonte: Dyckhoff (1990).
Na década de 90 o trabalho de Dias (1991) tratou o problema de encaixe de figuras
irregulares em uma área retangular. Ghandforoush et al. em 1992 e Macleod et al. em 1993
(CUNHA, 1998) contemplaram novas heurísticas para o problema de corte tipo guilhotina de
retângulos com restrição e também métodos para obtenção da solução ótima dos problemas
propostos por Oliveira e Ferreira em 1990, Viswanathan e Bachi em 1993, Christofides e
Hadjiconstantinou em 1995 e Daza et al. em 1995 (CUNHA, 1998). Vinadé (1997) tratou o
problema de encaixe de figuras irregulares em uma área irregular.
2.1.1 Problemas de Corte e Empacotamento
O problema de corte consiste em efetuar o arranjo de peças diversas em uma região maior,
com intuito de efetuar o corte dessas peças e obter o melhor aproveitamento possível da matériaprima envolvida no processo. Já o problema de empacotamento, consiste neste mesmo arranjo de
peças do problema de corte, sendo que o intuito deste arranjo de peças não é o corte, e sim, obter
uma melhor ocupação do espaço.
O problema de empacotamento pode ser entendido como o inverso do problema de corte,
onde o problema de corte trata o ajuste das peças para o corte da matéria-prima, obtendo assim, o
menor desperdício e uma minimização das perdas. Já o problema de empacotamento trata o ajuste
20
das peças para uma melhor ocupação da área envolvida, neste caso a peça maior, com o intuito de
uma maximização da área. Atenta-se que os objetivos dos problemas são inversos (minimização de
perdas e maximização da área ocupada), mas as abordagens para solução destes problemas são as
mesmas.
Para que se possa obter um maior rendimento da matéria-prima, faz-se necessário um
processo eficiente de agrupamento das peças envolvidas no processo. Este agrupamento é um
arranjo das áreas menores em uma área maior, visando assim, uma ocupação maior do objeto
delimitador, que neste caso, refere-se à área maior, citada anteriormente (DIAS, 1991).
Os problemas de corte e empacotamento podem ter dimensões variadas. Segundo a tipologia
definida por Dyckhoff (1990), os problemas podem ser unidimensionais, onde apenas uma
dimensão é considerada; bidimensionais, onde duas dimensões são consideradas; tridimensionais,
que considera três dimensões e multidimensionais, que considera mais de três dimensões. No caso
dos problemas multidimensionais, são problemas com mais de três dimensões. Dyckhoff (1990)
exemplifica um problema multidimensional que possui quatro dimensões. Este problema envolve o
posicionamento de peças em um contêiner, neste caso um problema tridimensional, sendo que as
peças devem ficar posicionadas por um tempo determinado. Neste caso, a variável tempo torna o
problema com quatro dimensões.
O estudo dos problemas de corte e empacotamento contribui para diversos problemas
existentes nas indústrias. A cada ano, novas abordagens e propostas de soluções surgem para estes
tipos de problemas, contribuindo para que indústrias de couro, plástico, vidro, papel, metal, tecido,
dentre outras, possam diminuir o desperdício de matéria-prima utilizada na produção de Peças
(FRITSCH; VORNBERGER, 1995). Para muitas empresas, uma alternativa para redução de custos
é um melhor aproveitamento ou redução de sobras da matéria-prima utilizada.
Nascimento (2006) mostrou algumas definições para o problema de corte e empacotamento,
estas definições foram adaptadas do trabalho de Cunha (1998). Seguem abaixo estas definições:
1. Trim Loss Problem (Problema de Perdas por Corte): Problema referente à redução do
desperdício de matéria-prima. Trata a otimização do corte de peças maiores para
produção de peças menores. Este problema pode estar envolvido em complexidades
unidimensional, bidimensional, tridimensional ou multidimensional.
21
2. Bin Packing Problem (Empacotamento de caixas, tiras ou faixas): Problema referente à
redução de espaços vazios dentro de objetos. Trata o empilhamento de itens da uma lista
de pedidos.
3. Knapsack Problem (Problema da Mochila): Segundo Nascimento (2006),
O problema da mochila consiste na escolha de um subconjunto de itens, cada qual com uma
correspondente utilidade e um valor (em geral denominado “peso”) que define o quanto
este item utilizará da capacidade da mochila. A escolha dos itens a serem inseridos na
mochila deve repercutir no maior beneficio possível, medido de acordo com a natureza do
problema em estudo.
4. Vehicle Loading (Carregamento de Veículos): Problema de acomodamento de itens
diversos dentro de um veículo, visando uma ocupação melhor do espaço e, diminuindo
assim, o número de viagens necessárias para o transporte de todos estes itens.
5. Container and Pallet Loading (Carregamento de Paletes e Contêineres): Problema de
acomodamento de itens dentro de um volume. Este volume pode ser palete ou contêiner.
Trata itens com três dimensões (3D), empilhando-os de maneira a reduzir os espaços
vazios (NASCIMENTO, 2006).
6. Layout Problems (Problemas de Leiaute): Segundo Nascimento (2006),
Envolve a alocação de componentes em um espaço disponível, de forma que um conjunto
de objetivos pré-especificados possam ser atingidos, respeitando-se restrições de espaço e
performance.
7. Nesting and Partitioning Problems (Problemas de Encaixe e Particionamento):
Segundo Whitwell (2004, apud NASCIMENTO, 2006),
O termo “encaixe” é utilizado para representar o empacotamento de itens com duas
dimensões e formato irregular, problema muito comum na indústria metal-mecânica. O
arranjo proposto de itens é referenciado como um “particionamento” por este segmento da
indústria.
8. Budgeting Capital Problem (Problemas de Cálculo de Capital): Problema de alocação
de investimentos. Deve-se maximizar o retorno auferido dos investimentos respeitando
os recursos disponíveis e o nível mínimo e máximo associado a cada investimento
possível (MATHEMATICAL PROGRAM GLOSSARY, 2005 apud NASCIMENTO,
2006).
22
9. Assembly Line Balancing (Balanceamento de Linhas de Montagem): Problema da
divisão do trabalho necessário para montar uma variedade de produtos ao longo de
diferentes estações e linhas de montagem. O objetivo é otimizar a utilização de recursos
disponíveis em uma indústria (BOCKMAYR, PISARUK, 2001 apud NASCIMENTO,
2006).
10. Multiprocessor Scheduling Problems (Problemas de Ordenamento de Tarefas com
Múltiplos Processadores): Problema na programação de uma série de tarefas ao longo
de um período definido, respeitando as restrições de tempo, mão-de-obra e
seqüenciamento.
Conforme pôde ser observado anteriormente, diversos pesquisadores contribuíram para o
tratamento dos problemas de corte e empacotamento. Cada pesquisador sugeriu ou implementou
técnicas novas para tentar obter os melhores resultados nos seus trabalhos. Segundo Nascimento
(2006): “Nos últimos anos, vem-se dando prioridade à resolução dos problemas de corte a partir da
utilização de algoritmos heurísticos e metaheurísticos, podendo-se destacar a utilização dos
algoritmos genéticos.”. A utilização de algoritmos heurísticos e metaheurísticos contribuem para
melhorias no sorteamento das peças envolvidas no problema.
A utilização de Algoritmos Genéticos e Simulated Annealing para este tipo de problema
podem ser vistos nos trabalhos de Parada, Sepúlveda & Alvarenga (1998) que utilizaram Simulated
Annealing para o problema de corte guilhotina. Liang et al. (2001) tratou o problema de corte
unidimensional utilizando-se Algoritmos Genéticos. Hifi, Paschos & Zissimopoulos (2004)
utilizaram Simulated Annealing para o problema de corte circular.
2.2 Problemas de corte industrial
O problema de corte industrial é conhecido na literatura inglesa como Cutting Stock
Problem. O estudo dos problemas de corte e empacotamento contribui para que problemas
industriais (indústrias de couro, tecido, metal, vidro, plástico e outras) possam ser resolvidos, visto
que irão tratar o melhor arranjo das peças que serão cortadas, diminuindo o desperdício de matériaprima (NASCIMENTO, 2002).
Para que se possa obter um maior rendimento da matéria-prima, faz-se necessário um
processo eficiente de agrupamento das peças que a empresa irá cortar. Este agrupamento é um
arranjo das áreas menores em uma área maior delimitadora, visando assim, uma ocupação maior
23
do objeto delimitador, que neste caso, refere-se à área maior citada anteriormente (DIAS,
1991).
Dentre os problemas existentes na indústria, o problema de corte no segmento têxtil está
relacionado ao tema proposto nesta pesquisa. Este problema consiste no ajuste de peças que serão
cortadas em uma mesa do corte com o intuito de diminuir o desperdício de tecido (NASCIMENTO,
2006). A Tabela 2 mostra as características do problema do corte de tecido conforme os critérios de
classificação propostos por Dyckhoff (1990).
Tabela 2. Características do problema de corte da indústria tecido
Critério
Dimensionalidade
Sistema de medidas
Forma geométrica
Sortimento
Disponibilidade
Características do problema
Bidimensional
Sistema de medida discreta ou inteira
Formas irregulares e assimétricas
Itens com figuras diferentes quanto à forma e tamanho
Disponibilidade finita de itens e objetos
Fonte: Nascimento (2006).
Nascimento (2006) descreve o problema da indústria têxtil relacionado com a ordem de
corte das peças. Esta pesquisa irá se basear no problema da indústria têxtil como sendo o encaixe de
figuras irregulares e não serão tratadas as variáveis envolvidas no problema em questão. O motivo
de escolha do problema da indústria têxtil é à disposição das formas geométricas das peças
envolvidas e da área delimitadora. O item 2.3.1 desta pesquisa descreve a geometria das peças e da
área delimitadora envolvida nesta pesquisa.
A utilização de heurísticas e metaheurísticas para os problemas de corte industrial pode ser
observada em trabalhos recentes como Constantino e Gomes (2002) que utilizaram Algoritmos
Genéticos como técnica da otimização para o problema de corte bidimensional. Araujo (2004)
propôs em seu trabalho a utilização de p-medianas e Busca Tabu para o problema de corte
guilhotina bidimensional. Burke et al. (2006) utilizou Busca Tabu e Hill Climbing para o problema
do encaixe bidimensional de peças irregulares.
2.3 Problema de Encaixe de figuras irregulares
O problema de encaixe de figuras irregulares pode ser entendido como uma classe dos
problemas de corte e empacotamento. O encaixe de figuras irregulares consiste no posicionamento
das figuras em uma área maior. Este processo de posicionamento tem o intuito de obter o melhor
24
posicionamento das figuras, minimizando o desperdício do espaço que será ocupado. O processo
deverá garantir que não haverá sobreposição das figuras encaixadas (DIAS, 1991).
A garantia de não sobreposição das figuras deve-se ao fato de que a forma de ocupação de
um espaço bidimensional classifica-se em três tipos: encaixe, cobertura e enchimento (VINADÉ,
1997). Esta pesquisa irá tratar o encaixe das figuras.
O encaixe de figuras irregulares envolve qualquer polígono fechado (DIAS, 1991). Estes
polígonos são figuras discretizadas em seqüências de segmentos de reta, formando o polígono.
Este tipo de problema envolve como área delimitadora, ou área maior, polígonos convexos e
não convexos. Na indústria, o problema pode ser encontrado em indústrias metal-mecânica, têxtil e
calçadista (VINADÉ, 1997).
2.3.1 Definição do problema
Para o entendimento do processo de encaixe de figuras irregulares, é necessário entender, ou
conhecer, as diferenças entre polígonos convexos e não convexos. Os polígonos convexos (Figura
1-a) são formados por segmentos de retas cujo ângulo entre essas retas não ultrapassa 180°. Ao
traçar qualquer reta internamente a um polígono convexo, todos os pontos da reta serão internos a
este polígono. Já os polígonos não convexos (Figura 1-b), o ângulo entre os segmentos de retas
poderá ser maior que 180° e retas que forem traçadas internamente a este tipo de polígono, poderá
não ter todos os seus pontos internos a este polígono. A Figura 1 exemplifica polígonos convexos e
não convexos respectivamente.
(a)
(b)
Figura 1. Tipos de Polígonos: (a) Polígono convexo; (b) Polígono não convexo
Fonte: Adaptado de Vinadé (1997).
25
O posicionamento das figuras poderá ser do tipo encaixe, onde não ocorrerá a sobreposição,
do tipo cobertura, onde é permitida a sobreposição e do tipo enchimento, onde também não é
permitida a sobreposição das figuras. No caso da cobertura e do enchimento, a área delimitadora
deverá ser preenchida, sem sobrar espaços vazios. A Figura 2 mostra os tipos de encaixe descritos
anteriormente (DIAS, 1991).
Figura 2. Tipos de Preenchimento
Fonte: Adaptado de Vinadé (1997).
A eficiência do processo de posicionamento das figuras é determinada pela razão entre a
soma das áreas das figuras envolvidas e a área do objeto delimitador (VINADÉ, 1997). As
Equações Equação 1, Equação 2 e Equação 3 mostram os valores limites de eficiência que se podem
obter no processo de encaixe, cobertura e enchimento, respectivamente. As equações se baseiam no
modelo apresentado por Vinadé (1997), onde Ap refere-se a soma das áreas das figuras utilizadas no
processo em questão e A refere-se a área onde as figuras serão posicionadas.
1
Equação 1
1
Equação 2
1
Equação 3
A Equação 1 determina que quanto mais próximo de 1 for o valor resultante da equação,
melhor será o rendimento do processo de encaixe das figuras. Onde valores próximos de 1,
significam que a soma da área das figuras encaixadas é próximo do valor da área do retângulo que
delimita a área de encaixe. Fazendo que o desperdício de matéria-prima seja menor. Apesar da
26
porcentagem da área ocupada pelas figuras ser um fator de medição da qualidade do processo de
encaixe, será considerado o comprimento ocupado pelas figuras encaixadas como sendo o fator de
decisão de qualidade. Assim o menor comprimento das figuras encaixadas determinará o melhor
encaixe.
27
3 DESENVOLVIMENTO
3.1 Métodos utilizados para resolução dos problemas de encaixe
A metodologia abordada nesta pesquisa considerou uma seqüência de passos que definiram
o processo de encaixe das figuras. O processo envolveu, de forma mais geral, três procedimentos: a
ordenação das figuras, o encaixe das figuras e a garantia de não sobreposição destas figuras. A
ordenação das figuras utilizou dois métodos metaheurísticos: Algoritmos Genéticos e Simulated
Annealing. O encaixe das figuras foi feito utilizando a regra de movimento left-bottom e a garantia
de sobreposição foi feita utilizando um processo de verificação se um ponto é interno a um
polígono, este processo de verificação utilizou um método denominado nesta pesquisa como PNP
(ponto no polígono) e uma função de verificação de intersecção entre duas retas, função esta,
apresentada nos trabalhos de Dias (1991) e Vinadé (1997), denominada função D.
3.1.1 Ordenação das figuras
O processo de ordenação das figuras foi o responsável por definir a ordem que cada figura
deveria ser encaixada. Foram utilizados métodos metaheurísticos para a definição da ordem das
figuras. Estes métodos não exigem um elevado esforço computacional, permitindo assim, a busca
pela melhor ordem de encaixe das figuras durante o processo.
3.1.1.1 Algoritmos Genéticos
Introdução
Os Algoritmos Genéticos estão incluídos na classe de métodos evolucionários. Os métodos
evolucionários pertencem a uma classe de métodos que se baseiam em mecanismos probabilísticos.
Estes métodos probabilísticos se diferem de métodos determinísticos por não necessitarem de
características de continuidade e diferenciabilidade. Dentro do contexto de métodos probabilísticos
há os métodos estocásticos que se baseiam na classe de métodos probabilísticos (BEZ, 2005).
Mesmo os Algoritmos Genéticos pertencerem à classe de algoritmos probabilísticos de busca e
otimização, estes não são aleatórios. Estes se utilizam de conceitos de probabilidade, mas não de
buscas aleatórias que, pelo contrário, dirigem a busca para regiões do espaço onde é “provável” que
os pontos ótimos estejam (CORRÊA, 2000).
28
Os algoritmos genéticos foram introduzidos por Holland em 1975 no seu livro "Adaptation
in Natural and Artificial Systems" (BEZ, 2005). Representam técnicas de buscas baseadas na
seleção natural, que foi apresentada por Charles Darwin em 1858 com sua Teoria da Evolução. Os
trabalhos de Holland juntamente com a publicação “Genetic Algorithms in Search, Optimization
and Machine Learning” de Goldberg (1989) são considerados pioneiros sobre este tema (BEZ,
2005).
Os métodos evolucionários como já citado, são baseados na teoria da evolução de Charles
Darwin. A partir de uma população inicial, a busca é realizada com base na seleção do indivíduo
mais apto. A aptidão de cada indivíduo é medida a cada geração que surge, onde os indivíduos mais
aptos ou adaptados se destacam para uma seleção. Segundo Bez (2005), os métodos evolucionários
operam sobre uma população de soluções potenciais, aplicando o princípio de sobrevivência do
mais apto para produzir melhores aproximações para uma solução.
Segundo Goldberg (1989 apud CORRÊA, 2000), os algoritmos genéticos possuem as
seguintes características:
•
Operam sobre uma população, que é o equivalente a um conjunto de pontos, não a partir
de um único ponto;
•
Operam num espaço de soluções codificadas, não no espaço de busca diretamente;
•
Necessitam somente de informações sobre o valor de uma função objetivo para cada
membro da população, não requerendo que a função seja diferenciável ou contínua; e
•
Usam regras de transições probabilísticas, neste caso referente à mudança de um estado
para outro, diferentes da utilização de regras determinísticas.
Os algoritmos genéticos partem de uma população inicial de indivíduos. Estes indivíduos
irão evoluir e se modificar através recombinação entre os indivíduos e mutações que ocorrerão em
uma parcela da população. Os indivíduos mais aptos sobreviverão, sendo que a aptidão é definida
através de uma função denominada justamente de função de aptidão ou avaliação. Esta função irá
classificar os indivíduos pelo seu grau de aptidão (BEZ, 2005).
genético pode ser vista na Figura 3.
29
A estrutura de um algoritmo
Figura 3. Estrutura do algoritmo genético
Fonte: Adaptado de Bez (2005).
Tanomaru (1995, apud ROSÁRIO, 2002) sugere a seguinte definição para algoritmos
genéticos: “Algoritmos Genéticos (AGs) são métodos computacionais de busca baseados nos
mecanismos de evolução natural e na genética. Em AGs, uma população de possíveis soluções para
o problema em questão evolui de acordo com operadores probabilísticos concebidos a partir de
metáforas biológicas, de modo que há uma tendência de que, na média, os indivíduos representem
soluções cada vez melhores à medida que o processo evolutivo continua”.
Conceitos dos Algoritmos Genéticos
A partir do próximo tópico, serão mostrados outros aspectos do algoritmo genético. Para
isso, fazem-se necessários o entendimento de conceitos importantes presentes neste algoritmo.
Segue abaixo a descrição destes conceitos com base na descrição feita por Bez (2005).
•
Função Aptidão: é conhecida como Fitness, trata-se do mecanismo de avaliação
utilizado a cada geração processada. Cada indivíduo possui um valor desta função, valor
30
este, que irá definir o nível de adaptação deste indivíduo no ambiente. Quanto melhor o
valor da função, mas são as chances do individuo sobreviver, se perpetuar e gerar
descendentes.
•
Gene: é a representação de cada parâmetro. É através deste que as características dos
indivíduos serão transmitidas.
•
Genótipo: é a constituição genética do indivíduo. Nos algoritmos genéticos, ele é
responsável pela distribuição dos genes num cromossomo.
•
Fenótipo: é o cromossomo codificado.
•
Cromossomo: representa uma possível solução. Ele é formado por um conjunto de
genes e é responsável pela informação genética do indivíduo.
Representação e codificação
Originalmente, os Algoritmos Genéticos possuem representação binária (zero-um), sendo
que atualmente, também podem apresentar uma representação decimal ou mesmo uma
representação baseada na ordem. Essa representação baseada na ordem torna-se eficaz no problema
do caixeiro viajante (BEZ, 2005).
Utilizando a terminologia Genética, cada indivíduo no espaço de busca, é um fenótipo
correspondente a realização de um dado código, neste caso, o seu genótipo. A escolha da
codificação para um determinado problema é a escolha da função ou regra que associa os elementos
do espaço dos genótipos, com aqueles do espaço de busca, os fenótipos (ROSÁRIO, 2002).
Ao utilizar uma representação do tipo posicional, a posição de cada gene no cromossomo
influencia diretamente no fenótipo. Seja uma representação do indivíduo dada por 10110001, este
indivíduo será diferente de um indivíduo com representação 10100110, isso porque a representação
posicional considera a posição dos genes. O primeiro indivíduo tem o fenótipo 177 e o segundo
indivíduo tem o fenótipo 166. Em uma representação não posicional, os fenótipos mostrados acima
serão considerados iguais, visto que neste tipo de representação, a quantidade de genes com valor 1
é que são considerados, portanto os indivíduos possuem fenótipo 4 (BEZ, 2005).
Operadores Genéticos
Os operadores genéticos são de fundamental importância para os algoritmos genéticos. São
estes operadores que irão evoluir os indivíduos (cromossomos) e sem eles, os indivíduos
31
permanecem inalterados. Sem a utilização dos operadores, as evoluções não ocorreriam,
impossibilitando o processo de otimização.
Segundo Goldberg (1989, apud BEZ, 2005), os operadores conhecidos por seleção,
cruzamento e mutação apresentam bons resultados em problemas de otimização aplicando
algoritmos genéticos. Estes operadores serão vistos a seguir.
Seleção
A seleção tem por objeto fazer com que os indivíduos mais aptos tenham uma maior
probabilidade de serem inseridos na nova população. A seleção utiliza-se do valor de aptidão que
cada indivíduo possui, e assim aplicar-se, conforme a técnica pré-definida, a escolha dos indivíduos
que formarão nova população.
Dentre os processos de determinação de uma nova população, Barbosa (1997, apud
ROSÁRIO, 2002) apresenta um esquema de seleção que pode ser enquadrado em uma das seguintes
categorias:
•
seleção estabilizante, também chamada normalizante, tende a eliminar indivíduos com
valores extremos de aptidão;
•
seleção direcional, que tem o efeito de aumentar (ou diminuir, em caso de minimização)
a aptidão média da população;
•
seleção perturbante, que tende a eliminar os indivíduos moderados de aptidão.
Outros métodos de seleção são conhecidos, podendo-se destacar o método da roleta e o
método elitista.
O método da roleta consiste inicialmente em colocar os indivíduos em uma roleta atribuindo
a cada um destes indivíduos uma parte proporcional à sua aptidão, sendo assim, os indivíduos mais
aptos tem um valor maior na roleta, aumentando a probabilidade de estarem na nova população. Em
seguida, roda-se a roleta e o indivíduo correspondente à fatia onde a agulha parar permanecerá para
a próxima geração. A roleta é acionada quantas vezes forem necessárias para gerar a quantidade de
indivíduos requerida para formar a população. A Figura 4 ilustra o processo de seleção pelo método
da roleta, nesta, as partes possuem tamanhos diferenciados que expressão as diferentes
probabilidades dos indivíduos. Já o método elitista, é um processo que previne a eliminação dos
melhores indivíduos e mantendo sempre na população os indivíduos mais aptos. O método consiste
32
na ordenação de todos os indivíduos em ordem decrescente ou crescente, de acordo com o tipo do
problema, do valor de aptidão. Retiram-se os n primeiros indivíduos, onde n é a quantidade de
indivíduos requerida para formar a população.
Figura 4. Método da roleta
Fonte: Boechel (2005).
Cruzamento
Este operador genético é conhecido na literatura inglesa como crossover e é responsável
pela reprodução dos indivíduos da população. O cruzamento irá gerar indivíduos a partir da
combinação do material genéticos de pelo menos dois “pais” e irá gerar um ou dois “filhos”. A
seguir serão mostrados três tipos de cruzamento, sendo eles: cruzamento simples, cruzamento de
dois pontos e cruzamento uniforme.
Cruzamento simples
Após a seleção dos indivíduos que irão efetuar um cruzamento, é feito um sorteio de uma
posição de crossover e é feita a troca de material genético entre esses indivíduos “Pais”. A Figura 5
mostra a troca do material genético entre o “Pai 1” e o “Pai 2”, resultando no “Filho 1” e ‘Filho 2”.
É importante perceber que a troca dos genes foi efetuada na posição três do cromossomo.
Os valores expressados nos cromossomos utilizam a notação decimal e são valores definidos
sem seguir um padrão. São valores decimais sem repetição, apenas exemplificam as operações
feitas sobre os cromossomos.
33
Figura 5. Cruzamento simples
Fonte: Adaptado de Rosário (2002).
Cruzamento de dois pontos
Neste tipo de cruzamento, dois pontos são sorteados e o material genético entre esses dois
pontos é recombinado. Os genes localizados entre os dois pontos sorteados serão trocados, ou seja,
o “Filho1” terá os genes localizados entre os pontos sorteados do “Pai 1” e os genes que não
pertencem ao intervalo sorteado do “Pai 2”. O “Filho 2” terá o seu material genético formado pelo
inverso do processo realizado com o “Filho 1”. A Figura 6 ilustra o cruzamento de dois pontos.
Figura 6. Cruzamento de dois pontos
Fonte: Adaptado de Rosário (2002).
Cruzamento uniforme
Neste cruzamento é introduzida uma máscara que irá definir as posições de troca de genes.
Neste caso, trata-se de uma máscara de bits (01001) com o mesmo comprimento do cromossomo
que indicará a ocorrência ou não da troca de genes no ponto determinado. Uma máscara m formada
por 1 0 1 0 1 indicará que as posições um, três e cinco terão trocas de genes entre os “Pais”. A
Figura 7 exemplifica esta troca de genes com a utilização de uma máscara.
Figura 7. Cruzamento uniforme
Fonte: Adaptado de Rosário (2002)
Um problema decorrente dos cruzamentos realizados entre os cromossomos é a
inconsistência. Trata-se de um problema com os cromossomos filhos, onde seus genes se repetem
34
no mesmo cromossomo. Este problema pode ocorrer, por exemplo, no cruzamento simples ou de
dois pontos. Para esses casos, é sorteada uma posição aleatória e a troca de genes é realizada. Neste
momento, o cromossomo dos “pais” pode repetir algum gene nos filhos gerados. Esta condição não
pode acontecer, assim é preciso efetuar um tratamento de inconsistência.
Para o tratamento de inconsistências, podem ser aplicados diversos métodos. Entre estes
métodos, há o operador PMX (Partially Mapped Crossover). Este operador funciona com o
cruzamento de dois pontos, onde se percorre o cromossomo testando cada gene. Inicia-se o percurso
a partir da posição de corte 2. Para cada gene é testado se o mesmo se repete, caso este gene esteja
repetido, efetua-se a troca do gene na posição testada pelo gene relativo do outro filho gerado. Este
teste é feito para todos os genes do cromossomo. A Figura 8 mostra o operador PMX. Os genes
marcados com “*” se repetiram e foram trocados pelos genes marcados com uma seta. A troca dos
genes é feita com o gene do outro filho gerado.
Figura 8. Tratamento de Inconsistência por PMX
Além do operador PMX, utilizam-se os operadores OX (Order Crossover), CX (Cycle
Crossover) e outros para o tratamento de inconsistência (GOLDBERG, 1989). No caso do operador
OX, seleciona-se um fragmento de um dos “pais” e este fragmento é adicionado ao “filho”
mantendo a posição dos genes no cromossomo. Este fragmento é obtido a partir de dois pontos do
cromossomo. Então os genes não preenchidos do “filho” serão completados com os genes do outro
“pai”. Para isso percorre-se o segundo “pai” selecionando seus genes unitariamente. Para cada gene
selecionado, verifica-se se o mesmo já existe no filho gerado, caso não se exista, este gene é
adicionado ao “filho”. A Figura 9 mostra os passos da aplicação do operador OX.
35
Figura 9. Tratamento de Inconsistência por OX
Fonte: Mendes (1999).
Mutação
Segundo Bez (2005), o operador genético de mutação tem como principal objetivo
introduzir algumas características que não estão presentes na população inicial. Nesse processo, os
indivíduos são escolhidos aleatoriamente.
A mutação poderá proporcionar novas regiões promissoras no espaço de busca, afinal novos
indivíduos com características diferentes surgirão na população.
O processo de mutação é simples, basta selecionar um ou mais genes do cromossomo e
então efetuar a troca destes genes. O processo de seleção dos genes é realizado através de uma
escolha aleatória. A Figura 10 exemplifica o processo de mutação em um indivíduo com notação
binária.
Figura 10. Mutação
Fonte: Adaptado de Rosário (2002).
O operador de mutação não precisa se restringir a troca de apenas um gene, podem-se
escolher n genes e assim efetuar a troca dos mesmos. Outro processo é a escolha de dois pontos no
cromossomo e partir destes pontos, mudarem a ordem dos genes entre esses pontos conforme a
Figura 11. Esta figura representa um cromossomo com notação decimal.
36
Figura 11. Mutação com mudança na ordem dos genes
Parâmetros Genéticos
Os algoritmos genéticos, como muitos métodos de otimização, possuem parâmetros que
influenciam no seu comportamento. O número de indivíduos da população, a taxa de cruzamentos e
a taxa de mutação são os parâmetros dos algoritmos genéticos.
O número de indivíduos é importante para a definição do espaço de busca. A utilização de
poucos indivíduos acarreta na redução deste espaço de busca e problemas de convergência
prematura, já a utilização de um número maior de indivíduos resultará em uma maior cobertura do
espaço de busca, prevenindo esta convergência prematura. O tamanho da população está ligado ao
esforço computacional exigido pelo o algoritmo (BEZ, 2005).
Quanto maior a taxa de cruzamento, mais rapidamente novos indivíduos serão introduzidos
na população. Com uma taxa de mutação muito alta a busca se torna essencialmente aleatória. Bons
resultados geralmente são obtidos com valores baixos para a taxa de mutação, o qual introduz e
mantém a diversidade genética da população (CORRÊA, 2000 apud ROSÁRIO, 2002).
O importante é perceber que os cruzamentos de cromossomos irão gerar os indivíduos com
mais chances de sobrevivência, e a mutação poderá tornar esses indivíduos mais aptos na
população, norteando a busca.
Pseudocódigo de um AG
Barbosa (1997, apud ROSÁRIO, 2002), descreve um algoritmo que consegue englobar a
grande maioria dos algoritmos genéticos existentes, conforme a Figura 12.
37
Algoritmo Genético genérico
1.
Inicialize a população
2.
Avalie indivíduos na população
Repita
3.
Selecione indivíduos para reprodução
4.
Aplique os operadores de recombinação e mutação
5.
Selecione indivíduos para sobreviver
Até critério de parada satisfeita
Fim
Figura 12. Algoritmo genético genérico
Fonte: Adaptado de Barbosa (1997, apud ROSÁRIO, 2002).
As linhas enumeradas são processos do algoritmo onde estão incluídos os operadores
genéticos.
O primeiro passo é a inicialização da população, que criará a primeira geração de indivíduos
que será utilizada inicialmente pelo algoritmo. No segundo passo, é a avaliação inicial dos
indivíduos da população, esta avaliação irá efetuar a primeira ordenação dos indivíduos conforme
suas aptidões. Os próximos passos irão acontecer em um loop, cujo não irá terminar até que um
critério de parada seja satisfeito. No terceiro passo é feita a seleção dos indivíduos que irão se
reproduzir, a escolha poderá ser aleatória ou pelo grau de aptidão dos indivíduos, ou seja, um
número n de indivíduos mais aptos serão selecionados. O quarto passo contempla o cruzamento dos
indivíduos e a mutação dos mesmos, para o mesmo são aplicados os operadores de cruzamento de
mutação explicados anteriormente. E no quinto passo é feita a seleção dos indivíduos que irão
sobreviver. Os passos três, quatro e cinco ocorrem em um loop até que um critério de parada seja
satisfeito.
3.1.1.2 Algoritmo Simulated Annealing
O Simulated Annealing é uma técnica heurística que foi publicada inicialmente por
Metropolis et al (1953 apud BEZ, 2005) e baseia-se no processo de recozimento que ocorre na
indústria metalúrgica, no qual se busca a obtenção de um material sem impurezas (METROPOLIS
et al, 1953; KIRKPATRICK et al, 1983 apud BEZ, 2005).
Busseti (2001a apud GOMES, 2003) afirma sobre o Simulated Annealing que, “Sua
principal vantagem sobre os outros métodos é a sua habilidade e flexibilidade para se aproximar do
ótimo global. O algoritmo é bastante versátil desde que ele não dependa de alguma propriedade
restritiva do modelo”.
38
Segundo Oliveira (2004), a técnica publicada por Metropolis et al. em 1953 trata de um
método numérico simples que representa o estado de um conjunto de átomos em equilíbrio em uma
certa temperatura. O método era análogo ao processo de recozimento (annealing) da indústria
metalúrgica. Este processo trata a exposição do metal a altas temperaturas, fazendo com que os
átomos do metal vibrem violentamente. Após a elevação da temperatura, o metal é esfriado
gradualmente para que os átomos atinjam padrões estáveis. Com base neste processo, surgiu o
algoritmo de simulação computacional Simulated Annealing ou Recozimento Simulado
(OLIVEIRA, 2004).
O comportamento dos átomos pode ser observado na Figura 13, Figura 14 e Figura 15. Estas
figuras representam respectivamente: a desordem dos átomos durante a elevação da temperatura,
onde os átomos estão se agitando por causa desta elevação na temperatura; um resfriamento brusco
da temperatura, provocando assim, um estado conhecido como amorfo, onde o nível de energia via
baixar rapidamente deixando este estado menos estável que o estado da Figura 15, esse resfriamento
rápido estaciona os átomos; e um estado onde a temperatura foi diminuída lentamente, ao contrário
da Figura 14 que teve uma diminuição brusca da temperatura. Este estado mostra um
comportamento ordenado das moléculas por causa da diminuição gradativa da temperatura
(NORONHA, 2000). A Figura 13 representa as moléculas se agitando, sendo as setas uma
indicação do movimento das moléculas.
Figura 13. Estado desordenado das moléculas da matéria em fusão
Fonte: Adaptado de Noronha (2000).
39
Figura 14. Estado desordenado das moléculas após a um resfriamento rápido
Fonte: Adaptado de Noronha (2000).
Figura 15. Estado ordenado das moléculas após a um resfriamento lento
Fonte: Adaptado de Noronha (2000).
Segundo Bez (2005), “Simulated Annealing, como todo método estocástico, tem como
característica uma busca exploratória estocástica, ou seja, aleatória. A origem desta técnica
computacional é da mecânica estatística e tem como objetivo principal determinar soluções
próximas do menor custo global para grandes problemas de otimização”.
O algoritmo apresentado por Metropolis et al. (1953 , apud BEZ, 2005) tira o nome do fato
que seu procedimento de otimização simula o resfriamento lento da matéria. A principal variável de
controle é chamada temperatura, por analogia ao fenômeno físico. Na Figura 16 é apresentada a
formulação geral do Simulated Annealing,onde s* representa a melhor solução encontrada durante a
execução do algoritmo (NORONHA, 2000).
40
Início
Estabelecer uma solução realizável S0;
s = s0;
Determine uma temperatura inicial T > 0;
Enquanto o sistema não estiver resfriado faça
efetuar L iterações de:
escolher aleatoriamente um vizinho v ∈ v(s)
∆ = objetivo(ν) – objetivo(s)
Se ∆ < 0 então
s = v;
Se objetivo(ν) < objetivo(s*) então
s* = ν;
Senão
s = ν com a probabilidade Fim da Busca Interna;
Reduzir a temperatura;
Fim do Enquanto
∆
;
Fim
Figura 16. Simulated Annealing
Fonte: Adaptado de Noronha (2000).
Segundo Noronha (2000), este algoritmo decompõe duas grandes buscas sobrepostas. A
busca externa que controla o término do processo e é baseado na noção de estado resfriado e a
busca interna que contém o processo de otimização.
Durante a busca interna, para uma determinada temperatura, escolhe-se um vizinho (v)
aleatoriamente. Caso v seja um vizinho melhor, neste caso seu valor objetivo deverá ser inferior ao
valor objetivo da solução corrente s, v será aceito como uma nova solução. Caso a passagem de s a
ν degrade o objetivo, aceita-se o movimento com uma probabilidade ligada a diferença das
quantidades objetivo e a temperatura corrente. Isto é um mecanismo de aceitação condicional das
“ascensões” que permitem ao método de sair dos mínimos locais. Ao fim de L iterações diminuemse a temperatura (NORONHA, 2000).
Quando a temperatura se eleva, praticamente todos os movimentos serão autorizados.
Quanto mais a temperatura é reduzida, mais as degradações serão penalizadas em função de lucro
dos movimentos melhores, e assim, o método então convergirá para o ótimo local mais próximo
(NORONHA, 2000).
Será considerado que o problema está resfriado no seu estado se não houver mais chances de
se achar uma melhor solução na continuação da exploração. Dentre os numerosos critérios para
tomar a decisão de parar o algoritmo, um dos mais utilizados é a não melhoria do objetivo em certo
número n de iterações a uma determinada temperatura (NORONHA, 2000).
41
Uma revisão do algoritmo é a administração da temperatura. Existem numerosas regras de
administração da temperatura. A mais simples consiste em trabalhar a temperatura fixa
(NORONHA, 2000). Um caso freqüentemente encontrado é a diminuição lenta da temperatura.
Para este, existem dois parâmetros a ajustar: a temperatura inicial e a regra de diminuição da
mesma. A temperatura pode ser diminuída, por exemplo, através de um valor fixo, onde é definido
um valor para a diminuição e temperatura é decrementada. Hajek (1988 apud NORONHA, 2000)
propôs uma diminuição logarítmica da temperatura que assegura a convergência do algoritmo. A
temperatura evolui segundo a Equação 4:
ln 1
Equação 4
onde Tk é a temperatura na iteração k. Hajek (1988 apud NORONHA, 2000) apresentou as regras de
diminuição de “C” assegurando a convergência do algoritmo sob reserva que a vizinhança tenha
boas propriedades. Na Figura 17 é apresentada uma modificação do algoritmo do Simulated
Annealing que foi apresentado anteriormente para contemplar a administração da temperatura.
Neste algoritmo, a função de probabilidade é modificada para contemplar o modelo de
administração de temperatura.
Início
Estabelecer uma solução realizável S0;
s* = s = s0;
k = 0;
Determine uma temperatura inicial T > 0;
Enquanto o sistema não estiver resfriado faça
k = k + 1; escolher aleatoriamente um vizinho v ∈ v(s)
∆ = objetivo(ν) – objetivo(s)
Se ∆ < 0 então
s = v;
Se objetivo(ν) < objetivo(s*) então
s* = ν;
Senão
s = ν com a probabilidade
Reduzir a temperatura;
Fim do Enquanto
∆/ ;
Fim
Figura 17. Simulated Annealing
Fonte: Adaptado de Noronha (2000).
3.1.2 Encaixe das Figuras
O encaixe consistiu no posicionamento das figuras conforme a ordem definida a partir da
utilização das metaheurísticas apresentadas anteriormente. O posicionamento das figuras utilizou o
processo left-bottom. O left-bottom, como o nome já diz, trata-se do movimento das figuras no
42
sentido esquerdo e inferior. Neste caso, as figuras antes de serem encaixadas, estarão posicionadas
em coordenadas aleatórias que variarão conforme a criação destas figuras. O left-bottom funcionou
como uma regra de encaixe, onde todas as figuras são encaixadas, ou posicionadas, seguindo a regra
do sentido esquerdo e inferior. A Figura 18 mostra o sentido do encaixe por left-bottom. O
responsável pela qualidade do encaixe é o processo de ordenamento das figuras.
Figura 18. Left-Bottom
3.1.3 Tratamento de Sobreposição das Figuras
O tratamento de sobreposição garantiu que as figuras posicionadas não ficassem
sobrepostas. Foi um processo importante do algoritmo, pois a partir da ordem das figuras geradas
pelas metaheurísticas, o processo de encaixe das figuras inicia o posicionamento das mesmas
utilizando left-bottom. O processo de encaixe necessita de uma verificação de sobreposição e uma
correção do posicionamento das figuras, que é realizado nesta parte do algoritmo.
Este trabalho sugeriu um método chamado de função PNP (Ponto no polígono), trata-se de
um método para verificar se um ponto é interno ou não a um polígono. Os trabalhos de Dias (1991)
e Vinadé (1997) descrevem dois métodos denominados para o ajuste das figuras denominados
Intersecção de Matrizes e Função D.
A função D em particular, utiliza-se da geometria analítica para verificar a intersecção entre
duas retas. É possível saber através do valor resultante da função, se um segmento de reta está ou
não fazendo intersecção com outra reta de um polígono, podendo assim identificar uma possível
43
sobreposição entre os polígonos. A função D foi utilizada durante a verificação de sobreposição do
algoritmo.
3.1.3.1 Função PNP
A função PNP verifica se um ponto, neste caso se uma coordenada (x,y) é interna a um
polígono. Para que isso seja possível, a função utiliza-se a idéia de traçar uma reta que cortará o
polígono em questão. Esta reta poderá ter qualquer direção, sendo que a partir do ponto em questão,
traça-se uma reta de uma direção única qualquer. A partir desta reta, são verificadas quantas
intersecções ela possui com o polígono, esse número de intersecções ou cruzamentos é conhecido
como crossing number. Caso o número de intersecções seja “par”, significará que o ponto é externo
ao polígono, caso o número de intersecções seja “ímpar”, significará que o ponto é interno ao
polígono (HAINES, 1994). A Figura 19 ilustra as intersecções da reta, nesta figura são utilizados
polígonos não convexos para exemplificar uma maior quantidade de intersecções do ponto com os
segmentos do polígono.
Figura 19. Ponto interno ao polígono
Alguns tratamentos são necessários durante a identificação da quantidade de cruzamentos
existentes entre o ponto de verificação e o polígono em questão. A Figura 20 exemplifica alguns
problemas existentes com os cruzamentos entre os segmentos do polígono.
44
Figura 20. Quantidade de cruzamentos nos segmentos do polígono
O algoritmo segue algumas regras durante a verificação do ponto interno ao polígono.
Conforme mostrado na Figura 20, há o problema de traçar uma reta que corte um ponto de junção
entre dois segmentos ou esta reta traçar um segmento por completo, neste caso, a reta teria o mesmo
ângulo do segmento traçado. Por estes casos, definiu-se que o algoritmo traçará sempre uma reta
horizontal (sem ângulo ou ângulo de 0º) para a verificação da quantidade de cruzamento ocorridos,
segmentos horizontais são excluídos da verificação e um segmento inclui seu ponto inicial e exclui
seu ponto final da verificação. A inclusão ou exclusão do ponto inicial e final do segmento faz que
quando uma reta traçar um ponto de junção entre dois segmentos seja possível definir o cruzamento
de forma correta conforme definido neste problema.
3.1.3.2 Intersecção de Matrizes
O método consiste na discretização da área de encaixe e das figuras que serão encaixadas em
uma matriz de bits. O valor nulo desta matriz representa uma área vazia (DIAS, 1991; VINADÉ,
1997). A Figura 21 ilustra a representação de uma figura por uma matriz de bits.
45
Figura 21. Representação de uma figura em matriz de bits
Fonte: Dias (2000).
O posicionamento das figuras com a utilização do método de intersecção de matrizes ocorre
percorrendo a área maior com a matriz de bits da figura em questão. Serão executadas rotinas para
verificar a sobreposição de figuras. Para a nova posição da figura discretizada, é verificado se os
pontos dos vértices estão em uma área já ocupada e uma verificação com os pontos das arestas da
peça. Somente após esses passos, é definida a nova posição da figura (VINADÉ, 1997).
3.1.3.3 Método de Deslizamento e Função D
Um processo de posicionamento das figuras pode ser a partir de um deslizamento das
figuras no plano de encaixe. Considerando que as figuras são formadas por segmentos de retas é
possível fazer uma aproximação da figura que será encaixada com as demais. Utiliza-se a definição
de uma direção de deslizamento e a partir da obtenção da distancia de um ponto a uma reta o
deslizamento é realizado (DIAS, 1991). Segundo Dias (1991), a técnica de posicionamento das
figuras por deslizamento foi proposta por Bernardo (1987, apud DIAS, 1991). Defini-se através de
um vetor V a direção que a figura será deslocada e com a utilização de uma função denominada D é
possível definir quais arestas das figuras já posicionadas fazem intersecção com a figura que se
deseja posicionar. Assim é possível determinar a distância de colisão entre os vértices das figuras já
posicionadas e obter um conjunto de valores mínimos de deslocamento para a figura que será
posicionada até o momento (DIAS, 1991).
46
A partir da função D é possível conhecer a posição relativa de um ponto com relação a uma
reta. A função D é obtida a partir da equação que calcula a distância de um ponto P a uma reta AB
(DIAS, 1991). A distância (d) de um ponto P a uma reta AB é dada pelas Equação 5 e Equação 6:
! " #$ ! $% & ! $ ! $" ! % '
Equação 5
onde:
2
2
' () ! * $) ! $* Equação 6
A Figura 22 mostra os elementos de cálculo da distância entre o Ponto P e a reta AB.
Figura 22. Exemplificação de Ponto e Reta
Fonte: Adaptado de Dias (1991).
Segundo Dias (1991), a função D é definida pelo produto de d e L. A posição relativa do
ponto P em relação a reta AB é dada pelo sinal do valor resultante da função D. Dias (1991), diz que
partir da função D, pode-se saber que:
•
P encontra-se à esquerda de AB se o valor de D > 0;
•
P encontra-se à direita de AB se o valor de D < 0;
•
P encontra-se sobre o segmento AB se o valor de D = 0;
47
O teste de intersecção das peças com a utilização da função D exige que todos os segmentos
da peça sejam verificados. Para este, deve-se percorrer cada segmento de reta da figura e verificar
se este segmento faz intersecção com algum outro segmento das figuras já encaixadas. A partir de
dois segmentos de retas formados, por exemplo, pelos pontos AB e CD, uma possível intersecção
ocorrerá se os sinais dos resultados da aplicação da função D do ponto A para o segmento CD e do
ponto B para o segmento CD forem contrários. A intersecção só será confirmada se os sinais da
aplicação da função D para os pontos C e D em relação ao segmento AB também forem contrários
(DIAS, 19991). A Figura 23 ilustra a intersecção das retas AB e CD.
Figura 23. Intersecção das Retas AB e CD
Fonte: Adaptado de Dias (1991).
3.2 Modelagem algorítmica
A seqüência de passos descrita anteriormente para definição do processo de encaixe das
figuras envolvia os procedimentos de ordenação, encaixe e a garantia de não sobreposição destas
figuras. Esta seqüência de passos possui dois modelos algorítmicos que são seguidos. Esta
diferenciação se deve pelo uso de dois métodos metaheurísticos para definir a ordem das peças.
O modelo que utilizou Algoritmo Genético tem a ordem de encaixe de cada figura definida
pelo cromossomo. Por exemplo, em um encaixe de 10 figuras, estas figuras foram enumeradas e
assim geraram-se os cromossomos. Estes possuíam 10 genes, referentes a cada figura deste
exemplo. A ordem dos genes no cromossomo foi a ordem que cada figura foi encaixada. Para um
48
cromossomo com genótipo: 5 1 8 9 6 3 7 4 2 10 significam que a primeira figura encaixada foi a de
número 5, a segunda figura encaixada foi a de número 1 e assim por diante.
Durante a execução do Algoritmo Genético, é necessário definir os melhores indivíduos para
então permitir ao algoritmo convergir para o indivíduo mais apto. O indivíduo mais apto foi o que
permitiu a obtenção do menor comprimento da área utilizada para o encaixe de todas as figuras.
O fitness, neste caso, a aptidão dos indivíduos foi definida, como informado anteriormente,
pelo menor comprimento da área de encaixe das figuras cuja seqüência destas figuras foi definida
pelo indivíduo em questão.
A seleção dos melhores indivíduos necessita que este valor de aptidão de cada indivíduo já
esteja calculado, assim antes de efetuar a seleção dos indivíduos é necessário efetuar o encaixe das
figuras para cada indivíduo da população e assim, efetuar a seleção dos mais aptos (com menor
comprimento de encaixe). O algoritmo tem como critério de parada inicial um número n de
iterações.
O modelo que utilizou Simulated Annealing para definição da ordem das figuras que foram
encaixadas utilizou uma solução inicial s. Esta solução é definida por uma seqüência de valores que
define o número da figura encaixada. Conforme o modelo que utilizou Algoritmo Genético, onde
um cromossomo possuía a ordem das figuras encaixadas, a solução s utilizada no Simulated
Annealing, também possui uma lista de ordens de figuras. Assim durante a execução do algoritmo, a
cada solução gerada é calculado o valor objeto desta solução (neste caso o valor de objetivo é
comprimento da área das figuras encaixadas). Conforme as regras do algoritmo, ao final a solução
que gerar o menor comprimento da área de encaixe é escolhida.
Para ambos os modelos de encaixe, o processo de posicionamento das figuras é o mesmo.
As figuras são movidas no sentido esquerdo e inferior e a cada iteração de movimentação é feita
uma verificação de sobreposição. Caso o movimento deixe a figura sobrepondo as demais figuras já
encaixadas, este movimento é cancelado.
A verificação de sobreposição foi inicialmente planejada para utilizar apenas a função PNP,
sendo que também foi necessária a utilização da função D. A função PNP apenas verifica se um
ponto é interno ao polígono, mas há casos em que este procedimento não é suficiente, assim sempre
que a função PNP retorna a informação que não há sobreposição, é feita uma verificação com a
função D para certificar que não há uma sobreposição de segmentos de retas. A Figura 24 ilustra um
49
tipo de sobreposição onde não há pontos internos aos polígonos, apenas intersecções entre os
segmentos.
Figura 24. Intersecção de segmentos de reta
3.3 Ensaios Numéricos
A realização dos ensaios numéricos envolveu a definição de um conjunto de figuras que
serviram para toda a coleta de dados que foi efetuada. Foram definidas 48 figuras com tamanhos e
formas geométricas variadas. Estas figuras são exemplos de peças encontradas na indústria têxtil,
portanto possuem formas geométricas não convexas.
A coleta de dados para ambos os processos de encaixe, neste caso, para o processo que
utilizou Algoritmo Genético e o processo que utilizou Simulated Annealing, foi realizada com a
definição de diferentes valores para os parâmetros necessários para cada processo. A Figura 25
mostra as figuras que foram utilizadas durante os testes dos algoritmos.
Os ensaios numéricos aplicados ao Algoritmo Genético e Simulated Annealing consideraram
respectivamente como valor de Aptidão e Objetivo, o comprimento necessário para o encaixe das
figuras. Não foram consideradas unidades de medidas.
Os testes foram repetidos 8 vezes para cada valor diferente dos parâmetros definidos nos
testes de cada metaheurística. Foram totalizadas 360 execuções do processo de encaixe. A média de
50
tempo para o processo por Algoritmo Genético variou de 293 a 1.860 segundos. O processo por
Simulated Annealing teve uma variação de tempo entre 168 e 447 segundos.
Figura 25. Figuras utilizadas no encaixe
3.3.1 Ensaios realizados com Algoritmo Genético
Os ensaios numéricos realizados com o procedimento de encaixe que utilizou Algoritmo
Genético consideraram três variáveis: o tamanho da população, a taxa de cruzamento e a taxa de
mutação.
O processo completo de coleta de dados necessitou de uma análise inicial dos parâmetros
que deveriam ser utilizados para a definição cada parâmetro. Assim, inicialmente foram feitas
combinações de valores para definir qual o tamanho da população, taxa de cruzamento e taxa de
mutação deveriam ser utilizados para o inicio dos testes.
Definiu-se que o tamanho inicial da população seria de 25 indivíduos e que a taxa de
mutação seria de 5%. A taxa de cruzamentos que variou de 25% a 75% nos primeiros testes. A
Figura 26 mostra os resultados da variação da taxa de cruzamentos.
51
Taxa de Cruzamentos
311
Valor Aptidão
310
309
308
307
306
305
Percentual de
25
35
45
55
65
75 Cruzameto
Figura 26. Definição da Taxa de Cruzamentos
A Figura 26 mostrou que a melhor taxa de cruzamentos foi o valor de 65% da população. O
segundo parâmetro que foi analisado foi a taxa de mutação. Esta análise manteve o tamanho da
população já definido de 25 indivíduos e a taxa de cruzamentos em 65% conforme definida na
análise anterior. A taxa de mutação variou entre 5% a 21% da população. A Figura 27 mostra os
resultados da variação da taxa de mutação.
Valor de Aptidão
Taxa de Mutação
310
309
308
307
306
305
304
303
302
301
5
7
9
13
17
21
Percentual de
Mutação
Figura 27. Definição da Taxa de Mutação
A Figura 27 mostrou que a melhor taxa de mutação foi o valor de 17% da população. Com
as taxas de cruzamento e mutação definidas, foi feita uma análise da quantidade de gerações para a
quantidade de 25 indivíduos, que já está utilizada nos testes, e também para uma quantidade de 35
indivíduos. A Tabela 3 mostra esta variação da quantidade de gerações. É possível verificar que
52
para um população de 25 indivíduos o maior número de gerações convergiu para um melhor
resultado. Já para uma população de 35 indivíduos, verifica-se o início de uma convergencia, sendo
que uma quantidade maior de gerações pudesse melhorar o resultado. É importante verificar o
tempo de processamento para cada situação, pois algumas situações possuem tempos elevados de
processamento.
Tabela 3. Variação da Quantidade de Gerações
Tamanho da População
25
25
25
25
35
35
35
35
Qtd. De Gerações
30
40
50
60
30
40
50
60
Aptidão
309,564184
309,074695
308,321043
307,611869
306,565446
307,855062
309,564395
307,317809
Tempo Processamento
394 segundos
531 segundos
648 segundos
780 segundos
562 segundos
736 segundos
925 segundos
1157 segundos
A variação do tamanho da população foi analisada e definiram-se valores de 20 a 70
indivíduos. A quantidade de gerações definida para a análise do tamanho da população foi de 30
gerações. Este valor foi definido devido ao resultado de aptidão e tempo de processamento que pôde
ser verificado na Tabela 3. A Figura 28 mostra os resultados da variação do tamanho da população
para as iterações executadas.
Valor de Aptidão
Tamanho da População
309
308,5
308
307,5
307
306,5
306
305,5
305
304,5
304
303,5
20
30
40
50
60
70 Tamanho da
População
Figura 28. Definição do Tamanho da População
A Figura 28 mostrou que o melhor resultado foi obtido foi para uma população de 60
indivíduos. É importante analisar que para uma população de 20 indivíduos, o resultado foi bem
53
próximo ao melhor obtido e o tempo de processamento para este foi cerca de 3 vezes menos ao
tempo da melhor solução. É importante registrar que normalmente quanto maior a quantidade de
indivíduos de uma população, melhor deveria ser o resultado de aptidão do melhor indivíduo. A
Figura 28 mostrou que o aumento do tamanho da população não convergiu para resultados
melhores, apenas no caso da utilização de 60 indivíduos. O que pode ter acontecido é que valores
maiores de população não tenham gerado soluções piores, mas sim, não conseguiram gerar soluções
melhores para a quantidade de gerações definida.
Durante todos os testes, verificou-se que na média os tamanhos da população próximos de
30 indivíduos e a quantidade de 30 gerações geraram bons resultados, principalmente se for
considerado o tempo de processamento.
3.3.2 Ensaios realizados com Simulated Annealing
Os ensaios numéricos realizados com o procedimento de encaixe que utilizou Simulated
Annealing consideraram três variáveis de manipulação: a temperatura inicial, o decremento da
temperatura e a quantidade de iterações do processo.
O processo completo de coleta de dados necessitou de uma análise inicial dos parâmetros
que deveriam ser utilizados para a definição cada parâmetro. Assim, inicialmente foram feitas
combinações de valores para definir qual a temperatura inicial, o decremento da temperatura e a
quantidade de iterações deveriam ser utilizados para o inicio dos testes. Definiu-se que a quantidade
de iterações inicial seria de 500 e o decremento da temperatura seria de 0,3. A temperatura inicial
foi de 50. A partir destes valores foram iniciadas as coletadas de dados. A Figura 29 mostra os
valores obtidos para a definição de uma temperatura inicial.
54
Temperatura Inicial
Valor Função Objetivo
311,5
311
310,5
310
309,5
309
308,5
308
307,5
50
100
150
230
270
320
380
450
520 Temperatura
Figura 29. Temperatura Inicial
Após a definição da temperatura inicial, foi necessário definir qual decréscimo de
temperatura possibilitou a obtenção de uma solução. Foram geradas soluções que utilizaram
diferentes valores de decremento de temperatura. A Figura 30 mostra os resultados obtidos para as
diferentes variações no decremento da temperatura. Para estes testes utilizou-se uma temperatura
inicial de 150.
Decremento da Temperatura
Valor Função Objetivo
312
311
310
309
308
307
306
305
304
0,1
0,3
0,8
1,3
1,5
1,9
2,3
2,6
3,1 Decremento da
temperatura
Figura 30. Decremento da Temperatura
A Figura 30 mostrou que o valor que decremento da temperatura que gerou a melhor
solução foi de 1,3. Já foram definidos o valor da temperatura inicial e o decremento da temperatura,
sendo que o próximo valor a ser ajustado é a quantidade de iterações. A variação da quantidade de
iterações variou de 300 a 1200. A Figura 31 mostra os resultados obtidos com os diferentes valores
da quantidade de iterações.
55
Quantidade de Iterações
Valor Função Objetivo
311
310
309
308
307
306
305
304
303
300
400
500
600
800
900
1000 1100 1200
Quantidade de
Iterações
Figura 31. Quantidade de Iterações
É possível verificar na Figura 31 que a quantidade de iterações que gerou a solução foi de
400. Assim, a melhor temperatura inicial foi de 150, o decremento de 1,3 e 400 iterações para o
processo.
3.3.3 Comparativo entre os resultados
A análise realizada entre o processo de encaixe por Algoritmo Genético e Simulated
Annealing, mostrou que o Algoritmo Genético retornou valores melhores que os valores retornados
pelo processo por Simulated Annealing. O processo realizado com Algoritmo Genético levou mais
tempo de processamento, o que pode ser um fator no momento da escolha de qual metaheurística
melhor se aplica ao processo de encaixe. A Figura 32 mostra o melhor resultado gerado pelo
Algoritmo Genético e pelo Simulated Annealing.
56
Resultado
Comprimento do encaxie
306,5
306
305,5
305
304,5
304
303,5
303
302,5
Algoritmo Genético
Simulated Annealing
Figura 32. Resultado do Algoritmo Genético e Simulated Annealing
O melhor resultado obtido com o Algoritmo Genético utilizou uma população de 25
indivíduos, uma taxa de cruzamento de 65%, uma taxa de mutação de 17% e foram geradas 30
gerações de indivíduos. O tempo de processamento foi de 395 segundos e o valor foi de
304,006023. A Figura 33 mostra os dados gerados durante a execução do teste.
Solução com Algoritmo Genético
316
Valor de Aptidão
314
312
310
308
306
304
302
1
3
5
7
9
11 13 15 17 19 21 23 25 27 29
Gerações
Figura 33. Melhor solução com Algoritmo Genético
O melhor resultado obtido com o Simulated Annealing utilizou uma temperatura inicial de
150, um valor de decremento da temperatura de 1,3 e a quantidade de iterações de 400. O tempo de
processamento foi de 133 segundos e o valor da solução foi de 306,072381. A Figura 34 mostra os
dados gerados durante a execução do teste.
57
Solução com Simulated Annealing
Valor Função Objetivo
402
382
362
342
322
302
1
16
31
46
61
76
91
106
121
136
Figura 34. Melhor solução com Simulated Annealing
Ao comparar os dois resultados gerados pelas metaheurísticas, verifica-se que o Algoritmo
Genético gerou a melhor solução, porém o tempo processamento de sua melhor solução é quase três
vezes o tempo de processamento do encaixe com Simulated Annealing.
As Figuras Figura 35 e Figura 36 mostram respectivamente o resultado do encaixe
utilizando Algoritmo Genético e Simulated Annealing. É importante perceber que foi utilizado o
mesmo algoritmo de encaixe das figuras, sendo que as diferentes ordens geradas pelas
metaheurísticas definiram o melhor resultado.
Figura 35. Resultado do encaixe com Algoritmo Genético
58
Figura 36. Resultado do encaixe com Simulated Annealing
59
4 CONCLUSÕES
Esta pesquisa apresentou um problema de encaixe de figuras irregulares e propôs uma
solução para o mesmo. São utilizadas metaheurísticas para definir a ordem que as figuras serão
encaixadas.
A opção de utilizar metheurísticas neste tipo de problema, é o foco na otimização do
processo de definição da ordem em que as figuras serão encaixadas. Este foco na utilização de
metaheurísticas no ordenamento das figuras ocorreu após perceber esta utilização em trabalhos
pesquisados.
Foram pesquisados trabalhos que trataram o problema de corte e empacotamento em geral,
pesquisaram-se livros, artigos e outras publicações sobre este tipo de problema. Esta pesquisa teve
dois grandes problemas para solucionar: um algoritmo eficiente para ordenação das figuras e um
processo rápido e eficiente de encaixe destas figuras. As metaheurísticas utilizadas, Algoritmos
Genéticos e Simulated Annealing, provaram-se eficientes quanto ao tempo de processamento para a
busca de uma solução. Em contra partida, o processo de encaixe das figuras foi o responsável pelo
maior consumo de processamento durante o processo de encaixe.
Durante os testes com o algoritmo de encaixe, verificou-se que quando há figuras com
tamanhos bem variados e com grandes diferenças nas suas áreas, a busca por soluções boas se torna
mais difícil e exigiria um processo mais lento no geral. A lentidão se daria pelo número de iterações
que seria necessário para buscar melhores soluções e mesmo assim não seria possível prever se o
elevado número de iterações resultaria em bons resultados. O processo de encaixe implementado
não efetuou nenhuma classificação e agrupamento das figuras conforme suas áreas assim couberam
as metaheurísticas encontrarem boas ordens de figuras.
A separação das figuras em grupos de menores e maiores pode ser observado no trabalho de
Dias (1991), cujo após efetuar a separação das figuras, efetua o encaixe das peças grandes e
pequenas em conjunto. É feito o encaixe de um grupo de figuras grandes, que neste caso formam
uma coluna na largura definida, e as figuras menores são encaixadas para preencher espaços que
podem ter ficado durante o encaixe das figuras grandes.
Os resultados gerados pelas metaheurísticas mostraram que o Algoritmo Genético é mais
eficiência. Este bom resultado pode ser explicado pelas próprias características dos Algoritmos
60
Genéticos, onde uma solução boa pode ser melhorada aplicando os operadores genéticos. Em contra
partida, o tempo de execução do processo completo foi quase três vezes maior ao processo com
Simulated Annealing. O processo com Simulated Annealing é bem aleatório e enquanto a
temperatura está elevada, a possibilidade de aceitação de soluções piores é maior, visto que a
função de probabilidade de aceitação varia conforme a temperatura do momento. Quando a
temperatura está chegando a níveis baixos, somente novas boas soluções começam a serem aceitas,
fazendo que o resultado seja uma boa solução e o processo possa convergir.
61
5 TRABALHOS FUTUROS
A pesquisa realizada neste trabalho mostrou que o problema de encaixe da indústria têxtil é
uma área muito interessante de ser estudada e carente de materiais com propostas de solução. É um
problema que possui diversas restrições que dificultam seu tratamento, mas podem trazer bons
resultados quando aplicadas. É um bom problema a ser pesquisado e junto à uma pesquisa de
melhoria no processo de encaixe, seja ela com a separação das figuras em grupos de tamanhos ou
mesmo com procedimentos mais eficientes para a definição da posição das figuras durante o
encaixe, dariam boas linhas de estudo. Envolvendo uma complexidade tanto na área de corte e
empacotamento como na área da geometria analítica.
Outra linha de melhoria que pode ser seguida é a aplicação de diferentes operadores
genéticos para o encaixe que utilizou Algoritmo Genético. A pesquisa considerou apenas um tipo de
tratamento de inconsistência nos cruzamentos e um tipo de mutação. Assim a aplicação de outras
técnicas pode resultar em resultados melhores no encaixe das figuras.
Este trabalho não é uma solução para um problema em específico, assim a aplicação de
procedimentos de encaixe em problemas específicos pode trazer melhores resultados, visto que o
processo de encaixe poderá se especificar para o problema a ser tratado. A separação das figuras em
grupos de tamanhos que possuirão prioridades no momento de encaixe, novos tratamentos
geométricos para a definição da posição da peça e de verificação de sobreposição são sugestões de
melhorias para o processo de encaixe.
62
REFERÊNCIAS BIBLIOGRÁFICAS
ARAUJO, R. S. Uma Abordagem para o problema de corte guilhotinado bi-dimensional para
peças regulares com a utilização de p-medianas e pesquisa tabu. 2004. 72f. (Monografia) –
Universidade do Vale do Rio do Sinos, São Leopoldo, 2004.
BEZ, E. T. Procedimento de representação de soluções em otimização global: Aplicação em
modelos de interação espacial. 2005. 224f. Tese (Doutorado em Engenharia de Produção) –
Universidade Federal de Santa Catarina, Florianópolis, 2005.
BOECHEL, T. Algoritmo de otimização: uma abordagem híbrida utilizando o algoritmo das
formigas e genético. 2005. 70 f. Dissertação (Mestrado em Ciência da Computação) – PósGraduação em Ciência da Computação. Universidade Federal de Santa Catarina. Florianópolis,
2005
BURKE, E. K.; HELLIER, R. S. R.; KENDALL, G.; WHITWELL, G. A new bottom-left fill
heuristic algorithm for the two-dimensional irregular packing problem. Operations Research. v.
54, 2006. P. 587-601.
CONSTANTINO, A. A.; GOMES JUNIOR, A. M.. Um algoritmo genético aplicados ao problema
de corte bidimensional. Acta Scientiarum, Maringá-PR, v. 24, n. 6, p. 1727-1731, 2002.
CORRÊA, E. S. Algoritmos genéticos e busca tabu aplicados ao problema das p-medianas.
2000. 102 f. Dissertação (Mestrado em Métodos Numéricos) – Universidade Federal do Paraná,
Curitiba, 2000.
CUNHA, R. R. M. Um Algoritmo de minimização de Sobras em Corte Unidimensional. 1998.
91 f. Dissertação (Mestrado em Engenharia Mecânica) – Pós-Graduação em Engenharia Mecânica,
Universidade Federal de Santa Catarina, Florianópolis, 1998.
DIAS, A. Encaixe geral de figuras planas. 1991. 127 f. Tese (Doutorado em Engenharia
Mecânica) – Universidade Católica do Rio de Janeiro, Rio de Janeiro, 1991.
DIAS, A. General nesting of non-convex 2-D parts. In: Flexible Automation and Intelligent
Manufacturing 2000, 2000, College Park, MD - USA. Proceedings of the Tenth International
FAIM Conference. Wheaton, MD - USA: Econo Printing Graphics, Inc, 2000. v. 1. p. 382-391.
DYCKHOFF, H. A typology of cutting and packing problems. European Journal of Operational
Research. N. 44, 1990. P. 145-159.
FRITSCH, A.; VORNBERGER, O. Cutting stock by iterated matching. Operations Research
Proceedings. 1995. P. 92-97.
GOLDBERG, D. E. Genetic algorithms in search, optimization, and machine learning.
Reading, Mass: Addison-Wesley, c1989. 412 p.
HAINES, E. Point in Polygon Strategies. In: HERCKBERT, P. S. Graphics Gems IV. San Diego,
1994. cap 1. p 24 – 46.
63
HIFI, M.; PASCHOS V. T.; ZISSIMOPOULOS V. A simulated annealing approach for the circular
cutting problem. European Journal of Operational Research. N. 159, 2004. P. 430-448.
HOBSBAWM, E.J. A Era das revoluções: Europa: 1789-1848. Trad. Port. Rio de Janeiro: Paz e
Terra, 1982.
LIANG, Ko-Hsin; YAO, Xin; NEWTOWN, C.; HOFFMAN D. A new evolutionary approach to
cutting stock problems with and without contiguity. Computers & Operations Research, 2001.
LIU, H. Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and
lowest-gravity-center principle. Shanghai, 2005.
MENDES, A. S. Algoritmos meméticos aplicados aos problemas de seqüenciamento de
máquinas. 1999. 91 f. Tese (Mestrado em Engenharia Elétrica) – Universidade Estadual de
Campinas, Campinas, 1999.
MONTEIRO, M. A. Introdução a organização de computadores. 3. ed. Rio de Janeiro: São
Paulo: Livros Técnicos e Científicos, 1996. 397p.
NASCIMENTO, D. B. Otimização da programação de ordens de corte em indústrias têxteis.
2006. 215 f. Tese (Doutorado em Engenharia de Produção) – Universidade Federal de Santa
Catarina, Florianópolis, 2006.
NORONHA, T. F.; ALOISE, D. J.; SILVA, M. M. Uma Abordagem sobre estratégias
metaheurísticas. REIC. Revista eletrônica de iniciação científica. v. 1, 2000. Disponível em
<http://www.sbc.org.br/index.php?language=1&subject=101&content=article&option=pdf&aid=97
>. Acesso em: 13 maio 2007.
OLIVEIRA, M. H.; STEFFEN, V. Jr. Estudo de otimização e casos utilizando algoritmos genéticos
e recozimento simulado. FAMAT em Revista. N 03, 2004. P. 101-108.
PARADA, V.; SEPULVEDA, M.; ALVARENGA, A. G. Solución al problema de corte de piezas
mediante el algoritmo simulated annealing. Computers & Operations Research. v. 25, n. 01,
1998.
PISINGER, D. Algoritms for knapsack problems.1995.200f. Ph.D. prize of the Danish Academy
of Natural Sciences – University of Copenhagen, Copenhagen 1995.
ROSÁRIO, R. R. L. Proposta de solução para o problema das p-medianas na localização de
unidades de Saúde 24 horas. 2002. Dissertação (Mestrado em Métodos Numéricos em
Engenharia) – Universidade Federal do Paraná, 2002.
VINADÉ, C. A. C. Problema de encaixe de figuras não convexas em contorno não convexo.
1997. 107 f. Dissertação (Mestrado em Engenharia Mecânica) – Pós-Graduação em Engenharia
Mecânica, Universidade Federal de Santa Catarina, Florianópolis, 1997.
64
APÊNDICES
65
TIPOS DE FIGURAS UTILIZADAS NOS TESTES
As figuras utilizadas nos testes variaram entre figuras convexas e não convexas. Apesar
destas figuras terem um resultado visual que aparenta uma figura com curvas e retas, suas curvas
foram discretizadas em segmentos de retas, estas figuras são todas formadas por segmentos de retas.
A Figura 37 mostra o desenho sem repetição das figuras utilizadas nos ensaios numéricos.
Figura 37. Figuras utilizadas no encaixe
66
EXEMPLOS DE ENCAIXES DE FIGURAS
Exemplo 1 de encaixe de figuras
A Figura 38 mostra um exemplo de encaixe para figuras pequenas e de tamanhos próximos.
Figura 38. Exemplo 1 de encaixe de figuras
67
Exemplo 2 de encaixe de figuras
A Figura 39 mostra um exemplo de encaixe para figuras com variação de peças grandes e
pequenas.
Figura 39. Exemplo 2 de encaixe de figuras
68