使用哪种算法来解决这个优化问题？

人工智能 算法
2021-10-21 14:41:38
  • 我有从 1 到 7 的名为“资源”的项目。
  • 我必须在从 1 到 10 标识的不同操作中使用它们。
  • 我每次最多可以做4个动作。这称为“操作”。
  • 即使使用了 4 次，每次“操作”的资源使用成本为 1。
  • 下表显示了执行相关操作所需的资源：
|        |            Resources             |
|--------|----------------------------------|
| Action |  1 |  2 |  3 |  4 |  5 |  6 |  7 |
|--------|----------------------------------|
|     1  |  1 |  0 |  1 |  1 |  0 |  0 |  0 |
|     2  |  1 |  1 |  0 |  0 |  1 |  0 |  0 |
|     3  |  1 |  0 |  1 |  0 |  0 |  1 |  0 |
|     4  |  0 |  1 |  0 |  0 |  0 |  0 |  0 |
|     5  |  1 |  0 |  1 |  1 |  0 |  1 |  0 |
|     6  |  1 |  1 |  1 |  0 |  0 |  0 |  0 |
|     7  |  0 |  1 |  0 |  0 |  0 |  0 |  0 |
|     8  |  1 |  0 |  1 |  0 |  1 |  0 |  0 |
|     9  |  0 |  1 |  0 |  1 |  0 |  0 |  0 |
|    10  |  1 |  1 |  1 |  0 |  0 |  0 |  1 |

目标是将“操作”中的所有“操作”分组以最小化总成本。例如，由动作 {3,7,9} 组成的组需要资源 {1,2,3,4,6}，因此成本为 5，但由动作 {4,7,9} 组成的组需要资源 {2, 4}，因此成本为 2。

需要以最经济的方式完成所有行动。

哪种算法可以解决这个问题？

2个回答

一种可能的方法是首先将动作分组到所有可能的组中。对于最多 6 个分组的 30 个操作，这意味着：

C630+C530+C430+C330+C230+C130=768211
操作。

然后，我将定义约束以简化问题，就像在约束满足问题 (CSP) 中一样。您拥有的主要约束是一个动作只能在一个操作中表示。因此，如果您选择 768ks 操作中的 1 个开始，则第二个选项将受条件限制。

然后我会做一些计划并总结成本，直到最后进行深度优先搜索。每当我发现总成本比以前的更好时，您就会更新最佳值。（请记住，在所有使用的操作之间，搜索结束，所有操作都被探索过一次。）

在进行搜索时，成本会在旅途中累加。您可以预先计算一个与操作数相同大小的向量，其中每个值对应于操作的总成本，然后在您沿着路径前进时对其求和。

您还应该添加一些启发式方法以防止以不同的顺序检查相同的操作。例如，操作 [2,3,4] 后跟 [7,10]，其中每个数字代表一个动作，与执行：[7,10] 后跟 [2,3,4] 相同。

我终于放弃了用精确的方法来做的想法，转而使用启发式。我混合了多重引导、本地搜索和某些随机动作。显然这被称为贪婪随机自适应搜索程序（GRASP）

假设：最佳解决方案是用每个“操作”的最大“操作”填充“操作”。其他组合更贵

  1. 创建一个随机解
    [[1 2 3 4] [5 6 7 8] [9 10]]

  2. 计算每个“操作”的成本
    [[6] [6] [5]] == 17

  3. 研究最小化较低“操作”与其他“操作”置换某些“操作”的可能性。
    动作 4 和 7 用 9 和 10
    [[1 2 3 9] [5 6 10 8] [4 7]]

  4. 计算新成本
    [[6] [7] [1]] == 14

  5. 重复步骤 2 到 4，直到无法最小化下限，然后是第二个下限，然后是第三个等

  6. 您很快就会找到本地最小值。如果不允许更多移动但局部最小值不是全局最小值，则在两个随机“操作”之间置换两个随机“动作”并重复步骤 2º 到 5º。

使用这种方法，可以非常快速地找到调整到最小全局成本的解决方案，复杂度为 O(n·log(n))，其中 n 是“动作”的数量

我用 60 个“动作”和 26 个“资源”的随机样本对其进行了测试，这些样本分为 6 个“动作”的“操作”。大约需要 5 分钟才能得到一个非常好的解决方案，比最初的解决方案(*)好 40% 左右，30 分钟后它只得到了大约 1% 的更好解决方案

(*) 初始解实际上不是随机解。相反，我使用 15 只蚂蚁的“蚁群”算法来获得更好的初始解决方案并减少迭代次数，但这是另一段历史

其它你可能感兴趣的问题
上一篇是否有描述神经网络学习曲线的数学公式？ 下一篇如何对人类行为进行分类？