邯郸学步1之亦步亦趋：也做随机优化分班

aoe1981

　　前面我关于均衡分班主要发了两帖：“超1”和“超2”，第三帖是上两帖的总结帖，新东西不多。
　　今天，又挤出了点新东西，想发布为“超3”，但是忽然不自信了，又改了名……因为，一般来说，续集给人的感觉并不好……呵呵
　　这个“新东西”就是：随机优化分班，我用我的方式做了个，可以运行的。
　　这时，我又想起：“眼前有景道不得，崔颢题诗在上头”！法师已经做了随机优化分班了，我不自量力、不明就里、稀里糊涂又来了一个。
　　……
　　附件如下：
　　 随机优化分班研究之搜寻马航MH170.rar (36.09 KB, 下载次数: 119)

2014-8-7 17:10 上传

点击文件名下载附件

　　（11楼问题已纠正，附件已更新。2014.8.7　17：09）

　　原理、做法在后后几楼详述。

aoe1981

　　大家也许注意到我使用了类似“变1”、“变2”……这样的字眼，不只是为了赚取眼球，确有类似的感觉。
　　我也使用了“搜寻马航MH170”这样的字眼，也不只是为了赚取眼球，也是确有类似的感觉。

aoe1981

　　1.这个附件像目前以来搜寻马航一样的不可靠（以后一定会好的我坚信），所以不敢再用“超X”；
　　2.所以不可靠是因为我的附件对于寻找“方差最小方案”来说可谓是大海捞针、愚公移山。

aoe1981

　　首先解释下“方差”的计算：
　　各科理想平均分＝各科总分/总人数　　备注：我习惯性叫做“级平均分”，因为要分班的学生总数就是一级的人数。
　　各班各科平均分＝各班各科总分/各班总人数　　备注：我习惯性叫做“班平均分”。
　　设有n个班m科，则方差是：
　　∑∑（各班各科平均分ij－各科理想平均分j）^2
　　下标i：对应第一个求和符号，取值为1～n；
　　下标j：对应第二个求和符号，取值为1～m。

aoe1981

　　何谓“大海捞针”？
　　设共有h名要分班的学生，让这h名学生站成一排，反复做全排列，则共有h!种；
　　对于每一种可能的排列，从1号开始，到h号等距截取n个班的学生，就是一种分班，且人数首先保证均衡了。当然余数也要平均分配，不能空缺到最后一个班。我的做法是把余数从第1班开始，每班1人，往后分，直到分完。
　　这时，您感觉到了吗？h!就是大海！
　　Excel中最大能够计算的阶乘是=FACT(170)，照这样说，才是总人数170人！您说现实中，一级学生动辄数千都是有可能的，更别说是170人！那么，可以想到，这个总人数的全排列该有多么地大，难道不是“大海”吗？
　　再说捞针。前述方差最小的方案，我想只有一个，或者是相等的不多几个，这个概率是如此的小，要找到谈何容易！

aoe1981

　　关于“捞针”的效率，上个图：
　　
　　备注：这个是在170名学生数的基础上测试的。

aoe1981

　　看了上图，我们可能感觉普通家用计算机也是很给力的，这是时代的进步！
　　但是我依然不自信，因为这个随机的方式是有缺点的：
　　假设学生总数的全排列是1000万，那么直接随机运行来个1000万次或者来上100次10万次是否就能遍历了呢？
　　答案是：很不幸，这是不大可能的……
　　为什么？
　　因为在后来出现的随机方案中很可能包括前面已经随机产生并测试过的方案，该随机方案中包括重复测试！而且这种重复的可能性在随机测试次数的逐步增大中，越来越大！

aoe1981

　　我没有根本性的规避和解决办法，但是好在我的代码可以做到“愚公移山”！
　　什么是“愚公移山”？
　　就是干一点，有一点的效果，这个效果不会被清零！
　　当您运行10万次随机后，这时已经找到了一个“方差次优方案”，这个方案会被储存下来，并最终输出到工作表中……
　　下次当您在来个随机10万次时，会在上次的基础上进行再比较、再寻优……
　　您会有所感觉：“替换较小方差状态”的次数会越来越少，总体上而言！

aoe1981

　　再上一个代码运行中的消息框截图：
　　
　　可见，随机10000次，能够找到并替换掉的“方差次优方案”仅为12次，当下一次再来10000次时，可能更少了，依次类推！

aoe1981

　　关于附件中代码运行的步骤说明：
　　1.在工作表“分班信息”中相应单元格里选择“班级数”；
　　2.点击按钮“生成分表”；
　　3.在工作表“分班信息”中点击微调按钮，调整相应单元格里随机次数，或者手动输入；
　　4.点击按钮“随机优化”；
　　5.点击按钮“分段统计”。
　　对于不按上述操作步骤进行的，不排除会发生部分目前未预见的错误。
　　不过，完成上述步骤2之后，步骤3、4可以循环进行。