實數變數離散化研究：應用於實數最佳化之離散模型建構式遺傳演算法

Abstract

實數最佳化廣泛應用於智慧灌溉、無人機路徑規劃等領域，近年在研究與實務上均受到高度重視。然而，這類問題常同時具有高維度與多峰性，使得求解更加困難。 在高維度情境下，現今的最佳化方法（如 RV-GOMEA）雖展現出優異的搜尋能力，但其模型建構與相依結構的維護成本會隨變數數量增加而快速攀升，進而顯著提高記憶體需求。當問題規模擴大時，記憶體消耗可能呈現急遽成長，使其難以在個人電腦環境中穩定部署，也會對硬體資源受限的邊緣運算場景帶來額外負擔。 為在維持搜尋能力的同時降低資源需求，本研究採用延伸式精簡基因演算法（ECGA）作為最佳化後端。相較於 RV-GOMEA，ECGA 具備更緊湊的模型表示，可有效抑制維度成長所帶來的記憶體開銷，進一步提升方法在通用運算環境與邊緣運算場景中的可行性與部署彈性。 在此基礎上，本文進一步提出一種創新的離散化策略，稱為偏斜多維按需分割（smSoD），針對可分解的高維多峰實數最佳化問題設計，以因應高維度與多峰性並存所造成的搜尋困難。相較於既有的多維按需分割（mSoD），smSoD 透過分析競爭式選擇機制下的樣本分布特性（以球面函數為分析基礎），將切分點由隨機選取改為依據當前樣本分布動態決定。 實驗結果顯示，在兩組基準測試套件——可分解連結問題（decomposable linkage problems）與擴展版 CEC 2014 基準測試（extended version of the CEC 2014 benchmark）——中，無論在已知或未知連結資訊的情境下，smSoD 在高維度設定下展現出最佳的平均排名。在這些情況中，smSoD 的表現優於 mSoD 以及 CEC 2014 競賽優勝演算法 L-SHADE。此外，在僅有 1 GB 記憶體限制的嚴格條件下，smSoD 相較於 RV-GOMEA 同樣達成最佳平均排名，突顯其在計算資源受限的實際應用環境中具備強大的潛力。

Real-valued optimization is widely applied in areas such as smart irrigation and UAV path planning, and has attracted significant attention in both research and practice in recent years. However, such problems often exhibit both high dimensionality and multimodality, which makes them particularly difficult to solve. In high-dimensional settings, modern optimization methods (e.g., Real-valued GOMEA (RV-GOMEA)) can demonstrate strong search capability, but the costs of model construction and dependency-structure maintenance rise rapidly as the number of variables increases, resulting in substantial memory requirements. As the problem scale grows, memory consumption can increase sharply, making stable deployment on personal computers difficult and imposing additional burdens in resource-constrained edge-computing scenarios. To reduce resource demands while preserving search performance, this study adopts the extended compact genetic algorithm (ECGA) as the optimization backend. Compared with RV-GOMEA, ECGA provides a more compact model representation, which effectively curbs the memory overhead caused by increasing dimensionality, thereby improving feasibility and deployment flexibility in general computing environments and edge-computing scenarios. Building on this, we further propose an innovative discretization strategy called skew multidimensional split-on-demand (smSoD) to address the search difficulty arising from the coexistence of high dimensionality and multimodality. Compared with the existing multidimensional split-on-demand (mSoD), smSoD analyzes the sample-distribution characteristics induced by tournament selection (with the spherical function used as the basis of analysis) and replaces random split-point selection with a mechanism that dynamically determines split points according to the current sample distribution. Experimental results on two benchmark suites—decomposable linkage problems and an extended version of the CEC 2014 benchmark—under both known and unknown linkage settings show that smSoD achieves the best average ranking in high-dimensional settings. In these cases, smSoD ranks ahead of mSoD and L-SHADE (the CEC 2014 competition winner). Furthermore, under a stringent 1 GB memory constraint, smSoD also attains the best average ranking relative to RV-GOMEA, highlighting its strong practical potential in computationally resource-constrained environments.