基于遗传算法的组合逻辑电路设计的FPGA实现

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系列EPIC6Q240C8型号芯片上进行了实现。系统采用Verilog语言编写，开发平台为Altera公司自带的Quart usII 6．0集成环境。为验证系统的正确性和测试系统的性能，本文，对系统进行了测试，即给出一个三输入一输出的组合逻辑电路的真值表，测试真值表如表1所示。