全域搜尋與區域搜尋分工對最佳化演算法效能影響之分析

Abstract

全域搜尋與區域搜尋之間的分工一直是最佳化演算法裡的最受關注的課題之一，而隨著迷因演算法(memetic algorithm)這類以全域搜尋和區域搜尋分工為特色的演算法盛行，此課題更顯重要。雖然迷因演算法已成功廣泛應用在不同的領域裡，這些各式各樣的研究結果與理論推導，因其專注問題與演算法的不同，仍無法提供與解釋最佳化演算法達到最佳的全域搜尋與區域搜尋分工的關鍵機制。本論文提出區域搜尋地區(local search zone)的概念來描述最佳化演算法裡全域搜尋與區域搜尋的分工行為。基於此概念，我們建立了一個適用於一般迷因演算法行為的理論模型，並更進一步在幾個具代表性的最佳化演算法原型上，使用區域搜尋地區概念和其理論模型，分析探討一些常見的最佳化機制與參數對全域搜尋與區域搜尋分工以及演算法效能影響。本論文所提出的理論模型，經過理論推導和實驗驗證，可描述一個具代表性的迷因演算法原型於不同問題上全域搜尋與區域搜尋的分工行為。而在探討最佳化機制與參數對演算法效能影響上，區域搜尋地區的概念亦提供了一個能合理解釋最佳化演算法全域搜尋與區域搜尋分工行為的系統化分析。整體而言，本論文提供了一個解釋最佳化演算法行為的觀點與方法，希望此觀點能給予設計最佳化演算法一些洞悉。

The synergy between exploration and exploitation has been a prominent issue in optimization. The rise of memetic algorithms, a category of optimization techniques which feature the explicit exploration-exploitation coordination, much accentuates this issue. While memetic algorithms have achieved remarkable success in a wide range of real-world applications, the key to successful exploration-exploitation synergy still remains obscure as conclusions drawn from empirical results or theoretical derivations are usually quite algorithm specific and/or problem dependent. In this study, we propose the concept of local search zones in an attempt to delineate the collaboration between exploration and exploitation in optimization algorithms on a broad class of objective functions. Based on this concept, we establish a theoretical model for general memetic algorithms and further conduct investigations on the effect of different optimization mechanisms on the collaboration between exploration and exploitation as well as optimization performance on different classes of problems. In the investigations, the concept of local search zones and the established theoretical model are adopted as basis to interpret the behavior of various archetypes of optimization algorithms. As this approach is capable of providing an unified and reasonable interpretation to the behavior of different algorithm-problem complexes in the investigations, the concept of local search zones may be a potential model providing an unified perspective to the physics behind manifold optimization algorithms and further give insights into the design of optimization algorithms.