焊接机器人路径规划问题的算法研究
|
摘要
本文讨论了目前在焊接机器人路径规划领域广泛使用的智能算法:遗传算法和Hopfield神经网络。针对这些算法处理路径优化问题时的不足,提出了基于DNA计算处理焊接机器人路径规划问题的算法。基于焊接机器人路径规划问题的数学模型,将焊接机器人路径规划问题转化为完全正权无向图的最短Hamilton环路问题;结合焊接机器人工作的实际情况,运用DNA算法获得最短Hamilton环路路程,从而实现焊接机器人的工具原点运动的最优化;最后通过算例证明了方法的有效性。针对已有的DNA计算模型的缺点,采取了相应的改进,把包含重复顶点的闭链剔除出去,满足了实际规划问题中不重复焊接同一焊点的要求。
本文还讨论了DNA计算实现实际工作中焊接机器人路径规划时出现的几个问题,并提出了作者的一些想法,为以后研究这些问题指出了努力的方向。
Discussion of the current field of welding path widespread use of Intelligent algorithms: genetic algorithms and Hopfield neural networks. These algorithms address the lack of path optimization problems is proposed welding robot path planning algorithms based on DNA computing.Based on the mathematical model, the welding robot path planning problem is transformed into the shortest completely weighted undirected graph of Hamilton loop problem; combination of the actual situation of the robot, the use of DNA method was the shortest Hamilton Circle distance to the origin of welding robot movement optimization tool; Finally, a numerical example demonstrates the effectiveness of the method. DNA computing model for the existing shortcomings, take a corresponding improvement, to include removing duplicate vertices of closed-chain out to meet the actual planning problems do not repeat the same solder welding requirements.
This article also discusses the practical work of DNA Computing for welding robot path planning, several issues emerged and made of some of the ideas for the future study of these issues that direction.
本文还讨论了DNA计算实现实际工作中焊接机器人路径规划时出现的几个问题,并提出了作者的一些想法,为以后研究这些问题指出了努力的方向。
Discussion of the current field of welding path widespread use of Intelligent algorithms: genetic algorithms and Hopfield neural networks. These algorithms address the lack of path optimization problems is proposed welding robot path planning algorithms based on DNA computing.Based on the mathematical model, the welding robot path planning problem is transformed into the shortest completely weighted undirected graph of Hamilton loop problem; combination of the actual situation of the robot, the use of DNA method was the shortest Hamilton Circle distance to the origin of welding robot movement optimization tool; Finally, a numerical example demonstrates the effectiveness of the method. DNA computing model for the existing shortcomings, take a corresponding improvement, to include removing duplicate vertices of closed-chain out to meet the actual planning problems do not repeat the same solder welding requirements.
This article also discusses the practical work of DNA Computing for welding robot path planning, several issues emerged and made of some of the ideas for the future study of these issues that direction.
引文
[1]周康,强小利,同小军等.求解TSP算法[J].计算机工程与应用,2007,43(29).
[2]周康,刘文斌,许进.TSP的DNA计算算法[J].系统工程与电子技术,2007,29(2).
[3] Barricelli, Nils Aall. Esempi numerici di processi di evoluzione[J]. Methodos, 1954: 45–68.
[4] Holland, John H. Adaptation in Natural and Artificial Systerms[D],Ann Arbor :University of Michigan Press,1975.
[5]杨辉,康立山,陈毓屏.一种基于构建基因库求解TSP问题的遗传算法[J].计算机学报, 2003, 26 (12) : 175321758.
[6]王磊,潘进,焦李成.免疫算法[J ].电子学报, 2000, 28(7) : 74278.
[7] DeJong K A. An Analysis of the Behaviour of a Class of Genetic Adaptive Systems [D]. M ichigan: University of Michigan,Ann Arbor, 1975.
[8] Goldberg D E, Richardson J. Genetic A lgorithm with Sharing for Multimodal Function Optimization [A ].Proc of the Int Confon Genetic Algorithms [C].Lawrence Erlbaum , 1987: 41249.
[9] Baraglia R, Hidalgo J I, Perego R. A Hybrid Heuristic for the Traveling Saleman Problem [J ]. IE E E Trans on Evolutionary Computation, 2001, 5 (6) : 6132622.
[10]杨虎.利用遗传算法求解最小变形的焊接路径[J].机械设计与研究,2004,20(2)
[11] Hopfield J J. Neural Networks and Physical Systems with Emergent Collective Computational Abilities [J].Proc of the National Academy of Science, 1982, 79 (4) :255422558.
[12]王凌,郑大钟. TSP及其基于Hopfield网络优化的研究[J].控制与决策.1999, 14 (6): 6702674.
[13] Wang S, Tsai C M. Hopfield Nets w ith Time-varying Energy Function for Solving the Traveling Salesman Problem [A]. Int J Confon Neural Networks [C].Seattle, Washington, 1991: 8072812.
[14] Xu X, T sai W T. Effective Neural Algorithms for theTraveling Salesman Problem [J]. Neural Network,1991, 4 (1) : 1932205.
[15] Aiyer S V B,Niranjan M , Fallside F. A Theoretical Investigation into the Performance of the Hopfield Model[J]. IEEE Transon Neural Networks, 1990, 1 (2): 2042215.
[16] Ackley D H, Hinton G E, Sejnowski T J. A LearningAlgorithm for Boltzmann Machines [J]. Cognitive Science, 1985, 9 (1): 1472169.
[17] Tang Z, Jin H H,Murao K, et al. A Gradient A scent Learning for Hopfield Networks [J]. Trans of IEICE of Japan, 2000, J 832A (3): 3192331.
[18]金海和,陈剑,唐政等.基于Hopfield网络的极小值问题学习算法[J].清华大学学报, 2002, 42 (6) : 7312734.
[19] Adleman L. Molecular Computation of Solutions to Combinatorial Problems[J].Science,1994, 266(5187): 1021~1023.
[20] Dan Boneh, Christopher Dunworth, Richard J. Lipton, and Jiri Sgall. On the Computational Power of DNA[J]. DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science 71.1996.
[21] Lila Kari, Greg Gloor, Sheng Yu. Using DNA to solve the Bounded Post Correspondence Problem[J]. Theoretical Computer Science, 2000,231 (2): 192–203.
[22] Yaakov Benenson1, Binyamin Gil, Uri Ben-Dor, Rivka Adar, Ehud Shapiro. An autonomous molecular computer for logical control of gene expression[J]. Nature, 2004,429: 423–429.
[23] David I. Lewin. DNA Computing[J]. Computing in Science & Engineering,2002,4 (3): 5–8.
[24] C. H. Bennett. Logical Reversal of Computation[J]. IBM Journal of Research and Development , 1973,17 (6): 525–532.
[25] Kahan M, Gil B,Adar R, Shapiro E .Towards Molecular Computers that Operate in a Biological Environment[J]. Physica D: Nonlinear Phenomena ,2008,237 (9): 1165–1172.
[26] Benenson, Yaakov; Paz-Elizur, Tamar; Adar, Rivka; Keinan, Ehud; Livneh, Zvi; Shapiro, Ehud. Programmable and Autonomous Computing Machine Made of Biomolecules[J]. Nature, 2001, 414 (6862): 430–434.
[27] Nayebi, A. Parallel DNA implementation of fast matrix multiplication techniques based on an n-moduli set[J]. arXiv,2009, 0912.0750: 1–15.
[28] Saiki, RK; Scharf S, Faloona F, Mullis KB, Horn GT, Erlich HA, Arnheim N. Enzymatic amplification of beta-globin genomic sequences and restriction site analysis for diagnosis of sickle cell anemia[J]. Science, 985,230 (4732): 1350–4.
[29] Saiki, RK; Gelfand DH, Stoffel S, Scharf SJ, Higuchi R, Horn GT, Mullis KB, Erlich HA. Primer-directed enzymatic amplification of DNA with a thermostable DNA polymerase[J]. Science, 1988, 239: 487–91.
[30] Rychlik W, Spencer WJ, Rhoads RE. Optimization of the annealing temperature for DNA amplification in vitro[J]. Nucl Acids Res,1990, 18: 6409–6412.
[31] Chien A, Edgar DB, Trela JM. Deoxyribonucleic acid polymerase from the extreme thermophile Thermus aquaticus[J]. J. Bacteriol,1976, 174: 1550–1557.
[32] Lawyer FC, Stoffel S, Saiki RK, Chang SY, Landre PA, Abramson RD, Gelfand DH. High-level expression, purification, and enzymatic characterization of full-length Thermus aquaticus DNA polymerase and a truncated form deficient in 5' to 3' exonuclease activity[J]. PCR Methods Appl,1993, 2: 275–287.
[33] Berg JM, Tymoczko JL Stryer L. Biochemistry (5th ed.)[M]. WH Freeman. ISBN 0-7167-4955-6.
[34] Robyt, John F.; White, Bernard J. Biochemical Techniques Theory and Practice[M]. Illinois: Waveland Press. ISBN 0-88133-556-8.
[35] Mukherjee D, et al. Analysis of RNA Exonucleolytic Activities in Cellular Extracts[J]. Springer protocols,2002, 257: 193–211.
[36] Pamela A. Frischmeyer, et al. (2002). An mRNA Surveillance Mechanism That Eliminates Transcripts Lacking Termination Codons.". Science 295 (5563): 2258–61.
[37] Rose J A,Hagiya M,Deaton R J,et a1.A DNA—based in vitro genetic program[J].J Biol Phys,2002,28(3):493-498.
[38]周康,同小军,许进.最优指派问题DNA算法[J].系统工程与电子技术,2007,29(7):1183—1187.
[39] Zhou K,Tong X J,Xu J.The improvement on algorithm of DNA computing on 0-1 planning problem[C]//Prnceedings of the FifnlInternational Conference on Machine Learning and Cybernetics,Dalian,13-16 August 2006:4282—4286.
[40]周康,王子成,许迸.最大流问题的DNA计算两阶段法[J].华中科技大学学报:自然科学版,2005,33(8):104—107.
[41] Brmch R S,Chclyapov N,Johnson C,et a1.Solution of a 20-vailable 3-SAT problem on a DNA Computer[J].Science,2002,296(5567):499—502.
[42]周康,覃磊,高婧,等.DNA计算在电路设计中的应用[J].华中科技大学学报:自然科学版,2008,36(8):107一l 10.
[43]周康.同小军,许进.路序问题基于表面的DNA算法[J].华中科技大学学报:自然科学版,005,33(8):100—103.
[44]周康,同小军,许进.基于DNA计算的指派问题[J].华中科技大学学报:自然科学版,2008,36(2):35—38.
[45] Sakamoto K,Gouzu H,Komiya K,et a1.Molecular computation by DNA hairpin formation[J].Science,2000.288(5469):1223一1226.
[46]周康,同小军,刘文斌,等.最短路问题的闭环DNA算法[J].系统工程与电子技术,2008,30(3):556—560.
[47]周康.同小军,刘文斌.排课表问题的闭环DNA计算模型的算法[J].计算机应用,2007,27(4):991—993.
[48]周康,许进.最小顶点覆盖问题的闭环DNA算法[J].计算机工程与应用,2006,42(20):7—9.
[49] Wang L,1.iu Q,Frntos A G,et a1.Surface—based DNA computing operations:DESTROY and READOUTL[J].Biosystems,1999,52(1/3):189—191.
[50]周康.同小军,刘文斌,等.基于闭环DNA的最大独立集问题的算法[J].计算机工程,2008,34(4):40—44.
[51]周康,殷燕芳,李玉华,等.最大权匹配问题的闭环DNA算法[J].华中科技大学学报:自然科学版,2007,35(8):63—66.
[52] Darehmiraki M,Nehi H M.A aurfaee—based DNA algorithm for the solving binaryknapsack problem[J].Applied Mathematics and Computation,2007,188(2):1991—1994.
[53] Cai W,Condon A,Corn R M,et a1.The power of surface—based computation[C]//Proc Fimt International Conference OH Computa-tional Molecular Biology.January 1997.
[54] Yin Z X,Zhang F Y,Xu J.A general 0-1 programming problembased on DNA computing[J].Biosystem,2003,70(1):73-79.
[55]许进,董亚非,魏小鹏,等.粘贴DNA计算机模型(I):理论[J].科学通报,2004,49(31):205—212.
[56]许进,李三平,董亚非,等.粘贴DNA计算机模型(II):应用[J].科学通报,2004,49(4):299—307.
[57]许进,董亚非.粘贴DNA计算模型理论及应用[J].科学通报,2003.49(3):205—212.
[58]周康.同小军.许进.基于闭环DNA模型的八皇后问题算法[J].计算机工程与应用,2007,43(6):4—6.
[59] Kari L,Paun G,Rozenberg G,et al,DNA computing ,sticker systerns,and universality[J].Acta lnformatica.1998,35(5):40142.
[60] Freund R,Kari L,Paun G.DNA computing based on splicing:The existence of universal computers[J].Theory of Computing System,1999,32(1):69—1 12.
[61] Paun G.On the splicing oporation[J].Discrete Applied Mathematics,1996,70(1):57—79.
[62] Dassow J.Mitrana V.Splicing grammar systems[J].Computers and Artificial Intelligence,1996,15(2,3):109—122.
[63] Benenson Y,Paz-Elizur T,Adar R,et a1.Programmable and autonomous computing machine made of biomoleoules[J].Nature,200l,414(22):430—434.
[64]周康,王延峰,刘文斌,等.基于闭环DNA的边着色问题DNA算法[J].华中科技大学学报:自然科学版,2006,34(9):25—28.
[65] Chiu D T,Pezzoli E,Wu H,et a1.Using three-dimensional microfluidic networks for solving computationally hard problems[J].Applied Physical Seieuees,2001,98(6):296l一2966.
[66] Seemam N C,Wang H,Liu B,et a1.The perils of polynuleotides:The experimental gap belween the design and assembly of unusual DNA structures[C]//DIMACS Series in Discrete Mathematicsand Theoretical Computer Science,1999,44:215—233.
[67] Ma R I,Kallenbach N R,Sheardy R D,et a1.Three—arm nucleicacid junctions are flexible[J].Nucleic Acids Res,1996,14(24):9745_-9753.
[68] Jonoska N , Stephen A K , Mamahico S . Three dimensional DNA structures in computing[J].BioSystems,1999,52(1):143—153.
[69]罗生斌.白车身焊接机器人焊接路径规划及其仿真[D].上海:同济大学,2006.
[70]刘海江,罗生斌.白车身侧围工位焊接机器人路径优化研究[J].制造业自动化,2005,27(7):35-38.
[71]杨虎.利用遗传算法求解最小变形的焊接路径[J].机械设计与研究,2004,20(2).
[72] Bondy J A , Murty U S R. Graph theory with applications[M] .London : The Macmillan Press LTD ,1976.
[73]钱颂迪,田丰,胡运权,等.运筹学(修订版) [M] .北京:清华大学出版社,1990.
[74]周康,同小军,许进.路径排序问题基于表面的DNA算法[J].华中科技大学学报(自然科学版),2005,33(8).
[75] Lipton R J . DNA solution of hard computational problem[J ] . Science , 1995 , 268 (28) , 5422545.
[76]刘文斌.赋权Hamilton路的DNA计算模型[J].系统工程与电子技术,2002,24(6).
[2]周康,刘文斌,许进.TSP的DNA计算算法[J].系统工程与电子技术,2007,29(2).
[3] Barricelli, Nils Aall. Esempi numerici di processi di evoluzione[J]. Methodos, 1954: 45–68.
[4] Holland, John H. Adaptation in Natural and Artificial Systerms[D],Ann Arbor :University of Michigan Press,1975.
[5]杨辉,康立山,陈毓屏.一种基于构建基因库求解TSP问题的遗传算法[J].计算机学报, 2003, 26 (12) : 175321758.
[6]王磊,潘进,焦李成.免疫算法[J ].电子学报, 2000, 28(7) : 74278.
[7] DeJong K A. An Analysis of the Behaviour of a Class of Genetic Adaptive Systems [D]. M ichigan: University of Michigan,Ann Arbor, 1975.
[8] Goldberg D E, Richardson J. Genetic A lgorithm with Sharing for Multimodal Function Optimization [A ].Proc of the Int Confon Genetic Algorithms [C].Lawrence Erlbaum , 1987: 41249.
[9] Baraglia R, Hidalgo J I, Perego R. A Hybrid Heuristic for the Traveling Saleman Problem [J ]. IE E E Trans on Evolutionary Computation, 2001, 5 (6) : 6132622.
[10]杨虎.利用遗传算法求解最小变形的焊接路径[J].机械设计与研究,2004,20(2)
[11] Hopfield J J. Neural Networks and Physical Systems with Emergent Collective Computational Abilities [J].Proc of the National Academy of Science, 1982, 79 (4) :255422558.
[12]王凌,郑大钟. TSP及其基于Hopfield网络优化的研究[J].控制与决策.1999, 14 (6): 6702674.
[13] Wang S, Tsai C M. Hopfield Nets w ith Time-varying Energy Function for Solving the Traveling Salesman Problem [A]. Int J Confon Neural Networks [C].Seattle, Washington, 1991: 8072812.
[14] Xu X, T sai W T. Effective Neural Algorithms for theTraveling Salesman Problem [J]. Neural Network,1991, 4 (1) : 1932205.
[15] Aiyer S V B,Niranjan M , Fallside F. A Theoretical Investigation into the Performance of the Hopfield Model[J]. IEEE Transon Neural Networks, 1990, 1 (2): 2042215.
[16] Ackley D H, Hinton G E, Sejnowski T J. A LearningAlgorithm for Boltzmann Machines [J]. Cognitive Science, 1985, 9 (1): 1472169.
[17] Tang Z, Jin H H,Murao K, et al. A Gradient A scent Learning for Hopfield Networks [J]. Trans of IEICE of Japan, 2000, J 832A (3): 3192331.
[18]金海和,陈剑,唐政等.基于Hopfield网络的极小值问题学习算法[J].清华大学学报, 2002, 42 (6) : 7312734.
[19] Adleman L. Molecular Computation of Solutions to Combinatorial Problems[J].Science,1994, 266(5187): 1021~1023.
[20] Dan Boneh, Christopher Dunworth, Richard J. Lipton, and Jiri Sgall. On the Computational Power of DNA[J]. DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science 71.1996.
[21] Lila Kari, Greg Gloor, Sheng Yu. Using DNA to solve the Bounded Post Correspondence Problem[J]. Theoretical Computer Science, 2000,231 (2): 192–203.
[22] Yaakov Benenson1, Binyamin Gil, Uri Ben-Dor, Rivka Adar, Ehud Shapiro. An autonomous molecular computer for logical control of gene expression[J]. Nature, 2004,429: 423–429.
[23] David I. Lewin. DNA Computing[J]. Computing in Science & Engineering,2002,4 (3): 5–8.
[24] C. H. Bennett. Logical Reversal of Computation[J]. IBM Journal of Research and Development , 1973,17 (6): 525–532.
[25] Kahan M, Gil B,Adar R, Shapiro E .Towards Molecular Computers that Operate in a Biological Environment[J]. Physica D: Nonlinear Phenomena ,2008,237 (9): 1165–1172.
[26] Benenson, Yaakov; Paz-Elizur, Tamar; Adar, Rivka; Keinan, Ehud; Livneh, Zvi; Shapiro, Ehud. Programmable and Autonomous Computing Machine Made of Biomolecules[J]. Nature, 2001, 414 (6862): 430–434.
[27] Nayebi, A. Parallel DNA implementation of fast matrix multiplication techniques based on an n-moduli set[J]. arXiv,2009, 0912.0750: 1–15.
[28] Saiki, RK; Scharf S, Faloona F, Mullis KB, Horn GT, Erlich HA, Arnheim N. Enzymatic amplification of beta-globin genomic sequences and restriction site analysis for diagnosis of sickle cell anemia[J]. Science, 985,230 (4732): 1350–4.
[29] Saiki, RK; Gelfand DH, Stoffel S, Scharf SJ, Higuchi R, Horn GT, Mullis KB, Erlich HA. Primer-directed enzymatic amplification of DNA with a thermostable DNA polymerase[J]. Science, 1988, 239: 487–91.
[30] Rychlik W, Spencer WJ, Rhoads RE. Optimization of the annealing temperature for DNA amplification in vitro[J]. Nucl Acids Res,1990, 18: 6409–6412.
[31] Chien A, Edgar DB, Trela JM. Deoxyribonucleic acid polymerase from the extreme thermophile Thermus aquaticus[J]. J. Bacteriol,1976, 174: 1550–1557.
[32] Lawyer FC, Stoffel S, Saiki RK, Chang SY, Landre PA, Abramson RD, Gelfand DH. High-level expression, purification, and enzymatic characterization of full-length Thermus aquaticus DNA polymerase and a truncated form deficient in 5' to 3' exonuclease activity[J]. PCR Methods Appl,1993, 2: 275–287.
[33] Berg JM, Tymoczko JL Stryer L. Biochemistry (5th ed.)[M]. WH Freeman. ISBN 0-7167-4955-6.
[34] Robyt, John F.; White, Bernard J. Biochemical Techniques Theory and Practice[M]. Illinois: Waveland Press. ISBN 0-88133-556-8.
[35] Mukherjee D, et al. Analysis of RNA Exonucleolytic Activities in Cellular Extracts[J]. Springer protocols,2002, 257: 193–211.
[36] Pamela A. Frischmeyer, et al. (2002). An mRNA Surveillance Mechanism That Eliminates Transcripts Lacking Termination Codons.". Science 295 (5563): 2258–61.
[37] Rose J A,Hagiya M,Deaton R J,et a1.A DNA—based in vitro genetic program[J].J Biol Phys,2002,28(3):493-498.
[38]周康,同小军,许进.最优指派问题DNA算法[J].系统工程与电子技术,2007,29(7):1183—1187.
[39] Zhou K,Tong X J,Xu J.The improvement on algorithm of DNA computing on 0-1 planning problem[C]//Prnceedings of the FifnlInternational Conference on Machine Learning and Cybernetics,Dalian,13-16 August 2006:4282—4286.
[40]周康,王子成,许迸.最大流问题的DNA计算两阶段法[J].华中科技大学学报:自然科学版,2005,33(8):104—107.
[41] Brmch R S,Chclyapov N,Johnson C,et a1.Solution of a 20-vailable 3-SAT problem on a DNA Computer[J].Science,2002,296(5567):499—502.
[42]周康,覃磊,高婧,等.DNA计算在电路设计中的应用[J].华中科技大学学报:自然科学版,2008,36(8):107一l 10.
[43]周康.同小军,许进.路序问题基于表面的DNA算法[J].华中科技大学学报:自然科学版,005,33(8):100—103.
[44]周康,同小军,许进.基于DNA计算的指派问题[J].华中科技大学学报:自然科学版,2008,36(2):35—38.
[45] Sakamoto K,Gouzu H,Komiya K,et a1.Molecular computation by DNA hairpin formation[J].Science,2000.288(5469):1223一1226.
[46]周康,同小军,刘文斌,等.最短路问题的闭环DNA算法[J].系统工程与电子技术,2008,30(3):556—560.
[47]周康.同小军,刘文斌.排课表问题的闭环DNA计算模型的算法[J].计算机应用,2007,27(4):991—993.
[48]周康,许进.最小顶点覆盖问题的闭环DNA算法[J].计算机工程与应用,2006,42(20):7—9.
[49] Wang L,1.iu Q,Frntos A G,et a1.Surface—based DNA computing operations:DESTROY and READOUTL[J].Biosystems,1999,52(1/3):189—191.
[50]周康.同小军,刘文斌,等.基于闭环DNA的最大独立集问题的算法[J].计算机工程,2008,34(4):40—44.
[51]周康,殷燕芳,李玉华,等.最大权匹配问题的闭环DNA算法[J].华中科技大学学报:自然科学版,2007,35(8):63—66.
[52] Darehmiraki M,Nehi H M.A aurfaee—based DNA algorithm for the solving binaryknapsack problem[J].Applied Mathematics and Computation,2007,188(2):1991—1994.
[53] Cai W,Condon A,Corn R M,et a1.The power of surface—based computation[C]//Proc Fimt International Conference OH Computa-tional Molecular Biology.January 1997.
[54] Yin Z X,Zhang F Y,Xu J.A general 0-1 programming problembased on DNA computing[J].Biosystem,2003,70(1):73-79.
[55]许进,董亚非,魏小鹏,等.粘贴DNA计算机模型(I):理论[J].科学通报,2004,49(31):205—212.
[56]许进,李三平,董亚非,等.粘贴DNA计算机模型(II):应用[J].科学通报,2004,49(4):299—307.
[57]许进,董亚非.粘贴DNA计算模型理论及应用[J].科学通报,2003.49(3):205—212.
[58]周康.同小军.许进.基于闭环DNA模型的八皇后问题算法[J].计算机工程与应用,2007,43(6):4—6.
[59] Kari L,Paun G,Rozenberg G,et al,DNA computing ,sticker systerns,and universality[J].Acta lnformatica.1998,35(5):40142.
[60] Freund R,Kari L,Paun G.DNA computing based on splicing:The existence of universal computers[J].Theory of Computing System,1999,32(1):69—1 12.
[61] Paun G.On the splicing oporation[J].Discrete Applied Mathematics,1996,70(1):57—79.
[62] Dassow J.Mitrana V.Splicing grammar systems[J].Computers and Artificial Intelligence,1996,15(2,3):109—122.
[63] Benenson Y,Paz-Elizur T,Adar R,et a1.Programmable and autonomous computing machine made of biomoleoules[J].Nature,200l,414(22):430—434.
[64]周康,王延峰,刘文斌,等.基于闭环DNA的边着色问题DNA算法[J].华中科技大学学报:自然科学版,2006,34(9):25—28.
[65] Chiu D T,Pezzoli E,Wu H,et a1.Using three-dimensional microfluidic networks for solving computationally hard problems[J].Applied Physical Seieuees,2001,98(6):296l一2966.
[66] Seemam N C,Wang H,Liu B,et a1.The perils of polynuleotides:The experimental gap belween the design and assembly of unusual DNA structures[C]//DIMACS Series in Discrete Mathematicsand Theoretical Computer Science,1999,44:215—233.
[67] Ma R I,Kallenbach N R,Sheardy R D,et a1.Three—arm nucleicacid junctions are flexible[J].Nucleic Acids Res,1996,14(24):9745_-9753.
[68] Jonoska N , Stephen A K , Mamahico S . Three dimensional DNA structures in computing[J].BioSystems,1999,52(1):143—153.
[69]罗生斌.白车身焊接机器人焊接路径规划及其仿真[D].上海:同济大学,2006.
[70]刘海江,罗生斌.白车身侧围工位焊接机器人路径优化研究[J].制造业自动化,2005,27(7):35-38.
[71]杨虎.利用遗传算法求解最小变形的焊接路径[J].机械设计与研究,2004,20(2).
[72] Bondy J A , Murty U S R. Graph theory with applications[M] .London : The Macmillan Press LTD ,1976.
[73]钱颂迪,田丰,胡运权,等.运筹学(修订版) [M] .北京:清华大学出版社,1990.
[74]周康,同小军,许进.路径排序问题基于表面的DNA算法[J].华中科技大学学报(自然科学版),2005,33(8).
[75] Lipton R J . DNA solution of hard computational problem[J ] . Science , 1995 , 268 (28) , 5422545.
[76]刘文斌.赋权Hamilton路的DNA计算模型[J].系统工程与电子技术,2002,24(6).