基於子空間映射與多臂吃角子老虎機技術之實數最佳化

Abstract

本論文提出了一新的實數多模態(multimodal)最佳化方法。大多數的現實問題都可以由多個單峰問題合成。而對於實數最佳化，我們較感興趣的是多模態且可被拆解成多個階層化的單峰問題。然而，一旦面對多模態問題，我們就必須面對利用性(exploitation)與探索性(exploration)的問題。本論文提出一解決多模態問題的技巧。此技巧結合了階層式聚合(hierarchically clustering)與最小描述長度(minimum description length)， 來辨識搜尋空間中可能的單峰模型。接著，我們使用一加一演化策略((1+1)-Evolutionary Strategy)來最佳化一齊次座標(homogeneous coordinate)上的線性轉換矩陣，並利用此矩陣將原搜尋空間投影到另一有良好邊界定義的子空間。此投影嘗試定義出只包含一單峰之感興趣區域(region of interest)。最後，我們提出一新的多臂吃角子老虎(multi-armed bandit)技術，來分配給各個子空間的資源，以最大化獲得全域最佳解的機率，我們將此結果與自適應共變異數矩陣演化策略(Covariance Matrix Adaptation Evolution Strategies)、標準粒子群演算法(Standard Particle Swarm Optimization 2011)、與實數域蟻群演算法(Ant Colony Optimization for Continuous Domain)結合，並利用CEC 2005實數最佳化測試問題來比較結果。

This thesis presents a new technique for real-valued multimodal optimization.Most of the real-world problems can be described as a composition of unimodal subproblems. For real-valued optimization, we are interested in problems that are composed of multiple hierarchically decomposable unimodals. However, allocating resources to exploit different unimodals leads to the common dilemma between exploration and exploitation. This thesis propose some new techniques that aim to solve multimodal problems more efficiently. A new technique combining hierarchical clustering and minimum description length is proposed to help identify potential unimodals in the search space. Then, a linear transform matrix in homogeneous coordinate, optimized by the (1+1)-Evolutionary Strategy, projects the search space to a subspace with well-defined boundary. This projection aims to define a region of interest that isolates a unimodal subproblem. Finally, a new multi-armed bandit technique, aiming to maximize the probability of acquiring the global optimum, is proposed to allocate resources for each unimodal. We combined our new techniques with Covariance Matrix Adaptation Evolution Strategy, Standard Particle Swarm Optimization 2011, and Ant Colony Optimization for Continuous Domain. The results are evaluated with the special session on real-parameter optimization benchmark problems of CEC 2005.