Identificação do Operador de Seleção do Algoritmo Genético Paralelo para o Problema de Corte Bidimensional

• Mayrton de Queiroz UFPB
• Elaine Marques UFRPE

Abstract

When constructing a product, we must take into account, among other factors, the best use of the raw material. With the gradual increase of the population, it becomes increasingly necessary to optimize the use of natural resources. The cutting problem is well known in the literature and can be applied in various materials such as glass, iron, wood, among others. However, in this work, we will emphasize the cut of a piece of wood, specifically. Before the This article aims to identify the best type of roulette selection operator to be integrated to the Parallel Genetic Algorithm, seeking to find the best way to cut pieces of wood. To reduce processing speed, the Genetic Algorithm was developed in a distributed way with the aid of the API Message Passing Interface (MPI), and the selection operators adopted were sequential addict roulette and addicted roulette with and without migration, in order to to verify which selection operator best meets the solution to the problem of cuts. With the experiments, it was possible to identify that the method of selection of the roulette with migration stood out when compared to the others.

Keywords: Algoritmos e Complexidade, Inteligência Artificial, Otimização Combinatória

References

Jorge, A. R., Mundim, L. R., Cherri, L. H., and Andretta, M. (2015). O problema de corte de itens irregulares: aplicaçao na industria de aventais e forros de luva. Simpósio Brasileiro de Pesquisa Operacional, Porto de Galinhas, Pernambuco-PE.

Linden, R. (2012). Algoritmos genéticos (3a ediçao). Brasport.

Parmar, K. B., Prajapati, H. B., and Dabhi, V. K. (2014). Cutting stock problem: A survey of evolutionary computing based solution. In International Conference on Green Computing Communication and Electrical Engineering (ICGCCEE), pages 1–6. IEEE.

Rangel, S. and Figueiredo, A. G. d. (2008). O problema de corte de estoque em indústrias de móveis de pequeno e médio portes. Pesquisa Operacional, 28(3):451–472.

Simon, D. (2013). Evolutionary optimization algorithms. John Wiley & Sons.

Souza, G. P. K. d. (2014). Otimização de funções reais multidimensionais utilizando algoritmo genético contínuo.

Wäscher, G., Haußner, H., and Schumann, H. (2007). An improved typology of cutting and packing problems. European journal of operational research, 183(3):1109–1130.