很多研究者已經利用演化演算法（Evolutionary Algorithm, EA） 來解決機器學習中的複雜最優化問題。例如，EA 可以用來優化神經網路，包括訓練連接權重、結構優化和超參數優化。這種演化的人工神經網路模型能取得非常好的性能，甚至能媲美手動設計的模型。儘管演化學習已經取得了很多成功，但也很難得到機器學習社區的廣泛認同，其中一個重要的原因是 一直以來演化學習缺少堅實的理論基礎，演化計算的研究者過於關注啟發式的策略設計演算法，缺乏對演化計算理論的關注。南大周志華，俞揚，錢超深耕演化計算理論近二十年，近期準備出版演化學習：理論與演算法進展一書將為演化學習提供理論框架支撐。本文嘗試為讀者解讀這一最新進展，希望能引起機器學習和演化計算領域的研究者更多的關注。

1 簡介之演化計算理論與機器學習的前世今生

2001年周志華教授與其合作者提出了selective ensemble approach，其主要思想是通過從一批訓練好的神經網路中選擇一個子集進行結合，泛化性能甚至優於結合所有神經網路。這項研究工作採用了遺傳演算法，是最為常見的一種演化演算法（Evolutionary Algorithm, EA）

周志華認為演化演算法作為一種強大的優化方法，演化演算法可能對許多機器學習任務都有用。那個時候，演化計算基本上都是純啟發式的，而機器學習社區更加青睞於傳統的數學優化方法，例如梯度法等等理論味道相對濃一點的優化方法，對演化演算法在機器學習方面的應用並沒有被廣泛接受。演化演算法在一些非凸優化問題，經典的組合優化問題上取得了不錯的效果，然而一直以來因為過於依賴啟發式的策略設計演算法並且包含複雜的隨機行為,使得很難對其進行理論分析,因而目前還缺乏嚴格的理論基礎,尤其是當演化演算法作為優化演算法應用時的性能缺乏理論保障。理論基礎的缺乏一方面阻礙了演化演算法的進一步發展，另一方面也阻礙了演化演算法在對計算性能有嚴格要求的問題上的應用。

周志華教授相信演化演算法在應用中神祕成功的背後必定有其理論解釋。在這樣一個想法的驅使之下，周志華教授的學生 俞揚博士以 演化計算的理論研究為博士研究課題，錢超博士也相繼投入該領域的研究。這一研究歷程經歷了十餘年之久。在開始研究演化演算法時，就面臨著一個非常尷尬的兩邊不討好的境地，在演化計算領域，理論研究過於滯後，根本無法對實際的演算法有指導意義，因此基本少有人關注演化計算的理論進展，而在人工智慧領域，更是艱難，當時演化計算已經是在頂級會議上冷下去的話題。

經過周志華等研究者的共同努力，目前演化學習已經不再是完全缺乏理論支撐的玄學，其關鍵部分上已經有了理論結果，並且對演算法設計能夠給出一定的指導，使得演化學習成為一個有理論基礎的研究領域。這本書大部分內容都是三位作者在過去近二十年裏取得的研究成果。

本書包含四部分內容：

第一部分介紹了演化學習，機器學習，多目標優化和一些基礎預備知識。

第二部分給出了關於演化學習最重要的兩個性質：時間複雜度和近似能力的理論分析方法。這一部分給出的方法是演化學習理論分析的通用性基礎工具。

第三部分給出了關於演化學習的關鍵技術環節的理論分析，包括演化演算法的運算元、表徵、評估和種羣等。

第四部分以選擇性集成等機器學習任務為例，展示瞭如何分析和設計有理論支撐的演化學習演算法。

2 分章節概覽

2.1 對應書的 part 2 Analysis Methodology

談到優化演算法有兩個最基本的命題：1演算法複雜度，2演算法能否收斂到最優（很多時候無法收斂到最優，則退而求其次分析與最優的距離）。這兩個命題在傳統的數學優化領域和機器學習領域的理論分析非常多。演化計算的理論核心問題也是上面這兩個點，我們想知道加入交叉運算元，變異運算元或者各種改進的策略對演算法到底有什麼影響，是否能夠使得演算法變好。演化計算中大量的參數到底代表著什麼意義，如何科學地選取這些參數。演化計算一般求到的是近似最優解，那麼這個近似到底有多麼近？實際上面的問題到目前為止也沒有一個非常完美的答案。

在過去的二十年間，在運行效率方面，演化計算的核心理論是平均演算法複雜度。舉例來說pseudu-Boolean linear problems 被廣泛的應用來分析演化計算的效率和演算法參數該如何給定。有趣的是，我們常常會得到相反的結論，例如在一些問題中加入 recombination operators 可以提升演算法的效率，但在另外一些問題上加入recombination operators 則沒有明顯的效果。又例如在一些問題中採用比較大的種羣規模會比較有效，而在另外一些問題中大的種羣規模並沒有顯著的作用。這是因為各式各樣不同類型的優化問題具有非常複雜和非常不同的特性。當演化計算面對各式各樣不同類型的優化問題的時候，我們需要一個相對一般的工具或者理論幫助和指導我們來設計更好的演化計算方法，而不是僅僅是完全盲目的從零開始去試湊。

本章的核心點是建立了首次達到時間（first hitting time)和收斂率（Convergence rate）之間的關係。並且依據這個橋樑關係提出了一種基於收斂率的演化演算法複雜度分析方法,並對多種演化演算法在困難問題上的複雜度下界進行了分析。如下圖所示是首次達到時間 和收斂率之間關係

具體內容可參考演化學習一書的第三章內容和參考文獻[1]

