鏈結學習型基因演算法之設計改進研究

Abstract

鍵結學習 (linkage learning) 功能，是用來使基因演算法 (Genetic Algorithms, GAs) 有能力偵測基因或變數間的相互影響之關聯性，並得以藉由此種資訊，正確而適當地安 排基因或變數在染色體上的位置，以利產生出優良答案的建構基石 (building blocks) 之 重要機制。因此，鏈結學習在基因演算法的設計中，一直是最重要的課題之一。由文獻 中的各項研究可以得知，為了要使得基因演算法能夠發揮其正常的效能，在染色體上表 現出來的建構基石必須群聚於同一區段。為了要讓基因演算法的使用者，可以免除必須 為要處理的問題設計或選擇一個適當的染色體表現方式 (representation)，在基因演算法 中使用各種鏈結學習技術，則是目前的解決方法之一。在現今文獻裡所提出的各項鏈結 學習技術中，鏈結學習型基因演算法 (linkage learning genetic algorithm, LLGA) 使用了 可供鏈結學習的演化式基因實體架構 (genotypic structure)，於演化計算的過程中利用特 殊設計的表示機制來進行鏈結學習，即為本研究計畫中欲加以改進的演算法本體。 儘管鏈結型基因演算法成功地在處理含有對目標函數值貢獻非常不一致的建構基 石 (badly scaled building blocks) 的問題時，達成鏈結學習的目的並從而解決問題；但是 在處理含有貢獻一致之建構基石 (uniformly scaled building blocks) 的問題時，其效能卻 不如預期地好。目前，在文獻中有提出針對鏈結學習型基因演算法在處理含有貢獻一致 之建構基石的問題時所遇到的困難，來進行解釋和說明的收斂時間 (convergence time) 理論模型。此一收斂時間理論模型除了用以解釋困難的徵結所在以外，同時也指出了鏈 結學習型基因演算法在處理該類問題時，理論上的效能障礙。本研究計畫便是根據此收 斂時間模型，改進目前鏈結學習型基因演算法之設計，以期能加強演算法的效能。本計 畫著重於重新設計鏈結學習型基因演算法的表現方式、處理流程、以及執行機制，以避 免於收斂時間模型中所指出之效能障礙的主要因素。此外，本計畫也會以實驗方式驗證 所提出的新設計對鏈結學習型基因演算法效能之提昇。我們相信，本研究計畫除了計畫 結果能改進鏈結學習型基因演算法在處理問題時的效能以外，也能於計畫的執行過程 中，獲得對於該演算法的運作模式與過程有更進一步的理論瞭解及啟發。