英语原文共 27 页，剩余内容已隐藏，支付完成后下载完整资料
遗传算法在FPGA上的高性能并行实现
马休斯F.托尔夸托和马塞洛A. C.费尔南德斯
计算机工程和自动化系
北里约热内卢联邦大学(UFRN)嵌入式系统与可重构计算(RESRC)课题
摘要
遗传算法是用来解决搜索和优化问题，其中一个最优解可以找到一个迭代过程与概率和非确定性的过渡。然而，根据问题的性质，由于遗传算法的计算复杂性，在连续机器中找到解决方案所需的时间可能很高。提出了一种在现场可编程门阵列(FPGA)上并行实现遗传算法的方法。优化系统的处理时间是本项目的主要目标。结果与处理时间和现场可编程门阵列占用(在FPGA上)的各种人口规模进行了分析。对遗传算法在优化两个变量函数时的准确性进行了评估，并进行了硬件实现。然而，本文提出的高性能实现可以通过对硬件架构进行一些调整来处理更多的变量。
关键词:并行实现，FPGA，遗传算法，可重构计算。
1.介绍
在过去几年中，随着集成电路密度的增长和电源电压的不断降低，涉及实时系统的关键应用越来越多，这使得开发新的合适的计算解决方案变得更加困难。由于电子产品市场对较小时间范围内的高处理速度的强烈需求，同时又不忽视能源节约，在设计硬件解决方案以满足这一不断增长的需求方面，技术行业面临着极其激烈和极具挑战性的局面。研究人员和开发人员发现的解决这种需求的一种方法是使用算法并行化技术。并行处理用于同时处理数据，以便在计算算法的一个部分时，其他工作站对另一组数据[1]执行类似的操作。与顺序解决方案相比，将硬件实现与算法并行化相结合通常是高性能、高速度应用程序的满意解决方案。
现场可编程门阵列(FPGAs)是一种可重新配置的硬件设备，由于其架构的性质适合这种情况。考虑到fpga是巨大的可配置门，它们可以被编程成硬件中的多个并行路径。通过这种方式，可以实现真正的并行化，即运行的操作不需要争用相同的资源，因为每个操作将由不同的门[2]执行。FPGA密度的增加和价格的降低为开发人员和研究人员提供了更多的机会来使用密度更高的FPGA设备来实现硬件[3]，考虑到使用这样的设备是有利的，因为开发时间和成本大大降低了[4]。
研究了遗传算法、并行化技术和可重构硬件实现之间的融合，提出了一种基于FPGA的遗传算法并行实现方案。本文主要讨论需要满足纳秒时间约束的高性能和关键应用程序。另一方面,在应用程序的处理速度并不是关键因素限制或是低于低功耗的必要性,可以降低能量利用率降低时钟周期,考虑到动态功率利用率减少当工作频率低于最大理论是使用[5]。处理大量数据流的应用程序可以通过这里开发的这个实现受益并加速。应用实例有:数据挖掘、触觉互联网、海量数据处理和生物信息学。
1.1。相关工作
遗传算法和人工智能(AI)长期以来被应用于最多样化的领域，以优化和找到令人满意的解决方案，在计算、工程和其他领域。最近，在研究场景中观察到更广泛的应用和遗传算法的变体，如并行和分布式应用程序、硬件实现、遗传算子的新建议和遗传算法的混合(软件和硬件)实现。
在[6]中，提出了一种实现通用遗传算法的FPGA可定制知识产权核(IP核)。在这项工作中，作者重点研究了在IP核中实现的遗传算法的可编程性。可以对种群大小、世代数、交叉和突变率、随机数产生子和适应度函数进行定制。该工作的亮点之一是对这些功能的多种支持。所建议的IP最多可以编程8个适应度函数，这些功能可以与GA结合在一起并在同一FPGA器件中实现。拟议的核心还具有额外的输入/输出端口，允许用户添加更多的健身功能，这些功能已经在第二个FPGA设备或其他一些外部设备上实现。该实现利用了Xilinx Virtex II Pro (xc2vp30-7ff896)中13%的可用逻辑单元。然而，由于存在性能和灵活性之间的权衡，而且一旦作者将重点放在灵活性而不是性能上，那么与类似软件实现相比，加速只有times;5.16。
硬件遗传算法的实现也可以在[7]中观察到，
[8][9]和[10]。在[10]中详细介绍的工作表明，OIMGA的策略是只保留理想个体，使记忆需求大大降低。摘要提出了一种基于FPGA的遗传算法，该算法以概率向量的形式表示染色体的数目。这项工作的重点是降低硬件对内存、功耗和空间资源的消耗，但它并没有在FPGA上完全实现，因为它使用了一个用c 编写的软件来计算适应度函数的值。工作[9]提出了一种基于FPGA的高速遗传算法实现。该实现是基于[11]提出的HGA实现的，[11]是已知的第一个基于FPGA的GA实现，作者声称根据他们的实验，所开发的系统超越了任何现有的或提出的解决方案。P-HGAv1，由
HGA的[9]声称是参数化的，硅要求低，支持多种适应度函数。虽然作者关注的是算法的速度，并达到0.021毫秒的时间为每一代遗传算法，这种速度可能不兼容实时应用程序，需要低延迟。
[12]、[13]和[14]的工作展示了使用GAs的地面移动机器人的应用，前两个是在FPGA上的嵌入式实现。根据作者的介绍，[12]开发了第一个基于ga的地面机器人同步定位和映射(SLAM)系统的硬件实现。利用可重构硬件的流水线和并行化能力，实现了显著的硬件加速。在这个项目中，组成种群的遗传基因代表了基于先前位置的可能的机器人运动。之后，在[13]开发的工作中，目标是确定最优的运动，考虑到路线跟踪、低能耗、避免障碍物碰撞等各个方面。作者指出，该实现适合于实时使用，并指出所有的遗传算法阶段都已在硬件模块中实现。在这项工作中提出的解决方案提供了不到2毫秒的收敛时间，它使用了FPGA中可用的17600(97%)查找表(LUTs)中的17124，但是合成过程之后得到的频率没有得到通知。针对多移动机器人的全局轨迹规划问题，提出了一种基于协同进化策略的遗传算法。根据[15]理论，协同进化是两个或多个种群同时相互适应的过程，它被用来反映所有物种在特定的物理环境中同时共同进化的事实。[14]的实施有望改善传统天然气的遗传算子，并提出了一种新的遗传修饰算子，但这些发展并没有在硬件上实现。
在[16]、[17]和[18]中看到的实现是在FPGA上嵌入的数字信号处理和控制系统中的GA应用。[16]提出了一种用于自适应滤波的实时遗传算法，硬件实现了适应度函数、选择、交叉、变异、随机数发生器等功能模块。在硬件上进行了实现，合成后达到每秒32万代的速率。同时，[17]提出了一种基于滤波器组的多载波动态系统遗传算法。[18]的作者提出了一种基于遗传算法和FPGA的PID控制器的设计与实现。研究人员指出，基于FPGA和GA的智能PID控制器的设计方法已被成功验证，具有设计灵活、自动在线调试、可靠性高、技术开发周期短、执行速度快等优点。在本例中，每个GA染色体都用增益K、K和K的控制器集进行编码，未报告FPGA区域占用的详细信息和获得的吞吐量。pi d
最后，[19]和[20]给出了基于fpga的并行分布式遗传算法实现。[19]提出了一种多fpga并行遗传算法的解决方案。在并行气体中使用多个种群是基于这样一种思想，即种群隔离可以保持更大的遗传多样性，而它们之间的通信可以使气体一起工作以找到更好的解决方案。[19]的实现被应用于三个不同的基准测试，包括旅行推销员问题，作者从实验结果表明，在4 fpga的配置下，一个多核处理器遗传算法的平均加速度达到了30倍。[20]引入了GRATER，这是一种FPGA加速器的自动化设计工作流，它利用了不精确的计算来增加数据级并行性，并实现了更高的计算吞吐量。在这项工作的主要思想是建立一个谈判之间的电路涉及面积，能源和性能，以换取精度降低。这是通过对特定硬件块(如加法器和乘法器)的不精确实现来实现的，因为减少硬件面积可以更好地利用数据并行性，从而提高了产量。同样在[20]中，遗传规划被用来进化输入核的变体，直到找到一个具有理想分配的变体，它减少了合成核的面积，同时仍然随机地满足输出所需的质量。在Altera Stratix V FPGA上的合成结果表明，与基准相比，近似内核的缩小面积产生了1.4到3.0倍的增益，而质量损失不到1%。
需要注意的是，文献中的工作提出了基于FPGA软硬件的解决方案。这种答案增加了灵活性，但降低了吞吐量。因此，与文献中的论文不同，这项工作提出了GA的高性能并行实现。 该实现在allGA操作中使用完全并行策略，以最大化吞吐量。
1.2。论文组织
在第二节中，我们将探讨元启发式的理论基础，以及遗传算法的主要特点、优点和不同的应用。第3节将详细描述体系结构的开发和实现，描述用于构建并行遗传算法的各种硬件模块。稍后，在第4节中，将对上一节中描述的实现所获得的结果进行仔细分析。最后给出了仿真结果、FPGA的综合以及所提体系结构的验证。该分析将根据可重构硬件中嵌入的不同架构配置，对占用面积和采样频率等参数进行分析。接下来，第5节将获得的作品与现有的其他类似作品进行比较。最后，第6节将提出最后的考虑，对所得结果的结论。
2.遗传算法
该算法用于求解搜索和优化问题，通过迭代过程找到最优解，在迭代过程中，搜索从初始种群开始，然后结合初始种群的最优代表，得到一个新的种群来代替原来的[21]。
遗传算法是从随机产生的N条染色体开始的一种迭代算法。N甚至，在这个拟议的工作中，是为了促进执行。在每一个第k次迭代，也称为世代或纪元，N个染色体被评估、选择、重组和突变，形成一个新的群体也N个染色体，即整个亲本群体被新的后代取代。然后，将新的种群作为该算法下一个迭代(代)的输入，该种群更新过程重复K次，其中K为遗传算法的代数。
算法1显示了遗传算法的伪码。这段代码详细描述了将在接下来的小节中介绍的实现中使用的所有变量和过程。变量x[m](k)表示第k代m位的第j条染色体，x[m](k)是存储所有N条染色体的向量，即
(1)
(1)
初始化过程结束后，适应度函数FF(算法1第4行)计算种群的N条染色体x[m](k)的适应度值
算法1遗传算法
用随机值初始化X [m]（k）
将该操作应用于所有染色体，并为每个第j个染色体得出各自的值y j [a]（k），其中b是代表适应度值的位数。 染色体x j [m]（k）的值y j [a]（k）越好，它在新世代中延续的可能性就越大。 所有N个人的适应度值存储在
(2)
(2)
在计算第k代第j个染色体的适应度值后，进行选择操作。在GAs中，选择的目的是突出染色体x[m](k)及其各自的适应度值y[a](k)，以便产生更好的未来种群。j j在文献中有很多种选择方法，其中有排名法、锦标赛法、轮盘赌法和精英主义法。本实现中使用的锦标赛选择方法是最常用的[22]之一，它使存储在X[m](K)中的种群中的两个或多个随机选择的染色体之间进行竞争。这种竞争包括比较所有参与的染色体的强度(适合度)，y[a](k)和在y[a](k)中各自拥有最佳值的那条染色体，然后在算法中向前传递它们的基因。j 选择函数在这里称为SF(算法1的第7行)，它输入第k代的向量Y[a](k)和X[m](k)，对于每个输入值，它输出变量w[m](k)，该变量可以假定存储在X [m]（k）中的N个染色体中任何一个的值。所有w j [m]（k）个值都分组
(3)
(3)
以便在交叉阶段使用。
第k代的交叉阶段是通过选择函数选择群体中最合适的染色体(储存在W[m](k)中)，目的是产生新的染色体，在突变阶段后，组成更新向量X[m](k)的下一代遗传算法。在文献中提出了几种交叉技术，在实施中采用的策略是单点交叉。这里的交叉操作称为CF(算法1的第10行)，它将第k代向量W[m](k)中的元素作为输入对，将第k代向量W[m](k)中的元素作为输出对，
(4)
(4)
它在交叉后储存染色体，也就是新的第k个后代。
遗传算法的最后一步是突变操作，改变群体P染色体的值，以提供更大的多样性，避免其解决方案稳定在局部极小值。突变率，MR，是负责控制突变染色体数量的参数。正常情况下，MR值在0.1%到2%之间。P值可以用表达式很容易地计算出来
(5)
(5)
这里的突变操作称为MF，在算法1的第13行中给出，具体如公式6所示。
(6)
(6)
其中z为要突变的染色体，Rand为随机变量。z和Rand (zoplus;Rand)之间的这种排他或运算的结果是x。
3.硬件建议
图1给出了所提出的GA硬件实现的总体架构。整个算法是使用类似于[23]的并行架构开发的，该架构关注于加速处理速度，利用可用的硬件资源。图中详细描述了所提议的实现的主要子系统，这些子系统又被封装起来，以使架构的总体可视化不那么复杂
SyncM
RX1
x [m] (k)1
w w [m] [m] (k) (k)12
SM2
͘͘͘
͘͘͘
͘͘͘
͘͘͘
RXn
x [m] (k)n
FFMn
y[一](k)n
SMn
图1:提出的并行遗传算法实现的一般架构。
根据算法1，可以观察到一个包含m个比特的N条染色体的种群，其中x[m]
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[236737]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
