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

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...

Full description

Autores:
Tipo de recurso:
article
Fecha de publicación:
2015
Institución:
Pontificia Universidad Javeriana
Repositorio:
Repositorio Universidad Javeriana
Idioma:
eng
OAI Identifier:
oai:repository.javeriana.edu.co:10554/25636
Acceso en línea:
http://revistas.javeriana.edu.co/index.php/iyu/article/view/10853
http://hdl.handle.net/10554/25636
Palabra clave:
Rights
openAccess
License
Atribución-NoComercial-SinDerivadas 4.0 Internacional
id JAVERIANA_3df57db0a323abf7af95a0a3a241cf4d
oai_identifier_str oai:repository.javeriana.edu.co:10554/25636
network_acronym_str JAVERIANA
network_name_str Repositorio Universidad Javeriana
repository_id_str
spelling Un algoritmo genético eficiente para el strip-packing problemA New Genotype-Phenotype Genetic Algorithm for the Two-Dimensional Strip Packing Problem with Rotation of 90°Gatica, GustavoVillagrán, GonzaloContreras-Bolton, CarlosLinfati, RodrigoEscobar, John WillmerDado 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.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. Pontificia Universidad Javeriana2020-04-16T17:28:18Z2020-04-16T17:28:18Z2015-12-07http://purl.org/coar/version/c_970fb48d4fbd8a85Artículo de revistahttp://purl.org/coar/resource_type/c_6501info:eu-repo/semantics/articlePeer-reviewed Articleinfo:eu-repo/semantics/publishedVersionPDFapplication/pdfhttp://revistas.javeriana.edu.co/index.php/iyu/article/view/1085310.11144/Javeriana.iyu20-1.ngpg2011-27690123-2126http://hdl.handle.net/10554/25636enghttp://revistas.javeriana.edu.co/index.php/iyu/article/view/10853/12530Ingenieria y Universidad; Vol 20 No 1 (2016): January-June; 119-138Ingenieria y Universidad; Vol. 20 Núm. 1 (2016): Enero-Julilo; 119-138Atribución-NoComercial-SinDerivadas 4.0 Internacionalinfo:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2reponame:Repositorio Universidad Javerianainstname:Pontificia Universidad Javerianainstacron:Pontificia Universidad Javeriana2023-03-29T17:44:12Z
dc.title.none.fl_str_mv Un algoritmo genético eficiente para el strip-packing problem
A New Genotype-Phenotype Genetic Algorithm for the Two-Dimensional Strip Packing Problem with Rotation of 90°
title Un algoritmo genético eficiente para el strip-packing problem
spellingShingle Un algoritmo genético eficiente para el strip-packing problem
Gatica, Gustavo
title_short Un algoritmo genético eficiente para el strip-packing problem
title_full Un algoritmo genético eficiente para el strip-packing problem
title_fullStr Un algoritmo genético eficiente para el strip-packing problem
title_full_unstemmed Un algoritmo genético eficiente para el strip-packing problem
title_sort Un algoritmo genético eficiente para el strip-packing problem
dc.creator.none.fl_str_mv Gatica, Gustavo
Villagrán, Gonzalo
Contreras-Bolton, Carlos
Linfati, Rodrigo
Escobar, John Willmer
author Gatica, Gustavo
author_facet Gatica, Gustavo
Villagrán, Gonzalo
Contreras-Bolton, Carlos
Linfati, Rodrigo
Escobar, John Willmer
author_role author
author2 Villagrán, Gonzalo
Contreras-Bolton, Carlos
Linfati, Rodrigo
Escobar, John Willmer
author2_role author
author
author
author
description 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.
publishDate 2015
dc.date.none.fl_str_mv 2015-12-07
2020-04-16T17:28:18Z
2020-04-16T17:28:18Z
dc.type.none.fl_str_mv http://purl.org/coar/version/c_970fb48d4fbd8a85
Artículo de revista
http://purl.org/coar/resource_type/c_6501
info:eu-repo/semantics/article
Peer-reviewed Article
info:eu-repo/semantics/publishedVersion
format article
status_str publishedVersion
dc.identifier.none.fl_str_mv http://revistas.javeriana.edu.co/index.php/iyu/article/view/10853
10.11144/Javeriana.iyu20-1.ngpg
2011-2769
0123-2126
http://hdl.handle.net/10554/25636
url http://revistas.javeriana.edu.co/index.php/iyu/article/view/10853
http://hdl.handle.net/10554/25636
identifier_str_mv 10.11144/Javeriana.iyu20-1.ngpg
2011-2769
0123-2126
dc.language.none.fl_str_mv eng
language eng
dc.relation.none.fl_str_mv http://revistas.javeriana.edu.co/index.php/iyu/article/view/10853/12530
Ingenieria y Universidad; Vol 20 No 1 (2016): January-June; 119-138
Ingenieria y Universidad; Vol. 20 Núm. 1 (2016): Enero-Julilo; 119-138
dc.rights.none.fl_str_mv Atribución-NoComercial-SinDerivadas 4.0 Internacional
info:eu-repo/semantics/openAccess
http://purl.org/coar/access_right/c_abf2
rights_invalid_str_mv Atribución-NoComercial-SinDerivadas 4.0 Internacional
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
dc.format.none.fl_str_mv PDF
application/pdf
dc.publisher.none.fl_str_mv Pontificia Universidad Javeriana
publisher.none.fl_str_mv Pontificia Universidad Javeriana
dc.source.none.fl_str_mv reponame:Repositorio Universidad Javeriana
instname:Pontificia Universidad Javeriana
instacron:Pontificia Universidad Javeriana
instname_str Pontificia Universidad Javeriana
instacron_str Pontificia Universidad Javeriana
institution Pontificia Universidad Javeriana
reponame_str Repositorio Universidad Javeriana
collection Repositorio Universidad Javeriana
_version_ 1803712847017934848

Publicaciones similares