複雜結構之演化：應用結構調適與多倍體於多狀態問題之研究

Abstract

自然界的演化是多樣與奇妙的。本篇研究著眼在由簡單到複雜與動態環境的兩個重要的演化現象。而遺傳演算法提供了一個簡化的演化平台，很適合應用於這些重要演化現象的模擬與探索。藉由簡單到複雜的過程，自然界的生物演化出了複雜的遺傳機制，例如適合在動態環境下生存的多倍體結構。本篇論文發展了一結構調適的模型，並將傳統的單倍體遺傳演算法延伸為多倍體。結構調適模型主要包含了結構的複雜化，結構的精簡化與結構的自我演化等概念。我們同時發展了結構延展、結構縮減與結構強制同型等遺傳運算來實現以上的概念。再者，我們也發展了兩個控制多倍體表現型的方法，控制基因與顯隱性函數。 本篇論文的目標是希望能夠加強傳統的遺傳演算法於解決具多狀態特性的動態問題上。在一個多狀態問題中，問題的最佳解會隨著問題的狀態而改變。例如投資問題，投資者往往會依據是市場目前的狀態，而使用不同的投資策略。自然界的多倍體提供了生物擁有兩組以上生存策略的能力，很適合應用多狀態問題。狀態與狀態之間的界限，有些是模糊而重疊的，有些則是明確的。針對這兩種類型，我們也發展了不同的機制來分別解決。 我們提供了三組實驗來測試所提出的多倍體與結構調適的模型。三組實驗分別為：多狀態的背包問題、多狀態的函數最佳化問題與模糊控制器的自動學習。實驗結果驗證了所提出的模型不僅可以有效的解決多狀態問題，也可已演化出合適的多倍體結構，兼具效能與效率上的優點。

Natural evolution, which guides organisms' adaptation to the natural environment, is marvelous and fascinating. This study considers two important properties of natural evolution, a {\it simple-to-complex\/} process and a {\it dynamic environment\/}. Based on simple-to-complex evolution, natural organisms have developed complex chromosomal structures such as polyploids, which help them to survive in a dynamic environment. Genetic algorithms (GAs), which include several simple operators to simulate the process of biological adaptation, are feasible evolutionary platforms to explore these natural properties. Many real world problems are hard to solve by artificial intelligence systems, because of their dynamic properties. In nature, polyploidy facilitates organisms' having dynamic survival strategies. This fact motivates the extension of the haploid encoding used by conventional GAs to a complex form, {\it polyploid\/}, to solve dynamic strategy problems. The proposed method is expected to enable GAs to solve a special kind of dynamic strategy problems, {\it multi-state problems\/}, in which different problem solving strategies should be employed in different problem states. The dominance function can be represented in either a fuzzy or a crisp way according to the characteristics of the problem since the boundaries between states may be fuzzy in a multi-state problem. Two dominance mechanisms, including {\it regulator genes\/} and {\it dominance functions\/}, are proposed to control the phenotype of a polyploid. In practice, genetic algorithms cannot easily obtain optimal solutions when the chromosome structure is too complex, because a complex structure, such as that of polyploid, always involves a large search space. This study proposes a {\it structural adaptation\/} model, which comprises the concepts of structural variation, simple-to-complex evolution, and selection, to overcome the difficulty of a large search space. In the structural adaptation model, a population of individuals with the simplest structure initially, progressively develops new survival strategies by structural variation, and the selection determines the appropriate polyploid structures. This study also presents three basic structural operations, {\it structural expansion, structural deletion\/}, and {\it structural coercion\/} to simulate random structural variation in nature. A series of experiments, including solving non-stationary knapsack problems, optimizing multi-state Dejong functions, and modeling fuzzy systems, are presented to verify the polyploid and structural adaptation. The experimental results demonstrate that the proposed model can effectively solve multi-state problems, and find both the optimal solution and the optimal polyploid structure.