利用異質計算平行化加速相依性結構矩陣遺傳演算法二代

Abstract

相依式結構矩陣遺傳演算法二代在許多指標問題上有著良好的效能，此演算法透過偵測問題結構來建構模型，並透過兩個族群混合運算子來尋求更好的解。建構模型雖是造成其效能良好的原因之一，但這個過程卻十分耗時；此外族群混合運算子在計算混合後的適應分數亦需要不少時間。 本篇論文透過平行化的方式來加速這兩個耗時的運算。在建構模型上的加速使用圖形處理器，首先提出演算法概念上相同的加速版本，而後再提出利用修改演算法降低模型準確度，來獲得更高加速的第二個版本。在混合運算子的平行化上考慮到問題特性，故透過中央處理器進行加速。模型建構的及混合運算子的加速在我們使用的幾個常見的測試問題中，都展現出穩定的加速成果，且可應用於理論最大值將近兩萬四千位元左右之問題上。 模型建構式的基因演算法受限於模型建構的運算過程而難以平行化，此研究透過微幅降低模型的準確度及對演算法本身的修改，結合兩種異質計算的平行化後，顯示出模型建構式的基因演算法還是有利用平行化的方式來達到大幅加速的可能。

DSMGA-II has good performances on many benchmark problems. DSMGA-II builds a model by detecting the problem structure and uses two mixing operators to generate better offsprings. The model building is one of the factors to achieve such performances. However, this process is time-consuming. Two mixing operators also take plenty of time when evaluating the fitness function. This thesis aims to use parallelisms on two heterogeneous computing platforms to speed up the model building process and the two mixing operators. I use GPU to parallelize the model building process and CPU to parallelize two mixing operators. I propose two speedup schemes for model building. The first scheme is algorithmically identical to the original DSMGA-II, and the second scheme sacrifices some model accuracy for further speedup. As for speeding up mixing operators, I use CPU instead of GPU to perform parallelization due to the core ability and also use it to parallelize the mixing operators with lossy implementations. On several commonly used benchmark problems, the speedup on CPU and GPU are stable, and the largest theoretical applicable proble size is up to about 24 thousand bits. MBGA is hard to be parallelized due to the model building process. However, this thesis shows a possibility to gain huge speedup by combining two heterogeneous parallelisms and lossy designs.