时隔5年，再做均衡分班

aoe1981

2014年8月前后，我发的均衡分班帖子主要如下：
1.邯郸学步2之学有所成：随机优化分班
http://club.excelhome.net/thread-1143904-1-1.html
(出处: ExcelHome技术论坛)

2.关于我做的均衡分班小结
http://club.excelhome.net/thread-1143346-1-1.html
(出处: ExcelHome技术论坛)

……我也难以准确罗列……

5年后的今日，我忽然“神经”了，再做一下“均衡分班”。
真实原因是：自己在之前帖子中暴露出的愚不自知、骄傲自满，想改改。
譬如：
1.没能理解香川大侠的金玉良言：


2.没能处理一众坛友的精到建议：










主要涉及：班级数上限拓展、增加处理“民族”、择班或禁班、科目添加。

如今“再做”，自然是冲着上面的问题的，均已实现。
1.真正做到了香川大侠谈到的“随机交换优化”，使得优化时间可控，大意是“随机选取两个不同班的任意两个学生交换”；
2.班级数上限随意，虽然在“数据验证”里最大设置了80个班，但不再设置工作表密码，可以自行修改，真正的上限是学生总人数；
3.像“性别”、“民族”、“地址区域”等需要数值化处理的项目，均作为特殊科目，请提前加工好原始数据，作为“科目”添加进“基础数据表”；
4.“禁班”的意思是“指定某学生不能在哪些班”，由于不止一个班，程序处理较烦，统一以其反面“择班”代替，“择班生”可以事前在“基础数据表”首列“班级”里输入所选正确的班级号，便不再参与后续“换班优化”；
5.“科目”可拓展，目前以“科目1”、“科目2”、“科目3”、……命名，也可以采用：“性别”、“民族”、“语文”、“数学”、“综合”等有实际意义的名称，并不影响程序运行。

或许，今日所做还有“未知问题”，不敢自夸了。

附件有两个版本：
1.保留费时的“遍历交换”： 再做均衡分班程序（遍历交换）.zip (145.86 KB, 下载次数: 537)

2019-9-18 00:03 上传

点击文件名下载附件

2.新增时间可控的“随机交换”： 再做均衡分班程序（随机交换）.zip (159.05 KB, 下载次数: 808)

2019-9-18 00:03 上传

点击文件名下载附件

（20190916 13：11对附件作了更新，主要是：优化了代码、修改了几处小失误、增加了较为有用的错误检测识别代码。详情见6楼。）

（20190917 23：50主要对“随机交换”附件作了更新，主要是：修复了极端情况下会出现的bug，并从新优化了代码，详情见9楼。）

附件中的“基础数据表”列结构如下：



其中：首列“班级”、次列“识别ID”（用于识别学生，防止重名）、三列“姓名”是固定次序的列，不可调换，否则出错。

最重要的原理如下图：
1.


2.


“随机交换”附件可以很快速的得到相当不错的结果：






但是，越追求极致结果，越费时，效用递减，而且不易达到极致结果。
但我个人推荐“随机交换”附件，追求一般极致结果的效率是很高的。

“遍历交换”附件中，遍历基础数据1次也要花很长时间，基本可能是数据规模（学生总人数、班级数）的平方倍，效率很低。但愿意花时间的话，又或者计算资源很优异的话，却是可以得到“随机交换”附件难以企及的结果的。如图：






最终，附件中的结果是：
遍历交换最小方差：9.809 0058253135
随机交换最小方差：9.809 39784309757

哈哈，算是一个新阶段的暂停吧。

aoe1981

下面又测试了一组分18个班的，每班人数均为53人，总人数是：954人，还是1楼附件中的基础数据，其中科目1实为“性别”，科目2实为“民族”（只分为汉族100和其他0），且事先择班生再没有改变。
测试效果图依次如下：
（1）随机交换优化分班：


















