¿Qué tan malo es ser codicioso?

¿Ser codicioso es malo?

Explorando una solución ambiciosa para el problema de corte de existencias

Contenido

  1. Motivación del problema de corte de existencias
  2. Visión general rápida de los problemas NP-Difícil
  3. Codificación del problema de corte de existencias en Python
  4. El algoritmo ambicioso
  5. Comparación con la búsqueda exhaustiva en un espacio n bajo
  6. Comparación con la búsqueda aleatoria en un espacio n más alto
  7. Conclusión

Motivación del problema de corte de existencias

Soy científico de datos de profesión. Si bien mis habilidades en ciencia de datos son muy importantes en el trabajo (por definición), ¡encuentro que los conceptos de ciencia de datos también ayudan a resolver muchos problemas fuera del trabajo!

Una de las formas en que mis habilidades de ciencia de datos son útiles es en mi pasatiempo como aficionado/creador. Un desafío común es saber cómo planificar el corte de material. Tengo una lista de cortes que necesito hacer en múltiples piezas de material del mismo tamaño de la tienda. ¿Cómo se planifican los cortes de manera que se desperdicie lo menos posible? ¡Este desafío se conoce como el ‘Problema de Corte de Existencias’! Como resulta, ¡este puede ser un problema realmente difícil de resolver, de hecho, NP-Difícil!

En este artículo, exploraré un ‘atajo’ (con el juego de palabras correspondiente) para resolver este problema y analizaré cómo se compara este método con la forma larga.

Tablero de roble blanco, mesa de base de acero que hice el año pasado - imagen del autor

Visión general rápida de los problemas NP-Difícil

No voy a entrar en mucha profundidad sobre los problemas NP-Difícil aquí, pero sí quiero dar alguna intuición al respecto. Lo que hace que un problema de optimización sea difícil es típicamente el tamaño de su espacio de soluciones. ¿Cuántas soluciones posibles debes explorar para encontrar la mejor? La dificultad de un problema generalmente se evalúa por la rapidez con la que crece el espacio de soluciones a medida que crece el tamaño del problema.

Para el ‘Problema de Corte de Existencias’, el problema se vuelve más grande, mucho más grande a medida que agregas más cortes. ¡Observa lo rápido que crece el espacio de soluciones a continuación!

Imagen del autor

El espacio de soluciones crece factorialmente, lo que significa que el número total de soluciones que se deben buscar para asegurarse de obtener la respuesta óptima es n!, lo cual, como puedes ver, aumenta muy, muy rápido.

NP significa ‘no determinista polinomial’, lo que significa que el problema crece más rápido que cualquier función polinomial. Hay toneladas de recursos que profundizan en los problemas NP/NP-difícil. Esto es todo lo que discutiré aquí.

Codificación del problema de corte de existencias en Python

El problema de corte de existencias se reduce fundamentalmente a un problema de ordenamiento. Realizas los cortes en un orden específico y, cuando te quedas sin longitud en una pieza de existencias, comienzas a cortar (aún en orden) en la siguiente pieza de existencias.

Una visualización explica esto mejor. Digamos que tenemos este orden de cortes
[4′, 2′, 1′, 2′, 2′, 1′], y tenemos piezas de existencias de tamaño 5′. El cálculo de desperdicio se ve así:
Imagen del autor

Aquí tenemos un desperdicio total de 4′.

Pero, si cambiamos el orden (manteniendo todos los mismos cortes), podemos obtener diferentes niveles de desperdicio. Intentemos [4′, 1′, 2′, 2′, 1′, 2′]:

Imagen del autor

Aquí, solo obtenemos 3′ de desperdicio – ¡simplemente cambiando el orden redujimos nuestro desperdicio! Esta es toda la idea de este problema de optimización. Queremos encontrar cuál es el mejor orden de los cortes.

Ahora, para codificar esto en un script de Python, necesitamos (1) funciones para calcular el desperdicio de cada orden, y (2) un algoritmo para ordenar listas en órdenes óptimos.

La función para calcular el desperdicio simplemente replica la lógica descrita anteriormente. Aquí está el código en Python:

