應用於支向機分類器與彈性多工排程問題之最佳化演算法設計

Optimization Algorithms Design for Support Vector Machine Classifier and Flexible Job-shop Scheduling Problem

呂俊良(Chun-Liang Leu)

指導教授 ： 翁慶昌

淡江大學/工學院/電機工程學系博士班/博士(2009年)

https://doi.org/10.6846/TKU.2009.00767

摘要

本論文提出兩種單目標混合型最佳化演算法來改善支向機分類器的分類正確率以及兩種多目標最佳化演算法來解決彈性多工排程問題。在支向機分類器的設計上，本論文提出一種可與輸入訓練資料的順序無關的動態濃縮最近鄰居點的演算法，其可以減少因冗餘或雜訊之訓練樣本在分類過程中所造成的影響。然後我們提出分別使用基因演算法與粒子群演算法來將重要代表點的建立、特徵的選取、以及支向機的核心函數之參數設定等三項同時做最佳化處理。本論文提出GA-DCNN-SVM與PSO-DCNN-SVM兩種混合型最佳化演算法，並且和其他先前已公開發表的演算法做比較，經由多種的UCI標準測試資料集的實驗顯示，本論文所提出的混合型演算法可改善支向機的分類正確率，並且表現優於現存的方法。此外，在彈性多工排程問題上，本論文首先提出一個多目標粒子群演算法以尋找問題的多目標最佳解。在此方法中，本論文提出一個有效的編碼法來將粒子的實數值拆成整數部份與小數部份，並且分別表示機器選擇與任務順序，再提出一個循序指派的解碼機制來得到合理可行的排程候選解。因此標準實數型的粒子群演算法整合突變運算的演算法架構即可用來求解彈性多工排程問題。最後，我們提出一個新的多目標蒙地卡羅樹狀搜尋演算法，本論文提出一個循序的機器與任務的指派混合編碼方式來將原來演繹式架構的問題轉換成樹狀搜尋架構的問題，並且採用NSGA-II非支配解排序的計算方式來修改原始的UCT公式，使其適用於求解多目標的問題，然後就可以應用所提出的多目標蒙地卡羅樹狀搜尋演算法來求解彈性多工排程問題。經由與其他演算法的比較，可驗證所提出兩種方法確實可以有效地解決彈性多工排程問題。

關鍵字

支向機分類器 ； 彈性多工排程問題 ； 動態濃縮鄰居 ； 多目標粒子群最佳化 ； 蒙地卡羅樹狀搜尋

並列摘要

In this dissertation, two types of single-objective hybrid model are proposed to improve the classification rate for Support Vector Machine (SVM) classifier and two effective multi-objective optimization algorithms are developed to solve Flexible Job-shop Scheduling Problems (FJSP). In the optimization design for SVM classifier, an order-independent algorithm for the data reduction, called the Dynamic Condensed Nearest Neighbor (DCNN) rule, is proposed to adaptively construct prototypes in training dataset and to reduce the redundant or noisy instances in a classification process for the SVM classifier. Furthermore, two hybrid models based on the Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) algorithm are adopted to simultaneously optimize the prototype construction, feature selection, and the SVM kernel parameters setting. Several UCI benchmark datasets are considered to compare the proposed GA-DCNN-SVM and PSO-DCNN-SVM approaches with the other previously published methods. The experimental results show that the developed hybrid models outperform the existing method and improve the classification accuracy for the support vector machine. In the optimization design for FJSP, an evolutionary Multi-Objective Particle Swarm Optimization (MOPSO) approach is adopted and successfully applied to find the optimal Pareto solutions for FJSP. An effective encoding method is proposed to divide the continuous real value into both integer and decimal numbers, which indicates the machine selection and operation order, respectively. By using the sequential assignment decoding mechanism, a feasible schedule is always obtained and the standard continuous PSO algorithm incorporated with the mutation operator can be adopted. Finally, a Multi-Objective Mote-Carlo Tree Search (MOMCTS) algorithm is proposed to solve the FJSP. The Sequential Operation-Machine Assignment (SOMA) scheme for encoding representation is first introduced to always produce feasible solutions, and then the evolution-based FJSP mapping to a general tree search structure via SOMA is successively completed. The modification of formal UCT (Upper Confidence Bound Apply to Tree) algorithm by using the non-dominated sort strategy makes it suitable for the characters of multi-objective problems, and the Pareto-optimal solutions for FJSP can be obtained. Compared to some developed algorithms, the experimental results illustrate the effectiveness of the both proposed methods for FJSP.

並列關鍵字

Support Vector Machine (SVM) Classifier ； Flexible Job-shop Scheduling Problems (FJSP) ； Dynamic Condensed Nearest Neighbor (DCNN) ； Multi-Objective Particle Swarm Optimization (MOPSO) ； Mote-Carlo Tree Search (MCTS)

參考文獻

[1] K. Deb, Optimization for Engineering Design: Algorithm and Examples, New Delhi: Prentice-Hall, 1995.

[2] K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley, 2001.

[3] V.N. Vapnik, Statistical Learning Theory, Wiley, New York, 1998.

[4] D. L. Luo, S. X. Wu, M.Q. Li, and Z. Yang, “Ant colony optimization with local search applied to the flexible job shop scheduling problems,” ICCCAS conference in Communications, Circuits and Systems, 2008, pp. 1015-1020.

[5] W. Xia and Z. Wu, “An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems,” Computers and Industrial Engineering, vol. 48, 2005, pp. 409-425.