遗传算法(Genetic Algorithm)是模仿达尔文生物进化论的天然挑选和遗传学机理的生物进化进程的核算模型，是一种通过模仿天然进化进程查找最优解的办法，它开端是由美国Michigan大学J．Holland教授于1975年首先提出来的。跟着经济社会的快速开展，人类科学研究与出产活动的广度与深度都大大拓宽了。科研与出产实践中出现出的很多新课题对作为社会开展催化剂的信息与操控科学提出了史无前例的应战。传统信息处理算法在面临各种非线性、不确认、不能准确解析以及建模机理杂乱的问题时，往往显得绰绰有余。正是在这种布景下，各种智能信息处理算法如漫山遍野般出现出来。作为智能信息处理算法中的重要一员，遗传算法近年来以其共同而杰出的功用日渐引起了人们的重视。
组合逻辑电路其特色是功用上无回忆，结构上无反应，即电路在恣意时刻的输出状况只取决于该时刻各输入状况的组合，而与电路的原状况无关。本文通过实例介绍组合逻辑电路的规划办法，并通过电子规划主动化EDA(Electronic Design Automation)进行仿真剖析，使组合逻辑电路的规划变得更便利，更有用。
跟着FPGA功用的不断进步，依据FPGA的核算加快现已逐渐成为进步核算速度和核算功率的重要手法之一。FPGA能够完结程序的并行化处理，不只结构简略，而且有效地减少了运算时刻、进步了运转功率，为遗传算法能在一些实时、高速的场合得到运用供给了依据。
1 依据FPGA遗传算法规划
遗传算法是一种多点并行的迭代查找算法，它的每一代称为一个种群，由多个个别组成，每个个别称为染色体，染色体由一定数意图字符组成。每个字符称为一个基因，基因在染色体中的方位决议了基因所表达的特性。
文中依据FPGA的遗传算法，整个别系分为4个单元，4个单元分别为：挑选单元、穿插单元、变异单元和习惯度核算单元。
1．1 挑选单元
挑选单元履行遗传算法中的挑选操作。挑选战略决议哪些个别存活并得以繁衍，因其直接关系到遗传算法的运转导向问题故对遗传算法的功用有直接而且严重的影响。规范遗传算法所选用的轮盘赌挑选战略简洁直观，但或许会发生较大的抽样差错。所以，各种改善的挑选战略发生了。
最早提出的运用浓度操控的挑选战略能够确保集体的多样性然后避免了早熟现象而且进步了算法的鲁棒性及运算功率。后来通过对浮点遗传算法早熟收敛现象的剖析，有人提出了一种新的父代挑选战略，即运用当时代的子代个别作为下代的父代个别，可使穿插算子继续地探究和开发新空间。现在，人们又发现能够通过挑选战略的改动调控并坚持种群多样性。这类研究成果中，文献中说到的重复串的习惯度处理是一个有利的测验。
1．2 穿插单元
穿插模块履行遗传算法中的穿插操作。由随机数模块发生的随机数与事前确认的穿插概率相比较，假如随机数小于穿插概率，则一对个别进行穿插操作，不然该对个别不变，直接进入变异模块。
文中一对个别进行穿插操作的基因位由随机数决议。随机数模块发生一个与个别等长的随机二进制串，若随机二进制串中的某一位为1，则该对个别中该方位的基因彼此穿插；不然，该对个别中该方位的基因坚持不变。
1．3 变异单元
变异模块履行遗传算法中的变异操作。与穿插模块类似，变异模块也是将随机数模块发生的随机数与事前确认的变异概率相比较，决议是否进行变异操作。一起个别中进行变异操作的基因位也是由一个与个别等长的随机二进制字符串决议的。对个别而言，履行变异操作的基因位不宜过多，不然简单对个别形成较大的损坏，影响种群的稳定性。本文将两个随机二进制字符串(每一位0、1等概率)进行相与操作，这样得到的新的随机二进制字符串中每一位为1的概率将降低到25％，用这个新的随机二进制串来决议个别变异的基因位。这样履行变异操作的个别中，每一位基因变异的概率也会降低到25％。
1．4 习惯度核算单元
习惯度核算模块履行遗传算法中的习惯度核算比较操作，它依据习惯度核算函数来核算种群中每一个个别的习惯度，包含遗传算法开端时初始化发生的种群和后来遗传变异后发生的种群，并把每个个别的习惯度巨细保存到存储器中。一起，习惯度核算模块还需要记载每一代种群中习惯度最高的个别。习惯度核算模块有一个内置的计数器，计数器随习惯度核算模块的发动而发动，从0开端计数，每个时钟周期加1。计数器数值表明当时个别及其习惯度在存储器模块傍边的寄存地址。习惯度核算模块停止作业时，计数器会从头归零，等候新一轮的发动信号。
2 遗传算法的进程规划
遗传算法通过对当时种群施加挑选、穿插、变异等一系列遗传操作，发生出新一代的种群，通过屡次迭代，使种群逐渐进化到包含或挨近最优解的状况，如图1所示。一般来说，一个完好的遗传算法包含编码、初始种群的生成、用于进行个别评价的习惯度函数的规划、遗传算子(挑选、穿插和变异)以及操控参数(停止原则)的设定5个方面。
1)体系由外部给出reset信号：随机数模块开端发生随机数种子；操控模块重启，从头发动后，由该模块操控体系运转。
2)操控模块给出相应信号，初始化模块运转，初始化种群。
3)当初始化结束后，有操控模块宣布相应信号，体系进入进化核算阶段，进行遗传算法的具体操作。
4)各个遗传算法功用模块进行算子操作，经由穿插、变异、挑选操作发生新的种群，一起记载体系的运转信息。如未完本钱代进化核算，则重复本过程。
5)完结一代核算后，由操控模块宣布相应指令，存储相关运转参数、转化存储器的作业状况。假如以完结核算，则宣布完结信号，假如未完结，重复过程4)。
2．1 遗传算法编码
把一个问题的可行解从其解空间转化到遗传算法所能处理的查找空间的转化办法叫做编码。编码办法应具有如下性质：齐备性、封闭性、健全性和非冗余性。
遗传算法的编码办法有很多种，二进制编码办法是最常用的编码办法之一，最早由Holland提出。可是二进制编码的遗传算法进行数值优化时，存在接连到离散的映射差错、精度不高，最优解邻近查找较慢等缺陷。尽管进步个别编码串长度能够进步精度，可是会使遗传算法的查找空间添加，然后使得查找变得反常缓慢。
本文中遗传算法首要处理的问题是组合逻辑电路的主动规划，组合逻辑电路由与门、或门、非门、同或门、异或门五种根本的门电路组成。在FPGA进步行遗传算法的编码，本文选用二进制字符串编码的办法，每个个别都有64位二进制数组成，由64位二进制数解码出一个组合逻辑电路。
2．2 随机数发生模块
随机数操控模块的作用是依据外部信号操控随机数内部模块，宣布相应的使能、重启信号，发生随机数种子，然后发生随机数。
本体系中随机数模块所发生的随机序列由线性反应移位寄存器(Linear Feedback Shift Registers，LFSR)生成。LFSR在FPGA上易于完结，且所发生的随机序列具有周期长、随机性好的特色。随机数模块需要向挑选模块供给随机序列，作为存储器单元的地址，一起随机数模块还要向穿插模块和变异模块供给随机序列，用于确认是否履行穿插和变异操作，以及履行穿插和变异操作的方位。
2．3 存储器模块
存储器模块用来存储种群中的个别及其习惯度。在本体系中，个别和习惯度是分隔存储的，因此对整个种群而言，其存储区可分为4个部分：父代个别存储区，父代习惯度存储区，子代个别存储区以及子代习惯度存储区。
因为本体系中的遗传算法选用彻底流水线完结，因此必然会涉及到对存储器模块的一起读写操作，比如在挑选模块从存储器模块中读取父代种群中的个别及其习惯度的一起，习惯度模块则在向存储器模块中写入子代种群中的新个别及其习惯度。
3 试验成果
体系在Altera公司的Cyclone系列EP%&&&&&%6Q240C8类型芯片进步行了完结。体系选用Verilog言语编写，开发渠道为Altera公司自带的Quart usII 6．0集成环境。为验证体系的正确性和测验体系的功用，本文，对体系进行了测验，即给出一个三输入一输出的组合逻辑电路的真值表，测验真值表如表1所示。
遗传算法参数设置如下：种群规划为100，穿插概率为0．6，变异概率为0．1，基因长度为16，遗传代数为100。其间针对给出的真值表，通过代码输入、编译、归纳、布局布线后，得到成果如图2所示。
即最优解为：C3bFC396。通过解码，得到电路图如图3所示。所得到的电路图满意真值表的要求。
4 结束语
本文在FPGA上完结了依据遗传算法的组合逻辑电路的主动规划。对整个别系结构进行了自顶而下的规划，对模块功用进了区分。硬件完结遗传算法能有效地缩短运转时刻，为实时运用供给了或许。跟着FPGA芯片技能的进一步开展，大规划并行遗传算法的完结也将成为或许。
