臺灣博碩士論文加值系統

本研究之目的著重於測試且應用啟發式尋優方法，驗證其於搜尋多項式普羅比模式之全域最大概似估計值的尋解能力與效率，以發展一個更準確且有效率的多項式普羅比模式校估方法。本研究共測試以下四種尋優方法：分散搜尋法(Scatter Search, SSOrig)、改良之分散搜尋法(SSImp)、結合遺傳演算法與Nelder-Mead鄰近搜尋法之混合演算法(GANM)以及結合遺傳演算法與非線性規劃法之GAMNP校估方法。其中改良之分散搜尋法，乃於分散搜尋法之搜尋階段中，加入篩選機制以挑選出部分較佳之可行解以進行區域尋解，藉以提昇分散搜尋法之尋解效率。
本研究並以四種選項數目(3,5,10,15)與三種不同之變異─共變異矩陣設計一系列的數值實驗，以測試上述四種尋優方法於搜尋多項式普羅比模式之全域最大概似估計值的效能。根據數值實驗的結果可得到以下結論：(1)以概似函數值而言，不論原始或改良的分散搜尋法均較結合遺傳演算法與其他鄰近搜尋法之混合演算法(如GANM或GAMNP)為佳；(2)以求解效率而言，改良的分散搜尋法所需之尋解時間遠比其他尋解方法為短，而且其概似函數值均相當接近於這四種尋優方法可得到之最佳值；(3)在相近的計算時間內，與全域搜尋相較之，鄰近搜尋在分散搜尋法和混合演算法中所扮演的角色較為重要。

This research focused on assessing the efficacy of applying heuristic methods in finding the global maximum likelihood estimates in multinomial probit (MNP) model. Four types of heuristic methods were compared in terms of accuracy and efficiency. They were scatter search (SSOrig), improved scatter search (SSImp) and two hybrid methods─one combined genetic algorithm and Nelder-Mead simplex method (GANM) and the other combined genetic algorithm and nonlinear programming (GAMNP). In an attempt to increase the searching efficiency of the scatter search, a screening mechanism was added to the search procedure of the SSImp to single out more feasible and plausible solutions for further local searches.
A series of numerical experiments differing in numbers of alternative (3,5,10,15) and types of variance-covariance matrix were designed to assess these four types of heuristic methods. The results showed that the performances of both SSOrig and SSImp are better than those of hybrid methods (GANM and GAMNP) in terms of computed likelihood value. As for searching efficiency, the study found that SSImp is the best because the needed searching time is the shortest while the computed likelihood value is comparable to the best value obtained from the four types of heuristic methods. Finally, with similar computational time the local search played a much more important role in scatter search (SSOrig and SSImp) and GANM as compared to the global search.

第一章 緒論................................................1
1.1 問題定義與動機.......................................1
1.2 研究目的與內容.......................................4
1.3 研究方法與求解流程...................................5
1.4 研究流程.............................................6
第二章 文獻回顧............................................7
2.1 前言.................................................7
2.2 多項式普羅比模式之校估方法...........................7
2.3 分散搜尋法（Scatter Search, SS）.....................10
2.3.1 發展歷程....................................10
2.3.2 基本架構....................................11
2.3.3 搜尋流程....................................13
2.3.4 SS的相關應用研究............................14
2.4 混合演算法...........................................22
2.4.1 文獻回顧....................................22
2.5 小結.................................................23
第三章 研究方法............................................25
3.1 前言.................................................25
3.2 最大概似估計法（MLE）................................25
3.2.1 MLE的一般介紹...............................25
3.2.2 MLE在MNP模式的應用..........................27
3.3 向量化蒙地卡羅（VMC）模擬法..........................28
3.3.1 蒙地卡羅模擬法..............................29
3.3.1.1 估算原理.........................29
3.3.1.2 估算步驟.........................30
3.3.2 向量化蒙地卡羅模擬法........................32
3.3.2.1 估算原理.........................32
3.3.2.2 估算步驟.........................33
3.4 參數校估程序中的分散搜尋法...........................33
3.4.1 三項式普羅比模式例子的說明..................35
3.4.2 多樣化解產生方法（DGM）.....................37
3.4.3 改進方法（IM）..............................39
3.4.3.1 NM的初始化.......................40
3.4.3.2 基礎幾何變換之反射變換...........41
3.4.3.3 基礎幾何變換之膨脹變換...........43
3.4.3.4 基礎幾何變換之一維收縮變換.......44
3.4.3.5 基礎幾何變換之多維收縮變換.......46
3.4.3.6 反覆步驟的停止條件和NM參數的設定.47
3.4.3.7 NM完整的搜尋流程.................47
3.4.4 參考解集合更新方法（RSUM）..................49
3.4.5 子集合產生方法（SGM）.......................51
3.4.6 新解合成方法（SCM）.........................52
3.4.7 小結........................................53
3.5 參數校估程序中的混合演算法...........................55
3.5.1 遺傳演算法..................................55
3.5.1.1 GA的初始化.......................58
3.5.1.2 染色體的解碼方式.................58
3.5.1.3 適應函數值的計算方法.............59
3.5.1.4 選擇機制.........................59
3.5.1.5 交配.............................61
3.5.1.6 突變方式.........................62
3.5.1.7 演算法停止條件...................62
3.5.2 鄰近搜尋法在基因演算法中的角色..............62
3.6 小結.................................................64
第四章 數值實驗與結果......................................65
4.1 前言.................................................65
4.2 觀測資料.............................................66
4.3 三項式普羅比模式.....................................69
4.3.1 SSOrig和SSImp...............................70
4.3.1.1 SSOrig和SSImp之間的差別..........70
4.3.1.2 實驗目的.........................72
4.3.1.3 實驗設計.........................73
4.3.1.4 實驗結果與分析...................75
4.3.2 GANM........................................101
4.3.2.1 實驗目的.........................101
4.3.2.2 實驗設計.........................101
4.3.2.3 實驗結果與分析...................102
4.3.3 GAMNP.......................................109
4.3.3.1 實驗目的.........................109
4.3.3.2 實驗設計.........................109
4.3.3.3 實驗結果與分析...................110
4.3.3.4 GAMNP和其它三個校估模式的比較....114
4.4 多項式普羅比模式.....................................115
4.4.1 實驗目的....................................115
4.4.2 實驗設計....................................116
4.4.3 實驗結果與分析..............................116
4.5 小結.................................................117
第五章 結論與建議..........................................119
5.1 前言.................................................119
5.2 結論.................................................119
5.3 建議.................................................120
參考文獻....................................................122
附錄一......................................................127

