基于趋向型紧凑遗传算法的演化硬件实现方法

摘要

一种基于趋向型紧凑遗传算法的演化硬件实现方法，该方法包括：1)获取实际的可编程逻辑器件的配置参数；2)将实际的可编程逻辑器件的配置参数进行映射并形成染色体个体；3)计算当前染色体个体的适应度值fitness；4)根据适应度值fitness的情况对演化是否终止进行判断。本发明提供了一种可增强硬件配置结构位串的搜索能力、提高候选解空间的多样性、更快地获得高质量的最优的硬件配置结构位串、大幅度地提高了收敛速度、减少得到最优的硬件电路结构所需要的时间以及增强了实际演化硬件的实时性的基于趋向型紧凑遗传算法的演化硬件实现方法。

说明书

技术领域

本发明属计算机控制领域，涉及一种演化硬件的实现方法，尤其涉及一种 基于趋向型紧凑遗传算法的演化硬件实现方法。

背景技术

演化硬件(Evolvable Hardware)是一种硬件电路或者大规模集成电路，它 能够像生物一样根据环境的变化而改变自身的结构以适应其生存环境，具有自 组织、自适应、自修复的功能。

演化硬件是通过模拟自然演化过程将演化算法的思想用于硬件物理结构的 设计，主要由两个要素构成：一个是以CPLD、FPGA为代表的可编程逻辑器件， 另一个是演化算法。演化硬件的实现，建立在演化计算和可编程逻辑器件发展 的基础上。

演化硬件的基本原理是将可编程逻辑器件的结构和参数等组成的配置位串 作为演化算法的演化对象，通过演化算法的演化操作产生当前所需实现功能的 相应的配置位串，再将其下载到可编程逻辑器件中，经过反复的需求适应度比 较和演化操作，不断地生成趋近于需求适应度最佳的配置位串，最后得到最适 合当前环境和动作目的的硬件结构，即通过直接调整可编程逻辑器件的配置位 串，从而得到所需的最佳的硬件结构，以确保硬件结构一直处于最适合状态， 保持其能够实时高效地工作。

演化算法是一种具有鲁棒性的随机搜索优化算法，它通过模拟大自然的生 物进化过程，依据简单的遗传操作和优胜劣汰的自然选择法则来寻求问题的最 优解。演化算法具有适于高度并行与自组织、自学习、自适应等特征。一方面 当使用演化算法对实际问题进行求解时，算法可以利用演化过程中所获得的相 关信息自行地组织搜索行为。另一方面由于演化算法采用种群的方式组织进行 对最优解的搜索，从而能够对实际问题的解空间的多个区域同时进行搜索，因 此特别适合于大规模并行。

紧凑遗传算法(CGA，Compact Genetic Algorithm)是常用演化算法中的一 种，其使用概率变量来描述问题候选解空间。考虑到在实现演化硬件时，要求 演化算法消耗的运行时间更少，而通过软件来执行演化算法所需要的时间消耗 是很不理想的。因此，研究者开始考虑使用FPGA等硬件来执行演化算法。CGA 算法被提出的主要目的就是为了能够使演化算法更好地在硬件上执行。通过硬 件实现的CGA算法，大幅度降低了演化算法在运行时间的消耗上。同时由于使 用概率变量值来表示问题解空间，从而减少了硬件实现时所需的存储资源。

尽管CGA算法有着便于硬件实现的优点，但是它只适用于解决规律性较为 明显的简单问题，对于略为复杂的问题算法在演化过程中很容易发生局部收敛 现象。另外，在概率变量收敛之前，CGA算法经常会丢失所获得的优秀解。最 为关键的是，在使用CGA算法实现演化硬件时，由于其搜索能力不足、收敛速 度慢，导致所实现的演化硬件很难适用于实际应用的需求。

发明内容

为了解决背景技术中存在的上述技术问题，本发明提供了一种可增强硬件 配置结构位串的搜索能力、提高候选解空间的多样性、更快地获得高质量的最 优的硬件配置结构位串、大幅度地提高了收敛速度、减少得到最优的硬件电路 结构所需要的时间以及增强了实际演化硬件的实时性的基于趋向型紧凑遗传算 法的演化硬件实现方法。

