禁忌搜尋法與一個差異集合間的整體學習共演化

Ensemble-Based Coevolution of Tabu Search and a Diversification Set

紀權展(Cyuan-Jhan Ji)

指導教授 ： 尹邦嚴

國立暨南國際大學/管理學院/資訊管理學系/碩士(2016年)

摘要

全域最佳化(global optimization)問題的特性與組合最佳化 (combinatorial optimization) 問題不同，但兩者同樣非常具有挑戰性和重要性。近年來應用次經驗法則(Meta-Heuristic)儼然成為解決全域最佳化問題的常見方法之一。本研究提出以文獻相對點共演化學習式禁忌搜尋法 (尹邦嚴, 楊天祿, 2014)為基礎，加入整體學習(Ensemble Learning)的概念，整體學習演算法是利用系統化的方式挑選目前搜尋階段最適合的演算法策略及其參數，藉由過去執行的效果來調整下一次挑選的權重。搭配禁忌搜尋法演化中所取得的差異化集合，並使用以下三種演算法策略:(1)路徑重劃(Path-relinking)以廣域(exploration)的方式進行搜尋，(2)全面式學習(Comprehensive learning)可進行分割維度的合作學習，(3)算術交配(Arithmetic crossover)。再以爬山法(Hill climbing)進行深度搜尋進而獲得較佳的實驗結果。本研究兩種標竿函數各以不同維度進行全域函數最佳化的驗證，實驗結果顯示我們的演算法具有一定的求解能力。

關鍵字

全域最佳化 ； 整體學習 ； 全面式學習 ； 路徑重劃 ； 算術交配

並列摘要

The characteristics of global optimization are different to those of combinatorial optimization, but both of which are very challenging and important. Recent years, researchers resorted to the use of metaheuristics as a basis for settlement to solve global optimization problems. This study presents modifications to the reference (尹邦嚴, 楊天祿, 2014) which proposed a coevolutionary framework consisting of a tabu search and a diversification set of various solutions. We employ the ensemble learning approach which systematically selects alternative strategies and the associated parameter values deemed most appropriate for the current search phase. In this paper, three algorithmic strategies are considered and they are: (1) path-relinking - an exploration strategy, (2) comprehensive learning – a dimensional decomposition learning strategy, and (3) arithmetic crossover - an exploitation strategy for digging the region between the current solution and the best opposition point. Finally, to further improve the obtained solution, the hill-climbing heuristic is applied. Two well-known benchmark datasets of global optimization functions have been experimented with, the experimental results show that our approach is superior to a number of state-of-the-art methods in global optimization.

並列關鍵字

global optimization ； ensemble learning ； comprehensive learning ； path-relinking ； arithmetic crossover

參考文獻

一、 　中文部分

尹邦嚴、楊天祿(民103年11月)。相對點共演化學習式禁忌搜尋法之全域最佳化。2014年臺灣作業研究學會年會暨海運物流學術研討會，基隆：國立臺灣海洋大學。

二、 　英文部分

Bagheri, M. A., Gao, Q., & Escalera, S. (2013, December). A framework towards the unification of ensemble classification methods. In Machine Learning and Applications (ICMLA), 2013 12th International Conference on (Vol. 2, pp. 351-355). IEEE.

Bhardwaj, M., Bhatnagar, V., & Sharma, K. (2016). Cost-effectiveness of classification ensembles. Pattern Recognition, 57, 84-96.