《華為研究：軟件吞噬一切，開源吞噬軟件（2022）（151頁）.pdf》由會員分享，可在線閱讀，更多相關《華為研究：軟件吞噬一切，開源吞噬軟件（2022）（151頁）.pdf（151頁珍藏版）》請在三個皮匠報告上搜索。

1、華為技術有限公司深圳市龍崗區坂田華為總部辦公樓電話：+86 755 28780808郵編：518129免責聲明本資料可能含有預測信息，包括但不限于有關未來的財務、運營、產品系列、新技術等信息。由于實踐中存在很多不確定因素，可能導致實際結果與預測信息有很大的差別。因此，本資料信息僅供參考，不構成任何要約或承諾，華為不對您在本資料基礎上做出的任何行為承擔責任。華為可能不經通知修改上述信息，恕不另行通知。版權所有 2022 華為技術有限公司，保留一切權利。非經華為技術有限公司書面同意，任何單位和個人不得擅自摘抄、復制本資料內容的部分或全部，并不得以任何形式傳播。商標聲明 和 是華為技術有限公司商標或

2、者注冊商標，在本資料中以及本資料描述的產品中，出現的其它商標、產品名稱、服務名稱以及公司名稱，由其各自的所有人擁有。、操作系統演進：歷史、現在與展望 第1頁MindSpore：人工智能開源生態系統實踐 第18頁技術使能藝術：新一代HDR Vivid視頻技術標準 第122頁2022年12月第 3 期（總第3期）內部資料 免費交流準印證號：（粵BL）022060040Communications of HUAWEI RESEARCH華為研究內部資料，免費交流準印證號：（粵BL）022060040主編：廖恒本期責任主編：陳海波，陸品燕編委會：廖恒，童文，肖新華，胡邦紅，周慧慧，鮑豐，Jeff Xu，

3、陳海波，陸品燕，張小俊，李瑞華，白博索閱、投稿、建議和意見反饋，請聯系：HWR印刷數量：4000本印刷單位：雅昌文化（集團）有限公司印刷地址：深圳市南山區深云路19號印刷日期：2022年12月16日版權所有 2022 華為技術有限公司，保留一切權利。華為研究內部資料，免費交流準印證號：（粵BL）022060040主編：廖恒本期責任主編：陳海波，陸品燕編委會：廖恒，童文，肖新華，胡邦紅，周慧慧，鮑豐，Jeff Xu，陳海波，陸品燕，張小俊，李瑞華，白博索閱、投稿、建議和意見反饋，請聯系：HWR印刷數量：4000本印刷單位：雅昌文化（集團）有限公司印刷地址：深圳市南山區深云路19號印刷日期：202

4、2年12月16日版權所有 2022 華為技術有限公司，保留一切權利。編者按陳海波華為基礎軟件首席科學家陸品燕華為理論計算機首席科學家歡迎大家來到華為研究軟件與理論分冊！軟件正在重塑數字世界與物理世界，成為數字世界的核心基礎設施。如何構建軟件基礎能力并突破軟件核心技術，是現代企業乃至國家擁抱數字世界的核心抓手。與物理世界的對象不同，軟件是一種“看不見摸不著”的邏輯實體，可能也是人類迄今為止所設計的最復雜的系統，一個大型軟件系統的代碼往往可達數億行。軟件的發展有其客觀規律，不存在一勞永逸的“銀彈”。軟件包含基礎軟件、應用軟件與工具軟件等不同類型，面向智能終端、嵌入式設備、云與企業 IT 等諸多產業

5、，它們的發展規律各具特色，生態現狀與需求也存在差異。軟件的生命周期與供應鏈管理具有自身的獨特性，支撐軟件不斷發展的軟件理論也在不斷演進。研究與掌握這些規律和理論，是我們研發出好軟件的關鍵。華為公司長期以來在軟件與理論領域持續投入，不僅面向終端、聯接、計算、云與智能駕駛等多產業構筑了良好的競爭力，通過可信及軟件工程變革不斷提升軟件的工程與可信能力，還構建了歐拉和鴻蒙兩大操作系統生態，從而推動了openEuler、OpenGuass、MindSpore、OpenHarmony 等基礎軟件開源社區的建設。本分冊匯聚了華為公司在基礎軟件、軟件理論以及開源社區構建等領域的專家觀點與新近成果。在基礎軟件領

6、域，操作系統演進：歷史、現在與展望從產業應用演進與硬件演進兩個維度來分析操作系統發展軌跡、創新機遇與技術挑戰，并介紹 openEuler 和 OpenHarmony 在技術演進方面的實踐；GaussDB：云原生分布式數據庫介紹了中央軟件院高斯部開發的企業級分布式數據庫平臺 GaussDB Kernel，以及該平臺的架構和主打特性；MindSpore：人工智能開源生態系統實踐介紹了深度學習框架 MindSpore 的主要架構與核心技術，以及在人工智能開源生態系統方面的實踐探索；華為畢昇編譯器的創新與實踐在總結分析編譯器技術演進的基礎上，系統性地介紹了華為畢昇編譯器的技術創新與實踐，分析核心技術特

7、性，并闡述了進一步演進和創新的技術方向。在軟件理論領域，在線匹配領域的最新進展介紹了在線匹配技術的最新學術進展；面向組合優化的學習增強算法設計介紹了在組合優化中運用 AI 技術的新近學術成果；求解器是一類非常重要的工具軟件，也是工業軟件的核心基礎，隨機游走與適應度函數相結合求解布爾可滿足性問題介紹了隨機游走技術在 SAT 求解器算法中的重大突破；域理論是編程語言及其分析工具最早的數學理論基礎，域理論與交互式計算是一篇綜述文章，詳細介紹了域理論自上世紀六十年代以來的發展歷史，以及在編程模型不斷演進的過程中，如何被用于刻畫交互、并發等行為?！败浖淌梢磺?，開源吞噬軟件”，開源策略的制定與社區構建的

8、度量從企業開源策略的制定和企業開源社區的構建等方面闡述了企業如何利用開源發展生態經濟，并推動產業數字化轉型。本分冊還有很多優秀文章，內容面向軟件領域的關鍵挑戰，力求貼近產業熱點，希望對讀者有所啟發。不當之處，也請多多批評指正！0112183748587910211312289基礎軟件軟件理論軟件技術與生態操作系統演進：歷史、現在與展望陳海波，錢梽楊，賈寧，胡欣蔚，李毅GaussDB：云原生分布式數據庫Andy Li，任陽MindSpore：人工智能開源生態系統實踐于璠，時北極，王紫東，金學峰，陳雷，蘇騰，李銳鋒，周斌，丁誠，譚焜華為畢昇編譯器的創新與實踐高耀清，華保健 在線匹配領域的最新進展唐

9、志皓，張宇昊面向組合優化的學習增強算法設計黃棱瀟，王彧弋，閻翔隨機游走與適應度函數相結合求解布爾可滿足性問題蔡少偉，姜滔域理論與交互式計算Glynn Winskel智能汽車LiDAR輔助GNSS-RTK定位 Han Gao，Weisong Wen，Li-Ta Hsu，Yongliang Wang技術使能藝術：新一代HDR Vivid視頻技術標準余全合，徐巍煒，王弋川，張繼武，陳虎，袁樂開源策略的制定與社區構建的度量侯培新，李自，王曄暉0112183748587910211312289基礎軟件軟件理論軟件技術與生態操作系統演進：歷史、現在與展望陳海波，錢梽楊，賈寧，胡欣蔚，李毅GaussDB：云

10、原生分布式數據庫Andy Li，任陽MindSpore：人工智能開源生態系統實踐于璠，時北極，王紫東，金學峰，陳雷，蘇騰，李銳鋒，周斌，丁誠，譚焜華為畢昇編譯器的創新與實踐高耀清，華保健 在線匹配領域的最新進展唐志皓，張宇昊面向組合優化的學習增強算法設計黃棱瀟，王彧弋，閻翔隨機游走與適應度函數相結合求解布爾可滿足性問題蔡少偉，姜滔域理論與交互式計算Glynn Winskel智能汽車LiDAR輔助GNSS-RTK定位 Han Gao，Weisong Wen，Li-Ta Hsu，Yongliang Wang技術使能藝術：新一代HDR Vivid視頻技術標準余全合，徐巍煒，王弋川，張繼武，陳虎，袁樂

11、開源策略的制定與社區構建的度量侯培新，李自，王曄暉01|華為研究2022 年 12 月基礎軟件操作系統承上啟下，向上服務應用，向下管理與挖潛硬件能力，是構建硬件生態與應用生態的關鍵。本文分別從產業與應用演進和硬件演進兩個維度來分析其發展軌跡、創新機遇與技術挑戰，并介紹 openEuler 和 OpenHarmony 的實踐。關鍵詞操作系統，openEuler，OpenHarmony摘要陳海波 1，錢梽楊 1，賈寧 1，胡欣蔚 1，李毅 21中央軟件院2 終端 BG 軟件部操作系統演進：歷史、現在與展望華為研究|022022 年 12 月圖 1 操作系統在整個計算系統中的定位圖 2 操作系統與產

12、業應用的共生發展歷史1 引言按照 計算機科學技術百科全書（第三版）1的定義，操作系統是“管理硬件資源、控制程序運行、改善人機界面和為應用軟件提供支持的一種系統軟件”。操作系統自誕生以來，其內涵與外延一直在不斷擴大，早期的操作系統只包含操作系統內核與原始的 Shell（如命令行終端），現代操作系統的功能不斷擴大，包含了擴展操作系統內核管理與抽象硬件資源功能的操作系統服務以及為應用創建執行環境與管理應用執行的應用框架（如圖 1）。操作系統在整個計算系統中發揮“承上啟下”的關鍵作用。承上就是為應用提供運行時和開發環境服務，并在一些場景下還作為應用生態與云服務的入口；啟下則是高效、安全地管理硬件，最大

13、程度地發揮硬件潛力，并使能硬件生態。本文將分別從產業與應用演進和硬件演進兩個維度來觀察和思考其發展軌跡，并從應用場景驅動與硬件驅動兩個維度來展望操作系統發展方向。最后，本文將介紹openEuler 和 OpenHarmony 的創新實踐。操作系統操作系統應用應用系統服務內核芯片和硬件芯片和硬件云服務云服務應用框架2 產業演進中的操作系統2.1 操作系統伴隨產業浪潮誕生與發展回顧操作系統的發展史（見圖 2），在業界取得成功的操作系統通常都是伴隨著產業浪潮誕生與發展的，并與產業互相促進。在早期的計算機中軟件硬件深度耦合，從而使得應用程序開發的專業性高、開發效率低，對更方便地使用計算機并進行應用開發

14、的需求直接推動了編程語言和操作系統的誕生，也使得軟硬件持續解耦。1956 年誕生的 GM-NAA I/O 2 系統可以被稱為操作系統的雛形，主要提供了輸入和輸出的管理系統。直到20 世紀 60 年代，才形成了真正意義上的操作系統。在此之前，大型機的軟件與硬件深度耦合，軟件往往需要等待硬件研制后數年才得以研發成功上市，從而影響整體系統的上市節奏。1964 年，IBM 發布的 OS/360 3 首次推動了軟件與硬件解耦；并且，這一操作系統的復雜研制過程還催生了“軟件工程”學科的開創性書籍人月神話：軟件項目管理之道4，該書對今天我們認識軟件的復雜性仍然具有很強的現實指導意義。1969 年，貝爾實驗室

15、的 Ken Thompson 和 Dennis Ritchie 在參加多任務信息與計算系統（Multiplexed Information and Computing Service，Multics）5 的研究后，認為這一系統過于復雜，從而在簡化 Multics 系統的設計理念的基礎上研制了 Unix 操作系統（原本叫 Unics，其中的 Uni-與 Multics 中 Multiplexed對應）6；基于此操作系統的理念，誕生了后續包括 Linux在內的一系列操作系統。20 世紀 80 年代面世的一系列操作系統，推動了小型機到 PC 機和嵌入式的演進與發展。舉例而言，QNX 7誕生于 198

16、2 年，廣泛應用于嵌入式領域，當前在智能車領域被廣泛應用；VxWorks 8 誕生于 1982 年，主要在嵌入式和工業場景廣泛使用；Windows 的誕生則推動了 PC的發展，并在隨后的 30 多年時間里始終在個人電腦和 PC服務器市場上占據主流地位；此外，前文提及的 1991 年誕1980s1980s1990s1990s2010s2010sPC&嵌入式PC互聯網移動互聯網萬物智聯2020s2020s聯接數：1000億用戶數：10億+用戶數：30億+用戶數：40億+QNX/QNX/VxWorksVxWorks(1982)(1982)Windows(1985)Windows(1985)主機用戶數

17、：數萬 OS/360(1964)OS/360(1964)Unix(1969)1960s1960s iOSiOS(2007)(2007)Android(2008)Android(2008)？Linux(1991)Linux(1991)03|華為研究2022 年 12 月基礎軟件生的 Linux 系統，推動了 PC 服務器和云計算的發展。iOS 和 Android 等移動操作系統的誕生則推動了手機等移動設備從功能機走向智能機，并伴隨著移動互聯網的發展，成為移動互聯網時代的王者。面向未來，隨著信息技術（Information Technology，IT）、通信技術（Communication Tec

18、hnology，CT）和運營技術（Operational Technology，OT）的逐步融合，以及人工智能（Artificial Intelligence，AI）與 5G 等技術的發展，操作系統將迎來萬物智聯的新發展機遇與挑戰。2.2 操作系統的成功要素也伴隨著產業不斷演進操作系統所承載的價值和成功要素也在不斷演進，大致經歷了硬件附屬、作為獨立的軟件產品、作為生態與云服務入口以及賦能和賦智千行百業等階段（見圖 3）。早期的操作系統（IBM OS/360 和早期的 Unix 等）作為硬件的附屬品，其價值也依附于硬件的價值產生。例如，IBM OS/360 作為 IBM 大型機的附屬而體現其價值

19、。彼時，硬件設備性能約束大，在這個階段的操作系統關鍵的成功要素是性能。硬件附屬硬件附屬獨立的軟件產品獨立的軟件產品生態入口生態入口+云服務云服務賦能、賦智千行百業賦能、賦智千行百業1960s1960sOSOS的的價值價值年代年代1980s1980s2000s2000s2020s2020s例如：IBM OS/360和Unix例如：Windows例如：Android+GMS成功要素：性能成功要素：通用成功要素：粘性成功要素：柔性、智能圖 3 操作系統的價值與成功要素演進20 世紀 80 年代以來，操作系統逐步成為一個獨立的軟件產品。例如，Windows 就是這一階段作為獨立的軟件產品銷售的典型代表

20、。由于軟件的可復制性非常強，銷售軟件授權（License）可以獲得巨大價值，這使得微軟在很長一段時間內都是市值最高的 IT 公司之一。這一階段，操作系統獲得成功的關鍵要素是通用。Windows 對設備的兼容性和應用的通用性，推動了 PC 時代的發展。2000 年以后，操作系統的商業模式逐步演進為作為生態與云服務的入口。例如蘋果 iOS+iCloud+App Store與安卓+GMS+應用市場形式，通過提供一個生態入口，加上與云的連接，形成一個非常強大的生態，它的成功因素主要是生態的粘性。展望未來，隨著數字世界進入每個人、每個家庭、每個組織，從而構建萬物互聯的智能世界，操作系統支撐這一戰略的關鍵

21、是要能夠賦能、賦智各行各業，而其核心成功要素是柔性和智能。需要強調的是，上述四種模式并不是替代關系，而是逐步演進的，舊的模式在相當長的時期里會一直存在。面向未來，我們將看到多種形態的共存。例如，操作系統將持續支撐設備類產品的競爭力，操作系統作為生態與云服務入口的方式方興未艾，同時業界也在積極探索如何賦能、賦智千行百業。華為研究|042022 年 12 月圖 4 人機物融合與云網邊端協同新使命 9圖 5 硬件形態爆炸式地進化、雜交和演變面向未來賦能、賦智千行百業，終端、IT 與 CT 等技術逐步融合，從某種程度來講，操作系統將承擔起人機物融合以及云網邊端協同的新使命（見圖 4）。封閉場景下的操作

22、系統所面對的往往是物理資源安全的、靜態孤立的網絡域，適用小規模抽樣數據分析，整體是一個靜態、封閉、受限的系統。而面向千行百業，操作系統從一個靜態、封閉、受限的系統演進到一個動態、開放、擴展的系統，適用全樣本大規模的數據分析，需要更加關注虛擬資源的安全 9。3 業務場景驅動的操作系統創新方向展望3.1“昆蟲綱悖論”呼喚元 OS 架構創新萬物智聯會帶來許多新的變化，其中一個顯著變化就人機物人機物融合融合態勢態勢靜態、封閉、受限的系統靜態、封閉、受限的系統小規模抽樣數據分析小規模抽樣數據分析靜態孤立網絡靜態孤立網絡物理資源安全物理資源安全動態、開放、擴展的系統動態、開放、擴展的系統全樣本大規模數據分

23、析全樣本大規模數據分析移動泛在互聯網移動泛在互聯網虛擬資源安全虛擬資源安全主機臺式機1960s1960s1980s1980s2000s2000s2020s2020s是產品和應用場景會呈現爆炸式地形態進化、雜交和不斷演進。我們傳統認知上的一種設備，跟其他設備進行雜交、融合，就可能會誕生出新的硬件形態，并增加原有硬件的附加值（見圖 5）?！袄ハx綱悖論”是東京大學的坂村健教授對個性化與通用性之間矛盾提出的一個形象比喻。地球上的哺乳動物大約有 5 千多種，好比傳統的服務器、PC 和手機等設備；昆蟲大概有 100 多萬種，好比萬物智聯時代的多樣化設備。一方面，數量更大的萬物智聯設備帶來的累計價值，可能會

24、超過 PC 和手機市場；但另一方面，由于缺乏可大批量復制的軟硬件和應用，沒有批量也就難以有低成本，因而很難產生很大的市場。面向萬物智聯時代的硬件形態不斷創新，會帶來操作系統的“昆蟲綱悖論”挑戰，亟需應對多樣化場景下的資源大小、功能、性能、安全、生態等多方面的差異化。操作系統必須實現組件式解耦與按需合成，既能夠保證架構的一致05|華為研究2022 年 12 月基礎軟件性，便于統一維護，同時可以通過彈性組合的方式去解決個性問題。我們將滿足這樣設計意圖的操作系統架構稱為“元OS 架構”。元 OS 架構的目標是“One OS Kit for All”，即我們要打造的不再只是一個操作系統，而是一個可以被

25、靈活組裝的操作系統能力集合（OS Kit），基于一個高度彈性的架構，將這些操作系統能力組合成為滿足各行各業場景需要的場景化操作系統，進而緩解“昆蟲綱悖論”挑戰。3.2 新形態計算呼喚操作系統誕生新的計算抽象回顧虛擬化和容器這兩個當前主流的計算抽象的歷史（見圖 6），前者誕生于上世紀 70 年代，早在 IBM OS/370 就已提供了虛擬化能力，而創立于 1998 年的VMware 則開啟了 PC 服務器虛擬化的時代序幕；后者在上世紀 70 年代也出現了雛形，比如，早在 1979 年 Unix V7 就提供了早期的隔離環境，而現在業界主流的 Linux 容器（Linux Container，LX