def total_waste(stock_size, solution):        '''        Calcula el desperdicio de corte dada una solución específica                parámetros        stock_size (float): la dimensión del stock disponible para comprar        solution (list): lista de números flotantes que representan el orden de los cortes                salida        cut_off_waste (float): el desperdicio total de corte de la solución dada        '''        # configurar variable para realizar un seguimiento de las longitudes totales de cortes en la pieza actual de stock    temp_cut_length = 0        # comenzar sin desperdicio    cut_off_waste = 0    for cut in solution:                # si el siguiente corte no cabe en el stock actual,        # calcular nuevo desperdicio y reiniciar para otra pieza de stock        if temp_cut_length + cut > stock_size:            # calcular el desperdicio de corte            cut_off_waste += stock_size - temp_cut_length            # reiniciar la longitud del corte            temp_cut_length = cut        else:            # agregar a la longitud acumulativa de cortes en el stock            temp_cut_length += cut    # agregar el desperdicio del último corte - no se captura en el bucle    cut_off_waste += stock_size - temp_cut_length        return cut_off_waste

Cubriremos el algoritmo que necesitamos en la siguiente sección.

El algoritmo voraz

El algoritmo voraz es extremadamente simple, solo encuentra la pieza más grande que cabe en lo que queda del stock actual en el que estás trabajando.

Usando el ejemplo anterior, diremos que queremos hacer estos cortes [4′, 2′, 1′, 2′, 2′, 1′] y necesitamos un algoritmo voraz para optimizar el orden.

Primero comenzamos con el corte más largo que cabe en nuestra pieza actual de stock. Como no hemos hecho ningún corte, nuestra pieza actual de stock es de 5′. 4′ es el corte más largo que tenemos y cabe en 5′ de stock restante. El siguiente corte más largo es de 2′, como solo nos queda 1′ de stock, es demasiado largo. Pasamos al siguiente corte más largo, que es de 1′. Esto cabe en el stock restante, por lo que nuestro próximo corte es de 1′. El algoritmo sigue este patrón hasta que no haya más cortes.

Esto es lo que ese algoritmo se ve en Python:

def greedy_search(cuts, stock_size):        '''        Calcula una solución óptima voraz                parámetros:        cuts (list)        : cortes que deben hacerse        stock_size (float) : tamaño del stock disponible para comprar                salidas:        cut_plan (list) : secuencia de cortes para obtener resultados óptimos voraces                           waste (float)   : cantidad de material desperdiciado por la solución            '''        # plan de cortes vacío, para ser llenado    cut_plan = []    # comenzar con el tamaño de corte igual al tamaño del stock    cut_off = stock_size    # copiar la lista de cortes para evitar modificar la lista original    cuts_copy = copy(cuts)        # ordenar los cortes en orden descendente    cuts = list(np.sort(cuts)[::-1])        # continuar ordenando los cortes hasta    # que todos los cortes hayan sido ordenados    while len(cuts_copy) > 0:        for cut_size in cuts_copy:                        # si el tamaño del corte es menor que el stock restante,            # asignar el corte ahora            if cut_size < cut_off:                # agregar el corte al plan                cut_plan.append(cut_size)                                # actualizar la cantidad restante                cut_off -= cut_size                                # eliminar el corte de la lista de cortes que aún deben                 # ser ordenados                cuts_copy.remove(cut_size)                # restablecer cut_off para que sea el tamaño completo del stock        cut_off = stock_size        # calcular el desperdicio utilizando la función total_waste    waste = total_waste(stock_size, cut_plan)    return cut_plan, waste

Comparación con la búsqueda exhaustiva en un espacio n bajo

Nos estamos ahorrando mucho tiempo al usar una aproximación de la solución óptima a través del algoritmo voraz, pero ¿qué tan buena es esa aproximación? Una búsqueda exhaustiva del espacio de soluciones da la solución óptima global, que es nuestro estándar de oro. Comparemos la solución del algoritmo voraz con las soluciones óptimas globales para escenarios con solo unos pocos cortes (recuerda que encontrar la solución óptima global con muchos cortes es realmente difícil).

