論文研讀-元啟發式算法的平移、縮放和旋轉不變變異算子的設計原則

• 更多內容請關注許志偉課題組官方中文主頁：https://JaywayXu.github.io/zh-cn/
• 分享一篇由田野老師、張興義老師、何成老師、KC老師、金耀初老師發表在電子學報英文版上的論文。與大家一起學習，歡迎討論以及批評指正。
• Tian Y, Zhang X, He C, Tan K C, Jin Y. CIE, 2023. Principled design of translation, scale, and rotation invariant variation operators for metaheuristics[J]. Chinese Journal of Electronics, 2023, 32(1): 111–129.

• 僅供學術分享, 相關課題最新進展歡迎訪問BIMK-platemo官方主頁：https://github.com/BIMK/PlatEMO

1. 引言

1.1 元啟發式算法的重要性

元啟發式算法（Metaheuristics）廣泛應用于復雜優化問題的求解，其性能和搜索行為在很大程度上依賴于核心的變異算子（Variation Operators）。這些算子的設計通常受到自然現象的啟發，并在多種優化場景中表現出顯著的適應性。例如：

• 遺傳算法（GA）
  基于進化理論和遺傳定律設計，主要通過父代個體的交叉操作和后代個體的變異操作生成新解。交叉和變異算子為 GA 提供了強大的探索能力，使其在多模態問題上表現優異【16】【17】。

• 差分進化（DE）
  利用兩個解的加權差分實現變異，對處理復雜變量耦合問題表現出色【18】。

• 協方差矩陣適應進化策略（CMA-ES）
  基于種群學習多變量正態分布模型，動態采樣新解，在眾多實際優化問題中展現了卓越性能【19】。

• 粒子群優化（PSO）
  模擬鳥群行為，將個體歷史最佳和全局最佳結合，用于粒子位置更新，從而實現快速收斂【20】。

盡管現有變異算子在各自領域展現了不同的優勢，但它們的性能和適應性往往受到優化問題特性或搜索空間特性的限制，這顯著影響了算子的魯棒性和泛化能力。

1.2 當前變異算子面臨的問題

元啟發式算法的魯棒性和廣泛適應性依賴于變異算子對 搜索空間的獨立性（Search Space Independence）。搜索空間獨立性要求算子在以下搜索空間變換下保持一致的性能：