26、C）誕 生 于 2008 年，Docker則誕生于 2013 年。虛擬化和容器在一定程度上使能了云計算革命。然而，隨著函數計算、邊緣計算的興起，虛擬機和容器這樣的計算抽象存在一定的局限性。以函數計算為例，對運行時環境的新訴求逐步突顯，包括（但不僅限于）：75%的函數計算的最大執行時間僅為 10 秒，希望運行時環境具備極致輕量化和超短生命周期能力；81%的函數計算為低頻調用(平均每分鐘少于 1 次），要求更高效地減少駐留內存，提升資源利用率；傳統的分支預測在面對短函數時錯誤率非常高，呼吁打造更有效的新型調度機制；場景更加開放，對安全隔離的訴求更高等 10。這些對操作系統的新訴求與傳統操作系統的差

27、異非常大，虛擬機和容器的抽象顯得過于厚重，安全隔離性也存在可提升的空間。以上新形態計算訴求正在呼喚操作系統領域誕生新的運行時抽象。3.3 系統的復雜性和敏捷性之間的矛盾逐步催生“學習型系統”系統的復雜性和敏捷性之間的矛盾催生“Learned Systems”，即 AI 與系統相結合。在封閉系統下，過去的操作系統是一個結果確定的、整體等于部分之和、穩定封閉的操作系統，因此適用基于經驗的調優；然而，面向一個開放、成長的復雜系統，它的整體可能會大于部分總和，而且會不斷演化，因此更適合用 Learning 的方式提升系統效率9（見圖 7）。然而，用機器學習或者用 AI 來解決系統問題，需要思考如何把機

28、器學習的方式和傳統的基于經驗的或者基于系統設計的方式，進行有效結合，才能發揮學習型系統的優勢。圖 6 操作系統運行時抽象的演進圖 7 還原論與系統論的差別 91970s1970s1980s1980s1990s1990s2000s2000s2010s2010s2020s2020s大型機（Mainframe）虛擬化小型機（Unix）虛擬化PC服務器虛擬化（VMware/Xen/KVM）容器（LXC/Docker）?穩定封閉的穩定封閉的系統系統整體等于部整體等于部分之和分之和結果確定性結果確定性開放成長的開放成長的復雜系統復雜系統整體大于部整體大于部分之和分之和關聯演化關聯演化還原論還原論系統論系統

29、論華為研究|062022 年 12 月圖 8 算力演進示意圖操作系統的參數數量龐大、業務負載與系統狀態瞬息萬變，如何實現自動調優和運維是業界面臨的普遍挑戰，也是學術界的研究熱點。近年來，學術界在該領域也不斷取得新的研究進展，包括（但不僅限于）：基于學習的操作系統 11、基于學習的可擴展索引 12、基于學習的緩存 13與基于學習的并發控制 14 等。4 硬件驅動的操作系統創新方向展望4.1 異構眾核 SoC、XPU 協同和新計算架構演進呼喚新的計算范式從算力的角度看，操作系統需要協同和推動異構眾核片上系統（System on a Chip，SoC）、XPU 協同和新計算架構三大方面的計算范式演進

30、（見圖 8）。異構眾核 SoC：CPU 從單核、多核演進到了當前的眾核，在服務器場景下已經可見數百核，甚至千核的規模；同時，我們觀察到大小核/異構核也從過去的手機等終端設備，進入到 PC 場景（例如蘋果 M1），并且有演進到服務器的趨勢。圍繞異構眾核 SoC，操作系統需要研究諸多挑戰性的課題，包括但不僅限于：合成大規模的可擴展同步原語 15、提升同步CPUDRAM閃存/硬盤以以CPUCPU為中心為中心DPUGPUGPUDPUNPUCPUNPUCPU以數據為中心 DRAM SCM NAND HDDDSADSA單核 多核 眾核眾核 異構眾核異構眾核XPUXPU算力協同算力協同新計算架構新計算架構原

31、語的可靠性和可擴展性以便能夠可靠地釋放并發算力 16、非統一內存訪問（Non-uniform Memory Access，NUMA）+非 對 稱 多 處 理（Asymmetric Multiprocessing，AMP）架構感知和瞬態線程遷移等。領域專屬架構（Domain-Specific Architecture，DSA）下的 XPU 算力協同：操作系統需要突破 XPU（例如CPU、GPU、NPU、DPU等）間的高效協同，從過去的單一操作系統演進為 SoC 上的一組協同的操作系統，從而最大程度地發揮 SoC 的整體能效。新計算架構探索：DSA 的弊端逐步顯現，例如，廠家要看護多種硬件架構、功

32、能重疊浪費、軟件棧難以共享、XPU 間協同調度效率難以大幅提升等。牧村定律 17認為半導體技術每十年完成一次定制化和通用化的回歸。業界也期待 DSA 之后能夠誕生新的計算架構。而在新的計算架構下，傳統操作系統的基礎架構和基礎能力也將發生根本性的變革。4.2 新存儲介質和互聯技術需要操作系統提供新的數據管理范式傳統的緩存、內存、存儲的速度與成本是涇渭分明的，它們以 CPU 為中心，形成了梯次緩存的多層存儲結構。而存儲級內存（Storage Class Memory，SCM）等非易失07|華為研究2022 年 12 月基礎軟件內存的出現，使得存儲介質時延從毫秒級進入到微秒級（見圖 9）；同時，結合

33、 UB 等高性能、高可擴展性的新型互聯技術出現 18（見圖 10），傳統的數據管理范式正在面臨挑戰。存儲介質時延從毫秒級進入到微秒級，軟件棧的時延在整個 I/O 中的占比呈數量級地提升，因此超低時延的存儲軟件棧 19、高并發下數據一致性 20 等成為近年的研究熱點。在新介質與新互聯技術的共同推動下，傳統操作系統的內存和存儲兩層存儲管理架構將可能逐步演進到以數據為中心的單級存儲（Single-Level Store，SLS）架構，即內存和存儲在邏輯層面上實現了融合管理，從而大幅減1 ns1 ns10 ns10 ns100 ns100 ns1 1 s10 10 s100 100 s1 1 msms

34、10 10 msms100 100 msms1s1sSRAMSRAMDRAMDRAMNANDNANDHDDHDDTapeTapePM/SCMPM/SCM內存內存存儲存儲圖 9 新介質正在使得內存與存儲融合圖 10 互聯技術的性能與可擴展性圖 11 操作系統計算架構與范式的演進趨勢可擴展性性能RoCE/InfiniBandPCIe內存總線UBUB14224 Gbit/s14224 Gbit/s50 Gbit/s464 Gbit/s12.525 Gbit/s少數據搬移；進一步，如何使數據離計算節點更近，實現以業務為中心的效果？這也呼吁近數計算（Near Data Computing，NDC）系統的

35、出現（見圖 11）。4.3 機密計算架構呼喚操作系統領域研究新的信任范式“機密計算”（Confidential Computing）是指在可信硬件支持下的隔離環境中運行安全計算任務，從而實現對安全計算任務的代碼和數據進行保護的一項安全技術。隨著數據安全與隱私監管的不斷加強（例如，歐盟的 GDPR、以及中國的數據安全法等），機密計算受到業界越來越多的關注。從 2002 年 ARM 提出 TrustZone 架構起，出現了各種機密計算技術方案和抽象演進（見圖 12）21。TrustZone 是 ARM 在 2002 年提出的隔離機制，其隔離對象包含了 CPU、內存、總線結構和外圍設備，提供了獨立的

36、物理機抽象 22。目前，TrustZone 在移動端ARM手機上被廣泛部署和使用，提供生物信息識別（例如，指紋識別、人臉識別、虹膜識別）以及安卓系統密鑰管理等安全特性。通常，在 ARM TrustZone 會運行一個小而安全的操作系統，例如，Huawei iTrustee 23、OP-TEE 24、Trustonic 25 等。DPUDPUGPUGPUGPUGPUDPUDPUNPUNPUCPUCPUNPUNPUCPUCPU新介質新介質SLSSLSCPUCPUDRAMDRAM閃存閃存/硬盤硬盤以以CPUCPU為中心的三層架構為中心的三層架構CPU+多層存儲以數據為中心的以數據為中心的SLSSLS

37、XPU+新介質架構以業務為中心的原位計算以業務為中心的原位計算面向業務的高質量數據劃分面向業務的高質量數據劃分按照數據應用特征進行均衡劃分數據節點數據節點數據節點數據節點數據節點數據節點數據節點數據節點數據節點數據節點基于原位計算的事務處理框架基于原位計算的事務處理框架微秒級低時延數據遷移軟硬協同的本地事務執行華為研究|082022 年 12 月圖 12 機密計算主要技術及其發展歷史2021 年 的 ARM Vision Day 上，ARM 發 布 了 新一代 ARM V9 架構，其中提出了 ARM 機密計算架構（Confidential Compute Architecture，CCA），在

38、 原有的 Non-Secure World 和 Secure World（之前的可信執行環境，TEE）基礎上，新引入一個安全區叫 Realm。CCA 新架構的本質是改變了信任范式，從此前終端領域的“信任設備，不信任應用”，演進到云計算領域的“客戶信任自己的應用，但不必信任基礎設施提供商”。操作系統需要支持 Realm Manager 以及其上的可信任操作系統，才能有效支撐 ARM CCA 的這一信任范式改變 26。2015 年，Intel 正式宣布軟件防護擴展（Software Guard Extensions，SGX）技術并發布第一代 SGX。SGX在用戶態進程中劃分出一塊安全“飛地”（En

39、clave），Enclave 內的代碼和數據對外界完全不可見。程序員需要顯式地對代碼進行靜態劃分：安全部分（Enclave）與非安全部分（App），并規定好二者交互的接口。SGX 的安全威脅模型不信任操作系統，因此 SGX 在硬件設計中定義了大量功能，用于檢驗底層不可信特權軟件的行為，主要包括安全頁表管理、安全線程管理、安全內存的換頁管理、以及安全內存的完整性校驗等。由于 Enclave 抽象是應用的一部分，而應用與操作系統的接口與交互極其復雜并且經常演進，導致 SGX 的硬件設計比較復雜，硬件需要承載很多軟件的功能，并且性能開銷也較大。2022 年 1 月 Intel 宣布在除服務器之外的新

40、桌面/筆記本/嵌入式處理器中放棄所有的 SGX 特性 27。信 任 域 擴 展（Trust Domain Extensions，TDX）是 Intel 繼 SGX 之后推出的新安全計算抽象。在設計上，TDX 引入了單獨的可信的 Hypervisor/VMM，和原有的云平臺 VMM 共享同一物理主機?？尚诺?Hypervisor 稱為TDX Module，是一小塊安全模塊，負責可信域（Trusted Domain，TD）內的可信虛擬機和外部不可信 VMM 之間的交互檢查。從 ARM CCA 和 Intel TDX 等演進趨勢看，操作系統領域需要研究相應的信任范式演進，通過創新操作系統的架構設計（

41、例如，微內核架構）來減少機密計算抽象內的可信計算基（Trusted Computing Base，TCB）的大小，同時也需要使用合理的方式來保障機密計算抽象中 TCB 的安20022002年年20152015年年20162016年年20192019年年20202020年年20212021年年ARM提出TrustZoneTrustZoneIntel發布SGXv1SGXv1硬件硬件AMD發布SEVSEV硬件硬件AWS發布Nitro HypervisorNitro HypervisorAMD發布SEVSEV-SNPSNP規范Intel發布TDXTDX規范ARM發布CCACCA規范Intel發布Sca

42、lable SGXScalable SGX硬件RISC-VKeystoneKeystone開源RISC-VPenglaiPenglai開源全性與可信性，如軟硬件協同安全加固、形式化驗證、安全性更高的語言（例如 Rust）等。5 openEuler 和 OpenHarmony的實踐5.1 openEuler 的實踐2019年12月，華為創建歐拉開源項目（openEuler），通過開源的方式，把多年來積累的操作系統能力開放出來，攜手產業伙伴共同發展操作系統產業；2021 年 11 月，在操作系統產業峰會上，華為攜手社區伙伴，將歐拉正式捐贈給開放原子開源基金會，實現了歐拉開源操作系統從企業主導到產業

43、主導的重要轉變 28。從產業應用角度看，openEuler 打造了一套靈活的架構支持服務器、云計算、邊緣計算、嵌入式等ICT和OT場景，成為面向數字基礎設施統一的開源操作系統；同時，從硬件角度看，openEuler 支持多樣性算力的協同釋放，打造了面向 SCM 等新存儲介質的存儲軟件棧，同時還打造了自動化、智能化的性能調優引擎。在 各 參 與 方 的 攜 手 努 力 下，截 至 2022 年 3 月，openEuler 及其發行版已經實現了在十多個行業的應用，實現對 5000 多種軟件的認證支持，并已兼容 60 多種整機和 200 多種主流板卡，支持鯤鵬、x86、飛騰、龍芯、申威、RISC-V

44、 等多種處理器架構 29。5.2 OpenHarmony 的實踐華為于 2020 年起陸續將其智能終端操作系統（即“鴻蒙操作系統”）的基礎能力捐獻給開放原子開源基金會，由開放原子開源基金會整合其他參與者的貢獻，形 成 OpenHarmony 開 源 項 目，同 時 華 為 持 續 參 與OpenHarmony 開源項目的共建。09|華為研究2022 年 12 月基礎軟件OpenHarmony 是面向萬物互聯時代的智能終端統一的操作系統，為不同設備的智能化、互聯與協同提供了統一的語言，為消費者帶來簡捷、流暢、連續、安全可靠的全場景交互體驗。具有三個獨有特征：一套操作系統可以滿足大小設備需求，實現

45、統一 OS彈性部署；OpenHarmony 通過組件化和彈性化等設計方法，做到硬件資源的可大可?。ㄖС謴陌?KB 級到 GB 級的內存大?。?，并覆蓋了 ARM、RISC-V和 x86 等多種處理器架構。搭載該系統的設備在系統層面融為一體、形成超級終端，讓設備的硬件能力可以彈性擴展，實現設備之間硬件互助、資源共享；OpenHarmony 的分布式能力使得終端設備間能夠快速發現與互聯，并實現高效數據傳輸，以及跨設備任務協同。OpenHarmony 提供了跨終端的應用開發框架和 API一致性，面向開發者，實現一次開發、多端部署。OpenHarmony 在技術架構上整體遵從分層設計，從下向上依次為：內

46、核層、系統服務層、框架層和應用層。系統功能按照“系統 子系統 組件”逐級展開，在多設備部署場景下，支持根據實際需求裁剪某些非必要的組件。5.3 openEuler 與 OpenHarmony 的協同創新openEuler 側重面向數字基礎設施，OpenHarmony則 側 重 智 能 終 端。而 面 向 未 來，openEuler 和OpenHarmony 協同創新，預期將有機會打造出一個覆蓋云、管、邊、端能力的協同操作系統?？删幊虄群丝蚣芸删幊虄群丝蚣芏嗄ｒ寗涌蚣芏嗄ｒ寗涌蚣芏嘤蛉诤霞夹g多域融合技術端云協同總線端云協同總線分布式數據框架分布式數據框架分布式調度框架分布式調度框架鴻蒙系鴻蒙系統

47、服務統服務歐拉系歐拉系統服務統服務鴻蒙基礎服務鴻蒙基礎服務歐拉基礎軟件歐拉基礎軟件端云協同運行時端云協同運行時鴻蒙應用框架鴻蒙應用框架歐拉應用框架歐拉應用框架鴻蒙應用鴻蒙應用鴻蒙應用歐拉應用歐拉應用歐拉應用鴻蒙/歐拉互通應用 openEuler 和 OpenHarmony 之間的能力共享：包括（但不僅限于）內核、驅動框架、協作總線、端云協同運行時環境等（見圖 13）。openEuler 和 OpenHarmony 組合實現一機多域、優勢互補：在一些復雜場景下例如，辦公 PC 既要打造流暢、低功耗的用戶體驗，又要利用現有的生產力工具和應用生態可以通過打通 openEuler和 OpenHarmo

48、ny，實 現“一 機 多 域”混 合 部 署（見圖 14）。openEuler 和 OpenHarmony 協同突破云網邊端的跨域融合：基于近遠場融合軟總線等技術，實現近遠場設備的自發現、自連接、彈性規模和服務水平 協 議（Service Level Agreement，SLA），打造體驗感知的鏈路管理，并實現云網邊端算力互助（見圖 15）。圖 13 openEuler 和 OpenHarmony 能力共享圖 14 openEuler 和 OpenHarmony 多域組合鴻蒙鴻蒙辦公辦公PCPC歐拉歐拉流暢/低功耗用戶體驗利用生產力工具和應用生態容器華為研究|102022 年 12 月圖 15

49、 openEuler 和 OpenHarmony 云網邊端跨域融合終端設備終端設備云云&邊邊鴻蒙鴻蒙歐拉歐拉鏈路管理與算鏈路管理與算力互助力互助6 結語操作系統承上啟下，向上服務應用，向下管理、挖潛硬件能力。本文分別從產業應用場景演進和硬件演進兩個視角來觀察和思考操作系統的發展軌跡。從產業應用演進看，萬物智聯時代產品形態多樣化，要求操作系統具備彈性架構；函數計算、邊緣計算等新計算形態興起，呼喚操作系統誕生新的極致輕量、短生命周期、安全隔離的計算抽象；而系統的復雜性和敏捷性之間的矛盾，又將推動“學習型系統”的發展。從硬件演進看，異構眾核 SoC、DSA 架構下的 XPU協同、以及新計算架構演進，

50、呼喚操作系統領域研究新的計算范式；新存儲介質和互聯技術呼喚研究新的數據管理范式；同時，ARM V9 發布的 CCA 架構正在推動操作系統信任范式從終端設備的“信任設備、不信任應用”到云計算場景的“客戶信任自己的應用，但不必信任基礎設施提供商”轉變，催生機密計算操作系統。openEuler 側重面向數字基礎設施，OpenHarmony則側重智能終端，而 openEuler 和 OpenHarmony 協同創新，正在逐步打造一個覆蓋云、管、邊、端能力的協同操作系統體系。參考文獻1 張效祥等.計算機科學技術百科全書（第三版）.清華大學出版社，2018.2 https:/en.wikipedia.or

51、g/wiki/GM-NAA_I/O3 Frederick P.Brooks Jr.,The IBM operating system/360,Software Pioneers,Springer,Berlin,Heidelberg,2002,170-178.4 Frederick P.Brooks Jr.,The Mythical Man-Month:Essays on Software Engineering,Pearson Education,1995.5 V.A.Vyssotsky,F.J.Corbat,and R.M.Graham,Structure of the Multics su

52、pervisor,Proceedings of the November 30-December 1,1965,Fall Joint Computer Conference,part I,1965.6 Dennis M.Ritchie,The evolution of the Unix time-sharing system,Symposium on Language Design and Programming Methodology,Springer,Berlin,Heidelberg,1979.7 David C.Sastry and Mettin Demirci,The QNX ope

53、rating system,Computer,28.11(1995):75-77.8 https:/ 王懷民.分布計算 2.0：基于網絡的聯接計算.2020 CCF 中國軟件大會特邀報告，2020.10 Mohammad Shahrad,Jonathan Balkind,and David Wentzlaff,Architectural implications of function-as-a-service computing,Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitectu

54、re,2019.11 Yiying Zhang and Yutong Huang,Learned operating systems,ACM SIGOPS Operating Systems Review,53.1(2019):40-45.12 Chuzhe Tang et al.,XIndex:A scalable learned index for multicore data storage,Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,20

55、20.13 Xingda Wei,Rong Chen,and Haibo Chen,Fast RDMA-based ordered key-value store using remote learned cache,14th USENIX Symposium on Operating Systems Design and Implementation,Banff,Alberta,Canada,November 2020.11|華為研究2022 年 12 月基礎軟件14 Jiachen Wang,Ding Ding,Huan Wang,Conrad Christensen,Zhaoguo Wa

56、ng,Haibo Chen,and Jinyang Li,Polyjuice:High-performance transactions via learned concurrency control,in Proceedings of the 15th USENIX Symposium on Operating Systems Design and Implementation,July 2021.15 Rafael Lourenco de Lima Chehab et al.,CLoF:A compositional lock framework for multi-level NUMA

57、systems,Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles,2021.16 Jonas Oberhauser et al.,VSync:push-button verification and optimization for synchronization primitives on weak memory models,Proceedings of the 26th ACM International Conference on Architectural Support for

58、Programming Languages and Operating Systems,2021.17 Tsugio Makimoto,Implications of Makimotos Wave,Computer,46.12(2013):32-37.18 Tan Kun et al.,UB:Unified and scalable memory-semantic interconnection for next-generation computing systems,Communications of HUAWEI RESEARCH,vol.1.19 Mingkai Dong and Ha

59、ibo Chen,Soft updates made simple and fast on non-volatile memory,2017 USENIX Annual Technical Conference(USENIX ATC 17),2017.20 Jifei Yi et al.,HTMFS:Strong consistency comes for free with hardware transactional memory in persistent memory file systems,Proceedings of the 20th USENIX Conference on F

60、ile and Storage Technologies,2022.21 Fahmida Y.Rashid,The rise of confidential computing:Big tech companies are adopting a new security model to protect data while its in use-news,IEEE Spectrum,57.6(2020):8-9.22 Sandro Pinto and Nuno Santos,Demystifying Arm TrustZone:A comprehensive survey,ACM Compu

61、ting Surveys(CSUR),51.6(2019):1-36.23 https:/ 0680&postId=030251307616991036324 https:/www.op-tee.org/25 https:/ Dominic P.Mulligan et al.,Confidential computinga brave new world,2021 IEEE International Symposium on Secure and Private Execution Environment Design(SEED),2021.27 https:/ https:/openeul

62、er.org/29 https:/www.openeuler.org/zh/compatibility/華為研究|122022 年 12 月華為 GaussDB 是由 2012 實驗室中央軟件院高斯部開發的企業級分布式數據庫內核。該內核歷經十數年的開發，現在已經被廣泛應用于國內各地的企業客戶，包括一些大規模金融機構。中國前七大銀行中有五家選擇了 GaussDB，并廣泛應用在其核心業務場景如核心銀行、互聯網金融服務、渠道業務、客戶關系管理（Customer Relationship Management，CRM）/企業資源計劃（Enterprise Resource Planning，ERP）等

63、。截止到 2021 年年底，GaussDB在中國有1500多家企業客戶。本文介紹了GaussDB的架構和它的一些主打特性。GaussDB在高可用、高性能、混合負載、安全以及自治五大方面構筑競爭力。關鍵詞分布式數據庫，云化，高性能，高可用，混合負載，安全，自治，openGauss，GaussDB摘要Andy Li，任陽高斯部GaussDB：云原生分布式數據庫13|華為研究2022 年 12 月基礎軟件1 引言圖 1 GaussDB 高級邏輯系統架構2 架構隨著新業務和新基礎設施的出現，應用對數據庫提出了新的技術要求。隨著移動互聯網的普及，2C 服務大量出現。金融服務、移動設備上的電子商務應用、社

64、交應用以及物聯網（Internet of Things，IoT）設備正在產生各種類型的海量數據。這一切的變化，要求改變傳統業務基于柜臺和集中處理的服務模式。在此背景下，數據庫技術從集中式數據庫走向分布式數據庫，再發展到基于云的分布式數據庫。為更好地滿足金融、企業服務以及相關新型應用需求并高效利用云計算基礎設施，華為發布了自主研發的企業級云分布式數據庫 GaussDB。與傳統的分布式應用架構和分布式中間件架構數據庫不同，GaussDB 分布式數據庫從一開始就為分布式而設計，擁有結構化查詢語言（Structured Query Language，SQL）引擎、執行引擎和存儲引擎等組件。GaussD

65、B 在以下五個方面構筑自己的競爭力：高可用、高性能、混合工作負載、安全和自治。GaussDB采用基于 shared-nothing 大規模并行處理（Massively Parallel Processing，MPP）架構，支持美國國家標準學會（American National Standards Institute，ANSI）SQL 2008 標準。本文的其余部分組織如下。第 2 節介紹了 GaussDB的架構概況以及競爭力的五個主要方向。第 3 節中我們進行總結并對未來可能的工作進行了一些討論。在這一節中，我們首先介紹 GaussDB 的架構。GaussDB 基于 shared-nothi

66、ng 架構，單套數據庫可以線性擴展到數百臺物理機，可以并行處理各種工作負載。數據庫的數據按照一定條件分布在并存儲在各個數據節點（Data Node，DN）中。這些節點滿足本地“原子性，一致性，隔離性和持久性”（Atomicity,Consistency,Isolation,Durability，ACID）屬性，系統通過使用兩階段提交（Two Phase Commit，2PC）和全局事務管理器（Global Transaction Manager，GTM）來保證跨節點的一致性。GaussDB 同時支持行存儲及列存儲格式?；诹写鎯Ω袷?，GaussDB 實現了向量執行引擎以高效利用處理器最新的單指

67、令多數據（Single Instruction Multiple Data，SIMD）指令，從而實現指令級別的細粒度并行。系統生成的執行計劃以及執行器都針對分布式系統進行設計，可在數百臺服務器上對執行計劃進行并行處理，節點間按需交換數據且并行執行查詢。GaussDB 采用基于時間戳的 GTM-Lite 技術，最大限度降低跨節點事務的性能衰減。系統中相關的邏輯實例有運維管理器（Operation Manager，OM）、集 群 管 理 器（Cluster Manager，CM）、GTM、協調節點（Coordinator Node，CN）和DN。應用程序通過 CN 發送 SQL 語句，經 CN 產

68、生執行計劃，下推到相關 DN 執行查詢，DN 將結果匯總到 CN 上，最后由 CN 返回給應用程序。表 1 系統實例描述實例功能CN接收 SQL 語句并產生執行計劃，協調DN 節點完成執行計劃DN存儲實際數據。DN 相互配合一起完成SQL 查詢。GTM產生全局時間戳并提供全局快照。CM由 CM Agent 以及 CM Server 組成，負責集群仲裁和提供高可用能力。Gauss Data Source(GDS)提供數據并行加載能力。華為研究|142022 年 12 月2.2 高可用圖 2 GaussDB 高可用能力全景圖GaussDB 的高性能建立在充分利用硬件資源基礎上。針對鯤鵬處理器，Ga

69、ussDB 重構了數據庫內核中的關鍵數據結構從而避免了全局共享數據結構的跨片訪問，大大減少了 CPU 偽共享（False Sharing）的問題。同時GaussDB 使用鯤鵬處理器的原子“取有效地址”（Load Effective Address，LEA）指令重構了數據庫中的自旋鎖（Spin Lock），將自旋鎖的性能提高了 4 倍?；诖鎯墐却妫⊿torage Class Memory，SCM）和遠程直接數據存?。≧emote Direct Memory Access，RDMA）技術，GaussDB 團隊研究了以內存為中心的架構和下一代分布式數據庫通信網絡。所有這些使 GaussDB 在單

70、節點2-socket 鯤鵬服務器上提供 150 萬 tpmC 處理能力，在單節點 4-socket 鯤鵬服務器上提供超過 230 萬 tpmC 處理，線性伸縮比達到 1.5。此外，GaussDB 通過以下四個方面增強系統性能。Shared-Nothing 架構，GaussDB 將數據按照一定規則分布在各個 DN 上。在執行查詢時，DN 在本地處理自己的數據，并根據需要在節點之間打散數據。對稱多處理（Symmetric Multiprocessing，SMP）技術，為了充分利用現代 CPU 多核能力，GaussDB實現了查詢的 SMP 技術。在一個節點內，數據被分成多個部分并由不同的線程并行處理

71、。在一些計算密集型的查詢中，系統可以充分利用CPU來加速查詢處理。指令級并行（Instruction-Level Parallelism，ILP）技術，基于現代 CPU 的 SIMD 能力，GaussDB 實現了向量執行引擎。向量執行引擎以批處理模式（每次 1000 個 tuple）處理數據，使得系統在 TPC-H 和TPC-DS 基準測試中獲得高分。2.1 高性能 動態編譯技術，為了不斷提高處理性能，我們采用了動態編譯策略。使用低級虛擬機（Low Level Virtual Machine，LLVM）技術精簡查詢涉及的 CPU 指令數，從而提升查詢性能。GaussDB 的高可用能力包括五個部

72、分：防錯、容錯、糾錯、快速定位和服務可用性。從初始設計開始，GaussDB 的架構理念是防止系統單點故障（Single Point of Failure，SPOF），系統的相關硬件交換機、網卡和電源等硬件組件通過冗余達到該目標。對于本地盤，系統使用 RAID5 陣列提供數據保護，防止單個磁盤數據損壞時導致業務中斷，對于 EVS 云盤，系統使用云盤自身的多副本機制提供數據可用性。除了硬件冗余外，系統對于實例角色的架構設計也采用高可用架構，系統中 CN 采用多副本對等架構、DN 采用主備副本機制，CM、GTM 等也都采用溫備份機制。各個角色的主備裁決均由 CM 進行，CM 自身的主備裁決依賴于分布

73、式鍵值存儲系統（Editable Text Configuration Daemon，ETCD）組件。CM 作為集群的大腦，決定實例的主備角色。其自身有多個溫備份，當系統主 CM 的主實例發生故障時，經過 ETCD 裁決，選擇一個 CM 備進行升主操作，從而接管集群仲裁能力。GTM 和DN 等角色的主實例和溫備實例定期向 CM 主實例發送心跳。根據心跳，CM 確定各個角色的主實例，并在主實例故障時進行切換。除此之外，GaussDB 提供多種日志分析工具、核心轉儲分析工具、分布式跟蹤工具等，在系統出現故障時提供高效問題定位手段。同時，GaussDB 還提供運維操作不中斷服務的能力，在線升級和在線

74、擴容功能可以保證在升級和擴容操作時業務工作流程不中斷。15|華為研究2022 年 12 月基礎軟件2.3 混合工作負載2.4 安全能力在實際金融行業的生產系統中，根據不同業務的高可用要求，GaussDB 提供多層次的高可用能力：單個可用分區（Availability Zone，AZ）高可用、跨 AZ 高可用以及跨 Region 高可用能力。在 AZ 中，基于無單點故障的設計，GaussDB 在提供 RPO=0，RTO 10s 的高可用能力。在保證 AZ 級高可用能力基礎上，GaussDB 在 100+物理節點上能夠提供 1.2 億 tpmC 的超高性能。GaussDB提供跨 AZ 集群部署，提

75、供強一致性以及對應的高可用能力（RPO=0 和 RTO 1，（值最大化）秘書問題都有一個確定性算法，算法的期望競爭比漸近為gc,()，表示為：函數f(c)是依據 Lambert W函數的兩個分支W0和W1得出，寫作f(c)=expW0(1/(ce)expW1(1/(ce)。在線二分匹配。在線二分匹配問題中，有二分圖G=(L R,E)（其中，|L|=n且|R|=m），其節點集L以均勻隨機順序在線到達 73,66。一個節點到達后，會顯示與各鄰居之間的邊權重R。算法必須不可撤銷地決定是否把到達的在線節點匹配給R中的某個（當前尚未匹配的）鄰居。針對此設定，Kesselheim 等人 66 給出了一個緊

76、的1/e-競爭確定性算法，對經典秘書算法中的相同保證進行了顯著泛化 77,37。此設定中的預測結果即為值向量p=(p1,.,pm)，在某個固定最優（離線）二分匹配中，該向量可以預測節點r R相鄰各邊的權重。也就是說，預測值p表示存在一個固定的最優二分匹配，該匹配中的每個節點r R都與一條權重為pr的邊相鄰。于是，預測誤差就是取r R所有節點的最大預測誤差，并在所有最優匹配中最小化。這樣就實現了經典秘書問題中預測能力的泛化。這種類型的預測與頂點加權在線二分匹配問題高度對應 2。4 的研究顯示，對于任意 0和c d 1，在線二分匹配問題存在一種確定性算法，算法的期望競爭比漸近為gc,d,()，表示

77、為：式中，|為實例中最優（離線）匹配的基數。裝箱。裝箱是經典的優化問題，也是一個 NP 難問題。在裝箱問題的在線變種版本中，事先并不清楚物品集，物品是以序列的形式逐一呈現。一個新物品到達時，在線算法將其放入一個已打開的現有箱子中（以不超出箱子容量為前提），或放入一個新的箱子。假設每個物品的大小是1,k中的一個整數，k表示箱子的容量這也是 27,41,110 等許多有效裝箱算法所依賴的自然假設。此外，在不限制物品大小的前提下，88 的研究發現，如果在線算法輸出的大小建議與輸入的大小呈次線性關系，那么算法的競爭比不優于1.17（即使該建議為零誤差）。這一負面結果意味著，為了利用基于頻率的預測，需要

78、對物品大小進行限制?？紤]輸入序列。對于任意x 1,k，令nx,表示中大小為x的物品數量。定義fx,，表示中大小x的出現頻率，令該頻率等于nx,/n，于是有fx,0,1。算法使用這些頻率作為預測值。具體而言，對于每個大小x（x 1,k）在中的出現頻率，都有一個預測值，表示為fx,。預測會有誤差，所以通常情況下，fx,?=fx,。為量化預測誤差，令f和f分別表示中大小x的出現頻率及其預測值，也即 k 維空間中的點。根據前文有關預測式在線算法的研究（如 104），誤差即為f與f之間距離的 L1 范數。gc,()=max1ce,f(c)(max1+opt,0)if 0 gc,()=1ceif gc,d

79、,()=max1cln(cd),d12c(max1(+)|opt,0)if 0 1cln(cd)if 華為研究|642022 年 12 月度量任務系統。給定包含一系列狀態的度量空間M，其中的狀態可以解釋為動作、投資策略或者某種生產機器的配置。算法從預定義的初始狀態x0開始。在每個時間點t=1,2,.，有成本函數t:M R+0,+，算法的任務是決定要停留在狀態xt1并支付成本t(xt1)，還是要移動到（可能成本更低的）另一狀態xt并支付成本dist(xt1,xt)+t(xt)，其中dist(xt1,xt)表示在xt1和xt兩個狀態間遷移的成本。算法的目標是最小化隨時間推移所產生的總成本。在每個時

80、間點t，預測器都會針對算法在該時間點應處的狀態生成預測值pt。對于某個離線算法 OFF，預測誤差為：式中，ot表示 OFF 在時間點t所處的狀態，T表示輸入序列的長度。3 證明了兩種一般化的結果。其一，令A為-競爭的確定性在線算法，用于求解度量任務系統（Metrical Task System，MTS）問題P。存在一種求解問題P的預測式確定性算法，與任意離線算法 OFF 相比，該算法實現了9 min,1+4/OFF的競爭比，其中表示相對于OFF的預測誤差。其二，令A為-競爭的隨機在線算法，用于求解 MTS 問題P，問題的度量空間直徑為D。對于任意 1/4，存在一種求解問題P的預測式隨機算法，實

81、現低 于(1+)min,1+4/OFF OFF+O(D/)的 成本，其中表示相對于 OFF 的預測誤差。于是，若 OFF（近似）最優，且 OFF，則競爭比接近1+。=T?t=1t;t=dist(pt,ot)13.1.2 預測式流算法數據流模型是一種基礎模型，用于在內存有限的情況下快速處理海量數據集。60 研究了一種大流量對象神諭，能夠預測某個數據元的出現頻率是否高于給定閾值。研究表明，這種神諭可以應用于數據流中的廣泛問題。借助該神諭，研究人員獲得了此類問題的第一個最優界限，有時界限還突破了未使用該神諭時的已知下界。研究中還將該神諭用于流差異中離散元數量的計算、頻率矩的估計、級聯聚合的估計，以及

82、幾何數據流的矩估計。針對離散元問題，該技術能夠突破已知下界，從而得到一種新的空間最優算法。對于0 p 2時第p個頻率矩的估計，則實現了二次方量級的內存節省，突破了無神諭時的已知下界。設數據流模型中有基礎頻率向量x Zn，初始化為0n，該值隨著流的過程而演變。該流由形如(i,w)的更新組 成，即xi xi+w。設 流 的 過 程 中 有M，且 令|x|=maxi1,.,n|xi|M。在流的結尾處，要求為函數f:Zn R近似出函數f(x)。由于流的規模很大，多數算法采用近似和隨機的處理方式。通常做法是，算法輸出一個估計值Z，值的范圍為P(1 )f(x)Z (1+)f(x)2/3，式中的概率取決于算

83、法使用的隨機種子，而與輸入流的隨機性無關，即輸入流可能為最壞情況。以恒定次數獨立重復運行算法，并獲取中位數估計，可以將成功概率2/3替換為大于1/2的任意常數。算法的空間復雜度以比特為單位，目標在于減少存儲x所需的空間，使得實際所用空間顯著少于平凡n比特空間?？紤]在數據流模型下對以下公共函數f(x)進行估計。離散元：f(x)=|x|0，式中|x|0為x的非零坐標數量，定義為|x|0=|i:xi=0|。此數量用于拒絕服務（Denial of Service，DoS）攻擊的檢測和數據庫查詢的優化 61。Fp矩：f(x)=|x|pp，式 中x的p范 數 定 義 為|x|p=(?i|xi|p)1/p。

84、當0 p 2時，這些范數用于估計斜率和峰度 58。(k,p)級聯范數：該問題中，x是一個n d矩陣，可以 接 收 對 其 單 個 條 目 的 更 新，且 有f(x)=|x|k,p:=(?i(?j|xij|p)k/p)1/k。該 矩 陣 有助于對數據庫執行多個查詢 26,59。假設有一個大流量對象神諭，基于輸入i n，判斷流結尾處的xi是不是大流量對象，并輸出判斷的結果。大流量對象的定義因數據流問題的類型而異。神諭則分兩類，第一類指示|xi|T是否成立，第二類指示|xi|p1T|x|pp是否成立，其中T表示與問題關聯的預設閾值。我們將使用第一類神諭來處理離散元問題，而使用第二類神諭來處理所有其他

85、問題。在x的坐標存在增刪的情況下，要估計L0=|x|0，目前的最佳算法由 61 提出。61 的研究表明，基于訓練好的神諭，有一種算法可以得到(1 )-近似的L0，算法使用的空間為O(2(logn)log(1/)，成功概率至少為2/3，更新與上報時間為O(1)。61 還得出以下結果。在大流量對象神諭的完美假設下，可以在1 2因數內估計|x|pp，空間復雜度為O(4n1/21/plog(n)log(M)比特，成功概率至少為3/5?？紤]神諭給出錯誤預測的概率為 0。那么，在1 2因數內估計|x|pp時所需的空間，當=O(1/n)時 為O(4(n)1/21/plog(n)log(M)比特，否則為O(4

86、(n)12/plog(n)log(M)比特。這兩種保證都具有至少3/5的成功概率。65|華為研究2022 年 12 月軟件理論令0 p 2且0 1s|x|pp）。假設大流量對象神諭出錯的概率為=O?2log2(1/)log log(1/)?，那么也存在具有相同保證度的算法。對于級聯范數，設 0和k p 2為常數。存在一種隨機算法，以坐標增刪流的n d矩陣x為輸入，可以按至少2/3的概率將(1+)-近似的結果輸出到|x|k,p，使用的空間為O(n11kp2kd121p)。此外，在大流量對象神諭的假設下，存在一個矩形高效的單通流算法，當p 2時，以1 的概率將(1 )-近似的結果輸出到|x|pp。

87、處理流中的每個矩形時，使用的空間為O(d(1/21/p)比特，時間為O(d(1/21/p)。3.2 學習后優化3.2.1 基于樣本的優化本節回顧“學習后優化（Learning to Optimize）”的當前研究進展，考察了“基于樣本的優化”和“面向噪聲的優化”兩個主要研究方向。以下介紹這兩個方向涉及的數學模型，以及不同設定下的不可能結果和算法結果。本節將歷史數據看作從某個基礎分布中提取的樣本，目的是研究如何基于樣本數據來優化目標函數?？紤]以下形式的（約束）組合優化問題：maxSMf(S)式中，f:2N R為目標函數，M 2N為約束集合。假設存在值神諭Of，可以返回子集S N的值f(S)。為評

88、估用于優化的樣本的能力，Balkanski 等人 11 首次提出以下模型，稱之為基于樣本的優化（Optimization from Samples，OPS）。定義 3.1：OPS 模型給定函數f:2N R，設S:=Si,f(Si)ti=1為樣本的集合，其中每個Si都是從某個基礎分布D中抽取的獨立同分布樣本。給定參數 (0,1，若要使函數族F:2N R對于分布D和約束M是-可近似的，則需存在算法A，在給定誤差參數 (0,1)并以集合S為輸入的情況下，輸出結果S M并滿足：PrS1,.StDt?EAf(S)maxTMf(T)?1 1式中，被稱為近似比，t表示樣本復雜度。還需注意，此處并不要求A為多

89、項式算法，因為我們關注的是 OPS 模型下樣本的功效。顯然，分布D顯著影響F的可近似性。譬如，若D總是返回空集或固定的子集，則無法期望從樣本中學習到足夠的信息用于優化。因此，要考慮分布的“合理性”，并考察在查詢模型Of下可近似的函數到了 OPS 模型下是否仍然可近似，比如次模函數。為此，Balcan 等人 8 提出的 一 個 名 為 PMAC-可學 習 性（Probably Mostly Approximately Correct Learnability）的函數族進入了人們的視野。大體來說，若對于任意子集S D，可以通過樣本集合S高概率地學習到f(S)，則說函數f對于某個分布D是 PMAC-

90、可學習的。PMAC 包含大量的函數族，其中，OPS 模型下研究得最多的是覆蓋函數和影響函數。下面先介紹覆蓋函數的定義。定義 3.2：覆蓋最大化給定二分圖G=(L,R,E)，L和R分別表示左、右節點集，E表示L和R之間的邊集。覆蓋函數f:2L R0被定義為子集S L的鄰居數量，即f(S)=|N(S)|。覆蓋最大化問題在于選擇一個大小為k 1的子集S L，使得f(S)最大化，即maxSL:|S|=kf(S)。值得注意的是，覆蓋最大化問題是 PMAC-可學習的 6，在查詢模型下可采用(1 1/e)-近似貪心算法求解98。接下來介紹影響函數的定義?？梢哉J為，影響函數是覆蓋函數泛化后的一般有向圖，它在社

91、交網絡中應用甚廣。定義3.3：影響最大化給定有向圖G=(V,E,p)，V為節點集，E為邊集，pe為E中每條邊e E的概率向量，每個節點有已激活或未激活兩種狀態。給定種子集S0，令其在時間點t=0處于已激活狀態，接著按下述過程激活其他節點：首先，在時 間 點t=1,2,.，令St=St1。然 后，對 于 任 意v/St1，令Nin(v)表示節點集合u，且有(u,v)E。每個節點u Nin(v)(St1 St2)以概率puv獨立地激活v，最后將所有已激活節點v添加到St。當不再有新的節點 被 激 活 時，就 得 到 一 個 已 激 活 子 集 的 序 列S0 S1 S2。給定S0，定義(S0)為最

92、終已激活節點 的 集 合，并 將 影 響 函 數f:2V R定 義 為f(S)=E|(S)|即種子集S0的期望已激活數量。影響最大化問題在于選擇一個大小至多為k的種子集S，使f(S)最大化。華為研究|662022 年 12 月需要注意，覆蓋函數和影響函數都屬于次模函數。1OPS 模型可以自然地分成兩個步驟：1.基于具備 PMAC-可學習性保證的樣本，構造函數f，作為對f的估計。2.在查詢模型f下優化原有問題。不過，接下來我們會看到，雖然這兩個步驟都不難實現，但一旦組合起來可能就無法得到合理的（近似）算法。下面介紹目前在 OPS 模型下的不可能結果和算法結果，模型包含覆蓋最大化和影響最大化這兩個

93、問題。不可能結果。Balkanski 等人 11 首先研究了 OPS模型下的覆蓋最大化問題，提出以下定理。定理 3.4：覆蓋最大化問題的不可能結果 11對于任意分布D，覆蓋最大化算法的近似度不優于n1/4的緊界限，無法實現所觀察樣本數少于指數數量的目標。這一結果有些出乎意料，因為覆蓋最大化問題已被證明是 PMAC-可學習的 6。得出該結果的主要思路是構造一類函數，使這些函數從分布D的多數子集學習時可以獲得較好的學習效果，但不足以學習到（近似）最優解，如此一來，樣本就無法提供足夠的信息用于優化。不可能結果也存在于其他問題設定中。Balkanski 等人 12 構造了一類次模最小化問題f:2N 0

94、,1，并證明任何基于多項式樣本的算法都無法提供(1/2 O(1)加性近似。此結果可以擴展到凸最小化領域 13?？傮w而言，我們注意到，即使函數是 PMAC-可學習的，在查詢模型和 OPS 模型下的可近似性仍可能存在巨大的差別。為克服上述不可能結果，進一步研究的進展如下。算法結果。一般可以通過三種嘗試來獲得算法結果。第一種是假設f滿足額外屬性。例如，Balkanski 等人 10考察了曲率為c 0,1的單調次模函數。2通過研究，他們提供了一個緊的(1 c)/(1+c+c2)-近似算法。該算法符合我們對 OPS 模型下線性函數可求解的直覺。不過，覆蓋函數和影響函數的曲率都是1。對于影響最大化問題，B

95、alkanski 等人 9 假設社交網絡G由隨機塊模型生成，并提出一種常數近似算法?？傮w而言，這種嘗試并沒有改變 OPS 模型，因此，需要為不同的優化問題設計特定的屬性。第二種嘗試是弱化 OPS 模型的目標。Rosenfeld 等人 107 并未對整個函數進行優化，而是提出了一個基于樣本的分布性優化（Distributional Optimization from Samples，DOPS）模型。模型的目標是，對于從同一分布中抽取的一個較小樣本集合和另一個未知的較大樣本集合，可以基于這個較小集合，從較大集合中找到優化的樣本。該 研 究 證 明，在 DOPS 模 型 下，可 近 似 性 與 PM

96、AC-可學習性是等價的。這種嘗試為采樣模型下的 PMAC-可學習性提供了解釋。然而，我們可能仍希望對合理分布D找到全局最優解。第三種嘗試則假設我們不僅擁有樣本Si的值f(Si)，還獲得了額外的結構化信息。Chen 等人 23 首先針對覆蓋最大化問題，對這一方法開展了研究，提出以下基于結構 化 樣 本 的 優 化（Optimization from Structured Samples，OPSS）模 型。模 型 中，每 個 樣 本 由(Si,NG(Si)表示，NG(Si)為Si的鄰居集合。該研究證明，如果D滿足某項溫和的假設（比如D是某種均勻分布），那么可以為覆蓋最大化問題求得O(1)-近似的解

97、。此外，Chen 等人 24 還將這一結果擴展到影響最大化問題，問題中的各樣本表示為(Si,0,Si,1,.,Si,n1)，形式上由完整的傳遞路徑組成?；贒是乘積分布的假設，該研究提供了一個常數近似算法?？偨Y而言，額外的結構化信息可以彌補可學習性和可近似性之間的差距。另外，結構化信息因問題而異，因此考察適用于其他問題的結構化信息將有所裨益。3.2.2 面向噪聲的優化2曲率用于測量次模函數趨于線性的程度。曲率越接近 0，次模函數就越趨于線性。1 若對于任意S T N和u/T，有f(S u)f(S)f(T u)f(T)，則認為f是次模函數。如前文所述，OPS 模型下的主要困難似乎在于，可能無法基

98、于樣本估計來得到最優解的值。那么進一步的問題是，如果能對所有子集進行估計，是否就可以實現優化呢？這 就 引 出 另 一 研 究 方 向“面 向 噪 聲 的 優 化（Optimization with Noises）”，也即可以學習到函數f，作為基礎目標f的估計，使得對于任意S 2N，有f(S)(1 )f(S)。此處，(0,1)表示噪聲參數，值越小越好。要獲得f這個估計值，可以基于歷史樣本，通過神經網絡或構建草圖的方式來學習。出乎意料的是，即使得到了f，優化問題仍可能很難求解。下面討論誤差神諭（Erroneous Oracle）和噪聲神諭（Noisy Oracle）兩種設定下的情況。誤差神諭。H

99、assidim 等人 48 提出一個誤差神諭，對任意S 2N，有：f(S)=S f(S)式中，S 1 ,1+。此處，S可以由對手選擇。該研究證明了以下定理，表明使用誤差神諭很難求解次模最大化問題。67|華為研究2022 年 12 月軟件理論定理 3.5：使用誤差神諭時的不可能結果 48有誤差為的神諭。存在基數約束，使得對誤差神諭的查詢少于指數次。在此約束下，要使單調次模函數最大化，任何隨機算法都無法達到n0.5+的近似度。該研究的主要思路是構造函數f1和f2，兩個函數對于幾 乎 所 有 子 集S 2N都 互 相 近 似，比 如f1(S)(1 )f2(S)。因此，對手可以選擇噪聲參數S，使得對于

100、這些子集無法將f1和f2區分開來。然而，f1和f2的最優解值存在很大差異。Hassidim 等人 48 證明，在此設定中，多項式查詢數量不足以區分f1和f2。為消除這種不可能的結果，Hassidim 等人 48 提出一種噪聲神諭，它的S D是從獨立同分布中抽取的樣本，而非由對手選擇。該研究利用噪聲神諭，獲得了(1 1/e )的近似度。但是，算法所要求的查詢數量必須達到nO(1/)，復雜度仍有待降低。本節從“學習后優化”的兩個方向“基于樣本的優化”和“面向噪聲的優化”，回顧了相關研究進展。這些研究頗具啟發性，但仍然存在若干問題有待解決，譬如，需要有更合理的模型以消除不可能結果，現有算法結果的樣本

101、復雜度或查詢復雜度也有待降低。4 啟發式算法與機器學習的組合4.1 控制策略的學習接下來，我們介紹啟發式算法與機器學習的組合。與理論算法相比，在啟發式算法中運用機器學習時，可以認為啟發式算法是負責高階結構的控制，同時調用機器學習模型來輔助低階決策。圖 3 總結了這一學習增強框架。算法通常為解決某類一般性問題而設計，換句話說，可以從這類問題中獲取任意可求解的實例作為輸入，進而輸出所需的解。而且，理論研究通?；谒袉栴}實例的最壞情況來分析算法的屬性，如收斂速度和近似比。然而，對于實踐中的每個特定實例，算法的性能通常對算法參數和初始解的選擇非常敏感（如果沒有預先指定算法的初始解）。因此，很自然的思

102、路是，通過學習為算法找到針對具體實例的最佳控制策略，而無需改造算法本身。本節將這種方法命名為“學習增強算法（Learning Augmented Algorithm）”，并回顧相關研究進展。我們先介紹兩個具有代表性的研究方向“控制策略的學習”和“熱啟動的學習”，再探討被稱為“適應性學習增強”的新興方向。圖 3 組合優化算法會重復查詢同一機器學習模型以做出決策。機器學習模型以算法的當前狀態為輸入，算法可包含問題定義。算法的控制策略主要指超參數，例如迭代算法的更新率，或啟發式算法的搜索策略。本節介紹分支限界算法的一個應用示例，并總結與控制策略學習相關的其他類似學習增強算法。分支限界法簡稱 BnB（

103、Branch and Bound），主要是指求解離散優化問題的一種范式?？紤]基于可行集S來最小化實值函數f的問題，其中S是離散值。BnB 算法通常從單個根狀態開始，并維護一個已激活節點的隊列L，該隊列容納S的子集，同時用作目標的全局上下界。只要隊列L不為空，BnB 算法就使用某種節點選擇策略，每一步從L中彈出一個節點Si S，通過必要的松弛、并利用高效求解器，計算出受子集Si限制的目標界限。BnB 算法根據局部界限和全局界限來區分三種可能的情況：1.局部下界大于當前全局上界，這意味著，不可能通過進一步生成子集分支的方式來獲得更好的解，因而修剪掉該子樹（子集）。2.局部下界與局部上界匹配，則找到

104、受限于子樹（子集）內的最優解。3.否則，生成Si的所有分支，并將這些分支推回L。在情況 2 和 3 中，會相應更新全局上下界。當L為空或全局上下界的差距足夠小時，算法終止。BnB 算法最重要的控制策略是節點選擇策略，準確地說就是，如何從隊列中選擇下一個子集來計算界限并決定是否生成分支。通常來說，一個好的策略可以盡快找到最優解。這就是說，策略必須先選擇適當的分支子集，以便盡快找到好的解，并修剪掉多數不必要的子樹（子集）。有幾種策略在傳統的應用中很流行，包括眾所周知的先進華為研究|682022 年 12 月先出和后進先出策略，以及依賴另一優先級隊列的最佳優先策略按局部下界對節點排序就是其中一例。另

105、一種直接的思路是，利用訓練數據來處理待求解的問題，從而學習到一個好的策略。盡管問題和隊列都有定制化的表示，但自然的學習過程仍在于學習每個隊列中最可能的節點，從而找到問題實例的最優解。Bai 等人 7 應用了此范式來求解兩個輸入圖之間的 最 大 公 共 子 圖（Maximum Common Subgraph，MCS）。該研究把待分支的子集設計為輸入圖之間可能的節點對，利用強化學習，將所找到的公共子圖最大化，從而學習到這些節點對。Liu 等人 79 也考慮了類似的方法，將學習目標設置為最小化分支生成的次數。相比于基于端到端學習的 MCS 問題求解器，這兩種學習增強 BnB 算法都實現了更好的性能。

106、He 等人 49 應用了此范式來解決 MILP 問題。待分支的子集天然就是變量以及這些變量所屬的區域。除了學習每個狀態的恰當分支變量，該研究還學習到一個剪枝策略，用于預測最優解是否屬于某個子樹（子集）。剪枝策略進一步促進算法加速，由于已經預測出不包含最優解的多數子樹，因而可以忽略這些子樹的局部上下界計算。與面向 MILP 問題的 SOTA 求解器相比，這兩種控制策略的運用都使 BnB 算法在速度和最優間隙方面獲得了更好的性能。還有一些其他的研究路徑，針對 MILP 問題設計出不同的機器學習技術，學習到分支限界樹上每個節點所做的分支決策 68,80,52。類似地，針對 MILP 實例，Krube

107、r 等人 74 使用機器學習預先確定 Dantzig-Wolfe 分解的應用是否會有效。Bonami 等人 21 使用機器學習來確定對問題的線性化處理是否有助于更快地求解。機器學習還可以用于選擇 MILP 求解器和啟發式構建框架的攻擊性參數 62,85。此外，在二次規劃(Quadratic Programming，QP)領域，Baltean-Lugojan 等人 14 利用了機器學習來選擇合適的切割平面。缺點。學習到的控制策略通常由神經網絡表示，執行這些策略也會占用計算資源、需要時間預算。在提到的 BnB 示例中，算法每次決定一個分支節點時都會調用策略。這意味著，學習到的控制策略必須大幅提高原

108、有算法的性能，才能覆蓋額外的成本。4.2 熱啟動的學習然而，針對特定問題實例，熱啟動能夠預測恰當的初始解，這種能力肯定有助于提高算法的性能。例如，如果迭代算法的初始解足夠接近最優解，那么算法獲得最優解所需的時間自然就更少。這正是新近一些研究工作的出發點。這些工作基本上就是針對部分問題實例，基于訓練數據學習到預測模型，進而獲得問題的最優解。而其他工作中的問題實例則應用傳統算法，并使用熱啟動作為預測解。例如，Bemporad 和 Naikr 的論文 18，以及 Masti 和 Bemporad 的論文 86，都基于這一思路來學習 BnB 算法的熱啟動，從而求解 MILP 問題。Duan 等人 35

109、 將預測解作為熱啟動，應用于求解納什均衡的傳統算法，在計算效率和近似最優性方面都取得了相似的改進效果。缺點?！盁釂訉W習”所采用的方法，存在與“控制策略學習”共通的缺點，即在求解每個問題實例之前，都要進行額外的神經網絡推理。而且，針對特定算法學習最優熱啟動的研究甚少。從理論上講，尚不清楚是否初始解越接近最優解，相應的熱啟動就越好。相反方向的研究。一種有趣的觀點是，可以反過來把“熱啟動的學習”看作是傳統算法對機器學習的增強。例如，Li 等人 76 設計了一個學習框架來求解組合優化問題，主要涉及三個等效問題最大團（Maximum Clique，MC）、最大獨立集（Maximum Independe

110、nt Set，MIS）和最小頂點覆蓋（Minimum Vertex Cover，MVC）。這個學習框架為每個輸入實例輸出一組解，并運用局部搜索算法加以改進，最終找到最優解。然而，在 MC、MIS、MVC 的傳統求解器中，先使用簡單的方法生成初始解，然后運用局部搜索算法，是很常見的做法。換言之，這種學習方式其實就是為局部搜索學習到一組好的熱啟動。4.3 適應性學習增強雖然許多啟發式算法會將初始解構造為算法的第一個迭代步驟，但與控制策略相比，初始解的好壞似乎并不那么重要。類似情況也出現在許多算法的理論分析中。除專門用于識別初始解的算法以外，隨機初始化或任意較差初始化算法的收斂性和最優性通常都得到了

111、證明。前兩種學習增強方案可以看作是“靜態增強”，因為控制策略或熱啟動的學習模型在增強算法的運行過程中是固定的。最近一項工作 118 設計的學習過程則不同，它以每個問題實例為輸入，在算法運行過程中進行適應性地學習增強。本節簡要介紹這項工作所研究的問題、增強后的啟發式算法，以及對應的學習框架。旅行商問題定義為一個完整的無向圖，圖中每條邊都有一個成本，表示這條邊的兩個端點之間的距離。該問題在于找到一條哈密頓線路，使線路中各條邊的成本總和最小。LKH（Lin-Kernighan-Helsgaun）算法是一種基于局部搜索的著名啟發式算法，用于求解旅行商問題。LKH 算法從初始解開始搜索，迭代運行一種名為

112、k-opt 的特殊局部搜索技術。每個k-opt過程會考慮當前解的k條邊，測試這些邊的2k個端點之間的一系列其他k條連接，并使用最優選擇（最小總成本）來替換這k條邊。LKH 算法的69|華為研究2022 年 12 月軟件理論關鍵是根據值（及其擴展）來選擇這k條邊。此處忽略詳細的計算，人們通常認為，具有較小值的邊更有可能構成旅行商問題的最優解。Zheng 等人 118 設計了一個強化學習過程來取代 2-opt 過程。該過程基于值確定每條邊的初始 Q 值。之后每一步，系統的狀態為節點pi，采取的動作是根據 Q 值選擇該節點的一條鄰邊(pi,pi+1)，而后系統遷移到下一節點pi+2，該節點連接到原有

113、解中的pi+1（這個操作實際是將上一個解中的兩條邊(pi1,pi)和(pi+1,pi+2)替換為另兩條邊(pi,pi+1)和(pi+2,pi1)，而不影響解的可行性)。只要將每個狀態動作對的獎勵設置為解的改進程度，就可以通過標準強化學習來更新 Q 值。該方法結合了強化學習技術和傳統啟發式過程，與LKH 算法相比，在求解大型旅行商問題實例方面取得了更好的性能。Q 值作為值的增強，在這個過程中發揮了重要作用。Q 值具有適應性更新的優雅設計，這種設計一方面為學習增強提供了新的潛力，另一方面也依賴于大量有關問題結構和啟發式算法本身的領域信息。5 基于學習的機制設計5.1 拍賣設計中的機器學習本節的拍賣

114、設計問題圍繞以下設定展開討論。一個賣家，擁有一個m件物品的集合。一個n名競拍者的集合，競拍者具有獨立私人估值vi:2m R0，其中i=1,2,.,n。每個競拍者i的估值遵循已知分布vi Fi。一個拍賣機制，由分配規則g()和支付規則p()表示。當競拍者i出價bi、其他競拍者出價bi時：gi(bi,bi)表示物品分配給競拍者i的概率（向量）；pi(bi,bi)表示競拍者i需要支付的金額；于是，競拍者i的收益定義為 ui(vi,bi,bi)=vTi gi(bi,bi)pi(bi,bi)。設 計 一 種 機 制，使 得 在 以 下 約 束 下，期 望 收 入Ev1F1,.,vnFn?ipi(vi,v

115、i)達到最大化。激勵相容約束：i,vi,bi,vi,ui(vi,vi,vi)ui(vi,bi,vi)個體理性約束：i,vi,vi,ui(vi,vi,vi)0Myerson 95 提供了m=1時的收入最大化拍賣機制，但即使m=2，也不存在完整的解析解結果。之后的許多工作針對多件物品的設定來設計最優拍賣，設定中假設競拍者數量固定（通常為兩個），或估值分布的支撐集是有限的（僅包含兩個取值）。其他工作還研究了與最優收入具有恒定近似比的機制設計。Duetting 等人 36 首次引入深度神經網絡表示拍賣機制。這種表示方式把拍賣設計問題轉移到深度學習任務中，不僅近似地還原出已知的最優機制，而且在相應設定下

116、，獲得了比近似最優機制更多的期望收入。準確地說，神經網絡將分配規則g()和支付規則p()參數化為g()和p()。具體表達式寫作pi=i(vTi gi)，式中i 0,1，該 表 達 式 直 接 滿 足 個 體 理 性 約 束。激 勵 相 容 約 束 則 被 轉 移 到 一 組 損 失 函 數rgti=Ev1F1,.,vnFnmaxbiui(vi,bi,vi)ui(vi,vi,vi)中，函數表示每個參與者對不謊報的后悔程度。若對所有i，有rgti=0，則滿足激勵相容約束。于是，訓練過程會從已知 分 布 中 抽 樣 競 拍 者 估 值，合 并 負 值 期 望 收 入Ev1F1,.,vnFn?ipi(

117、vi,vi)與rgti，并使用隨機梯度下降法更新神經網絡的參數。Feng 等人 38 將上述方法應用到帶預算約束的設定中。Sakurai 等人 109 進一步引入防假名約束，利用類似激勵相容約束的損失函數，防止競拍者操縱虛假身份參與拍賣而從中獲益。Shen 等人 112 也采用類似的思路，使用了神經網絡參數化機制，但不同之處在于，該研究使機制設計可以看作算法設計的一個特殊過程，該過程認為參與者都是理性的。準確地說，可以定義一個算法，將特定問題的任意實例作為輸入，進而返回滿足某種預期屬性的輸出。而機制設計好之后，參與者為機制提供輸入實例，并從機制的輸出中受益。因此，在設計機制時，必須同時考慮機制

118、的目標和參與者謊報的激勵。機制設計的自然思路是給參與者設計一種博弈，使用參與者的動作作為輸入，使得博弈的納什均衡產生預期的輸出。幸運的是，根據著名的顯示原理，我們可以專注于真實機制的設計，真實機制會如實報告每個參與者的均衡策略。這是因為，當參與者運用均衡策略時，如果機制優化了一個目標，就會有一個等效的真實機制來采納參與者的真實報告并模擬最優機制。不過總的來說，機制仍然很難設計，尤其在各參與者報告多項輸入的場景中，這種困難體現得更為明顯。傳統的研究工作通常會為設計好的機制提供解析形式的實現，并從理論上證明其（近似）最優性。這在一定程度上限制了面向大規模問題的機制設計研究。有所不同的是，一個新興的

119、研究方向使用了深度神經網絡來表示復雜的機制，顯示出克服這種困難的潛力。本節將這個研究方向稱為“基于學習的機制設計”，并總結了新近的相關研究。我們首先介紹最具代表性的機制設計問題拍賣設計，也稱“與金錢有關的機制設計”，多數研究都與此相關。然后，在“與金錢無關的機制設計”方面，我們再介紹一些基于學習的應用。最后，我們探討了一種拍賣設計與機器學習的新組合。華為研究|702022 年 12 月用另一個網絡替代了與激勵相容約束相關的損失函數，新的網絡表示競拍者在給定機制下采取的最優動作。換言之，研究中并未采用顯示原理，轉而從一個更大的參數化空間中搜索最優拍賣機制。Rahme 等人 105 進一步將機制網

120、絡與競拍者網絡之間的互動建模為兩人博弈。另外，Cai 等人 22 對學習輔助式拍賣設計進行了動態擴展，研究了重復拍賣的情形，使得機制與競拍者都可以隨時間演進。然而，為了獲得令人信服的性能，他們將拍賣機制的設計空間限制為帶保留價的二價拍賣，并使用強化學習來找到每個時間周期中的最優保留價。最近，Liu 等人 78 還將基于學習的拍賣機制應用于廣告拍賣的現實場景中，拍賣中假定投標人的估值分布具有特定結構。其他相關工作。前文介紹的工作主要考察了基于學習的機制設計方法。另有大量論文研究了需要多少樣本才能通過理論分析學習到拍賣機制。這個問題更為基礎，本文不作相關工作的評述。5.2 金錢無關機制設計中的機器

121、學習6.1 組合優化與模式識別的比較5.3 面向學習式參與者的拍賣設計典型情況是，賣家反復拍賣同一類型的物品，而獨立買家（可能具有完全相同的估值分布）使用無悔學習算法來找到合理出價，從而實現長期收益的最大化（即最大限度地降低后悔程度）。Nekipelov 等人 97 首次開展了相關研究，針對二價拍賣，基于買家都是無悔學習者的假設，考察如何估計買家的出價。最近，Deng 等人 29 又考察了一價拍賣。一價拍賣尚無納什均衡的理論表征。該研究指出，存在一種無悔學習算法，可以讓買家獲得納什均衡。6 限制與挑戰上述拍賣機制是用分配規則和支付規則表示的，而很多其他的機制設計問題并不涉及支付規則。這類問題被

122、稱為與金錢無關的機制設計。由于這類機制設計不具備統一的設定，我們只介紹一項最近的工作，它研究了如何通過機器學習來增強機制設計。Golowich 等人 47 研究了設施選址問題，即政府要求參與者報告自己的位置，然后從中找到一個對所有參與者都有利的設施建造位置。該研究采取類似 38 的思路，將“選址規則”表示為神經網絡，以參與者的報告為輸入，進而輸出設施的選址。經過訓練，神經網絡會最小化設施位置與每個參與者之間的總（加權）距離。每個參與者謊報的激勵（謊報的目的是使設施位置盡可能靠近自己）轉換為訓練中使用的損失函數?？梢哉J為，拍賣設計是賣家設計博弈規則，買家參與博弈。前述工作主要使用機器學習來增強賣

123、家，同時假設買家是理性的，也就是說買家能夠找到自己的最優出價。確切地說，在收入最大化拍賣機制中，收入的定義是基于每個買家的出價都遵循納什均衡的假設，而顯示原理又將納什均衡進一步轉換為真實的出價。然而，在實踐中，買家可能無法找到這個均衡。因此，拍賣機制應用于現實世界之前，拍賣設計必須考慮非理性的買家，尤其是學習式參與者。引入機器學習方法求解組合優化問題，當前仍面臨一些限制與挑戰。本節先通過組合優化與模式識別的比較，引出組合優化中應用機器學習的若干困難。之后提出，在當前研究中，增強算法還有哪些屬性問題有待解決。下文通過與模式識別比較，總結機器學習引入到組合優化中所面臨的困難。1.難以構造高質量的訓

124、練數據集。如今，要訓練出性能良好的機器學習模型，通常需要大規模的訓練數據集，因此獲得高質量的數據集至關重要。在模式識別中，數據點通常由特征和標簽組成。有幾種成本可接受的方法可用來獲取訓練數據，比如雇傭人工來打標簽。但是，組合優化實例的標簽通常就是最優解。計算最優解的成本高昂，對于大規模實例尤其如此，而且不太可能像模式識別中那樣由人工來打“標簽”。因此，構建包含不同規模實例的高質量數據集是一大挑戰。2.對擾動和噪聲的敏感性。在模式識別中，魯棒性是對機器學習模型的一項關鍵要求，也就是說，機器學習模型不應對小的擾動或噪聲過于敏感。為提高所學到的機器學習模型的魯棒性，可以在維護標簽時輕微擾動訓練數據。

125、但是，組合優化問題卻具有很高的敏感性，即使微小的擾動或噪聲都可能對問題的最優解產生影響。以旅行商問題為例，添加單條邊就會改變最優解，比如圖 4 中，添加邊(A,D)導致最優解中一半的邊發生了改變。SAT 問題也存在同樣的敏感性，在問題中添加子句可能使可滿足狀態改變為不可滿足。此外，在 CSP 問題中，添加一條約束或從問題的約束關系中刪除一個元組，原本容易滿足的問題就可能變得難以滿足。組合優化的這種敏感性也導致難以構建高質量的訓練數據集，因為無法像模式識別那樣通過小的擾動來構建不同的實例。因此，我們希望學習到的機器學習模型能夠識別這種敏感性，但這一要求不同于模式識別，帶來很大的挑戰。71|華為研

126、究2022 年 12 月軟件理論6.2 增強算法的期望屬性將機器學習納入組合優化，盡管相關研究已取得一些進展，但在增強算法的設計上仍存在許多挑戰。挑戰體現在多個方面，包括組合優化的具體性質、對理論或啟發式方法缺乏理解，以及現實的需求。1.擴展性。構建大規模訓練數據的難度很大。因此，為組合優化問題訓練機器學習模型時，目前通常使用小規模的數據集，比如最多 1000 個變量。然而，研究人員仍希望設計出增強的算法，使算法在輸入規模較大時也具備良好的性能。這使機器學習模型的擴展性成為關注的焦點，在新近的幾次調研中 114,87,19，擴展性已被列為未來的研究方向。已有部分工作 111,68,90 嘗試擴

127、展到規模大得多的實例。不過，現有的很多增強框架并不具備良好的擴展性，當實例規模增加時，解的質量會迅速下降 114。2.適應性。與經典的組合優化問題不同，實際的應用場景通常涉及額外的目標或約束。為減少問題變化時重新設計算法的成本，學習到的增強框架應能適應問題集內的數據擾動，或適配同一問題族中的其他問題。已有一些初步工作 96 對機器學習模型的適應性開展了研究。3.理論保證。傳統的理論算法通常具有執行時間、近似比和泛化界限等方面的可證明保證。在引入機器學習算法時，應盡量不影響已有的理論保證，這樣可以提高所學模型的可解釋性，但要做到這一點挑戰很大。執行時間與模型性能一樣，都與算法的實現密切相關。增強

128、算法從設計上應減少算法運行時間，同時不影響輸出解的質量。已有初步研究 17,72 用更少的時間實現了相近的求解性能，提升了機器學習模型的效率。然而，這些研究提供的框架只能處理 100 個節點，遠未達到最先進的水平。圖 4 旅行商問題的敏感性示例近似比是對輸出解質量的理論保證。實現近似保證的一種方法是將近似算法與機器學習方法結合起來，例如在頂點覆蓋問題和旅行商問題 68 中的組合應用。然而，現有的組合通常只考慮基本的理論方法或啟發式方法，比如貪心算法或分支限界算法。因此有必要進一步考察其他近似算法，雖然這些算法可能更復雜，但它們具有更好的近似比。機器學習方法如果與更好的近似算法結合運用，可以提供

129、更佳的近似保證。泛化能力反映所學模型能否在其他一般性實例上表現良好，體現模型的實用價值。傳統理論算法考慮的是最壞情況界限，因而自然地滿足泛化要求。然而，機器學習學到的模型通常依賴特定的訓練數據集，其泛化能力就成為機器學習的重要課題。因此，有必要進一步研究，在引入機器學習方法的同時，如何保持模型的泛化能力。樣本復雜度與上述所有因素相關。樣本的數量通常決定訓練花費的時長以及所學模型的質量，模型質量又可能影響增強算法的近似比。此外，如果訓練數據和測試數據是從相同分布中提取的，那么泛化界限通常與從訓練數據集估得的基礎分布好壞程度有關，而這很大程度上取決于樣本復雜度。華為研究|722022 年 12 月

130、1 Dimitris Achlioptas,Marek Chrobak,and John Noga.Competitive analysis of randomized paging algorithms.Theoretical Computer Science,234(1-2):203218,2000.2 Gagan Aggarwal,Gagan Goel,Chinmay Karande,and Aranyak Mehta.Online vertex-weighted bipartite matching and single-bid budgeted allocations.In Proc

131、eedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms,pages 12531264.SIAM,2011.3 Antonios Antoniadis,Christian Coester,Marek Elias,Adam Polak,and Bertrand Simon.Online metric algorithms with untrusted predictions.In International Conference on Machine Learning,pages 345355.PM

132、LR,2020.4 Antonios Antoniadis,Themis Gouleakis,Pieter Kleer,and Pavel Kolev.Secretary and online matching problems with machine learned advice.In 34th Conference on Neural Information Processing Systems.Curran Associates,Inc.,2020.5 Sanjeev Arora.Polynomial time approximation schemes for Euclidean t

133、ravelling salesman and other geometric problems.Journal of the ACM(JACM),45(5):753782,1998.6 Ashwinkumar Badanidiyuru,Shahar Dobzinski,Hu Fu,Robert Kleinberg,Noam Nisan,and Tim Roughgarden.Sketching valuation functions.In Yuval Rabani,editor,Proceedings of the Twenty-Third Annual ACM-SIAM Symposium

134、on Discrete Algorithms,SODA 2012,Kyoto,Japan,January 17-19,2012,pages 10251035.7 Yunsheng Bai,Derek Xu,Alex Wang,Ken Gu,Xueqing Wu,Agustin Marinovic,Christopher Ro,Yizhou Sun,and Wei Wang.Glsearch:Maximum common subgraph detection via learning to search.CoRR,abs/2002.03129,2020.8 Maria-Florina Balca

135、n and Nicholas J.A.Harvey.Learning submodular functions.In Peter A.Flach,Tijl De Bie,and Nello Cristianini,editors,Machine Learning and Knowledge Discovery in Databases-European Conference,ECML PKDD 2012,Bristol,參考文獻UK,September 24-28,2012.Proceedings,Part II,volume 7524 of Lecture Notes in Computer

136、 Science,pages 846849.Springer,2012.9 Eric Balkanski,Nicole Immorlica,and Yaron Singer.The importance of communities for learning to influence.In Isabelle Guyon,Ulrike von Luxburg,Samy Bengio,Hanna M.Wallach,Rob Fergus,S.V.N.Vishwanathan,and Roman Garnett,editors,Advances in Neural Information Proce

137、ssing Systems 30:Annual Conference on Neural Information Processing Systems 2017,December 4-9,2017,Long Beach,CA,USA,pages 58625871,2017.10 Eric Balkanski,Aviad Rubinstein,and Yaron Singer.The power of optimization from samples.In Daniel D.Lee,Masashi Sugiyama,Ulrike von Luxburg,Isabelle Guyon,and R

138、oman Garnett,editors,Advances in Neural Information Processing Systems 29:Annual Conference on Neural Information Processing Systems 2016,December 5-10,2016,Barcelona,Spain,pages 40174025,2016.11 Eric Balkanski,Aviad Rubinstein,and Yaron Singer.The limitations of optimization from samples.In Hamed H

139、atami,Pierre McKenzie,and Valerie King,editors,Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing,STOC 2017,Montreal,QC,Canada,June 19-23,2017,pages 10161027.ACM,2017.12 Eric Balkanski and Yaron Singer.Minimizing a submodular function from samples.In Isabelle Guyon,Ulrike von

140、 Luxburg,Samy Bengio,Hanna M.Wallach,Rob Fergus,S.V.N.Vishwanathan,and Roman Garnett,editors,Advances in Neural Information Processing Systems 30:Annual Conference on Neural Information Processing Systems 2017,December 4-9,2017,Long Beach,CA,USA,pages 814822,2017.13 Eric Balkanski and Yaron Singer.T

141、he sample complexity of optimizing a convex function.In Satyen Kale and Ohad Shamir,editors,Proceedings of the 30th Conference on Learning Theory,COLT 2017,Amsterdam,The Netherlands,7-10 July 2017,volume 65 of Proceedings of Machine Learning Research,pages 275301.PMLR,2017.14 Radu Baltean-Lugojan,Pi

142、erre Bonami,Ruth Misener,73|華為研究2022 年 12 月軟件理論and Andrea Tramontani.Selecting cutting planes for quadratic semidefinite outer-approximation via trained neural networks.Technical Report,Imperial College,London,2018.15 Nikhil Bansal,Kedar Dhamdhere,Jochen Knemann,and Amitabh Sinha.Non-clairvoyant sch

143、eduling for minimizing mean slowdown.Algorithmica,40(4):305318,2004.16 Luca Becchetti and Stefano Leonardi.Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines.In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing,pages 94103,2001.17 I

144、rwan Bello,Hieu Pham,Quoc V.Le,Mohammad Norouzi,and Samy Bengio.Neural combinatorial optimization with reinforcement learning.In 5th International Conference on Learning Representations,ICLR 2017,Toulon,France,April 24-26,2017,Workshop Track Proceedings.OpenR,2017.18 Alberto Bemporad and Vihangkumar

145、 V.Naik.A numerically robust mixed-integer quadratic programming solver for embedded hybrid model predictive control.IFAC-PapersOnLine,51:412417,2018.19 Yoshua Bengio,Andrea Lodi,and Antoine Prouvost.Machine learning for combinatorial optimization:A methodological tour dhorizon.European Journal of O

146、perational Research,2020.20 Bernd Bischl,Pascal Kerschke,Lars Kotthoff,Marius Lindauer,Yuri Malitsky,Alexandre Frchette,Holger Hoos,Frank Hutter,Kevin Leyton-Brown,Kevin Tierney,et al.Aslib:A benchmark library for algorithm selection.Artificial Intelligence,237:4158,2016.21 Pierre Bonami,Andrea Lodi

147、,and Giulia Zarpellon.Learning a classification of mixed-integer quadratic programming problems.In International Conference on the Integration of Constraint Programming,Artificial Intelligence,and Operations Research,pages 595604.Springer,2018.22 Qingpeng Cai,Aris Filos-Ratsikas,Pingzhong Tang,and Y

148、iwei Zhang.Reinforcement mechanism design for e-commerce.In Proceedings of the 2018 World Wide Web Conference,WWW 18,page 13391348,Republic and Canton of Geneva,CHE,2018.International World Wide Web Conferences Steering Committee.23 Wei Chen,Xiaoming Sun,Jialin Zhang,and Zhijie Zhang.Optimization fr

149、om structured samples for coverage functions.In Proceedings of the 37th International Conference on Machine Learning,ICML 2020,13-18 July 2020,Virtual Event,volume 119 of Proceedings of Machine Learning Research,pages 17151724.PMLR,2020.24 Wei Chen,Xiaoming Sun,Jialin Zhang,and Zhijie Zhang.Network

150、inference and influence maximization from samples.In Marina Meila and Tong Zhang,editors,Proceedings of the 38th International Conference on Machine Learning,ICML 2021,18-24 July 2021,Virtual Event,volume 139 of Proceedings of Machine Learning Research,pages 17071716.PMLR,2021.25 Nicos Christofides.

151、Worst-case analysis of a new heuristic for the travelling salesman problem.Technical report,Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group,1976.26 Graham Cormode and S Muthukrishnan.Space efficient mining of multigraph streams.In Proceedings of the Twenty-Fourth ACM SIGMOD-SIG

152、ACT-SIGART Symposium on Principles of Database Systems,pages 271282,2005.27 Janos Csirik,David S Johnson,Claire Kenyon,James B Orlin,Peter W Shor,and Richard R Weber.On the sum-of-squares algorithm for bin packing.Journal of the ACM(JACM),53(1):165,2006.28 George B Dantzig.Maximization of a linear f

153、unction of variables subject to linear inequalities.Activity Analysis of Production and Allocation,13:339347,1951.29 Xiaotie Deng,Xinyan Hu,Tao Lin,and Weiqiang Zheng.Nash convergence of mean-based learning algorithms in first price auctions,2021.30 Michel Deudon,Pierre Cournut,Alexandre Lacoste,Yos

154、siri Adulyasak,and Louis-Martin Rousseau.Learning heuristics for the TSP by policy gradient.In International Conference on the Integration of Constraint Programming,Artificial Intelligence,and 華為研究|742022 年 12 月Operations Research,pages 170181.Springer,2018.31 Nikhil R Devanur and Thomas P Hayes.The

155、 adwords problem:Online keyword matching with budgeted bidders under random permutations.In Proceedings of the 10th ACM Conference on Electronic Commerce,pages 7178,2009.32 Marco Dorigo,Mauro Birattari,and Thomas Stutzle.Ant colony optimization.IEEE Computational Intelligence Magazine,1(4):2839,2006

156、.33 Marco Dorigo and Gianni Di Caro.Ant colony optimization:A new meta-heuristic.In Proceedings of the 1999 Congress on Evolutionary Computation-CEC99(Cat.No.99TH8406),volume 2,pages 14701477.IEEE,1999.34 Lu Duan,Haoyuan Hu,Yu Qian,Yu Gong,Xiaodong Zhang,Jiangwen Wei,and Yinghui Xu.A multi-task sele

157、cted learning approach for solving 3D flexible bin packing problem.In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems,pages 13861394,2019.35 Zhijian Duan,Dinghuai Zhang,Wenhan Huang,Yali Du,Yaodong Yang,Jun Wang,and Xiaotie Deng.PAC learnability of approx

158、imate Nash equilibrium in bimatrix games,2021.36 Paul Duetting,Zhe Feng,Harikrishna Narasimhan,David Parkes,and Sai Srivatsa Ravindranath.Optimal auctions through deep learning.In Kamalika Chaudhuri and Ruslan Salakhutdinov,editors,Proceedings of the 36th International Conference on Machine Learning

159、,volume 97 of Proceedings of Machine Learning Research,pages 17061715.PMLR,0915 Jun 2019.37 Evgenii Borisovich Dynkin.The optimum choice of the instant for stopping a Markov process.Soviet Mathematics,4:627629,1963.38 Zhe Feng,Harikrishna Narasimhan,and David C.Parkes.Deep learning for revenue-optim

160、al auctions with budgets.In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems,AAMAS 18,page 354362,Richland,SC,2018.International Foundation for Autonomous Agents and Multiagent Systems.39 Thomas A Feo and Mauricio GC Resende.Greedy randomized adaptive sear

161、ch procedures.Journal of Global Optimization,6(2):109133,1995.40 Merrill M Flood.The travelling-salesman problem.Operations Research,4(1):6175,1956.41 Alex S Fukunaga and Richard E Korf.Bin completion algorithms for multicontainer packing,knapsack,and covering problems.Journal of Artificial Intellig

162、ence Research,28:393429,2007.42 Fred Glover.Tabu search:part i.ORSA Journal on Computing,1(3):190206,1989.43 Fred Glover.Tabu search:part ii.ORSA Journal on Computing,2(1):432,1990.44 Fred Glover and Manuel Laguna.Tabu search.In Handbook of Combinatorial Optimization,pages 20932229.Springer,1998.45

163、Fred Glover,Manuel Laguna,and Rafael Mart.Fundamentals of scatter search and path relinking.Control and Cybernetics,29(3):653684,2000.46 David E Goldberg.Genetic Algorithms.Pearson Education India,2006.47 Noah Golowich,Harikrishna Narasimhan,and David C.Parkes.Deep learning for multi-facility locati

164、on mechanism design.In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence,IJCAI-18,pages 261267.International Joint Conferences on Artificial Intelligence Organization,7 2018.48 Avinatan Hassidim and Yaron Singer.Submodular optimization under noise.In Satyen

165、Kale and Ohad Shamir,editors,Proceedings of the 30th Conference on Learning Theory,COLT 2017,Amsterdam,The Netherlands,7-10 July 2017,volume 65 of Proceedings of Machine Learning Research,pages 10691122.PMLR,2017.49 He He,Hal Daume III,and Jason M Eisner.Learning to search in branch and bound algori

166、thms.In Z.Ghahramani,M.Welling,C.Cortes,N.Lawrence,and K.Q.Weinberger,editors,Advances in Neural Information Processing Systems,volume 27.Curran Associates,Inc.,2014.75|華為研究2022 年 12 月軟件理論50 Michael Held and Richard M Karp.A dynamic programming approach to sequencing problems.Journal of the Society

167、for Industrial and Applied mathematics,10(1):196210,1962.51 Holger H Hoos.Automated algorithm configuration and parameter tuning.In Autonomous Search,pages 3771.Springer,2011.52 Andre Hottung,Shunji Tanaka,and Kevin Tierney.Deep learning assisted heuristic tree search for the container pre-marshalli

168、ng problem.Computers&Operations Research,113:104781,2020.53 Chen-Yu Hsu,Piotr Indyk,Dina Katabi,and Ali Vakilian.Learning-based frequency estimation algorithms.In International Conference on Learning Representations,2018.54 Sungjin Im,Janardhan Kulkarni,and Kamesh Munagala.Competitive algorithms fro

169、m competitive equilibria:Non-clairvoyant scheduling under polyhedral constraints.Journal of the ACM(JACM),65(1):133,2017.55 Sungjin Im,Janardhan Kulkarni,Kamesh Munagala,and Kirk Pruhs.Selfishmigrate:A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors.In 2014 IEEE 55th Ann

170、ual Symposium on Foundations of Computer Science,pages 531540.IEEE,2014.56 Sungjin Im,Ravi Kumar,Mahshid Montazer Qaem,and Manish Purohit.Non-clairvoyant scheduling with predictions.In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures,pages 285294,2021.57 Piotr Ind

171、yk.Stable distributions,pseudorandom generators,embeddings,and data stream computation.Journal of the ACM(JACM),53(3):307323,2006.58 Piotr Indyk and David Woodruff.Optimal approximations of the frequency moments of data streams.In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of C

172、omputing,pages 202208,2005.59 Thathachar S Jayram and David P Woodruff.The data stream space complexity of cascaded norms.In 2009 50th Annual IEEE Symposium on Foundations of Computer Science,pages 765774.IEEE,2009.60 Tanqiu Jiang,Yi Li,Honghao Lin,Yisong Ruan,and David P Woodruff.Learning-augmented

173、 data stream algorithms.In International Conference on Learning Representations,2019.61 Daniel M Kane,Jelani Nelson,and David P Woodruff.An optimal algorithm for the distinct elements problem.In Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems,page

174、s 4152,2010.62 Daniel Karapetyan,Abraham P Punnen,and Andrew J Parkes.Markov chain methods for the bipartite boolean quadratic programming problem.European Journal of Operational Research,260(2):494506,2017.63 Anna R.Karlin,Mark S.Manasse,Lyle A.McGeoch,and Susan Owicki.Competitive randomized algori

175、thms for nonuniform problems.Algorithmica,11(6):542571,1994.64 Narendra Karmarkar.A new polynomial-time algorithm for linear programming.In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing,pages 302311,1984.65 Marek Karpinski,Michael Lampis,and Richard Schmied.New inapproxima

176、bility bounds for TSP.Journal of Computer and System Sciences,81(8):16651677,2015.66 Thomas Kesselheim,Klaus Radke,Andreas Tnnis,and Berthold Vcking.An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions.In European Symposium on Algorithms,pages 589600.S

177、pringer,2013.67 Leonid Genrikhovich Khachiyan.A polynomial algorithm in linear programming.In Doklady Akademii Nauk.Russian Academy of Sciences,1979.68 Elias Khalil,Hanjun Dai,Yuyu Zhang,Bistra Dilkina,and Le Song.Learning combinatorial optimization algorithms over graphs.In Advances in Neural Infor

178、mation Processing Systems,pages 63486358,2017.華為研究|762022 年 12 月69 Scott Kirkpatrick,C Daniel Gelatt,and Mario P Vecchi.Optimization by simulated annealing.Science,220(4598):671680,1983.70 Victor Klee and George J Minty.How good is the simplex algorithm.Inequalities,3(3):159175,1972.71 Wouter Kool,H

179、erke van Hoof,and Max Welling.Attention,learn to solve routing problems!In International Conference on Learning Representations,2018.72 Wouter Kool,Herke van Hoof,and Max Welling.Attention,learn to solve routing problems!In 7th International Conference on Learning Representations,ICLR 2019,New Orlea

180、ns,LA,USA,May 6-9,2019.OpenR,2019.73 Nitish Korula and Martin Pl.Algorithms for secretary problems on graphs and hypergraphs.In International Colloquium on Automata,Languages,and Programming,pages 508520.Springer,2009.74 Markus Kruber,Marco E Lbbecke,and Axel Parmentier.Learning when to use a decomp

181、osition.In International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems,pages 202210.Springer,2017.75 Eugene L Lawler.The travelling salesman problem:A guided tour of combinatorial optimization.Wiley-Interscience Series in Discrete Mathematics,19

182、85.76 Zhuwen Li,Qifeng Chen,and Vladlen Koltun.Combinatorial optimization with graph convolutional networks and guided tree search.In S.Bengio,H.Wallach,H.Larochelle,K.Grauman,N.Cesa-Bianchi,and R.Garnett,editors,Advances in Neural Information Processing Systems,volume 31.Curran Associates,Inc.,2018

183、.77 Denis V Lindley.Dynamic programming and decision theory.Journal of the Royal Statistical Society:Series C(Applied Statistics),10(1):3951,1961.78 Xiangyu Liu,Chuan Yu,Zhilin Zhang,Zhenzhe Zheng,Yu Rong,Hongtao Lv,Da Huo,Yiqing Wang,Dagui Chen,Jian Xu,Fan Wu,Guihai Chen,and Xiaoqiang Zhu.Neural au

184、ction:End-to-end learning of auction mechanisms for e-commerce advertising.KDD 21,page 33543364,New York,NY,USA,2021.Association for Computing Machinery.79 Yanli Liu,Chu-Min Li,Hua Jiang,and Kun He.A learning based branch and bound for maximum common subgraph related problems.Proceedings of the AAAI

185、 Conference on Artificial Intelligence,34:23922399,04 2020.80 Andrea Lodi and Giulia Zarpellon.On learning and branching:A survey.Top,25(2):207236,2017.81 Michele Lombardi and Michela Milano.Boosting combinatorial problem modeling with machine learning.arXiv preprint arXiv:1807.05517,2018.82 Helena

186、R Loureno,Olivier C Martin,and Thomas Sttzle.Iterated local search.In Handbook of Metaheuristics,pages 320353.Springer,2003.83 Thodoris Lykouris and Sergei Vassilvtiskii.Competitive caching with machine learned advice.In International Conference on Machine Learning,pages 32963305.PMLR,2018.84 Qiang

187、Ma,Suwen Ge,Danyang He,Darshan Thaker,and Iddo Drori.Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning.arXiv preprint arXiv:1911.04936,2019.85 Franco Mascia,Manuel Lpez-Ibez,Jrmie Dubois-Lacoste,and Thomas Sttzle.Grammar-based generation of stochastic local

188、 search heuristics through automatic algorithm configuration tools.Computers&Operations Research,51:190199,2014.86 Daniele Masti and Alberto Bemporad.Learning binary warm starts for multiparametric mixed-integer quadratic programming.pages 14941499,06 2019.87 Nina Mazyavkina,Sergey Sviridov,Sergei I

189、vanov,and Evgeny Burnaev.Reinforcement learning for combinatorial optimization:A survey.arXiv preprint arXiv:2003.03600,2020.88 Jesper W Mikkelsen.Randomization can be as helpful as a glimpse of the future in online computation.In 43rd International Colloquium on Automata,Languages,and Programming(I

190、CALP 2016).Schloss Dagstuhl-Leibniz-Zentrum fr Informatik,2016.77|華為研究2022 年 12 月軟件理論89 Joseph SB Mitchell.Guillotine subdivisions approximate polygonal subdivisions:A simple polynomial-time approximation scheme for geometric TSP,k-MST,and related problems.SIAM Journal on Computing,28(4):12981309,19

191、99.90 Akash Mittal,Anuj Dhawan,Sahil Manchanda,Sourav Medya,Sayan Ranu,and Ambuj Singh.Learning heuristics over large graphs via deep reinforcement learning.arXiv preprint arXiv:1903.03332,2019.91 Michael Mitzenmacher and Sergei Vassilvitskii.Algorithms with predictions.arXiv preprint arXiv:2006.091

192、23,2020.92 Nenad Mladenovi and Pierre Hansen.Variable neighborhood search.Computers&Operations Research,24(11):10971100,1997.93 Rajeev Motwani,Steven Phillips,and Eric Torng.Nonclairvoyant scheduling.Theoretical Computer Science,130(1):1747,1994.94 Katta G Murty.Computational complexity of parametri

193、c linear programming.Mathematical Programming,19(1):213219,1980.95 Roger B Myerson.Optimal auction design.Mathematics of Operations Research,6(1)5873,1981.96 Mohammadreza Nazari,Afshin Oroojlooy,Lawrence Snyder,and Martin Takc.Reinforcement learning for solving the vehicle routing problem.In Advance

194、s in Neural Information Processing Systems,pages 98399849,2018.97 Denis Nekipelov,Vasilis Syrgkanis,and Eva Tardos.Econometrics for learning agents.In Proceedings of the Sixteenth ACM Conference on Economics and Computation,EC 15,page 118,New York,NY,USA,2015.Association for Computing Machinery.98 G

195、eorge L.Nemhauser,Laurence A.Wolsey,and Marshall L.Fisher.An analysis of approximations for maximizing submodular set functions-I.Math.Program.,14(1):265294,1978.99 Alex Nowak,Soledad Villar,Afonso S Bandeira,and Joan Bruna.A note on learning algorithms for quadratic assignment with graph neural net

196、works.In Proceeding of the 34th International Conference on Machine Learning(ICML),volume 1050,page 22,2017.100 Pekka Orponen and Heikki Mannila.On Approximation Preserving Reductions:Complete Problems and Robust Measures.Citeseer,1987.101 Manfred Padberg and Giovanni Rinaldi.A branch-and-cut algori

197、thm for the resolution of large-scale symmetric travelling salesman problems.SIAM Review,33(1):60100,1991.102 Marcelo Prates,Pedro HC Avelar,Henrique Lemos,Luis C Lamb,and Moshe Y Vardi.Learning to solve NP-complete problems:A graph neural network for decision TSP.In Proceedings of the AAAI Conferen

198、ce on Artificial Intelligence,volume 33,pages 47314738,2019.103 Manish Purohit,Zoya Svitkina,and Ravi Kumar.Improving online algorithms via ML predictions.In Advances in Neural Information Processing Systems,pages 96619670,2018.104 Manish Purohit,Zoya Svitkina,and Ravi Kumar.Improving online algorit

199、hms via ML predictions.In S.Bengio,H.Wallach,H.Larochelle,K.Grauman,N.Cesa-Bianchi,and R.Garnett,editors,Advances in Neural Information Processing Systems,volume 31.Curran Associates,Inc.,2018.105 Jad Rahme,Samy Jelassi,and S.Matthew Weinberg.Auction learning as a two-player game.In International Co

200、nference on Learning Representations,2021.106 Dhruv Rohatgi.Near-optimal bounds for online caching with machine learned advice.In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms,pages 18341845.SIAM,2020.107 Nir Rosenfeld,Eric Balkanski,Amir Globerson,and Yaron Singer.L

201、earning to optimize combinatorial functions.In Jennifer G.Dy and Andreas Krause,editors,Proceedings of the 35th International Conference on Machine Learning,ICML 2018,Stockholmsmssan,Stockholm,Sweden,July 10-15,2018,volume 80 of Proceedings of Machine Learning Research,pages 43714380.華為研究|782022 年 1

202、2 月118 Jiongzhi Zheng,Kun He,Jianrong Zhou,Yan Jin,and Chu-Min Li.Combining reinforcement learning with Lin-Kernighan-Helsgaun algorithm for the traveling salesman problem.CoRR,abs/2012.04461,2020.108 Francesca Rossi,Peter van Beek,and Toby Walsh.Handbook of Constraint Programming(Foundations of Art

203、ificial Intelligence).Elsevier Science Inc.,USA,2006.109 Yuko Sakurai,Satoshi Oyama,Mingyu Guo,and Makoto Yokoo.Deep False-Name-Proof Auction Mechanisms,pages 594601.10 2019.110 Ethan L Schreiber and Richard E Korf.Improved bin completion for optimal bin packing and number partitioning.In Twenty-Thi

204、rd International Joint Conference on Artificial Intelligence,2013.111 Daniel Selsam,Matthew Lamm,Benedikt Bnz,Percy Liang,Leonardo de Moura,and David L Dill.Learning a SAT solver from single-bit supervision.arXiv preprint arXiv:1802.03685,2018.112 Weiran Shen,Pingzhong Tang,and Song Zuo.Automated Me

205、chanism Design via Neural Networks,page 215223.International Foundation for Autonomous Agents and Multiagent Systems,Richland,SC,2019.113 Daniel A Spielman and Shang-Hua Teng.Smoothed analysis of algorithms Why the simplex algorithm usually takes polynomial time.Journal of the ACM(JACM),51(3):385463

206、,2004.114 Natalia Vesselinova,Rebecca Steinert,Daniel F Perez-Ramirez,and Magnus Boman.Learning combinatorial optimization on graphs:A survey with applications to networking.arXiv preprint arXiv:2005.11081,2020.115 Alexander Wei.Better and simpler learning-augmented online caching.In Approximation,R

207、andomization,and Combinatorial Optimization.Algorithms and Techniques(APPROX/RANDOM 2020).Schloss Dagstuhl-Leibniz-Zentrum fr Informatik,2020.116 Gerhard J Woeginger.Exact algorithms for NP-hard problems:A survey.In Combinatorial Optimization:Eureka,You Shrink!,pages 185207.Springer,2003.117 Yaoxin

208、Wu,Wen Song,Zhiguang Cao,Jie Zhang,and Andrew Lim.Learning improvement heuristics for solving the travelling salesman problem.arXiv preprint arXiv:1912.05784,2019.79|華為研究2022 年 12 月軟件理論可滿足性（Boolean Satisfiability，SAT）問題在計算機科學中相當重要。很多啟發式算法可用于求解可滿足性問題，但這些算法基于實驗方式來評估，缺乏理論分析。本文將主要關注隨機游走（Random Walk，RW）技

209、術，并結合適應度函數，提升隨機游走的性能。這種改進版的 RW 被稱為 RWF。為了驗證 RWF 的性能，我們基于三種 SAT 表達式，分析比較了 RW、(1+1)EA（一種典型的演化算法）和 RWF 的期望運行時間。結果表明，RWF 在部分實例上的性能優于 RW 和(1+1)EA。關鍵詞布爾可滿足性，隨機游走，運行時間分析摘要蔡少偉，姜滔中國科學院軟件研究所計算機科學國家重點實驗室隨機游走與適應度函數相結合求解布爾可滿足性問題華為研究|802022 年 12 月1 引言布爾可滿足性（Boolean Satisfiability，SAT）問題是指，確定是否存在使給定命題表達式為真的變量賦值的問題

210、，是計算機科學中相當重要的一類問題。SAT 問題是第一個被證明為 NP 完全的問題，這意味著其他 NP 復雜度分類下的問題的求解難度不會超過 SAT 問題。除了理論上的重要地位，SAT 算法還在硬件驗證、密碼學、資源分配和規劃等領域有著廣泛的實際應用。SAT 問題在理論上極具挑戰性，尚無高效的求解算法。簡單窮舉算法可以窮盡n個變量的2n個取值，得到O(2n)的平凡邊界，但迄今還沒新的算法能突破這一界限。實際上，強指數時間假設（Strong Exponential Time Hypothesis，SETH）認為，當常數c fitness(x)，則 x:=y5:end while以下算法將 RW

211、方法和適應度函數相結合，是我們分析的重點。該算法每一步用一個適應值來引導搜索。算法 3 帶適應度函數的隨機游走(RWF)算法1:隨機選取一個初始比特串x；2:while 表達式未滿足 do 3:隨機選取一個未滿足的子句c；4:隨機選取c中的一個變量并翻轉其值，得到解y；5:若 fitness(y)fitness(x)，則 x:=y6:end while3.2 RW 與 RWF 算法對比本節分析了 RW 和 RWF 兩種算法求解兩個不同 SAT實例的時間復雜度（平均情況和最壞情況），以便從理論上認識這兩種算法。實 例 3.2.1 設x=(x1xn)0,1n，SAT 實 例1(x)定義為滿足條件的

212、賦值為(00)和(11)。命題 3.2.1 在 SAT 實例1上，RW 的期望運行時間為|m|1=(n2)。證明：參見12。命題 3.2.2 在 SAT 實例1上，RWF 的期望運行時間為|m|1=O(n)。證明：本文后續內容中，對于任意賦值x，用|x|來表示x中“1”的數量。根據式（1），1的適應度函數為fit1(x)=2(n 1)|x|,x=(0 )n 1+|x|1,x=(1 )1(x)=(x1 x2)(x1 xn)(x1 x2)(x1 xn)fit(x)=c1(x)+c2(x)+cm(x)(1)華為研究|822022 年 12 月該 適 應 度 函 數 只 與x1和|x|相 關。具 體

213、來 說，若x=(0 )，函數隨|x|單調下降，否則單調增加。圖 1為n=20時適應度函數fit1(x)的圖像。簡單起見，設n為偶數。將搜索空間S劃分為2n個子空間：令Xt 0,1n(t=0,1,.)為隨機變量，用于表示RWF 算法求解 SAT 實例1時，在時間t所處的狀態，則轉移概率描述如下。當k=0，有 當1 k n2 1，對于Xt S0,k，未滿足子句的形式為x1 xi。若算法使x1為 1，適應度函數下降，該突變不會被保留。當n2 k n 1，對于 Xt S0,k，未滿足子句的形式為x1 xi。如果算法使x1為 1，適應度函數上升，該突變將被保留。圖 1 n=20的適應度函數fit1(x)

214、S0,k=x|x=(0 ),|x|=k(k=0,.,n 1)S1,k=x|x=(1 ),|x|=k(k=1,.,n)P(Xt+1 S0,k|Xt S0,k)=12P(Xt+1 S0,k1|Xt S0,k)=12P(Xt+1 S0,k|Xt S0,k)=1P(Xt+1 S0,k1|Xt S0,k)=12P(Xt+1 S1,k+1|Xt S0,k)=12同理可得：當k=n，有當n2+1 k n 1，有當1 k n2，有引入具有狀態空間z0,0,z0,1,.,z0,n1;z1,1,z1,2,.,z1,n的輔助齊次馬爾可夫鏈Zt(t=0,1,.)，則轉移概率定義為式中，u,v 0,1且h,k 0,.,

215、n。此時，Zt就是一個吸收馬爾可夫鏈，其吸收狀態為z0,0和z1,n。對于任意x Su,k(u 0,1,k 0,.,n)，平均首次到達時間mx等于mzu,k。根據吸收馬爾可夫鏈理論，隨機過程Zt的平均首次到達時間表示為接下來，需要證明m0,k 2kn2 k n 1當k=n2，有P(Xt+1 S1,k|Xt S1,k)=1P(Xt+1 S1,k|Xt S1,k)=12P(Xt+1 S1,k+1|Xt S1,k)=12P(Xt+1 S0,k1|Xt S1,k)=12P(Xt+1 S1,k+1|Xt S1,k)=12P(Zt+1=zv,h|Zt=zu,k)=P(Xt+1 Sv,h|Xt Su,k)m

216、0,k=2k1 k n2 1m0,k=12(m0,k1+1)+12(m1,k+1+1)n2 k n 1m1,k=2(n k)n2+1 k n 1m1,k,=12(m0,k1+1)+12(m1,k+1+1)1 k n2m0,n2=12(m0,n21+1)+12(m1,n2+1+1)=12(2(n2 1)+1)+12(2(n2 1)+1)=n 1式中83|華為研究2022 年 12 月軟件理論對于|x|=k，SAT 實例2的適應度函數為該函數是一個關于k的二階多項式。如果 RWF 選取的初始解為x(|x|n 12)，根據 RWF 的搜索過程，可得到局部最優解(0,.,0)，而非全局最優解(1,.,

217、1)。當k n 12時，始于Sk的 RWF 算法永遠無法達到滿足條件的賦值(1,.,1)，因為適應度隨著|x|的增加而降低。當k n 12，有根據期望的定義：至此，證明結束。先前的結果中，RWF 在 SAT 實例1上的期望運行時間優于 RW。而在 SAT 實例2上，RW 的期望運行時間優于 RWF，與先前的結果相反。我們注意到，用 RW 算法求解 SAT 問題，求解過程的分析高度依賴于適應度函數。由于適應度函數表達式在書寫上存在障礙，對于一般性 SAT 問題的求解，要分析RWF 算法的期望運行時間非常困難。接下來，我們構造一個 SAT 實例3(x)，在不書寫適應度函數表達式的情況下來分析 RW

218、F 算法的期望運行時間。3.3 RW、局部(1+1)EA 和 RWF 算法對比實例 3.3.1 對于x=(x1xn)0,1n，SAT 實例3(x)由以下子句構成：(x1 x2),(x1 xn),(x1 x2)(x1 xn),(x1 x2),(x1 xn),(x1 x2)(x1 xn),可得k=n2時，m0,k 2k成立。假設k n2時該結論也成立（即m0,k 2k），則有進而可得m0,k+1 k+n k 1 2(k+1)k n2對于m1,k，可得出類似結論，概括如下：因此，|m|1=O(n)。對于 SAT 實例1，RWF 的期望運行時間邊界O(n)優于 RW 的O(n2)。然而，下面另一個 S

219、AT 實例2中，在一定條件下會出現相反的結果。實例 3.2.2 SAT 實例2具有以下子句xi,xi xji,j 1,.,n,i=jSAT 實例2唯一滿足條件的賦值為(1,.,1)。命題 3.2.3 對于 SAT 實例2，RW 的期望運行時間為|m|=(n2)。證明：參見 12。命題 3.2.4 RWF 在 SAT 實例2上的期望運行時間為證明：首先，將搜索空間劃分為n+1個子空間：滿足條件的集合為Sn。m0,k+1=12(m0,k+1)+12(m1,k+2+1)=12m0,k+n k 1m0,k 2k0 k n 1m1,k 2(n k)1 k nmi=+,i Product-Profit-P

220、roject）這樣的商業閉環，并不斷推動開源的可持續發展。當今企業擁抱開源已經不單純是為了降低成本、快速開發新產品盡管這還是很多企業的主要動機（圖 1）近年來，隨著生態經濟、行業數字化轉型、軟件定義一切的發展，越來越多的企業希望通過主動開源來加速上述目標的實現（圖 2）。1 引言2 開源策略的制定2.1 要素一：商業模式圖 1 OSSRA 各行業使用開源占比圖 2 垂直行業主動開源占比本文從企業開源策略的制定、企業級開源社區的構建等方面闡述企業如何利用開源來發展生態經濟、推動行業數字化轉型，并提出面向社區開發者和管理者的社區度量方法，以支撐企業構建高成長性、高粘性的開源社區，實現其開源戰略。一

221、般情況下，開源策略的制定需要考慮如下六個要素3：商業模式、知識產權策略、開源技術策略、項目治理與社區平臺策略、生態構建策略、成功度衡量。在這六個維度中，前五個將是本節闡述的主要內容，而最后一個維度則在第 3 節“社區構建的度量”中著重闡述。開源要支撐怎樣的商業模式，如何進行商業變現，這是支撐其他要素的基礎，因此需要首先確定下來。企業開源不可能是做慈善，沒有商業變現的支撐，就無法保證持續的投入與發展。業界的開源通常支持以下幾種商業模式：軟件訂閱與支持：售賣圍繞開源代碼的訂閱服務并提供商業支持，如紅帽企業 Linux（Red Hat Enterprise Linux，RHEL）、Pivotal C

222、loud Foundry；特性增強并收費：開源基礎版本，但對專有代碼的附加組件進行收費，如 GitLab Enterprise 以及大量設備商的產品，包括華為的高斯 DB 和基于 OpenStack、K8S 等開源軟件構建的商業軟件。關聯產品（引流模式）：通過開源軟件增加用戶觸達，并為其他業務導流，例如，安卓開源項目（Android Open Source Project，AOSP）及 Mozilla Firefox項目為 Google 搜索等業務提供導流。軟件雙許可：一般同一軟件會有一個免費許可，具備傳染性的 copyleft 開源許可，如 GNU GPL（General Public Li

223、cense），用于吸引廣大用戶及共建者；另一個則是私有軟件許可，收費，但用戶可以不受開源許可證（比如 GNU GPL）的限制，并享受商業公司提供的 SLA 保障與服務，如 Linux 桌面系統 Qt。（云）服 務：以 云 服 務 的 方 式 售 賣 開 源 軟 件，如 Amazon OpenSearch Service、Google Kubernetes Engine 等；硬件：售賣硬件產品，但將硬件相關軟件開源，以吸引并方便開發者使用，例如 Intel Clear Linux 開源項目對 Intel x86 CPU 的支持與使能。華為研究|1042022 年 12 月值得注意的是，開源項目不

224、等于商業產品，哪怕產品的軟件源碼與開源項目完全一致。商業產品基于開源項目構筑商業模式時需做如下考慮：相對于開源項目，產品要有足夠的商業價值；相對于開源項目，產品需要更明確的定位；產品要和開源項目中的軟件競爭；不同的公司將使用相同的開源項目軟件進行競爭。這里以 RHEL 為例來說明以上幾點。RHEL 的所有源碼均來自于上游社區RHEL 一直秉承著“上游優先”甚至“上游 Only”的原則，即使是自己開發的特性，也會先合入上游社區再拉取回 RHEL 產品。第一，獨特的商業價值。Linux 的服務器操作系統非常復雜，RHEL 通過訂閱與支持為客戶在使用、管理、配置、維護等方面提供企業級服務，以及豐富的

225、南北向認證，這是開源項目無法提供的獨特商業價值。第二，明確的產品定位。RHEL 將企業所關注的操作系統穩定性、長期維護及支持與社區先進特性綜合在一起，實現二者之間的均衡，這與上游開源項目本身主要關注新特性開發以及有限版本、較短時長的維護相比，產品定位更加明確，也更貼近企業用戶需求。第三，盡管 RHEL 相比上游社區項目具有獨特的價值與定位，但難免還是會有用戶直接從上游社區項目獲取軟件，自己集成、安裝、維護。RHEL 的做法是與其任由這些用戶自由發展，還不如基于 RHEL 版本構建（收購）CentOS 社區，去除所有 RHEL 的商標痕跡，并定期維護、更新 RHEL。用戶不僅可以享受到與 RHE

226、L 基本等同的產品質量與維護，而且不用支付任何費用。表面上看，CentOS 似乎與 RHEL 形成了競爭，但實際上它吸引并留存了 RHEL 的潛在客戶，也防止了相當數量的用戶流向自下載構建操作系統或流向競爭對手。第四，與其他基于相同開源項目的產品競爭。在 Linux商業發行版這個領域內，除了 RHEL，還有 SUSE Linux Enterprise、Ubuntu 等競品，因此 RHEL 也需要應對來自于這些產品的挑戰。這些產品依賴同樣的開源項目，因此在特性上大同小異，但在長期競合中逐漸形成了各自的客戶群及生態系統。雖然 RHEL 一家獨大，但也能長期共存。2.2 要素二：知識產權策略開源軟件

227、擁有完整的知識產權屬性，因此一般意義上的公有領域（Public Domain）的智力成果不是開源軟件，因為沒有與之相關聯的知識產權。開源軟件知識產權的制定涉及專業的法律問題，因此就如何制定知識產權策略，本文不會提供任何具體的指導。讀者可以從如下 4 個維度進行思考，并以此為切入點向知識產權律師或法務專業人員提出訴求，以制定相關策略：開源許可證主動對外開源的開源軟件必須選定一個許可證（為適配不同的應用場景或與不同的開源軟件集成，有時同一個開源軟件也可能選擇多個許可證）。一般而言，一旦軟件首創者選定了某個開源許可證，后續其他貢獻者貢獻的代碼也自然會采用選定的這個許可證。但有一種情況比較特殊，就是集

228、成發行版。以 openEuler為例，其作為操作系統的發行版，集成了數千款原生上游社區已有的開源軟件。這些軟件的許可證可能存在差異，因此，許可證是否兼容就決定了這些軟件能否集成到一起?？紤]到開發者后續可能還會引入新的開源軟件以增強操作系統功能，許可證的合規策略一般還會逐單審視、定期刷新。一般集成發行版社區都會采取許可證黑白名單方式，如 Fedora、openEuler社區都有類似機制（https:/fedoraproject.org/wiki/Licensing:Main#Good_Licenses）。此外，開源許可證還存在一些其他挑戰，包括：軟件中殘缺許可證的識別、許可證應用顆粒度的多樣性（

229、軟件級、模塊級、文件級）、許可證場景的多樣性（同一許可證在用戶態/內核態、靜態鏈接/動態鏈接等不同場景下的權利和義務也不相同）、軟件許可證變更等。這些都需要相關的工具系統（https:/compliance.openeuler.org/）及法律專業人員的深度介入。著作權開源軟件不論是托管給開源基金會進行開放治理還是由公司控制治理，著作權所有權（ownership）一般歸屬于原創開發者或其雇傭者，不會隨開源貢獻而發生轉移。開源只是在許可證或其他類似貢獻者協議（CLA 或 DCO）的約束下，賦予使用者（包括開源基金會）非常廣泛的著作權權利，比如使用、復制、分發、修改等，有時這些權利甚至是永久的、非

230、排他的、不可召回的（詳情可以參考各開源許可證文本及 OSI對于開源軟件的定義），但這并不意味著將著作權所有權轉移給了其他人。尤其是當原創者或原創企業將開源軟件捐贈給開源基金會進行開放治理的時候，這點往往會引起一些誤解。這也是各大主流開源基金會所形成的實踐（包括但不限于 Linux 基金會、Apache基金會、OpenStack 基金會等）。當然，也有一些開源基金會要求轉移著作權，FSF 就是如此（https:/www.gnu.org/licenses/why-assign.en.html），但這更多是出于“軟件自由”的理念以及維權便利性的考慮，而非業界（尤其是大企業）主動采用的開源著作權策略。

231、這里要特別指出，即便是在 FSF，這種著作權的轉移也不是強制的，只有當貢獻者希望由FSF 全權處理維權時才會轉移著作權。近來，我們105|華為研究2022 年 12 月軟件技術與生態2.3 要素三：開源技術策略2.4 要素四：項目治理與社區平臺策略也看到 FSF 旗下的一些項目已經取消了這一策略，例如 GCC 已不再要求轉移著作權（https:/news.slashdot.org/story/21/06/05/0246247/gcc-will-no-longer-require-copyrights-be-assigned-to-the-fsf）。專利權 有些許可證有明確的專利免費使用授權，要

232、注意由于開源而喪失專利起訴權利的場景；對于我方重點布局的專利領域，貢獻開源及參與開源需要謹慎。最徹底的專利隔離方式是成立獨立公司（如高通、愛立信、微軟），專職做開源貢獻。商標 如果開源項目捐贈給了開源基金會，項目商標的所有權一般也會轉移；項目商標與產品商標若存在沖突，在貢獻給基金會前要提前準備好新的項目商標；項目商標的使用權，尤其在開放治理的場景下（托管給基金會），一般會對所有使用者一視同仁，無法保留專有權利。開源技術策略分兩個維度：技術賣點當前開源項目數不勝數，如何在眾多項目中脫穎而出，關鍵在于技術競爭力及先進性。要解決真實世界的問題：從無到有（O3DE）：在開放 3D 引擎（Open 3D

233、 Engine，O3DE）引入之前，市場上主流的商業軟件都是閉源的，有限的幾款開源引擎要么是 2D 引擎，要么無法提供 AAA 級游戲主機畫面質量。AWS 在收購 CryEngine 代碼后重新進行改造、增強并開源，希望打破原有產業格局并快速牽引 O3DE 算力上云。從有到優（AOSP）：AOSP 出現之前，基于Linux的移動操作系統有幾大痛點，包括但不限于：1）關鍵組件缺乏高質量的開源軟件（如電話子系統 RIL、瀏覽器、Java 虛擬機等都需要從商業公司購買）；2）各開源組件版本及選型碎片化嚴重，無法形成統一的應用開發接口，上層應用開發無法歸一化，也沒有統一的應用市場進行應用分發與變現；3

234、）沒有對接新興的云服務（如地圖、搜索服務等）；4）不具備當時代表了下一代操控體驗（電容觸屏滑動體驗）的MMI（iPhone已具備），或需要自己開發或購買第三方組件。而 AOSP 的推出解決了上述所有問題，因此迅速吸引了大量南北向開發者，生態快速成長。巨大愿景（ECOMP）：電信網絡云化，見圖 3。圖 3 電信網絡云化的愿景 開什么、閉什么以RHEL為例，基于“上游優先”、“上游Only”原則，RHEL 的代碼完全來自上游社區，要如何構筑差異化競爭力呢？因此，RHEL 對如下內容不做開源：構 建 工 具 鏈，包 括 編 譯 選 項（形 成 競 爭 力 1：RHEL 商業版本的二進制優化能力）；打

235、造測試集及相關工具（形成競爭力 2：RHEL商業版本的缺陷解決效率）。項目治理：分為開放治理、封閉治理兩種方式，圖 4中橫軸代表參與者更多是個人導向還是公司導向，以及社區是否接受來自所屬公司以外的開發者，與是否由公司控制并無耦合關系 3。代碼工程與社區運營平臺：包括代碼托管及相關的軟件工程、運營平臺工具（DevOps 流水線、CICD、貢獻檢查及門禁、開發者門戶、官網等），見圖 5。圖 4 開放治理模型華為研究|1062022 年 12 月有些工具可能存在業務連續性風險，常見的遷移策略包括：商業工具/服務逐步切換成可信供應商；開源組件轉國內商業服務；風險開源組件逐漸形成獨立維護與演進。圖 5

236、代碼工程與社區運營平臺2.5 要素五：生態構建策略作為社區的主導者，我們需要引導不同類型的生態伙伴發現參與社區的價值，這里針對 4 種常見類型的生態伙伴分別給出對應的策略 3：用戶：通過增加采用量來發展用戶生態系統；針對以用戶為中心的項目，創建一個完整的發行版；專注于推動下載，集成到其他開源生態系統中去。開發者：通常情況下，最好是將開源項目貢獻給開源基金會，以實現開放治理，吸引更多開發者參與進來。專注于框架、平臺或工具，而不是完整的發行版，這樣有助于提高開發者的生產力；專注于與其他開源開發的輕松整合。其他公司（含友商）：選擇現有的基金會，減少他人加入所帶來的法務工作。先以項目開發為主，而后建立

237、社區適配，例如：Kubernetes-CNCF，OpenStack-OpenStack 基金會，Ceph-Ceph 基金會，Apache 孵化器-Apache 項目。通 過 優 秀 的 觀 眾 渠 道 啟 動 項 目，例 如，Kubernetes 是 在 2014 年 的 DockerCon 大 會上 啟 動 的，而 OpenStack 則 是 在 2010 年 的OSCON 開源大會上啟動的。107|華為研究2022 年 12 月軟件技術與生態圖 6 OpenDayLight 項目的貢獻主體示意圖2.6 要素六：成功度衡量3 社區構建的度量3.1 社區度量的兩個角度 在組建前先宣布組建意向，

238、以招募成員。例如，Linux 基 金 會 曾 于 2015 年 宣 布 其 組 建Hyperledger的意向，但在次年才正式啟動組建。與供應商一起招募終端用戶，確保項目能提供價值并得到推廣。例如，Hyperledger 項目就是與 CME Group、Deutsche Brse、State Street、Wells Fargo 等聯手推出的。預先與其他公司溝通并就架構主導與看護達成一致（圖 6 以 Cisco OpenDayLight 項目為例）。成員 活動 貢獻者 培訓 開發者活躍度 下游項目“社區”指的是一群因共同利益而聚集在一起的人或組織。從根本上來說，創建一個成功的社區就是創建一個生

239、態系統，成員們可以在社區中從事有意義的工作，快速提升自我，保持持續成長的動力，這樣的社區才能長盛不衰。在確定了項目開源策略之后，就可以對外發布并建立社區了，最終目標是建立一個高成長性、高粘性的可持續發展的開源社區。當然在社區構建和運營過程中，會面臨許多問題，例如社區 Issue 長時間無人答復、開發者滿意度差、開發者流失等。要解決這些問題，就必須構建一套完善的社區度量體系。社區度量的意義在于衡量社區是否達成了既定的階段性目標。具體說來，需要制定有效的量化方案，根據度量標準設計合理的預期，及時洞察度量結果以制定改進方案，確保社區健康的發展。一個社區是否成功，可以從兩個角度來衡量：一個是開發者角度

240、，一個是社區管理者角度。標準與產業組織 開源的參考實現（EFSP(JCP)-Jakarta EE）開源引領標準化（Docker-OCI）成功度衡量可以從最終商業結果與社區發展過程這兩個維度進行。商業結果度量維度相對簡單，也是閉環開源策略制定與執行效果的終極度量，但往往需要較長時間才能得出結果，不利于掌握過程并及時進行調整。圍繞社區發展過程這個維度，本節主要給出一些常用的中間態結果度量，并指出其對后續商業決策的潛在影響：用戶數度量（網站 portal 或用戶調查）：用戶數或者下載量 社區大小 用戶數或者公司數（公司 X 下載了我們項目 200次，所以我們可以嘗試將產品賣給它）用戶的地理位置（中國

241、區的用戶下載量占 30%，所以我們應該在中國區開設一個銷售辦事處）其他生態活動度量（基金會度量平臺或社區洞察 工具）：3.2 面向開發者的度量社區的核心力量是社區成員，而開發者又是社區成員中最關鍵的角色，高效的開發者是社區成功的關鍵因素之一。為了建立面向開發者的度量，我們先簡要闡述構建成員畫像的幾個基本原則 6：根據社區的愿景使命及階段性目標，確定主要成員的畫像類型，如用戶畫像、布道者畫像、活動組織者畫像、Issue 支持者畫像、開發者畫像等，有些畫像的角色可能是重疊的。由于構建畫像需要耗費大量人力，我們應該更關注畫像類型的質量而不是數量。在構建成員畫像時，需要重點關注以下幾個要素：能力、經驗

242、、動機、關心的事情、期待的獎勵以及關注的領域。下面我們將詳細介紹構建開發者畫像的過程。華為研究|1082022 年 12 月3.2.1 構建開發者畫像3.2.2 建立開發者社區的參與旅程框架開發者畫像是用戶畫像技術在社區開發場景中的一種實踐。開發者畫像通常由社區開發者的多項特征以及與其他開發者的關聯關系構成：開發者特征通常是一系列的標簽。如圖 7 所示，我們可以通過標簽來代表一位開發者在社區中所展現出來的技能特征。圖 7 開發者技能云圖 8 一名開發者參與貢獻的所有項目標簽集合圖 9 開發者關系圖譜開發者關系圖譜通?？梢苑譃樯缃魂P系、直接協作關系和間接協作關系 4。每種關系下又包含了詳細的協作

243、關系，關系類型和關系強度將視為協作關系的屬性。在開發者的開發活動中，“社交關系”是指在特定社區中開發者之間的人際關系。雖然與開發活動并不直接相關，但研究發現，開發者加入好友所在的項目，其貢獻率將會大幅提升 5。社交關系又可以細分為關注關系和同組織關系，分別表示開發者之間的相互關注和開發者隸屬于同一個組織?！爸苯訁f作”是指開發者之間存在直接的交互關系，即兩個開發者面對同一任務需要緊密的溝通合作。例如開發者 D1 與開發者 D2 之間若存在 Answer to 和 Call API 的關系，則表示 D1 回答了 D2 提出的問題、在實現某些功能時 D1 調用了 D2提供的接口，這些協作的頻度用數字

244、表示。此外，開發者共同修改代碼文件、對同一代碼的開發和測試也屬于這種緊密型的協作關系，其他類似的協作關系還有很多，恕不一一列舉。最后，“間接協作”是指開發者之間存在間接的交互關系。相對于直接協而言，間接協作是一種較弱的協作關系，但對于整體的開發任務也會起到一定的作用。例如開發者 D1 與開發者D2 都回答了某個問題，或者都向某個開源項目提交了自己的代碼，則他們之間就構成了 Co-answer 和 Co-commit 的關系。另外，我們還可以構建開發者的貢獻度特征?！柏暙I度”是指開發者在特定社區中對該社區作出的貢獻，主要考察開發者在社區中的活躍度和熟練度。這些貢獻覆蓋了開發者的各項活動，如在 G

245、itee 開源社區中參與項目或提交代碼，在 Stack Overflow 問答社區中回答問題，等等。如圖 8 所示，我們可以構建開發者參與社區的貢獻度特征，圖中的標簽代表該開發者參與的所有項目，圓形直徑代表開發者對項目的貢獻度，直徑越長，貢獻度越高。與其他開發者的關聯關系可以用開發者關系圖譜來表示，通過將開發者之間的交互可視化，來量化社區的協作強度。利用開發者關系圖譜，我們可以識別開發者參與社區的趨勢特別是核心開發者還可以判斷開發者是否有從社區流失的傾向等。如圖 9 所示，在完成開發者畫像的構建之后，接下來需要建立開發者在社區的參與旅程框架（如圖 10 所示），方便度量開發者在不同階段為社區創

246、造的價值 6。該框架涵蓋了社區參與的三個關鍵部分。不同的成員畫像類型，需要不同的參與旅程框架：新人引導：五角星左邊代表社區幫助新人以最簡單的方式盡快創造價值，價值本身既是新人自己的，也是社區的。109|華為研究2022 年 12 月軟件技術與生態3.2.3 構建開發者 NPS 度量模型圖 10 開發者社區的參與旅程框架圖 11 社區畫像成熟度模型圖 12 NPS 定義 參與狀態轉換：五角星右邊代表開發者開始在訪客 ?？?核心成員這三個關鍵身份之間轉換。激勵：為了促進社區發展、保持成員的參與度，我們會采取一系列措施（藍色方塊），幫助成員積累經驗、培養新技能并維持積極性。在介紹完開發者畫像及社區參

247、與旅程框架后，下面我們可以引出社區畫像成熟度模型（如圖 11 所示），該模型提供了一套工具來定義開發者畫像在各階段的成功：當我們完成了開發者畫像的構建，并設計了開發者在整個社區的參與旅程框架，要衡量他們在不同階段（新人/訪客/?？?核心成員）為社區創造的價值，就需要從開發者角度出發構建凈推薦度（Net Promoter Score，NPS）度量模型 7通過度量和洞察，讓社區與開發者為彼此帶來更多價值。NPS 是業界用來衡量用戶體驗的通用指標，是管理用戶體驗、提升客戶滿意度的有效工具。通過一個終極問題你有多大可能會將我們的社區推薦給同事和親朋好友？為什么?NPS 可以清晰地將用戶分成三類，并在此

248、基礎上計算出一個簡單易懂的值，然后制定出計劃，以期改進并獲得成功（如圖 12 所示）。開發者 NPS 度量模型（圖 13）由兩部分組成：第一部分是 NPS 度量體系，第二部分是 NPS 反饋體系。通過NPS 度量體系，結合開發者畫像，我們可以通過 NPS 問卷調查的形式感知社區存在的問題以及開發者的訴求。通過NPS 反饋體系，及時給出解決方案，調整社區的相關治理機制。最終提升開發者滿意度，以及開發者對社區的忠誠度。3.3 面向社區管理者的度量圖 13 開發者 NPS 度量模型作為社區的管理者，開源社區有許多度量指標及度量模型可以衡量社區是否成功。但問題是開源項目面臨著浩瀚使用方法如下：沿著橫軸

249、，可以看到社區參與旅程框架的各個階段，包括新人、訪客、?？秃秃诵某蓡T階段。針對這些階段，分別定義各個階段的成功標準，并利用不同維度的指標來進行度量。個人價值：某成員畫像應該為他/她本人帶來哪些可度量的價值？例如，對于新人階段，Issue 支持者畫像的成功標準可以定義為“在社區提出新 Issue 并獲得答案”。社區價值：某成員畫像為社區帶來了哪些可度量的價值？例如，對于新人階段，Issue 支持者畫像的成功標準可以定義為“解決了社區其他成員提出的 Issue”。同行價值：某成員畫像為社區其他成員帶來了哪些可度量的價值？例如，對于?？碗A段，成功標準可以是“為社區不同成員提供一對一指導或者培訓”。領

250、導力價值：某成員畫像在社區領導力方面帶來了哪些可度量的價值？華為研究|1102022 年 12 月3.4 社區體驗改進3.3.1 選擇度量指標3.3.2 核心組織的支持3.4.1 開發者畫像助力社區維系開發者圖 14 組織能力成熟度模型如煙的數據，任何可以獲得數據的對象，都能收集、跟蹤。每個組織跟蹤的度量標準以及他們如何處理數據在很大程度上取決于自身社區獨有的戰略目標，以及他們在市場和開源社區中的獨特挑戰。特別是對于大型組織來說，有太多的項目，不可能跟蹤所有的對象并保證此舉有意義。為擺脫這一困境，在選擇度量指標和度量領域時，需要結合社區的戰略目標，投入自己的思考 8。設定社區的戰略目標包括：構

251、建社區的遠景使命、明確社區為人/組織提供的價值、制定階段性目標。具體執行過程中，我們需要有針對性地衡量社區的工作成果。在制定具體指標時，我們需要保證目標能夠清晰、準確地衡量，切忌模棱兩可。為此，我們需要遵循以下四個規則 6：衡量關鍵維度社區主要有七個關鍵維度：增長率：有多少新人加入社區？如何隨時間變化？留存率：有多少人在持續地參與社區活動？社區內成員的活躍度；組織成員與社區成員的協作活躍度；交付能力：社區內不同的貢獻者是否按照其職責提供了相應的價值；出席率：線上、線下活動的出勤情況；高效性：整個社區的運轉機制是否暢通無阻？同時度量“質”與“量”跟蹤不同類型的貢獻數量是衡量活躍度和交付率的好辦法

252、，但同時也要驗證貢獻的質量，做到“質”與“量”兼顧。度量可量化在度量目標是否達成時，我們應能清晰地回答出“是”或“否”，而不是“也許”。限制度量指標的數量我們需要做到精簡指標數量，只跟蹤關鍵指標，這樣可以保持關注，簡化討論。作為社區的初創者及主導者，核心組織想要真正成功地創建一個社區，需具備從計劃、發展、互動到優化社區體驗的一整套技能。不僅需要發展這些技能，也需要在組織內部建立支持系統。組織發展這些技能的過程可分為三個階段 6：1.孵化新技能：營造一個兼具資源、教育、戰略和執行力的環境，該環境可以引入新技能、為人員提供培訓、在人們應用這些技能時提供支持。2.建立機制：在吸取孵化階段的經驗教訓后

253、，需要制定機制、加深團隊理解、完善和發展這些標準。3.整合：需要將這些機制推廣到組織內所有團隊中去。我們將這三個階段與專業領域的目標技能相結合，構建出了如下組織能力成熟度模型：如圖14所示，組織能力成熟度模型從上到下分為七行，每行代表一個專業領域，每個領域皆跨越了技能發展的三個階段。在使用該模型時，組織需定期復盤，向相關部門收集反饋意見，并將改進計劃整合到下一個迭代中去?；谏鐓^健康度度量體系和開發者畫像的關系，我們與華東師范大學王偉教授和上海交大曹健教授的團隊一起聯手，在華為主導的 openEuler/MindSpore 社區實施了社區體驗改進。在 OpenEuler 社區中，如圖 15 所

254、示，我們通過構建開發者在不同 SIG 組中的技能標簽，識別出大多數開發者都參與過 CVE 漏洞的修復工作。對于社區管理者而言，制定更簡單的漏洞修復流程、引入自動化漏洞感知和修復工具可以大幅提升開發體驗。111|華為研究2022 年 12 月軟件技術與生態3.4.2 開發者 NPS 度量模型推動 openEuler社區改進開發者體驗圖 15 openEuler 開發者標簽表 1 開發者旅程圖 16 MindSpore 社區協作者關系圖譜在 MindSpore 社區中，我們構建了開發者 Issue 交互關系圖譜，協助社區管理者識別了 10+不活躍開發者，并通過問卷、線下溝通等方式重新激活了部分存在

255、流失傾向的開發者（如圖16所示）。另外，通過構建開發者興趣圖譜，在 MindSpore 社區試點社區安全、前端、數據、科學計算SIG 組，提升了社區的整體活躍度。依據 3.2 節的討論，現在給出開發者 NPS 度量模型在openEuler 社區的實際應用。如表 1 所示，我們詳細定義了開發者通過引新活動（例如meetup）成為社區新人之后可能會經歷的所有社區旅程。4 結語當前，越來越多的企業主動擁抱開源，并將開源納入企業的發展戰略。但“為什么開源”、“如何開源”仍是企業不得不面對的實際挑戰。從開源策略六要素出發，本文從商業、項目、生態等多個角度全面審視了企業的開源活動，幫助企業通過社區度量掌握

256、開源健康度，構建高成長性、高粘性的開源社區，并最終支撐企業真正實現其開源戰略。在每個旅程節點，根據開發者角色（新人/訪客/?？?核心成員）構建了不同的開發者畫像。然后引入 NPS 調查問卷，對這些畫像精準投放不同的問題，以獲得開發者明確、清晰的反饋。通過這種方式，幫助社區及時發現問題，做針對性的管理與改進，最終提升開發者對社區的忠誠度。華為研究|1122022 年 12 月參考文獻1 Raymond and Eric S(1999),The cathedral and the bazaar:Musings on Linux and open source by an accidental re

257、volutionary,OReilly Media.ISBN 1-56592-724-9.2 Richard Stallman,FLOSS and FOSS,Accessed 9 October 2022.3 Bryan Che,OpenSource policy4 張建，孟祥鑫，孫海龍，王旭，劉旭東,數據驅動的軟件開發者智能協作技術,大數據,202101:76-93,2021.5 楊程，范強，王濤，尹剛，王懷民,基于多維特征的開源項目個性化推薦方法,軟件學報,2017,28(6):1357-1372,20176 Jono Bacon(2019),People powered,HarperCo

258、llins Focus.ISBN 9781400214884.7 Fred Reichheld and Rob Markel,The ultimate question 2.0(revised and expanded edition):How net promoter companies thrive in a customer-driven world,20118 Christine Abernathy,Chris Aniszczyk,Joe Beda,Sarah Novotny,and Gil Yehuda,Measuring your open source programs succ

259、ess,Accessed 9 October 2022.113|華為研究2022 年 12 月軟件技術與生態全球導航衛星系統動態實時差分（Global Navigation Satellite System Real-Time Kinematic，GNSS-RTK）定位可以基于固定解實現高精度定位，是自動駕駛車輛（Autonomous Driving Vehicles，ADV）絕對定位的必備技術。但城市建筑物對信號的阻擋、反射和衍射會使 GNSS-RTK 定位的性能大幅下降。因此，本文提出一種新方法，利用 3D LiDAR 和慣性傳感器生成局部環境映射，排除 GNSS 潛在非視距（Non-Li

260、ne-of-Sight，NLOS）接收信號，進一步提升城市峽谷場景下 GNSS-RTK 定位的性能。首先，通過基于因子圖優化的 LiDAR/慣性積分構建局部環境描述，即 3D點云圖（Point Cloud Map，PCM）。然后，在 GNSS-RTK 定位前采用 3D PCM 檢測并排除 GNSS 潛在 NLOS 接收信號。最后采用優化后的 GNSS-RTK 定位校正 LiDAR/慣性積分構建的 3D PCM 所產生的漂移。實驗利用低成本車載GNSS 接收機在不利于定位的城市環境中采集測試數據集，驗證了該方法的有效性。摘要Han Gao1，Weisong Wen2，Li-Ta Hsu2，Yon

261、gliang Wang11黎曼實驗室 2香港理工大學航空及民航工程學系智能汽車 LiDAR 輔助 GNSS-RTK 定位關鍵詞GNSS，RTK，NLOS，LiDAR，城市峽谷華為研究|1142022 年 12 月1 引言全球導航衛星系統動態實時差分（Global Navigation Satellite System Real-Time Kinematic，GNSS-RTK）廣泛應用于高精度航空測繪 1 以及 L4 等級的全自動駕駛車輛（Autonomous Driving Vehicle，ADV）定位2。GNSS-RTK 定位通常包括兩個步驟：（1）根據接收的 GNSS 測量數據估計浮點解。

262、（2）基于估計的浮點解，采用最小二乘算法（如 LAMBDA 3）計算整周模糊度，并作為初始猜測值。通過雙差分載波和碼測量可以在露天區域基于固定解實現厘米級定位。但在城市峽谷場景中，周邊建筑物對 GNSS 信號的反射和阻擋會產生 NLOS 和多徑接收信號，使 GNSS-RTK 定位的精度大幅下降。問題的根本原因是 GNSS NLOS 接收信號。因為部分 GNSS接收信號被嚴重污染，產生大量噪聲。根據以往研究 4，高度城市化地區中大部分 GNSS 接收信號都是多徑信號或NLOS 信號。因此，基于差分載波和碼測量估計的浮點解，其精度有所下降，模糊度更難求解。近幾十年，57 開展了大量研究以提升城市峽

263、谷場景下 GNSS-RTK 定位的性能。6 提出采用多天線提升GNSS-RTK 離群值測量的魯棒性，但該方法的有效性取決于 GNSS 污染信號量（多徑信號或 NLOS 接收信號量）。最近，5 提出通過 3D 建筑模型來排除 GNSS 污染信號，以提升城市峽谷場景下 GNSS-RTK 定位的性能。該方法可以通過視距（Line-of-Sight，LOS）測量提高固定率，但需要精確的 3D 建筑模型和 GNSS 接收機位置的初始猜測值。另一個研究方向是通過傳感器融合來增加傳感器。GNSS-RTK 和 慣 性 測 量 單 元（Inertial Measurement Unit，IMU）的結合能夠帶來更

264、多增益，因此已被廣泛研究。根據 8，在信號較好的典型城市場景中，高級雙頻多GNSS-RTK 定位在 1 小時車程內的正確整周模糊度固定率可達 76.7%。但總體定位性能很大程度上取決于 GNSS中斷期間 IMU 傳感器的成本 9。10 和 11 提出了在不利于 GNSS 定位的環境中將 GNSS-RTK 與視覺測量緊密結合，以提升定位性能。但是，視覺測量對動態對象的照明條件和密度比較敏感，而且視覺測量的比例復原在很大程度上取決于 GNSS 測量數據的質量。4，1315 沒有采用視覺測量，而是提出通過 3D LiDAR 傳感器不斷提升城市峽谷場景下 GNSS 單點定位（Single Point

265、Positioning，SPP）的性能，因為 3D LiDAR 傳感器魯棒性較高，且不受照明條件影響。該方法利用 3D LiDAR 傳感器生成的3D 點云來描述周邊環境，進一步排除 4 或校正 GNSS NLOS 接 收 信 號 13。16 的 最 新 成 果 結 合 了 GNSS NLOS接收信號的校正與重構，通過增量構建環境描述（3D PCM）提升城市場景下 GNSS SPP 定位的性能。但該方法只采用了碼測量，沒有對載波相位測量進行探討。本文基于 4 和 13 的 3D LiDAR 輔助 GNSS SPP定位，提出通過 3D LiDAR 傳感器從根本上解決信號反射和阻擋引起的定位精度下降

266、問題，從而提升城市峽谷場景下GNSS-RTK 定位的性能。首先，根據 17 的最新成果，通過因子圖優化（Factor Graph Optimization，FGO）將 LiDAR 和 IMU 測量松散結合，實現 LiDAR/慣性里程計（LiDAR/Inertial Odometry，LIO），以估計兩個歷元間的相對運動，并生成 3D PCM（即局部環境描述）。再基于 16，利用 PCM 檢測和排除 GNSS 潛在 NLOS 接收信號，從而提升 GNSS 測量數據的質量。然后利用未排除的 GNSS 衛星測量信號估計浮點解，并采用 LAMBDA算法求解模糊度。最后，結合 GNSS-RTK 定位固定

267、解的估計值和 LIO，進一步校正 3D 點云漂移。簡而言之，該方法有效結合了 LIO 和 GNSS-RTK 定位。LIO 在短周期內局部精度高，并為GNSS NLOS信號檢測提供了環境描述。GNSS-RTK 定位提供了無漂移的全局參考位置，但結果受 GNSS NLOS 接受信號的影響。本文的研究成果如下：（1）通 過 LiDAR/慣 性 積 分 檢 測 和 排 除 GNSS 潛 在NLOS 接收信號，進一步提升 GNSS-RTK 定位的性能。這是 LiDAR/慣性積分被首次應用于排除此類信號。（2）通過優化后的 GNSS-RTK 定位校正 3D 點云漂移，提高整體定位精度。（3）利用低成本 G

268、NSS 接收機采集的數據集來評估該方法的有效性。以下是本文各部分簡介。第 2 節提供方法概述。第 3節介紹如何生成局部環境描述。第 4 節介紹 NLOS 信號檢測和 GNSS-RTK 定位。第 5 節采用香港城市峽谷場景中采集的數據集進行實驗，評估方法的有效性。第 6 節得出結論，并提出未來研究方向。2 方法概述方法概述如圖 1 所示，由兩部分組成：（1）基于 3D LiDAR 和 IMU 在云上生成實時環境描述，并校正 GNSS-RTK 解。（2）基于實時環境描述檢測和排除 GNSS NLOS 信號，并基于未排除的衛星信號進行 GNSS-RTK定位。本文用加粗大寫字母表示矩陣，用加粗小寫字母

269、表示向量，用斜體小寫字母表示可變標量，用小寫字母表示常量標量。GNSS 接收機狀態和衛星位置均采用東北天坐標系（East,North,Up，ENU）表示。為使描述更加清晰，本文定義了以下幾種符號：給定歷元k內衛星s接收的偽距測量值為sr,k。下標r表示 GNSS 接收機，k表示時間索引，上標s表示衛星索引。給定歷元k內衛星s接收的載波相位測量值為sr,k。地心地固坐標系（Earth-centered,Earth-fixed，115|華為研究2022 年 12 月軟件技術與生態ECEF）或 ENU 坐標系中的變量用上標 G 和下標 L表示。例如，在 ENU 坐標系和 ECEF 坐標系中，位姿和位

270、置的轉換為TGL=RGL,tGL，其中RGL和tGL分別表示旋轉和平移。AHRS、LiDAR 和 GNSS 接收機的體坐標系用上標BI、BL 和 BR 表示。例如，PBLk表示歷元k內的一個3D LiDAR 點云坐標系。GNSS 接 收 機 和 3D LiDAR 之 間 的 外 部 參 數 為TBRBL=RBRBL,tBRBL。IMU 和 3D LiDAR 之間的外部參數為TBIBL=RBIBL,tBIBL。ECEF 坐 標 系 中，衛 星s在 給 定 歷 元k的 位 置 為sk=sk,x,sk,y,sk,zT。ECEF 坐標系和 ENU 坐標系中，GNSS 接收機在給定 歷 元k的 位 置

271、為pGr,k=pGr,k,x,pGr,k,y,pGr,k,zT和pLr,k,x,pLr,k,y,pLr,k,zT。ENU 坐 標 系 的 旋 轉 為RLr,k=Lr,k,x,Lr,k,y,Lr,k,zT。GNSS 接收機在給定歷元k的鐘差為r,k，單位為米。sr,k表示衛星鐘差，單位為米。云云LiDAR掃描匹配LiDAR因子LiDAR因子局部FGOPCM校正位置估算值位置估算值預積分PCMPCMPCMPCMGNSS NLOS信號排除GNSS-RTK浮點解估算浮點解位置估算值浮點解位置估算值浮點解GNSS接收機載波偽距測量GNSS接收機載波偽距測量最小二乘法定位衛星測量數據衛星測量數據模糊度求解

272、模糊度固定解模糊度固定解加速度計和陀螺儀加速度計和陀螺儀衛星測量數據IMU因子衛星測量數據IMU因子圖 1 方法概述。輸入為 IMU、3D LiDAR 和 GNSS 接收機的原始測量數據，輸出為 GNSS 接收機的估計狀態。3 生成局部環境描述本節介紹如何基于 LiDAR/慣性傳感器生成局部環境描述，以及如何進行 GNSS-RTK 校正。首先，采用LiDAR/慣性積分通過局部 FGO 生成 3D PCM（如圖 1 所示）。然后利用 3D PCM 檢測 GNSS NLOS 接收信號。但是 LiDAR/慣性積分會隨著時間的推移產生漂移。3D PCM 漂移可以通過全局 FGO 結合 GNSS-RTK

273、 和 LIO，利用優化后的 GNSS-RTK 定位結果進行校正（如圖 1 所示）。PCM 采用 ENU 坐標系表示，ENU 坐標系和原始LiDAR 坐標系之間的外部參數通過前幾個 GNSS-RTK 固定解進行校正 18。3.1 基于局部 FGO 的 LiDAR/慣性積分3.1.1 IMU 預積分模型LiDAR/慣性積分是 17 最近發表的研究（該文獻探討了基于滑窗的 FGO 松耦合積分），并非本文的主要研究成果。但為了論述的完整性，本節提供了 LiDAR/慣性積分的簡介。世界坐標系中第k個 IMU 狀態，即捕捉到 LiDAR點云第k個坐標系時的 IMU 狀態可表示為：xBL(0)k=?pBL(

274、0)BIk,vBL(0)BIk,qBL(0)BIk,bak,bgk?(1)(1)其中，xBL(0)k包括位置、速度、四元數旋轉、加速度偏差bak和陀螺儀偏差bgk。因此，FGO 局部窗口內的狀態集（XBL(0)）可表示為：XBL(0)=?xBL(0)0,xBL(0)1,xBL(0)K?(1)(2)其中，K表示 FGO 滑窗的大小。IMU 單元用于測量 IMU 體坐標系中系統的角速度和比力。加性噪聲以及加速度和陀螺儀偏差緩變會使測量結果產生偏差 19：aBI=RBIBL(0)(aBL(0)gBL(0)+ba+na(3)(4)BI=BI+bg+ng(1)aBI是 IMU 體坐標系的原始 IMU 加

275、速度測量值，aBL(0)是 ENU 坐標系中系統的無噪加速度。gBL(0)是世界坐標系中的重力。RBIBL(0)SO3是從 ENU 坐標系到 IMU體坐標系的旋轉矩陣。ba表示加速度偏差緩變，其導數服從高斯分布。na N(0,2a)是加速度的加性噪聲。BI是IMU 體坐標系中的原始 IMU 陀螺儀測量值，BI是無噪旋轉速率。bg是BI的偏差，同樣假設其導數對象服從高斯分布。ng N(0,2g)是BI的加性噪聲?？紤]到 IMU 測量的高頻特性，采用 IMU 預積分技術將多個 IMU 測量值堆疊到單個因子中 19，則局部坐標系Bk中的 IMU 預積分公式為：BIkBIk+1=?tk+1tkqBIk

276、BIt(aBIt bak)t2(5)華為研究|1162022 年 12 月3.2 LIO 與基于全局 FGO 的 GNSS-RTK積分3.1.2 LiDAR 掃描匹配測量模型3.1.3 求解局部 FGOBIkBIk+1=?tk+1tkqBIkBIt(aBIt bak)t(6)qBIkBIk+1=?tk+1tkqBIkBIt?012(BIt bgk)?t(7)其中，BIkBIk+1、BIkBIk+1和qBIkBIk+1分別是位置、速度和旋轉的預積分。實際上，IMU 測量是離散的，并通過線性插值與 LiDAR 坐標系同步。本文不采用上述的連續數值積分，而是采用中位積分。假設BIt和BIt+1是兩個

277、歷元BIk和BIk+1之間的兩個連續時間點，t是BIt和BIt+1之間的時間間隔。中位積分作為兩個 IMU 狀態間的相對運動測量值，可以起到約束作用。殘差rIMU(zBIkBIk+1,XBL(0)可定義為 19：rIMU(zBIkBIk+1,XBL(0)=(qBL(0)BIk)1(pBL(0)BIk+1 pBL(0)BIk vBL(0)BIkt 12gBL(0)t2)BIkBIk+12?(qBIkBIk+1)1(qBL(0)BIk)1 qBL(0)BIk+1)?xyz(qBL(0)BIk)1(vBL(0)BIk+1 vBL(0)BIk gBL(0)t)BIkBIk+1bak+1 bakbgk+

278、1 bgk(1)(8)其中，運算符xyz用于提取四元數的虛部。zBIkBIk+1表示預積分測量值，由BIkBIk+1、BIkBIk+1和qBIkBIk+1組成。本節采用 20 提出的掃描匹配法推導 3D 點云連續坐標系之間的相對運動。對這些相對運動進行累加，則LiDAR 里程計在給定歷元k的位姿估計值為TBL(0)BLk，計算公式如下 17：TBL(0)BLk=?pBL(0)BLk,qBL(0)BLk?(1)(9)LiDAR 掃描匹配的殘差rL(TWLk,X)可表示為TBL(0)BLk和xBL(0)k之間的差值：rL(TBL(0)BLk,XBL(0)=pBL(0)BLk pBL(0)BLk2?

279、(qBL(0)BLk)1 qBL(0)BLk?xyz(1)(10)17 介紹了掃描匹配的詳細推導過程。根據殘差推導結果，可通過以下組合目標函數優化滑窗內的狀態集XBL(0)21：XBL(0)=arg min12K?k=0(?rL(TBL(0)BLk,XBL(0)?2CLk)+K1?k=0(?rIMU(zBIkBIk+1,XBL(0)?2CBIkBIk+1)(11)其中，rL(TBL(0)BLk,XBL(0)表示 LiDAR 掃描匹配因子的殘差，zBIkBIk+1和rIMU(zBIkBIk+1,XBL(0)分別表示 IMU預積分因子的測量值和殘差，XBL(0)是待估計的最優狀態。CLk表示基于

280、17 推導的 LiDAR 掃描匹配因子的協方差矩陣。CBIkBIk+1表示 IMU 預積分因子的協方差矩陣。()表示基于柯西核 22 的魯棒性損失函數。最后，采用 Ceres Solver23 求 解 這 個 非 線 性 問 題，通 過 Levenberg-Marquardt（L-M）算法 24 迭代最小化代價函數（11）?；跔顟B集XBL(0)，在局部 FGO 滑窗內累加原始 3D 點云可以生成 PCM，結果表示為MBL(0)k。全局 FGO 是 LIO 位姿估計（見 3.1 節）和 GNSS-RTK 定位的融合。與 LIO 類似，全局 FGO 優化了滑窗內的狀態集。ENU 坐標系中 IMU

281、 坐標系的第k個狀態可表示為：xLk=?pLBIk,qLBIk?,(1)(12)其中，xLk由 ENU 坐標系中的位置和四元數旋轉組成。FGO 局部滑窗內的狀態集(XLk)可表示為：XL=?xL0,xL1,xLK?,(1)(13)(14)(15)(16)其 中，K表 示 FGO 滑 窗 的 大 小。假 設 優 化 后 的GNSS-RTK 位姿估計公式如下：zGr,k=?pGr,k,x,pGr,k,y,pGr,k,z?T(1)其中，zGr,k用 ECEF 坐標系表示。則zGr,k的殘差為：rGNSS(zGr,k,XL)=?(TGL)1(zGr,k tGL)pLBIk?(1)其中，rGNSS(zG

282、r,k,XL)表示與zGr,k關聯的殘差。根據LIO，給定歷元k的觀測結果是xBL(0)k，給定歷元k 1的觀測結果是xBL(0)k1。殘差計算公式如下：rLIO(xBL(0)k1,xBL(0)k,xLk1,xLk)=(P1 P2)(pLBIk pLBIk1)2?(R2)1R1)(pLBIk1 pLBIk)?xyz(1)117|華為研究2022 年 12 月軟件技術與生態其中：P1=(pLBL(0)1(RBIBL)1(pBL(0)BLk tBIBL)tLBL(0)P2=(pLBL(0)1(RBIBL)1(pBL(0)BLk1 tBIBL)tLBL(0)R1=(qLBL(0)1qBL(0)BLk

283、(RBIBL)1R2=(qLBL(0)1qBL(0)BLk1(RBIBL)1(17)(18)(19)(20)(21)(22)為使推導過程更加清晰，本文定義了P1和P2。根據殘差推導結果，可通過以下組合目標函數優化滑窗內的狀態集XL21：XL=arg min12K?k=0(?rGNSS(zGr,k,XL)?2CGNSS)+K1?k=0(?(xBL(0)k1,xBL(0)k,xLk1,xLk)?2CLIO)其 中，rGNSS(zGr,k,XL)表 示 GNSS 因 子 的 殘 差，rLIO(xBL(0)k1,xBL(0)k,xLk1,xLk)表示 LIO 因子的殘差，XL是待估計的最優狀態。CGN

284、SS表示 GNSS 因子的協方差矩陣。CLIO表示 LIO 因子的協方差矩陣。與局部 FGO 類似，通過 Ceres Solver23 利用 L-M 算法 24 求解公式(18)?；跔顟B集XL，在全局 FGO 滑窗內累加原始 3D 點云可以校正 PCM，表示為MLk。與 16 相比，通過 GNSS-RTK 定位積分生成的 PCM 沒有漂移，這是本文的研究成果之一。4 NLOS 信號排除與 GNSS-RTK定位4.1 基于 PCM 的 GNSS NLOS 信號排除4.2 基于未排除衛星的 GNSS-RTK 定位GNSS 接收機sr,k的偽距測量值可表示為 25：sr,k=rsr,k+c(r,k

285、 sr,k)+Isr,k+Tsr,k+sr,k(1)其中，rsr,k是衛星和 GNSS 接收機之間的幾何范圍。Isr,k表示電離層延遲距離，Tsr,k表示對流層延遲距離。sr,k表示多徑效應、NLOS 接收信號、接收機噪聲和天線相位相 關 噪 聲 引 起 的 誤 差。大 氣 效 應（Tsr,k和Isr,k）通 過RTKLIB 的傳統模型（Saastamoinen 和 Klobuchar 模型）進行補償 26。由于 ENU 坐標系中的 PCM、衛星仰角和方位角可以基于偽距測量值通過最小二乘法計算，因此可以通過 16 提出的快速搜索方法檢測 GNSS NLOS 接收信號。GNSS NLOS 接收信

286、號檢測如圖 2 所示。假設歷元k內接收的衛星集為SVr,k=SV1r,k,SVir,k,SVNr,k，其中包括 LOS 和NLOS 衛星。變量N表示歷元k內接收的衛星數量。SVir,k表示衛星i的測量值。檢測和排除 GNSS NLOS 接收信號后，未排除的衛星集為SSVr,k=SV1r,k,SVir,k,SVMr,k，其中變量M表示未排除的衛星數量。圖 2 基于 PCM 檢測 NLOS 接收信號。紅圈表示 GNSS NLOS衛星，藍圈表示 LOS 測量數據，圈內數字表示衛星仰角。GNSS 接收機的每次載波相位測量sr,k表示為 25：sr,k=rsr,k+c(r,k sr,k)+Isr,k+T

287、sr,k+Bsr,k+sr,k+sr,k(1)變量表示載波波長。變量sr,k表示載波相位校正項，其中包括天線相位偏移和變化、固體潮引起的站位移、相位轉繞效應和衛星時鐘相對論性校正。sr,k表示多徑效應、NLOS 接收信號、接收機噪聲和天線時延引起的誤差。Bsr,k是載波相位偏差，其計算公式如下。26 介紹了載波相位校正的詳細公式。Bsr,k=r,0,k s0,k+Nsr,k(1)變量r,0,k表示接收機本振的初始相位。類似地，變量s0,k代表衛星發射的導航信號的初始相位。變量Nsr,k表示載波相位的整周模糊度。衛星s的雙差（Double Difference，DD）偽距測量（sDD,k）公式如

288、下：sDD,k=(sr,k sb,k)(wr,k wb,k)(1)變量wb,k和sb,k代表參考站接收的偽距測量值，參考站用下標 b 表示。仰角最高的衛星其多徑和 NLOS 誤差往往最小。因此以仰角最高的衛星w為主衛星。將 DD 應用于偽距測量后，推導出來的sDD,k沒有鐘差，且不受大氣效應的影響 26。類似地，衛星s的 DD 載波相位測量（sDD,k）公式如下：華為研究|1182022 年 12 月(23)(24)(25)(26)(27)(28)(29)(30)(31)5 實驗結果及相關討論5.1 實驗設置sDD,k=(sr,k sb,k)(wr,k wb,k)(1)變量sb,k和wb,k代

289、表參考站接收的載波相位測量值。同樣，sDD,k也沒有括鐘差，且不受大氣效應的影響。變量sDD,k包括待估計的 DD 模糊度 26。GNSS-RTK 的浮點解可表示為：xfloatr,k=(pGr,k,N1rb,k,N2rb,k,NM1rb,k)T其中，變量xfloatr,k表示 GNSS 接收機在歷元k內的狀態，該狀態由 ECEF 坐標系中的位置（pGr,k）和 DD 模糊度組成。變量NM1rb,k表示衛星M 1的 DD 載波相位模糊度偏差。換句話說，每個 DD 載波相位測量值都有特定的模糊度偏差。因此，DD 偽距測量的觀測模型（sDD,k）可表示為：sDD,k=hsDD,k(xr,k,psk

290、,pwk,pb)+sDD,k(1)hsDD,k(xr,k,psk,pwk,pb)=(?xr,k psk?pb psk?)(?xr,k pwk?pb pwk?)(1)變 量sDD,k表 示 與sDD,k關 聯 的 噪 音。函 數hsDD,k()表 示 計 算 GNSS 接 收 機 狀 態 和 DD 測 量 值sDD,k的觀測函數。DD 偽距測量的誤差因子如下：?esDD,k?2sDD,k=?sDD,k hsDD,k(xr,k,psk,pwk,pb)?2sDD,k(1)變量sDD,k表示與變量sDD,k關聯的協方差，該變量通過收到的衛星測量信號的仰角和信噪比（Signal-to-Noise Rat

291、io，SNR）計算得出。同樣，DD 載波相位測量的觀測模型可表示為：sDD,k=hsDD,k(xr,k,psk,pwk,pb)+sDD,k(1)hsDD,k(xr,k,psk,pwk,pb)=(?xr,k psk?pb psk?)(?xr,k pwk?pb pwk?)+Nsrb,k(1)變量sDD,k表示與sDD,k關聯的噪聲。變量Nsrb,k表示載波相位測量的 DD 模糊度。則 DD 載波相位偽距測量的誤差因子如下：?esDD,k?2sDD,k=?sDD,k hsDD,k(xr,k,psk,pwk,pb)?2sDD,k(1)變 量sDD,k代 表 與sDD,k關 聯 的 協 方 差。則GNS

292、S-RTK 浮點解估計的目標函數為：xfloatr,k=arg min?s,k(?esDD,k?2sDD,k+?esDD,k?2sDD,k)(1)變量xfloatr,k表示浮點解的最優估計值。通過 Ceres Solver 23 求解上述目標函數（31），可得出當前歷元的GNSS-RTK 浮點解。得到 GNSS-RTK 浮點解后，使用模糊度求解算法估計固定解。載波相位測量值沒有噪聲時，變量Nsr,k應為整數。本文通過廣泛應用的 LAMBDA 算法 28 求解整周模糊度，得到固定解xfixr,k。然后將固定解代入全局 FGO 來校正 3.2 節中的 PCM 漂移。本節通過香港典型城市場景中采集的

293、數據集驗證本文方法的有效性。實驗采用多傳感器數據采集車，如圖 3 所示。測試場景如圖 3 右下角所示，街道兩側有高樓和樹木，不利于 GNSS-RTK 定位。實 驗 采 用 u-blox M8T GNSS 接 收 機 以 1Hz 的 頻率采集 GPS/北斗的原始測量數據，并部署了一個 3D LiDAR 傳感器（Velodyne 32）以 10 Hz 的頻率采集原始3D 點云數據，同時采用 Xsens Ti-10 IMU 以 200 Hz 的頻率收集數據。此外，還采用了 NovAtel SPAN-CPT 提供地面真值，這是一個 GNSS（GPS、GLONASS 和北斗）RTK/INS（光纖陀螺儀、

294、FOG）組合導航系統。FOG陀螺儀偏差運行穩定性為 1 度/小時，隨機游動為 0.067度/小時。數據采集車與 GNSS 基站間的基線距離約為 5公里。所有數據均采用機器人操作系統（Robot Operation System，ROS）29 來收集和同步。實驗前已對所有傳感器間的坐標系統進行校正。u-blox接收機IMU傳感器3D LiDARSPAN-CPT圖 3 數據采集車和測試場景119|華為研究2022 年 12 月軟件技術與生態下面通過比較三種方法分析 GNSS-RTK 定位性能，驗證本文方法用于提升 GNSS-RTK 定位性能的有效性。分析采用ENU坐標系評估精度，以第一個點作為參考

295、位置。（a）GNSS-RTK：基于 u-blox M8T 接收機原始測量數據的傳統 GNSS-RTK 定位方案 26。模糊度逐歷元求解。（b）u-blox 接收機:基于 u-blox M8T 接收機、無參考站校正的商用 GNSS 定位方案（c）GNSS-RTK-C：基 于 u-blox M8T 接 收 機 的 原始測量數據以及本文 GNSS NLOS 信號排除法的GNSS-RTK 定位方案。模糊度逐歷元求解。以上三種方法的結果對比如表 1 所示。表格第一行是用于定位估計的衛星數量。GNSS 定位平均需要 17 顆衛星的接收信號，而本文的 GNSS NLOS 信號排除法平均只需要 15.8 顆衛

296、星的接收信號。第二列為 u-blox 接收機的2D 定位誤差，定位結果基于 u-blox 接收機的標準 NMEA消息。平均誤差為 6.25 米，標準差為 7.31 米，最大誤差為 38.53 米。整個過程都采用了 GNSS 方案。第三列為傳統 GNSS-RTK 定位的結果。u-blox 接收機和參考站的原始測量數據使平均誤差降低到 2.43 米，標準偏差和最大誤差分別下降到 1.16 米和 7.20 米。由于測量數據的質量問題，固定率只有 1.0%。本文的 GNSS NLOS 信號排除法（GNSS-RTK-C）使平均誤差降至 1.95 米，標準偏差為1.003米，但最大誤差為12.40米，與G

297、NSS-RTK的7.20米相比大幅增加。不過固定率小幅度上升至 1.6%。實驗結果證明，本文方法能夠有效減少NLOS信號對定位的影響。5.2 城市峽谷場景性能評估150100500-50050100150200軌跡地面真值GNSS-RTKu-blox接收機GNSS-RTK-C樹木東（米）北（米）圖 4 三種方法的軌跡。黑色曲線表示地面真值，紅色、綠色和藍色曲線分別表示 GNSS-RTK、u-blox 接收機和 GNSS-RTK-C 方案。表 1 定位性能對比圖 5 上方為三種方法的誤差。紅色、綠色和藍色曲線分別表示 GNSS-RTK、u-blox 接收機和 GNSS-RTK-C方案。下方為排除

298、的 GNSS NLOS 衛星數量。時間（秒）誤差誤差（米）NLOS衛星數時間（秒）NLOS衛星數1510505.4995.49955.55.50055.5015.50155.5025.502543215.4995.49955.55.50055.5015.50155.5025.5025GNSS-RTKu-blox接收機GNSS-RTK-C上述三種方法的軌跡以及地面真值如圖 4 所示，整個實驗的定位誤差如圖5所示。在圖5圓圈標出的歷元A附近，本文方法引起的定位誤差明顯大于傳統的 GNSS-RTK，其原因是過度排除 GNSS NLOS 信號。圖 4 中部為接近歷元 A 的場景，其中樹木較多。圖 5

299、下方為排除的衛星數量，采用生成的 PCM 檢測到其中四顆衛星屬于 NLOS 衛星。排除 NLOS 衛星后，衛星的幾何分布嚴重扭曲，導致定位誤差增加。4、30 和 31 也發現了類似現象?？傮w而言，本文方法（GNSS-RTK-C）與傳統方法（GNSS-RTK）相比，能夠有效檢測和排除 GNSS 潛在NLOS 信號，從而提高定位性能。但兩種方法的固定率都不高（GNSS-RTK：1.0%，GNSS-RTK-C：1.6%），對于 GNSS-RTK-C 而言，這主要是因為排除 GNSS NLOS 信號會使衛星的幾何分布變差。項目u-blox 接收機GNSS-RTKGNSS-RTK-C平均衛星數17171

300、5.8平均誤差6.25 米2.43 米1.95 米標準差7.31 米1.16 米1.003 米最大誤差38.53 米7.20 米12.40 米固定率不涉及1.0%1.6%華為研究|1202022 年 12 月6 結語GNSS-RTK 定位目前仍然是實現自動駕駛定位的必備技術，自動駕駛需要精確的絕對定位。但是由于信號反射和衛星幾何分布較差，GNSS-RTK 定位難以廣泛應用于城市峽谷場景。本文提出一種新方法，通過車載傳感（LiDAR/慣性積分）檢測和排除 GNSS 潛在 NLOS 信號，從而提升 GNSS-RTK 定位的性能。對于實驗數據集，本文的NLOS 信號排除法使 GNSS-RTK 定位的

301、精度從 2.43 米提高到 1.95 米。但由于排除 GNSS NLOS 信號會使衛星的幾何分布變差，因此 GNSS-RTK 固定率仍然較低。未來，更多的環境特征將作為偽衛星被用于優化衛星的幾何分布，進一步提高城市峽谷場景下GNSS-RTK定位的整周模糊度固定率。多個 3D LiDAR 也將被用于生成更全面、更詳細的 PCM，從而增大環境重構的視場角。1 P.J.Teunissen and A.Kleusberg,GPS for geodesy,Springer Science&Business Media,2012.2 G.Wan et al.,Robust and precise vehi

302、cle localization based on multi-sensor fusion in diverse city scenes,in 2018 IEEE International Conference on Robotics and Automation(ICRA),2018:IEEE,pp.4670-4677.3 P.J.Teunissen,Least-squares estimation of the integer GPS ambiguities,in Invited lecture,section IV theory and methodology,IAG general

303、meeting,Beijing,China,1993.4 W.Wen,G.Zhang,and L.T.Hsu,Correcting NLOS by 3D LiDAR and building height to improve GNSS single point positioning,Navigation,vol.66,no.4,pp.705-718,2019.5 R.Furukawa,N.Kubo,and A.El-Mowafy,Prediction of RTK-GNSS performance in urban environments using a 3D model and con

304、tinuous LOS method,in Proceedings of the 2020 International Technical Meeting of The Institute of Navigation,2020,pp.763-771.6 P.Fan,W.Li,X.Cui,and M.Lu,Precise and robust RTK-GNSS positioning in urban environments with dual-antenna configuration,Sensors,vol.19,no.16,p.3586,2019.7 T.Li,H.Zhang,Z.Gao

305、,Q.Chen,and X.Niu,High-accuracy positioning in urban environments using single-frequency multi-GNSS RTK/MEMS-IMU integration,Remote Sensing,vol.10,no.2,p.205,2018.8 G.C.Chung,S.T.Su,and M.Y.Alias,Adaptive windowed statistical selection rake for long ultra-wideband multipath channels,(in English),Wir

306、eless Pers Commun,vol.98,no.1,pp.453-466,Jan 2018,doi:10.1007/s11277-017-4878-8.9 H.T.Zhang,Performance comparison of kinematic GPS integrated with different tactical grade IMUs,CALGARY,ALBERTA:THE UNIVERSITY OF CALGARY,2006.10 P.Henkel,A.Blum,and C.Gnther,Precise RTK positioning with GNSS,INS,Barom

307、eter and Vision,參考文獻121|華為研究2022 年 12 月軟件技術與生態in Proceedings of the 30th International Technical Meeting of the Satellite Division of The Institute of Navigation(ION GNSS+2017),2017,pp.2290-2303.11 T.Li,H.Zhang,Z.Gao,X.Niu,and N.El-Sheimy,Tight fusion of a monocular camera,MEMS-IMU,and single-freque

308、ncy multi-GNSS RTK for precise navigation in GNSS-challenged environments,Remote Sensing,vol.11,no.6,p.610,2019.12 X.Bai,W.Wen,and L.-T.Hsu,Performance analysis of visual/inertial integrated positioning in typical urban scenarios of Hong Kong,in Proceedings of 2019 Asian-Pacific Conference on Aerosp

309、ace Technology and Science,2019.13 W.Wen,G.Zhang,and L.-T.Hsu,GNSS NLOS exclusion based on dynamic object detection using LiDAR point cloud,IEEE Transactions on Intelligent Transportation Systems,2019.14 G.Zhang,Weisong Wen,and L.-T.Hsu,Correcting GNSS NLOS by 3D LiDAR and building height,ION GNSS+2

310、018,Miami,Florida,USA,2018.15 W.Wen,G.Zhang,and L.-T.Hsu,Exclusion of GNSS NLOS receptions caused by dynamic objects in heavy traffic urban scenarios using real-time 3D point cloud:An approach without 3D maps,in Position,Location and Navigation Symposium(PLANS),2018 IEEE/ION,2018:IEEE,pp.158-165.16

311、W.Wen,3D LiDAR aided GNSS and its tightly coupled integration with INS via factor graph optimization,in Proceedings of the 33rd International Technical Meeting of the Satellite Division of The Institute of Navigation(ION GNSS+2020),2020,pp.1649-1672.17 J.Zhang,W.Wen,F.Huang,and L.-T.Hsu,Loosely coup

312、led Lidar-inertial odometry for urban positioning and mapping(to be submitted),Remote Sensing,2021.18 W.Wen,G.Zhang,and L.-T.Hsu,Object-detection-aided GNSS and its integration with Lidar in highly urbanized areas,IEEE Intelligent Transportation Systems Magazine,vol.12,no.3,pp.53-69,2020.19 C.Forste

313、r,L.Carlone,F.Dellaert,and D.Scaramuzza,On-manifold preintegration for real-time visual-inertial odometry,IEEE Transactions on Robotics,vol.33,no.1,pp.1-21,2016.20 J.Zhang and S.Singh,LOAM:Lidar odometry and mapping in real-time,in Robotics:Science and Systems,2014,vol.2,no.9.21 F.Dellaert and M.Kae

314、ss,Factor graphs for robot perception,Foundations Trends in Robotics,vol.6,no.1-2,pp.1-139,2017.22 Z.Zhang,Parameter estimation techniques:a tutorial with application to conic fitting,Image vision Computing,vol.15,no.1,pp.59-76,1997.23 S.Agarwal and K.Mierle.Ceres Solver.http:/ceres-solver.org(acces

315、sed 6 January 2021).24 J.J.Mor,The Levenberg-Marquardt algorithm:implementation and theory,in Numerical analysis:Springer,1978,pp.105-116.25 E.Kaplan and C.Hegarty,Understanding GPS:principles and applications.Artech house,2005.26 T.Takasu and A.Yasuda,Development of the low-cost RTK-GPS receiver wi

316、th an open source program package RTKLIB,in International symposium on GPS/GNSS,2009:International Convention Center Jeju Korea,pp.4-6.27 A.M.Herrera,H.F.Suhandri,E.Realini,M.Reguzzoni,and M.C.de Lacy,goGPS:open-source MATLAB software,GPS Solution,vol.20,no.3,pp.595-603,2016.28 P.Teunissen,Theory of

317、 integer equivariant estimation with application to GNSS,Journal of Geodesy,vol.77,no.7-8,pp.402-410,2003.29 M.Quigley et al.,ROS:an open-source Robot Operating System,in ICRA workshop on open source software,2009,vol.3,no.3.2:Kobe,Japan,p.5.30 X.Bai,W.,Zhang,G.,Hsu,and Li-Ta,Real-time GNSS NLOS det

318、ection and correction aided by sky-pointing camera and 3D LiDAR,presented at the Proceedings of ION Pacific PNT 2019,Honolulu,HA,USA,2019.31 X.Bai,W.Wen,and L.-T.Hsu,Using Sky-pointing fish-eye camera and LiDAR to aid GNSS single-point positioning in urban canyons,IET Intelligent Transport Systems,v

319、ol.14,no.8,pp.908-914,2020.華為研究|1222022 年 12 月目前電視、電腦、手機、移動平板等顯示設備的顯示能力參差不齊，對于同一內容的顯示效果不盡相同。常常會出現制作時的畫面質量和終端呈現的畫面質量不一致的情況，使消費者無法完全感知創作意圖。為了緩解這一問題，創作者在創作時不得不做一些妥協；業界也制定了一些相關標準。盡管如此，消費者的體驗和創作者想要表達的內容還是無法做到一致。為了解決這一難題，HDR（High Dynamic Range）Vivid 通過分析制作端作品內容的特征，生成元數據，基于這些元數據在終端側根據人眼視覺系統的特性，結合終端的顯示能力進行亮

320、度、對比度、以及色彩感知保持的顯示適配，從而最大限度還原創作意圖。該技術通過優化色彩、亮度、對比度等畫面要素，精準調色，從而呈現更卓越的視覺效果，并在不同的消費終端呈現出相似的創作意圖，搭建了創作者和消費者之間的“橋梁”。關鍵詞HDR，色調映射，視覺感知，亮度和對比度保存，質量控制，色彩感知，人眼感知模型，優化摘要余全合1，徐巍煒1，王弋川1，張繼武1，陳虎2，袁樂31 中央媒體技術院2 慕尼黑音視頻實驗室3 上海海思信源技術開發部技術使能藝術：新一代 HDR Vivid視頻技術標準123|華為研究2022 年 12 月軟件技術與生態1 引言圖 1 高質量影像要素高質量影像主要取決于以下五個要

321、素：分辨率、位深度、幀速率、色域、動態范圍。分辨率指數字圖像中的像素數量 1。對于給定的顯示設備尺寸，分辨率越高，所包含的像素越多，對細節的表現也就更加精細。國際電信聯盟（International Telecommunication Union，ITU）發布的 BT.709 2 標準規定了高清影像的分辨率為 19201080。2012 年，ITU 又發布了 BT.2020 3 標準，將 4K（38402160）、8K（76804320）分辨率標準化。位深度表示每個像素可以顯示的顏色比特數 4。位深越大，可顯示的顏色數量就越多，整幅畫面的漸變就越自然。BT.709 標準規定了高清影像的 8 b

322、its 編碼格式，為適應 4K/8K 影像要求，BT.2020 標準將位深提升到了10/12 bits。幀速率指單位時間（1s）內連續顯示的圖像的數量 5。電影的幀速率一般為 24p（每秒 24 幀）；BT.709 標準規定高清影像的最高幀速率為 60p；針對 8K 廣播電視節目，BT.2020標準規定的最高幀速率可達120p，在該幀速率下，運動圖像的平滑程度在視覺上幾乎與真實世界無異。色域代表可以顯示的所有顏色的范圍合集 6。自然界中可見光譜的顏色組成了最大的色域空間，包含了人眼所能看到的所有顏色。顯示設備的色域越大，能夠再現的顏色就越多。BT.2020 標準相比 BT.709 標準，將色域

323、從Rec.709 擴展到 Rec.2020，進一步擴大了顏色范圍。動態范圍指某一事物最大值與最小值之間的差異，比例關系是其中的一種體現方式 7。在影像領域，動態范圍即是亮度的差別。動態范圍越大，圖像上同時記錄的亮部細節與暗部細節就越豐富，給觀看者的感受會更加真實。BT.2020 標準大幅推動了以上四個要素的發展，但在動態范圍上并沒有給出提升的建議。直到 2016 年，ITU 推出的 BT.2100 8 標準才正式定義了高動態范圍（High Dynamic Range，HDR）影像的相關參數。HDR 技術的發展對顯示終端的能力提出了更高的要求。根據 UHD 聯盟針對電視機等終端設備認證提出的Ul

324、traHD Premium 標準 9，以亮度要求為例，若需通過HDR 認證，顯示設備亮度特性需要滿足以下要求：最大峰值亮度達到 1000 nits（cd/m2），最大黑度值（屏幕能夠表現的僅次于關閉狀態的最暗的亮度）不超過 0.05 nits（cd/m2）；或者，最大峰值亮度達到 540 nits（cd/m2），最大黑度值不超過 0.0005 nits（cd/m2）。然而，創作者制作的高質量 HDR 影像往往具有更大的動態范圍。如何讓它們能夠在更低動態范圍的顯示設備上正確顯示，同時忠實地還原創作者的意圖，成為了需要解決的問題。降低動態范圍的同時盡量保持原始影像對比度、細節等特征的過程被稱為色調

325、映射（Tone Mapping）10。學術界早在多年前就開始對色調映射算法進行研究。Reinhard 11 基于人眼視錐細胞的光感受響應，構建出全局色調映射算子；Kim 12 基于人類視覺靈敏度，提出遵循高斯分布并取決于場景的平均對數亮度映射模型；隨著人工智能的發展，深度學習技術也被應用在色調映射研究中。Patel 13 利用生成對抗網絡，進行有監督的色調映射學習。Zhang 14 采用多尺度的卷積神經網絡，使得HDR 圖像的全局信息與局部信息在映射過程中均得以最大程度的保留。為了進一步提升終端顯示質量，工程實踐與標準化過程中進一步采用“元數據”的概念，元數據包含了原始影像的特征信息，傳輸到顯

326、示端后，再根據相應的標準規范，指導終端基于元數據進行色調映射。電影電視工程 師 協 會（Society of Motion Picture and Television Engineers，SMPTE）于 2014 年頒布了 ST 2086 標準15，對 HDR 的靜態元數據進行了規定。靜態元數據包含了藝術家在調色時使用的監視設備的信息。本文提出的 HDR Vivid 技術與傳統技術相比，其創新性主要體現在以下幾個方面：1.采用高分辨率、寬位深、高幀率、廣色域、高動態范圍的策略，制作高質量的 HDR Vivid 內容。2.提出了一種亮度對比度和色彩保持方法，保證 HDR 內容的靈活性，穩定性和

327、合理性，精確還原各種場景下的亮度對比度和色彩。3.采用動態元數據方案，結合人眼感知，確保 HDR 內容在具有不同顯示能力的終端設備上均可以得到較為一致的呈現效果。4.借助內容生成制作工具，開放動態元數據的調整接口，從而給予創作者更大的藝術創作空間。華為研究|1242022 年 12 月HDR Vivid 相關技術已經被中國超高清視頻產業聯盟采納，并成為高動態范圍視頻技術標準，本文將對 HDR Vivid 涉及的科學原理和技術方案做詳細介紹。2.1 視覺藝術與 HDR 制作2.2 HDR 分發2 端到端 HDR 系統創作者通常利用現代技術創作作品，整個創作過程主要包括制作、分發和顯示與感知。圖

328、2 端到端 HDR 系統視覺藝術是指運用一定的物質、材料、技術手法，創作可供人觀看欣賞的藝術作品。從廣義上說，雕塑、繪畫、攝影等藝術門類都屬于它的范疇，它不僅創作方式多樣，造型手法也十分多樣 16。視覺藝術作為一種傳達信息的“語言”，由視覺基本元素和設計原則兩部分構成的一套傳達意義的規范或符號系統 17?；驹匕ǎ壕€條、形狀、明暗、色彩、質感、空間。藝術家通過組織和運用這些基本元素實現創作意圖。藝術家根據需要選擇相應的材料和表現形式（雕塑或是繪畫、具象或是抽象等等），運用一定的原則和方法，在一定的范圍內控制各種元素之間的關系，最后形成能夠傳達特定信息的圖像 18。繪畫是一種古老的視覺藝術

329、19，其發展受到技術的限制。洞穴人利用土系顏料制作洞穴壁畫；文藝復興時期從天青石中提取得到明亮的深藍色顏料，使得該時期的圣母像呈現出高雅的藍色；十九世紀新型色素井噴式的發展以及金屬管的發明，為畫家們帶來了出門繪畫的可能性與便捷性，帶來了繪畫史上的外光寫生的發展。小孔成像的引入使繪畫的逼真感大幅提升 20,21，同時也推動了十九世紀攝影的誕生。攝影隨著蓋達爾的銀版攝影術誕生。1889 年，美國依斯曼柯達公司以硝化纖維素軟片作為基材，大規模生產照相膠卷，推動了照相機的小型化。膠片利用銀鹽顆粒感光，銀鹽感光顆粒的光學特性近似于 Gamma 曲線 22。根據相紙的感光特性，輔以增厚劑和減薄劑，使用光譜

330、特性狹窄的相紙等等才能獲得滿意的照片 23。二十世紀末，數碼相機的發明使攝影技術的發展進入了新的階段。根據攝影師 24測試，膠片相機可接受的寬容度為 8，而數碼相機可接受的寬容度有 9，在很多情況下膠片的噪聲和細節很難分辨，而數碼相機的表現更好。從固定的石壁，到雕塑、繪畫，再到電子顯示設備，技術的發展深刻地改變了人創造和感知視覺藝術的方式。陰極射線管（Cathode Ray Tube，CRT）是廣泛使用的電子顯示設備，其使用的 P22 熒光粉色域接近 BT.709，最高亮度接近 100 nits。后來，液晶顯示器（Liquid Crystal Display，LCD）快速發展，替代了 CRT，

331、提供了更寬的色域范圍以及更高的亮度 25。近年的 OLED（Organic Light-Emitting Diode）和 micro-LED 以及激光顯示更是將色域表現拓展至 DCI-P3（Digital Cinema Initiative-P3）甚至 BT.2020，峰值亮度提升至 300010000 nits，顯示位深提升至 10 bits。就像是礦物顏料提純技術的發展促進了繪畫的發展，HDR 技術的發展也來了更好感知體驗。HDR Vivid 支持 12 bits、400010000 nits 的動態范圍、BT.2020 色域（BT.2020 基本包絡了視覺系統可感知的顏色范圍）以及元數據

332、控制，為藝術創作帶來了更大的空間，為藝術的呈現帶來了更靈活的手段。為了將 HDR 制作的作品進行有效分發，需要考慮合理的編碼方式，其中位深度和線性到非線性轉換是兩個最重要因素。由于數字影像是離散的，為了保留更多、更細膩的信息，最簡單的方式就是增加位深。在最大亮度不變的情況下，BT.2020 標準使用 10/12 bits 編碼，記錄的信息比BT.709 標準使用的 8 bits 要豐富得多。此外，對原始 HDR 內容最直觀的編碼方式是采用線性編碼，但人類視覺感知系統并非是線性的，這種編碼方式會造成亮部占用色階過多，而暗部信息記錄不足，不利于被人類視覺系統所感知。在視頻領域，Gamma 輸入輸出

333、特性曲線除了指代 CRT 顯示器時代的“伽瑪校正”，還有更為廣泛的含義。采集端光傳感器對所記錄數據的轉換稱為光-電轉換函數（Opto-electronic Transfer Function，OETF），而編碼的數據在顯示端被還原并顯示出來的轉 換 稱 為 電-光 轉 換 函 數（Electro-optical Transfer Function,EOTF）。任何類型的 OETF 與對應的 EOTF曲線均可被認為是廣義上的伽瑪曲線。然而應該設計什么樣的 Gamma 曲線才能夠符合人類視覺感知呢？學術界對此有相當多的研究與成果。整個 HDR 創作過程如圖 2 所示。首先，創作者使用攝像機和調色軟件等工具制作出母版；然后，分發過程將母版進行壓縮和傳輸，形成壓縮碼流；最后，顯示和感知過程將壓縮碼流進行解碼和顯示。這三個過程相互聯系，每個過程的效果都會影響下一個過程。下面將對視覺藝術和 HDR制作