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

Question

我有 X 名学生，其中 X 是 6 的倍数。我现在想将学生分成 6 人一组。

我有一个函数可以衡量 6 人一组的“好”程度（假设它是一个目前以恒定时间运行的黑匣子）。通过将学生分开，然后对每个组调用我的函数来衡量其优点，然后总结每个组的优点，我就能够衡量一组特定组的“好”程度。

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

我预计运行该算法的学生数量 (X) 约为 36 人。

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

有人可以指出我正确的方向吗？我做了一些研究，这个问题似乎与旅行商问题几乎相同（问题空间是学生/节点的所有排列），但我不认为我可以将 TSP 算法应用于此，因为“节点”的数量“（大约 36）对于任何有效的东西来说都是相当大的。

Answer 1

让我们以 36 名学生分为 6 组为例。检查所有组合是不切实际的，因为共有 3,708,580,189,773,818,399,040 个。然而，通过检查学生在各组之间的分布来进行重复改进的策略应该是可行的。

\n

有 462 种方法可以将 12 名学生分成 2 组，因此找到最佳的 12\xe2\x86\x922 分布只需要调用“组质量”函数 924 次。6 个小组中有 15 种可能的小组配对，因此 13,860 个调用将揭示小组配对的最佳方式，并在配对之间重新分配学生以获得最大的进步。

\n

\n

该算法从随机初始分布开始，计算所有 15 个组对的最佳分布：AB,CD,EF,BC,DE,FA,AC,BD,CE,DF,EA,FB,AD,BE,CF。

\n

\n

然后比较所有 15 个配对组合的分数，找到总分最高的组合，例如DE+AC+FB。

\n

\n

然后它重新分配学生，并返回新的总分。这是一个改进步骤。然后，这个过程会重复多次，直到找不到更多的改进，或者直到你用完时间。从不同的随机初始分布开始多次运行该算法也可能很有用。

\n

该算法可以在配对和配对组合阶段进行微调。优化一对组时，您必须选择例如学生在两组中的分布是否使一组的分数增加 +4，但使另一组的分数减少 -1，对于综合提高 +3，优于两组得分均增加 +1 的分布，综合提高仅 +2。

\n

同样，在配对组合阶段，您必须决定是否需要对所有三对进行改进，或者是否选择综合改进最高的组合。

\n

我认为，如果允许一个小组在一个步骤后获得较低的分数，如果这可以提高总体分数，将允许学生在小组之间进行更多的移动，并可能导致探索更多的组合。

\n\n

为了能够编写代码来测试此策略，需要一个虚拟的“小组质量”函数，因此我将学生编号从 1 到 36，并使用一个函数来乘以相邻学生编号之间的距离。例如，该小组[2,7,15,16,18,30]将获得分数5*8*1*2*12 = 960。如果把编号想象成学生能力的排名，那么优质组就意味着混合能力组。最优分布为：

\n

\nA 组：[1, 7, 13, 19, 25, 31]\nB 组：[2, 8, 14, 20, 26, 32]\nC 组：[3, 9, 15, 21, 27, 33 ]\nD 组: [4, 10, 16, 22, 28, 34]\nE 组: [5, 11, 17, 23, 29, 35]\nF 组: [6, 12, 18, 24, 30, 36]\n

\n

各组得分6*6*6*6*6 = 7776，总分46656. 在实践中，我发现使用Log(score)会产生更好的结果，因为它有利于所有组的小改进，而不是一两个组的大改进。（支持对多个组的改进，或对质量最低的组的改进，或仅选择最佳的整体改进，是您必须针对特定的“组质量”功能进行微调的部分。）

\n\n

令我惊讶的是，该算法总是设法找到最佳解决方案，并且只需 4 到 7 个步骤，这意味着进行的“组质量”函数调用次数少于 100,000 次。我正在使用的“群体质量”算法当然非常简单，因此您必须用真实的东西来检查它，以衡量这种方法在您的特定情况下的有用性。但很明显，该算法只需几步即可彻底重新排列分布。

\n

（为了简单起见，下面的代码示例针对 36 名学生和 6 个组的情况进行了硬编码。对每组中的学生进行排序是为了简化质量函数。）

\n

\r\n

\r\n