He creado aleatoriamente 250 listas de cortes para tamaños de corte que van desde 2 hasta 10 cortes. Cada corte estaba entre 0 y 1 y el tamaño del material se estableció en 1.1. A continuación se muestra el rendimiento:

Imagen del autor

Como puedes ver, a medida que aumenta ‘n’, el rendimiento codicioso empeora en comparación con el óptimo global, pero se mantiene relativamente cerca y altamente correlacionado.

Comparación con la búsqueda aleatoria en un espacio n más alto

Desafortunadamente, tenemos un gran punto ciego… Es decir, no conocemos el óptimo global en un espacio n más alto. Ahora, nos adentramos en el negocio de comparar diferentes tipos de heurísticas (algoritmos diseñados para aproximar óptimos globales). ¿Cómo se comporta el algoritmo codicioso en comparación con una búsqueda aleatoria del espacio de soluciones?

Imagen del autor

Podemos ver que, a medida que el número de cortes aumenta, la búsqueda aleatoria empeora mucho. Esto tiene sentido porque la búsqueda aleatoria selecciona aleatoriamente 500 soluciones y elige la mejor, a medida que el espacio de soluciones se expande, el porcentaje de probabilidad del espacio de soluciones que buscamos aleatoriamente se vuelve más pequeño. Ahora podemos ver que la solución codiciosa es mucho mejor que simplemente mirar aleatoriamente posibles soluciones.

Conclusiones

Parece que la solución codiciosa para el problema de corte de material es una forma razonable y muy rápida de encontrar una solución bastante buena. Para mis propósitos, esto es suficiente. Solo hago unos pocos proyectos al año y suelen ser pequeños. Sin embargo, para aplicaciones como plantas de fabricación, enfoques más complicados e intensivos probablemente tengan un impacto significativo en los ingresos de la empresa. Puedes investigar la ‘programación lineal entera mixta’ (MILP), que es otra forma de buscar soluciones óptimas mejores.

Si profundizara más en este problema, compararía el enfoque codicioso con mejores algoritmos metaheurísticos (la búsqueda aleatoria probablemente sea la peor) como diversas versiones de escalada de colina, búsqueda tabú o recocido simulado. Por ahora, lo dejaré aquí, ¡sin embargo, tengo otra tabla que hacer!

Para todo el código utilizado en este artículo, consulta este repositorio.

We will continue to update Zepes; if you have any questions or suggestions, please contact us!

Share:

Was this article helpful?

93 out of 132 found this helpful

Discover more

Inteligencia Artificial

Gafas utilizan sonar e inteligencia artificial para interpretar posturas del cuerpo superior en 3D

Investigadores de la Universidad de Cornell han desarrollado un dispositivo portátil que utiliza ondas sonoras inaudi...

Inteligencia Artificial

Optimiza el costo de implementación de los modelos base de Amazon SageMaker JumpStart con los puntos finales asincrónicos de Amazon SageMaker

En esta publicación, nos enfocamos en estas situaciones y resolvemos el problema de arriesgar altos costos al impleme...

Inteligencia Artificial

Luma AI lanza Genie un nuevo modelo de IA generativa en 3D que te permite crear objetos en 3D a partir de texto.

En el modelado 3D, crear objetos 3D realistas a menudo ha sido una tarea compleja y que consume mucho tiempo. Las per...

Inteligencia Artificial

Expertos en ciberseguridad se disponen a asegurar las elecciones de Estados Unidos en 2024

Un equipo de expertos en ciberseguridad establecido a través del Centro de Intercambio y Análisis de Información Tecn...

Inteligencia Artificial

Manteniendo secretos en un mundo cuántico

Los criptógrafos están trabajando en esquemas de cifrado de datos lo suficientemente fuertes como para resistir ataqu...

Ciencia de Datos

Samsung adopta la IA y los grandes datos, revoluciona el proceso de fabricación de chips.

Samsung Electronics Co., el principal fabricante mundial de chips de memoria, está a punto de revolucionar su proceso...