基于DSP+FPGA的遗传算法硬件实现

陈先生528

基于DSP+FPGA的遗传算法硬件实现

许家玉  经亚枝（南京航空航天大学 自动化学院 江苏 南京 210016）

摘 要：本文针对软件实现遗传算法速度慢的缺点，提出了一种在DSP和FPGA系统中的用硬件实现遗传算法的方法，并利用组合优化学中的旅行商问题对算法的实现进行效果验证。实际效果显示，这种硬件实现方法，不仅结构简单，而且大大提高了算法的运算速度，为算法在实时、高速场合的应用打下基础。

关键词：遗传算法，旅行商问题，FPGA，DSP

/ N2 `2 H1 w8 L# R" e

引 言

       遗传算法是一类借鉴自然选择和自然遗传机制的随机化最优搜索算法。在利用遗传算法求解问题时，它通过模拟自然界生物种群的遗传、杂交、变异的过程，把问题的每个可能的解都被编码成一个“染色体”,即个体,若干个个体构成了种群(所有可能解)。在遗传算法开始时,随机地产生一些个体(即初始解),根据预定的目标函数对每个个体进行评价,给出了一个适应度值。基于此适应度值,根据“适者生存”的原理，选择出个体经过交叉和变异运算进行再组合生成新的一代。这一群新个体由于继承了上一代的一些优良性状,因而在性能上要优于上一代,这样逐步朝着更优解的方向进化。因此,遗传算法可以看作是一个由可行解组成的群体逐代进化的过程，对求解问题进行编码遗传运算，最后得到最优解。经过数年的发展，遗传算法已经成为一种成熟的具有高度鲁棒性和适应性的全局优化算法，并已应用于模式识别、人工智能、机器学习和各种优化组合问题的解决中。

    旅行商问题（TSP）是一个典型的、易于描述却难以处理的组合优化问题。它是很多领域出现的多种复杂问题的集中概括和简化形式。TSP 问题可以简单地描述成：已知N个城市之间的相互距离，现有一个推销员必须遍访这 N个城市，并且每个城市只能访问一次，最后又必须返回出发城市，如何安排城市的访问次序，找一条走遍所有城市的最短旅行路线。目前，用遗传算法求解TSP问题主要还是采用软件实现的遗传算法，在实际应用中，就无法满足一些高速、实时的应用场合。

       随着电子技术和芯片制造技术的发展，FPGA被广泛应用于电子设计领域，由于FPGA可以根据用户的设计对其内部功能进行编程和配置，设计周期短，而且对系统的修改、维护和扩充都很方便。同时，随着FPGA芯片技术的发展和相关电子设计辅助工具（EDA）的支持，使得FPGA已经成为解

决系统级设计的一个重要选择方案，而且使得在硬件系统中进行遗传算法的实现成为可能。

1.     算法结构分析

       针对具体的TSP问题的算法实现，不仅要考虑到具体问题的特殊性，而且还要考虑到硬件的结构。这些细节包括算法的编码方式，选择、交叉、变异和适应度计算的具体算法以及整个系统的运行模式，下面对各部分作一大概的介绍。

1.1编码方式

       遗传算法是通过遗传操作对群体中具有某种结构形式的个体进行结构重组，从而在群体中不断逼近并搜索到问题的最优解。所以，必须通过一个编码的过程把问题空间的参数变成遗传空间的由基因按照一定结构组成的染色体或个体。具体的编码方式很多，其中De Jong提出的编码原理由于其可操作性强，而且相对来说客观明确，常常作为编码规则。

De Jong的编码原理包括两条规则：

（1）            有意义积木块编码规则：所定编码应当易于生成与所求问题相关的短矩和低阶的积木块。

（2）            最小字符集编码规则：所定编码应采用最小字符集以使问题得到自然的表示和描述。

       这只是一般的遗传算法编码中的两个规则。对于TSP问题，考虑到存在非法个体的问题，即在一个个体中，不能出现两个同样的基因，所以，编码相对来说还更复杂一些，一般采用多参数级联符号编码的方式。

1.2  选择运算

              在遗传算法中，利用选择运算按照某种算法对群体中的个体进行优胜劣汰，通常是建立在对个体的适应度进行评价的基础上的。常用的选择算法有：适应度比例算法、最佳个体保存法、联赛法等。
7 v$ I9 }6 x4 Q4 Q7 C( B: V, A

游客，如果您要查看本帖隐藏内容请回复

9 F7 e5 ?6 c+ G  `  V

道法自然

很好的资料，楼主还有DSP和FPGA的资料嘛？