本发明的技术解决方案是：本发明提供了一种基于趋向型紧凑遗传算法的 演化硬件实现方法，其特殊之处在于：所述基于趋向型紧凑遗传算法的演化硬 件实现方法包括以下步骤：

1)获取实际的可编程逻辑器件的配置参数；

2)将步骤1)所获取得到的实际的可编程逻辑器件的配置参数进行映射并 形成染色体个体；所述染色体个体是由实际问题解空间中的一个解映射得到的 二进制串；所述染色体个体Chromosome＝{chrom[1]，...，chrom[i]，...， chrom[L]}，每一代演化的最优染色体个体winner＝{winr[1]，...，winr[i]，...， winr[L]}，其中L表示染色体个体的长度，i的取值范围为[1，L]；

3)依据染色体个体所对应的演化电路的输入输出逻辑关系，计算当前染色 体个体的适应度值fitness；所述适应度值fitness表示当前的电路逻辑功能与实际 问题需求的电路逻辑功能之间的符合度；

4)根据步骤3)所获取得到的适应度值fitness的情况对演化是否终止进行判 断，若fitness等于零，则演化过程结束；若fitness不等于零，则继续执行步骤1)～ 步骤4)。

上述步骤2)的具体实现方式是：

2.1)对概率变量初始化；

2.2)获取最优的染色体个体winner；

2.3)进行敛趋势性判断以及概率变量更新；

2.4)进行变异操作；所述变异操作是指在染色体个体的编码串中，依据一 定的变异概率，使用某些等位基因的值来替换其中的变异点上的基因值，从而 形成新的染色体个体。

上述步骤2.1)的具体实现方式是：

2.1.1)令概率变量P＝{p[1]，p[2]，...，p[i]，...，p[L]}皆为0.5，所述概率变 量P的值表示染色体个体Chromosome中chrom[i]为1的概率，其中i的取值范围为 [1，L]；

2.1.2)依据概率变量P随机生成两个相互独立的初始化染色体个体 Chromosome_a和Chromosome_b，并将染色体个体Chromosome_a和 Chromosome_b送入首次演化过程。

上述步骤2.2)的具体实现方式是：

2.2.1)首先将演化当代的两个染色体个体Chromosome_a和Chromosome_b 进行比较，选择出两者中适应度值较好的染色体个体，作为当前的最优染色体 个体winner；

2.2.2)通过设定重采样周期，在演化过程中，每隔与周期相同代时，使用 与当前概率变量值无关的概率值P_samp重新采样，生成新的染色体个体 Chromosome_s，并且将其与当前的最优染色体个体winner进行比较，选取两者 中优秀的一方作为新的最优染色体个体winner。

上述步骤2.3)的具体实现方式是：

2.3.1)将最优染色体个体winner的每一位winr[i]进行反转；

2.3.2)比较每一位反转后的个体的适应度值fitness_w与原个体的适应度值 fitness_wn；

2.3.3)若fitness_w大于fitness_wn，则继续判断winr[i]的值，如果winr[i]进行 反转后的值为1，则通过增加步长et来更新p[i]；如果winr[i]进行反转后的值为0， 则通过减少步长et来更新p[i]；其中更新步长et等于1/N，N表示种群数目；若 fitness_w小于fitness_wn，则不进行相应的p[i]的更新操作，即p[i]保持不变。

上述步骤2.4)的具体实现方式是采用二进制编码实现或采用随机变异算子 实现。

上述步骤2.4)中实现方式是采用二进制编码来实现时，所述步骤2.4)的具 体实现方式是：对winr[i]的值及其概率变量值p[i]进行判断，若p[i]的值小于0.5 且winr[i]的值为1，则对该位变异，将其变为0；若p[i]的值大于等于0.5且winr[i] 的值为0，则对该位变异，将其变为1。

上述步骤2.4)中实现方式是采用随机变异算子来实现时，所述步骤2.4)的 具体实现方式是：选用随机变异模板，设定变异概率P_mode，通常在0.01～0.001 范围内取值，依概率生成随机变异模板mutatemode＝{mtmd[1]，...，mtmd[i]，...， mtmd[L]}，模板的长度与winner的长度相同，若mtmd[i]的值为1，则winr[i]发生 变异，即对该位进行取反操作。

上述步骤3)构造适应度的具体实现方式是：

