将学生分成几组的最快的启发式算法是什么？

Question

我有X个学生数，其中X是6的倍数，现在我想把学生分成6组。

我有一个函数来衡量一组6的“好”程度(让我们说它是一个黑匣子，目前运行时间是恒定的)。通过把学生分开，然后调用我对每一组的函数来衡量它是好的，然后总结每一组的好，我就能测量出某一组的“好”。

我试图创建一种算法，以一种方式对学生进行分组，使所有组的总优度最大化，并且没有一个组的优度低于某个值y。换句话说，将学生分组为6组，在所有组都有优优高于y的约束下，将其最大化。

我期望在这个算法上运行的学生数(X)大约是36。

这个问题似乎是NP-完全的，所以我同意解决一个启发式算法。我对此没有太多的经验，但是某种遗传算法或模拟退火，甚至是贪婪的算法，我认为可能会奏效，但我不知道从哪里开始我的研究。

有人能给我指点方向吗？我做了一些研究，这个问题似乎与旅行推销员问题(问题空间都是学生/节点的排列)几乎相同，但是我认为我不能将TSP算法应用到这个问题上，因为“节点”的数量(大约36个)对于任何有效的东西都是相当大的。

Answer 1

我要从一个非常简单的“随机搜索”算法开始：

start from a random solution (a partition of X to groups), call it S[0]

score[0] = black_box_socre(S[0])

i = 0

while (some condition):
    i++
    S[i] = some small permutation on S[i-1]  # (1)
    score[i] = black_box_score(S[i])
    if score[i] < score[i-1]:  # (2)  
        S[i] = S[i-1]
        score[i] = score[i-1]

(1) -在你的情况下，可以是小的排列，使两个人在不同的群体中转换。

(2) -如果我们做了一个改变，使我们的解决方案更糟(较低的分数)，我们拒绝它。稍后，您可以用接受一些概率的更坏的解来代替这一点，从而使这个算法成为模拟退火。

首先，只需运行1000次迭代，然后将scorei作为i的函数来绘制，以获得解决方案改进速度的感觉。运行这几次(尝试不同的随机起点)。

然后，您可以处理不同的排列(1)，使算法不那么贪婪(2)，或者添加一些花哨的自动逻辑来停止搜索(例如，在最后的T迭代中没有进展)。