一种保证质量的快速软硬件划分方法
一种保证质量的快速软硬件划分方法
【技术领域】
[0001] 本发明涉及计算机技术领域，具体涉及一种对嵌入式系统模型进行软硬件划分的 方法。
【背景技术】
[0002] 随着嵌入式系统与微电子技术的飞速发展，硬件的集成度越来越高，这使得将 CPU、存储器和I/O设备集成到一个硅片上成为可能，S0C应运而生，并以其集成度高、可靠性 好、产品问世周期短等特点逐步成为当前嵌入式系统设计技术的主流。
[0003] 针对嵌入式系统Soc设计面临的问题与挑战，研究者们开始探索新的设计方法 学--软硬件协同设计(Hardware/Software Co-Design)方法学。软硬件协同设计不仅是 一种设计技术，同时也是种新的设计方法学，其核心问题是协调软件子系统和硬件子系统。 与传统的嵌入式系统设计方法不同，软硬件协同设计强调软件和硬件设计开发的并行性和 相互反馈，如图1所示，克服了传统方法中把软件和硬件分开设计所带来的种种弊端，协调 软件和硬件之间的制约关系，达到系统高效工作的目的，软硬件协同设计提高了设计抽象 的层次，拓展了设计覆盖的范围。
[0004] 软硬件划分是软硬件协同设计中的一个关键技术。软硬件划分是指在系统设计过 程中，给每个功能模块分配一种实现方式，或者是硬件电路实现，或者是在通用处理器上用 软件代码实现。软件实现成本较低并且几乎不占用芯片面积，但速度较慢;而硬件实现速度 很快但会占用较大芯片面积并且成本较高。
[0005] 软硬件划分的目的是综合软件和硬件各自的优点，根据所设计的具体系统的特性 和用户对各种性能指标的要求，给出一个能兼顾各个属性并满足系统要求的分配方案。一 个好的划分方案可以减少资源的使用、降低系统的成本，为后面的设计与开发打好基础，而 要得到好的划分方案就必须有好的划分算法，划分算法性能不佳会导致开发周期的增加， 甚至影响整个开发过程。
[0006] 任务图用来对划分目标进行建模，任务图为一个有向无环图，它重点描述系统中 任务之间的数据、控制关系以及每个节点的参数信息，而与现实中系统采用的具体体系结 构无关。任务图的每个节点代表一个任务，节点的属性包含该任务分别用软件和硬件实现 所需的面积、时间、成本和功耗，任务图的每条有向边上有一个权值，表示与其相连的两个 节点采用不同实现方式时的通信功耗。对一个用任务图描述的嵌入式系进行软硬件划分的 例子如图2所示。
[0007] 启发式算法(Heuristic Algorithm)是相对于最优化算法提出的。一个问题的最 优算法求得该问题每个实例的最优解。启发式算法可以这样定义:一个基于直观或经验构 造的算法，在可接受的花费(指计算时间和空间）下给出待解决组合优化问题每一个实例的 一个可行解，该可行解与最优解的偏离程度一般不能被预计。
[0008] 遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机 理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算 法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定 数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要 载体，即多个基因的集合，其内部表现（即基因型)是某种基因组合，它决定了个体的形状的 外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一 开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，往 往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演 化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助 于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将 导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经 过解码，可以作为问题近似最优解。遗传算法整体流程如图3。然而，遗传算法存在耗时较长 的缺点。
[0009] 生物免疫系统是一个自适应和自组织的系统，具有强大的信息处理能力。生物免 疫系统的主要作用是能够辨别"自己"与"异己"物质，只对非自体成份的抗原作出免疫应 答，对"自体"成份形成免疫耐受，并具有排除与记忆非己的功能。而阴性选择算法是免疫系 统识别非自体，对自体形成自我耐受的关键所在，因此成为核心免疫算法之一，其性能对整 个免疫系统具有重要意义。阴性选择算法的一个主要优点就是在未知的状态下可以对非我 模式进行有效的防御。阴性选择算法整体流程如图4。然后，阴性选择算法结果随机性打、容 易陷入局部最优的缺点。
【发明内容】
[0010] 针对现有技术的不足，本发明旨在提供一种保证质量的快速软硬件划分方法，基 于遗传算法和阴性选择算法的软硬件划分方法来软硬件划分的速度以及提高最终划分方 案的质量和分布的广泛性。
[0011] 为了实现上述目的，本发明采用如下技术方案：
[0012] -种保证质量的快速软硬件划分方法，包括如下步骤：
[0013] S1给定一个描述嵌入式系统的任务图，首先进行参数和数据结构设置，包括自我 集self、自我集更新长度aSelf、自我集最小匹配长度bSelf、记录每个基因位上0的浓度的 数组(3〇11818七611〇6_0和记录每个基因位上1的浓度的数组〇〇11818七611〇6_1、交叉概率?〇和变 异概率Pm;
[0014] S2根据编码码长和当前进化代数更新自我集最小匹配长度bSelf;
[0015] S3产生一个新的种群，把个体每一位上0和1的等位基因浓度作为概率，随机设置 所有个体每一位上的值；
[0016] S4使用自我集对步骤S3中产生的种群进行阴性选择，把不满足条件的个体淘汰 掉，然后将上一代保留的优秀个体加入到种群中；
[0017] S5计算个体在每个子目标函数上的取值，并根据种群的整体状态更新种群中每个 个体的状态；
[0018] S6从种群中获取满足限制条件的有效解作为优秀个体保留；
[0019] S7使用带海明距离检测的均匀两点交叉算子对种群进行交叉运算；
[0020] S8使用考虑等位基因的多样性的变异算子对种群进行变异运算；
[0021] S9按照步骤S5对每个个体的状态进行更新，调整每一位的等位基因浓度，并根据 种群特性更新自我集；
[0022] S10判断是否达到最大进化代数，如果是，则退出；否则将当前进化代数加1并返回 步骤S2开始下一代进化，以寻找更好的解。
[0023]需要说明的是，所述步骤S1的具体方法如下：
[0024] 1.1)设置自我集更新长度aSelf为编码长度的二分之一；
[0025] 1.2)设置自我集最小匹配长度bSelf为编码长度的五分之一；
[0026] 1.3)设置各个基因位0和1的浓度默认值为5000;
[0027] 1.4)初始化自我集，把每一位都设置为2，当某一位为2时表示该位为空；
[0028] 1.5)设置交叉概率Pc和变异概率Pm。
[0029]需要说明的是，步骤S2中，具体按下式对自我集最小匹配长度bSelf进行更新：
[0031]其中L为编码长度，gen为当前进化代数，Maxgen为最大进化代数，η为一个用于调 整的参数。
[0032]需要说明的是，步骤S3的具体方法如下：
[0033] 3.1)产生一个新的种群，其中包括2L个新个体，L为编码长度，并初始化所有个体 的每一位为空；
[0034] 3.2)对于步骤3.1)中所得种群的所有个体，循环处理其中的每一位;其中，单个个 体的处理过程如下：
[0035] 3 · 2 · 1)对于当前位，产生一个随机数rd;
[0036] 3.2.2)计算该位上0的浓度除以0和1浓度之和的值proportion;
[0037] 3 · 2 · 3)如果在步骤3 · 2 · 1)中所得的rd小于在步骤3 · 2 · 3)计算所得的proportion， 则设置该位为〇;否则设置该位为1;
[0038] 3.2.4)判断是否所有位均被处理完毕，如果是，则结束当前个体的处理，并转至处 理下一个个体，否则转至下一位，并返回至步骤3.2.1);
[0039] 3.3)所有个体均按照步骤3.2.1)-3.2.4)的方法进行处理后，转至执行步骤S4。
[0040] 需要说明的是，步骤S4中的具体方法如下：
[0041] 4.1)对于步骤S3最终得到的种群，将其中的每一个个体分别与自我集进行按位比 较，得到每个个体中与自我集不相同的位的个数，即海明距离的d;
[0042] 4.2)对于每个个体，如果d小于自我集最小匹配长度bSelf，则把该个体从种群中 剔除，否则保留该个体；
[0043] 4.3)所有个体处理完毕后，将上一代保留的优秀个体加当前的种群中。
[0044] 需要说明的是，步骤S5中，每个个体的状态具体为个体在每个子目标函数上的值， 以及根据对这些子目标函数值进行排序后得到的等级而计算出的适应度值，所述子目标函 数包括面积函数、成本函数和功耗函数;所述步骤S5的具体方法如下：
[0045] 5.1)按下式计算并更新每个个体的面积：
[0047] 其中N为种群中个体的数量，对于种群中任意一个节点i，wi为节点i的实现方式， 值为〇代表软件实现，值为1代表硬件实现，AHHf表节点i用硬件实现时所占用的芯片面积， 用软件实现时占用芯片面积为〇;
[0048] 5.2)按下式计算并更新每个个体的成本：
[0050]其中Wi为节点i的实现方式，值为0代表软件实现，值为1代表硬件实现，CHi和CSi分 别代表节点i用硬件实现和用软件实现时的成本；
[0051 ] 5.3)对于每个个体，按如下公式计算并更新功耗：
[0053]其中，wi为节点i的实现方式，值为0代表软件实现，值为1代表硬件实现，PHi和PSi 分别代表节点i用硬件实现和用软件实现时的功耗，CPHjPCSHi分别为节点i用硬件实现时 与所有前驱节点和所有后继节点之间的通信功耗，CPSi和CSSi分别为 节点i用软件实现时与 所有前驱节点和所有后继节点之间的通信功耗；
[0054] 5.4)将种群中的个体根据子目标函数值进行排序并标记等级，排序依据为:对任 意两个个体，记为a，b，如果a在每个子目标函数上的值都小于或等于b在每个相应子目标函 数上的值，且a至少在一个子目标函数上的值小于b在相应子目标函数上的值，则称a可以支 配b;排序步骤如下：
[0055] 5.4.1)挑选出种群中所有不能被其他任何个体支配的个体，将它们的等级标记为 m，m的初始值设置为1;
[0056] 5.4.2)将步骤5.4.1)中被标记为等级m的个体从种群中暂时移出，放到临时空间 中；
[0057] 5.4.3)将m的值加1;如果还存在没有被标记等级的个体，则返回步骤5.4.1)，否则 转至执行步骤5.5);
[0058] 5.5)按如下公式计算并更新每一个个体的适应度值：
[0060]其中对于任意一个个体i，Ri为步骤5.4)中得到的个体i的等级。
[0061 ]需要说明的是，步骤S6的具体方法如下：
[0062] 对于每个个体，将步骤S5中计算得到的其在子目标函数上的取值与用户给出的相 应限制条件进行比较，如果其在所有目标函数值都在限制条件之内，则该个体为有效个体， 将其保留，否则淘汰。
[0063] 需要说明的是，所述步骤S7的具体方法如下：
[0064] 7.1)按如下公式计算交叉阈值：
[0066]其中CL为发生交叉操作的两个个体间的最小海明距离，g为当前代数，G为总的进 化代数，L为编码长度；
[0067] 7.2)将个体的顺序打乱；
[0068] 7.3)按打乱后的顺序每次选取两个个体并计算其海明距离；
[0069] 7.4)如果计算所得的海明距离小于阈值CL，则对应的两个个体不进行交叉，并返 回到步骤7.3)进行下两个个体的判断，否则转到步骤7.5);
[0070] 7.5)产生一个随机数rd，如果rd小于交叉概率Pc，则转至步骤7.6)，否则返回步骤 7.3) 进行下两个个体的判断；
[0071] 7.6)在0、1、2中随机选择一个数字记为c，并随机产生两个交叉点cl和c2,其中，cl <c2；
[0072] 7.7)如果c是0,则将两个个体的编码的从0到cl之间的部分交换;如果c是1，则将 两个个体的编码的从cl到c2之间的部分交换;如果c是2,则将两个个体的编码的从(：2到1^之 间的部分交换，其中，L为编码长度；
[0073] 7.8)判断是否所有个体都被处理过，如果是，则继续执行步骤S8,否则返回步骤 7.3) 继续处理。
[0074]需要说明的是，步骤S8中，需要对所有个体分别进行处理，而对于每一个个体，循 环处理其每一位;单个个体的处理方法具体如下：
[0075] 8.1)对于当前位，生成一个随机数rd;
[0076] 8.2)如果步骤8.1)中的随机数rd大于变异概率Pm，则不对该位进行变异，并转至 步骤8.3)，否则转至步骤8.4);
[0077] 8.3)判断是否所有位均被处理完毕，如果是，结束该个体的处理，并转至处理下一 个个体，否则转至下一位并返回执行步骤8.1);
[0078] 8.4)按如下公式求出该位的等位基因多样度：
[0080] 其中Si(j)表示个体i的基因在第j位上的值，Vi(j)表示个体i的第j位的等位基因 多样度;PopSize为种群规模，即所有等位基因的个数;某一位上的等位基因多样度即为在 该位上的数值与该位相同的个体个数在种群中所占比例；
[0081] 8.5)如果步骤8.4)计算得到的等位基因多样度大于阈值，则对该位进行变异，即 用1减去该位上的值，并用得到的值替换原有值；
[0082] 8.6)判断是否所有位均被处理完毕，如果是，结束该个体的处理，并转至处理下一 个个体，否则转至下一位并返回执行步骤8.1)。
[0083]需要说明的是，步骤S9的具体步骤如下：
[0084] 9.1)按步骤S5的方法更新每个个体的状态，并计算所有个体的平均适应度值avg;
[0085] 9.2)设置两个数组num_0和num_l，分别存储每个基因位上取0和取1的适应度值小 于a vg的个体的个数；
[0086] 9 · 3)清空保存优秀个体的数组GoodOnes;
[0087] 9.4)循环处理所有个体，单个个体i的处理方法如下：
[0088] 9.4.1)将其适应度值与平均适应度值avg进行比较，如果个体i适应度值大于avg， 则转步骤9.4.2)，否则转至步骤9.4.4);
[0089] 9.4.2)对个体i每一位进行判断，如果该位是1，则将记录等位基因浓度的数组 consistence」在这一位上的值加上该个体的适应度值;如果该位是0，则将记录等位基因 浓度的数组cons istence_0在这一位上的值加上该个体的适应度值；
[0090] 9.4.3)将个体i放入步骤9.3)中被清空的优秀个体数组GoodOnes中并结束个体i 的处理；
[0091] 9.4.4)对个体i每一位进行判断，如果该位是1，则将记录等位基因浓度的数组 consistence」在这一位上的值减去该个体的适应度值，并将num_l在这一位上的值加1;如 果该位是〇,则将记录等位基因浓度的数组consistence_0在这一位上的值减去该个体的适 应度值，并将num_0在这一位上的值加1;
[0092] 9.5)循环比较11111]1_0和11111]1_1的每一位，其中每一位的比较方法如下：
[0093] 9.5.1)求num_0和num_l在这一位上的差的绝对值，如果该绝对值大于自我集更新 长度aSelf，则自我集的这一位需要更新，否则转至步骤9.5.2);更新方法如下：
[0094] 如果num_0在当前位上的值大于num_l在当前位上的值，则设置自我集的当前位为 〇;否则置自我集的当前位为1;
[0095] 9.5.2)判断是否所有位均被处理完毕，如果是，则转至下一位并返回步骤9.5.1)， 否则结束处理。
[0096]本发明的有益效果在于:本发明保留遗传算法的交叉运算和变异运算，并引入阴 性选择算法的阴性选择过程和基于等位基因浓度来指导产生新个体的策略，采取了一种新 型的进化方法来加速进化的过程并保证个体的质量，这主要由于:遗传算法的选择运算过 程需要对所有个体按其适应度值进行排序，每一代进化都需要重复此排序过程，所以耗时 较长。本发明引入了阴性选择算法的阴性选择过程，仅需将个体与自我集按位比较，最后根 据相同位的个数按一定策略选择淘汰或留下，速度比排序过程快很多，因此代数越多加速 效果越明显。阴性选择算法虽然速度较快，但其得到的解集过度依赖于初始种群的状态，由 于初始种群是随机产生的，所以其得到的解集的质量也有较大随机性，而本发明使用了遗 传算法的交叉和变异运算，相应的增强了算法的全局搜索能力和局部搜索能力，从而使最 终得到的解集的质量得到保证。
【附图说明】
[0097]图1为软硬件协同设计流程；
[0098]图2为对任务图进行软硬件划分示意图；
[0099]图3为遗传算法整体流程；
[0100]图4为阴性选择算法整体流程；
[0101] 图5为本发明的算法流程。
【具体实施方式】
[0102] 以下将结合附图对本发明作进一步的描述，需要说明的是，本实施例以本技术方 案为前提，给出了详细的实施方式和具体的操作过程，但本发明的保护范围并不限于本实 施例。
[0103] 如图5所示，一种保证质量的快速软硬件划分方法，包括如下步骤：
[0104] S1给定一个描述嵌入式系统的任务图，首先进行参数和数据结构设置，包括自我 集self、自我集更新长度aSelf、自我集最小匹配长度bSelf、记录每个基因位上0的浓度的 数组(3〇11818七611〇6_0和记录每个基因位上1的浓度的数组〇〇11818七611〇6_1、交叉概率?〇和变 异概率Pm;
[0105] S2根据编码码长和当前进化代数更新自我集最小匹配长度bSelf;
[0106] S3产生一个新的种群，把个体每一位上0和1的等位基因浓度作为概率，随机设置 所有个体每一位上的值；
[0107] S4使用自我集对步骤S3中产生的种群进行阴性选择，把不满足条件的个体淘汰 掉，然后将上一代保留的优秀个体加入到种群中；
[0108] S5计算个体在各子目标函数上的取值，并根据种群的整体状态更新种群中每个个 体的状态；
[0109] S6从种群中获取满足限制条件的有效解作为优秀个体保留；
[0110] S7使用带海明距离检测的均匀两点交叉算子对种群进行交叉运算；
[0111] S8使用考虑等位基因的多样性的变异算子对种群进行变异运算；
[0112] S9按照步骤S5对每个个体的状态进行更新，调整每一位的等位基因浓度，并根据 种群特性更新自我集；
[0113] S10判断是否达到最大进化代数，如果是，则退出；否则将当前进化代数加1并返回 步骤S2开始下一代进化，以寻找更好的解。
[0114] 需要说明的是，所述步骤S1的具体方法如下：
[0115] 1.1)设置自我集更新长度aSelf为编码长度的二分之一；
[0116] 1.2)设置自我集最小匹配长度bSelf为编码长度的五分之一；
[0117] 1.3)设置各个基因位0和1的浓度默认值为5000;
[0118] 1.4)初始化自我集，把每一位都设置为2，当某一位为2时表示该位为空；
[0119] 1.5)设置交叉概率Pc和变异概率Pm。
[0120] 需要说明的是，步骤S2中，具体按下式对自我集最小匹配长度bSelf进行更新：
[0122] 其中L为编码长度，gen为当前进化代数，Maxgen为最大进化代数，η为一个用于调 整的参数。
[0123] 需要说明的是，步骤S3的具体方法如下：
[01 24] 3.1)产生一个新的种群，其中包括2L个新个体，L为编码长度，并初始化所有个体 的每一位为空；
[0125] 3.2)对于步骤3.1)中所得种群的所有个体，循环处理其中的每一位;其中，单个个 体的处理过程如下：
[0126] 3.2.1)对于当前位，产生一个随机数rd;
[0127] 3 · 2 · 2)计算该位上0的浓度除以0和1浓度之和的值proportion;
[ΟΙ28] 3 · 2 · 3)如果在步骤3 · 2 · 1)中所得的rd小于在步骤3 · 2 · 3)计算所得的proportion， 则设置该位为〇;否则设置该位为1;
[0129] 3.2.4)判断是否所有位均被处理完毕，如果是，则结束当前个体的处理，并转至处 理下一个个体，否则转至下一位，并返回至步骤3.2.1);
[0130] 3.3)所有个体均按照步骤3.2.1)-3.2.4)的方法进行处理后，转至执行步骤S4。
[0131]需要说明的是，步骤S4中的具体方法如下：
[0132] 4.1)对于步骤S3最终得到的种群，将其中的每一个个体分别与自我集进行按位比 较，得到每个个体中与自我集不相同的位的个数，即海明距离的d;
[0133] 4.2)对于每个个体，如果d小于自我集最小匹配长度bSelf，则把该个体从种群中 剔除，否则保留该个体；
[0134] 4.3)所有个体处理完毕后，将上一代保留的优秀个体加当前的种群中。
[0135] 需要说明的是，步骤S5中，每个个体的状态具体为个体在每个子目标函数上的值， 以及根据对这些子目标函数值进行排序后得到的等级而计算出的适应度值，所述子目标函 数包括面积函数、成本函数和功耗函数;所述步骤S5的具体方法如下：
[0136] 5.1)按下式计算并更新每个个体的面积：
[0138] 其中N为种群中个体的数量，对于种群中任意一个节点i，wi为节点i的实现方式， 值为〇代表软件实现，值为1代表硬件实现，AHHf表节点i用硬件实现时所占用的芯片面积， 用软件实现时占用芯片面积为〇;
[0139] 5.2)按下式计算并更新每个个体的成本：
[0141 ]其中Wi为节点i的实现方式，值为0代表软件实现，值为1代表硬件实现，CHi和CSi分 别代表节点i用硬件实现和用软件实现时的成本；
[0142] 5.3)对于每个个体，按如下公式计算并更新功耗：
[0144]其中，Wi为节点i的实现方式，值为0代表软件实现，值为1代表硬件实现，PHi和PSi 分别代表节点i用硬件实现和用软件实现时的功耗，CPHjPCSHi分别为节点i用硬件实现时 与所有前驱节点和所有后继节点之间的通信功耗，CPSi和CSSi分别为节点i用软件实现时与 所有前驱节点和所有后继节点之间的通信功耗；
[0145] 5.4)将种群中的个体根据子目标函数值进行排序并标记等级，排序依据为:对任 意两个个体，记为a，b，如果a在每个子目标函数上的值都小于或等于b在每个相应子目标函 数上的值，且a至少在一个子目标函数上的值小于b在相应子目标函数上的值，则称a可以支 配b;排序步骤如下：
[0146] 5.4.1)挑选出种群中所有不能被其他任何个体支配的个体，将它们的等级标记为 m，m的初始值设置为1;
[0147] 5.4.2)将步骤5.4.1)中被标记为等级m的个体从种群中暂时移出，放到临时空间 中；
[0148] 5.4.3)将m的值加1;如果还存在没有被标记等级的个体，则返回步骤5.4.1)，否则 转至执行步骤5.5);
[0149] 5.5)按如下公式计算并更新每一个个体的适应度值：
[0151 ]其中对于任意一个个体i，Ri为步骤5.4)中得到的个体i的等级。
[0152]需要说明的是，步骤S6的具体方法如下：
[0153]对于每个个体，将步骤S5中计算得到的其在子目标函数上的取值与用户给出的相 应限制条件进行比较，如果其在所有目标函数值都在限制条件之内，则该个体为有效个体， 将其保留，否则淘汰。
[0154]需要说明的是，所述步骤S7的具体方法如下：
[0155] 7.1)按如下公式计算交叉阈值：
[0157] 其中CL为发生交叉操作的两个个体间的最小海明距离，g为当前代数，G为总的进 化代数，L为编码长度；
[0158] 7.2)将个体的顺序打乱；
[0159] 7.3)按打乱后的顺序每次选取两个个体并计算其海明距离；
[0160] 7.4)如果计算所得的海明距离小于阈值CL，则对应的两个个体不进行交叉，并返 回到步骤7.3)进行下两个个体的判断，否则转到步骤7.5);
[0161] 7.5)产生一个随机数rd，如果rd小于交叉概率Pc，则转至步骤7.6)，否则返回步骤 7.3) 进行下两个个体的判断；
[0162] 7.6)在0、1、2中随机选择一个数字记为c，并随机产生两个交叉点cl和c2,其中，cl <c2；
[0163] 7.7)如果c是0,则将两个个体的编码的从0到cl之间的部分交换;如果c是1，则将 两个个体的编码的从cl到c2之间的部分交换;如果c是2,则将两个个体的编码的从(：2到1^之 间的部分交换，其中，L为编码长度；
[0164] 7.8)判断是否所有个体都被处理过，如果是，则继续执行步骤S8,否则返回步骤 7.3) 继续处理。
[0165] 需要说明的是，步骤S8中，需要对所有个体分别进行处理，而对于每一个个体，循 环处理其每一位;单个个体的处理方法具体如下：
[0166] 8.1)对于当前位，生成一个随机数rd;
[0167] 8.2)如果步骤8.1)中的随机数rd大于变异概率Pm，则不对该位进行变异，并转至 步骤8.3)，否则转至步骤8.4);
[0168] 8.3)判断是否所有位均被处理完毕，如果是，结束该个体的处理，并转至处理下一 个个体，否则转至下一位并返回执行步骤8.1);
[0169] 8.4)按如下公式求出该位的等位基因多样度：
[0171] 其中Si(j)表示个体i的基因在第j位上的值，Vdj)表示个体i的第j位的等位基因 多样度;PopSize为种群规模，即所有等位基因的个数;某一位上的等位基因多样度即为在 该位上的数值与该位相同的个体个数在种群中所占比例，例如，当第i个个体的第j位为0， 那么这一位的多样度就等于所有在这一位上为0的个体的个数占整个种群的比例。
[0172] 8.5)如果步骤8.4)计算得到的等位基因多样度大于阈值，则对该位进行变异，即 用1减去该位上的值，并用得到的值替换原有值;所述阈值可以取0.3;
[0173] 8.6)判断是否所有位均被处理完毕，如果是，结束该个体的处理，并转至处理下一 个个体，否则转至下一位并返回执行步骤8.1)。
[0174] 需要说明的是，步骤S9的具体步骤如下：
[0175] 9.1)按步骤S5的方法更新每个个体的状态，并计算所有个体的平均适应度值avg;
[0176] 9.2)设置两个数组11111]1_0和11111]1_1，分别存储每个基因位上取0和取1的适应度值小 于a vg的个体的个数；
[0177] 9.3)清空保存优秀个体的数组GoodOnes;
[0178] 9.4)循环处理所有个体，单个个体i的处理方法如下：
[0179] 9.4.1)将其适应度值与平均适应度值avg进行比较，如果个体i适应度值大于avg， 则转步骤9.4.2)，否则转至步骤9.4.4);
[0180] 9.4.2)对个体i每一位进行判断，如果该位是1，则将记录等位基因浓度的数组 consistence」在这一位上的值加上该个体的适应度值;如果该位是0，则将记录等位基因 浓度的数组cons istence_0在这一位上的值加上该个体的适应度值；
[0181 ] 9.4.3)将个体i放入步骤9.3)中被清空的优秀个体数组GoodOnes中并结束个体i 的处理；
[0182] 9.4.4)对个体i每一位进行判断，如果该位是1，则将记录等位基因浓度的数组 consistence」在这一位上的值减去该个体的适应度值，并将num_l在这一位上的值加1;如 果该位是〇,则将记录等位基因浓度的数组consistence_0在这一位上的值减去该个体的适 应度值，并将num_0在这一位上的值加1;
[0183] 9.5)循环比较11111]1_0和11111]1_1的每一位，其中每一位的比较方法如下：
[0184] 9.5.1)求num_0和num_l在这一位上的差的绝对值，如果该绝对值大于自我集更新 长度aSelf，则自我集的这一位需要更新，否则转至步骤9.5.2);更新方法如下：
[0185]如果num_0在当前位上的值大于num_l在当前位上的值，则设置自我集的当前位为 〇;否则置自我集的当前位为1;
[0186] 9.5.2)判断是否所有位均被处理完毕，如果是，则转至下一位并返回步骤9.5.1)， 否则结束处理。
[0187]对于本领域的技术人员来说，可以根据以上的技术方案和构思，作出各种相应的 改变和变形，而所有的这些改变和变形都应该包括在本发明权利要求的保护范围之内。
【主权项】
1. 一种保证质量的快速软硬件划分方法，其特征在于，包括如下步骤： Sl给定一个描述嵌入式系统的任务图，首先进行参数和数据结构设置，包括自我集 self、自我集更新长度aSelf、自我集最小匹配长度bSelf、记录每个基因位上O的浓度的数 组(3〇11818七611〇6_0和记录每个基因位上1的浓度的数组(3〇11818七611〇6_1、交叉概率?(3和变异 概率Pm; S2根据编码码长和当前进化代数更新自我集最小匹配长度bSelf; S3产生一个新的种群，把个体每一位上O和1的等位基因浓度作为概率，随机设置所有 个体每一位上的值； S4使用自我集对步骤S3中产生的种群进行阴性选择，把不满足条件的个体淘汰掉，然 后将上一代保留的优秀个体加入到种群中； S5计算个体 在每个子目标函数上的取值，并根据种群的整体状态更新种群中每个个体 的状态； S6从种群中获取满足限制条件的有效解作为优秀个体保留； S7使用带海明距离检测的均匀两点交叉算子对种群进行交叉运算； S8使用考虑等位基因的多样性的变异算子对种群进行变异运算； S9按照步骤S5对每个个体的状态进行更新，调整每一位的等位基因浓度，并根据种群 特性更新自我集； SlO判断是否达到最大进化代数，如果是，则退出；否则将当前进化代数加1并返回步骤 S2开始下一代进化，以寻找更好的解。2. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，所述步骤 Sl的具体方法如下： 1.1) 设置自我集更新长度aSelf为编码长度的二分之一； 1.2) 设置自我集最小匹配长度bSelf为编码长度的五分之一； 1.3) 设置各个基因位0和1的浓度默认值为5000; 1.4) 初始化自我集，把每一位都设置为2，当某一位为2时表示该位为空； 1.5) 设置交叉概率Pc和变异概率Pm。3. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，步骤S2 中，具体按下式对自我集最小匹配长度bSelf进行更新：其中L为编码长度，gen为当前进化代数，Maxgen为最大进化代数，η为一个用于调整的 参数。4. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，步骤S3的 具体方法如下： 3.1) 产生一个新的种群，其中包括2L个新个体，L为编码长度，并初始化所有个体的每 一位为空； 3.2) 对于步骤3.1)中所得种群的所有个体，循环处理其中的每一位;其中，单个个体的 处理过程如下： 3.2.1)对于当前位，产生一个随机数rd; 3.2.2) 计算该位上O的浓度除以O和1浓度之和的值proportion; 3.2.3) 如果在步骤3.2.1)中所得的rd小于在步骤3.2.3)计算所得的proportion，则设 置该位为0;否则设置该位为1; 3.2.4) 判断是否所有位均被处理完毕，如果是，则结束当前个体的处理，并转至处理下 一个个体，否则转至下一位，并返回至步骤3.2.1); 3.3)所有个体均按照步骤3.2.1 )-3.2.4)的方法进行处理后，转至执行步骤S4。5. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，步骤S4中 的具体方法如下： 4.1) 对于步骤S3最终得到的种群，将其中的每一个个体分别与自我集进行按位比较， 得到每个个体中与自我集不相同的位的个数，即海明距离的d; 4.2) 对于每个个体，如果d小于自我集最小匹配长度bSelf，则把该个体从种群中剔除， 否则保留该个体； 4.3) 所有个体处理完毕后，将上一代保留的优秀个体加当前的种群中。6. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，步骤S5 中，每个个体的状态具体为个体在每个子目标函数上的值，以及根据对这些子目标函数值 进行排序后得到的等级而计算出的适应度值，所述子目标函数包括面积函数、成本函数和 功耗函数;所述步骤S5的具体方法如下： 5.1) 按下式计算并更新每个个体的面积：其中N为种群中个体的数量，对于种群中任意一个节点i，wi为节点i的实现方式，值为0 代表软件实现，值为1代表硬件实现，AH1R表节点i用硬件实现时所占用的芯片面积，用软 件实现时占用芯片面积为〇; 5.2) 按下式计算并更新每个个体的成本：其中Wi为节点i的实现方式，值为0代表软件实现，值为1代表硬件实现，CHi和CSi分别代 表节点i用硬件实现和用软件实现时的成本； 5.3) 对于每个个体，按如下公式计算并更新功耗：其中，Wi为节点i的实现方式，值为0代表软件实现，值为1代表硬件实现，PHi和PSi分别 代表节点i用硬件实现和用软件实现时的功耗，CPHjPCSH1分别为节点i用硬件实现时与所 有前驱节点和所有后继节点之间的通信功耗，CPS i和CSSi分别为节点i用软件实现时与所有 前驱节点和所有后继节点之间的通信功耗； 5.4) 将种群中的个体根据子目标函数值进行排序并标记等级，排序依据为:对任意两 个个体，记为a，b，如果a在每个子目标函数上的值都小于或等于b在每个相应子目标函数上 的值，且a至少在一个子目标函数上的值小于b在相应子目标函数上的值，则称a可以支配k 排序步骤如下： 5.4.1) 挑选出种群中所有不能被其他任何个体支配的个体，将它们的等级标记为m，m 的初始值设置为1; 5.4.2) 将步骤5.4.1)中被标记为等级m的个体从种群中暂时移出，放到临时空间中； 5.4.3) 将m的值加1;如果种群中还存在没有被标记等级的个体，则返回步骤5.4.1)，否 则转至执行步骤5.5); 5.5)按如下公式计算并更新每一个个体的适应度值：其中对于任意一个个体i，Ri为步骤5.4)中得到的个体i的等级。7. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，步骤S6的 具体方法如下： 对于每个个体，将步骤S5中计算得到的其在子目标函数上的取值与用户给出的相应限 制条件进行比较，如果其在所有目标函数值都在限制条件之内，则该个体为有效个体，将其 保留，否则淘汰。8. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，所述步骤 S7的具体方法如下： 7.1) 按如下公式计算交叉阈值：其中CL为发生交叉操作的两个个体间的最小海明距离，g为当前代数，G为总的进化代 数，L为编码长度； 7.2) 将个体的顺序打乱； 7.3) 按打乱后的顺序每次选取两个个体并计算其海明距离； 7.4) 如果计算所得的海明距离小于阈值CL，则对应的两个个体不进行交叉，并返回到 步骤7.3)进行下两个个体的判断，否则转到步骤7.5); 7.5) 产生一个随机数rd，如果rd小于交叉概率Pc，则转至步骤7.6)，否则返回步骤7.3) 进行下两个个体的判断； 7.6) 在O、1、2中随机选择一个数字记为c，并随机产生两个交叉点c 1和c2，其中，c l〈c2; 7.7) 如果c是O，则将两个个体的编码的从O到cl之间的部分交换；如果c是1，则将两个 个体的编码的从cl到c2之间的部分交换;如果c是2,则将两个个体的编码的从c2到L之间的 部分交换，其中，L为编码长度； 7.8) 判断是否所有个体都被处理过，如果是，则继续执行步骤S8，否则返回步骤7.3)继 续处理。9. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，步骤S8 中，需要对所有个体分别进行处理，而对于每一个个体，循环处理其每一位;单个个体的处 理方法具体如下： 8.1) 对于当前位，生成一个随机数rd; 8.2) 如果步骤8.1)中的随机数rd大于变异概率Pm，则不对该位进行变异，并转至步骤 8.3)，否则转至步骤8.4); 8.3) 判断是否所有位均被处理完毕，如果是，结束该个体的处理，并转至处理下一个个 体，否则转至下一位并返回执行步骤8.1); 8.4) 按如下公式求出该位的等位基因多样度：其中S1(J)表示个体i的基因在第j位上的值，V1(J)表示个体i的第j位的等位基因多样 度;PopSize为种群规模，即所有等位基因的个数;某一位上的等位基因多样度即为在该位 上的数值与该位相同的个体个数在种群中所占比例； 8.5) 如果步骤8.4)计算得到的等位基因多样度大于阈值，则对该位进行变异，即用1减 去该位上的值，并用得到的值替换原有值； 8.6) 判断是否所有位均被处理完毕，如果是，结束该个体的处理，并转至处理下一个个 体，否则转至下一位并返回执行步骤8.1)。10.根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，步骤S9 的具体步骤如下： 9.1) 按步骤S5的方法更新每个个体的状态，并计算所有个体的平均适应度值avg; 9.2) 设置两个数组1111111_0和1111111_1，分别存储每个基因位上取0和取1的适应度值小于 a vg的个体的个数； 9.3) 清空保存优秀个体的数组GoodOnes; 9.4) 循环处理所有个体，单个个体i的处理方法如下： 9.4.1) 将其适应度值与平均适应度值avg进行比较，如果个体i适应度值大于avg，则转 步骤9.4.2)，否则转至步骤9.4.4); 9.4.2) 对个体i每一位进行判断，如果该位是1，则将记录等位基因浓度的数组 consistence」在这一位上的值加上该个体的适应度值;如果该位是0，则将记录等位基因 浓度的数组cons istence_0在这一位上的值加上该个体的适应度值； 9.4.3) 将个体i放入步骤9.3)中被清空的优秀个体数组GoodOnes中并结束个体i的处 理； 9.4.4) 对个体i每一位进行判断，如果该位是1，则将记录等位基因浓度的数组 consistence」在这一位上的值减去该个体的适应度值，并将num_l在这一位上的值加1;如 果该位是〇,则将记录等位基因浓度的数组consistence_0在这一位上的值减去该个体的适 应度值，并将num_0在这一位上的值加1; 9.5)循环比较num_0和num_ 1的每一位，其中每一位的比较方法如下： 9.5.1)求num_0和num_l在这一位上的差的绝对值，如果该绝对值大于自我集更新长度 aSelf，则自我集的这一位需要更新，否则转至步骤9.5.2);更新方法如下： 如果num_0在当前位上的值大于numj在当前位上的值，则设置自我集的当前位为0;否 则置自我集的当前位为I; 9.5.2)判断是否所有位均被处理完毕，如果是，则转至下一位并返回步骤9.5.1 )，否则 结束处理。
【专利摘要】本发明公开了一种保证质量的快速软硬件划分方法，保留遗传算法的交叉运算和变异运算，并引入阴性选择算法的阴性选择过程和基于等位基因浓度来指导产生新个体的策略，采取一种新型的进化方法来加速进化的过程并保证个体的质量，从而克服传统遗传算法耗时长以及阴性选择算法结果随机性大、容易陷入局部最优的缺点。
【IPC分类】G06N3/12, G06F9/44
【公开号】CN105487873
【申请号】CN201510884819
【发明人】段振华, 李炳岩, 张南, 黄伯虎, 田聪, 王小兵
【申请人】西安电子科技大学
【公开日】2016年4月13日
【申请日】2015年12月4日
【技术领域】
[0001] 本发明涉及计算机技术领域，具体涉及一种对嵌入式系统模型进行软硬件划分的 方法。
【背景技术】
[0002] 随着嵌入式系统与微电子技术的飞速发展，硬件的集成度越来越高，这使得将 CPU、存储器和I/O设备集成到一个硅片上成为可能，S0C应运而生，并以其集成度高、可靠性 好、产品问世周期短等特点逐步成为当前嵌入式系统设计技术的主流。
[0003] 针对嵌入式系统Soc设计面临的问题与挑战，研究者们开始探索新的设计方法 学--软硬件协同设计(Hardware/Software Co-Design)方法学。软硬件协同设计不仅是 一种设计技术，同时也是种新的设计方法学，其核心问题是协调软件子系统和硬件子系统。 与传统的嵌入式系统设计方法不同，软硬件协同设计强调软件和硬件设计开发的并行性和 相互反馈，如图1所示，克服了传统方法中把软件和硬件分开设计所带来的种种弊端，协调 软件和硬件之间的制约关系，达到系统高效工作的目的，软硬件协同设计提高了设计抽象 的层次，拓展了设计覆盖的范围。
[0004] 软硬件划分是软硬件协同设计中的一个关键技术。软硬件划分是指在系统设计过 程中，给每个功能模块分配一种实现方式，或者是硬件电路实现，或者是在通用处理器上用 软件代码实现。软件实现成本较低并且几乎不占用芯片面积，但速度较慢;而硬件实现速度 很快但会占用较大芯片面积并且成本较高。
[0005] 软硬件划分的目的是综合软件和硬件各自的优点，根据所设计的具体系统的特性 和用户对各种性能指标的要求，给出一个能兼顾各个属性并满足系统要求的分配方案。一 个好的划分方案可以减少资源的使用、降低系统的成本，为后面的设计与开发打好基础，而 要得到好的划分方案就必须有好的划分算法，划分算法性能不佳会导致开发周期的增加， 甚至影响整个开发过程。
[0006] 任务图用来对划分目标进行建模，任务图为一个有向无环图，它重点描述系统中 任务之间的数据、控制关系以及每个节点的参数信息，而与现实中系统采用的具体体系结 构无关。任务图的每个节点代表一个任务，节点的属性包含该任务分别用软件和硬件实现 所需的面积、时间、成本和功耗，任务图的每条有向边上有一个权值，表示与其相连的两个 节点采用不同实现方式时的通信功耗。对一个用任务图描述的嵌入式系进行软硬件划分的 例子如图2所示。
[0007] 启发式算法(Heuristic Algorithm)是相对于最优化算法提出的。一个问题的最 优算法求得该问题每个实例的最优解。启发式算法可以这样定义:一个基于直观或经验构 造的算法，在可接受的花费(指计算时间和空间）下给出待解决组合优化问题每一个实例的 一个可行解，该可行解与最优解的偏离程度一般不能被预计。
[0008] 遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机 理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算 法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定 数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要 载体，即多个基因的集合，其内部表现（即基因型)是某种基因组合，它决定了个体的形状的 外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一 开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，往 往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演 化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助 于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将 导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经 过解码，可以作为问题近似最优解。遗传算法整体流程如图3。然而，遗传算法存在耗时较长 的缺点。
[0009] 生物免疫系统是一个自适应和自组织的系统，具有强大的信息处理能力。生物免 疫系统的主要作用是能够辨别"自己"与"异己"物质，只对非自体成份的抗原作出免疫应 答，对"自体"成份形成免疫耐受，并具有排除与记忆非己的功能。而阴性选择算法是免疫系 统识别非自体，对自体形成自我耐受的关键所在，因此成为核心免疫算法之一，其性能对整 个免疫系统具有重要意义。阴性选择算法的一个主要优点就是在未知的状态下可以对非我 模式进行有效的防御。阴性选择算法整体流程如图4。然后，阴性选择算法结果随机性打、容 易陷入局部最优的缺点。
【发明内容】
[0010] 针对现有技术的不足，本发明旨在提供一种保证质量的快速软硬件划分方法，基 于遗传算法和阴性选择算法的软硬件划分方法来软硬件划分的速度以及提高最终划分方 案的质量和分布的广泛性。
[0011] 为了实现上述目的，本发明采用如下技术方案：
[0012] -种保证质量的快速软硬件划分方法，包括如下步骤：
[0013] S1给定一个描述嵌入式系统的任务图，首先进行参数和数据结构设置，包括自我 集self、自我集更新长度aSelf、自我集最小匹配长度bSelf、记录每个基因位上0的浓度的 数组(3〇11818七611〇6_0和记录每个基因位上1的浓度的数组〇〇11818七611〇6_1、交叉概率?〇和变 异概率Pm;
[0014] S2根据编码码长和当前进化代数更新自我集最小匹配长度bSelf;
[0015] S3产生一个新的种群，把个体每一位上0和1的等位基因浓度作为概率，随机设置 所有个体每一位上的值；
[0016] S4使用自我集对步骤S3中产生的种群进行阴性选择，把不满足条件的个体淘汰 掉，然后将上一代保留的优秀个体加入到种群中；
[0017] S5计算个体在每个子目标函数上的取值，并根据种群的整体状态更新种群中每个 个体的状态；
[0018] S6从种群中获取满足限制条件的有效解作为优秀个体保留；
[0019] S7使用带海明距离检测的均匀两点交叉算子对种群进行交叉运算；
[0020] S8使用考虑等位基因的多样性的变异算子对种群进行变异运算；
[0021] S9按照步骤S5对每个个体的状态进行更新，调整每一位的等位基因浓度，并根据 种群特性更新自我集；
[0022] S10判断是否达到最大进化代数，如果是，则退出；否则将当前进化代数加1并返回 步骤S2开始下一代进化，以寻找更好的解。
[0023]需要说明的是，所述步骤S1的具体方法如下：
[0024] 1.1)设置自我集更新长度aSelf为编码长度的二分之一；
[0025] 1.2)设置自我集最小匹配长度bSelf为编码长度的五分之一；
[0026] 1.3)设置各个基因位0和1的浓度默认值为5000;
[0027] 1.4)初始化自我集，把每一位都设置为2，当某一位为2时表示该位为空；
[0028] 1.5)设置交叉概率Pc和变异概率Pm。
[0029]需要说明的是，步骤S2中，具体按下式对自我集最小匹配长度bSelf进行更新：
[0031]其中L为编码长度，gen为当前进化代数，Maxgen为最大进化代数，η为一个用于调 整的参数。
[0032]需要说明的是，步骤S3的具体方法如下：
[0033] 3.1)产生一个新的种群，其中包括2L个新个体，L为编码长度，并初始化所有个体 的每一位为空；
[0034] 3.2)对于步骤3.1)中所得种群的所有个体，循环处理其中的每一位;其中，单个个 体的处理过程如下：
[0035] 3 · 2 · 1)对于当前位，产生一个随机数rd;
[0036] 3.2.2)计算该位上0的浓度除以0和1浓度之和的值proportion;
[0037] 3 · 2 · 3)如果在步骤3 · 2 · 1)中所得的rd小于在步骤3 · 2 · 3)计算所得的proportion， 则设置该位为〇;否则设置该位为1;
[0038] 3.2.4)判断是否所有位均被处理完毕，如果是，则结束当前个体的处理，并转至处 理下一个个体，否则转至下一位，并返回至步骤3.2.1);
[0039] 3.3)所有个体均按照步骤3.2.1)-3.2.4)的方法进行处理后，转至执行步骤S4。
[0040] 需要说明的是，步骤S4中的具体方法如下：
[0041] 4.1)对于步骤S3最终得到的种群，将其中的每一个个体分别与自我集进行按位比 较，得到每个个体中与自我集不相同的位的个数，即海明距离的d;
[0042] 4.2)对于每个个体，如果d小于自我集最小匹配长度bSelf，则把该个体从种群中 剔除，否则保留该个体；
[0043] 4.3)所有个体处理完毕后，将上一代保留的优秀个体加当前的种群中。
[0044] 需要说明的是，步骤S5中，每个个体的状态具体为个体在每个子目标函数上的值， 以及根据对这些子目标函数值进行排序后得到的等级而计算出的适应度值，所述子目标函 数包括面积函数、成本函数和功耗函数;所述步骤S5的具体方法如下：
[0045] 5.1)按下式计算并更新每个个体的面积：
[0047] 其中N为种群中个体的数量，对于种群中任意一个节点i，wi为节点i的实现方式， 值为〇代表软件实现，值为1代表硬件实现，AHHf表节点i用硬件实现时所占用的芯片面积， 用软件实现时占用芯片面积为〇;
[0048] 5.2)按下式计算并更新每个个体的成本：
[0050]其中Wi为节点i的实现方式，值为0代表软件实现，值为1代表硬件实现，CHi和CSi分 别代表节点i用硬件实现和用软件实现时的成本；
[0051 ] 5.3)对于每个个体，按如下公式计算并更新功耗：
[0053]其中，wi为节点i的实现方式，值为0代表软件实现，值为1代表硬件实现，PHi和PSi 分别代表节点i用硬件实现和用软件实现时的功耗，CPHjPCSHi分别为节点i用硬件实现时 与所有前驱节点和所有后继节点之间的通信功耗，CPSi和CSSi分别为 节点i用软件实现时与 所有前驱节点和所有后继节点之间的通信功耗；
[0054] 5.4)将种群中的个体根据子目标函数值进行排序并标记等级，排序依据为:对任 意两个个体，记为a，b，如果a在每个子目标函数上的值都小于或等于b在每个相应子目标函 数上的值，且a至少在一个子目标函数上的值小于b在相应子目标函数上的值，则称a可以支 配b;排序步骤如下：
[0055] 5.4.1)挑选出种群中所有不能被其他任何个体支配的个体，将它们的等级标记为 m，m的初始值设置为1;
[0056] 5.4.2)将步骤5.4.1)中被标记为等级m的个体从种群中暂时移出，放到临时空间 中；
[0057] 5.4.3)将m的值加1;如果还存在没有被标记等级的个体，则返回步骤5.4.1)，否则 转至执行步骤5.5);
[0058] 5.5)按如下公式计算并更新每一个个体的适应度值：
[0060]其中对于任意一个个体i，Ri为步骤5.4)中得到的个体i的等级。
[0061 ]需要说明的是，步骤S6的具体方法如下：
[0062] 对于每个个体，将步骤S5中计算得到的其在子目标函数上的取值与用户给出的相 应限制条件进行比较，如果其在所有目标函数值都在限制条件之内，则该个体为有效个体， 将其保留，否则淘汰。
[0063] 需要说明的是，所述步骤S7的具体方法如下：
[0064] 7.1)按如下公式计算交叉阈值：
[0066]其中CL为发生交叉操作的两个个体间的最小海明距离，g为当前代数，G为总的进 化代数，L为编码长度；
[0067] 7.2)将个体的顺序打乱；
[0068] 7.3)按打乱后的顺序每次选取两个个体并计算其海明距离；
[0069] 7.4)如果计算所得的海明距离小于阈值CL，则对应的两个个体不进行交叉，并返 回到步骤7.3)进行下两个个体的判断，否则转到步骤7.5);
[0070] 7.5)产生一个随机数rd，如果rd小于交叉概率Pc，则转至步骤7.6)，否则返回步骤 7.3) 进行下两个个体的判断；
[0071] 7.6)在0、1、2中随机选择一个数字记为c，并随机产生两个交叉点cl和c2,其中，cl <c2；
[0072] 7.7)如果c是0,则将两个个体的编码的从0到cl之间的部分交换;如果c是1，则将 两个个体的编码的从cl到c2之间的部分交换;如果c是2,则将两个个体的编码的从(：2到1^之 间的部分交换，其中，L为编码长度；
[0073] 7.8)判断是否所有个体都被处理过，如果是，则继续执行步骤S8,否则返回步骤 7.3) 继续处理。
[0074]需要说明的是，步骤S8中，需要对所有个体分别进行处理，而对于每一个个体，循 环处理其每一位;单个个体的处理方法具体如下：
[0075] 8.1)对于当前位，生成一个随机数rd;
[0076] 8.2)如果步骤8.1)中的随机数rd大于变异概率Pm，则不对该位进行变异，并转至 步骤8.3)，否则转至步骤8.4);
[0077] 8.3)判断是否所有位均被处理完毕，如果是，结束该个体的处理，并转至处理下一 个个体，否则转至下一位并返回执行步骤8.1);
[0078] 8.4)按如下公式求出该位的等位基因多样度：
[0080] 其中Si(j)表示个体i的基因在第j位上的值，Vi(j)表示个体i的第j位的等位基因 多样度;PopSize为种群规模，即所有等位基因的个数;某一位上的等位基因多样度即为在 该位上的数值与该位相同的个体个数在种群中所占比例；
[0081] 8.5)如果步骤8.4)计算得到的等位基因多样度大于阈值，则对该位进行变异，即 用1减去该位上的值，并用得到的值替换原有值；
[0082] 8.6)判断是否所有位均被处理完毕，如果是，结束该个体的处理，并转至处理下一 个个体，否则转至下一位并返回执行步骤8.1)。
[0083]需要说明的是，步骤S9的具体步骤如下：
[0084] 9.1)按步骤S5的方法更新每个个体的状态，并计算所有个体的平均适应度值avg;
[0085] 9.2)设置两个数组num_0和num_l，分别存储每个基因位上取0和取1的适应度值小 于a vg的个体的个数；
[0086] 9 · 3)清空保存优秀个体的数组GoodOnes;
[0087] 9.4)循环处理所有个体，单个个体i的处理方法如下：
[0088] 9.4.1)将其适应度值与平均适应度值avg进行比较，如果个体i适应度值大于avg， 则转步骤9.4.2)，否则转至步骤9.4.4);
[0089] 9.4.2)对个体i每一位进行判断，如果该位是1，则将记录等位基因浓度的数组 consistence」在这一位上的值加上该个体的适应度值;如果该位是0，则将记录等位基因 浓度的数组cons istence_0在这一位上的值加上该个体的适应度值；
[0090] 9.4.3)将个体i放入步骤9.3)中被清空的优秀个体数组GoodOnes中并结束个体i 的处理；
[0091] 9.4.4)对个体i每一位进行判断，如果该位是1，则将记录等位基因浓度的数组 consistence」在这一位上的值减去该个体的适应度值，并将num_l在这一位上的值加1;如 果该位是〇,则将记录等位基因浓度的数组consistence_0在这一位上的值减去该个体的适 应度值，并将num_0在这一位上的值加1;
[0092] 9.5)循环比较11111]1_0和11111]1_1的每一位，其中每一位的比较方法如下：
[0093] 9.5.1)求num_0和num_l在这一位上的差的绝对值，如果该绝对值大于自我集更新 长度aSelf，则自我集的这一位需要更新，否则转至步骤9.5.2);更新方法如下：
[0094] 如果num_0在当前位上的值大于num_l在当前位上的值，则设置自我集的当前位为 〇;否则置自我集的当前位为1;
[0095] 9.5.2)判断是否所有位均被处理完毕，如果是，则转至下一位并返回步骤9.5.1)， 否则结束处理。
[0096]本发明的有益效果在于:本发明保留遗传算法的交叉运算和变异运算，并引入阴 性选择算法的阴性选择过程和基于等位基因浓度来指导产生新个体的策略，采取了一种新 型的进化方法来加速进化的过程并保证个体的质量，这主要由于:遗传算法的选择运算过 程需要对所有个体按其适应度值进行排序，每一代进化都需要重复此排序过程，所以耗时 较长。本发明引入了阴性选择算法的阴性选择过程，仅需将个体与自我集按位比较，最后根 据相同位的个数按一定策略选择淘汰或留下，速度比排序过程快很多，因此代数越多加速 效果越明显。阴性选择算法虽然速度较快，但其得到的解集过度依赖于初始种群的状态，由 于初始种群是随机产生的，所以其得到的解集的质量也有较大随机性，而本发明使用了遗 传算法的交叉和变异运算，相应的增强了算法的全局搜索能力和局部搜索能力，从而使最 终得到的解集的质量得到保证。
【附图说明】
[0097]图1为软硬件协同设计流程；
[0098]图2为对任务图进行软硬件划分示意图；
[0099]图3为遗传算法整体流程；
[0100]图4为阴性选择算法整体流程；
[0101] 图5为本发明的算法流程。
【具体实施方式】
[0102] 以下将结合附图对本发明作进一步的描述，需要说明的是，本实施例以本技术方 案为前提，给出了详细的实施方式和具体的操作过程，但本发明的保护范围并不限于本实 施例。
[0103] 如图5所示，一种保证质量的快速软硬件划分方法，包括如下步骤：
[0104] S1给定一个描述嵌入式系统的任务图，首先进行参数和数据结构设置，包括自我 集self、自我集更新长度aSelf、自我集最小匹配长度bSelf、记录每个基因位上0的浓度的 数组(3〇11818七611〇6_0和记录每个基因位上1的浓度的数组〇〇11818七611〇6_1、交叉概率?〇和变 异概率Pm;
[0105] S2根据编码码长和当前进化代数更新自我集最小匹配长度bSelf;
[0106] S3产生一个新的种群，把个体每一位上0和1的等位基因浓度作为概率，随机设置 所有个体每一位上的值；
[0107] S4使用自我集对步骤S3中产生的种群进行阴性选择，把不满足条件的个体淘汰 掉，然后将上一代保留的优秀个体加入到种群中；
[0108] S5计算个体在各子目标函数上的取值，并根据种群的整体状态更新种群中每个个 体的状态；
[0109] S6从种群中获取满足限制条件的有效解作为优秀个体保留；
[0110] S7使用带海明距离检测的均匀两点交叉算子对种群进行交叉运算；
[0111] S8使用考虑等位基因的多样性的变异算子对种群进行变异运算；
[0112] S9按照步骤S5对每个个体的状态进行更新，调整每一位的等位基因浓度，并根据 种群特性更新自我集；
[0113] S10判断是否达到最大进化代数，如果是，则退出；否则将当前进化代数加1并返回 步骤S2开始下一代进化，以寻找更好的解。
[0114] 需要说明的是，所述步骤S1的具体方法如下：
[0115] 1.1)设置自我集更新长度aSelf为编码长度的二分之一；
[0116] 1.2)设置自我集最小匹配长度bSelf为编码长度的五分之一；
[0117] 1.3)设置各个基因位0和1的浓度默认值为5000;
[0118] 1.4)初始化自我集，把每一位都设置为2，当某一位为2时表示该位为空；
[0119] 1.5)设置交叉概率Pc和变异概率Pm。
[0120] 需要说明的是，步骤S2中，具体按下式对自我集最小匹配长度bSelf进行更新：
[0122] 其中L为编码长度，gen为当前进化代数，Maxgen为最大进化代数，η为一个用于调 整的参数。
[0123] 需要说明的是，步骤S3的具体方法如下：
[01 24] 3.1)产生一个新的种群，其中包括2L个新个体，L为编码长度，并初始化所有个体 的每一位为空；
[0125] 3.2)对于步骤3.1)中所得种群的所有个体，循环处理其中的每一位;其中，单个个 体的处理过程如下：
[0126] 3.2.1)对于当前位，产生一个随机数rd;
[0127] 3 · 2 · 2)计算该位上0的浓度除以0和1浓度之和的值proportion;
[ΟΙ28] 3 · 2 · 3)如果在步骤3 · 2 · 1)中所得的rd小于在步骤3 · 2 · 3)计算所得的proportion， 则设置该位为〇;否则设置该位为1;
[0129] 3.2.4)判断是否所有位均被处理完毕，如果是，则结束当前个体的处理，并转至处 理下一个个体，否则转至下一位，并返回至步骤3.2.1);
[0130] 3.3)所有个体均按照步骤3.2.1)-3.2.4)的方法进行处理后，转至执行步骤S4。
[0131]需要说明的是，步骤S4中的具体方法如下：
[0132] 4.1)对于步骤S3最终得到的种群，将其中的每一个个体分别与自我集进行按位比 较，得到每个个体中与自我集不相同的位的个数，即海明距离的d;
[0133] 4.2)对于每个个体，如果d小于自我集最小匹配长度bSelf，则把该个体从种群中 剔除，否则保留该个体；
[0134] 4.3)所有个体处理完毕后，将上一代保留的优秀个体加当前的种群中。
[0135] 需要说明的是，步骤S5中，每个个体的状态具体为个体在每个子目标函数上的值， 以及根据对这些子目标函数值进行排序后得到的等级而计算出的适应度值，所述子目标函 数包括面积函数、成本函数和功耗函数;所述步骤S5的具体方法如下：
[0136] 5.1)按下式计算并更新每个个体的面积：
[0138] 其中N为种群中个体的数量，对于种群中任意一个节点i，wi为节点i的实现方式， 值为〇代表软件实现，值为1代表硬件实现，AHHf表节点i用硬件实现时所占用的芯片面积， 用软件实现时占用芯片面积为〇;
[0139] 5.2)按下式计算并更新每个个体的成本：
[0141 ]其中Wi为节点i的实现方式，值为0代表软件实现，值为1代表硬件实现，CHi和CSi分 别代表节点i用硬件实现和用软件实现时的成本；
[0142] 5.3)对于每个个体，按如下公式计算并更新功耗：
[0144]其中，Wi为节点i的实现方式，值为0代表软件实现，值为1代表硬件实现，PHi和PSi 分别代表节点i用硬件实现和用软件实现时的功耗，CPHjPCSHi分别为节点i用硬件实现时 与所有前驱节点和所有后继节点之间的通信功耗，CPSi和CSSi分别为节点i用软件实现时与 所有前驱节点和所有后继节点之间的通信功耗；
[0145] 5.4)将种群中的个体根据子目标函数值进行排序并标记等级，排序依据为:对任 意两个个体，记为a，b，如果a在每个子目标函数上的值都小于或等于b在每个相应子目标函 数上的值，且a至少在一个子目标函数上的值小于b在相应子目标函数上的值，则称a可以支 配b;排序步骤如下：
[0146] 5.4.1)挑选出种群中所有不能被其他任何个体支配的个体，将它们的等级标记为 m，m的初始值设置为1;
[0147] 5.4.2)将步骤5.4.1)中被标记为等级m的个体从种群中暂时移出，放到临时空间 中；
[0148] 5.4.3)将m的值加1;如果还存在没有被标记等级的个体，则返回步骤5.4.1)，否则 转至执行步骤5.5);
[0149] 5.5)按如下公式计算并更新每一个个体的适应度值：
[0151 ]其中对于任意一个个体i，Ri为步骤5.4)中得到的个体i的等级。
[0152]需要说明的是，步骤S6的具体方法如下：
[0153]对于每个个体，将步骤S5中计算得到的其在子目标函数上的取值与用户给出的相 应限制条件进行比较，如果其在所有目标函数值都在限制条件之内，则该个体为有效个体， 将其保留，否则淘汰。
[0154]需要说明的是，所述步骤S7的具体方法如下：
[0155] 7.1)按如下公式计算交叉阈值：
[0157] 其中CL为发生交叉操作的两个个体间的最小海明距离，g为当前代数，G为总的进 化代数，L为编码长度；
[0158] 7.2)将个体的顺序打乱；
[0159] 7.3)按打乱后的顺序每次选取两个个体并计算其海明距离；
[0160] 7.4)如果计算所得的海明距离小于阈值CL，则对应的两个个体不进行交叉，并返 回到步骤7.3)进行下两个个体的判断，否则转到步骤7.5);
[0161] 7.5)产生一个随机数rd，如果rd小于交叉概率Pc，则转至步骤7.6)，否则返回步骤 7.3) 进行下两个个体的判断；
[0162] 7.6)在0、1、2中随机选择一个数字记为c，并随机产生两个交叉点cl和c2,其中，cl <c2；
[0163] 7.7)如果c是0,则将两个个体的编码的从0到cl之间的部分交换;如果c是1，则将 两个个体的编码的从cl到c2之间的部分交换;如果c是2,则将两个个体的编码的从(：2到1^之 间的部分交换，其中，L为编码长度；
[0164] 7.8)判断是否所有个体都被处理过，如果是，则继续执行步骤S8,否则返回步骤 7.3) 继续处理。
[0165] 需要说明的是，步骤S8中，需要对所有个体分别进行处理，而对于每一个个体，循 环处理其每一位;单个个体的处理方法具体如下：
[0166] 8.1)对于当前位，生成一个随机数rd;
[0167] 8.2)如果步骤8.1)中的随机数rd大于变异概率Pm，则不对该位进行变异，并转至 步骤8.3)，否则转至步骤8.4);
[0168] 8.3)判断是否所有位均被处理完毕，如果是，结束该个体的处理，并转至处理下一 个个体，否则转至下一位并返回执行步骤8.1);
[0169] 8.4)按如下公式求出该位的等位基因多样度：
[0171] 其中Si(j)表示个体i的基因在第j位上的值，Vdj)表示个体i的第j位的等位基因 多样度;PopSize为种群规模，即所有等位基因的个数;某一位上的等位基因多样度即为在 该位上的数值与该位相同的个体个数在种群中所占比例，例如，当第i个个体的第j位为0， 那么这一位的多样度就等于所有在这一位上为0的个体的个数占整个种群的比例。
[0172] 8.5)如果步骤8.4)计算得到的等位基因多样度大于阈值，则对该位进行变异，即 用1减去该位上的值，并用得到的值替换原有值;所述阈值可以取0.3;
[0173] 8.6)判断是否所有位均被处理完毕，如果是，结束该个体的处理，并转至处理下一 个个体，否则转至下一位并返回执行步骤8.1)。
[0174] 需要说明的是，步骤S9的具体步骤如下：
[0175] 9.1)按步骤S5的方法更新每个个体的状态，并计算所有个体的平均适应度值avg;
[0176] 9.2)设置两个数组11111]1_0和11111]1_1，分别存储每个基因位上取0和取1的适应度值小 于a vg的个体的个数；
[0177] 9.3)清空保存优秀个体的数组GoodOnes;
[0178] 9.4)循环处理所有个体，单个个体i的处理方法如下：
[0179] 9.4.1)将其适应度值与平均适应度值avg进行比较，如果个体i适应度值大于avg， 则转步骤9.4.2)，否则转至步骤9.4.4);
[0180] 9.4.2)对个体i每一位进行判断，如果该位是1，则将记录等位基因浓度的数组 consistence」在这一位上的值加上该个体的适应度值;如果该位是0，则将记录等位基因 浓度的数组cons istence_0在这一位上的值加上该个体的适应度值；
[0181 ] 9.4.3)将个体i放入步骤9.3)中被清空的优秀个体数组GoodOnes中并结束个体i 的处理；
[0182] 9.4.4)对个体i每一位进行判断，如果该位是1，则将记录等位基因浓度的数组 consistence」在这一位上的值减去该个体的适应度值，并将num_l在这一位上的值加1;如 果该位是〇,则将记录等位基因浓度的数组consistence_0在这一位上的值减去该个体的适 应度值，并将num_0在这一位上的值加1;
[0183] 9.5)循环比较11111]1_0和11111]1_1的每一位，其中每一位的比较方法如下：
[0184] 9.5.1)求num_0和num_l在这一位上的差的绝对值，如果该绝对值大于自我集更新 长度aSelf，则自我集的这一位需要更新，否则转至步骤9.5.2);更新方法如下：
[0185]如果num_0在当前位上的值大于num_l在当前位上的值，则设置自我集的当前位为 〇;否则置自我集的当前位为1;
[0186] 9.5.2)判断是否所有位均被处理完毕，如果是，则转至下一位并返回步骤9.5.1)， 否则结束处理。
[0187]对于本领域的技术人员来说，可以根据以上的技术方案和构思，作出各种相应的 改变和变形，而所有的这些改变和变形都应该包括在本发明权利要求的保护范围之内。
【主权项】
1. 一种保证质量的快速软硬件划分方法，其特征在于，包括如下步骤： Sl给定一个描述嵌入式系统的任务图，首先进行参数和数据结构设置，包括自我集 self、自我集更新长度aSelf、自我集最小匹配长度bSelf、记录每个基因位上O的浓度的数 组(3〇11818七611〇6_0和记录每个基因位上1的浓度的数组(3〇11818七611〇6_1、交叉概率?(3和变异 概率Pm; S2根据编码码长和当前进化代数更新自我集最小匹配长度bSelf; S3产生一个新的种群，把个体每一位上O和1的等位基因浓度作为概率，随机设置所有 个体每一位上的值； S4使用自我集对步骤S3中产生的种群进行阴性选择，把不满足条件的个体淘汰掉，然 后将上一代保留的优秀个体加入到种群中； S5计算个体 在每个子目标函数上的取值，并根据种群的整体状态更新种群中每个个体 的状态； S6从种群中获取满足限制条件的有效解作为优秀个体保留； S7使用带海明距离检测的均匀两点交叉算子对种群进行交叉运算； S8使用考虑等位基因的多样性的变异算子对种群进行变异运算； S9按照步骤S5对每个个体的状态进行更新，调整每一位的等位基因浓度，并根据种群 特性更新自我集； SlO判断是否达到最大进化代数，如果是，则退出；否则将当前进化代数加1并返回步骤 S2开始下一代进化，以寻找更好的解。2. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，所述步骤 Sl的具体方法如下： 1.1) 设置自我集更新长度aSelf为编码长度的二分之一； 1.2) 设置自我集最小匹配长度bSelf为编码长度的五分之一； 1.3) 设置各个基因位0和1的浓度默认值为5000; 1.4) 初始化自我集，把每一位都设置为2，当某一位为2时表示该位为空； 1.5) 设置交叉概率Pc和变异概率Pm。3. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，步骤S2 中，具体按下式对自我集最小匹配长度bSelf进行更新：其中L为编码长度，gen为当前进化代数，Maxgen为最大进化代数，η为一个用于调整的 参数。4. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，步骤S3的 具体方法如下： 3.1) 产生一个新的种群，其中包括2L个新个体，L为编码长度，并初始化所有个体的每 一位为空； 3.2) 对于步骤3.1)中所得种群的所有个体，循环处理其中的每一位;其中，单个个体的 处理过程如下： 3.2.1)对于当前位，产生一个随机数rd; 3.2.2) 计算该位上O的浓度除以O和1浓度之和的值proportion; 3.2.3) 如果在步骤3.2.1)中所得的rd小于在步骤3.2.3)计算所得的proportion，则设 置该位为0;否则设置该位为1; 3.2.4) 判断是否所有位均被处理完毕，如果是，则结束当前个体的处理，并转至处理下 一个个体，否则转至下一位，并返回至步骤3.2.1); 3.3)所有个体均按照步骤3.2.1 )-3.2.4)的方法进行处理后，转至执行步骤S4。5. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，步骤S4中 的具体方法如下： 4.1) 对于步骤S3最终得到的种群，将其中的每一个个体分别与自我集进行按位比较， 得到每个个体中与自我集不相同的位的个数，即海明距离的d; 4.2) 对于每个个体，如果d小于自我集最小匹配长度bSelf，则把该个体从种群中剔除， 否则保留该个体； 4.3) 所有个体处理完毕后，将上一代保留的优秀个体加当前的种群中。6. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，步骤S5 中，每个个体的状态具体为个体在每个子目标函数上的值，以及根据对这些子目标函数值 进行排序后得到的等级而计算出的适应度值，所述子目标函数包括面积函数、成本函数和 功耗函数;所述步骤S5的具体方法如下： 5.1) 按下式计算并更新每个个体的面积：其中N为种群中个体的数量，对于种群中任意一个节点i，wi为节点i的实现方式，值为0 代表软件实现，值为1代表硬件实现，AH1R表节点i用硬件实现时所占用的芯片面积，用软 件实现时占用芯片面积为〇; 5.2) 按下式计算并更新每个个体的成本：其中Wi为节点i的实现方式，值为0代表软件实现，值为1代表硬件实现，CHi和CSi分别代 表节点i用硬件实现和用软件实现时的成本； 5.3) 对于每个个体，按如下公式计算并更新功耗：其中，Wi为节点i的实现方式，值为0代表软件实现，值为1代表硬件实现，PHi和PSi分别 代表节点i用硬件实现和用软件实现时的功耗，CPHjPCSH1分别为节点i用硬件实现时与所 有前驱节点和所有后继节点之间的通信功耗，CPS i和CSSi分别为节点i用软件实现时与所有 前驱节点和所有后继节点之间的通信功耗； 5.4) 将种群中的个体根据子目标函数值进行排序并标记等级，排序依据为:对任意两 个个体，记为a，b，如果a在每个子目标函数上的值都小于或等于b在每个相应子目标函数上 的值，且a至少在一个子目标函数上的值小于b在相应子目标函数上的值，则称a可以支配k 排序步骤如下： 5.4.1) 挑选出种群中所有不能被其他任何个体支配的个体，将它们的等级标记为m，m 的初始值设置为1; 5.4.2) 将步骤5.4.1)中被标记为等级m的个体从种群中暂时移出，放到临时空间中； 5.4.3) 将m的值加1;如果种群中还存在没有被标记等级的个体，则返回步骤5.4.1)，否 则转至执行步骤5.5); 5.5)按如下公式计算并更新每一个个体的适应度值：其中对于任意一个个体i，Ri为步骤5.4)中得到的个体i的等级。7. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，步骤S6的 具体方法如下： 对于每个个体，将步骤S5中计算得到的其在子目标函数上的取值与用户给出的相应限 制条件进行比较，如果其在所有目标函数值都在限制条件之内，则该个体为有效个体，将其 保留，否则淘汰。8. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，所述步骤 S7的具体方法如下： 7.1) 按如下公式计算交叉阈值：其中CL为发生交叉操作的两个个体间的最小海明距离，g为当前代数，G为总的进化代 数，L为编码长度； 7.2) 将个体的顺序打乱； 7.3) 按打乱后的顺序每次选取两个个体并计算其海明距离； 7.4) 如果计算所得的海明距离小于阈值CL，则对应的两个个体不进行交叉，并返回到 步骤7.3)进行下两个个体的判断，否则转到步骤7.5); 7.5) 产生一个随机数rd，如果rd小于交叉概率Pc，则转至步骤7.6)，否则返回步骤7.3) 进行下两个个体的判断； 7.6) 在O、1、2中随机选择一个数字记为c，并随机产生两个交叉点c 1和c2，其中，c l〈c2; 7.7) 如果c是O，则将两个个体的编码的从O到cl之间的部分交换；如果c是1，则将两个 个体的编码的从cl到c2之间的部分交换;如果c是2,则将两个个体的编码的从c2到L之间的 部分交换，其中，L为编码长度； 7.8) 判断是否所有个体都被处理过，如果是，则继续执行步骤S8，否则返回步骤7.3)继 续处理。9. 根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，步骤S8 中，需要对所有个体分别进行处理，而对于每一个个体，循环处理其每一位;单个个体的处 理方法具体如下： 8.1) 对于当前位，生成一个随机数rd; 8.2) 如果步骤8.1)中的随机数rd大于变异概率Pm，则不对该位进行变异，并转至步骤 8.3)，否则转至步骤8.4); 8.3) 判断是否所有位均被处理完毕，如果是，结束该个体的处理，并转至处理下一个个 体，否则转至下一位并返回执行步骤8.1); 8.4) 按如下公式求出该位的等位基因多样度：其中S1(J)表示个体i的基因在第j位上的值，V1(J)表示个体i的第j位的等位基因多样 度;PopSize为种群规模，即所有等位基因的个数;某一位上的等位基因多样度即为在该位 上的数值与该位相同的个体个数在种群中所占比例； 8.5) 如果步骤8.4)计算得到的等位基因多样度大于阈值，则对该位进行变异，即用1减 去该位上的值，并用得到的值替换原有值； 8.6) 判断是否所有位均被处理完毕，如果是，结束该个体的处理，并转至处理下一个个 体，否则转至下一位并返回执行步骤8.1)。10.根据权利要求1所述的一种保证质量的快速软硬件划分方法，其特征在于，步骤S9 的具体步骤如下： 9.1) 按步骤S5的方法更新每个个体的状态，并计算所有个体的平均适应度值avg; 9.2) 设置两个数组1111111_0和1111111_1，分别存储每个基因位上取0和取1的适应度值小于 a vg的个体的个数； 9.3) 清空保存优秀个体的数组GoodOnes; 9.4) 循环处理所有个体，单个个体i的处理方法如下： 9.4.1) 将其适应度值与平均适应度值avg进行比较，如果个体i适应度值大于avg，则转 步骤9.4.2)，否则转至步骤9.4.4); 9.4.2) 对个体i每一位进行判断，如果该位是1，则将记录等位基因浓度的数组 consistence」在这一位上的值加上该个体的适应度值;如果该位是0，则将记录等位基因 浓度的数组cons istence_0在这一位上的值加上该个体的适应度值； 9.4.3) 将个体i放入步骤9.3)中被清空的优秀个体数组GoodOnes中并结束个体i的处 理； 9.4.4) 对个体i每一位进行判断，如果该位是1，则将记录等位基因浓度的数组 consistence」在这一位上的值减去该个体的适应度值，并将num_l在这一位上的值加1;如 果该位是〇,则将记录等位基因浓度的数组consistence_0在这一位上的值减去该个体的适 应度值，并将num_0在这一位上的值加1; 9.5)循环比较num_0和num_ 1的每一位，其中每一位的比较方法如下： 9.5.1)求num_0和num_l在这一位上的差的绝对值，如果该绝对值大于自我集更新长度 aSelf，则自我集的这一位需要更新，否则转至步骤9.5.2);更新方法如下： 如果num_0在当前位上的值大于numj在当前位上的值，则设置自我集的当前位为0;否 则置自我集的当前位为I; 9.5.2)判断是否所有位均被处理完毕，如果是，则转至下一位并返回步骤9.5.1 )，否则 结束处理。
【专利摘要】本发明公开了一种保证质量的快速软硬件划分方法，保留遗传算法的交叉运算和变异运算，并引入阴性选择算法的阴性选择过程和基于等位基因浓度来指导产生新个体的策略，采取一种新型的进化方法来加速进化的过程并保证个体的质量，从而克服传统遗传算法耗时长以及阴性选择算法结果随机性大、容易陷入局部最优的缺点。
【IPC分类】G06N3/12, G06F9/44
【公开号】CN105487873
【申请号】CN201510884819
【发明人】段振华, 李炳岩, 张南, 黄伯虎, 田聪, 王小兵
【申请人】西安电子科技大学
【公开日】2016年4月13日
【申请日】2015年12月4日
最新回复(0)