2017华为软件精英挑战赛总结

作者: 云中布衣   分类:  生活随笔    热度: (680℃)   时间: 2017-5-3 15:00   标签: #比赛心得    

距离2017华为软件精英挑战赛初赛结束已经快一个月了,是时候总结一波了,再不总结就真的忘记了,根据艾宾浩斯记忆曲线估计我已经忘得差不多了。

从3月20日和小耿组队开始到4月5日初赛结束,整整15天时间里一直处于一个看论文,写程序,调模型的过程。

从零开始构建解决问题的模型以及程序的实现,不断的调参看论文,想法子改进,着实让我学到了很多在实验室学不到的东西,于是就想等闲下来好好的总结一下。

这次比赛的题目为大视频时代.布局,可以概括为图的最小费用最大流(多源多汇)+设施选址的问题。简单的来说就是在网络节点中选择某些节点放置服务器,在满足所有用户消费流量需求的情况下,使得产生的费用最小?

其中:total_cost(总的费用)=server_cost(服务器建设费用)+(bandwidth_cost)宽带租用费用

比赛的详细信息可以访问这个页面:http://codecraft.huawei.com/home/detail

点击查看原图

上面的结论现在说出来很简单,但第一次看到题目的时候,我可是一脸懵逼,这讲得啥啊,心中一万只草泥马在奔腾,要不不做了?就这么认怂了~当晚和小耿同学通电话,说题目我看不懂啊,实验室还得干活之类的。

结果小耿同学不干了,说她实验室的师弟(天津大学精密仪器专业的)得分了,而且还进京津东北区域64强了,这也就算了,关键她还在实验室说和我组队了说让我带她。我艹,这……我竟无言以对。

于是我就问自己,你一个计算机科班出身的(姑且算吧,毕竟本科学了三年计算机,一年物理)难道还比不过一个学精密仪器的,这不科学啊,虽然知道自己很菜,但也不至于菜到这个地步吧。

管它三七二十几,背上小白就泡自习室了,硬着头皮,认认真真的再次读题,一遍不够再来一遍,一边读一边画~

咦!好像有些思路了,这个不就是图算法中多源多汇的费用流模型么?以服务器为源点,以消费节点尾汇点,求算图中给定需求流量的情况下的最小费用~

第二天背着小白和圣经《算法导论》又去泡自自习室了~

打开《算法导论》翻到图那一章就是一顿啃,从图的存储啃到图的遍历,从最短路径啃到费用流,啃的我牙的都疼了(是真的疼了,智齿发炎了)

无奈啊,谁让我读研以后,就很少啃算法导论了,搞了一年多的python,准备献身于人工智能,奈何发现搞不过人家学数学的~

当我啃到,最小费用最大流算法的时候,眼前一亮,就它了,撸起袖子就是干~

眼下需要解决两个问题:图的存储与最短路径算法~

图的存储由邻接矩阵和邻接表,考虑到网络的规模未知,决定采用邻接表的存储方式~

至于最短路径算法算法导论中介绍了Dijkstra,Bellman_Ford,二者都是解决带权重有向图上的单源最短路径问题,但是如果实现方法合适Dijkstra算法在时间上要优于Bellman_Ford算法(这里要注意下,Dijkstra不能解决负权边,这里是个坑,我就踩进去了)

毫无疑问,最短路径算法当然选择Dijkstra算法~

选择好了图的存储结构和最短路径算法,再结合最大流算法便开始写程序了,照着算法导论上伪代码,结合自己的理解,边写边调。

越写越不对劲,感觉自己入坑了,跑一遍最小路径算法,再把路径上的边的容量减去路径的流量,并把其反向边加上路径的流量,直到满足所有消费节点的流量需求则停止算法,此时得到的费用就是最小费用。

问题来了,这减法,减着减着就可能是负的啊,大哥,负边迪杰斯特拉算法处理不了啊,这是常识,瞬间感觉自己好傻逼~

每当有困难的时候,Google总是能帮你解决问题!

于是我就Google了一下,最短路径解决负权边的算法?

惊喜的找到了spfa算法,它是Bellman-ford算法的一种队列优化,效率比起Bellman_ford有很大的改观,而且还能处理负边,就它了~

由于spfa是求单源最短路径的一种算法,而赛题中是一个多源多汇的问题,根据算法导论中的建议,分别建立超级源点S和超级汇点T,将多源多汇问题转化为单源单汇问题。为了方便起见,直接将服务器放在消费节点的旁边,这样费用虽然高些,但是可以保证满足消费需求~

暂时不去考虑服务器选址的问题,虽说赛题的主要难点就是在设施选址,但万丈高楼平地起嘛,咱这先把地基打牢~

根据上述策略很顺利完成了第一版程序,本地测试也通过了,开心的提交了程序~

20分钟过后~(4月1号之前,每次判题需要20分钟出结果)

妈的,0分,什么意思嘛,本地测试好好的啊,于是跑到讨论区灌水去了,对照零分的帖子一个一个的对,发现输出格式有问题,仔细调了调再提交了下~

20分钟过后~

哈哈哈哈,19.2分,143名,终于得分了,心中还是蛮开心的~(满分100分,评分的规则是共三个测试用例,节点规模由小到大,50、300、800,按照费用的排名,分别计算得分,三个用例的权重是0.2、0.3、0.5)


地基打好了,开始盖楼了!

上群里灌灌水,发现大家都是卡在选址的问题上,选址问题才是这次比赛真正需要需要解决的问题,也就是说前面那些都是打基础啊~

吓的我赶紧喝了口水,压压惊,打电话给小耿同学问问她有啥好的建议,讨论无果。

