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

0 引言
    集成电路在过去30年的发展几乎完全遵循Moore定律，即集成电路的集成度每隔18个月就翻一番。现在集成电路的面积进一步减小，并获得更高的集成度。集成度增加的结果就是能集成越来越多的功能，甚至是一个完整的系统都能够被集成到单个芯片之中。这样原来由微处理器、协处理器和多块其他外围芯片组成的系统，可以集成在一块芯片内实现，这种一块芯片集成一个系统的技术，叫做系统集成芯片(SOC，System-On—Chip)技术。但是传统的系统设计面临着许多必须解决的矛盾问题，首先是系统高性能和低成本之间的矛盾；其次是系统复杂性与更新换代周期之间的矛盾。
    面对这种矛盾，一个可行的解决方案是采用SOC软硬件协同设计方法。而软硬件划分是软硬件协同设计方法的关键问题。软硬件划分问题是一个多目标优化问题，在优化过程中要针对成本、面积、功耗、时间等多个目标。现在已经有很多算法应用到软硬件划分中，如遗传算法、蚂蚁算法、禁忌搜索算法、模拟退火算法等。本文主要采用基于小生境技术(Niching Methods)和精英保持策略的改进遗传算法来进行软硬件划分研究。

l 遗传算法基本思想
    美国Michigan大学J．Holland教授于1975年提出的遗传算法，遗传算法是以达尔文的自然选择和优胜劣汰的生物进化理论为基础的。和传统的搜索算法不同，遗传算法从一组随机产生的成为种群(Population)的初始解开始搜索。种群中的每一个体都是问题的一个解，称为染色体，这些染色体在后续迭代中不断进化，称为遗传。在新一代形成中，根据适应值的大小选择部分后代，淘汰部分后代。经过若干代之后，算法收敛于最好的染色体，它可能是问题的最优解或近似最优解。图l是遗传算法基本的流程示意图。

    遗传算法有三类基本的操作：选择(Selection)、交叉(Crossover)、和变异(Mutation)。选择的目的是为了从当前群体中选出优良的个体，是它们有机会作为父代为下一代繁殖子孙，选择的原则是给予适应度强的个体较大的机会。交又是最主要的遗传算法操作，它同时对两个染色体进行操作，组合二者的特性产生新的后代，遗传算法的性能很大程度上取决于采用的交叉运算的性能。变异发生的概率最低，变异操作是在染色体上自发地产生随机变化，在遗传算法中变异可以提供初始种群中不包括的基因，为种群提供新的个体。
    遗传算法的主要优点是：1)具有领悟无关的群体性全局搜索能力，可避免陷入局部最优；2)搜索使用评价函数启发过程简单；3)使用概率机制进行迭代，具有随机性；4)可扩展性强，易于介入已有的模型中去，且易于与其他优化技术结合。

2 小生境技术和精英保持策略
2．1 小生境技术
    早熟收敛是遗传算法最严重的一个问题，保持群体的多样性可以有效地防止群体的早熟收敛，而且种群多样性也是遗传算法能够搜索全局最优解的基本条件。其中小生境(niching methods)技术是遗传算法维持种群多样性而广为采用的方法。在生物学中，小生境是指特定环境下的一种生存环境，相同的生物生活在同一个小生境中。借鉴此概念，遗传算法将每一代个体划分成若干类，每个类中选出若干适应度较高的个体作为一个类的优秀代表组成一个种群，再在种群中以及不同种群之间通过杂交、变异产生新一代个体群，同时采用预选择机制或者排挤机制或共享机制完成选择操作。这样就可以更好的保持群体的多样性，使其具有较高的全局寻优能力和收敛速度。遗传算法中模拟小生境的方法主要有以下几种：1)基于预选择的小生境实现方法；2)基于排挤的小生境实现方法；3)基于共享函数的小生境实现方法。
2．2 精英保持策略
    在遗传算法的运行过程中，通过对个体进行交叉、变异等遗传操作而不断地产生出新的个体。虽然随着群体的进化过程会产生出越来越多的优良个体，但是犹豫遗传算法的随机性，可能会破坏当前群体中的最好的个体。这将对遗传算法的有效性和收敛性都有很大影响。为了使适应度最好的个体能够保存到下一代群体中，本文使用精英保持策略(Elitlsm Preserving)来进行优胜劣汰，将当前群体中适应度最高的个体不参与交叉和变异运算，而是用它来替代当前代中适应度最低的个体。假设P，代表第i代的进化群体，则精英保持策略的操作示意如图2：

    如图2所示，精英保持策略的基本思想是对Pi进行非劣排序，在群体中挑出最优的个体保留到下一代Pi+1。这种保留通过在遗传操作外部维持一个辅助群体P*来实现。P*中个体的编码决策向量是所有解向量中的非被支配向量，即当前代的Pareto最优解。由于每代进化后的非支配向量大小是个不定量，外部群体P*的大小具有不确定性。为了保持外部群体大小不变，在实际操作过程中采用截断操作的办法防止边界解的遗失。其具体做法是：将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 结论
    综上所述，在小生境技术的基础上引入精英保持策略和保持群体多样性的方法，即经过优化策略之后的算法，能够更好更快地搜索到最优解集，从而达到了加速算法收敛速度、并避免陷入局部最优的目的。