設計高效能的通用型粒子群最佳化演算法

Abstract

解最佳化問題為許多研究領域的重要課題，演化式計算為解最佳化問題的有效方法之一，而粒子群最佳化又為新近發展的一種演化式計算演算法。一般而言，使用專家經驗而為問題特別設計的演算法較能更有效率地解決特定的最佳化問題。然而，欲解最佳化問題的研究學者大部份具有該問題領域的知識，但欠缺發展演算法的經驗能力。本研究試圖發展一個通用型的粒子群最佳化演算法GPPSO來解決各類型的最佳化問題。GPPSO 使用了三個技巧來克服一些難題，如函數之參數間較強交互作用，具有眾多局部最佳解的函數及具大量最佳化參數的函數：1)以均勻取樣來建立初始的粒子族群，2)使用局部搜尋運算子的輔助，3)利用智慧型的粒子移動機制。GPPSO的高效能主要是源於使用直交實驗設計，藉由直交表和因素分析，能有效增加廣度和深度的搜尋效能；均勻取樣的初始粒子族群能增加求解的穩定性。本論文針對GPPSO的主要參數加以分析，提供預設值，亦可加以調整。本論文使用文獻提供的標準測試函數庫，實驗結果顯示GPPSO與現有粒子群最佳化方法比較，其效能良好，可以作為解最佳化問題的通用型演算法。

Solving optimization problems is an important issue in many research domains. Evolutionary computation is one efficient method to solve optimization problems and particle swarm optimization (PSO) is a newly-developed algorithm of evolutionary computation. Generally speaking, the customized algorithm using expert experience can more efficiently solve specific optimization problems. However, the most researchers of solving optimization problems often have knowledge of application domains but not ability of developing the algorithm. This study aims to develop an efficient general-purpose particle swarm optimization (GPPSO) algorithm to solve various kinds of optimization problems. GPPSO utilizes three techniques to cope with the difficulties of intractable functions such as strong interactions among parameters, multi-modal function and large number of parameters: a) initial particle swarm of uniform sampling, b) Solis and Wets local search and c) intelligent move mechanism. The high performance of GPPSO arises mainly from an orthogonal experimental design with orthogonal array and factor analysis which can effectively advance the search performance of exploration and exploit. Furthermore, the proposed initialization of particle swarm can advance robustness of obtained solutions. The main control parameters of GPPSO are analyzed and their default values of parameters are suggested or user-defined. This study utilizes some benchmarks to evaluate GPPSO by comparing existing particle swarm optimization methods. The simulation results reveal that GPPSO performs well and can be served as an efficient general-purpose algorithm of solving optimization problems.