1

介绍

我需要使用设置的两个值（在本例中为重量和体积）拆分一个填充有某种类型（例如，我们以水桶为例）的数组，同时将总重量之间的差异保持在最小（首选）和小于 1000 的总卷之间的差异（必需）。这不需要是一个完整的遗传算法或类似的东西，但它应该比我目前拥有的更好......

当前实施

由于不知道如何做得更好，我首先将数组拆分为两个长度相同的数组（数组可以填充奇数个项目），用两个值都为 0 的项目替换可能的空点。双方不需要有相同数量的项目，我只是不知道如何处理它。

在分发了这些之后，我正在尝试像这样优化它们：

func (main *Main) Optimize() {
    for {
        difference := main.Difference(WEIGHT)

        for i := 0; i < len(main.left); i++ {
            for j := 0; j < len(main.right); j++ {
                if main.DifferenceAfter(i, j, WEIGHT) < main.Difference(WEIGHT) {
                    main.left[i], main.right[j] = main.right[j], main.left[i]
                }
            }
        }

        if difference == main.Difference(WEIGHT) {
            break
        }
    }

    for main.Difference(CAPACITY) > 1000 {
        leftIndex := 0
        rightIndex := 0
        liters := 0
        weight := 100

        for i := 0; i < len(main.left); i++ {
            for j := 0; j < len(main.right); j++ {
                if main.DifferenceAfter(i, j, CAPACITY) < main.Difference(CAPACITY) {
                    newLiters := main.Difference(CAPACITY) - main.DifferenceAfter(i, j, CAPACITY)
                    newWeight := main.Difference(WEIGHT) - main.DifferenceAfter(i, j, WEIGHT)

                    if newLiters > liters && newWeight <= weight || newLiters == liters && newWeight < weight {
                        leftIndex = i
                        rightIndex = j
                        liters = newLiters
                        weight = newWeight
                    }
                }
            }
        }

        main.left[leftIndex], main.right[rightIndex] = main.right[rightIndex], main.left[leftIndex]
    }
}

功能：

main.Difference(const)计算两侧的绝对差，作为参数的常数决定计算差的值

main.DifferenceAfter(i, j, const)模拟两个桶之间的交换，i 是左边的桶，j 是右边的桶，然后计算得到的绝对差，然后常量再次确定要检查的值

解释：

基本上这是从优化权重开始的，这是第一个 for 循环所做的。在每次迭代中，它都会尝试可以切换的桶的所有可能组合，如果之后的差异小于当前差异（导致更好的分布），它会切换它们。如果权重不再变化，它就会跳出 for 循环。虽然不完美，但效果很好，我认为这对于我想要完成的事情是可以接受的。

然后应该是根据体积优化分布，所以总的差异小于1000。这里我尝试更加小心，并在切换之前搜索一次运行中的最佳组合。因此，它搜索导致最大容量变化的铲斗开关，并且也应该在这之间进行权衡，尽管我看到第一个铲斗组合尝试的缺陷将设置升和重量变量，从而导致下一个可能的组合被大量减少。

结论

我想我需要在这里包含更多的数学，但老实说我被困在这里并且不知道如何继续在这里，所以我想从你那里得到一些帮助，基本上可以帮助我在这里是受欢迎的。

4

2 回答 2

2

如前所述，您的问题实际上是一个受约束的优化问题，对您的体积差异有约束。

从数学上讲，这将在体积差小于 1000 的约束下最小化体积差。将其表示为线性优化问题的最简单方法是：

min weights . x
    subject to  volumes . x < 1000.0
                for all i, x[i] = +1 or -1

a . b矢量点积在哪里。解决此问题后，所有索引x = +1对应于您的第一个数组，所有索引x = -1对应于您的第二个数组。

不幸的是，已知0-1 整数编程是NP-hard。解决它的最简单方法是对空间进行详尽的蛮力探索，但它需要测试所有2^n可能的向量x（原始向量和向量n的长度在哪里），这很快就会失控。有很多关于这个主题的文献，有更有效的算法，但它们通常高度特定于一组特定的问题和/或约束。你可以谷歌“线性整数规划”来看看在这个主题上做了什么。weightsvolumes

我认为最简单的方法可能是执行基于启发式的蛮力搜索，在这种情况下，您可以尽早修剪您的搜索树，因为它会让您摆脱音量限制，并保持接近您的限制（作为一般规则，线性的解决方案优化问题在可行空间的边缘）。

以下是您可能想阅读的有关此类优化的几篇文章：

如果您不熟悉优化文章或一般数学，维基百科文章提供了很好的介绍，但大多数关于此主题的文章都会快速显示一些您可以立即适应的（伪）代码。

如果您n很大，我认为在某些时候您将不得不在解决方案的优化程度和计算速度之间做出权衡。您的解决方案可能不是最理想的，但它比穷举搜索要快得多。根据问题的确切配置，可能会有更好的权衡。

于 2012-11-02T12:41:54.020 回答
1

在您的情况下，重量差异似乎是客观的，而体积差异只是一个约束，这意味着您正在寻求优化重量属性差异（尽可能小）的解决方案，并满足差异的条件卷属性（总数 < 1000）。在这种情况下，它是一个单目标约束优化问题。

然而，如果您对多目标优化感兴趣，也许您想看看 Pareto Frontier 的概念：http ://en.wikipedia.org/wiki/Pareto_efficiency 。有利于保持多个在不同目标中具有优势的良好解决方案，即不失去多样性。

于 2012-11-02T02:27:34.897 回答