4

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

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

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

我希望运行此算法的学生人数（X）约为 36。

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

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

4

2 回答 2

5

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

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

随机初始分布

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

所有组配对

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

所有配对组合

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

该算法可以在配对和配对组合阶段进行微调。在优化一对组时，您必须选择例如学生在两组上的分布是否使一个组的分数增加+4但将另一组的分数降低-1，以获得组合+3 的改进优于两组都将其分数提高 +1 的分布，因为组合改进仅 +2。

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

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

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

A组：[1, 7, 13, 19, 25, 31]
B组：[2、8、14、20、26、32]
C组：[3, 9, 15, 21, 27, 33]
D组：[4、10、16、22、28、34]
E组：[5、11、17、23、29、35]
F组：[6, 12, 18, 24, 30, 36]

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

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

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

function improve(groups) {
    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]];
    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]];
    // FIND OPTIMAL DISTRIBUTION FOR ALL PAIRS OF GROUPS
    var optim = [];
    for (var i = 0; i < 15; i++) {
        optim[i] = optimise(groups[pairs[i][0]], groups[pairs[i][1]]);
    }
    // FIND BEST COMBINATION OF PAIRS
    var best, score = -1;
    for (var i = 0; i < 15; i++) {
        var current = optim[combi[i][0]].score + optim[combi[i][1]].score + optim[combi[i][2]].score;
        if (current > score) {
            score = current;
            best = i;
        }
    }
    // REDISTRIBUTE STUDENTS INTO GROUPS AND RETURN NEW SCORE
    groups[0] = optim[combi[best][0]].group1.slice();
    groups[1] = optim[combi[best][0]].group2.slice();
    groups[2] = optim[combi[best][1]].group1.slice();
    groups[3] = optim[combi[best][1]].group2.slice();
    groups[4] = optim[combi[best][2]].group1.slice();
    groups[5] = optim[combi[best][2]].group2.slice();
    return score;
}

// FIND OPTIMAL DISTRIBUTION FOR PAIR OF GROUPS
function optimise(group1, group2) {
    var optim = {group1: [], group2: [], score: -1};
    var set = group1.concat(group2).sort(function(a, b) {return a - b});
    var distr = [0,0,0,0,0,1,1,1,1,1,1];
    // TRY EVERY COMBINATION
    do {
        // KEEP FIRST STUDENT IN FIRST GROUP TO AVOID SYMMETRIC COMBINATIONS
        var groups = [[set[0]], []];
        // DISTRIBUTE STUDENTS INTO GROUP 0 OR 1 ACCORDING TO BINARY ARRAY
        for (var j = 0; j < 11; j++) {
            groups[distr[j]].push(set[j + 1]);
        }
        // CHECK SCORE OF GROUPS AND STORE IF BETTER
        var score = quality(groups[0]) + quality(groups[1]);
        if (score > optim.score) {
            optim.group1 = groups[0].slice();
            optim.group2 = groups[1].slice();
            optim.score = score;
        }
    } while (increment(distr));
    return optim;

    // GENERATE NEXT PERMUTATION OF BINARY ARRAY
    function increment(array) {
        var digit = array.length, count = 0;
        while (--digit >= 0) {
            if (array[digit] == 1) ++count
            else if (count) {
                array[digit] = 1;
                for (var i = array.length - 1; i > digit; i--) {
                    array[i] = --count > 0 ? 1 : 0;
                }
                return true;
            }
        }
        return false;
    }
}

// SCORE FOR ONE GROUP ; RANGE: 0 ~ 8.958797346140275
function quality(group) {
    // LOGARITHM FAVOURS SMALL IMPROVEMENTS TO ALL GROUPS OVER LARGE IMPROVEMENT TO ONE GROUP
    return Math.log((group[5] - group[4]) * (group[4] - group[3]) * (group[3] - group[2]) * (group[2] - group[1]) * (group[1] - group[0]));
}

// SUM OF SCORES FOR ALL 6 GROUPS ; RANGE: 0 ~ 53.75278407684165
function overallQuality(groups) {
    var score = 0;
    for (var i = 0; i < 6; i++) score += quality(groups[i]);
    return score;
}

// PREPARE RANDOM TEST DATA
var 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];
var groups = [[],[],[],[],[],[]];
for (var i = 5; i >=0; i--) {
    for (var j = 5; j >= 0; j--) {
        var pick = Math.floor(Math.random() * (i * 6 + j));
        groups[i].push(students[pick]);
        students[pick] = students[i * 6 + j];
    }
    groups[i].sort(function(a, b) {return a - b});
}

// DISPLAY INITIAL SCORE AND DISTRIBUTION
var score = overallQuality(groups);
document.write("<PRE>Initial: " + score.toFixed(2) + " " + JSON.stringify(groups) + "<BR>");

// IMPROVE DISTRIBUTION UNTIL SCORE NO LONGER INCREASES
var prev, step = 0;
do {
    prev = score;
    score = improve(groups);
    document.write("Step " + ++step + " : " + score.toFixed(2) + " " + JSON.stringify(groups) + "<BR>");
} while (score > prev && score < 53.75278407684165);
if (score >= 53.75278407684165) document.write("Optimal solution reached.</PRE>");

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

于 2016-01-03T00:46:35.163 回答
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 人。

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

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

然后你可以玩不同的排列（1），减少算法的贪婪（2），或者添加一些花哨的自动逻辑来停止搜索（例如，最后T一次迭代没有进展）。

于 2016-01-02T20:55:20.617 回答