Un algoritmo genético eficiente para el strip-packing problem

Given a set of rectangular pieces and a fixed width with infinite length, the strip-packing problem (SPP) of two dimensions (2D), with a rotation of pieces in 90° consists of orthogonally placing all the pieces on the strip, without overlapping them, minimizing the height of the strip used. Several algorithms have been proposed to solve this problem, being Genetic Algorithms one of the most popular approach due to it effectiveness solving NP-Hard problems. In this paper, three binary representations, and classic crossover and mutation operators are introduced. A comparison of the three binary representations on a subset of benchmarking instances is performed. The representation R2 outperforms the results obtained by representation R1 and R3. Indeed, some of the best-known results found by previous published approaches are improved. Dado un conjunto de piezas rectangulares y un contenedor de ancho fijo y largo variable, el problema del Strip Packing (SP) consiste en posicionar ortogonalmente todas las piezas dentro del contenedor, sin solaparlas, para así minimizar la altura alcanzada dentro del contenedor. Diversos métodos se han utilizado para su resolución, siendo algunos de los más populares los Algoritmos Genéticos, debido a su efectividad en otros problemas combinatoriales. Se han utilizado representaciones numéricas que obligan a la utilización de operadores genéticos que alteran la representación para preservar la factibilidad de las soluciones, coartando la naturaleza de la evolución. Nosotros proponemos un enfoque del tipo genotipo-fenotipo que no altera la evolución darwiniana, permitiendo el uso de operadores genéticos tradicionales. Los resultados computacionales se ejecutaron con dos grupos de problemas que corresponden a los benchmarking propuestos en la literatura. Los resultados obtenidos mostraron que el algoritmo supera el 100% de los casos resueltos por algoritmos genéticos clásicos con representación numérica