現在位置首頁 > 博碩士論文 > 詳目
論文中文名稱:適度-距離相關性分析之研究 [以論文名稱查詢館藏系統]
論文英文名稱:A Study on Fitness-Distance Correlation Analysis [以論文名稱查詢館藏系統]
院校名稱:臺北科技大學
學院名稱:管理學院
系所名稱:工業工程與管理研究所
畢業學年度:98
出版年度:99
中文姓名:徐浩騰
英文姓名:Hao-Teng Hsu
研究生學號:97378019
學位類別:碩士
語文別:中文
口試日期:2010-06-17
論文頁數:58
指導教授中文名:吳建文
指導教授英文名:Chien-Wen Wu
口試委員中文名:林榮禾;陳鵬文
口試委員英文名:Rong-Ho Lin;Peng-Wen Chen
中文關鍵詞:適度-距離相關性分析區域搜尋二次指派問題訂單排序問題
英文關鍵詞:FDC analysisLocal searchQAPOrder Sequence Problem
論文中文摘要:由於適度-距離相關性分析是驗證演算法成效、分析搜尋空間結構的一個很有用的工具。因此,本研究撰寫出適度-距離相關分析的程式,使用和Stutzle一樣的二次指派問題測試範例來證明程式的正確性。除此之外,本研究將適度-距離相關分析應用在訂單排序的問題上,也證明了適度-距離相關性分析的有效性。
論文英文摘要:The Fitness-Distance Correlation (FDC) analysis is a very useful tool to verify the effectiveness of algorithms and to analyze search space structure. This study designs the FDC analysis programs and uses the same test samples of Quadratic Assignment Problem (QAP) as Stutzle used to demonstrate the correctness of the programs. Moreover, the study applies FDC analysis approach on Order Sequence Problem to prove that the FDC analysis can be applied to other issues effectively.
論文目次:摘 要 i
ABSTRACT ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究架構 2
第二章 文獻探討 5
2.1 搜尋空間的特徵 5
2.1.1 適度環境之分析 5
2.1.2 適度距離相關分析相關文獻 6
2.1.3 適度距離相關分析應用在旅行者問題 13
2.1.4 適度距離相關分析應用在二次指派問題 15
2.2 區域搜尋法 19
2.3 訂單排序 20
第三章 研究方法 22
3.1 問題定義與分析 22
3.1.1 二次指派問題 22
3.1.2 訂單排序問題 23
3.1.3 訂單排序的重要性 24
3.1.4 訂單排序之參數定義及數學模型 25
3.2 研究方法 26
3.2.1 2-opt區域搜尋法 26
3.2.2 相關分析 27
3.3 研究流程 29
3.3.1 FDC應用在QAP 29
3.3.2 FDC應用在訂單排序 32
第四章 實驗設計與實驗結果 35
4.1 實驗設計 35
4.1.1 二次指派問題 35
4.1.2 訂單排序問題 35
4.2 實驗結果 36
4.2.1 二次指派問題 36
4.2.2 訂單排序問題 42
第五章 結論與建議 43
5.1 結論 43
5.2 後續研究與建議 44
參考文獻 45
附錄:實驗結果範例 50
論文參考文獻:[1] T. Stutzle, H. Hoos, “MAX-MIN ant system,” Future Generation Computer Systems, vol 16, no. 8, 2000, pp. 889–914.
[2] T. Stutzle,” Iterated local search for the quadratic assignment problem,” European Journal of Operational Research, vol. 174, no. 3, 2006, pp. 1519-1539.
[3] P.F. Stadler, “Towards a theory of landscapes,” Technical Report SFI–95–03–030, Santa Fe Institute, USA, 1995, pp. 78-163
[4] E.D. Weinberger,” Correlated and uncorrelated fitness landscapes and how to tell the difference,” Biological Cybernetics, vol. 63,no. 5, 1990, pp. 325-336
[5] K.D. Boese, Models for iterative global optimization, Ph.D. Thesis, Computer Science Department, University of California, Los Angeles, USA, 1996.
[6] P. Merz, B. Freisleben, Fitness landscapes and memetic algorithm design, London: McGraw-Hill, 1999, pp. 245–260
[7] T. Jones, S. Forrest,” Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms,” Proceedings of the Sixth International Conference on Genetic Algorithms, Morgan Kaufmann, San Francisco, CA, 1995, pp. 184–192.
[8] K.D. Boese, A.B. Kahng, S. Muddu,” A new adaptive multi-start technique for combinatorial global optimizations,” Operations Research Letters, vol. 16, 1994, pp. 101–113.
[9] L. Kallel, M. Schoenauer, “Fitness distance correlation for variable length representations,”Technical Report 363, CMAP, Ecole Polytechnique, 1996
[10] L. Altenberg,” Fitness distance correlation analysis: An instructive counterexample,” Seventh International Conference on Genetic Algorithms, Morgan Kaufmann, 1997, pp. 57-64
[11] A.B.M. Sultan, R. Mahmud, M.N. Sulaiman, M.R.A. Bakar,” Measuring Metaheuristic Performance over Timetabling Problem Instances Using Fitness Distance Correlation Method,” International Journal of Computer Science and Network 20 Security, vol. 6, no. 6, 2006, pp. 20-22.
[12] P. Merz, Memetic Algorithms for Combinatorial Optimization Problems: Fitness Landscapes and Effective Search Strategies. PhD thesis, Department of Electrical Engineering and Computer ScienceUniversity of Siegen, Germany, 2000.
[13] E. Balas and M.C. Carrera,”A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering,” OPERATIONS RESEARCH, vol. 44, no.2, 1996, pp.875-890.
[14] M. Finger, T. Sutzle, H. Louren,” Exploiting Fitness Distance Correlation of Set Covering Problems,” Applications of Evolutionary Computing: EvoWorkshops, Kinsale, Ireland, 2002, pp. 251-265.
[15] T. Schiavinotto, T. Stützle,”Search space analysis of the linear ordering problem,” Proceedings of the 2003 international conference on Applications of evolutionary computing, Essex, UK, 2003, pp. 322-333.
[16] M. Tomassini, L. Vanneschi, P. Collard, M. Clergue,” A study of fitness distance correlation as a difficulty measure in genetic programming,” Evolutionary Computation, vol. 13, no. 2, 2005, pp. 213-239.
[17] I. Heckman, J.C. Beck,” Fitness-distance correlation and solution-guided multi-point constructive search for CSPs,” Proceedings of the 5th international conference on Integration of AI and OR techniques in constraint programming for combinatorial optimization problem,” Paris, France, 2008, pp. 112-126.
[18] F. Sambo, M.A.M. de Oca, B. Di Camillo, T. Stützle,” On the difficulty of inferring gene regulatory networks: A study of the fitness landscape generated by relative squared error,” In Proceedings of the 9th International Conference on Artificial Evolution, Strasbourg, France, 2009
[19] P. Merz, “Advanced fitness landscape analysis and the performance of memetic algorithms,” Evolutionary Computation, vol. 12, no.3, 2004, pp. 303-325.
[20] H.J. Park, T.L. Williams, Lecture Notes in Computer Science, New Orleans, LA: Springer Berlin / Heidelberg, 2009, pp. 331-342
[21] M. Kubiak, A. Jaszkiewicz, P. Kominek,”Fitness-distance analysis of a car sequencing problem,” Foundations of Computing and Decision Sciences, Vol. 31, No. 3-4, 2006, pp. 263-276
[22] B. Draskoczy, Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2010, pp. 47-58.
[23] S. Kirkpatrick, G. Toulouse,”Configuration space analysis of travelling salesman problems,” J. de Physique , vol. 46, no. 8, 1985, pp. 1277–1292
[24] H. Mühlenbein, “Evolution in time and space — the parallel genetic algorithm,” Morgan Kaufmann, San Francisco, CA, 1991, pp. 316–337.
[25] E.D. Taillard, “Comparison of iterative searches for the quadratic assignment problem,” Location Science, vol 3, no. 2, 1995, pp. 87-105.
[26] S. Lin, "Computer Solutions of the Traveling Salesman Problem," Bell Syst. Tech J. 44, 1965, pp. 2245-2269.
[27] G.A. Croes, “A Method for Solving Traveling-Salesman Problems,” Operations Research, vol 6, no. 6, 1958, pp. 791-812.
[28] M.R. Garey, D.S. Johnson and R. Sethi, “The complexity of flowshop and jobshop Scheduling,” Mathematics of Operations Research, vol. 1, 1976, pp. 117-129.
[29] X.G. Dong, H.K. Huang and P. Chen, “An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion,” Computers & Operations Research, vol. 36, 2009, pp. 1664-1669.
[30] J.Y. Liu and C.R. Reeves, “Constructive and composite heuristic solutions to the P// scheduling problem,” European Journal of Operational Research, vol. 132, 2001, pp. 439-452.
[31] J.M. Framinan and R. Leisten, “An efficient constructive heuristic for flowtime minimisation in permutation flow shops,” OMEGA, vol. 31, 2003, pp. 311-317.
[32] X.P. Li, C. Wu C, “An efficient constructive heuristic for permutation flow shops to minimize total flowtime,” Chinese Journal of Electronics, vol. 14, no. 2, 2005, pp. 203-208.
[33] T. Yamada and C.R. Reeves, “Solving the permutation flowshop scheduling problem by genetic local search.” Proceedings of IEEE international conference on evolutionary computation, 1998, pp. 230-234.
[34] C. Rajendran and H. Ziegler, “Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs,” European Journal of Operational Research, vol. 155, 2004, pp. 426-438.
[35] C. Rajendran, H. Ziegler, “Two ant-colony algorithms for minimizing total flowtime in permutation flowshops,” Computers and Industrial Engineering, vol. 48, 2005, pp. 789-797.
[36] M.F. Tasgetiren, Y-C Liang, M. Sevkli and G. Gencyilmaz, “A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem,” European Journal of Operational Research, vol. 177, 2007, pp. 1930-1947.
[37] A. El-Bouri, S. Balakrishnan and N.Popplewell, “A neural network to enhance local search in the permutation flowshop,” Computers and Industrial Engineering, vol. 49, 2005, pp. 182-196.
[38] E.M. Loiola, N.M.M. de Abreu, P.O. Boaventura, P. Hahn, T. Querido,” A survey for the quadratic assignment problem,” European Journal of Operational Research, vol 176, no. 2, 2007, pp. 657-690.
[39] J.M. Jarvis and E.D. McDowell,” Optimal product layout in an order picking warehouse,” IIE Transactions, vol. 23, no. 1, 1991, pp. 93-102.
[40] C.C. Jane, “Storage location assignment in a distribution center,” International Journal of Physical and Logistics Management, vol. 30, no. 1, 2000, pp. 55-71.
[41] 游志青、林士彥編譯,統計學(下冊),台中:滄海書局,2003,第271-273頁。
[42] 江建良編著,統計學,台北縣:普林斯頓國際有限公司,2005,第422-426頁。
論文全文使用權限:不同意授權