$\mathrm{fitness}=\underset{j}{\Sigma }{[\mathrm{outputvalue}\left(j\right)-\mathrm{idealvalue}\left(j\right)]}^2$

其中，outputvalue表示当前演化电路的实际输出，idealvalue表示实际问题需 求的电路结构的输出，j表示实际问题需求的电路输出的数目。

本发明的优点是：

本发明提供了一种基于趋向型紧凑遗传算法(TCGA，Compact Genetic  Algorithm with Tendency)的演化硬件实现方法，该方法将实际可编程逻辑器件 的配置结构位串作为演化对象，具有更快更精确地获得实际硬件的最优配置位 串的优势，能够有效地提供演化硬件的实时性，该方法在保持了易于硬件实现 的优点的同时，能够有效地提高演化算法的收敛速度，是一种具有更强实时性 的演化硬件的实现方法。该方法增强了对于最优硬件配置结构位串的搜索能力， 并且提高了候选解空间的多样性；能够更快地获得高质量的最优的硬件配置结 构位串；大幅度地提高了收敛速度，减少了得到最优的硬件电路结构所需要的 时间；增强了实际演化硬件的实时性，具体而言，本发明的优点主要有：

1、引入了当前配置位串朝向最优配置位串的趋势性的判断，以促进概率变 量的更新能够在每一步都逐渐地接近最优配置位串。在每一代的演化过程中， 对于候选染色体个体的每一位，首先对其进行反转，然后判断比较每一位反转 后的个体与原个体之间的适应度值。当新个体的适应度值更大时，再判断反转 位的值，如果该位进行反转后的值为1，则通过增加1/N的步长来更新该位所对 应的概率变量值；如果该位进行反转后的值为0，则通过减少1/N的步长来更新 该位所对应的概率变量值。N表示演化的种群数目。依靠对于收敛趋势性的判断， 有效地指引了候选染色体个体的概率变量值的更新方向，使得候选染色体个体 能够更快地收敛到最优的硬件配置位串。

2、引入了改进的变异操作。传统的变异操作是随机性的，使用变异概率值 来控制变异操作。本发明在传统的随机变异方法的基础上，增加了新的变异步 骤，判断染色体个体的每一位的概率变量值决定是否对候选染色体个体执行变 异操作。其判断标准为，如果当前位的概率变量值大于0.5，且该位为0则对其进 行反转，为1则保持不变；否则，该位为1则对其进行反转，为0则保持不变。通 过引入改进的变异操作，能够以更大的机率得到更好的染色体个体，并且增加 了演化过程中种群的多样性，避免了局部收敛状况现象。

附图说明

图1是本发明所提供的实现方法的流程图。

具体实施方式

参见图1，本发明提供了一种基于趋向型紧凑遗传算法的演化硬件实现方 法，该方法包括以下步骤：

首先，将实际的可编程逻辑器件的配置参数映射为算法引擎所需的染色体 个体，染色体个体的编码方式使用二进制编码。染色体个体表示由实际问题解 空间中的一个解映射得到的二进制串。

令染色体个体Chromosome＝{chrom[1]，...，chrom[i]，...，chrom[L]}，每 一代演化的最优染色体个体winner＝{winr[1]，...，winr[i]，...，winr[L]}，其中 L表示染色体个体的长度，i的取值范围为[1，L]。

然后，依据染色体个体Chromosome所对应的演化电路的输入输出逻辑关系， 计算当前染色体个体Chromosome的适应度值fitness，适应度值fitness表示当前的 电路逻辑功能与实际问题需求的电路逻辑功能之间的符合度。

构造适应度计算函数如下：

$\mathrm{fitness}=\underset{j}{\Sigma }{[\mathrm{outputvalue}\left(j\right)-\mathrm{idealvalue}\left(j\right)]}^2$

其中，outputvalue表示当前演化电路的实际输出，idealvalue表示实际问题需 求的电路结构的输出，j表示实际问题需求的电路输出的数目。依照该构造函数， fitness的值越小，则当前染色体个体Chromosome所对应的电路结构就越接近实 际需求。当fitness等于零时，完全符合实际的电路逻辑功能需求。

根据适应度值fitness的情况，进行终止判断。终止准则为：若fitness等于零， 则演化过程结束；否则，继续演化过程。

