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

Abstract

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.