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

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*的大