針對符號回歸之值域與綁定基因編程演算法

Abstract

基因編程演算法是一種利用群體中程式個體重組、突變、選擇操作，進行演化以達到生成完成目標的程式的演算法。本論文提出了一種針對符號回歸問題的基因編程演算法，以利用程式語法資訊和語義資訊讓演化更有效率。提出的演算法由兩個機制組成，綁定機制與值域機制。綁定機制是針對語法資訊所設計，藉由保護族群中常見的兩層結構函式來避免在重組操作中重要的結構被破壞。值域機制是針對語義資訊所設計，藉由當前程式的輸出範圍與目標的輸出範圍之大小差異，來選擇重組中的子樹對象，用以保留父代的優異性。此兩種機制在實驗中顯示在實際應用資料集中具有優於其他當代方法的最佳化能力。此外，此演算法在綁定機制中存在一個待保護的常見函式的個數，是一個需調整的參數，因此本論文使用了適應機制來自動調整此參數。最後，前期實驗顯示此演算法在高維度中相較其他當代方法會有較不穩定的表現，為此本論文提出了基於最小冗餘最大相關特徵選擇演算法進行降維，得到更穩定的表現。

Genetic programming is an evolutionary algorithm that utilizes recombination, mutation, and selection operations in a population to evolve programs. This thesis presents a genetic programming algorithm specifically designed for symbolic regression problems, aiming to utilize both syntax and semantic information for more efficient evolution. The algorithm consists of two mechanisms: the binding mechanism and the ranging mechanism. The binding mechanism protects frequently occurring two-layer function structures during recombination to preserve their importance. The ranging mechanism adjusts the selection of subtrees for recombination based on the difference between the output range of the current program and the target output range, aiming to retain the superiority of the parent programs. Empirical results demonstrate that ranging-binding genetic programming outperforms other contemporary methods in terms of the mean absolute error on Penn machine learning benchmarks. However, two issues are identified: the need to adjust the number of protected functions as a parameter and the algorithm's instability in high-dimensional problems. To automatically adjust the number of protected functions in the binding mechanism, an adaptive mechanism is proposed to automatically adjust this parameter. Furthermore, to stabilize the performance in high-dimensional problems, a feature selection based on minimum redundancy maximum relevance is proposed for dimensionality reduction, resulting in more stable performance.