基於島模型以及退火法之GPU平行化基因演算法

Tunghai University Institutional Repository > 工學院 > 資訊工程學系所 > 碩士論文 > Item 310901/29181

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://140.128.103.80:8080/handle/310901/29181

题名:	基於島模型以及退火法之GPU平行化基因演算法
其它题名:	Parallel Genetic Algorithms on the GPU Using Island Model and Simulated Annealing
作者:	李正傑 LI,CHENG-CHIEH
贡献者:	林祝興 LIN,CHU-HSING 資訊工程學系
关键词:	基因演算法;模擬退火法;島模型;平行運算 Parallel computing;Genetic algorithm;TSP;GPU computing;Island model;Simulated annealing
日期:	2016
上传时间:	2017-07-17T04:10:27Z (UTC)
摘要:	目前對於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.
显示于类别:	[資訊工程學系所] 碩士論文

文件中的档案:

档案	描述	大小	格式	浏览次数
104THU00394012-001.pdf		6606Kb	Adobe PDF	644	检视/开启

在THUIR中所有的数据项都受到原著作权保护.

数据加载中.....