写点什么

挑战 10 的 1,143,913 次方种算法组合:这都不是事儿!

发布于: 2020 年 07 月 21 日
挑战10的1,143,913次方种算法组合:这都不是事儿!

摘要:在GECCO 2020国际会议中,华为云擎天架构的调度算法团队获得OCP(Optimal Camera Placement最优相机布局)和USCP(Unicost Set Covering Problem单一成本集合覆盖问题)运筹优化算法赛道两项分赛道的冠军。



从2012年启动预研,2014年构建软硬协同系统,2017年应用于华为云... 历时8年时间打造的华为云擎天架构,究竟有多强悍,或许我们能从下面的内容中找到答案。



在刚刚结束的GECCO 2020国际会议中,华为云擎天架构的调度算法团队获得OCP(Optimal Camera Placement最优相机布局)和USCP(Unicost Set Covering Problem单一成本集合覆盖问题)运筹优化算法赛道两项分赛道的冠军。





超乎想象的顶级的会议



GECCO会议始办于1999年,是进化计算领域最重要的盛会之一。本届比赛吸引了来自英国、法国等全球知名研究机构和顶尖学者,如法国的优化解决方案提供商Artelys(工业优化领域旗舰竞赛ROADEF/EURO Challenge 2018年度冠军),英国兰卡斯特大学(ROADEF/EURO Challenge 2016年度冠军),法国格勒诺布尔大学,英国伦敦大学学院等,可谓是高手云集。



了解了会议的大概情况,我们再来看看这次比赛获奖赛道所需要解决的问题。



计算机科学中的“进化计算”,指一系列“受生物进化启发的全局优化算法”,及研究此类算法的人工智能等子领域,主要应用于最优化问题的求解。而OCP与USCP作为经典的离散优化问题,是已被证明的NP-Hard问题,其中USCP更是Karp提出的21个NP-Complete问题之一,在计算复杂性理论研究方面具有重要意义,并被广泛应用于边缘站点选址、软件模糊测试等实际工业场景中。



OCP问题可以简单描述为:假定一个城市需要部署一组摄像头进行监控全覆盖,而每个摄像头部署的位置(400万个可选位置)、角度及可覆盖的监控区域都不尽相同,如何使用最少的摄像头实现城市监控的全覆盖。USCP问题则是采用更为抽象的数学集合形式进行描述,二者本质相同。



OCP问题示意图



云上实践与算法理论碰撞



此次赛题提供了基于实际的城市监控布局转换而来的数据集合,其中最大的数据包含了380万以上的监控候选位置。要从380万个候选位置中选出最优的布局方案,搜索空间高达2^(3,800,000)≈〖10〗^(1,143,913),该数字远远超过宇宙中所有原子的数量总和,即使动用全世界的算力,也无法在有限时间内逐一验证每一种方案的优劣。





庞大搜索空间,大幅提升赛题难度



华为云擎天架构调度算法团队提交的Weighting-Based Parallel Local Search(WPLS)算法同时结合了机器学习与运筹优化中的技巧,在局部搜索的过程中使用了禁忌表策略,并且自学习地调整评估函数来跳出局部最优。在实现上,该算法同时借助于华为云鲲鹏和昇腾的独特硬件优势,不仅发挥出算法的并行化加速能力,还在极短的时间找到接近于理论最优解的方案。



针对如何从380万个候选位置中选出最优的布局的问题,核心问题就是如何进行海量边缘站点选址、规划各站点容量,并通过智能全域调度实现全局业务接入体验最优,其本质也可以抽象为以集合覆盖问题为核心的一系列优化问题。华为云团队提出了“云站点选址”的方案。拟在全国范围内部署海量站点,计算出因时延、服务质量、实际环境等约束带来的覆盖区域有限问题,计算出各站点可覆盖区域及对应建站成本,最终提出可实现全覆盖的最优站点部署方案。



不得不说,该解决方案得益于当前云技术已成为时代发展的重要推力。随着产业的发展,行业对海量算力、极致时延体验等都提出了更高要求。云计算作为数字经济时代的核心生产工具,正逐步向边缘延伸,以满足澎湃算力的随时、随地、随需获取并实现业务的就近接入。



面向未来 华为云擎天架构的全栈技术投入



历经8年技术积淀的华为云擎天架构,通过对极简数据中心、专用硬件、虚拟化、云操作系统等全栈技术投入,提供硬核性能、极致稳定、极优效能、云边端协同的云服务,为华为云、华为云Stack、华为云边缘提供一致体验与一致生态。



“智慧云脑”作为华为云擎天架构的管控面,是面向云、AI、5G时代的分布式云操作系统,实现全域资源供给极优、多样性算力使用极简。其中,全域资源调度能力可支撑未来10万级分布式站点间复杂的调度协同,完成中心与边缘、边缘与边缘之间的智能按需调度,根据业务诉求匹配最优节点,实现就近接入。面向租户,智慧云脑通过资源画像及预测算法实现算力的智能推荐,让应用负载运行在最合适的算力之上。



未来,华为云将继续发挥全栈技术创新能力,与伙伴一起使能千行百业,助力政企实现数字化转型和智能化升级。



点击关注,第一时间了解华为云新鲜技术~



发布于: 2020 年 07 月 21 日阅读数: 60
用户头像

提供全面深入的云计算技术干货 2020.07.14 加入

华为云开发者社区,提供全面深入的云计算前景分析、丰富的技术干货、程序样例,分享华为云前沿资讯动态,方便开发者快速成长与发展,欢迎提问、互动,多方位了解云计算! 传送门:https://bbs.huaweicloud.com/

评论

发布
暂无评论
挑战10的1,143,913次方种算法组合:这都不是事儿!