1 A genotype/phenotype binary representation for the strip packing problem with genetic algorithms Gonzalo Villagrán 1, Gustavo Gatica 1, Carlos Contreras Bolton 2 y Víctor Parada 2 1 Universidad Andrés Bello 2 Universidad de Santiago de Chile 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 1

2 Contenido 1.Motivación. 2.Materiales y métodos. 3.Resultados y discusión. 4.Conclusión. 5.Bibliografía. 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 2

3 Motivación El problema de Strip Packing (SPP) se define a partir de una región rectangular de ancho W definido y largo infinito, en el cual se deben ubicar todas las piezas de un conjunto predefinido R={r 1, r 2,…, r n }, que tienen dimensiones de ancho w i y largo h i, sin sobreponerlas, con el fin de minimizar la altura H obtenida en el contenedor. Motivación 3 XXIV Encuentro Chileno de Computación - ECC'2012 12/11/2012

4 Motivación Optimización del uso de materias primas, lo que involucra una reducción significativa de los costos de producción. Vidrios. Papeleras. Maderas. 4 XXIV Encuentro Chileno de Computación - ECC'2012 Fuente: Sitio web de Tesafilm® http://www.tesatape.es/industry/paper/paper/reducir-costes- aumentar-la-seguridad,75504,2,Gallery.html [visitado el 29 de Junio de 2012] http://www.tesatape.es/industry/paper/paper/reducir-costes- aumentar-la-seguridad,75504,2,Gallery.html 12/11/2012

5 Motivación Strip Packing Problem – Problema de optimización combinatoria. – Es NP-Hard (Garey & Johnson, 1979). Enfoques de resolución – Exactos (Alvarez-Valdés et al., 2008). – Heurísticas (Burke, Hyde, & Kendall, 2011; Chen, Fu, Shang, & Huang, 2008; Kotov & Cao, 2011, Leung et al, 2011). – Metaheurísticas (Alvarez-Valdés et al., 2007, 2008; ADereli & Sena Daş, 2007; Gómez-Villouta et al., 2010, Yang et al, 2012; Leung et al, 2011). 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 5

6 Motivación Representaciones en la literatura de AG enteras con operadores especiales. Utilización de Algoritmos Genéticos – Representación binaria de las soluciones. – Operadores genéticos clásicos. 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 6

7 Motivación 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 7

8 Materiales y métodos Proceso evolutivo 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 8

9 Materiales y métodos Representación 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 9

10 Materiales y métodos Decodificación 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 10

11 Materiales y métodos Algoritmo de colocación – Fast Heuristic (Leung et al., 2011): es una estrategia inspirada en la construcción de muros basada en capas (Zhang et al., 2008). – La idea de ésta estrategia es colocar rectángulos por capa. Una nueva capa esta determinada por un rectángulo de referencia, se inicia cuando la capa actual no se puede poner más rectángulos. 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 11

12 Materiales y métodos Parámetros genéticos – Cruzamiento : 85%. – Mutación: 5%. – Individuos: 250 – Generaciones: 50 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 12

13 Materiales y métodos Ejecución del AG: 10 veces por instancia. Instancias utilizadas: – Hopper & Turton (2001). C1 – C7 (16 a 197 piezas). 3 Problemas por clase. – Burke, Kendall & Whitwell (2004). N1-N12 (10 a 500 piezas). 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 13

14 Resultados y discusión Proceso evolutivo 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 14

15 Resultados y discusión Comparación de resultados SPGAL (Bortfeldt, 2006) GRASP (Alvarez-Valdés et al., 2008) MGA (Mancapa et al., 2009) CTS (Gómez-Villouta et al., 2010) CJ+EA (Matayoshi, 2010) FH (Leung & Zhang, 2011) SW (Burke et al., 2011) ISA (Leung et al., 2012) SRA (Yang et al., 2012) 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 15

16 Resultados y discusión 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 16 Instancia H*HAQHHGRASPFHSWBFbccISASRAAG+FH N1 40 4440 N2 50 525054 40 50 N3 50 51 505450 N4 8081 838183 80 N5 100102101102 101106 101100101 N6 100101 102 100 N7 100101 102101103 100 N8 8081 82 81 80 N9 150151 155 150 N10 150151 152 150 N11 150151 154 150 151 N12 300303 301304306 301

17 Resultados y discusión 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 17 InstanciaH* SPGALGRASPMGACTSCJ+EAFHSWBFbccISA SRAAG+FH C1P120 - 22-2120-21 20 P220 - 23-2120-21 20 P320 - 23-2021-22 20 average gap C1 1,700,0013,330,003,331,671,506,670,00 C2P115 - 19-16 - 15 P215 - 19-1615-16 15 P315 - 19-1615-16 15 average gap C2 0,00 26,670,006,672,222,006,670,00 C3P130 - 36-3231-32 30 P230 -3134-3231-3231 P330 - 36-32 - 30 average gap C3 2,201,0817,780,006,674,441,006,671,11 C4P160 -6170-6561-6361 60 P260 -6172-6561-6261 60 P360 -6175-6461-626061 60 average gap C4 0,001,6420,561,647,781,67 3,891,111,670,00 C5P190 -91117-9891-9291 90 P290 -91124-9990-9390 P390 -91109-9891- 90 average gap C5 0,001,129,631,469,260,741,112,220,740,370,00 C6P1120 -121159-134121-122121 120 P2120 -121160-133121-122121 120 P3120 -121160-133121-122121 120 average gap C6 0,30,8333,061,9111,110,83 1,670,83 0,00 C7P1240 -244330--241-244242241 P2240 -242346--241-243241 242 P3240 -243352--241-244242241 average gap C7 0,31,2342,782,04-0,421,251,530,690,420,56 Average 0,640,8426,261,017,471,711,344,190,640,630,24

