“贪婪有多糟糕？”

探索一种贪婪解决方案来解决库存切割问题

目录

1. 库存切割问题的动机
2. NP-难问题的快速概述
3. 将库存切割问题编码为Python
4. 贪婪算法
5. 与低维度穷举搜索的比较
6. 与高维度随机搜索的比较
7. 结论

库存切割问题的动机

我是一名数据科学家。虽然我的数据科学技能在工作中非常重要（根据定义），但我发现数据科学的概念也有助于解决很多工作之外的问题！

我的数据科学技能在我作为一个DIY爱好者/制造商的业余爱好中非常有用。一个常见的挑战是如何规划材料的切割。我有一个从商店购买的多个相同尺寸材料的切割清单。如何以尽可能少的浪费方式规划切割？这个挑战被称为“库存切割问题”。事实证明，这是一个非常难解决的问题，事实上是NP-难问题！

在本文中，我将探索一种解决这个问题的“捷径”（双关语）并分析这种方法与传统方法的比较。

NP-难问题的快速概述

在这里，我不打算深入讨论NP-难问题，但我想给出一些直观的理解。一个优化问题之所以困难，通常是由于其解空间的大小。也就是说，为了找到最佳解决方案，您需要探索多少个可能的解决方案？问题的困难程度通常根据问题大小增长时解空间的增长速度来评估。

对于“库存切割问题”，随着添加更多切割，问题变得更大，甚至变得非常大。请看下面解空间的增长速度！

解空间的增长是阶乘级的，也就是说，必须搜索的总解决方案数量是n！，正如您所看到的，增长速度非常快。

NP代表“非确定性多项式”，这意味着该问题的增长速度快于任何多项式函数。有很多资源可以深入了解NP/NP-难问题。这就是我在这里要讨论的全部内容。

将库存切割问题编码为Python

库存切割问题本质上可以归结为一个排序问题。您按照特定的顺序进行切割，当一块库存的长度用完时，您继续按顺序切割下一块库存。

通过可视化可以最好地解释这一点。假设我们有以下切割顺序

[4英尺，2英尺，1英尺，2英尺，2英尺，1英尺]，并且我们有5英尺的库存尺寸。浪费计算如下所示：

这里我们总共浪费了4英尺。

但是，如果我们改变顺序（保持所有相同的切割），我们可以得到不同程度的浪费。让我们试试[4英尺，1英尺，2英尺，2英尺，1英尺，2英尺]：

在这里，我们只得到了3英尺的废料 – 只需改变顺序就可以减少废料！这就是优化问题的整个思想。我们想找出哪种切割顺序最好。

现在，为了将其编码为Python脚本，我们需要（1）计算每种顺序的废料的函数，和（2）将列表排序为最佳顺序的算法。

计算废料的函数只是复制上面概述的逻辑。以下是Python代码：

def total_waste(stock_size, solution):        '''        计算给定解决方案的截断废料                输入        stock_size (float) : 可购买的库存尺寸        solution (list)    : 描述切割顺序的浮点数列表                输出        cut_off_waste (float) : 给定解决方案的截断废料总量        '''        # 设置变量以跟踪当前库存上切割的总长度    temp_cut_length = 0        # 从没有废料开始    cut_off_waste = 0    for cut in solution:                # 如果下一个切割无法放在当前库存上，        # 计算新的废料并为另一块库存重置        if temp_cut_length + cut > stock_size:            # 计算截断废料            cut_off_waste += stock_size - temp_cut_length            # 重置切割长度            temp_cut_length = cut        else:            # 添加到累计切割长度上的库存            temp_cut_length += cut    # 添加最后一个切割废料 - 在循环中没有捕获到    cut_off_waste += stock_size - temp_cut_length        return cut_off_waste

我们将在下一部分介绍所需的算法。

贪婪算法

贪婪算法非常简单，只需找到适合当前工作库存剩余部分的最大切割。

