臺灣博碩士論文加值系統

本研究旨在探討分散式基因演算法中，相關的演化參數對於其計算成本與解題精確度的影響分析。由於分散式基因演算法解題的精確度與運算成本均比傳統基因演算法表現較好，因此是一個特別適合運用於複雜性高的最佳化問題之演算法，且可運用的問題領域極廣，但隨著問題複雜度的提高與範圍的擴大，解題的品質與效能一直是各方研究的焦點。
由最佳化的觀點出發，我們將調整群體規模、遷移時機以及遷移率進行多次求解實驗，針對結果探討如何利用調整相關參數改善演化效能，並嘗試利用資料探勘推導出各遷移參數與適應值的關係式，以找出最佳的遷移參數組合，進一步提升預測解題的效果與品質，最後我們將其結果應用於最大值求解、生產排程最佳化、旅行銷售員與具時窗限制之車輛途程含回程取貨等不同領域的最佳化問題。

While probing into distributed genetic algorithms (DGAs) in this research purport. The design of distributed genetic algorithms (DGAs) aims to achieve computation efficiency than that of genetic algorithms. DGAs are suitable for solving complex optimization problems in many areas. As the optimization problems become more complex, more attention will focus on the problem-solving quality and efficiency of DGAs.
Our research is trying to determine the optimal parameters of DGAs Initial Migration Generation, Migration Rate and Migration Interval to improve the Fitness Values of objective function in a more efficient way. We apply the obtained parameters in solving the Max Ones and Job Shop optimization problems. At present these optimal migration parameters are derived by observing summary statistics. We apply the results in Max Ones, Job Shop Scheduling, Traveling Salesman Problem, and Vehicle Routing Problem with Time Windows Constraint. The outcomes of the experiments indicate better computation performance can be derived. In the future, we will construct a formula consisted of the three migration parameters, Starting Migration Generation, Migration Rate and Migration Interval, and the Fitness Value.

1. 緒論 1
1.1. 研究背景與動機 1
1.2. 研究目的 1
1.3. 重要性 2
2. 文獻探討 3
2.1. 基因演算法 3
2.1.1. 源由 3
2.1.2. 運作方式 3
2.1.3. 運算元 4
2.1.4. 控制參數 5
2.2. 分散式基因演算法 5
2.2.1. 運作流程 6
2.2.2. 島嶼模式(Island Model) 7
2.3. 發展情況 9
2.4. 建構演化效能模式 13
3. 研究方法 15
3.1. 研究流程 15
3.2. 實驗環境 16
3.3. 實驗參數設定 17
4. 實驗對象 18
4.1. 最大值求解(Max Ones Problem) 18
4.2. 生產排程最佳化(Job Shop Problem) 19
4.3. 旅行銷售員(Traveling Salesman Problem) 19
4.4. 具時窗限制之車輛途程含回程取貨 (Vehicle Routing Problem with Backhaul and Time Windows Constraint) 20
5. 實驗結果 22
5.1. 群體規模對求解品質與運算成本的影響 22
5.2. 遷移率對求解品質與運算成本的影響 25
5.3. 開始遷移代數對求解品質的影響 27
5.4. 遷移間隔對求解品質的影響 32
5.5. 遷移次數對求解品質的影響 36
5.6. 最佳的開始遷移代數與遷移間隔實驗結果 41
5.7. 採用資料探勘建構效能模式 46
5.8. C&R Tree資料探勘結果 47
5.9. Linear Regression資料探勘結果 52
5.10. Neural Network資料探勘結果 53
6. 實驗結果驗證 53
7. 結論與未來展望 57
參考文獻 59

中文文獻
[1]王照晴, "印刷電路板產品組合最適化決策之研究," 元智大學, 碩士論文, 民國九十二年。
[2]李捷隆, "分散式基因演算法應用於旅行家銷售員問題," 中原大學, 碩士論文, 民國九十三年。

