目前對於NP-hard問題的解決方式，我們依然是利用找出近似解的演算法來降低其複雜度，雖然速度比起窮舉法要來的快，但是缺點是大部分的狀況下只能找出近似解。而基因演算法是一種隨機全域搜索和優化的方法，而最初的基因演算法有著許多樣的缺點，如過早收斂、容易掉進區域最佳解等問題。而後來出現了平行化基因演算法(PGA)來解決這樣的問題，目前在平行化基因演算法的領域上已經有非常多的研究了，也衍伸出了許多的演算模型。本篇的研究主要是利用GPU有著大量核心數的特性來找出並且優化適合GPU的SIMD架構的演算模型，並且配合平行化模擬退火法讓我們可以在平行化基因演算法上有著更好的效果。 To solve NP-hard problems, we can use algorithms for finding approximate solutions to reduce the complexity of the problems. Although this approach can come up with solutions much faster than brute-force methods, the downside of it is that only approximate solutions are found in most situations. Genetic algorithm is a global search heuristic and optimization method. Initially, genetic algorithms have many shortcomings, such as premature convergence and the tendency to converge towards local optimal solutions; hence many parallel genetic algorithms have been proposed to solve these problems. Currently, there exist many literatures on parallel genetic algorithms. Also, a variety of parallel genetic algorithms have been derived. This study mainly uses the advantages of the GPU, which has a large number of cores, and identifies better algorithms suitable for computation in single instruction, multiple data (SIMD) architecture of the GPU. Furthermore, the parallel simulated annealing algorithm is also adopted to enhance performance of the parallel genetic algorithm.
