臺灣博碩士論文加值系統

解最佳化問題為許多研究領域的重要課題，演化式計算為解最佳化問題的有效方法之一，而粒子群最佳化又為新近發展的一種演化式計算演算法。一般而言，使用專家經驗而為問題特別設計的演算法較能更有效率地解決特定的最佳化問題。然而，欲解最佳化問題的研究學者大部份具有該問題領域的知識，但欠缺發展演算法的經驗能力。本研究試圖發展一個通用型的粒子群最佳化演算法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.

摘 要 i
ABSTRACT ...ii
誌 謝 .iv
目 錄 ..v
表 目 錄 .vii
圖 目 錄 ...viii
一、緒論 ........1
1.1 研究背景與動機 ......1
1.2 研究目的 ..2
1.3 論文架構 ..2
二、相關研究 ..4
2.1 粒子群最佳化演算法 ..4
2.2 直交實驗設計 ..6
2.2.1 直交表 .6
2.2.2 兩水準直交表的產生方式 ....7
2.2.3 多水準直交表產生方式 ........8
2.2.4 因素分析 .9
2.2.5 直交實驗 .......10
2.3 Local Search ...10
2.4 智慧型粒子移動機制步驟 ...........10
2.5 Dynamic Multi-Swarm Particle Swarm Optimizer with Local Search 介紹......... 11
2.6 Orthogonal Particle Swarm Optimization(OPSO)介紹 .......12
2.7 基因演算法與GPPSO 比較 .........12
2.7.1 基因演算法簡介 ...12
2.7.2 傳統基因演算法與粒子群演算法的操作對應 .........14
2.7.3 傳統基因演算法與粒子群演算法的相異之處 .........15
三、提出GPPSO 方法論 ...16
3.1 想法起源 16
3.2 理論基礎 16
3.3 GPPSO 之設計 ......18
3.3.1 GPPSO 流程 ...18
3.3.2 由直交實驗求出GPPSO 參數 19
3.3.3 GPPSO 的方法全貌敘述 ......20
3.3.3.1 直交表初始化 ...........20
3.3.3.2 Local search .20
3.3.3.3 智慧型粒子移動機制 ...21
3.4 GPPSO 與基因演算法的操作對應 ..........21
四、實驗結果與效能分析 ..............23
4.1 測試函數介紹 ....23
4.2 實驗說明 26
4.3 實驗設計 27
4.3.1 PSO 的預設參數 .27
4.3.2 GPPSO 中個機制的實驗結果 ...........33
4.3.2.1 單純的PSO，與加入均勻取樣初始化的PSO 的實驗結果比較...33
4.3.2.2 單純的PSO，與加入local search 的PSO 的實驗結果比較..........34
4.3.2.3 單純的PSO，與加入modified IMM 的PSO 的實驗結果比較......34
4.3.3 CEC 2005 special session dimension 10 及 dimension 30 實驗結果...........35
4.3.4 GPPSO 與Dynamic Multi-Swarm Particle Swarm Optimizer with Local
Search 的比較 .42
4.3.5 GPPSO 與其他演算法比較 .43
4.3.6 GPPSO 與OPSO 的比較 ....45
4.3.7 GPPSO 演算法複雜度 .........45
4.3.8 GPPSO 中個機制的收斂速度比較 .....48
五、結論 .57
5.1 結論 ..57
5.2 未來展望 ..57
參考文獻 .58
附錄一 .....60

[1] S. Forrest and M. Mitchell. “Relative buildingblock fitness and the building-block
hypothesis,” FOGA-92. Proc. of Workshop on Foundations of Genetic Algorithms and
Classifier Systems, pp.109-126, 1992.
[2] C. Darwin, On the origin of species. London: John Murray, 1859.
[3] J. Kennedy and R. C. Eberhart, “Particle swarm optimization, ” in Proc. IEEE Conf.
Neural Networks IV, Vol. 4, pp. 1942-1948, 1995
[4] J. Kennedy, R. C. Eberhart and Y. Shi, Swarm Intelligence, San Francisco: Morgan
Kaufmann, 2001.
[5] H.-M. Chen, B.-F. Liu, H.-L. Huang, S.-F. Hwang, and S.-Y. Ho*, "SODOCK:
Swarm Optimization for Highly Flexible Protein-Ligand Docking," Journal of
Computational Chemistry, vol. 28, pp. 612-623, 2007. (SCI)
[6] S.-Y. Ho, H.-S. Lin, W.-H. Liauh and S.-J. Ho, "OPSO: Orthogonal Particle
Swarm Optimization and Its Application to Task Assignment Problems," accepted by IEEE
Trans. Systems, Man, and Cybernetics -Part A, Systems and Humans, 2006. (SCI, EI)
[7] J. J. Liang and P. N. Suganthan, "Dynamic Multi-Swarm Particle Swarm
Optimizer with Local Search," IEEE Congress on Evolutionary Computation,
vol. 1, pp. 522-528, 2005.
[8] M. S. Phadke, Quality Engineering Using Robust Design. Englewood Cliffs. NJ:
Prentice-Hall, 1989.
[9] S. H. Park, Robust Design and Analysis for Quality Engineering. Chapman &
Hall, 1996
[10] Y.-W. Leung and Y. Wang, “An orthogonal genetic algorithm with quantization for
global numerical optimization,” IEEE Trans. Evolutionary Computation, vol. 5, no. 1,
pp. 41-53, Feb. 2001.
[11] A. Dey, Orthogonal Fractional Factorial Designs. New York:Wiley, 1985.
[12] A. S. Hedayat, N. J. A. Sloane, and J. Stufken, Orthogonal Arrays: Theory and
Applications. New York: Springer-Verlag, 1999.
[13] J. J. Liang, and P. N. Suganthan, "Dynamic Multi-Swarm Particle Swarm Optimizer,"
Proc. of IEEE International Swarm Intelligence Symposium, pp. 124-129, 2005.
[14] P. N. Suganthan, N. Hansen, J. J. Liang, K. Deb, Y.-P. Chen, A. Auger, and S. Tiwari,
"Problem Definitions and Evaluation Criteria for the CEC 2005 Special Session on
Real-Parameter Optimization," Nanyang Technological University Technical Report,
Singapore May 2005 AND KanGAL Technical Report No. 2005005, IIT Kanpure, India 2005.