- 學位論文
一個三方演化架構的全域最佳化策略
A Tripartite Evolutionary Architecture for Global Optimization
摘要
全域最佳化(Global optimization)問題是指在開闊的解空間之中找到最佳解，隨著問題的不同，解空間地勢呈現的樣貌也不同，有的高低起伏大、有的則相對平坦，根據天下沒有白吃的午餐原則，很難有一個演算法能夠適用於所有的問題，因此全域最佳化問題至今仍普遍用來測試演算法效能。本研究提出一個三方演化架構，並依此架構實作提出相對點共演化學習式禁忌搜尋法(Opposition-Based Co-evolution Learning Tabu Search, OCLTS)求解全域最佳化問題，演算法以禁忌搜尋法為主要演算法搜尋解空間，並利用Landscape Analysis，記錄演算法走過之路徑，分析演算法到達區域之地勢，藉此預測往後地勢的趨勢，以此調變演算法執行時步伐大小，使之有效對應各種可能情況，並加入重啟(Restart)機制，防止演算法陷入局部最佳解；利用演算法的目前解來產生該解之相對點(Opposition point)，可以在必要時增加演算法的搜尋速度，及得到具有多樣性(Diversity)的解，搭配共演化(Co-evolution)依靠不同群體間互相交換資訊進而互相影響共同進化的方法，可以幫助演算法尋找更佳的解及解決過早收斂的問題。我們以不同維度組合成的多個全域最佳化標竿函數來驗證本研究所提出三方演化架構的效能，結果顯示在多數的標竿函數下可以求得良好的品質。
並列摘要
Global optimization means finding the global optimal solution in the enormous solution space. Due to different problem natures, the fitness landscape varies. Some problems have prickly landscapes some others have smooth ones. According to the No-free-lunch theorem, there exists no such an algorithm that can fit to all kinds of problems, leaving global optimization still a challenging problem. This study proposes a tripartite evolutionary architecture, under which an Opposition-Based Co-evolution Learning Tabu Search (OCLTS) scheme is presented. The OCLTS is majorly based on tabu search and uses landscape analysis to analyze the profile of executed course, so as to predict the landscape of forthcoming course and to adapt the step size of the solution movement. Our method employs the restart mechanism in order to avoid getting trapped by local optimality. The adoption of the opposition point to the incumbent solution is useful in increasing the population diversity. Moreover, the co-evolution scheme is deployed to exchange information between populations such that the premature convergence can be prevented. The performance of the proposed tripartite evolutionary architecture is validated by a number of benchmark global optimization functions. The results show that our method obtains good quality solutions for most of the benchmark functions.