行业互联网,云计算|双榜首！华为云擎天架构刷新进化计算大赛新纪录
在刚刚结束的GECCO 2020国际会议中 ， 华为云擎天架构的调度算法团队同时获得OCP与USCP运筹优化算法赛道第一名 ， 且算法运行结果刷新了十个文献算例的已知最好结果 。充分展现华为云在云资源调度、多目标优化等领域的技术积累 ， 更为解决云上超大规模离散优化问题提供全新思路 。
文章图片
文章图片
获奖证书
GECCO会议始办于1999年 ， 是进化计算领域最重要的盛会之一 。本届比赛吸引了来自英国、法国等全球知名研究机构和顶尖学者 ， 如法国的优化解决方案提供商Artelys（ROADEF Challenge 2018冠军） ， 法国格勒诺布尔大学 ， 英国伦敦大学学院等 。华为云擎天架构的调度算法团队与华中科技大学吕志鹏教授团队 ， 针对“面向云的高性能求解器”进行深度技术合作 ， 并将设计的Weighting-Based Parallel Local Search（WPLS）算法应用于本次比赛 ， 实现在邻域设计、邻域快速评估机制、邻域解选择策略、并行化加速等方面的多项突破 ， 方案全场景领先第二名10% 。
挑战超过宇宙原子数量总和搜索空间
计算机科学中的“进化计算” ， 指一系列“受生物进化启发的全局优化算法” ， 及研究此类算法的人工智能等子领域 ， 主要应用于最优化问题的求解 。而OCP（Optimal Camera Placement ， 最优摄像头部署问题）与USCP（Unicost Set Covering Problem ， 单成本集合覆盖问题）作为经典的离散优化问题 ， 是已被证明的NP-Hard问题 ， 其中USCP更是Karp提出的21个NP-Complete问题之一 ， 在计算复杂性理论研究方面具有重要意义 ， 并被广泛应用于边缘站点选址、软件模糊测试等实际工业场景中 。
OCP问题可以简单描述为：假定一个城市需要部署一组摄像头进行监控全覆盖 ， 而每个摄像头部署的位置（400万个可选位置）、角度及可覆盖的监控区域都不尽相同 ， 如何使用最少的摄像头实现城市监控的全覆盖 。USCP问题则是采用更为抽象的数学集合形式进行描述 ， 二者本质相同 。
文章图片
文章图片
OCP问题示意图
此次比赛提供了基于实际的城市监控布局转换而来的数据集合 ， 其中最大的数据包含了380万以上的监控候选位置 。要从380万个候选位置中选出最优的布局方案 ， 搜索空间高达
， 该数字远远超过宇宙中所有原子的数量总和 ， 即使动用全世界的算力 ， 也无法在有限时间内逐一验证每一种方案的优劣 。
文章图片
文章图片
庞大搜索空间 ， 大幅提升赛题难度
透过现象看本质
【行业互联网,云计算|双榜首！华为云擎天架构刷新进化计算大赛新纪录】云上实践与算法理论的绝佳融合
AI、5G等技术的蓬勃发展 ， 催生应用对海量算力、极致时延体验等更高要求 ， 而云计算作为数字经济时代的核心生产工具 ， 正逐步向边缘延伸 ， 以满足澎湃算力的随时、随地、随需获取并实现业务的就近接入 。现实的挑战是 ， 如何进行海量边缘站点选址、规划各站点容量 ， 并通过智能全域调度实现全局业务接入体验最优 ， 其本质也可以抽象为以集合覆盖问题为核心的一系列优化问题 。例如 ， 云站点选址可抽象描述为：
云服务商拟在全国范围内部署海量站点以实现接入全覆盖 ， 满足客户的业务需求 。调研筛选出大量备选站点 ， 但因时延、服务质量、实际环境等约束 ， 每个站点可以覆盖的区域有限 。已知各站点可覆盖区域及对应建站成本 ， 要求给出可实现全覆盖的最优站点部署方案 。
推荐阅读
- 互联网|上线半年收获6700万用户，这款聚焦下沉用户的陌生人社交APP是怎么做到的？
- 互联网|5G商用一周年，华为云向互联网企业大抛绣球
- 互联网|中台产品经理实战(14)：中台与SaaS、微服务关系
- 互联网|行业观察 | 你所不知道的5G消息
- 互联网|多名知名人物推特被黑，拜登奥巴马都“中招”，比尔盖茨也在其内
- 互联网|发放高利贷，还要窃取用户信息？这些金融APP在秀“道德底线”
- 互联网|东莞先知：数字智能，先觉“先知”
- 云计算|从互联网到AI崛起，上海能弯道超车吗？
- 行业互联网,5G|江苏有线顺利完成园区5G信号开通测试
- 行业互联网,AI人工智能|城市教育大脑以“ AI+ 大数据”为核心 , 引领教育变革