function improve(groups) {\n    var pairs = [[0,1],[0,2],[0,3],[0,4],[0,5],[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]];\n    var combi = [[0,9,14],[0,10,13],[0,11,12],[1,6,14],[1,7,13],[1,8,12],[2,5,14],[2,7,11],[2,8,10],[3,5,13],[3,6,11],[3,8,9],[4,5,12],[4,6,10],[4,7,9]];\n    // FIND OPTIMAL DISTRIBUTION FOR ALL PAIRS OF GROUPS\n    var optim = [];\n    for (var i = 0; i < 15; i++) {\n        optim[i] = optimise(groups[pairs[i][0]], groups[pairs[i][1]]);\n    }\n    // FIND BEST COMBINATION OF PAIRS\n    var best, score = -1;\n    for (var i = 0; i < 15; i++) {\n        var current = optim[combi[i][0]].score + optim[combi[i][1]].score + optim[combi[i][2]].score;\n        if (current > score) {\n            score = current;\n            best = i;\n        }\n    }\n    // REDISTRIBUTE STUDENTS INTO GROUPS AND RETURN NEW SCORE\n    groups[0] = optim[combi[best][0]].group1.slice();\n    groups[1] = optim[combi[best][0]].group2.slice();\n    groups[2] = optim[combi[best][1]].group1.slice();\n    groups[3] = optim[combi[best][1]].group2.slice();\n    groups[4] = optim[combi[best][2]].group1.slice();\n    groups[5] = optim[combi[best][2]].group2.slice();\n    return score;\n}\n\n// FIND OPTIMAL DISTRIBUTION FOR PAIR OF GROUPS\nfunction optimise(group1, group2) {\n    var optim = {group1: [], group2: [], score: -1};\n    var set = group1.concat(group2).sort(function(a, b) {return a - b});\n    var distr = [0,0,0,0,0,1,1,1,1,1,1];\n    // TRY EVERY COMBINATION\n    do {\n        // KEEP FIRST STUDENT IN FIRST GROUP TO AVOID SYMMETRIC COMBINATIONS\n        var groups = [[set[0]], []];\n        // DISTRIBUTE STUDENTS INTO GROUP 0 OR 1 ACCORDING TO BINARY ARRAY\n        for (var j = 0; j < 11; j++) {\n            groups[distr[j]].push(set[j + 1]);\n        }\n        // CHECK SCORE OF GROUPS AND STORE IF BETTER\n        var score = quality(groups[0]) + quality(groups[1]);\n        if (score > optim.score) {\n            optim.group1 = groups[0].slice();\n            optim.group2 = groups[1].slice();\n            optim.score = score;\n        }\n    } while (increment(distr));\n    return optim;\n\n    // GENERATE NEXT PERMUTATION OF BINARY ARRAY\n    function increment(array) {\n        var digit = array.length, count = 0;\n        while (--digit >= 0) {\n            if (array[digit] == 1) ++count\n            else if (count) {\n                array[digit] = 1;\n                for (var i = array.length - 1; i > digit; i--) {\n                    array[i] = --count > 0 ? 1 : 0;\n                }\n                return true;\n            }\n        }\n        return false;\n    }\n}\n\n// SCORE FOR ONE GROUP ; RANGE: 0 ~ 8.958797346140275\nfunction quality(group) {\n    // LOGARITHM FAVOURS SMALL IMPROVEMENTS TO ALL GROUPS OVER LARGE IMPROVEMENT TO ONE GROUP\n    return Math.log((group[5] - group[4]) * (group[4] - group[3]) * (group[3] - group[2]) * (group[2] - group[1]) * (group[1] - group[0]));\n}\n\n// SUM OF SCORES FOR ALL 6 GROUPS ; RANGE: 0 ~ 53.75278407684165\nfunction overallQuality(groups) {\n    var score = 0;\n    for (var i = 0; i < 6; i++) score += quality(groups[i]);\n    return score;\n}\n\n// PREPARE RANDOM TEST DATA\nvar students = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36];\nvar groups = [[],[],[],[],[],[]];\nfor (var i = 5; i >=0; i--) {\n    for (var j = 5; j >= 0; j--) {\n        var pick = Math.floor(Math.random() * (i * 6 + j));\n        groups[i].push(students[pick]);\n        students[pick] = students[i * 6 + j];\n    }\n    groups[i].sort(function(a, b) {return a - b});\n}\n\n// DISPLAY INITIAL SCORE AND DISTRIBUTION\nvar score = overallQuality(groups);\ndocument.write("<PRE>Initial: " + score.toFixed(2) + " " + JSON.stringify(groups) + "<BR>");\n\n// IMPROVE DISTRIBUTION UNTIL SCORE NO LONGER INCREASES\nvar prev, step = 0;\ndo {\n    prev = score;\n    score = improve(groups);\n    document.write("Step " + ++step + " : " + score.toFixed(2) + " " + JSON.stringify(groups) + "<BR>");\n} while (score > prev && score < 53.75278407684165);\nif (score >= 53.75278407684165) document.write("Optimal solution reached.</PRE>");

\r\n

\r\n

\r\n

\n

注意：选择最佳的配对组合并重新分配这些配对组中的学生后，您当然知道这三对现在拥有最佳的学生分配。因此，您可以在下一步中跳过检查这三对，并使用它们的当前分数作为最佳分数。

\n\n

该方法的讨论和实际实现可以在 Nils Rieke 的学士论文“Synthesealgorithmus zur effizienten Einteilung von Software-Teams”（pdf）中找到，作者：Nils Rieke，2021 年，莱布尼兹大学\xc3\xa4t 汉诺威。

\n

Answer 2

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

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 个人。

(2) - 如果我们所做的更改使我们的解决方案变得更糟（得分较低），我们会拒绝它。您稍后可以用一定概率接受更差的解决方案来替换它，以使该算法成为模拟退火。

首先简单地运行 1000 次迭代左右，并将 Score[i] 绘制为 i 的函数，以了解您的解决方案改进的速度。运行几次（尝试不同的随机起点）。

然后，您可以尝试不同的排列 (1)，使算法不那么贪婪 (2)，或添加一些奇特的自动逻辑来停止搜索（例如，最后一次T迭代中没有进展）。