• 平移變換 (\(x' = x + b\))：算子在問題空間平移時性能不受影響。
• 尺度變換 (\(x' = ax\))：算子在問題空間尺度變化時保持一致性。
• 旋轉變換 (\(x' = xM\))：算子在問題空間旋轉時保持穩定性。

當前的研究對如何實現這些不變性特性提供了一定的理論支持：

• CMA-ES 通過步長與當前最優解的距離成比例實現了平移不變性【21】。
• DE 的變異算子采用多父代加權求和，因此滿足旋轉不變性【22】。

然而，這些研究依然存在以下關鍵痛點：

1. 缺乏系統性理論定義
   尚未有數學上嚴格的定義來描述算子如何實現平移、尺度和旋轉不變性。

2. 缺乏充分必要條件
   當前研究未能明確提出實現這些不變性特性的充分和必要條件，導致無法從理論上分析算子是否具備這些屬性。

3. 設計依賴于經驗
   當前變異算子的設計多基于領域專家的經驗，缺乏系統性和自動化的方法。這種設計方式限制了算子的魯棒性和泛化能力。

1.3 研究目標

為了解決上述挑戰，本文提出了一種系統化的框架 AutoV，以理論和實踐相結合的方式克服現有變異算子設計中的局限性：

理論目標

1. 系統性地定義變異算子在平移、尺度和旋轉變換下不變性的數學表達。
2. 提出實現這些不變性特性的充分必要條件，為算子設計提供理論依據。

實踐目標

1. 構建一個自動化算子設計框架 AutoV，將算子設計問題轉化為參數優化問題，通過進化算法生成高性能的變異算子。
2. 在設計過程中顯式地融入不變性要求，確保生成的算子在多種搜索空間變換下表現穩定。

驗證目標

1. 通過實驗驗證所生成算子在多模態、大規模優化問題上的適應性和魯棒性。
2. 比較 AutoV 生成的算子與經典變異算子的性能，證明其有效性和廣泛適用性。

2. 理論背景與不變性條件

在第二節中，作者通過數學推導給出了變異算子滿足平移、縮放和旋轉不變性所需的條件，并定義了這些不變性屬性的數學形式。這為后續算子設計提供了理論基礎。

2.1 平移不變性

平移不變性解釋

根據定義 1，平移不變性要求：

即，當搜索空間發生平移（所有父代解加上一個常數偏移量\(b\)）時，變異算子的輸出也只受到\(b\)的平移影響，而保持不變的相對差異。這一性質確保了算子對解的絕對位置不敏感。

現有算子的平移不變性

以下算子具有平移不變性：

• SBX（Simulated Binary Crossover）
  通過模擬二元交叉的方式生成后代，不依賴解的絕對位置，因此滿足平移不變性。

• DE（Differential Evolution，差分進化）
  DE 的變異算子依賴于父代解的差分進行操作（如\(x_{1d} + F \cdot (x_{2d} - x_{3d})\)），完全消除了絕對位置的影響。

• CMA-ES（Covariance Matrix Adaptation Evolution Strategy）
  CMA-ES 的步長調整和種群更新基于分布中心，獨立于搜索空間的絕對位置。

• FEP（Fast Evolutionary Programming）
  FEP 通過分布采樣和變異機制生成后代解，不依賴父代解的絕對位置，因此滿足平移不變性。

2.2 縮放不變性

縮放不變性解釋

根據定義 2，縮放不變性要求：

其中，\(a\)為任意非零常數。這意味著，當搜索空間的尺度發生變化（所有決策變量被乘以相同的比例\(a\)）時，變異算子的輸出應當同比例縮放，而不會受到其他影響。這一特性確保算子在不同尺度的搜索空間中具有一致的表現。

現有算子的縮放不變性

以下算子具有縮放不變性：

• SBX（Simulated Binary Crossover）
  SBX 的變異過程基于父代解的相對差異，比例縮放不影響其結果。

• DE（Differential Evolution，差分進化）
  DE 的變異算子通過父代解的差分計算變異，比例系數\(F\)是常數，因此具有縮放不變性。

• CMA-ES（Covariance Matrix Adaptation Evolution Strategy）
  CMA-ES 中的步長調整與當前種群分布的尺度成正比，且均值向量更新基于歸一化權重，從而滿足縮放不變性。

不具有縮放不變性的算子

• FEP（Fast Evolutionary Programming）
  FEP 的步長未與決策空間的尺度成比例關聯，因此其變異算子不滿足縮放不變性。

2.3 旋轉不變性

旋轉不變性解釋

根據定義 3，旋轉不變性要求：

其中，\(M\)為任意正交矩陣。這意味著，當搜索空間發生旋轉變換（每個決策向量與正交矩陣\(M\)相乘）時，變異算子的輸出會同步旋轉，但其內在關系保持不變。這一特性確保算子在旋轉搜索空間時的表現一致性。

現有算子的旋轉不變性

以下算子具有旋轉不變性：

• DE（Differential Evolution，差分進化）
  DE 的變異算子依賴父代解之間的差分項（如\(x_2 - x_3\)），這一差分項在旋轉后仍然保持正確的方向關系。根據公式（17）和（18），DE 的變異算子滿足：

因此，DE 是 旋轉不變 的。

不具有旋轉不變性的算子

以下算子不具有旋轉不變性：

• SBX（Simulated Binary Crossover）
  SBX 的變異算子形式為：

其中\(B\)為一個標量，因此其更新僅依賴于特定方向上的差分，不能保持旋轉后的差分關系。

• CMA-ES（Covariance Matrix Adaptation Evolution Strategy） 和 FEP（Fast Evolutionary Programming）
  CMA-ES 和 FEP 的更新方式均依賴于種群或決策空間的具體方向分布，而非決策變量間的內在相對關系，因此不滿足旋轉不變性。

3. 旋轉-縮放-平移 不變算子的一般范式

平移、縮放和旋轉不變性算子的條件

根據定理 3，一個連續可微的變異算子同時具有 平移不變性、縮放不變性 和 旋轉不變性 的充要條件為其滿足以下形式：

其中：
-\(r_1, r_2, r_3, \ldots\)為任意實數常數。

• 權重\(r_1 + r_2 + r_3 + \ldots = 1\)。

這一公式體現了算子的線性組合形式，同時約束了權重的歸一化性質，從而確保其在不同搜索空間變換下的魯棒性。

結論與推論

根據定理 3，可以推導出以下結論：

1. 縮放不變性：
   任意滿足公式 (61) 的算子都具有縮放不變性。

   • 原因：算子輸出是父代解的加權和，權重滿足歸一化條件，輸出與輸入的尺度變化成正比。

2. 縮放和平移不變性：
   如果權重滿足\(r_1 + r_2 + r_3 + \ldots = 1\)，則算子同時具有縮放和平移不變性。

   • 原因：加權和的歸一化消除了偏移對算子的影響。

3. 縮放和旋轉不變性：
   如果\(r_1, r_2, r_3, \ldots\)為常數（即不依賴于搜索空間的方向或位置），則算子同時具有縮放和旋轉不變性。

   • 原因：權重的常數性質確保算子在旋轉變換后的輸出與原始方向一致。

4. 旋轉-縮放-平移 不變算子的設計原則

4.1 變異算子參數化

在第 4.1 節中，作者系統地提出了參數化變異算子的設計方法，并結合公式 (69) 和公式 (70) 詳細說明了如何通過優化隨機化的權重參數和引入多參數集，生成魯棒性強、性能優越的變異算子。以下是該節的核心內容分析。

公式 (69)：隨機化變異算子

公式 (69) 是 AutoV 提出的核心變異算子的隨機化表達形式：

公式 (69) 的設計思想

1. 隨機化權重分布：

   • 權重\(r_i\)被定義為服從正態分布的隨機變量：
   \[ r_i \sim \mathcal{N}(\mu_i, \sigma_i^2) \]

   -\(\mu_i\)：權重的均值，表示變異算子的主要方向。
   -\(\sigma_i\)：權重的標準差，表示隨機化程度。

   • 隨機化引入了變異算子的多樣性，使其能夠在搜索過程中生成多樣化的解，提升搜索效率并增強跳出局部最優的能力。

2. 約束條件：

   • 權重\(r_i\)滿足歸一化約束：
   \[ \sum_{i=1}^{t} r_i = 1 \]

   這一條件保證了變異算子符合公式 (61) 的理論要求，從而滿足 平移不變性、縮放不變性 和 旋轉不變性。

3. 優化目標：

   • 算子的設計被轉化為優化正態分布參數\(\mu_i\)和\(\sigma_i\)的問題。
   • 通過優化這些參數，公式 (69) 能夠生成符合不同搜索場景需求的變異算子。

公式 (69) 的意義

• 提升魯棒性：隨機化權重分布允許算法適應不同的優化問題，特別是在復雜和多模態搜索空間中。
• 性能平衡：通過隨機采樣，公式 (69) 能夠在理論不變性要求和實際性能需求之間找到平衡點。
• 理論與實踐結合：在數學上滿足公式 (61) 的充分必要條件，同時在實踐中通過優化參數實現靈活性。

公式 (70)：多參數集矩陣表示

公式 (70) 進一步擴展了公式 (69)，通過引入 多參數集 的二維矩陣表示，提升算法的多樣性與性能適應性：

矩陣設計的核心思想

1. 參數集的多樣性：

   • 矩陣中的每一行代表一個參數集（parameter set），即一組用于生成變異算子的正態分布參數。
     -\(\mu_{ji}\)和\(\sigma_{ji}\)：分別表示第\(j\)個參數集第\(i\)個權重的均值和標準差。
     -\(p_j\)：表示選擇第\(j\)個參數集的概率。

2. 動態選擇機制：

   • 通過輪盤賭選擇方法（roulette-wheel selection）按\(p_j\)概率選擇一個參數集。
   • 選定的參數集決定變異算子權重的分布，從而動態適應不同優化需求。

3. 多樣化搜索行為：

   • 每個參數集對應不同的搜索行為（如全局搜索、局部搜索或特定方向性搜索），從而提升算法的靈活性與適應性。

矩陣設計的意義

• 旋轉不變性與性能平衡：

  • 在某些場景下，嚴格的旋轉不變性可能限制搜索靈活性。
  • 多參數集設計允許算法在不同權重配置之間切換，實現不變性與性能的平衡。

• 增強魯棒性：

  • 通過動態選擇不同參數集，減少算法陷入局部最優的風險。

• 優化問題的轉化：

  • 算子設計問題被轉化為矩陣中所有參數（\(\mu_{ji}, \sigma_{ji}, p_j\)）的優化問題，通過進化算法優化這些參數，生成高性能算子。

公式 (69) 和 (70) 的協同作用

• 公式 (69) 提供了隨機化的變異算子模型，通過優化正態分布的參數生成具有理論不變性要求的算子。
• 公式 (70) 將隨機化模型擴展為多參數集矩陣，進一步增強了算法在復雜優化問題中的適應性與魯棒性。

4.2 AutoV算法流程

• 進化算子的搜索整體遵循遺傳算子。比較有趣的是圖中標紅的區域，即 “如何評價進化算子”，“如何生成新的進化算子”

評價生成的進化算子

• 重復運行優化算法多次，其中優化算法中的個體變異算子使用算法1中的進化算子。取多次運行的最佳個體的適應度函數值的中位數作為進化算子的評價指標。具體偽代碼如算法2所示。
  

如何生成進化算子

• 由于本文提出的就是一種進化變異算子，因此其中的參數矩陣-公式（70）所示，可以由當前的，進化得到的最佳的進化算子-即當前世代的公式（70）中的矩陣按照公式（71）中的進化方式代入到公式（69）中對當前進化算子進行進化-即 自己進化自己