基於基模理論之平行DNA演算法

Parallel DNA Computing Algorithm Based on Schema Theory

潘致瑋(Chih-Wei Pan)

指導教授 ： 黃國勝 ； 陳昱仁

國立中正大學/工學院/電機工程學系/碩士(2013年)

摘要

DNA Computing為使用DNA、生物化學以及分子生物學等原理，所發展的一種運算形式。相較於傳統電腦，DNA Computer具有運算速度較快、所佔體積較小等優點。於本論文中，我們啟發於DNA Computing並配合計算機特性設計出一套演算法，DNA平行演算法，目標解決工程最佳化問題。

為了提升運算效能，我們融合進化演算法概念及基因演算法之基模理論，加強本演算法在搜尋空間中探索的準確性及速度。

在模擬實驗中，為了實現平行運算架構，我們採用GPGPU (General Purpose Computing on Graphics Processing Units)概念，將演算法實作在NVIDIA所提供之平行運算模型及平台CUDA (Compute Unified Device Architecture)上。

關鍵字

進化演算法 ； 基模理論 ； 平行運算 ； DNA 計算 ； CUDA

並列摘要

DNA computing is a form of computation, which uses DNA, biochemistry and molecular biology. By comparing to traditional computers, DNA computers have the advantage of less computing time and volume.

In this thesis, we developed a novel algorithm, Parallel DNA Computing Algorithm, which was inspired by DNA Computing for solving optimization problems in engineering. And we also matched our algorithm to characteristics of digital computers.

For improving the computing performance, we integrated the concept of evolutionary algorithms and the schema theory of genetic algorithm to enhance the accuracy and convergence rate of exploration in the search space.

To realize the architecture of parallel computing, the concept of GPGPU (General Purpose Computing on Graphics Processing Units) was used for simulation. And we implemented the algorithm on CUDA (Compute Unified Device Architecture), which is a parallel computing platform and programming model created by NVIDIA.

並列關鍵字

schema theory ； parallel computing ； DNA Computing ； Evolutionary algorithms ； CUDA

參考文獻

[1] Adleman, L. M.. “Molecular computation of solutions to combinatorial problems.” SCIENCE-NEW YORK THEN WASHINGTON, p.p.1021, 1994

[2] Watada, J. “DNA computing and its application.” In Computational Intelligence: A Compendium, Springer Berlin Heidelberg. pp. 1065-1089,2008.

[5] Ding, Y., & Ren, L. “DNA genetic algorithm for design of the generalized membership-type Takagi-Sugeno fuzzy control system.” Systems, Man, and Cybernetics, IEEE International Conference Vol. 5, pp. 3862-3867, 2000.

[6] Tropp, B. E. Molecular biology: genes to proteins. Jones & Bartlett Publishers, 2012.

[7] Holland, J. H. Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press, 1975.