# 臺灣博碩士論文加值系統

(44.210.149.205) 您好！臺灣時間：2024/04/16 20:01

:::

### 詳目顯示

:

• 被引用:1
• 點閱:251
• 評分:
• 下載:26
• 書目收藏:1
 最佳化問題可以區分為數值最佳化問題與組合最佳化問題，基因演算法(Genetic algorithms, GAs)已經被廣泛的應用在解最佳化問題上面，基因演算法搭配多親代交叉方法(multi-parent crossover)常被用來解數值最佳化問題。然而，在解組合最佳化問題方面，還沒有一個有效的多親代交叉方法。Partially mapped crossover (PMX)演算法是解組合最佳化問題方面最常用的交叉方法。在本篇論文中，我們提出了multi-parent partially mapped crossover (MPPMX)。大量的實驗結果顯示出MPPMX改進PMX的比率最高到達38.63 %。而t-test的 p-value在PMX與MPPMX的差異上的值是介於10-6 到10-14之間，也指出MPPMX針對PMX有顯著性的改進。
 Optimization problems are divided into numerical optimization problems and combinatorial optimization problems. Genetic algorithms (GAs) are applied to solve optimization problems widely. GAs with multi-parent crossover are often used to solve numerical optimization problems. However, no effective multi-parent crossover is used for combinatorial optimization problems. Partially mapped crossover (PMX) is the most popular crossover for combinatorial optimization problems. In this thesis, we propose multi-parent partially mapped crossover (MPPMX). A large amount of experimental results show that the improvement ratio of MPPMX reaches 38.63 % over PMX. The p-values of t-test on the difference between MPPMX and PMX range from 10-6 to 10-14, which indicates the significant improvement of MPPMX over PMX.
 1.INTRODUCTION1.1 GENETIC ALGORITHMS1.2 MULTI-PARENT CROSSOVERS1.3 COMBINATORIAL OPTIMIZATION PROBLEMS1.3.1 Traveling Salesman Problem1.3.2 Job Shop Scheduling Problem1.4 ORGANIZATION2.GENETIC ALGORITHMS FOR COMBINATORIAL OPTIMIZATION PROBLEMS2.1 REPRESENTATION2.1.1 Permutation Representation for the TSP2.1.2 Representations for the JSP2.2 SELECTION2.3 CROSSOVER2.3.1 Two-Parent CrossoverPartially Mapped Crossover (PMX)2.3.2 Multi-Parent CrossoverDiagonal CrossoverUniform Scanning Crossover (U-Scan)Occurrence Based Adjacency Based Crossover (OB-ABC)2.4 MUTATION2.4.1 Insertion Mutation2.4.2 Reciprocal Exchange Mutation3.THE PROPOSED METHOD - MPPMX3.1 MULTI-PARENT PARTIALLY MAPPED CROSSOVER (MPPMX)3.1.1 Algorithm3.1.2 Substrings Selection3.1.3 Substrings Exchange3.1.4 Mapping List Determination3.1.5 Offspring Legalization3.1.6 Complexity analysis of MPPMX3.2 MPPMX FOR COMBINATORIAL OPTIMIZATION PROBLEMS3.2.1 MPPMX for the TSP3.2.2 MPPMX for the JSP4.PERFORMANCE EVALUATION4.1 EMPIRICAL ANALYSIS4.2 EXPERIMENTAL RESULTS ON THE TSP4.3 EXPERIMENTAL RESULTS ON THE JSP5.CONCLUSIONS AND FUTURE WORKAPPENDIX A.SETTING AND DATA OF THE EXPERIMENTAL RESULTSA.1 DATA ON THE TSPA.1.1 The solution qualityA.1.2 The convergenceA.1.3 The dataA.2 DATA ON THE JSPA.2.1 The solution qualityA.2.2 The dataREFERENCES
 [1]H. J. Bremermann, M. Rogson, and S. Salaff, “Global properties of evolution processes,” In H.H. Pattee, E.A. Edlsack, L. Fein, and A.B. Callahan, editors, Natural Automata and Useful Simulations, pp. 3-41, Spartan Books, Washington DC, 1966.[2]L. J. Fogel, A. J. Owens, and M. J. Walsh, Artificial Intelligence through Simulated Evolution, John Wiley, 1966.[3]H. Kaufman, “An Experimental Investigation of Process Identification by Competitive Evolution,” IEEE Transactions on Systems Science and Cybernetics, vol. 3, No. 1, pp. 11-16, 1967.[4]S. Tsutusi, “Multi-Parent Recombination in Genetic Algorithm with Search Space Boundary Extension by Mirroring,” Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, pp. 428-437, 1998.[5]A. E. Eiben, “Multiparent Recombination in Evolutionary Computing,” In A. Ghosh and S. Tsutsui, editors, Advances in Evolutionary Computing, Natural Computing Series, Springer, pp. 175-192, 2002.[6]J. H. Holland, Adaptation in Natural and Artificial System, University of Michigan Press, 1975.[7]C. Darwin, The Origin of Species, John Murray, London, 1859.[8]C. K. Ting, “Design and Analysis of Multi-Parent Genetic Algorithms,” Dissertation of University of Paderborn, Germany, 2005.[9]C. K. Ting and H. K. Büning, “A Mating Strategy for Multi-Parent Genetic Algorithms by Integrating Tabu Search,” Proceedings of the 2003 Congress on Evolutionary Computation CEC2003, Canberra, Australia, IEEE Press, pp. 1259-1266, 2003.[10]A. E. Eiben, P-E. Raué, and Zs. Ruttkay, “Genetic Algorithms with Multi-Parent Recombination,” Proceedings of the 3rd Conference on Parallel Problem Solving from Nature, vol. 866 of LNCS, pp. 78-87, 1994.[11]A. E. Eiben, C. H. M. van Kemenade, and J. N. Kok, “Orgy in the Computer: Multi-Parent Reproduction in Genetic Algorithms,” Proceedings of the 3rd European Conference on Artificial Life, vol. 929, pp. 934-945, 1995.[12]A. E. Eiben, C. H. M. van Kemenade, and J. N. Kolk, “Diagonal Crossover in Genetic Algorithms for Numerical Optimization,” Journal of Control and Cybernetics, vol. 26, No. 3, pp. 447-465, 1997.[13]H.-M. Voigt, and H. Mühlenbein, “Gene Pool Recombination and Utilization of Covariances for the Breeder Genetic Algorithm,” Proceedings of the 2nd IEEE International Conference on Evolutionary Computation, pp. 172-177, 1995.[14]H. Mühlenbein and H.-M. Voigt, “Gene Pool Recombination in Genetic Algorithms,” Proceedings of the 6th International Conference on Genetic Algorithms, pp. 104-113, 1995.[15]I. Ono and S. Kobayashi, “A Real-coded Genetic Algorithm for Function Optimization Using Unimodal Normal Distribution Crossover,” Proceedings of the Seventh International Conference on Genetic Algorithms, pp. 246-253, 1997.[16]S. Tsutusi and A. Ghosh, “A Study on the Effect of Multi-Parent Recombination in Real Coded Genetic Algorithms,” Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, pp. 828-833, 1998.[17]S. Tsutsui, M. Yamamura, and T. Higuchi, “Multi-Parent Recombination with Simplex Crossover in Real Coded Genetic Algorithms,” Proceedings of the 1999 Genetic and Evolutionary Computation Conference, pp. 657-664, 1999.[18]D. Gong and X. Ruan, “A New Multi-Parent Recombination Genetic Algorithm,” Proceedings of the 5th World Congress on Intelligent Control and Automation, vol. 3, pp. 2099-2103, 2004.[19]C. K. Ting, “An Analysis of the Effectiveness of Multi-parent Crossover,” In Parallel Problem Solving from Nature VIII, vol. 3242 of LNCS, pp 131-140, Springer-Verlag, 2004.[20]J.P. Caldeira, F. Melicio, and A. Rosa, “Using a Hybrid Evolutionary-Taboo Algorithm to Solve Job Shop Problem,” Proceedings of the 2004 ACM Symposium on Applied Computing, pp. 1446-1451, 2004.[21]M. Garey, D. Johnson, and R. Sethi, “The Complexity of Flowshop and Jobshop Scheduling,” Mathematics of Operations Research, vol. 1, pp. 117-129, 1976.[22]M. Gen and R. Cheng, Genetic Algorithms and Engineering Design, John Wiley and Sons, New York, 1997.[23]M. Gen, Y. Tsujimura, and E. Kubota, “Solving Job-Shop Scheduling Problem Using Genetic Algorithms,” Proceedings of the 16th International Conference on Computers and Industrial Engineering, pp. 576-579, 1994.[24]L. Davis, “Job Shop Scheduling with Genetic Algorithms,” Proceedings of the First International Conference on Genetic Algorithms, pp. 136-140, 1985.[25]F. Croce, R. Tadei, and G. Vlota, “A Genetic Algorithm for the Job Shop Problem,” Computers and Operations Research, vol. 22, pp. 15-24, 1995.[26]U. Dorndorf and E. Pesch, “Evolution Based Learning in A Job Shop Scheduling Environment,” Computers and Operations Research, vol. 22, pp. 25-40, 1995.[27]D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, New York, 1989.[28]D. Goldberg and R. Lingle, “Alleles, Loci and the Traveling Salesman Problem,” Proceedings of the First International Conference on Genetic Algorithms, pp. 154-159, 1985.[29]C. H. M. van Kemenade, J. N. Kok, and A. E. Eiben, “Raising GA Performance by Simultaneous Tuning of Selective Pressure and Recombination Disruptiveness,” Proceedings of the 1995 IEEE International Conference on Evolutionary Computation, pp. 346-351, 1995.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 多父代遺傳演算法於投資組合決策模型之分析研究 2 基因演算法在多目標組合最佳化問題之研究-以旅行推銷員問題為例 3 瓶頸選擇內部節點最小生成樹問題之研究

 1 張錯，〈文學獎的爭議性〉，《文訊》，一三六期，一九九七年二月。 2 張健，〈六十年代的散文｜民國五十年到五十九年〉，《文訊月刊》，一三期，一九八四年八月。 3 張堂錡，〈跨越邊界｜現代散文的裂變與演化〉，《文訊》，一六七期，一九九九年九月。 4 孫治本，〈全球地方化、民族認同與文明衝突〉，《思與言》，三八卷一期，二○○○年三月。 5 胡錦媛，〈遠離非洲，遠離女性：「黑暗之心」中的旅行敘事〉，《中外文學》，二七卷一二期，一九九九年五月。 6 胡錦媛，〈繞著地球跑（下）｜當代台灣旅行文學〉，《幼獅文藝》，五一六期，一九九六年十二月。 7 胡錦媛，〈繞著地球跑（上）｜當代台灣旅行文學〉，《幼獅文藝》，五一五期，一九九六年十一月。 8 胡衍南，〈心靈逍遙遊｜國內中文旅遊書現況〉，《出版情報》，九八期，一九九六年六月。 9 林麗如，〈用生命揮灑大地｜專訪梁丹丰女士〉，《文訊月刊》，一八八期，二○○一年六月。 10 林怡君，〈愛麗絲的旅行：兒童文學中的女遊典範〉，《中外文學》，二七卷一二期，一九九五年五月。 11 林央敏，〈散文出位〉，《文訊》，一四期，一九八四年十月。 12 孟樊，〈風起雲湧的九○年代台灣文壇〉，《文訊雜誌》，二○○○年十二月。 13 李鴻瓊，〈空間．旅行．後現代：波西亞與海德格〉，《中外文學》，二六卷四期，一九九七年九月。 14 李有成，〈理論旅行與文學史〉，《中外文學》，二五卷三期，一九九六年八月。 15 宋美璍，〈自我主體、階級認同與國族建構：論狄福、菲爾定和包士威爾的旅行書〉，《中外文學》，二六卷四期，一九九七年九月。

 1 陣列光纖雷射銲接構裝與銲後位移量測 2 應用關聯規則建構具有方向性之領域知識結構圖--以資訊管理領域為例 3 運用多目標基因演算法於退化性引子設計 4 汽車產業演進之探討-以美日德三國為例 5 策略聯盟夥伴之關係（Guanxi）、信任、聯盟績效及未來繼續合作意願 6 我國公營交響樂團發展現況研究 7 從PAM架構探討高雄市警務機關在職教育訓練變革之研究 8 高雄居民冷氣消費行為及其影響因素之探討 9 應用監測式自然衰減法整治受石油碳氫化合物污染之地下水 10 低溫燒結氧化鋅變阻器粉體配方及熱處理條件之研究 11 蛋白質支鏈結構之螞蟻預測演算法 12 零售業賣場以無線網路進行體驗行銷之關鍵成功因素:以高雄市百貨公司為例 13 台灣可轉換公司債轉換套利之實證研究 14 純銅在減負荷下低週疲勞的微觀組織演化之研究 15 連續性生產事業導入標準成本制度對於績效考核之影響評估-以永豐餘造紙公司為例

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室