Solving the two dimensional cutting problem using evolutionary algorithms with penalty functions

In this work a solution using evolutionary algorithms with penalty function for the non-guillotine cutting problem is presented. In this particular problem, the rectangular pieces have to be cut from an unique large object, being the goal to maximize the total value of cut pieces. Some chromosomes c...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Beraudo, Vanina, Orellana, Alina, Alfonso, Hugo, Minetti, Gabriela F., Salto, Carolina
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2005
Materias:
Ciencias Informáticas
Algorithms
non-guillotine cutting problem
evolutionary algorithm
penalty function
selection methods
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/22952
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-22952
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Algorithms
non-guillotine cutting problem
evolutionary algorithm
penalty function
selection methods
spellingShingle Ciencias Informáticas
Algorithms
non-guillotine cutting problem
evolutionary algorithm
penalty function
selection methods
Beraudo, Vanina
Orellana, Alina
Alfonso, Hugo
Minetti, Gabriela F.
Salto, Carolina
Solving the two dimensional cutting problem using evolutionary algorithms with penalty functions
topic_facet Ciencias Informáticas
Algorithms
non-guillotine cutting problem
evolutionary algorithm
penalty function
selection methods
description In this work a solution using evolutionary algorithms with penalty function for the non-guillotine cutting problem is presented. In this particular problem, the rectangular pieces have to be cut from an unique large object, being the goal to maximize the total value of cut pieces. Some chromosomes can hold pieces to be cut, but some pieces cannot be arranged into the object, generating infeasible solutions. A way to deal with this kind of solutions is to use a penalizing strategy. The used penalty functions have been originally developed for the knapsack problem and they are adapted for the cutting problem in this paper. Moreover, the effect on the algorithm performance to combine penalty functions with two different selection methods (binary tournament and roulette wheel) is studied. The algorithm uses a binary representation, one-point crossover, big-creep mutation and in order to evaluated the quality of solutions a placement routine is considered (Heuristic with Efficient Management of Holes). Experimental comparisons of the performance of the resulting algorithms are carried out using publicly available benchmarks to the non-guillotine cutting problem. We report on the high performance of the proposed models at similar (or better) accuracy with respect to existing algorithms.
format Objeto de conferencia
Objeto de conferencia
author Beraudo, Vanina
Orellana, Alina
Alfonso, Hugo
Minetti, Gabriela F.
Salto, Carolina
author_facet Beraudo, Vanina
Orellana, Alina
Alfonso, Hugo
Minetti, Gabriela F.
Salto, Carolina
author_sort Beraudo, Vanina
title Solving the two dimensional cutting problem using evolutionary algorithms with penalty functions
title_short Solving the two dimensional cutting problem using evolutionary algorithms with penalty functions
title_full Solving the two dimensional cutting problem using evolutionary algorithms with penalty functions
title_fullStr Solving the two dimensional cutting problem using evolutionary algorithms with penalty functions
title_full_unstemmed Solving the two dimensional cutting problem using evolutionary algorithms with penalty functions
title_sort solving the two dimensional cutting problem using evolutionary algorithms with penalty functions
publishDate 2005
url http://sedici.unlp.edu.ar/handle/10915/22952
work_keys_str_mv AT beraudovanina solvingthetwodimensionalcuttingproblemusingevolutionaryalgorithmswithpenaltyfunctions
AT orellanaalina solvingthetwodimensionalcuttingproblemusingevolutionaryalgorithmswithpenaltyfunctions
AT alfonsohugo solvingthetwodimensionalcuttingproblemusingevolutionaryalgorithmswithpenaltyfunctions
AT minettigabrielaf solvingthetwodimensionalcuttingproblemusingevolutionaryalgorithmswithpenaltyfunctions
AT saltocarolina solvingthetwodimensionalcuttingproblemusingevolutionaryalgorithmswithpenaltyfunctions
bdutipo_str Repositorios
_version_ 1764820467934298115

Ejemplares similares