基於均值移動之自適應共變異數矩陣演化策略

Abstract

本論文將一個基於均值移動(mean shift)的計算模型，導入自適應共變異數矩陣演化策略(covariance matrix adaptation evolution strategies, CMA-ES)。所導入之均值移動程序提供了群聚功能。這可以使我們同時提供多組的自適應共變異數矩陣演化策略模組，平行地探索解空間中不同的區域。本論文創新的地方在於，我們不需要事先給定所需要模組的數目。我們利用均值移動的分群功能，經由在自適應共變異數矩陣演化策略樣本中的核密度估測，來判定合適的自適應共變異數矩陣演化策略模組個數。將每個演算法模組視為解空間中個別的自適應共變異數矩陣演化策略代理者，增強了其全域最佳化的能力。我們將所提出之基於均值移動之自適應共變異數矩陣演化策略(mean shift based covariance matrix adaptation evolution strategies, MS-CMA-ES)套用在多漏斗函數(multi-funnel functions)之最佳化上，用來驗證本論文所提演算法之效能。實驗結果說明了演算法在多峰(multimodal)、多漏斗函數下可以得到不錯的實驗效能。

We introduce a computational module based on mean shift procedure into the evolution strategies with covariance matrix adaptation (CMA-ES). The introduced mean shift procedure provides functions of clustering which allows us to apply multiple CMA-ES instances to explore different parts of the search space in parallel. The novelty of our approach is that we do not require the number of CMA-ES instances as a parameter; instead, we apply a mean shift-based mode detection method to the kernel density estimator of the selected points from the CMA-ES samples to determine the number of CMA-ES instances. The global exploration ability is enhanced by the concept that each instance forms a separate CMA-ES agent to explore different parts of the search space. We evaluate the performance of the new mean shift-based evolution strategies with covariance matrix adaptation (MS-CMA-ES) on the optimization of multi-funnel functions. The new MS-CMA-ES algorithm shows better performance on non-convex, multi-funnel functions. Keywords: mean shift, evolution strategy with covariance matrix adaptation, optimization.