本研究主要探討以雲端運算為基礎之平行化基因演算法的運作，並以物料裁切為例，實作兩種平行化基因演算法—Divide and Conquer與Collaboration，藉此觀察基於雲端運算之平行化基因演算法的運算效率。本研究的兩種方法是傳統平行化基因演算法常用的策略，其運算模式為主從式架構，與雲端運算之架構相同上，但由於雲端運算為基礎的平行化基因演算法，受到MapReduce運算之特有模式的影響，電腦間必須透過分散式檔案系統進行溝通而非傳統的MPI(Message Passing Interface)，故實作上必須進行調整。另外，由於本研究的兩種方法都是以小母體(population)來進行演化程序，為避免收斂過早的情形發生，將於實驗前進行參數測試，找出不同叢集下的參數設定，提升求解品質與運算效率。

Genetic algorithm is one of evolution algorithms, and it is commonly used to create useful solutions to optimization and search problems using techniques inspired by evolution process, such as selection, crossover, mutation, and replacement. Because genetic algorithms have drawbacks, e.g., the answer’s quality is not assurance and runtime cannot assure constant, it does something like parallelization. In this research, we have proposed two parallel schemes for the genetic algorithm based on the map-reduce programming model for solving the Cutting Stock Problem. We implement the parallel genetic algorithms on cloud computing system Hadoop in which the application is divided into small chunks of work, each of which may be executed on any worker in the cluster. Upon the map-reduce model, we propose two parallel schemes for running genetic algorithm. One is to proceed the genetic algorithm on all workers individually, then combine their results. The other one is to proceed the genetic algorithm cooperatively, in which each worker helps running part of the evolution. According to our experiments, we conclude that our methods elevate runtime efficient and solution quality.

中文
[1] 徐家賢(2010)，《具時間週期性的連續隨機需求之一維剩餘物料裁切問題之研究》，長榮大學資訊管理研究所碩士論文。
[2] 林豐澤(2005)，《演化式計算下篇：基因演算法以及三種應用實例》，智慧科技與應用統計學報（3卷1期）：29-56。
[3] 黃重憲(2009)，《淺淡雲端運算》，國立台灣大學計算機與資訊網路中心。
[4] 楊文誌(2010)，《雲端運算Cloud Computing 技術指南》，松崗出版社。
[5] 李昇暾、詹智安(2012)，《Android雲端實務程式設計》，碁峰出版社。
[6] 王耀聰、辜文元、魏綸毅譯(2011)，《Hadoop技術手冊，第二版》，歐萊禮出版社。譯自Tom White(2010)，Hadoop：The Definitive Guide, Second Edition 。
[7] 蘇明健(2009)，《應用啟發式演算法求解多目標型鋼切割計劃之研究》，中山大學資訊管理研究所在職專班碩士論文。

英文
[8] Bennell, J. A., & Dowsland, K. A. (1999). “A tabu thresholding implementation for the irregular stock cutting problem.” International Journal of Production Research, 37(18), 4259-4275.
[9] Belov, G., & Scheithauer, G. (2002). “A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths.” European Journal of Operational Research, 141(2), 274-294.
[10] Chu, P. C., & Beasley, J. E. (1998). “A genetic algorithm for the multidimensional knapsack problem.” Journal of heuristics, 4(1), 63-86.
[11] Czarn, A., MacNish, C., Vijayan, K., Turlach, B., & Gupta, R. (2004). “Statistical exploratory analysis of genetic algorithms.” Evolutionary Computation, IEEE Transactions on, 8(4), 405-421.
[12] Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., ... & Gruber, R. E. (2008). “Bigtable: A distributed storage system for structured data.” ACM Transactions on Computer Systems (TOCS), 26(2), 4.
[13] Dyckhoff, H. (1990). “A typology of cutting and packing problems.” European Journal of Operational Research, 44(2), 145-159.
[14] Dean, J., & Ghemawat, S. (2008). “MapReduce: simplified data processing on large clusters.” Communications of the ACM, 51(1), 107-113.
[15] Eiben, A. E., Hinterding, R., & Michalewicz, Z. (1999). “Parameter control in evolutionary algorithms.” Evolutionary Computation, IEEE Transactions on, 3(2), 124-141.
[16] Grefenstette, J. J. (1981). “Parallel Adaptive Algorithms for Function Optimization:(preliminary Report).” Computer Science Department, Vanderbilt University.
[17] Grefenstette, J. J. (1986). “Optimization of control parameters for genetic algorithms.” Systems, Man and Cybernetics, IEEE Transactions on, 16(1), 122-128.
[18] Gau, T., & Wäscher, G. (1995). “CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem.” European Journal of Operational Research, 84(3), 572-579.
[19] Gradišar, M., Resinovič, G., & Kljajić, M. (2002). “Evaluation of algorithms for one-dimensional cutting.” Computers & Operations Research, 29(9), 1207-1220.
[20] Ghemawat, S., Gobioff, H., & Leung, S. T. (2003). “The Google file system.” In ACM SIGOPS Operating Systems Review 37(5), 29-43.
[21] Holland, J. H. (1992). “Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control and artificial intelligence.” MIT press.
[22] Hinterding, R., & Khan, L. (1995). “Genetic algorithms for cutting stock problems: with and without contiguity” Springer Berlin Heidelberg , 166-186.
[23] Mell, P., & Grance, T. (2011). “The NIST definition of Cloud Computing (draft).” NIST special publication, 800, 145.
[24] Nowostawski, M., & Poli, R. (1999). “Parallel genetic algorithm taxonomy.” In Knowledge-Based Intelligent Information Engineering Systems, Third International Conference. IEEE , 88-92.
[25] Schaffer, J. D., Caruana, R. A., Eshelman, L. J., & Das, R. (1989). “A study of control parameters affecting online performance of genetic algorithms for function optimization.” In Proceedings of the third international conference on Genetic algorithms Morgan Kaufmann Publishers Inc., 51-60.
[26] Trkman, P., & Gradisar, M. (2007). “One-dimensional cutting stock optimization in consecutive time periods.” European Journal of Operational Research, 179(2), 291-301.
[27] Wäscher, G., Haußner, H., & Schumann, H. (2007). “An improved typology of cutting and packing problems.” European Journal of Operational Research, 183(3), 1109-1130.
[28] Hadoop , http://hadoop.apache.org/
[29] wiki , http://zh.wikipedia.org