基於遺傳程式設計在純函數程式設計規範下進行線性遞迴函數之程式合成

Abstract

程式合成是一個致力於從高階規範自動生成電腦程式的領域，遺傳程式設計是實現程式合成的一種常用方法。Push遺傳程式設計 (PushGP)合成堆疊語言，被認為是遺傳程式設計中最先進的程式合成器之一。然而，另一類研究趨勢則專注於合成基於語法的語言，因為其具有可讀性和易於維護的優勢。在本論文中，我們提出了循環結構遺傳程式設計（RSGP），一個生成純函數式程式的新型語法基程式合成器。RSGP定義了一個線性遞迴函數來模擬單層迴圈行為。此外，RSGP使用皮爾森相關係數當作fitness，並利用最小冗餘最大相關性來促進問題分解。實驗結果顯示，RSGP在CountOdds和LastIndexofZero（來自PSB1）、Luhn（來自PSB2）以及4個自行設計問題中的3個問題上成功次數上超越了PushGP、CBGP和HOTGP。此外，實驗結果亦表明，使用皮爾森相關係數和最小冗餘最大相關性特徵選擇雖然能夠鼓勵適當的問題分解，但是代價是降低了在相似鄰域內的搜索能力，因此RSGP利用一種適應機制調整最大相關性特徵選擇的參數來平衡這一取捨，以自動適應不同問題的需求。

Program synthesis (PS) focuses on the automatic generation of computer programs based on high-level specifications, with genetic programming (GP) being a commonly-used method to accomplish this task. PushGP, which operates on a stack-based language, is recognized as a state-of-the-art program synthesizer within the field of GP. Conversely, another area of research emphasizes grammar-based languages for their readability and ease of maintenance. In this thesis, we propose repetitive structure genetic programming (RSGP), a novel grammar-based program synthesizer under the pure functional programming paradigm. RSGP defines a linear recursive function to emulate the behavior of a single-layer loop. Moreover, RSGP uses the Pearson correlation coefficient (PCC) in the fitness and leverages the minimum redundancy maximum relevance (mRMR) feature selection technique to enhance problem decomposition. The experiment results indicate that RSGP outperforms PushGP, CBGP, and HOTGP in terms of the number of successful programs on CountOdds and LastIndexofZero from PSB1, Luhn from PSB2, and 3 out of 4 designed problems. Furthermore, the experiment results also show that employing PCC and mRMR encourages proper problem decomposition, though it comes at the cost of diminishing the search ability within a similar neighborhood. RSGP incorporates an adaptation mechanism to balance this trade-off, automatically adjusting a parameter in the mRMR selection to meet the needs of different problems.