2017华为精英挑战赛部分思路与总结

今天是华为经验挑战赛的最后一天,也是完结的一天,很遗憾没能进入复赛,以此记录自己这一阵子的付出,来年再战!

 

3.16 上传了第一份代码,代码没有几行,直接连接服务器,但是连续提交若干次都是0分,感觉很无语,对华为官网的判卷系统鄙视一番,而且连官方文档给的说明都是错的233。

最后终于瞎捣鼓出来目录格式,提交成功,很开心!


3.22 学习最小费用最大流,完成遗传算法的变异操作,交叉和选择没写,在更新测试用例后居然排在第6名!怀疑榜上的人可能是没有限制时间导致没有分数,忘记截图真的可惜

 


3.25 终于编完了遗传算法的交叉和选择算子,但是效果极差!比直连服务器还要糟糕,苦思冥想不知所措。意外发现群里人说自己的最小费用最大流算法只需要50ms,而自己一轮运算需要200ms以上,效率差4倍,于是一点点更改底层数据结构,终于使成本低于直连服务器


3.26 忽然发现一种神奇的方法,在初始种群前,先直连服务器,然后尝试一个一个删掉服务器,看看成本有没有降低,发现删完以后成本大大降低,比GA迭代以后结果好不知道哪去,干脆直接就这么提交了,初级和中级样例在经过这种预处理后能降低成本大约100~1000,高级没动静,但至少也算提高,勉强排在前30


 

3.31 更新为正式用例,此次更新大大提高了服务器成本。之前排名从30+调到60+,更新后又回到30+,对前面Dalao用的方法很好奇,而且基本上计算时间都很短,设想是不是有其他方法,不用启发式算法,但是依然没有头绪,盲目调参中。


 

4.4 事情一直不断,又是改卷子,又是做工程的= =弄得心情很烦躁,再加上努力应付学期作业,算法一直没有改进,期间尝试了退火算法以及同学的粒子群算法,效果都不好,无奈。更悲催的是,在3号早上猛然发现自己的最小费用最大流求错了。。。。。。。。。

简直晴天霹雳,3-4号花了2整天时间改费用流,成功的陷入BUG循环无法自拔,遂放弃,另想办法改遗传算法。求得是一个贪心费用流就无所谓了,至少能跑出结果,最后两天看能不能再提高提高。


4.5 终于到了最后一天了,也是才想起来更改初始化策略,对初中高三个样例连续运行若干小时,制定了初始化策略,提高了迭代次数,使成绩有小幅提升,但是杯水车薪,与已知的最好解27562、68894、198034相差甚远。最终没能爬上排行榜,结束了两个星期的战斗。


 

总结:

没能进复赛还是很难过的,毕竟花费了很多时间精力在里面,这让我想起上学期即使在那么多课程作业的情况下,依然顶着压力做CCF的竞赛。上学期几乎花去了所有课余时间做CCF,但是时间零碎,再加上对数据挖掘概念都不是很懂,光看了几篇csdn的文章就开始闷头瞎搞,结果也是没能进复赛。

这一次吸取上次的教训,先是在网上收集相关论文回来看,然后动手开始实践。粗略一数大约30篇论文看过,实际上都没有太大帮助。不得不说,国内的很多水文让人看了哭笑不得= =。理论上很美好的东西,实际拿来用几乎都是极差的效果,需要依据实际情况反复调整,最后才能有好的结果。

 

技术路线:

1.最大匹配+最短路径,这个想法是在看到题目第一时间想到的。先从用户出发,全部设立服务器,即此时服务器为A1,A2,A3,A4…An,存放在集合S,从S中取出距离最短的两个服务器Ai、Aj,尝试将他们合并,合并的位置为Ai-Aj路径上的某一点(可能要穷举这条路径上的所有点),合并成功则更新集合S,以此往复。

但是这种方法还没尝试就放弃了,考虑最大匹配难求以及合并问题,每一次都如此求得最短路径并穷举节点合并,合并后减去路上流量再次对集合求一个匹配合并,时间复杂度很高也难以实现。

2.双染色体的遗传算法,这种想法参考《改进遗传算法及其在物流配送中心选址优化的应用》,即我们所求的问题分为两部分,一个是选址问题,还有一个是选址后如何分流量的问题。这篇论文的思想是,选址使用遗传算法01编码(即所有的网络节点组成染色体A,染色体每一位基因有值0或1,0表示不放置服务器,1表示放服务器),分配流量也使用遗传算法整形编码(即若染色体A的每一位基因对应染色体B的N位基因,N表示消费者数量。比如用户数1,节点数3,A编码为010,B编码为{(000),(020),(000},这代表第2个网络节点提供给第2个用户资源为2)设置服务器和服务器分配资源都是随机的,通过遗传算法迭代改进。

这种方法让我豁然开朗,想不到居然还能这么算,将两个问题合二为一变成一个问题,简直神奇。然而,其实也应该能想到,对于这次竞赛的图来说约束条件太多,全部随机设置导致最终结果在10000个个体中只有不到30个个体有解,不用说最优解,局部最优都不可能找到。洋洋洒洒的1000+行代码没想清楚就白写了

3.单染色体的遗传算法+最小费用最大流,因为全随机效果很差,又从竞赛群中听来最小费用最大流,能在已知服务器的情况下求得服务器到用户的流量分配方案,这样相当于解决了一个问题,将问题完全变成了选址问题。

这种方法也是用到了最后,但可惜对费用流理解有误,求出的是一个贪心流,不是最优解,这可能导致了最后提交跳过最优解的情况,这是问题之一。另外对遗传算法不能完全按照随机初始种群的方法,这种方法最终得到的局部最优解固然不错但是迭代速度奇慢无比,所以后来我有尝试先遍历服务器尝试删除的方法初始化种群,这样能大大加快迭代速度。

4.K-中心聚类,大致思路为将距离较近的用户划为一类,如果能在这一类用户中找到一个点作为服务器,那么这个解就是较优解

因为对K中心不熟,加之后来事情太多,结果没心思做研究了,包括蚁群算法和拉格朗日松弛法都没能耐心看下去,如果来年再战有机会再次学习。

5.剪枝,虽然只用了一天时间做研究,但是发现种群的初始化是极其重要的,这一点恐怕不仅是遗传算法,其他启发式算法也是如此。通过长时间迭代后,将得到的局部最优解的信息统计,得到节点-服务器设立关系表

观察发现所有中级的较优解有95%以上在用户直连的节点上架设服务器,而100%的初级用例将服务器架设在直连点上,高级用例大约为85%以上。这样对初级和中级完全只用遍历直连点,相当于减少了超过一半的搜索空间,事实证明最后得到了更好的结果。而不管初中高,统计他们临边数、临近用户数等信息,可以制定一个策略,在随机时避免一些不可能作为服务器的点被随机选为服务器,这也是最后成绩能有小幅提高的原因。所以以后无论做什么研究,都离不开对数据的分析,这一点毋庸置疑。

 

最后的最后,算是前前后后忙活了两个星期,小有收获,但没能进复赛还是硬伤,又一次对自己实力产生了怀疑,单打独斗这些比赛真的很累。本想给自己休个假,不过好像老板们又有新的任务了╰( ̄▽ ̄)╭看来只能先浪上两天,然后重新投入工作。下一届,一定要再战一次!

发布者

VC-Robot

游戏爱好者,动漫迷,C++修炼中,编程菜鸟,随性

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据