可逆逻辑进化设计方法研究与开发
|
摘要
进化算法(Evolution Algorithm,EA)具有智能性、自适应性和全局搜索能力,能将实际问题编码后进行运算;PLD(ProgrammableLogic Device,PLD)具有可重构性,可以通过程序控制重新配置内部电路的功能与结构。基于EA和PLD的这些特点,科学家们提出了进化硬件(Evolvable Hardware,EHW)这一概念,并很快成为一个热门的研究领域,这为研究自适应机器提供了新的方法。传统的EHW设计法通常采用遗传算法(Genetic Algorithm,GA),由于GA在对复杂电路进行编码和解码时很复杂繁琐,可读性较差,并且容易产生早熟,甚至发生运行中断。本文研究了一种新的进化算法——基因表达式编程(Gene Expression Programming,GEP),将它应用于进化硬件设计中,研究了基于GEP的函数建模方法,国内外对基于GA的进化硬件进行了大量研究,基于这些研究成果最后研究了基于GA的可逆逻辑电路设计方法。
本文首先研究了进化硬件的研究历史和国内外研究状况,目前存在的主要问题。第二章研究了最常用的进化算法GA和进化硬件:主要研究了GA的二进制编码、实数编码和适应度评估;研究了进化硬件的原理和设计方法,基于GA的硬件编码方法和适应度评估方法。第三章研究了新兴的进化算法GEP及其在函数建模中的应用,研究了基于GEP的进化硬件设计:主要研究了算法的基本原理,基因和染色体构成,树型编码方法和适应度函数设计,提出了一种改进的GEP,并对GEP与GA进行了比较;重点研究了电路的树型编码法和进化操作步骤(包括交叉、变异、选择、插串和移项操作);对GEP在函数建模中的应用进行了实验;设计了一个基于GEP进化技术的半加器。在前两章的基础上,第四章研究了GA在可逆逻辑电路设计中的应用,首先研究了几种基本的量子逻辑门和量子电路,研究基于模板技术和PPRM的可逆逻辑电路综合法,最后研究了基于GA的量子电路综合法,从逻辑门和电路的编码、适应度评估上进行了研究。第五章对全文做了总结,并对今后的发展方向进行了展望。
Evolution algorithm(EA) has the intelligence,adaptability and global searching ability,it can encode the real problem and then operate.PLD has the reconfiguration ability,which can reconfigure the function and structure of internal circuit by program.Based on the characteristics of EA and PLD,evolvable hardware(EHW) was put forward,and it quickly became an important research field.EHW provides a new method for studying adaptive machine.Traditional EHW usually use genetic algorithm(GA),which is very complicated on coding and decoding,bad readability,and easy to cause early maturity,even interrupt running.A new evolution algorithmgene expression programming(GEP) is studied,which is applied to evolvable hardware design.Function modeling method based on GEP is studied.At last the method of reversible logic design based on GA is studied.
The propose and research status at home and abroad of EHW,and the present main problem are firstly studied.The most usual evolution algorithm GA and EHW are studied in chapter 2:the binary coding,real coding and fitness evaluation are mainly studied.The principle and design method of EHW and the hardware coding method and fitness evaluation method based on the GA are studied.A new evolution algorithm GEP and its application on function modeling are studied in chapter 3.And the the EHW based on GEP is studied.The principle of GEP,the structure of gene and chromosome,the tree coding method and fitness function are studied.An improved GEP is proposed,and the difference between GEP and GA is studied,the tree coding methods of circuit and evolution operation steps(including crossover,mutation,selection,insert and moving)are mainly studied.The experiment of the GEP application on function modeling is made.Half-adder circuit based on GEP evolvable technology is designed.The experiment shows quick convergence,and the circuit designed is in full accordance with the real circuit.On the base of the last two chapters,the application of GA on reversible logic circuit is studied.Firstly several basic kinds of quantum logic gates and quantum circuit is studied.And the synthesis of reversible logic circuit based on template technology and PPRM is researched.At last the quantum circuit synthesis based on GA is studied,which is from logic gate and circuit coding,fitness evaluation.The paper is summarized in chapter 5,and the future development direction is prospected.
本文首先研究了进化硬件的研究历史和国内外研究状况,目前存在的主要问题。第二章研究了最常用的进化算法GA和进化硬件:主要研究了GA的二进制编码、实数编码和适应度评估;研究了进化硬件的原理和设计方法,基于GA的硬件编码方法和适应度评估方法。第三章研究了新兴的进化算法GEP及其在函数建模中的应用,研究了基于GEP的进化硬件设计:主要研究了算法的基本原理,基因和染色体构成,树型编码方法和适应度函数设计,提出了一种改进的GEP,并对GEP与GA进行了比较;重点研究了电路的树型编码法和进化操作步骤(包括交叉、变异、选择、插串和移项操作);对GEP在函数建模中的应用进行了实验;设计了一个基于GEP进化技术的半加器。在前两章的基础上,第四章研究了GA在可逆逻辑电路设计中的应用,首先研究了几种基本的量子逻辑门和量子电路,研究基于模板技术和PPRM的可逆逻辑电路综合法,最后研究了基于GA的量子电路综合法,从逻辑门和电路的编码、适应度评估上进行了研究。第五章对全文做了总结,并对今后的发展方向进行了展望。
Evolution algorithm(EA) has the intelligence,adaptability and global searching ability,it can encode the real problem and then operate.PLD has the reconfiguration ability,which can reconfigure the function and structure of internal circuit by program.Based on the characteristics of EA and PLD,evolvable hardware(EHW) was put forward,and it quickly became an important research field.EHW provides a new method for studying adaptive machine.Traditional EHW usually use genetic algorithm(GA),which is very complicated on coding and decoding,bad readability,and easy to cause early maturity,even interrupt running.A new evolution algorithmgene expression programming(GEP) is studied,which is applied to evolvable hardware design.Function modeling method based on GEP is studied.At last the method of reversible logic design based on GA is studied.
The propose and research status at home and abroad of EHW,and the present main problem are firstly studied.The most usual evolution algorithm GA and EHW are studied in chapter 2:the binary coding,real coding and fitness evaluation are mainly studied.The principle and design method of EHW and the hardware coding method and fitness evaluation method based on the GA are studied.A new evolution algorithm GEP and its application on function modeling are studied in chapter 3.And the the EHW based on GEP is studied.The principle of GEP,the structure of gene and chromosome,the tree coding method and fitness function are studied.An improved GEP is proposed,and the difference between GEP and GA is studied,the tree coding methods of circuit and evolution operation steps(including crossover,mutation,selection,insert and moving)are mainly studied.The experiment of the GEP application on function modeling is made.Half-adder circuit based on GEP evolvable technology is designed.The experiment shows quick convergence,and the circuit designed is in full accordance with the real circuit.On the base of the last two chapters,the application of GA on reversible logic circuit is studied.Firstly several basic kinds of quantum logic gates and quantum circuit is studied.And the synthesis of reversible logic circuit based on template technology and PPRM is researched.At last the quantum circuit synthesis based on GA is studied,which is from logic gate and circuit coding,fitness evaluation.The paper is summarized in chapter 5,and the future development direction is prospected.
引文
(1) Yao X,Higuichi T.Promises and Challenges of Evolvable Hardware[J].IEEE Trans:On Systems Man and Cybernetics-PartC:Applications and Reviews,1999,29(1):87-97.
(2)赵曙光.基于进化的电路自动设计方法研究[D].西安:西安电子科技大学博士学位论文,2003.
(3)涂航.演化硬件研究[D].武汉:武汉大学博士学位论文,2004.
(4) D.Keymeulen and A.Stoica.Fault-Tolerant Evolvable Hardware Using Field-Programmable Transistor Arrays[J].IEEE Transaction on Reliability,2000,vol.49(3):305-316.
(5) A.Stoica.Evolvable Hardware for Space Applications[J].In the Second International Conference on Evolvable Systems:From Biology to Hardware(ICES98),1998:166-173.
(6) R.Zebulum.A Reconfigurable Platform for the Automatic Synthesis of Analog Circuits[J].In the Second NASAIDOD Workshop on Evolvable Hardware(EH '00),2000:91-98.
(7) Hemmi H,Mizoguchi J,ShimoharaK.Development and evolution of hardware behaviors[J].In Artificial Life Ⅳ:Proc.of 4~(th) Int.Workshop on the Synthesis and Simulation of Living Systems,MIT Press,1994:371-376.
(8) Hemmi H,Mizoguchi J,Shimohara K.Evolving Large Scale Digital Circuits[J].In:Proc.of the 5th Int.Workshop on the Synthesis and Simulation of Living Systems,Nara,Japan,1996:168-173.
(9) J.R Koza.Automated Synthesis of Analog Electrical Circuits by Means of Genetic Programming[J].IEEE Trans On Evolutionary Computation,1997,vol.1(2):109-128.
(10) A.Thompson.Explorations in Design Space:Unconventional Electronics Design Through Ariticial Evolution[J].IEEE Trans On Evolutionary Computation,1999,vol.3(3):167-196.
(11)徐阳.硬件演化理论、方法及实现[D].南京:南京航空航天大学硕士学位论文,2003.
(12) Higuchi T,Murakawa M,Kajitani I,et al.Evolvable hardware at function level[J].In:Proc.1997IEEE Int.Conf.Evolutionary Computation,Piscataway,NJ,1997:187-192.
(13)康立山,何巍,陈毓屏.用函数型可编程器件实现演化硬件[J].计算机学报,1999,Vol.22(7):791-784.
(14)徐渊,杨波,朱明程.模拟退火与遗传算法结合的数字FIR滤波器硬件进化算法[J].计算机辅助设计与图形学学报,2006,Vol.18(5):674-679.
(15)林勇,罗文坚,王煦法.硬件电路的选择性进化冗余[J].中国科学技术大学学报.2006,Vol.5(36):523-529.
(16)张义国,罗文坚,王煦法.基于免疫原理的逻辑电路设计算法[J].计算机工程与应用,2006,Vol.11(42):38-41.
(17)赵曙光,杨万海.基于函数级FPGA原型的硬件内部进化[J].计算机学报,2002,Vol.6(25):666-669.
(18)赵曙光,焦李成,王宇平等.基于多目标遗传算法的模拟电路进化设计方法[J].西安电子科技大学学报(自然科学版).2004,Vol.3(31):342-346.
(19)云庆夏.进化算法[M].北京:冶金工业出版社,2000.
(20)周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.
(21)王小平,曹立明.遗传算法--理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
(22)张伟.基于进化算法的硬件演化基础研究[D].南京:南京理工大学硕士学位论文,2008.
(23)刘睿.组合电路设计演化算法及软件框架[D].武汉:中国地质大学硕士学位论文,2008.
(24)莫海芳,康立山.用GEP实现复杂函数的自动建模[J].系统仿真学报,2008,Vol.20(11):2828-2831.
(25)李康顺,梁九生等.一种基于GEP的演化硬件复杂电路优化算法[J].计算机工程与应用,2008,44(8):83-86.
(26)谢方军,唐常杰等.基于基因表达式的演化硬件进化和优化算法[J].计算机辅助设计与图形学学报,2005,Vol.17(7):1415-1420.
(27)陈汉武.量子信息与量子计算简明教程[M].南京:东南大学出版社,2006.
(28)陈清.量子信息处理方案研究及其应用[D].合肥:中国科学技术大学博士学位论文,2006.
(29)R.Raussendorf.Measurement-based quantum computation with cluster states[D].博士学位论文,Ludwig-Maximilians-Universitat,LMU,Munchen,Germany,2003.
(30) Wen-zhen Cao,Tian Li,Hui-juan Jiang and Chong Li.Single qubit manipulation in Heteronuclear Diatomic Molecular System[J].International Journal of Quantum Information,2008,Vol.6(6).
(31)胡靖,马光胜,李东海,冯刚.考虑串扰因素的可逆电路的符合综合方法[J].电子学报,1998,7:331-332.
(32)詹明生,张登玉.量子逻辑门的表示与实现[J].原子与分子物理学报,2008,5(36):1029-1034.
(33)李文骞.量子可逆电路的自动合成及优化的相关关键技术的算法研究[D].南京:东南大学硕士学位论文,2007.
(34) Gupta P,Agrawal A,Jha N K.An Algorithm for Synthesis of Reversible Logic Circuits[J].IEEE Computer-Aided Design of Integrated Circuits and System,2006,25(11):2317-2330.
(35)乐亮.基于遗传算法的量子可逆逻辑电路综合方法研究[D].合肥:合肥工业大学硕士学位论文.2009.
(36) Vassilev V,Job D,Miller J.Towards the Automatic Design of More Efficient Digital Circuits [J].In:Proc.of the Second NASA/DOD Workshop on Evolvable Hardware(EH'00),2000,PaloAlto,CA:151-160.
(37) Stoica,R.Zebulum,and D.Keymeulen.Reconfigurable VLSI Architectures for Evolvable Hardware:from Experimental Field Programmable Transistor Arrays to Evolution-Oriented Chips[J].IEEE.Transactions on VLSI,2001,vol.9(1):227-232.
(38) Higuchi T,Iwata M,Kajitani I,et al.Evolvable hardware and its application to pattern recognition and fault-tolerant systems[J].In Toward Evolvable hardware:The evolutionary Engineering approach,Springer-Verlag,Berlin,1996:118-135.
(39) Holland J H.Adaptation in Natural and Artificial Systems.MIT Press,1975
(40) Goldberg D E.Genetic Algorithms in Search,Optimization,and Machine Learning.Reading [M].MA,Addison-Wisely,1989.
(41) J.F.Miller,D.Job,and V.K Vassilev.Principles in the Evolutionary Design of Digital Circuits-Part Ⅰ.[J]Genetic Programming and Evolvable Machines,Ⅰ(1/2):7-35,April 2000.
(42) Candida Ferreira.Gene Expression Programming:A New Adaptive Algorithm for Solving Problems[J].Complex System,2001,13(2):86-129.
(43) T Sasao.Logic Synthesis and Optimization[M].The Netherlands:Kluwer Academic Publishers,1993.
(44)D Maslov,C Young,D M Miller.Quantum Circuit Simplication using Templates[J].Design,Automation and Test in Europe,Munich,2005:1208-1213.
(45)郑金华.多目标进化算法及其应用[M].北京:科学出版社,2007.
(2)赵曙光.基于进化的电路自动设计方法研究[D].西安:西安电子科技大学博士学位论文,2003.
(3)涂航.演化硬件研究[D].武汉:武汉大学博士学位论文,2004.
(4) D.Keymeulen and A.Stoica.Fault-Tolerant Evolvable Hardware Using Field-Programmable Transistor Arrays[J].IEEE Transaction on Reliability,2000,vol.49(3):305-316.
(5) A.Stoica.Evolvable Hardware for Space Applications[J].In the Second International Conference on Evolvable Systems:From Biology to Hardware(ICES98),1998:166-173.
(6) R.Zebulum.A Reconfigurable Platform for the Automatic Synthesis of Analog Circuits[J].In the Second NASAIDOD Workshop on Evolvable Hardware(EH '00),2000:91-98.
(7) Hemmi H,Mizoguchi J,ShimoharaK.Development and evolution of hardware behaviors[J].In Artificial Life Ⅳ:Proc.of 4~(th) Int.Workshop on the Synthesis and Simulation of Living Systems,MIT Press,1994:371-376.
(8) Hemmi H,Mizoguchi J,Shimohara K.Evolving Large Scale Digital Circuits[J].In:Proc.of the 5th Int.Workshop on the Synthesis and Simulation of Living Systems,Nara,Japan,1996:168-173.
(9) J.R Koza.Automated Synthesis of Analog Electrical Circuits by Means of Genetic Programming[J].IEEE Trans On Evolutionary Computation,1997,vol.1(2):109-128.
(10) A.Thompson.Explorations in Design Space:Unconventional Electronics Design Through Ariticial Evolution[J].IEEE Trans On Evolutionary Computation,1999,vol.3(3):167-196.
(11)徐阳.硬件演化理论、方法及实现[D].南京:南京航空航天大学硕士学位论文,2003.
(12) Higuchi T,Murakawa M,Kajitani I,et al.Evolvable hardware at function level[J].In:Proc.1997IEEE Int.Conf.Evolutionary Computation,Piscataway,NJ,1997:187-192.
(13)康立山,何巍,陈毓屏.用函数型可编程器件实现演化硬件[J].计算机学报,1999,Vol.22(7):791-784.
(14)徐渊,杨波,朱明程.模拟退火与遗传算法结合的数字FIR滤波器硬件进化算法[J].计算机辅助设计与图形学学报,2006,Vol.18(5):674-679.
(15)林勇,罗文坚,王煦法.硬件电路的选择性进化冗余[J].中国科学技术大学学报.2006,Vol.5(36):523-529.
(16)张义国,罗文坚,王煦法.基于免疫原理的逻辑电路设计算法[J].计算机工程与应用,2006,Vol.11(42):38-41.
(17)赵曙光,杨万海.基于函数级FPGA原型的硬件内部进化[J].计算机学报,2002,Vol.6(25):666-669.
(18)赵曙光,焦李成,王宇平等.基于多目标遗传算法的模拟电路进化设计方法[J].西安电子科技大学学报(自然科学版).2004,Vol.3(31):342-346.
(19)云庆夏.进化算法[M].北京:冶金工业出版社,2000.
(20)周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.
(21)王小平,曹立明.遗传算法--理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
(22)张伟.基于进化算法的硬件演化基础研究[D].南京:南京理工大学硕士学位论文,2008.
(23)刘睿.组合电路设计演化算法及软件框架[D].武汉:中国地质大学硕士学位论文,2008.
(24)莫海芳,康立山.用GEP实现复杂函数的自动建模[J].系统仿真学报,2008,Vol.20(11):2828-2831.
(25)李康顺,梁九生等.一种基于GEP的演化硬件复杂电路优化算法[J].计算机工程与应用,2008,44(8):83-86.
(26)谢方军,唐常杰等.基于基因表达式的演化硬件进化和优化算法[J].计算机辅助设计与图形学学报,2005,Vol.17(7):1415-1420.
(27)陈汉武.量子信息与量子计算简明教程[M].南京:东南大学出版社,2006.
(28)陈清.量子信息处理方案研究及其应用[D].合肥:中国科学技术大学博士学位论文,2006.
(29)R.Raussendorf.Measurement-based quantum computation with cluster states[D].博士学位论文,Ludwig-Maximilians-Universitat,LMU,Munchen,Germany,2003.
(30) Wen-zhen Cao,Tian Li,Hui-juan Jiang and Chong Li.Single qubit manipulation in Heteronuclear Diatomic Molecular System[J].International Journal of Quantum Information,2008,Vol.6(6).
(31)胡靖,马光胜,李东海,冯刚.考虑串扰因素的可逆电路的符合综合方法[J].电子学报,1998,7:331-332.
(32)詹明生,张登玉.量子逻辑门的表示与实现[J].原子与分子物理学报,2008,5(36):1029-1034.
(33)李文骞.量子可逆电路的自动合成及优化的相关关键技术的算法研究[D].南京:东南大学硕士学位论文,2007.
(34) Gupta P,Agrawal A,Jha N K.An Algorithm for Synthesis of Reversible Logic Circuits[J].IEEE Computer-Aided Design of Integrated Circuits and System,2006,25(11):2317-2330.
(35)乐亮.基于遗传算法的量子可逆逻辑电路综合方法研究[D].合肥:合肥工业大学硕士学位论文.2009.
(36) Vassilev V,Job D,Miller J.Towards the Automatic Design of More Efficient Digital Circuits [J].In:Proc.of the Second NASA/DOD Workshop on Evolvable Hardware(EH'00),2000,PaloAlto,CA:151-160.
(37) Stoica,R.Zebulum,and D.Keymeulen.Reconfigurable VLSI Architectures for Evolvable Hardware:from Experimental Field Programmable Transistor Arrays to Evolution-Oriented Chips[J].IEEE.Transactions on VLSI,2001,vol.9(1):227-232.
(38) Higuchi T,Iwata M,Kajitani I,et al.Evolvable hardware and its application to pattern recognition and fault-tolerant systems[J].In Toward Evolvable hardware:The evolutionary Engineering approach,Springer-Verlag,Berlin,1996:118-135.
(39) Holland J H.Adaptation in Natural and Artificial Systems.MIT Press,1975
(40) Goldberg D E.Genetic Algorithms in Search,Optimization,and Machine Learning.Reading [M].MA,Addison-Wisely,1989.
(41) J.F.Miller,D.Job,and V.K Vassilev.Principles in the Evolutionary Design of Digital Circuits-Part Ⅰ.[J]Genetic Programming and Evolvable Machines,Ⅰ(1/2):7-35,April 2000.
(42) Candida Ferreira.Gene Expression Programming:A New Adaptive Algorithm for Solving Problems[J].Complex System,2001,13(2):86-129.
(43) T Sasao.Logic Synthesis and Optimization[M].The Netherlands:Kluwer Academic Publishers,1993.
(44)D Maslov,C Young,D M Miller.Quantum Circuit Simplication using Templates[J].Design,Automation and Test in Europe,Munich,2005:1208-1213.
(45)郑金华.多目标进化算法及其应用[M].北京:科学出版社,2007.