基于改进的遗传算法软硬件划分方法研究

小具有不确定性。为了保持外部群体大小不变，在实际操作过程中采用截断操作的办法防止边界解的遗失。其具体做法是：将Pi和P*i中所有的个体复制到P*i+1。如果P*i+1的群体大小超过了N*，利用截断操作减少|P*i+1|；如果P*i+1的群体大小少于N*，则用被支配个体填充P*i+1。

3 基于改进的遗传算法软硬件划分

SoC软硬件划分问题实际上可以看作一个求解多个目标的优化问题。其目标是在满足一定系统约束的前提下实现系统性能的最优化。基于改进的软硬件划分步骤如下：

步骤1：将待优化的SoC系统转化为数据流图DFG

步骤2：从IP库中调出数据流图中可实现每个任务节点的候选IP

步骤3：对个体进行整数编码初始化，形成群体P0

步骤4：对Pi中的每个个体进行性能评估，计算其执行时间、面积、功耗和成本

步骤5：适应度赋值

步骤6：合并Pi和P*i群体，对其进行Pareto排序，构造非支配集(NDS)。复制Pareto最优个体，即所得的非支配集，记做P*i+1

步骤7：判断结束条件是否满足，如果t>Gen，则进化结束，P*i+1为最终输出的非劣解，P*i+1中每个个体的实现方式即为候选的软硬件划分解。否则继续，转步骤8

步骤8：构造新群体。如果NDS<popsize，用分类方法构造新群体；如果NDS>popsize，用聚类方法构造新群体步骤9：对新群体执行遗传操作，操作的结果设为pi+l，令T=Pi+l；转步骤4

3．1 数据流图描述

数据流图DFG(Data Flow Graph)是一个包含顶点和边的有向无环图。DFG由节点和弧线构成，当一个DFG用来描述一个SoC系统时，其顶点通常用来表示一些功能单元，对应构成系统的软硬件部件；而弧则表示数据处理的顺序，或者说是顶点之间的数据依赖关系，如图3所示。

3．2 个体编码和遗传操作

在基于遗传算法的软硬件划分中，最常见的编码方法是二进制编码。通过二进制编码将数据流图的节点映射到位串空间0和1上，然后在位串空间进行遗传操作。一般用0表示该节点由软件实现，用l表示该节点由硬件实现。设IP核数目为20，每个节点编码长度为5，二进制编码的交叉变异情况如图3、图4所示。

在图3、图4的遗传操作过程中，有两个节点的个体{Xl，X2}的二进制编码长度为10，节点Xl、X2的编码取值范围均为[00000，l0011]，经过交叉和变异操作后，分别产生超出编码取值范围的无效个体{1011l，l0010}和{0llll，11010}。出于上述原因，本文采用整数向量编码的个体编码方案。该方法直接自然，避免了编码、解码的冗余，减轻了遗传算法的计算负担，提高了运算效率，能够更好地保持群体的多样性。

针对图3所示为目标对象，在交叉概率PC=0．62，变异概率Pm=0．02，种群大小sizePop=80，演化代数numGen=l00的条件下，通过Matlab遗传工具箱进行模拟仿真，得出仿真结果如图5所示。图5中群体均值随着迭代次数的增加逐渐收敛，说明基于小生境技术和精英保持策略的改进算法可以得到该优化问题的最优解。

4 结论

综上所述，在小生境技术的基础上引入精英保持策略和保持群体多样性的方法，即经过优化策略之后的算法，能够更好更快地搜索到最优解集，从而达到了加速算法收敛速度、并避免陷入局部最优的目的。