1. Bolduc, D., 1990. Autoregressive Alternatives in the Multinomial Probit Model. Presented at the TIMS/ORSA Joint National Meeting, Las Vegas, NV.
2. Bolduc, D., 1992. Generalized Autoregressive Errors in the Multinomial Probit Model. Transpn. Res. —B, Vol. 26B, No. 2, 155-170.
3. Campos, V., Glover, F., Laguna, M. and Marti, R., 2001. An Experimental Evaluation of a Scatter Search for the Linear Ordering Problem. Journal of Global Optimization 21, 397-414.
4. Campos, V., Laguna, M. and Marti, R., 1999. Scatter Search for the Linear Ordering Problem. New Ideas in Optimisation, D. Corne, M. Dorigo and F. Glover (Eds.), McGraw-Hill, 331-341.
5. Campos, V., Laguna, M. and Marti, R., 2003. Context-Independent Scatter and Tabu Search for Permutation Problems. University of Valencia, Spain.
6. Chelouah, R. and Siarry, P., 2003. Genetic and Nelder-Mead Algorithms Hybridized for A More Accurate Global Optimization of Continuous Multiminima Functions. European Journal of Operational Research 148 335-348.
7. Corberan, A., Fernandez, E., Laguna, M. and Marti, R., 2002. Heuristic Solutions to the Problem of Routing School Buses with Multiple Objectives. Journal of the Operational Research Society, vol. 53, no. 4, 427-435.
8. Cung, V.-D., Mautor, T., Michelon, P. and Tavares, A., 1997. A Scatter Search Based Approach for the Quadratic Assignment Problem. IEEE International Conference on Evolutionary Computation, 1997, 165-169.
9. Daganzo, C.F., 1979. Multinomial Probit: The Theory and Its Application to Demand Forecasting. Academic Press, New York.
10. Daganzo, C.F., Bouthelier, F. and Sheffi, Y., 1977. Multinomial Probit and Qualitative Choice: A Computationally Efficient Algorithm. Transportation Science, Vol. 11, No. 4.
11. Daganzo, C.F., Shoenfeld, L., 1978. CHOMP User’s Manual. Research Report UCB-ITS-RR-78-7, Institute of Transportation Studies, University of California, Berkeley, CA.
12. Felix, G.L., Belen, M.B., Jose A., M.P. and J. Marcos, M.V., 2003. Parallelization of the scatter search for the p-median problem. Parallel Computing, Volume: 29, Issue: 5, 575-589.
13. Fleurent, C., Glover, F., Michelon, P. and Valli, Z., 1996. A Scatter Search Approach for Unconstrained Continuous Optimization. Proceedings of IEEE International Conference on Evolutionary Computation, 1996, 643 -648.
14. Glover, F., 1977. Heuristics for Integer Programming Using Surrogate Constraints. Decision Sciences, vol 8, 156-166.
15. Glover, F., 1994. Taboo Search for Non Linear and Parametric Optimization with Links to Genetic Algorithms. Discrete Applied Mathematics 49, 231-255.
16. Glover, F., 1997. A Template for Scatter Search and Path Relinking. In: Hao Jk, Lutton E, Ronald E, Schoenauer M, and Snyers D (eds.). Lecture Notes in computer Science 1997, 1363: 13-54.
17. Glover, F., Laguna, M. and Marti, R., 2003. Scatter Search. In Advances in Evolutionary Computing: Theory and Applications, A. Ghosh and S. Tsutsui (Eds.), Springer-Verlag.
18. Greistorfer, P., 2003. A Tabu Scatter Search Metaheuristic for the Arc Routing Problem. Computers and Industrial Engineering, Volume: 44, Issue: 2, 249-266.
19. Habiba, D. and Nabila, A., 2001. Scatter search for SAT and W-MAX-SAT problems. Proceedings of the 33rd Southeastern Symposium on System Theory, 105 —109.
20. Horowitz, J.L., Sparmann, J.M. and Daganzo, C.F., 1982. An Investigation of the Accuracy of the Clark Approximation for the Multinomial Probit Model. Transportation Science, Vol. 16, No. 3.
21. Hung, W.N.-N. and Song, X.-Y., 2001. BDD variable ordering by scatter search. Computer Design, 2001. ICCD 2001. Proceedings. 2001 International Conference on 2001.
22. Hung, W.N.-N. and Song, X.-Y., 2002a. On optimal cell assignments in PCS networks. Performance, Computing, and Communications Conference, 2002. 21st IEEE International , Page(s): 225 —232.
23. Hung, W.N.N. and Song, X.-Y., 2002b. On Data Address Computation for Embedded DSP Systems. ISCAS 2002. IEEE International Symposium on Circuits and Systems, 2002, Volume: 4, 2002, IV-532 -IV-535 vol.4.
24. Hung, W.N.-N., Song, X.-Y., Aboulhamid, E1.M. and Driscoll, M.A., 2002. BDD minimization by scatter search. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume: 21 Issue: 8 , 974 —979.
25. Lagarias, J.C., Reeds, J.A., Wright, M.H. and Wright, P.E., 1998. Convergence Properties of the Nelder-Mead Simplex Method in Low Dimensions. Society for Industrial and Applied Mathematics, Vol. 9, No. 1, 112-147.
26. Laguna, M., 2002. Scatter Search. In Handbook of Applied Optimization, P. M. Pardalos and M. G. C. Resende (Eds.), Oxford University Press, 183-193.
27. Laguna, M. and Armentano, V., (In Press). Lessons from Applying and Experimenting with Scatter Search. To appear in Adaptive Memory and Evolution: Tabu Search and Scatter Search, Cesar Rego and Bahram Alidaee (Eds.).
28. Laguna, M. and Marti, R., 2000. Experimental Testing of Advanced Scatter Search Designs for Global Optimization of Multimodal Functions. Working paper, University of Colorado.
29. Laguna, M., Marti, R. and Campos, V., 1998. Intensification and Diversification with Elite Tabu Search Solutions for the Linear Ordering Problem. To appear in Computers and Operations Research.
30. Laguna, M., Lino, P., Pérez, A., Quintanilla, S. and Valls, V., 2000. Minimizing Weighted Tardiness of Jobs with Stochastic Interruptions in Parallel Machines. European Journal of Operational Research, vol. 127, no. 2, 444-457.
31. Lam, S.-H. and Mahmassani, H.S., 1991. Multinomial Probit Model Estimation: Computational procedures and Applications. Ph.D. Thesis, The University of Texas at Austin, USA.
32. Lerman, S.R. and Manski, C.F., 1981. On the Use of Simulated Frequencies to Approximate Choice Probabilities. Structural Analysis of Discrete Data with Econometric Applications, MIT Press, Cambridge, Massachusetts, 305-319.
33. Liu, Y.-H. and Mahmassani, H.S., 2000. Global Maximum Likelihood Estimation Procedure for Multinomial Probit (MNP) Model Parameters. Transportation Research Part B 34, 419-449.
34. Mahmassani, H.S., Jou, R.-C., 1996. Bounded Rationality in Commuter Decision Dynamics: Incorporating Trip Chaining in Departure Time and Route Switching Decisions. in Theoretical Foundations of Travel Choice Modelling, T. Garling, T. Laitila, K. Westin, ed., Sweden, 201-229.
35. Marti, R, Lourenco, H. and Laguna, M., 2000. Assigning Proctors to Exams with Scatter Search. Computing Tools for Modeling, Optimization and Simulation, Laguna and Gonzalez Velarde (Eds.), Kluwer, 215-227.
36. Martí, R., Laguna, M. and Campos, V., (In Press). Scatter Search Vs. Genetic Algorithms: An Experimental Evaluation with Permutation Problems. To appear in Adaptive Memory and Evolution, Tabu Search and Scatter Search, Cesar Rego and Bahram Alidaee (Eds.).
37. Michlewicz, Z. and Logan, TD, 1994. Evolutionary Operators for Continuous Convex Parameter Spaces. In: Seba;d AV and Fogel Lj (eds.) Proceedings of the 3rd Annual Conference on Evolutionary Programming. World Scientific Publishing, River Edge, NJ, 84-97.
38. Nelder, J.A. and Mead, R., 1965. A Simplex Method for Function Minimization. Computer Journal 7, 308-313.