下面对本发明中的算法引擎部分进行详细的描述。通过算法引擎部分，可 以对当前的染色体个体Chromosome进行操作，得到每一代演化中的最优染色体 个体winner，以便使得可编程逻辑器件的内部资源配置逐渐适应实际问题的电路 需求。

1、概率变量初始化

本发明中的算法引擎部分使用概率变量来描述实际问题的候选解空间，对 概率变量进行初始化，令概率变量P＝{p[1]，p[2]，...，p[i]，...，p[L]}皆为0.5， P的值表示染色体个体Chromosome中chrom[i]为1的概率，i的取值范围为[1，L]。 然后依据概率变量P随机生成两个相互独立的初始化染色体个体Chromosome_a 和Chromosome_b，并将其送入首次演化过程。由于采用概率变量P来表示种群， 能够极大地减少存储种群所需要的硬件资源，更加有利于算法的硬件实现。

2、对染色体个体Chromosome_a和Chromosome_b执行竞争操作

竞争操作首先将演化当代的两个染色体个体Chromosome_a和 Chromosome_b进行比较，选择出两者中适应度值较好的染色体个体，作为当前 的最优染色体个体winner。然后通过设定重采样周期，在演化过程中，每隔与周 期相同代时，使用与当前概率变量值无关的概率值P_samp重新采样，生成新的 染色体个体Chromosome_s，并且将其与当前的最优染色体个体winner进行比较， 选取两者中优秀的一方作为新的最优染色体个体winner。该方法使用染色体个体 的适应度的相对值作为评断标准，更加有利于适应度好的染色体个体的保留， 同时有助于避免在演化过程中陷入搜索的局部最优停滞。

3、收敛趋势性判断操作以及概率变量更新

收敛趋势性判断操作是本发明中的一个重点。在每一代的演化过程中，对 于最优染色体个体winner的每一位winr[i]，首先对winr[i]进行反转，然后比较每 一位反转后的个体的适应度值fitness_w与原个体的适应度值fitness_wn。若 fitness_w＞fitness_wn，再判断winr[i]的值，如果winr[i]进行反转后的值为1，则通 过增加步长et来更新p[i]；如果winr[i]进行反转后的值为0，则通过减少步长et来 更新p[i]。其中更新步长et等于1/N，N表示种群数目。依靠对于收敛趋势性的判 断，能够有效地指引候选染色体个体的概率变量值的更新方向，使得候选染色 体个体能够更快地收敛到最优解。

4、改进的变异操作

改进的变异操作是本发明中的另一个重点。变异操作是指在染色体个体的 编码串中，依据一定的变异概率，使用某些等位基因的值来替换其中的变异点 上的基因值，从而形成新的染色体个体。当采用二进制编码时，变异操作就是 将染色体个体在变异点上的0、1值进行取反操作。本发明在传统变异操作的基 础上，增加了结合当前的最优染色体个体winner的各个位winr[i]所对应的概率变 量值p[i]的情况来判断是否对winr[i]执行变异的操作步骤。首先对winr[i]的值及 其概率变量值p[i]进行判断，若p[i]的值小于0.5且winr[i]的值为1，则对该位变异， 将其变为0；若p[i]的值大于等于0.5且winr[i]的值为0，则对该位变异，将其变为 1。

使用传统的随机变异算子时，选用随机变异模板，设定变异概率P_mode， 通常在0.01～0.001范围内取值。

依概率生成随机变异模板mutatemode＝{mtmd[1]，...，mtmd[i]，...， mtmd[L]}，模板的长度与winner的长度相同，若mtmd[i]的值为1，则winr[i]发生 变异，即对该位进行取反操作。

变异操作的存在，有助于算法引擎跳出搜索的局部区域性，增大了每代演 化过程中的搜索范围，同时也扩展了候选解空间的多样性。

最后将演化结束后得到的最优的染色体个体winner转化为器件的内部资源 配置文件，下载该文件到可编程逻辑器件，从而实现符合实际问题需求的硬件 电路结构。

本发明中的收敛趋势性判断操作和改进的变异操作，不仅能够指引概率变 量的收敛方向，提高收敛速度，而且增强了对于可编程逻辑器件的最优配置位 串的搜索能力，扩展了候选解空间的多样性，更加有利于演化硬件中的现实应 用。