2.2 對應書的 part 3 Theoretical Perspectives

演化計算在對問題求解的過程中往往會遇到一些問題，演化計算理論部分主要圍繞如何針對這些問題從計算時間複雜度的角度進行分析，從而可以對演算法的設計上提供一些幫助。

• 演化演算法的問題邊界

隨著優化問題規模的擴大，這些大規模問題存在很多不同的結構，因此的對演化演算法的分析在這些問題上就變得困難許多。這裡提供了一個可以簡化分析的方法，即對問題進行分類，將大規模問題分成容易解決和困難兩類問題。困難的問題要結合問題的實例和演算法共同分析才能得到解決。 那麼，這部分就主要討論一下對演算法獨立的問題的邊界識別，找到「困難或者簡單」問題邊界的好處是可以研究一個演算法在一類問題上的表現，同時提供具體的實例來展示演算法的優缺點。

• 演化演算法中的重組

演化演算法的重組是產生新個體的重要過程，重組的方式根據不同的編碼方式有其對應的重組方法。但是目前對重組操作的理解還出在比較初級的階段，這一章通過分析One-bit和Bit-wise兩種重組操作在MOEA演算法上的時間複雜度，證明瞭重組的一個重要作用是可以加快Pareto front的填充。

• 問題的表示

演化演算法中最重要的一個步驟就是對問題的表示（編碼），同一個問題可以有多種編碼，如實值編碼或者二進位編碼等。不同的編碼要對應不同的變異和重組操作，並且編碼方式的不同也會導致搜索空間的不同，從而影響演化演算法的性能。這裡主要從運行時間的角度分析了一下二進位編碼的GA和用樹結構編碼的GP演算法，測試的問題是the maximum matching 和 minimum spanning tree problems.

• 不正確的適應度函數評估

在有雜訊的環境下，適應度函數的評估有可能是錯誤的，並且雜訊的存在很有可能實際上已經改變了問題的特點，進而將問題變得更為複雜。目前在演化演算法領域已經有很多關於如何處理有雜訊的問題，並且經驗地說明瞭不是所有雜訊都是消極的，有些雜訊甚至可以提高局部搜索演算法的效果。但是目前這些研究都是基於經驗來證明的，本章從運行時間的角度來理論分析雜訊對演化演算法的影響。

• 演化演算法中的種羣

大部分演化演算法在求解過程中都要維護一個解的集合，即種羣。本章分析了種羣的大小和演化演算法運行時間的關係，同時分析了種羣大小對於解魯棒性的影響。目前很多運行時間分析都是基於單獨父代或者單獨子代來進行的，而當同時涉及到多父代和多子代演算法時，分析往往會變得比較複雜。本章主要圍繞瞭解決子代父代個體不一致且大於1的演化演算法在 UBoolean function上的分析進行展開。

• 帶有約束的優化

約束問題是優化問題中的一個重要分支，問題的來源往往是從實際的問題中提煉的。目前對於約束問題的解法往往要避免在不可行區域搜索並且只需要輸出可行解，因為不可行解往往被認為是沒有意義的。演化演算法中也有很多方法來處理這樣的帶約束問題，這些方法中，通常是採用拋棄，修復或者添加懲罰項來處理不可行解。但是一些研究表示，在演化演算法中，不可行解會對最優解的出現有所幫助。這一章通過理論分析了何時不可行解是否有幫助的問題，分析結果顯示當有不可行解參與進化時，會更快的找到最優解。

2.3 對應書的 part 4 Learning Algorithms

集成方法對一個學習問題訓練併合並多個基模型的學習方法，如圖 (a) 所示。選擇性集成方法是從訓練的基模型集合中選擇一部分基模型進行集成，如圖 (b) 所示。選擇性集成模型降低了集成模型的規模，從而可以降低集成模型空間複雜度和預測的時間複雜度。此外，實驗表明，選擇性集成模型和將所有基模型進行集成的方法相比，具有更好的泛化能力。

從優化角度來說，選擇性集成模型本質上是兩個優化目標：提高集成模型的泛化能力和降低基模型的個數。當基模型的個數少於一定條件時，上述兩個目標變成相互衝突的優化目標。換句話說，減少基模型的個數將會降低集成模型的泛化能力，反之則反。優化選擇性集成模型的兩個指標，通常的做法是混合兩個指標為一個優化目標。然而，更為有效的方法是顯示地優化每一個指標，將兩個優化指標作為多目標優化問題。背後的原因是，多目標優化問題可以獲得目標空間每一個帕累託解，而混合後的單目標優化問題只能獲得按照指定的單一方向上的解。演化演算法是基於種羣的優化方法，一次迭代可以獲得一個解集，非常適合解決多目標優化問題。

本章的核心是提出演化多目標優化方法解決選擇性集成學習問題，從理論角度和實驗結果方面分析和驗證了所提的演化多目標優化方法的優越性。此外，本章對機器學習廣泛存在的一般化的問題，子集選擇問題，提出了一系列計算有界計算複雜度的演化多目標優化方法。

3 附全書目錄

註：本文由運籌OR副主編 文雨之，周巖，楊翠娥創作

參考文獻：

[1] Zhou Zhihua Yu Yang, Qian Chao. Evolutionary Learning: Advances in Theories and Algorithms[M]. Spring Verlag, Singapor, 2019.

[2] 俞揚. 演化計算理論分析與學習演算法的研究[D].南京大學,2011.

[3] 南大周志華、俞揚、錢超最新力作：《演化學習：理論與演算法進展》正式上線 https://mp.weixin.qq.com/s/BqgT6UWMcAsKn--oISJKEg

推薦閱讀：