多層式多重族群基因規劃法與其應用

Abstract

基因規劃法是屬於演化式計算的一種機器學習方法。其利用模擬生物界之演化機制，以「適者生存」的概念求取滿足給定條件之最佳解。 如何改進基因規劃法的效率，一直是個熱門的研究方向。

分類問題在知識工程中是一個很重要的問題。大部份的分類問題是不能由人力知識進行解決的，因此，如何從資料中找出分類的依據， 是許多機器學習方法被提出的動機。特徵選擇與特徵產生是兩個處理特徵的研究領域，經由對特徵進行適當的處理，在解決分類問題時， 可以提升處理效率與分類準確率。

本篇論文將合併基因規劃法、特徵選擇與特徵產生等三種研究方向，並提出可解決分類問題的多層式多族群基因演算法架構。 傳統的基因規劃法採用單族群機制， 由此族群進行演化模擬而得出最佳解。我們將延伸單族群基因規劃法至多族群基因規劃法，並且提出一種多層式的架構將族群進行整合。 每一層將使用多個族群進行演化模擬，並於下一層進行整合與再演化。此多層式架構不僅可利用多個族群來求得更好的解， 更利用多層式架構將解進行改善與調整。經由實驗，我們將證明此方法具有高度準確性與高效率。另外，為了提高每一族群之學習表現， 我們也提出一個依據平均適應度與剩餘演化世代數之動態突變調整方法。為了解決多類別分類問題， 我們提出一個基於統計理論的解決機制，讓基因規劃法不僅適用於多類別分類問題，更能提高分類準確率。 應用此架構，我們也提出一種融合特徵選擇與特徵產生的方法，並以實驗證明此方法之分類準確率與特徵處理效果。

This study focuses on a proposed method based on genetic programming (GP). Genetic programming is a prominent technique of evolutionary computation (EC). It mimics the evolution mechanism of biological environment to determine optimal solutions for given training instances. Many researchers have been devoted to enhance effectiveness and efficiency of genetic programming. The applications of the proposed method include classification and feature processing. Classification problems play an important role in the development of knowledge engineering. Hidden relations that can be used as a basis for classification are often unclear and not easily elucidated. Thus, many machine learning algorithms have arisen to solve such problems. Feature selection and feature generation are two important techniques dealing with features. Feature selection is capable of removing useless, irrelevant, redundant, and noisy features. Feature generation generates new useful features that could improve classification accuracy. In this study we propose a layered multi-population genetic programming method to solve classification problems. The proposed method that can complete feature selection and feature construction simultaneously is also proposed. The layered multipopulation genetic programming method employs layer architecture to arrange multiple populations. A layer is composed of a number of populations. Each population evolves to generate a discriminant function. A set of discriminant functions generated by one layer will be integrated and be transformed by the successive layer. To improve the learning performance, an adaptive mutation probability tuning method is proposed. Moreover, a statistical-based method is proposed to solve multi-category classification problems. Several experiments on classical classification problems and real-world medical problems are conducted using different configurations. Experimental results show that the proposed methods are accurate and effective.