Un nuevo algoritmo genético de genotipo-fenotipo para el problema de Strip Packing de dos dimensiones con rotación de 90°

Gustavo Gatica, Gonzalo Villagrán, Carlos Contreras-Bolton, Rodrigo Linfati, John Willmer Escobar

Resultado de la investigación: Article

Resumen

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 bestknown results found by previous published approaches are improved.

Idioma originalSpanish
Páginas (desde-hasta)119-138
Número de páginas20
PublicaciónIngenieria y Universidad
Volumen20
N.º1
DOI
EstadoPublished - 1 ene 2016

Huella dactilar

Benchmarking
Computational complexity
Genetic algorithms

ASJC Scopus subject areas

  • Engineering(all)

Citar esto

Gatica, Gustavo ; Villagrán, Gonzalo ; Contreras-Bolton, Carlos ; Linfati, Rodrigo ; Escobar, John Willmer. / Un nuevo algoritmo genético de genotipo-fenotipo para el problema de Strip Packing de dos dimensiones con rotación de 90°. En: Ingenieria y Universidad. 2016 ; Vol. 20, N.º 1. pp. 119-138.
@article{412763371f26485282aab1636696e331,
title = "Un nuevo algoritmo gen{\'e}tico de genotipo-fenotipo para el problema de Strip Packing de dos dimensiones con rotaci{\'o}n de 90°",
abstract = "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 bestknown results found by previous published approaches are improved.",
keywords = "Genetic algorithm, Genotype-phenotype, Phenotype generation, Strip packing problem",
author = "Gustavo Gatica and Gonzalo Villagr{\'a}n and Carlos Contreras-Bolton and Rodrigo Linfati and Escobar, {John Willmer}",
year = "2016",
month = "1",
day = "1",
doi = "10.11144/Javeriana.iyu20-1.ngpg",
language = "Spanish",
volume = "20",
pages = "119--138",
journal = "Ingenieria y Universidad",
issn = "0123-2126",
publisher = "Pontificia Univ Javariana",
number = "1",

}

Un nuevo algoritmo genético de genotipo-fenotipo para el problema de Strip Packing de dos dimensiones con rotación de 90°. / Gatica, Gustavo; Villagrán, Gonzalo; Contreras-Bolton, Carlos; Linfati, Rodrigo; Escobar, John Willmer.

En: Ingenieria y Universidad, Vol. 20, N.º 1, 01.01.2016, p. 119-138.

Resultado de la investigación: Article

TY - JOUR

T1 - Un nuevo algoritmo genético de genotipo-fenotipo para el problema de Strip Packing de dos dimensiones con rotación de 90°

AU - Gatica, Gustavo

AU - Villagrán, Gonzalo

AU - Contreras-Bolton, Carlos

AU - Linfati, Rodrigo

AU - Escobar, John Willmer

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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 bestknown results found by previous published approaches are improved.

AB - 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 bestknown results found by previous published approaches are improved.

KW - Genetic algorithm

KW - Genotype-phenotype

KW - Phenotype generation

KW - Strip packing problem

UR - http://www.scopus.com/inward/record.url?scp=84981717748&partnerID=8YFLogxK

U2 - 10.11144/Javeriana.iyu20-1.ngpg

DO - 10.11144/Javeriana.iyu20-1.ngpg

M3 - Article

AN - SCOPUS:84981717748

VL - 20

SP - 119

EP - 138

JO - Ingenieria y Universidad

JF - Ingenieria y Universidad

SN - 0123-2126

IS - 1

ER -