基于改进蚁群算法的嵌入式系统软硬件划分
潘颖 阮文惠
摘 要： 针对标准蚁群算法的软硬件划分问题求解难题，提出改进蚁群算法的系统软硬件划分方法。首先分析了当前嵌入式系统软硬件划分研究的现状，并构建软硬件划分的数学模型；然后采用蚁群算法模拟蚂蚁觅食行为搜索数学模型的最优解，并引入逆反馈机制提高蚁群算法的搜索性能；最后通过实验证明软硬件划分问题求解的有效性。实验结果表明，改进蚁群算法提高了问题求解的效率，获得了合理的软硬件划分结果，且结果优于标准蚁群算法。
关键词： 硬件系统； 蚁群算法； 软件系统； 收敛速度； 仿真测试
中图分类号： TN919?34； TP181 文献标识码： A 文章编号： 1004?373X（2017）03?0164?03
Embedded system hardware and software partition
based on improved ant colony algorithm
PAN Ying， RUAN Wenhui
（School of Digital Media， Lanzhou University of Arts and Science， Lanzhou 730030， China）
Abstract： Since it is hard for the standard ant colony algorithm to solve the software and hardware partition problem， the hardware and software partition method based on the improved ant colony algorithm is proposed. The research status of the embedded system hardware and software partition is analyzed. The mathematical model of the hardware and software partition was constructed. The ant colony algorithm is used to simulate the foraging behavior of ants to search the optimal solution of the mathematical model. The inverse feedback mechanism is introduced to improve the search performance of the ant colony algorithm. The solving validity of the hardware and software partition problem was proved by means of experiments. The results show that the improved ant colony algorithm has improved the efficiency of problem solving， and obtained the reasonable hardware and software partition result， which is better than the result of the standard ant colony algorithm.
Keywords： hardware system； ant colony algorithm； software system； convergence speed； simulation test
0 引 言
随着计算机技术和微电子技术的不断成熟，嵌入式系统的应用范围更加广泛[1]。嵌入式系统包括硬件系统和软件系统两部分，以前由于硬件成本高，价格高，软件系统占的比例大。近几年，随着集成技术的发展，硬件价格急剧下降，出现了硬件系统和软件系统平分天下的格局[2]。硬件系统和软件系统均有各自的优势，对于一个嵌入式系统，如何对硬件系统和软件系统进行准确划分，降低系统的成本，同时保证系统满足實际要求，成为人们关注的焦点[3?4]。
自嵌入式系统出现以后，很多机构和大学专门成立了嵌入式软硬件系统划分研究团队，提出了许多有效的嵌入式软硬件划分算法[5]。最原始的方法为整数规划算法，工作灵活，可以适应不同类型的嵌入式系统，但整数规划算法的嵌入式软硬件系统划分问题求解时间长、速度慢，不能满足嵌入式系统软硬件划分的效率[6]。随后有学者提出了基于迭代算法的嵌入式软硬件划分方法，但同样存在求解效率低的缺陷[7]。大量研究结果表明，嵌入式软硬件系统划分是一个限制条件多的NP难题，出现了基于遗传算法的软硬件划分算法、基于免疫算法的软硬件划分算法、基于蚁群算法的软硬件划分算法[8?10]。有学者对三种算法的优劣进行比较，发现基于蚁群算法的软硬件划分算法性能最优，然而标准蚁群算法存在收敛速度慢等不足，在嵌入式系统软硬件划分问题求解范围受限[11]。
为了对嵌入式系统软硬件进行精确划分，降低系统成本，针对标准蚁群算法在软硬件划分问题求解过程存在的难题，提出了改进蚁群算法的系统软硬件划分方法，通过实验证明该方法在软硬件划分问题上求解的有效性。
1 改进蚁群算法
1.1 标准蚁群算法
蚁群一共包含有[m]只蚂蚁，它们分布于[n]个节点上，不同蚂蚁下一次移动选择节点的概率不同，该节点没有被访问过，并且对路径上信息素浓度进行更新。
节点选择的条件为：节点[i]和[j]的路径信息素浓度为[τij；]节点[i]转移到[j]的启发信息为[ηij，]它们的值根据具体问题进行设置。在[t]时刻，蚂蚁[k]从节点[i]选择节点[j]为目的地的概率为：
[pkijt=ταijtηβijj∈Nkiταijtηβij] （1）
式中：[Nki]表示蚂蚁[k]可以选择的节点；[α]表示残留信息权值；[β]表示启发信息的重要程度。
在蚁群移动的过程中，为了不让残留信息对启发信息产生干扰，蚂蚁经过全部节点后，需要更新残留信息浓度，使部分信息素挥发，同时将最新访问节点信息加入到[τij，]即有：
[τijt+n=ρτijt+k=1mΔτkij] （2）
式中：[ρ]表示信息素的挥發程度；[Δτkij]表示残留信息素的浓度。
1.2 标准蚁群算法的不足以及改进
在标准蚁群算法的工作中，蚂蚁的数目固定不变，只有正反馈过程，不能实现逆反馈过程，导致算法的收敛速度慢，工作效率低。为了解决标准蚁群算法存在的不足，设计了逆反馈过程，引入一个阈值[ε，]当循环相遇蚂蚁的数量小于[ε，]就按标准蚁群算法进行工作，反之，相遇蚂蚁路径上的信息素均要进行更新，改进蚁群算法的具体工作流程如图1所示。
1.3 改进蚁群算法的有效性测试
为了比较改进蚁群算法（IACO）和标准蚁群算法（ACO）的优越性，选择两个Sphere和Rosenbrock测试执行速度和求解精度，结果见图2。对图2的变化曲线进行分析可以发现，IACO的迭代次数显著减少，计算时间复杂度明显下降，提高了蚁群搜索问题解的速度，而且得到更高的精度结果，这说明本文引入逆反馈过程可以获得更优的蚁群算法。
2 改进蚁群算法的嵌入式系统软硬件划分
2.1 软硬件问题的数学模型
嵌入式系统的软硬件功能可以用DAG表示，[V]表示节点的集合，且任务[i]满足条件：[vi∈V，][E]表示边的集合，且有[ei=vi，vj∈V，]采用“0”和“1”分别表示嵌入式系统的软件系统和硬件系统，那么节点的DAG具体如图3所示。
嵌入式系统软硬件划分的节点之间通信开销[cvi，vj]和的数学模型[12]为：
[cp（vi），vi=vj∈p（vi）c（vj，vi），由软件完成maxvj∈p（vi）c（vj，vi），由硬件完成 ] （3）
式中[p（vi）]表示[vi]的全部前驱节点。
相应的约束条件为：
[minTvends.t. i=1nphixi+psi（-xi）≤Pi=1nahixi≤Ahi=1nasi（-xi）≤Asxi∈Z] （4）
2.2 软硬件划分问题的求解
（1） 对具体的嵌入式系统软硬件问题进行分析，建立数学模型。
（2） 对改进蚁群算法的参数进行设置，并初始化蚁群。
（3） 将所有蚂蚁平均分配到嵌入式系统软硬件构成的DAG节点上。
（4） 根据式（1）计算每一只蚂蚁选择下一个节点的概率，并且从转移到的该节点上建立每只蚂蚁的转移路径。
（5） 对全部蚂蚁转移路径进行分析，看是否有相遇的蚂蚁，若有将相遇的蚂蚁，则将它们的路径取作为一条新路径。
（6） 根据阈值评价相遇蚂蚁的数目，为每一只蚂蚁建立自己的路径。
（7） 根据阈值判断结果进行信息素更新操作。在每次循环时，信息素浓度不能超过范围[τmin，τmax，]不然采用式（3）进行强制设置。
[τij=τmin，τij≤τminτmax，τij≥τmax] （5）
（8） 根据蚁群的最优路径得到嵌入式系统软硬件划分的最佳方案。
3 仿真实验的结果与分析
为了测试改进蚁群算法的嵌入式系统软硬件划分方法的有效性，选择粒子群算法（PSO）[13]的嵌入式系统软硬件划分方法进行仿真对比测试。
在不同节点数目的条件下，采用Matlab 2014R编程进行模拟测试，两种方法的嵌入式系统面积变化曲线如图4所示。从图4可以看出，随着节点数目的增加，两种嵌入式系统软硬件划分方法设计系统的面积随之增大，改进蚁群算法的面积要小于粒子群算法，说明改进蚁群算法的嵌入式系统的集成度更高，有效降低了嵌入式系统的功耗。
在不同节点数目的条件下，两种方法对嵌入式软硬件划分问题求解的时间变化曲线如图5所示。从图5可以看出，随着节点数目的增加，改进蚁群算法和粒子群算法的执行时间也延长，在相同条件下，改进蚁群算法的执行时间较短，是可以更快找到嵌入式软硬件划分问题的最优方案，满足了嵌入式软硬件划分问题求解的实时性，有效降低了嵌入式系统的功耗。
4 结 语
嵌入式系统是当前计算机领域中的研究热点，而软硬件划分直接影响嵌入式系统的性能，针对标准蚁群算法存在收敛速度慢，难以获得全局最优的软硬件划分方案的问题，本文提出了改进蚁群算法的系统软硬件划分方法。首先建立了软硬件划分的数学模型，然后采用改进蚁群算法模拟蚂蚁觅食行为搜索数学模型的最优解，实验结果表明，改进蚁群算法提高了问题求解的效率，获得了合理的软硬件划分结果，且结果优于其他算法，在嵌入式系统较硬件划分中具有更高的实际应用价值。
参考文献
[1] 邹谊，庄镇泉，杨俊安.基于遗传算法的嵌入式系统软硬件划分算法[J].中国科学技术大学学报，2003，34（6）：724?731.
[2] 唐思章，黄勇.SOPC与嵌入式系统软硬件协同设计[J].单片机与嵌入式系统应用，2005，25（12）：35?56.
[3] 何湘竹，陈军波，陈亚光，等.SOC软硬件划分系统中的关键算法[J].计算机工程与应用，2006，43（14）：105?108.
[4] 李正民，郭金金，吕莹莹.一种嵌入式系统软硬件划分算法[J].计算机仿真，2011，28（10）：104?107.
[5] 刘威，丁岩松，徐学航.嵌入式系统软硬件划分技术的研究[J].煤炭技术，2011，30（2）：173?175.
[6] 刘功杰，张鲁峰，李思昆.遗传算法在软硬件划分中的应用[J].国防科技大学学报，2002，24（2）：64?68.
[7] 李晖，姚放吾，邓新颖，等.基于免疫算法的嵌入式系统软硬件划分方法[J].计算机工程与设计，2006，27（22）：4239?4242.
[8] 陈玮，顾思思.基于组合算法的嵌入式系统软硬件划分方法[J].计算机应用与软件，2015，32（10）：241?244.
[9] 邵岁锋，张英杰.基于免疫粒子群的嵌入式系统软硬件划分方法[J].计算机应用，2010，30（2）：479?481.
[10] 纪颖，李兰英，石敏，等.基于遗传和禁忌搜索混合的软硬件划分算法[J].计算机工程与应用，2009，45（20）：81?83.
[11] 熊志辉，李思昆，陈吉华.遗传算法与蚂蚁算法动态融合的软硬件划分[J].软件学报，2005，16（4）：503?512.
[12] 郭荣佐，黄君，王霖.基于π网的嵌入式系统软硬件划分方法[J].计算机应用，2012，32（3）：855?860.
[13] 刘安，冯金富，梁晓龙，等.基于遗传粒子群优化的嵌入式系统软硬件划分算法[J].计算机辅助设计与图形学学报，2010，22（6）：927?934. 技术文
摘 要： 针对标准蚁群算法的软硬件划分问题求解难题，提出改进蚁群算法的系统软硬件划分方法。首先分析了当前嵌入式系统软硬件划分研究的现状，并构建软硬件划分的数学模型；然后采用蚁群算法模拟蚂蚁觅食行为搜索数学模型的最优解，并引入逆反馈机制提高蚁群算法的搜索性能；最后通过实验证明软硬件划分问题求解的有效性。实验结果表明，改进蚁群算法提高了问题求解的效率，获得了合理的软硬件划分结果，且结果优于标准蚁群算法。
关键词： 硬件系统； 蚁群算法； 软件系统； 收敛速度； 仿真测试
中图分类号： TN919?34； TP181 文献标识码： A 文章编号： 1004?373X（2017）03?0164?03
Embedded system hardware and software partition
based on improved ant colony algorithm
PAN Ying， RUAN Wenhui
（School of Digital Media， Lanzhou University of Arts and Science， Lanzhou 730030， China）
Abstract： Since it is hard for the standard ant colony algorithm to solve the software and hardware partition problem， the hardware and software partition method based on the improved ant colony algorithm is proposed. The research status of the embedded system hardware and software partition is analyzed. The mathematical model of the hardware and software partition was constructed. The ant colony algorithm is used to simulate the foraging behavior of ants to search the optimal solution of the mathematical model. The inverse feedback mechanism is introduced to improve the search performance of the ant colony algorithm. The solving validity of the hardware and software partition problem was proved by means of experiments. The results show that the improved ant colony algorithm has improved the efficiency of problem solving， and obtained the reasonable hardware and software partition result， which is better than the result of the standard ant colony algorithm.
Keywords： hardware system； ant colony algorithm； software system； convergence speed； simulation test
0 引 言
随着计算机技术和微电子技术的不断成熟，嵌入式系统的应用范围更加广泛[1]。嵌入式系统包括硬件系统和软件系统两部分，以前由于硬件成本高，价格高，软件系统占的比例大。近几年，随着集成技术的发展，硬件价格急剧下降，出现了硬件系统和软件系统平分天下的格局[2]。硬件系统和软件系统均有各自的优势，对于一个嵌入式系统，如何对硬件系统和软件系统进行准确划分，降低系统的成本，同时保证系统满足實际要求，成为人们关注的焦点[3?4]。
自嵌入式系统出现以后，很多机构和大学专门成立了嵌入式软硬件系统划分研究团队，提出了许多有效的嵌入式软硬件划分算法[5]。最原始的方法为整数规划算法，工作灵活，可以适应不同类型的嵌入式系统，但整数规划算法的嵌入式软硬件系统划分问题求解时间长、速度慢，不能满足嵌入式系统软硬件划分的效率[6]。随后有学者提出了基于迭代算法的嵌入式软硬件划分方法，但同样存在求解效率低的缺陷[7]。大量研究结果表明，嵌入式软硬件系统划分是一个限制条件多的NP难题，出现了基于遗传算法的软硬件划分算法、基于免疫算法的软硬件划分算法、基于蚁群算法的软硬件划分算法[8?10]。有学者对三种算法的优劣进行比较，发现基于蚁群算法的软硬件划分算法性能最优，然而标准蚁群算法存在收敛速度慢等不足，在嵌入式系统软硬件划分问题求解范围受限[11]。
为了对嵌入式系统软硬件进行精确划分，降低系统成本，针对标准蚁群算法在软硬件划分问题求解过程存在的难题，提出了改进蚁群算法的系统软硬件划分方法，通过实验证明该方法在软硬件划分问题上求解的有效性。
1 改进蚁群算法
1.1 标准蚁群算法
蚁群一共包含有[m]只蚂蚁，它们分布于[n]个节点上，不同蚂蚁下一次移动选择节点的概率不同，该节点没有被访问过，并且对路径上信息素浓度进行更新。
节点选择的条件为：节点[i]和[j]的路径信息素浓度为[τij；]节点[i]转移到[j]的启发信息为[ηij，]它们的值根据具体问题进行设置。在[t]时刻，蚂蚁[k]从节点[i]选择节点[j]为目的地的概率为：
[pkijt=ταijtηβijj∈Nkiταijtηβij] （1）
式中：[Nki]表示蚂蚁[k]可以选择的节点；[α]表示残留信息权值；[β]表示启发信息的重要程度。
在蚁群移动的过程中，为了不让残留信息对启发信息产生干扰，蚂蚁经过全部节点后，需要更新残留信息浓度，使部分信息素挥发，同时将最新访问节点信息加入到[τij，]即有：
[τijt+n=ρτijt+k=1mΔτkij] （2）
式中：[ρ]表示信息素的挥發程度；[Δτkij]表示残留信息素的浓度。
1.2 标准蚁群算法的不足以及改进
在标准蚁群算法的工作中，蚂蚁的数目固定不变，只有正反馈过程，不能实现逆反馈过程，导致算法的收敛速度慢，工作效率低。为了解决标准蚁群算法存在的不足，设计了逆反馈过程，引入一个阈值[ε，]当循环相遇蚂蚁的数量小于[ε，]就按标准蚁群算法进行工作，反之，相遇蚂蚁路径上的信息素均要进行更新，改进蚁群算法的具体工作流程如图1所示。
1.3 改进蚁群算法的有效性测试
为了比较改进蚁群算法（IACO）和标准蚁群算法（ACO）的优越性，选择两个Sphere和Rosenbrock测试执行速度和求解精度，结果见图2。对图2的变化曲线进行分析可以发现，IACO的迭代次数显著减少，计算时间复杂度明显下降，提高了蚁群搜索问题解的速度，而且得到更高的精度结果，这说明本文引入逆反馈过程可以获得更优的蚁群算法。
2 改进蚁群算法的嵌入式系统软硬件划分
2.1 软硬件问题的数学模型
嵌入式系统的软硬件功能可以用DAG表示，[V]表示节点的集合，且任务[i]满足条件：[vi∈V，][E]表示边的集合，且有[ei=vi，vj∈V，]采用“0”和“1”分别表示嵌入式系统的软件系统和硬件系统，那么节点的DAG具体如图3所示。
嵌入式系统软硬件划分的节点之间通信开销[cvi，vj]和的数学模型[12]为：
[cp（vi），vi=vj∈p（vi）c（vj，vi），由软件完成maxvj∈p（vi）c（vj，vi），由硬件完成 ] （3）
式中[p（vi）]表示[vi]的全部前驱节点。
相应的约束条件为：
[minTvends.t. i=1nphixi+psi（-xi）≤Pi=1nahixi≤Ahi=1nasi（-xi）≤Asxi∈Z] （4）
2.2 软硬件划分问题的求解
（1） 对具体的嵌入式系统软硬件问题进行分析，建立数学模型。
（2） 对改进蚁群算法的参数进行设置，并初始化蚁群。
（3） 将所有蚂蚁平均分配到嵌入式系统软硬件构成的DAG节点上。
（4） 根据式（1）计算每一只蚂蚁选择下一个节点的概率，并且从转移到的该节点上建立每只蚂蚁的转移路径。
（5） 对全部蚂蚁转移路径进行分析，看是否有相遇的蚂蚁，若有将相遇的蚂蚁，则将它们的路径取作为一条新路径。
（6） 根据阈值评价相遇蚂蚁的数目，为每一只蚂蚁建立自己的路径。
（7） 根据阈值判断结果进行信息素更新操作。在每次循环时，信息素浓度不能超过范围[τmin，τmax，]不然采用式（3）进行强制设置。
[τij=τmin，τij≤τminτmax，τij≥τmax] （5）
（8） 根据蚁群的最优路径得到嵌入式系统软硬件划分的最佳方案。
3 仿真实验的结果与分析
为了测试改进蚁群算法的嵌入式系统软硬件划分方法的有效性，选择粒子群算法（PSO）[13]的嵌入式系统软硬件划分方法进行仿真对比测试。
在不同节点数目的条件下，采用Matlab 2014R编程进行模拟测试，两种方法的嵌入式系统面积变化曲线如图4所示。从图4可以看出，随着节点数目的增加，两种嵌入式系统软硬件划分方法设计系统的面积随之增大，改进蚁群算法的面积要小于粒子群算法，说明改进蚁群算法的嵌入式系统的集成度更高，有效降低了嵌入式系统的功耗。
在不同节点数目的条件下，两种方法对嵌入式软硬件划分问题求解的时间变化曲线如图5所示。从图5可以看出，随着节点数目的增加，改进蚁群算法和粒子群算法的执行时间也延长，在相同条件下，改进蚁群算法的执行时间较短，是可以更快找到嵌入式软硬件划分问题的最优方案，满足了嵌入式软硬件划分问题求解的实时性，有效降低了嵌入式系统的功耗。
4 结 语
嵌入式系统是当前计算机领域中的研究热点，而软硬件划分直接影响嵌入式系统的性能，针对标准蚁群算法存在收敛速度慢，难以获得全局最优的软硬件划分方案的问题，本文提出了改进蚁群算法的系统软硬件划分方法。首先建立了软硬件划分的数学模型，然后采用改进蚁群算法模拟蚂蚁觅食行为搜索数学模型的最优解，实验结果表明，改进蚁群算法提高了问题求解的效率，获得了合理的软硬件划分结果，且结果优于其他算法，在嵌入式系统较硬件划分中具有更高的实际应用价值。
参考文献
[1] 邹谊，庄镇泉，杨俊安.基于遗传算法的嵌入式系统软硬件划分算法[J].中国科学技术大学学报，2003，34（6）：724?731.
[2] 唐思章，黄勇.SOPC与嵌入式系统软硬件协同设计[J].单片机与嵌入式系统应用，2005，25（12）：35?56.
[3] 何湘竹，陈军波，陈亚光，等.SOC软硬件划分系统中的关键算法[J].计算机工程与应用，2006，43（14）：105?108.
[4] 李正民，郭金金，吕莹莹.一种嵌入式系统软硬件划分算法[J].计算机仿真，2011，28（10）：104?107.
[5] 刘威，丁岩松，徐学航.嵌入式系统软硬件划分技术的研究[J].煤炭技术，2011，30（2）：173?175.
[6] 刘功杰，张鲁峰，李思昆.遗传算法在软硬件划分中的应用[J].国防科技大学学报，2002，24（2）：64?68.
[7] 李晖，姚放吾，邓新颖，等.基于免疫算法的嵌入式系统软硬件划分方法[J].计算机工程与设计，2006，27（22）：4239?4242.
[8] 陈玮，顾思思.基于组合算法的嵌入式系统软硬件划分方法[J].计算机应用与软件，2015，32（10）：241?244.
[9] 邵岁锋，张英杰.基于免疫粒子群的嵌入式系统软硬件划分方法[J].计算机应用，2010，30（2）：479?481.
[10] 纪颖，李兰英，石敏，等.基于遗传和禁忌搜索混合的软硬件划分算法[J].计算机工程与应用，2009，45（20）：81?83.
[11] 熊志辉，李思昆，陈吉华.遗传算法与蚂蚁算法动态融合的软硬件划分[J].软件学报，2005，16（4）：503?512.
[12] 郭荣佐，黄君，王霖.基于π网的嵌入式系统软硬件划分方法[J].计算机应用，2012，32（3）：855?860.
[13] 刘安，冯金富，梁晓龙，等.基于遗传粒子群优化的嵌入式系统软硬件划分算法[J].计算机辅助设计与图形学学报，2010，22（6）：927?934. 技术文
