约束单目标优化

Question

介绍我需要使用两个值集（在这种情况下为重量和体积）将填充有某种类型（例如水桶）的数组拆分，同时将权重的总和保持在最小值（首选）和卷总数之间的差异小于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是右侧的存储桶，并计算所得的绝对差，然后，该常数再次确定要检查的值结论我想我需要在这里包括更多的数学信息，但是老实说，我一直呆在这里，不知道如何继续在这里，所以我想从您那里得到一些帮助，基本上可以在这里为我提供帮助。

Answer 1

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

在数学上，这将在体积差异小于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原始weights和volumes向量的长度在哪里），这些向量可能会很快失去控制。关于此主题的文献很多，算法更为有效，但它们通常针对特定的问题和/或约束条件。您可以在Google上搜索“线性整数编程”，以查看在此主题上所做的事情。

我认为最简单的方法可能是执行基于启发式的蛮力搜索，在这种情况下，您会尽早修剪搜索树，以免超出体积约束，并保持接近约束（一般而言，线性解优化问题在可行空间的边缘）。

如果您一般不熟悉优化文章或数学知识，那么Wikipedia文章会提供很好的介绍，但是有关此主题的大多数文章会迅速显示一些您可以立即适应的（伪）代码。

如果您n的解决方案很大，我认为您将不得不在解决方案的优化程度与计算速度之间做出权衡。您的解决方案可能不是最佳选择，但是它比穷举搜索要快得多。可能会有更好的权衡取舍，具体取决于问题的确切配置。