Un algoritmo genético de genotipo-fenotipo nuevo 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 placing orthogonally all the pieces on the strip, without overlapping them, minimizing the height of the used strip. 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.

Idioma originalSpanish
PublicaciónIngenieria y Universidad
Volumen20
N.º1
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 algoritmo genético de genotipo-fenotipo nuevo para el problema de strip packing de dos dimensiones con rotación de 90°. En: Ingenieria y Universidad. 2016 ; Vol. 20, N.º 1.
@article{cda128c280b441b69a77ed12a72cd970,
title = "Un algoritmo gen{\'e}tico de genotipo-fenotipo nuevo 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 placing orthogonally all the pieces on the strip, without overlapping them, minimizing the height of the used strip. 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.",
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",
language = "Spanish",
volume = "20",
journal = "Ingenieria y Universidad",
issn = "0123-2126",
publisher = "Pontificia Univ Javariana",
number = "1",

}

Un algoritmo genético de genotipo-fenotipo nuevo 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.

Resultado de la investigación: Article

TY - JOUR

T1 - Un algoritmo genético de genotipo-fenotipo nuevo 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 placing orthogonally all the pieces on the strip, without overlapping them, minimizing the height of the used strip. 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.

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 placing orthogonally all the pieces on the strip, without overlapping them, minimizing the height of the used strip. 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.

KW - Genetic algorithm

KW - Genotype-phenotype

KW - Phenotype generation

KW - Strip packing problem

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

M3 - Article

VL - 20

JO - Ingenieria y Universidad

JF - Ingenieria y Universidad

SN - 0123-2126

IS - 1

ER -