人工智能 - 给定一个整数列表{C1, … ,Cñ}{C1,…,Cñ}，我如何找到一个整数DD使余数之和最小化∑一世C一世模式 D∑一世C一世模组 D? - 吾爱随笔录

给定一个整数列表{C1, … ,Cñ}{C1,…,Cñ}，我如何找到一个整数DD使余数之和最小化∑一世C一世模式 D∑一世C一世模组 D?

人工智能机器学习遗传算法优化约束优化

2021-10-27 23:40:15

我有一组固定整数 $S = \{c_1, \dots, c_N \}$ . 我想找到一个整数 $D$ , 大于某个阈值 $T$ ， IE $D > T \geq 0$ ，这将每个 $c_i$ 剩下的 $r_i \geq 0$ ， IE $r_i$ 可以写成 $r_i = c_i \text{ mod } D$ ，使得余数之和最小化。

换句话说，这是我的问题

\begin{aligned} D^{*} = {argmin}_{D} & \sum_{i} c_{i} mod D \\ subject to & D > T \end{aligned}

$\begin{equation} \begin{aligned} D^* \quad = \text{argmin}_D& \sum_i c_i \text{ mod } D \\ \textrm{subject to} &\quad D > T \end{aligned} \end{equation}$

如果整数有公约数，这个问题就很简单了。但是，如果整数是相对互质的，则不清楚如何解决它。

套装 $|S| = N$ 可以在附近 $10000$ ，并且每个元素也有数万的值。

我正在考虑用遗传算法（GA）解决它，但它有点慢。我想知道有没有其他方法可以解决这个问题。

1个回答

遗传算法不是这里最好的方法：

GA 是一种随机方法，因此永远无法保证最佳解决方案。
您的解决方案（GA 个体）被建模为一个简单的整数。GA 最适合找到建模为数组（如我们的基因组）的解决方案，因此它可以进行突变和交叉。

好方法：

集合 |S|=N 可以在 10000 左右，每个元素也有数万的值。

它当然看起来很多，但对于计算机来说，这不是那么多。我们可以从蛮力开始并逐步简化它以获得更好的性能：

蛮力：

您可以尝试从 D>T 到 D<max(S) 的每个整数并存储最佳候选者。

# Fully functional python solution:
import random
import time

# Let's start initializing a random T
T = random.randint(1, 100)
# And a S, with 10,000 integers fom T to 10,000
S = [random.randint(T, 10000) for i in range(10000)]


def LowestRemainder(List, Threshold):
    # Storing the all time lowest D and remainder
    Best_D_SoFar = Threshold+1
    lowestRemainderSoFar = sum(List)
    for d in range(Threshold+1, max(List)+1):
        remainder = sum(c%d for c in List)
        if remainder < lowestRemainderSoFar:
            lowestRemainderSoFar = remainder
            Best_D_SoFar = d
    return Best_D_SoFar, lowestRemainderSoFar

print("Looking for D > %d, that minimizes the sum of all remainder in a list containing %d integers" % (T, len(S)))
# Keep track of time
start_time = time.time()
# call the function
D, R = LowestRemainder(S, T)
# stop the clock
elapsed_time = time.time() - start_time
print("Found D =", D, "and lowest remainder =", R, "in", elapsed_time, "seconds")

我在我的机器上测试了几次，它总是在不到4 秒的时间内运行（最长

但这是蛮力基线。因此，让我们通过提前中断内部循环来提高效率：

    # Remove this:
    # remainder = sum(c%d for c in List)
    
    # Add this instead:
      remainder = 0
      for c in List:
          remainder += c%d
          if remainder > lowestRemainderSoFar:
              break

并做了！

现在只需不到 0.2 秒

（对于整个 10,000 大小的数组，随机整数高达 10,000:)

额外的想法：

由于最好的解决方案可能是一个较小的数字（如稍后讨论的那样），如果完成时间太长，您可以简单地中断，您仍然会有一个很好的解决方案（不保证是最佳的），就像 GA 一样（并且可能更好，因为您将快速利用最佳候选人，而不是探索空间）。

因式分解是我们的朋友：

假设一个解决方案D，得分为S。

现在分解解，找到构成 D: [p1,p2,…] 的素数列表。

现在删除一些 p，生成一个D'，你会注意到c mod(D) >= c mod(D')对于任何 c、任何 D 和任何 p。

这意味着，如果 D 已经被评估，您不需要探索 D 的任何倍数。

这将大大减少试验量！

无门槛场景：

使用这个因式分解原理，在 T=1 （如果 T<1，比 D=1 是最佳解）的更简单场景中，我们保证解是素数！此外，您不需要搜索到最大的数字max(S)，因为sqrt(max(S))就足够了。

有阈值场景

它使编程变得有点困难，但您仍然只需要遍历共同素数。

上限：

一旦你击中了大于最小 S ( d>min(S)) 的第一个候选者 (d)，那么这个余数将是 min(S)。

如果目前最好的解决方案已经优于 min(S)，我们可以跳过所有下一个候选者。

这个逻辑是累积的。一旦候选 d 大于 N 个最低的 S，余数之和将至少是所有 N 个最低 S 的总和。因此，我们的循环可能类似于：

if(sum([s<d for s in S]) > lowest):
  return d
else:
  d = next_coprime()

在包含数千个元素的列表中，极有可能尽早找到最小的元素。并且即使它不满足完成条件，它也只会随着 d 的增长而积累更多的元素。

总之：

从基线开始并限制边界，直到您的代码在所需的时间运行。

例子：

输入：

S = [10, 19, 28]
T = 3

过程：测试所有d>T，跳过倍数并停在上限：

d = 4 --> 余数 = [2,3,0] = 5
d = 5 --> 余数 = [0,4,3] = 7
d = 6 --> 余数 = [4,1,4] = 9
d = 7 --> 余数 = [3,5,0] = 8
d = 8 --> 是 4 的倍数（跳过）
d = 9 --> 余数 = [1,1,1] = 3
d = 10--> 是 5 的倍数（跳过）
d = 11--> 11>min(S) --> 余数 = [10,x,x] > 3.完成！

其它你可能感兴趣的问题

上一篇人工智能系统如何发展其领域知识？不仅仅是机器学习吗？下一篇在 YOLO 中，与每个锚框相关联的值究竟代表什么？

给定一个整数列表{C1, … ,Cñ}{C1,…,Cñ}，我如何找到一个整数DD使余数之和最小化∑一世C一世 模式 D∑一世C一世 模组 D?