生活中我們常需面對最佳化問題，如最小化時間與成本，最大化空間與利益等等。當最佳化的目標不只一個，而且又互相衝突時，如何在目標之間取捨並求出符合使用者期望的解決方案，是一個應用層面廣泛而且頗具挑戰性的主題。近十年來在演化式計算 (evolutionary computation) 領域中，多目標演化最佳化 (evolutionary multi-objective optimization, EMO) 已經逐漸形成一個主流議題。
演化式演算法一方面代表著對於計算資源的大量需求，另一方面也存在一定程度的並行性。由於存在這樣的需求與機會，各類型的帄行演化式演算法因應而生，帄行演化式演算法的執行需要帄行計算環境的支援，過去常見的帄行計算環境為叢集電腦或是分散式系統，然而這類環境的建置與維護對於一般使用者而言並不容易，成本也過於昂貴。
NVIDIA公司目前傾力提倡的 CUDA 帄行計算環境，便提供了軟體設計者一種與 C 語言高度相近的語法來撰寫帄行化程式，以有效利用其帄價的繪圖處理器產品。本論文之目的便在於建構一個完整、易用、高彈性的軟體開發框架 (framework)，與多目標演化式演算法、繪圖處理器共同形成一多目標最佳化解決方案。本軟體框架主要的特點為建置方便且成本低廉的帄行計算環境、快速簡單的軟體開發流程、易客製化的軟體開發框架。本論文將以多目標定序流線型工廠排程問題 (multi-objective permutation flow shop scheduling problem) 為應用實例，實驗結果顯示本論文所提出的軟體框架可以有效的加速演算法的執行。