英文文獻
[1]Arenas, M. G., Dolin, B., Merelo , J. J., PACastillo, Fdez de Viana, I., Schoenauer M, "JEO:Java Evolving Objects," Genetic and Evolutionary Computation Conference, pp. 991-994, 2002.
[2]Brudaru, O., Buzatu, O., "Distributed Genetic Algorithm for Finding Fuzzy Rational Approximators," Parallel Computing in Electrical Engineering, pp. 394-397, 2004.
[3]Cantú-Paz, E., "Migration Policies and Takeover Times in Parallel Genetic Algorithms," Genetic and Evolutionary Computation Conference, pp. 775, 1999.
[4]Chen, M. S., Han, J., Yu, P. S., "Data Mining: An Overview from a Database Perspective," IEEE Transactions on Knowledge and Data Engineering, Vol. 8, No. 6, pp. 866-883, 1996.
[5]Cohoon, J. P., Hegde, S. U., Martin, W. N., Richards, D. S., "Distributed Genetic Algorithms for the Floorplan Design Problem," Computer-Aided Design of Integrated Circuits and Systems, Vol. 10, No. 4, pp. 483-492, 1991.
[6]David, B., David, R. B., Ralph, R. M., "An Overview of Genetic Algorithms, Part1, Fundamentals," University Computing, Vol. 15, No. 2, pp. 58-69, 1993.
[7]David, B., David, R. B., Ralph, R. M., "An Overview of Genetic Algorithms, Part2, Research Topics," University Computing, Vol. 15, No. 4, pp. 170-181, 1993.
[8]Fayyad, U. M., Uthurusamy, R., "Data Mining and Knowledge Discovery in Database," Communications of the ACM, Vol. 39, No. 11, pp. 24-27, 1996.
[9]Gen, M., Cheng, R., Genetic Algorithms and Engineering Design, New York: John Wiley and Sons, 1997.
[10]Hiroyasu, T., Miki, M., Negami, M., "Distributed Genetic Algorithms with Randomized Migration Rate," IEEE Proceedings of Systems, Man and Cybernetics Conference SMC '99, Vol. 1, pp. 689-694, 1999.
[11]Inmon, W. H., "The Data Warehouse and Data Mining," Communications of the ACM, Vol. 39, No. 11, pp. 49-50, November 1996.
[12]Johan, B., Maolin, T. "Dynamic Optimization of Migration Topology in Internet-Based Distributed Genetic Algorithms," Genetic And Evolutionary Computation Conference, pp. 1579-1580, 2005.
[13]Jinwoo, K., Zeigler, B. P., "Hierarchical Distributed Genetic Algorithms: A Fuzzy Logic Controller Design Application," IEEE Expert, Vol. 11, No. 3, pp. 76-84, 1996.
[14]Karabudak, D., Hung, C. C., Bing, B., "An Intelligent Admission Control Scheme for Next Generation Wireless Systems Using Distributed Genetic Algorithms," IEEE Wireless Communications and Networking Conference, Vol. 5, No. 1, pp. 1742-1747, 2004.
[15]Knight, L. R., Wainwright, R. L., "HYPERGEN - A Distributed Genetic Algorithm on a Hypercube," IEEE Scalable High Performance Computing Conference, pp. 232-235, 1992.
[16]Kojima, K., Matsuo, H., Ishigame, M., "Asynchronous Parallel Distributed GA using Elite Server," Congress on Evolutionary Computation, Vol. 4, pp. 2603-2610, 2003.
[17]Matsumura, T., Nakamura, M., Miyazato, D., Onaga, K., Okech, J., "Effects of Chromosome migration on a Parallel and Distributed Genetic Algorithm," International Symposium on Parallel Architectures, Algorithms and Networks, pp. 357-361, 1997.
[18]Matsumura, T., Nakamura, M., Okech, J., Onaga, K., "A Parallel and Distributed Genetic Algorithm on Loosely-coupled Multiprocessor Systems," IEICE Trans, Vol. E81-A, No. 4, pp. 540-546, 1998.
[19]Nakamura, M., Yamashiro, N., Gong, Y., "Iterative Parallel and Distributed Genetic Algorithms with Biased Initial Population," Congress on Evolutionary Computation, Vol. 2, pp. 2296-2301, 2004.
[20]Pierreval, H., Paris, J. L., "Distributed Evolutionary Algorithms for Simulation Optimization," IEEE Transactions on Systems, Man and Cybernetics, Part A, Vol. 30, No.1, pp. 15-24, 2000.
[21]Scott, A., "An Introduction to Genetic Algorithms," AI Expert, Vol. 4, No. 3, pp. 49-53, 1990.
[22]Sean, L., Liviu, P., Gabriel, B., Zbigniew, S., Jeff, B., Robert, H., Alexander, C., "A Java-base Evolutionary Computation and Genetic Programming Research System", Available from http://cs.gmu.edu/~eclab/projects/ecj/.
[23]Tanese, R., "Distributed genetic algorithms," 3rd International Conference on Genetic Algorithms, pp. 434-439, 1989.
[24]Tan, K. C., Tay, A., Cai, J., "Design and Implementation of a Distributed Evolutionary Computing Software," IEEE Transactions on Systems, Man and Cybernetics: Part C (Applications and Reviews), Vol. 33, No. 3, pp. 325-338, 2003.
[25]Thangiah, S. R., Potvin J. Y., Sun, T., "Heuristic Approaches to Vehicle Routing with Backhauls and Time Windows," International Journal of Computers and Operations Research, Vol. 23, No. 11, pp. 1043-1057, 1996.
[26]Thuraisingham, B., "A Primer for Understanding and Applying Data Mining," IT Professional, Vol. 2, No.1, pp. 28-31, 2000.
[27]Whitley, W., D., Rana, S., B., Heckendorn, R. B., "Island Model Genetic Algorithms and Linearly Separable Problems," AISB Workshop on Evolutionary Computation, Vol. 1, pp. 109-125, 1997.
[28]Xiong, S. Li, C., "A Distributed Genetic Algorithm to TSP," 4th World Congress on Intelligent Control and Automation, Vol. 3, pp. 1827-1830, 2002.
[29]Yi, W., Liu, Q. He, Y., "Dynamic Distributed Genetic Algorithms," Evolutionary Computation, Vol. 2, pp. 1132-1136, 2000.