使用前面的例子，我们假设我们要进行以下切割[4英尺，2英尺，1英尺，2英尺，2英尺，1英尺]，我们需要一个贪婪算法来优化顺序。

我们首先从适合当前库存块的最长切割开始。由于我们还没有进行任何切割，我们当前的库存块尺寸为5英尺。4英尺是我们拥有的最长切割，并且适合剩余的5英尺库存。下一个最长的切割是2英尺，由于我们只剩下1英尺的库存，它太长了。我们继续下一个最长的切割，即1英尺。这适合剩余的库存，所以下一个切割是1英尺。算法按照这种模式进行，直到没有更多的切割。

以下是Python中该算法的样子：

def greedy_search(cuts, stock_size):        '''        计算贪婪最优解                输入：        cuts (list)        : 需要进行的切割        stock_size (float) : 可购买的库存尺寸                输出：        cut_plan (list) : 获得贪婪最优结果的切割顺序                           waste (float)   : 解决方案浪费的材料数量            '''        # 空的切割顺序计划，将被填充    cut_plan = []    # 起始截断尺寸等于库存尺寸    cut_off = stock_size    # 复制切割列表以避免修改原始列表    cuts_copy = copy(cuts)        # 按降序对切割进行排序    cuts = list(np.sort(cuts)[::-1])        # 继续排序切割，直到    # 所有切割都已排序    while len(cuts_copy) > 0:        for cut_size in cuts_copy:                        # 如果切割尺寸小于剩余库存，            # 立即分配该切割            if cut_size < cut_off:                # 将切割添加到计划中                cut_plan.append(cut_size)                                # 更新剩余库存量                cut_off -= cut_size                                # 从仍需要排序的切割列表中删除切割                cuts_copy.remove(cut_size)                # 将截断重置为完整的库存尺寸        cut_off = stock_size        # 使用total_waste函数计算废料    waste = total_waste(stock_size, cut_plan)    return cut_plan, waste

与低n空间的穷举搜索比较

通过使用贪婪算法的最优解的近似值，我们节省了大量时间，但是这个近似值有多好？对解决方案空间进行穷举搜索可以得到全局最优解 – 这是我们的黄金标准。让我们将贪婪算法的解决方案与只有几个切割的全局最优解进行比较（请记住，对于很多切割来说，找到全局最优解非常困难）。

我随机创建了250个切割列表，切割尺寸范围从2到10个切割。每个切割的大小在0和1之间，而库存尺寸设定为1.1。以下是性能：

如你所见，随着’n’的增加，贪婪算法的性能相对于全局最优解变差，但仍然保持相对接近且高度相关。

与高维n空间中的随机搜索比较

不幸的是，我们有一个重大盲点…也就是说，我们不知道高维n空间中的全局最优解。现在，我们开始比较不同类型的启发式算法（旨在逼近全局最优解的算法）。贪婪算法在解空间的随机搜索中表现如何？

我们可以看到，随着切割数量的增加，随机搜索的性能变得更差。这是有道理的，因为随机搜索是随机选择500个解决方案并选择最佳解决方案-随着解空间的扩大，我们随机搜索的解决方案的概率百分比越来越小。现在我们可以看到，贪婪解决方案比随机查看潜在解决方案要好得多。

结论

似乎贪婪解决方案对于切割库存问题是一种合理且非常快速的寻找相当好的解决方案的方式。对于我的目的来说，这已经足够了。我每年只做几个项目，而且它们通常很小。然而，对于制造厂等应用，更复杂和密集的方法可能会对公司产生重大的经济影响。你可以研究一下“混合整数线性规划”（MILP），这是另一种寻找更优解的方法。

如果我要更深入地研究这个问题，我会将贪婪方法与更好的元启发式算法（随机搜索可能是最差的一个）进行比较，例如各种版本的爬山法、禁忌搜索或模拟退火。目前我就到这里，不过我还有另一个表要做！

本文中使用的所有代码，请参见此存储库。