2018华为软件精英挑战赛总结（一）：贪心+遗传分配

欢迎点击「算法与编程之美」↑关注我们！

| 本文转载：

| 作者：胜

| 主页：http://sheng-blog.cn/

趁着五一放假不用上班，整理了一下比赛的代码。从3月22号动手写第一版代码到4月27号的决赛，断断续续用了一个多月的午休和熬夜，最后很遗憾败给了自己的心态，现场的一个小bug就击溃了我，最终和四强失之交臂，大概还是得失心太重，总想着那会要是镇静下来仔细思考一下就好了。

不过，总的来说也是收获了很多，过程中和各路大佬交流切磋，受益匪浅。这其中特别要感谢京津东北的小幽灵战队，初赛时一句对于滤波思路的提醒，只改了几行代码就让我坐稳了冠军的位置。还有本校非合作信号与信息处理团队的扯蛋兄复赛正式赛前一天分享的更优雅的滤波思路，很遗憾最终没能发挥威力。还有Hotpot的杨超一直保持着沟通交流，其他还有MCC,重大的典哥，重邮的狼牙啊等等。对了，还要感谢华为的徐超老师答疑解惑，忙前忙后，打榜的过程还是挺有乐趣的。

毕竟一个多月的午休和熬夜时间，尤其是初赛正赛前一天晚上，提交完最后一版代码后通宵赶工第二天要在组会上讲的项目介绍PPT，早上七点多做完最后一页，简单备了下讲稿，然后9点半左右上去讲了半小时。那天大概是讲过最差的一次PPT了，幸亏导师并没有发现异样~言归正传，决定总结一波。暂时先开源矩阵运算库和分配算法部分，两个代码仓库如下，矩阵库基于模板来写的，还是挺好用的，分配部分算法在虚拟机数量不是特别少的情况下，不用trick也能稳定保持0.97+的利用率。其他部分的代码和思路还是等决赛结束后再说吧。

• 基于模板的C++矩阵运算库

• 复赛的分配代码:贪心算法+遗传优化

问题描述

由于租户对ECS实例(虚拟机,VM)请求的行为具有一定规律,可以通过对历史ECS实例请求的分析,预测到未来一段时间的ECS实例请求,然后对预测的请求分配资源(如下图所示),这样可以找到一个接近最优的分配策略,实现资源最大化利用,同时也能参考预测的结果制定云数据中心的建设计划。复赛赛题中存在通用型(General)、计算加强型(High-Performance)和内存加强型(Large-Memory)这三种规格的物理主机，且需同时考虑cpu利用率及内存利用率。显然，这是一个多箱型装箱问题。

基于群体编码的遗传算法解多箱型装箱问题

对于装箱问题，根据基因编码方式不同，可分为基于箱子编码方式的遗传算法、基于物品编码方式的遗传算法、基于群体编码方式的遗传算法。参考资料1论证了基于群体编码方式的遗传算法是三者中最优的方法。

基于群体编码的染色体结构

基因的位置表示箱子，基因的值表示该箱子中放入的所有物品。染色体的长度为箱子的个数。如，有 8 个物品要装箱，则可能的染色体有{(1，2)，(3，4，5)，(6)，(7，8)}、{(1，2，6)，(4，5，8)，(7)}等。其中后一条染色体表示：1号物品、2号物品和 6 号物品放入箱子 1，4 号物品、5 号物品和 8 号物品放入箱子 2，7 号物品放入箱子 3。

种群初始化：贪心算法

思路很简单，将所预测得到的虚拟机进行唯一编码，然后随机打乱顺序，从头到尾顺序贪心地用三种箱子进行装填，当按顺序的下一个虚拟机无法装入时，则遍历剩下的虚拟机直到无法装入任何已有的虚拟机，然后选中利用率最大的箱子，接下来抛开这个箱子以及里面已装填的虚拟机，重复上述过程。因此，对于虚拟机的每一个排列，都会有一个贪心解与之对应。

适应值函数

根据参考资料1，此处选用每个箱子资源利用率的平方和然后再除以箱子数作为适应值，适应值越大越好，公式这里就懒得敲了。代码里很清楚。

自然选择

首先记录最优个体，如果当前群体中的最优个体比记录个体更优，则更新记录，如果更差，则用记录的最优个体替换掉种群中当前最优个体，总的来说就是一直保留最优个体。

交叉

对种群中相邻的两个个体，按照交叉概率，如果发生交叉，采用双亲双子交叉算子，交叉过程如下所述，如下图所示。

• 步骤1 从两个父代中各随机选择两个交叉位置，从而对每个父代选定交叉部分。

• 步骤2 将第1个父代交叉部分的内容插入到第2个父代第1个交叉位置之前。由于交叉对染色体的部分群体进行操作，这就意味着从第1个父代插入一些群体(箱子)到第2个父代中。

• 步骤3 从产生的后代中，去掉所有装有重复出现的物品的箱子，并使得这些物品原先的从属关系让位于“新”插入的箱子。如果有消失的箱子，则用贪心算法首先在已有的箱子中执行放入，对于剩下放不下的，依旧使用贪心算法选择开启利用率最大的新箱子执行放入。

• 步骤4 改变两个父代的角色并重新应用第2步到第3步生成第2个子代。

• 

变异

变异的策略为按照变异概率随机消除一个已经使用的箱子。消除的箱子中的物品用上述步骤3方法插入染色体中。

参考资料

• [1]张大斌,刘桂琴,王婧,朱侯.基于群体编码方式的遗传算法求解装箱问题[J].计算机工程与设计,2008(12):3154-3156.

• [2]张雅舰,刘勇,谢松江.一种求解装箱问题的改进遗传算法[J].控制工程,2016,23(03):327-331.

更多精彩文章：