引入重組運算子與動態鏈結開發技術於粒子群最佳化演算法

Abstract

粒子群最佳化演算法(PSO)為一有效率之演化計算演算法，近年更有許多改良粒子群最佳化演算法的研究持續進行中，其中針對粒子群最佳化演算法與基因演算法(GAs)之結合的主題亦已成為熱門研究。另一方面，於基因演算法中，如何有效處理基因鏈結(Genetic linkage)問題亦成為有效改良基因演算法效能的重要議題。因此於本論文中，主要欲達成之目標有二。第一，我們透過引入基因鏈結之概念於粒子群最佳化演算法中，藉以提昇其搜尋之效能。為了完成之目標，我們必須瞭解粒子群最佳化演算法及基因鏈結問題之特性，並尋找適當的結合模式以有效發揮兩者的功能。除此之外，我們希望能完成之另一目標為有效處理、辨識實數問題之基因鏈結，而為達成此一目標，我們必須設計一個特別的基因鏈結辨識技術。 於此篇論文中，我們假設基因鏈結於實數問題中是存在且隨著搜尋過程中而產生變動。於此假設前提下，我們設計了動態基因鏈結開發技術(dynamic linkage discovery technique)來處理基因鏈結問題，此技術為根據適者生存之自然淘汰為概念所設計，為有效且計算成本低廉的基因鏈結辨識技術。此外，為了有效提昇粒子最佳化演算法及基因鏈結辨識結合的效能，我們亦設計了重組運算子(recombination operator)，透過操作使用動態基因鏈結開發技術所辨識出的建構基石(building blocks)，粒子群最佳化演算法便能有效的處理存在於實數問題中的基因鏈結。 因此於此研究中，我們藉由引入動態基因鏈結開發技術來處理實數問題中的基因鏈結，搭配重組運算子的運作以提昇粒子群最佳化演算法的效能。最後我們透過仔細設計的各項數學函式做為評估實驗，針對所提出的演算化做效能上的評估分析，而由實驗的結果也可知，我們所設計的演算法確有完成提昇效能的目標。