约束单目标优化

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&nbsp; &nbsp; subject to&nbsp; volumes . x < 1000.0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for all i, x[i] = +1 or -1a . b矢量点积在哪里。解决此问题后，所有索引x = +1对应于您的第一个数组，所有索引x = -1对应于您的第二个数组。不幸的是，已知0-1整数编程是NP-hard的。解决该问题的最简单方法是对空间进行穷尽的蛮力探索，但它需要测试所有2^n可能的向量x（n原始weights和volumes向量的长度在哪里），这些向量可能会很快失去控制。关于此主题的文献很多，算法更为有效，但它们通常针对特定的问题和/或约束条件。您可以在Google上搜索“线性整数编程”，以查看在此主题上所做的事情。我认为最简单的方法可能是执行基于启发式的蛮力搜索，在这种情况下，您会尽早修剪搜索树，以免超出体积约束，并保持接近约束（一般而言，线性解优化问题在可行空间的边缘）。如果您一般不熟悉优化文章或数学知识，那么Wikipedia文章会提供很好的介绍，但是有关此主题的大多数文章会迅速显示一些您可以立即适应的（伪）代码。如果您n的解决方案很大，我认为您将不得不在解决方案的优化程度与计算速度之间做出权衡。您的解决方案可能不是最佳选择，但是它比穷举搜索要快得多。可能会有更好的权衡取舍，具体取决于问题的确切配置。