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

2023-11-30

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

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

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

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

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

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


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

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

random initial distribution

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

all pairings of groups

然后,它会比较所有 15 个配对组合的分数,找到总体分数最高的组合,例如DE+AC+FB.

all combinations of pairings

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

该算法可以在配对和配对组合阶段进行微调。当优化一对组时,您必须选择例如学生在两组中的分布是否比两组都增加的分布更可取:将一组的分数提高 +4,但将另一组的分数降低 -1,综合提高 +3他们的得分提高了+1,但综合进步仅+2。

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

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


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



group A: [1,  7, 13, 19, 25, 31]
group B: [2,  8, 14, 20, 26, 32]
group C: [3,  9, 15, 21, 27, 33]
group D: [4, 10, 16, 22, 28, 34]
group E: [5, 11, 17, 23, 29, 35]
group 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>");

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


该方法的讨论和实际实现可以在学士论文“Synthesalgorithmus zur effizienten Einteilung von Software-Teams”中找到(pdf)作者:Nils Rieke,2021 年,汉诺威莱布尼茨大学。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

将学生分组的最快启发式算法是什么? 的相关文章

  • 如何读取FTL文件中的JSONArray?

    我在我的 Java 文件中硬编码了以下 JSON 对象 JSONObject notificationInfoJson new JSONObject notificationInfoJson put title Payment Receiv
  • Hapijs 在一个连接上同时使用 Http 和 Https

    New to Hapijs http hapijs com 并尝试使用它来创建一个应用程序 该应用程序对所有请求使用 HTTPS 并将 HTTP 重定向到安全连接 问题是应用程序进入 HTTPS 模式没有问题 但如果我将 URL 更改为 H
  • Cassandra 会话与集群 有什么可分享的?

    考虑 Cassandra 的 Session 和 Cluster 类 Java 驱动程序 我想知道有什么区别 在 Hibernate 中 每次都会创建一个会话并共享会话工厂 从许多来源我了解到 它被认为是创建一个会话并在多个线程之间共享它
  • Git - 在特定提交之前压缩历史记录中的所有提交

    我有一个 Mercurial 存储库 正在将其转换为 Git 提交历史记录非常大 我不需要新存储库中的所有提交历史记录 一旦我将提交历史记录转换为 Git 并且在推送到新存储库之前 我想将某个标记之前的所有提交压缩为一个提交 所以 如果我有
  • Rails:统计用户未读通知的数量

    我目前有一个处理用户活动通知系统的活动模型 当发生某些操作 例如创建新文章 时 活动观察者会创建一个新活动 现在我想记录当前用户尚未看到的这些活动通知中有多少 类似于 facebook 上的通知宝石 每次用户单击通知链接时 数字应重置为 0
  • ftrace 是否允许捕获 Linux 内核的系统调用参数,或者仅捕获函数名称?

    目标是检查任何进程传递给特定系统调用 例如 exec open 等 的参数 来自官方文档 https www kernel org doc Documentation trace ftrace txt 没有描述记录函数参数的功能 主要查看
  • 在 url 中传递百分号 (%) 并使用 php 获取其准确值

    我正在尝试在 url 中传递百分号 例如 B6011000995504101 SB 但当我回声时 它又回来了 011000995504101 SB 我想要与在 URL 中传递的值完全相同的值 我尝试使用 urlencode 函数 但它给了我
  • 如何使用 jQuery 和“this”捕获更改的表单元素值

    我有以下代码 每当我的 Web 表单中发生元素更改时 该代码都会起作用 我一直在纠结的是如何捕捉表单字段元素 id name and 改变值当更改事件被触发时 谁能帮我解决这个问题吗 Thanks JavaScript
  • 闪亮的本地部署错误:输入字符串 1 无效 UTF-8

    我很惊讶地发现一个突然的错误 我的 ShinyApp 停止工作并出现未知错误 提示 输入字符串 1 无效 UTF 8 即使在昨天 该应用程序也可以正常运行 但是突然停止了 下面是我运行时的错误描述runApp gt runApp Liste
  • ES6解构对象赋值函数参数默认值

    您好 我正在查看在传递函数参数时使用对象解构的示例对象解构演示 https developer mozilla org en US docs Web JavaScript Reference Operators Destructuring
  • 在Python中使用os.makedirs创建目录时出现权限问题

    我只是想处理上传的文件并将其写入工作目录中 该目录的名称是系统时间戳 问题是我想以完全权限创建该目录 777 但我不能 使用以下代码创建的目录755权限 def handle uploaded file upfile cTimeStamp
  • 将蒙版图像作为 PNG 文件写入磁盘

    基本上 我从网络服务器下载图像 然后将它们缓存到磁盘上 但在这样做之前 我想屏蔽它们 我正在使用每个人似乎都指出的屏蔽代码 可以在这里找到 http iosdevelopertips com cocoa how to mask an ima
  • Java编程编译jar

    我有一个文本文件中的java源代码 必须在源代码中输入一些自定义的硬编码变量 然后将其转换为 jar 这是可行的 但是当我运行 jar 时 找不到 Main 类 当我用 WinRAR 解压 jar 文件时 我似乎找不到错误 当我通过 cmd
  • 美丽的汤刮 - 登录凭据不起作用

    尝试使用登录凭据抓取页面 payload email gmail com password urls login url https www spotrac com signin url https www spotrac com nba
  • Android 中用于过渡的自定义动画对象?

    我想用一些更奇特的东西来覆盖 Android 中的默认活动转换 我想做的事情不能用通常使用的 XML 集来完成 所以我不能使用overridePendingTransition因为它只接受对基于 XML 的动画资源的整数引用 我想做的是创建
  • dplyr::mutate 添加多个值

    网上有几个与此相关的问题dplyr Github 存储库 https github com hadley dplyr已经 并且至少有一个相关的问题 但没有一个问题完全涵盖了我的问题 我认为 在 dplyr mutate 调用中添加多列 ht
  • 使用 ActivePerl 时为什么必须指定带有备份扩展的 -i 开关?

    除非我使用备份扩展指定它们 否则我无法就地编辑在 ActivePerl 下运行的 Perl 单行代码 C gt perl i ape splice F 2 0 q inserted text qq F n file1 txt Can t d
  • 如何获取通过网络驱动器访问的文件的 UNC 路径?

    我正在 VC 中开发一个应用程序 其中网络驱动器用于访问文件 驱动器由用户手动分配 然后在应用程序中选择驱动器 这会导致驱动器并不总是映射到相同的服务器 我该如何获取此类文件的 UNC 路径 这主要是为了识别目的 这是我用来将普通路径转换为
  • 带有包含布局的导航抽屉布局

    我认为我的问题实际上很简单 但我不知道如何解决 有一个工作导航抽屉 代码如下
  • 相当于 JavaScript 中 Ruby 的each_cons

    许多语言都曾提出过这个问题 但 javascript 却没有 Ruby 有方法Enumerable each cons https devdocs io ruby 2 5 enumerable method i each cons看起来像这

随机推荐