[1] F. Pezzella, G. Morganti and G. Ciaschetti,“A genetic algorithm for the Flexible Job-shop Scheduling Problem,” Computers & Operations Research, vol. 35, pp. 3202 – 3212, March 2007.
[2] K. Deb and S. Tiwari,“Omni-optimizer: A generic evolutionary algorithm for single and multi-objective optimization,” European Journal of Operational Research, vol. 185, pp. 1062 – 1087, October 2006.
[3] Z. Cai, W. Gong and Y. Huang,“A Novel Differential Evolution Algorithm Based on ε -Domination and Orthogonal Design Method for Multiobjective Optimization,” Evolutionary Multi-Criterion Optimization, vol. 4403, pp. 286 – 301, 2007.
[4] Q. Zhang and H. Li,“MOEA/D: A multiobjective evolutionary algorithm based on decomposition,” IEEE Transation on Evolutionary Computation, vol. 11, pp. 712 – 731, December 2007.
[5] K. Deb, A. Pratap, S. Agarwal and T. Meyarivan,“A fast and elitist multiobjective genetic algorithm:NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, pp. 182 – 197, April 2002.
[6] E. Zitzler, M. Laumanns and L. Thiele,“SPEA2-Imprving the strength pareto evolutionary algorithm,” Computer Engineering and Networks Laboratory, Report 103, 2001.
[7] E. Zitzler and S. K¨unzli,“Indicator-based selection in multiobjective search,” In Proceedings of the 8th International Conference on Parallel Problem Solving from Nature, 2004, pp. 832 – 842.
[8] J. David Schaffer,“Multiple objective optimization with vector evaluated genetic algorithms,” In Proceedings of the 1st International Conference on Genetic Algorithms, 1985, pp. 93 – 100.
[9] NVIDIA, 2011, Retrieved from： www.nvidia.com.tw/object/cuda_home_new.html
[10] TIOBE software, 2011, Retrieved from： www.tiobe.com/index.php/content/paperinfo/tpci/
[11] E. Cantú-Paz, A Survey of Parallel Genetic Algorithms. Calculateurs Paralleles, 1998.
[12] M. Biazzini, B. Bánhelyi, A. Montresor and M. Jelasity,“Distributed hyper-heuristics for real parameter optimization,” In Proceedings of Genetic
___________________參考文獻
10 3
and evolutionary computation, 2009, pp. 1339 – 1346.
[13] B. Manderick and P. Spiessens, P.“Fine-grained parallel genetic algorithms.” In Proceedings of the Third International Conference on Genetic algorithms, 1989, pp. 428 – 433.
[14] N. Xiao and M. P. Armstrong,“A specialized island model and its application in multiobjective optimization.” In Proceedings of Genetic and Evolutionary Computation Conference, 2003, pp. 1530 – 1540.
[15] K. Deb, P. Zope and A. Jain,“Distributed computing of pareto-optimal solutions with evolutionary algorithms.” In Proceedings of Evolutionary Multi-Criterion Optimization, 2003, pp.534 – 549.
[16] J. Branke, H. Schmeck, K. Deb, and M. Reddy S,“Parallelizing multiobjective evolutionary algorithms: cone separation.” In Proceedings of Evolutionary Computation, 2004, pp. 1952 – 1957.
[17] M.L. Wang,“Parallel multi-objective evolutionary algorithms on graphics processing units.” In Proceedings of Genetic and Evolutionary Computation Conference, 2009, pp. 2515 – 2522.
[18] W.H. Zhu,“A study of parallel evolution strategy -pattern search on a gpu computing platform.” In Proceedings of Genetic and Evolutionary Computation Conference, 2009, pp.765 – 772.
[19] Y. Sato, N. Hasegawa and M. Sato,“Gpu acceleration for sudoku solution with genetic operations.” In Proceeding of IEEE Congress on Evolutionary Computation. 2011, pp. 296 – 303.
[20] J.-M. Li, H.-S. Tan, X. Li and L.-L. Liu,“A parallel simulated annealing solution for vrptw based on gpu acceleration.” In Proceedings of the Second KES International Symposium IDT, 2010, pp.201–208.
[21] M. Czapinski and S. Barnes,“Tabu search with two approaches to parallel flowshop evaluation on cuda platform.” Journal of Parallel and Distributed Computing, vol. 71, pp.802 – 811, June 2011.
[22] P. Kromer, J. Platos and V. Snasel,“Differential evolution for the linear ordering problem implemented on cuda.” In Proceeding of IEEE Congress on Evolutionary Computation, 2011, pp. 796 – 802.
[23] T. E. Lewis and G. D. Magoulas,“Strategies to minimise the total run time of cyclic graph based genetic programming with gpus.” In Proceedings of Genetic and Evolutionary Computation Conference, 2009, pp. 1379 – 1386.
[24] M. Wahib, A. Munawar, M. Munetomo and K. Akama,“Optimization of parallel genetic algorithms for nVidia gpus.” In Proceeding of IEEE Congress on Evolutionary Computation, 2011, pp.803 – 811.
___________________參考文獻
10 4
[25] M. G. Arenas, P. Collet, A. E. Eiben, M. Jelasity, J. J. Merelo, B. Paechter, M. Preußand and M. Schoenauer,“A framework for distributed evolutionary algorithms.” In Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, 2002, pp. 665 – 675.
[26] S. Luke, L. Panait, G. Balan. S. Paus, Z. Skolicki and E. Popovici, ECJ: A java-based evolutionary Computation Research System, 2011, Retrieved from：cs.gmu.edu/~eclab/projects/ecj/
[27] JDEAL: The java distributed evolutionary algorithms library. Retrieved from：laseeb.isr.ist.utl.pt/sw/jdeal/
[28] C. Gagné, M. Parizeau and M. Dubreuil,“Distributed BEAGLE: an environment for parallel and distributed evolutionary computations.” In: Proceedings of the Annu. Internat. Symp. High Performance Computing Systems and Applications, 2003, pp. 201 – 208.
[29] E. Alba, F. Almeida, M. Blesa1 J. Cabeza, C. Cotta, M. D´ıaz, I. Dorta, J. Gabarr´o, C. Len, J. Luna, L. Moreno, C. Pablos, J. Petit, A. Rojas and F. Xhafa,“MALLBA: A library of skeletons for combinatorial optimisation.” In Proceedings of the Euro-Par, 2002, pp. 927 – 932.
[30] N. Krasnogor and J. Smith,“MAFRA: A java memetic algorithms framework.” In Proceedings of Genetic and Evolutionary Computation Conference, 2000, pp. 125 – 130.
[31] S. Cahon, N. Melab and E. -G Talbi,“ParadisEO: A framework for the reusable design of parallel and distributed metaheuristics.” Journal of Heuristics, vol. 10, pp. 357 – 380, March 2004.
[32] NVIDIA, 2011, Retrieved from：developer.nvidia.com/category/zone/cuda-zone
[33] T.-C. Chiang, H.-C. Cheng and L.-C Fu,“NNMA: An effective memetic algorithm for solving multiobjective permutation flow shop scheduling problems.” Expert Systems with Applications, vol. 38, pp. 5986 – 5999, May 2011.
[34] E. Taillard,“Benchmarks for basic scheduling problems.” European Journal of Operational Research, vol. 64, pp 278–285, January 1993.