在剛剛結(jié)束的GECCO 2020國際會議中，華為云擎天架構(gòu)的調(diào)度算法團(tuán)隊(duì)同時獲得OCP與USCP運(yùn)籌優(yōu)化算法賽道第一名，且算法運(yùn)行結(jié)果刷新了十個文獻(xiàn)算例的已知最好結(jié)果。

　　這充分展現(xiàn)華為云在云資源調(diào)度、多目標(biāo)優(yōu)化等領(lǐng)域的技術(shù)積累，更為解決云上超大規(guī)模離散優(yōu)化問題提供全新思路。

　　獲獎證書

　　GECCO會議始辦于1999年，是進(jìn)化計(jì)算領(lǐng)域最重要的盛會之一。本屆比賽吸引了來自英國、法國等全球知名研究機(jī)構(gòu)和頂尖學(xué)者，如法國的優(yōu)化解決方案提供商Artelys（ROADEF Challenge 2018冠軍）、法國格勒諾布爾大學(xué)、英國倫敦大學(xué)學(xué)院等。

　　華為云擎天架構(gòu)的調(diào)度算法團(tuán)隊(duì)與華中科技大學(xué)呂志鵬教授團(tuán)隊(duì)，針對“面向云的高性能求解器”進(jìn)行深度技術(shù)合作，并將設(shè)計(jì)的Weighting-Based Parallel Local Search（WPLS）算法應(yīng)用于本次比賽，實(shí)現(xiàn)在鄰域設(shè)計(jì)、鄰域快速評估機(jī)制、鄰域解選擇策略、并行化加速等方面的多項(xiàng)突破，方案全場景領(lǐng)先第二名10%。

　　計(jì)算機(jī)科學(xué)中的“進(jìn)化計(jì)算”，指一系列“受生物進(jìn)化啟發(fā)的全局優(yōu)化算法”，及研究此類算法的人工智能等子領(lǐng)域，主要應(yīng)用于最優(yōu)化問題的求解。

　　而OCP（Optimal Camera Placement，最優(yōu)攝像頭部署問題）與USCP（Unicost Set Covering Problem，單成本集合覆蓋問題）作為經(jīng)典的離散優(yōu)化問題，是已被證明的NP-Hard問題，其中USCP更是Karp提出的21個NP-Complete問題之一，在計(jì)算復(fù)雜性理論研究方面具有重要意義，并被廣泛應(yīng)用于邊緣站點(diǎn)選址、軟件模糊測試等實(shí)際工業(yè)場景中。

　　“假定一個城市需要部署一組攝像頭進(jìn)行監(jiān)控全覆蓋，而每個攝像頭部署的位置（400萬個可選位置）、角度及可覆蓋的監(jiān)控區(qū)域都不盡相同，如何使用最少的攝像頭實(shí)現(xiàn)城市監(jiān)控的全覆蓋。USCP問題則是采用更為抽象的數(shù)學(xué)集合形式進(jìn)行描述，二者本質(zhì)相同。

　　OCP問題示意圖

　　此次比賽提供了基于實(shí)際的城市監(jiān)控布局轉(zhuǎn)換而來的數(shù)據(jù)集合，其中最大的數(shù)據(jù)包含了380萬以上的監(jiān)控候選位置。

　　要從380萬個候選位置中選出最優(yōu)的布局方案，搜索空間高達(dá)，該數(shù)字遠(yuǎn)遠(yuǎn)超過宇宙中所有原子的數(shù)量總和，即使動用全世界的算力，也無法在有限時間內(nèi)逐一驗(yàn)證每一種方案的優(yōu)劣。

　　龐大搜索空間，大幅提升賽題難度

　　AI、5G等技術(shù)的蓬勃發(fā)展，催生應(yīng)用對海量算力、極致時延體驗(yàn)等更高要求，而云計(jì)算作為數(shù)字經(jīng)濟(jì)時代的核心生產(chǎn)工具，正逐步向邊緣延伸，以滿足澎湃算力的隨時、隨地、隨需獲取并實(shí)現(xiàn)業(yè)務(wù)的就近接入�，F(xiàn)實(shí)的挑戰(zhàn)是，如何進(jìn)行海量邊緣站點(diǎn)選址、規(guī)劃各站點(diǎn)容量，并通過智能全域調(diào)度實(shí)現(xiàn)全局業(yè)務(wù)接入體驗(yàn)最優(yōu)，其本質(zhì)也可以抽象為以集合覆蓋問題為核心的一系列優(yōu)化問題。例如，云站點(diǎn)選址可抽象描述為：

　　云服務(wù)商擬在全國范圍內(nèi)部署海量站點(diǎn)以實(shí)現(xiàn)接入全覆蓋，滿足客戶的業(yè)務(wù)需求。調(diào)研篩選出大量備選站點(diǎn)，但因時延、服務(wù)質(zhì)量、實(shí)際環(huán)境等約束，每個站點(diǎn)可以覆蓋的區(qū)域有限。已知各站點(diǎn)可覆蓋區(qū)域及對應(yīng)建站成本，要求給出可實(shí)現(xiàn)全覆蓋的最優(yōu)站點(diǎn)部署方案。

　　憑借華為云擎天架構(gòu)調(diào)度算法團(tuán)隊(duì)在云資源規(guī)劃、調(diào)度領(lǐng)域的持續(xù)探索實(shí)踐，本次比賽提交的Weighting-Based Parallel Local Search（WPLS）算法同時結(jié)合了機(jī)器學(xué)習(xí)與運(yùn)籌優(yōu)化中的技巧，在局部搜索的過程中使用了禁忌表策略，并且自學(xué)習(xí)地調(diào)整評估函數(shù)來跳出局部最優(yōu)。

　　在實(shí)現(xiàn)上，該算法借助于華為云鯤鵬和昇騰實(shí)例的獨(dú)特硬件優(yōu)勢和特點(diǎn)，最大程度地發(fā)揮了算法的并行化加速能力，使用極短的時間就能找到接近于理論最優(yōu)解的方案，做到云上實(shí)踐與算法理論的絕佳融合。

　　歷經(jīng)8年技術(shù)積淀的華為云擎天架構(gòu)，通過對極簡數(shù)據(jù)中心、專用硬件、虛擬化、云操作系統(tǒng)等全棧技術(shù)投入，提供硬核性能、極致穩(wěn)定、極優(yōu)效能、云邊端協(xié)同的云服務(wù)，為華為云、華為云Stack、華為云邊緣提供一致體驗(yàn)與一致生態(tài)。

　　“智慧云腦”作為華為云擎天架構(gòu)的管控面，是面向云、AI、5G時代的分布式云操作系統(tǒng)，實(shí)現(xiàn)全域資源供給極優(yōu)、多樣性算力使用極簡。

　　其中，全域資源調(diào)度能力可支撐未來10萬級分布式站點(diǎn)間復(fù)雜的調(diào)度協(xié)同，完成中心與邊緣、邊緣與邊緣之間的智能按需調(diào)度，根據(jù)業(yè)務(wù)訴求匹配最優(yōu)節(jié)點(diǎn)，實(shí)現(xiàn)就近接入。面向租戶，智慧云腦通過資源畫像及預(yù)測算法實(shí)現(xiàn)算力的智能推薦，讓應(yīng)用負(fù)載運(yùn)行在最合適的算力之上。

　　未來，華為云將繼續(xù)發(fā)揮全棧技術(shù)創(chuàng)新能力，與伙伴一起使能千行百業(yè)，助力政企實(shí)現(xiàn)數(shù)字化轉(zhuǎn)型和智能化升級。