很显然嘛,啥论文也没看,本身设施选址这个问题都没搞清楚,就两个愣头青这么讨论下,能讨论出什么惊天动地的算法出来才怪呢!不过得出的结论倒是中肯,去看论文,看看前人都怎么做的,能不能吸取下经验。当务之急是先把设施选址这个问题搞清楚~


于是就打开知网,搜索设施选址,下了几篇硕士论文、博士论文以及一些期刊论文。文件夹中便多了下面几个文件:

设施选址中的一些模型与算法(吴仆).caj

设施选址问题的研究与应用(朱泓丞).caj

基于模拟退火算法的逆向物流网络设计与研究.pdf

......

接下来的一天时间里,就是蒙头看论文。

了解了什么设施选址问题?简单的说在网络中放置设置,可以是物流网络放置仓库,城市网络建设工厂,路由网络放置服务器~

选址问题根据设置允许放置设置的空间,可以分为连续选址和离散选址。选址研究中的典型问题如Weber问题、中位问题、覆盖问题、中心问题、多目标选址、竞争选址、不受欢迎的设施选址、选址分配……

研究前人在解决设施选址问题中所提出的一些办法?重点关注了

粒子群算法(PSO)

遗传算法

模拟退火算法

神经网络算法

爬山算法

以上都是一些启发式算法,也是目前解决设置选址问题应用最多的一些算法,但这些基本的算法需要根据实际问题做相应的设计和改进,有时候可能需要多种算法融合才能达到好的效果。

其中粒子群算法是我比较熟悉的,高级人工智能课上有一次作业,是利用粒子群算法来求一个二次函数的最大最小值。

柿子要挑软的捏,那就先用粒子群算法吧,用粒子群去找最优的服务器放置位置。

我先简单的描述下粒子群算法吧:

粒子群算法全称粒子群优化算法(Particle Swarm Optimation, PSO),算法的第一步是初始化一群随机粒子(随机解,每一个粒子就是一个解),然后通过迭代找到最优解。

注:每一次迭代,先记录当前个体最优值p_best以及整个种群的最优值g_best,再根据更新公式更新粒子的速度v以及粒子的位置p,进入下一次迭代。

但是算法是这么描述的,可是该怎么与实际问题结合呢?

算法中每一个粒子代表一个解,可是服务器的选址中服务器的个数不确定,选哪个点也不确定,该怎么表示?原始的粒子的群算法貌似不好使,于是又开始查论文看论文,发现了一种二进制粒子群优化算法(Binary Particle Swarm Optimization)。主要用于离散的搜索空间,这不正是我想要的么?

认真的从论文中提取出了这个二进制粒子群优化算法,并实现之~

本地小规模的网络可以很快的找到最优解,但是中等规模,高等规模的测试用例,找不到最优解。中等规模的网络提前收敛于一个值,高等规模,由于限定时间为90s,所以无法收敛~

这就尴尬了,不是还是有点小激动,看到小规模网络可以秒出最优解,内心还是很开心的,于是就提交了咯~

20分钟后,出成绩了~

66分,61名,我擦,进64强了,要不要这样~哈哈哈哈哈~好开森~

后面由陆续在BPSO算法中加入了遗传特性,尝试了量子行为的粒子群算法,也试过了遗传算法,排名也陆续挺进到56名,期间有升有降,这里就不累述了~

所有的源码都已分享到了GitHub仓库里:http://github.com/52ai/CodeCraft


说说最后的成绩吧,我们的队伍名称是:两只菜鸟闯江湖,属于京津东北赛区。最好的成绩是京津东北赛区区域第56强,截图如下:

点击查看原图

尽管最后遗憾没能进复赛,但这个过程却让我收获良多。

首先是收获了实实在在的知识层面上的各种算法的学习与应用:spfa最短路径算法、最大流最小费用算法、粒子群算法、二进制粒子群算法、量子行为粒子群算法、遗传算法,模拟退火算法。

除了知识层面上的收获,我想最大的收获应该是内心的成长,它让我认识到了自己和大佬们之间的差距,明白了努力的人还是可以收获不一样的自己,但这个努力需要有策略的努力,有针对性的努力。有差距从来就不是问题,我们需要的是找到差距,缩小差距!

从第一次拿分的喜悦:

点击查看原图

到名次的不断攀升至进64强的期待:

点击查看原图

再到大佬们刷榜被挤出64强的彷徨:

点击查看原图

再到优化算法模型再次进入64强的淡定。

点击查看原图


每一次的提交每一次的期待,每一次的前进每一次的喜悦,每一次的跌落每一次的懊恼。已经很少这么全身心的投入到一件事情当中了,真的可以说是废寝忘食,疯狂读论文,调模型和小耿童鞋头脑风暴,经常一个人调模型,写程序到半夜,特别享受那个过程。非常感谢华为,在我离开校园的时候能够有这么一次难忘比赛经历,我也会借助这次比赛所收获一些东西,让自己成长起来。


2017年5月3日

云中布衣书于北京.怀柔

56.8K

评论:

云中布衣 Say:
欢迎常来逛逛啦~

2017-05-04 16:57


云中布衣 Say:
哈哈哈,还好啦,就是记个流水账,捋一捋加深下印象~

2017-05-04 16:57


上海网站公司 Say:
顶一下的啦。。。

2017-05-04 16:49


上海网站建设 Say:
总结的还是不错的哟。。。

2017-05-04 16:48


发表评论:

© 云中布衣 2015 | Driven by EMLOG  | SiteMap | RunTime: 9.76ms RSS  |   | 回到顶部

文章数量【230】 评论数量【156】 稳定运行【1031天】

Visitor IP Address【54.80.82.9】