实际替换总次数为：314+18+10+11+5+5+6+1+0=370（次），10秒就可以达到17.543的方差，最后拼尽全力得到极致结果是：17.4091610300224；

（2）遍历交换优化分班：










实际替换总次数为：788+484+234+139+23=1668（次），对比随机交换优化的结果，容易想到：无效的互换次数居多。以上都是每次遍历基础数据1次的运行结果，足见“遍历一次基础数据”的用时是递增的，因为要找到可以替换的需要寻找更多的次数。最后费了更大力得到极致结果是：17.4084490328704，略微比随机交换优化的结果优异。
（3）综合对比：
大家也会发现：随机交换优化完胜遍历交换优化，前者短时间得到的结果，后者需要很长时间的努力才能超越！
只是：随着时间的延长，随机交换优化的效用递减，而遍历交换优化的效用对比递增的时间，可以说是持平，二者各有千秋吧，就让其并存吧，各取所需！

aoe1981

再次说明：
推荐“随机交换”版本！
推荐“随机交换”版本！
推荐“随机交换”版本！

重要的事情说三遍！
重要的事情说三遍！
重要的事情说三遍！

vvw123

沙发上顶一顶，先收藏

aoe1981

附件“随机交换”版本还有个特点：采取“小步快走”策略比“一次性迈大步”的效果更好。
仍然是954人分18个班，首次一次随机交换100000次取得的效果和7次5000、3次10000，共计65000次取得的效果一致，但再来10000次时并没有超越。
总得来说，随机策略下，“小步快走”或“少吃多餐”是不错的选择。

aoe1981

于2019年09月16日 13：11对1楼附件作了更新。
更新内容主要是：优化了代码、修改了几处小失误、增加了较为有用的错误检测识别代码（比如科目数为0时的错误，文本型成绩的排查等）。
同时，测试数据更新为7个科目，对应为：性别、民族、语文、数学、英语、品德、科学。其实还可以测试8个科目，比如增加“区域”，主要分为“服务区内学生”、“服务区外学生”。从运行情况看，都能做到“均衡”，虽然限制条件增多了，但似乎“一切皆有可能”。

boy8199

支持

二郎666

什么叫均衡分班，什么规则，还是自己设计规则

aoe1981

于2019年09月17日23：50对1楼附件作了更新。
更新主要内容是：修复了一个在极端情况下会出现的重要bug，并从新的角度出发，优化了代码。

这个bug所针对的极端情况是由“择班生”造成的。假设某个班级的择班生人数，超过了平均班级人数或平均班级人数+1，将出现错误；又或者含有“非择班生”的班级数小于2时，事实上是没有优化必要的（所谓“优化”，主要是针对不同班的“非择班生”的）。虽然，现实生活中，“择班”的是少数，比如一个班55人，择班的有那么3~5人，是正常的。但作为写程序，就必须考虑选择该班的学生人数，达到了55人或超过了55人时该怎么办，这样的防错代码还是必要的，至少在极端测试中有必要。

另外，由于该bug的发现，优化了产生两个随机班和两个随机学生的方法。之前由于两个随机班不能相同，第二个班有可能要反复随机几次，才能保证不同，效率有点低，但班的影响不大；可是随机学生在产生时，必须排除“择班生”，此时再反复随机，直到取到“非择班生”，则当择班生增多时，其实际抽取效率将极端低下。因此，本次更新中，采用了“kagawa经典数组洗牌法”由1循环到2和检测每班“非择班生”首次出现行号的办法，实现了精准随机，提高了随机的效率，是为“优化”。

aoe1981

更为极端的情况是：考虑n个班中，存在m个班被择班生占满(达到平均班级人数或平均班级人数+1)，则“随机优化”只能在剩余n-m个班中的“非择班生”中展开。此时，两个不同随机班的产生，是极有必要实现精准随机而非反复随机直到符合条件的，当n-m较小时，从1~n中随机产生符合条件的两个随机班时，效率也会变得极端低下。9楼谈到的更新就是解决了这个问题。