具自我調適能力的模糊遺傳演算法及其應用

Abstract

遺傳演算法是一個有效的搜尋方法，並且兼具強韌的搜尋結果與有效率的 搜尋時間等優點。在本篇論文中，我們將介紹兩種新方法，進一步改良傳 統的遺傳演算法。在許多真實的問題中，在決策的不同階段應該採用不同 的策略；具有這種特質的問題，我們稱之為多階段性問題。我們的第一個 研究方向著眼在多階段性問題的求解上。再者，在大部份的情形中，階段 與階段間並無明確界限；模糊理論正適合用來描述這種性質。我們發展了 兩套新技術以整合模糊理論與遺傳演算法：模糊化的特徵與模糊多倍染色 體。在第二個研究方向中，我們在遺傳演算法中加入自我調適的能力。我 們發展出一套動態的環境適存程度的測度方法；藉由這個方法，將使得演 化能持續進行，並提供更強軔的搜尋結果。為了驗證新方法的效力，我們 做了兩個實驗。首先，我們將我們的方法應用於電腦博奕：黑白棋中。由 於劇烈的棋局變化，黑白棋是一個極具挑戰性的遊戲。甚者，我們將新方 法應用於難度更高，更複雜，更有價值的實驗：台灣證券投資分析。我們 期望藉由這些實驗證明我們的方法是有效並可廣泛應用的。 It is known that genetic algorithms (GAs) are an effective search method which also have the advantages of robustness and efficiency. In this thesis, we introduce two new ideas to further improve GAs. The first direction is focused on solving it multi-stage problems, which have the property that different strategies should be employed in different stages. Since the boundaries between stages are rather fuzzy than crisp, fuzzy theories are suitable for describing these characteristics. We introduce two ways of incorporating fuzzy theory into GAs, i.e, fuzzily characterized features and fuzzy polyploidy. In the second approach, we add a self-adaptive function to traditional GAs. A dynamic fitnesst echniques was developed, which is helpful for continuous evolution and robust solution. We expect to improve not only the quality but also the efficiency of GA search by using these twomethods. Two experiments were presented in this thesis to verify the power of our new methods. First, we tested our idea in the domain of Othello game playing, which is an challenging game because of the drastic board changes that result from moves. Second, an even more difficult problem, Taiwan stock market investment analysis, was used to validate the effectiveness and robustness of our methods.