18 Conclusión AG propuesto obtiene mejores resultados – AG dependientes de la representación. – A los otros métodos también. Trabajos futuros – Mejorar los tiempos computacionales. 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 18

19 Bibliografía [1] M. R. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of NP- completeness. New York: W. H. Freeman & Co., 1979. [2] R. Alvarez-Valdés, F. Parreño, and J. M. Tamarit, “Reactive GRASP for the strip-packing problem,” Computer Operation Research, vol. 35, no. 4, pp. 1065–1083, 2008. [3] R. Alvarez-Valdés, F. Parreño, and J. Tamarit, “A branch and bound algorithm for the strip packing problem,” OR Spectrum, vol. 31, no. 2, pp. 431–459, 2009. [4] E. K. Burke, M. R. Hyde, and G. Kendall, “A squeaky wheel optimisation methodology for two- dimensional strip packing,” Computers & Operations Research, vol. 38, no. 7, pp. 1035–1044, 2011. [5] D. Chen, Y. Fu, M. Shang, and W. Huang, “A Quasi-Human Heuristic Algorithm for the 2D Rectangular Strip Packing Problem,” in Information Science and Engineering, 2008. ISISE ’08. International Symposium on, 2008, vol. 2, pp. 392 –396. [6] V. M. Kotov and D. Cao, “A heuristic algorithm for the non-oriented 2D rectangular strip packing problem,” Buletinul Academiei de Stiinte a republicii moldova. matemátia, vol. 2, pp. 81–88, 2011. [7] R. Alvarez-Valdés, F. Parreño, and J. M. Tamarit, “A tabu search algorithm for a two-dimensional non-guillotine cutting problem,” European Journal of Operational Research, vol. 183, no. 3, pp. 1167– 1182, 2007. [8] G. Gómez-Villouta, J.-P. Hamiez, and J.-K. Hao, “Tabu search with consistent neighbourhood for strip packing,” in Proceedings of the 23rd international conference on Industrial engineering and other applications of applied intelligent systems - Volume Part I, Berlin, Heidelberg, 2010, pp. 1–10. [9] T. Dereli and G. Sena Daş, “A Hybrid simulated-annealing algorithm for two-dimensional strip packing problem,” in Adaptive and Natural Computing Algorithms, vol. 4431, B. Beliczynski, A. Dzielinski, M. Iwanowski, and B. Ribeiro, Eds. Berlin: Springer Berlin Heidelberg, 2007, pp. 508–516. [10] E.-G. Talbi, Metaheuristics: from design to implementation, vol. 10. Hoboken: John Wiley & Sons Inc., 2009. 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 19

20 Bibliografía [11] E. Hopper and B. Turton, “A genetic algorithm for a 2D industrial packing problem,” Computers and Industrial Engineering, vol. 37, no. 1–2, pp. 375–378, 1999. [12] S. Jakobs, “On genetic algorithms for the packing of polygons,” European Journal of Operational Research, vol. 88, no. 1, pp. 165–181, 1996. [13] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, 1st ed. Boston: Addison- Wesley Longman Publishing, 1989. [14] G. Syswerda, “Schedule optimisation using genetic algorithms,” in Handbook of Genetic Algorithms, New York: Van Nostrand Reinhold, 1991, pp. 332–349. [15] A. Bortfeldt, “A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces,” European Journal of Operational Research, vol. 172, no. 3, pp. 814–837, 2006. [16] E. Hopper and B. Turton, “An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem,” European Journal of Operational Research, vol. 128, no. 1, pp. 34–57, 2001. [17] V. Mancapa, T. I. Van Niekerk, and T. Hua, “A genetic algorithm for two dimensional strip packing problems,” South African Journal of Industrial Engineering, vol. 20, no. 2, pp. 145 – 162, 2009. [18] M. Matayoshi, “The 2D strip packing problem: A new approach with verification by EA,” in Systems Man and Cybernetics (SMC), 2010 IEEE International Conference on, Istanbul, 10-13 Octubre 2010, Istanbul, 2010, pp. 2492 –2499. [19] E. Falkenauer, Genetic Algorithms and Grouping Problems. New York, NY, USA: John Wiley & Sons, Inc., 1998. [20] F. Rothlauf, Representations for Genetic And Evolutionary Algorithms. Netherlands: Springer, 2006. [21] M. Affenzeller, S. Winkler, S. Wagner, and A. Beham, Genetic Algorithms and Genetic Programming: Modern Concepts and Practical Applications. New York: Chapman & Hall/CRC, 2009. [22] E. K. Burke, G. Kendall, and G. Whitwell, “A new placement heuristic for the orthogonal stock-cutting problem,” Operations Research, vol. 52, no. 4, pp. 655–671, Jul. 2004. 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 20

21 Gracias por su atención. 12 Noviembre 2012 CYTED-HAROSA Workshop, Valparaiso, Chile 21