基于改进人工鱼群算法的软硬件划分方法

全浩军，张 涛，郭继昌

(天津大学电子信息工程学院，天津 300072)

嵌入式系统广泛应用于医疗、电力、航空、消费类电子等领域．在嵌入式系统的设计中，往往采用软硬件协同设计方法以缩短产品的研发周期，同时满足产品在成本、功耗、性能等多方面的需求[1-2]，而软硬件划分是软硬件协同设计中的重点和难点[3]．

由于软硬件划分技术可以在满足特定约束的条件下有效提高系统性能、降低功耗，因此近年来很多研究人员都进行了相关算法的研究工作并取得了一定的进展[4-5]．在精确算法的研究方面，主要有分支定界、动态规划和整数线性规划等[4]．精确算法可以得到高性能的软硬件划分方案，但算法复杂度很高，因此启发式算法成为目前主要的研究方向，其中包括遗传算法、模拟退火、禁忌搜索、贪婪算法等基本算法和一些结合及改进算法，如遗传模拟退火[6]、遗传禁忌搜索[7]、遗传粒子群优化[8]、分支定界粒子群优化[9]和改进的非支配分类遗传算法[10]等．

人工鱼群算法是将人工智能思想引入优化命题的解决中而产生的一种高效智能优化算法，具有并行性、简单性、全局性、跟踪性等诸多优点，且算法只考虑目标函数值而对目标函数本身的性质不敏感[11]．然而人工鱼群算法主要应用于求解连续型的优化问题，对于离散型的优化问题，虽已有人提出了应用方法[12]，但存在最优解出现概率低、收敛速度慢等问题．笔者将原始人工鱼群算法应用于软硬件划分，然后在对原始算法进行分析的基础上提出了基于随机步长和邻域搜索的改进方法，最后使用TGFF 工具生成的有向无环图(directed acyclic graphs，DAG)对两算法进行对比测试．实验结果验证了改进后算法的高效性．

1 基于人工鱼群算法的软硬件划分

1.1 鱼群行为与人工鱼群算法

人工鱼群算法以鱼群的聚群、追尾、觅食等几种典型行为为基础[11]．聚群行为是鱼类在进化过程中形成的一种生活习性，在集体觅食或躲避伤害时，鱼朝着某一中心位置聚集成群．追尾行为指当鱼群中有鱼发现食物时，邻近的鱼会尾随该鱼从而能尽快找到食物．觅食行为则是鱼随机游走以寻找食物的行为．人工鱼群算法通过以上行为更新鱼群并对鱼的位置进行评价，再通过行为选择来控制鱼群收敛，从而达到寻优的目的．

1.2 数学描述

假设待划分系统由 N 个结点构成，每个结点既可以用软件实现(用 0 表示)，也可以用硬件实现(用1 表示)，这样 N 个结点的软硬件划分构成了一个 N 维空间{0 ,1}N．将人工鱼群中的所有鱼置于该N 维空间中，令表示第i (i =1,2,… ,M )条鱼在空间中所处的位置，这样一个位置便对应于一个确定的软硬件划分方案，其中 xi,j= 0(xi,j= 1)表示第j 个结点用软件(硬件)实现．为便于描述，将第i条鱼在空间中的位置称为第i条鱼所处的状态，并以Xi,event表示第i条鱼在 event 事件下的状态，例如Xi,next表示第i条鱼在下一时刻的状态，Xi,dest表示第i条鱼的目标状态．令 Yi,event表示 Xi,event状态对应软硬件划分方案的耗时，则在方案可行的前提下，Yi,event的值越小表明 Xi,event状态对应的划分方案越好．

1.3 算法描述

文献[12]以旅行商问题为实例，提出将人工鱼群算法应用于组合优化问题．基于第 1.2 节中的定义，笔者将该算法应用于软硬件划分，其伪代码为

Algorithm.Alg-ori/*使用文献[12]中的人工鱼群算法进行软硬件划分*/

begin

M ：＝10，max_repeat_num：＝1,500，prey_try_num：＝10，delta：＝0.9，visual：＝30；/*变量初始化*/

Init_fishs()；/*鱼群初始化*/

Bulletin_update_old()；/*公告栏更新*/

forrepeat_num：＝1tomax_repeat_numdo begin

fori：＝1toMdo

begin

/*聚群行为*/

neighbour_fish_num：＝Num(Xi,now，visual)；

/*计算鱼在可视范围内的伙伴数目*/

Xi,center：＝Center(Xi,now，visual)；/*计算鱼在

可视范围内与所有伙伴的中心位置*/

/*判断中心位置是否有效、周围是否拥挤以及

中心位置对应的状态是否更优*/

if(is_valid（ Xi,center)&&neighbour_fish_num/

M ＜delta&& Yi,center＜Yi,now）

thenXi,next：＝ Xi,center；/*鱼向中心位置前进*/

elsePrey_behavior(prey_try_num)；/*觅食行

为*/

/*追尾行为*/

Xi,best：＝Best(Xi,now，visual)；/*计算鱼在可视

范围内伙伴的最优状态*/

/*计算最优伙伴在可视范围内的伙伴数目*/

neighbour_fish_num：＝Num( Xi,best，visual)；

/*判断该最优伙伴周围是否拥挤、是否比鱼的

当前状态更优*/

if(neighbour_fish_num/M＜delta&&) Yi,best＜Yi,now

thenXi,next：＝ Xi,best；/*鱼向最优伙伴前进*/

elsePrey_behavior(prey_try_num)；/*觅食行为*/

Moving_evaluation()；/*行为评价与选择*/

endof for；

Bulletin_update_old()；/*公告栏更新*/

endof for；

end.

其中M为鱼群规模，即鱼群中鱼的个数，max_repeat_num 为鱼群的最大更新次数，prey_try_num 为鱼的最大觅食尝试次数，delta 为拥挤度因子，visual 为鱼的可视范围．

在算法 Alg-ori 中，如果聚群行为(追尾行为)无法找到有效的更优状态，则进行觅食行为．在觅食行为中，首先令鱼在下一状态游走到可视范围内的一个随机状态，然后判断该状态是否有效、是否比当前状态更优，如果条件满足，则不再尝试，否则持续尝试直至到达限定次数prey_try_num．对于鱼群中的任一条鱼，在完成以上行为后，都对这些行为产生的下一状态进行评价并从中选择最优状态作为鱼的目标状态，即执行 Moving_evaluation()函数．而在完成一次完整的鱼群更新后，进行公告栏的更新，其伪代码为

Function.Bulletin_update_old()

/*原始的公告栏更新函数*/

begin

/*计算鱼群中鱼的最优状态和最差状态*/

Xnew_best：＝Find_best_fishstate()；

Xnew_worst：＝Find_worst_fishstate()；

if(Ynew_best＜Yold_best)

thenXold_best：＝ Xnew_best；

elseXnew_worst：＝Xold_best；

end.

在原始的公告栏更新函数中，首先计算更新后鱼群中鱼的最优状态Xnew_best与最差状态 Xnew_worst，然后将Xnew_best与更新前鱼群中鱼的最优状态 Xold_best进行比较．如果相应的划分方案耗时 Ynew_best小于 Yold_best，则记录更新后的最优状态Xnew_best，否则使用更新前的最优状态 Xold_best替换更新后的最差状态 Xnew_worst以保证鱼群状态更新的收敛性．

2 算法分析与改进

算法Alg-ori 通过鱼的3种行为不断更新鱼群状态，可以在一定程度上表现出向最优解收敛的特性，达到寻优的目的，然而在鱼移动步长、鱼群状态更新效率等方面存在问题，影响了算法的收敛速度．为此，从以下两个方面进行分析和改进．

2.1 随机步长

在算法 Alg-ori 中，觅食行为可以以一定概率找到更优状态，从而实现对局部解的逃逸，但这种搜索行为是随机的，或者可以说是 “盲目” 的．而在聚群和追尾这种“引导” 式的搜索行为中，鱼向目标状态的前进又是一步到达的，这样虽然鱼是朝着更优状态前进的，但存在两点不足：①鱼的当前状态与目标状态间可能存在更优的中间状态，而一步到达的方式跳过了这些中间状态，不利于鱼群的局部寻优；②如果已经有鱼处于目标状态(在追尾行为中，这种现象必然发生)，则鱼在下一状态会与另一条鱼的状态合并为一个状态，这样不利于全局极值的搜索．为此，使用随机步长的方法来改善鱼的游走行为．

如图 1 所示，第i 条鱼当前状态Xi,now与目标状态 Xi,dest对应两个不同的软硬件划分方案．设对结点j (j=1,2,… ,N)的划分方案中，鱼由当前方案 xi,now,j变为目标方案 xi,dest,j的概率为αi,j，令

图1 随机步长示意Fig.1 Schematic diagram of random step

则鱼由当前状态Xi,now变为目标状态Xi,dest的概率为

2.2 无效迭代的产生及邻域搜索

鱼群状态的更新是以鱼的更优状态来替换次优状态的过程，因此鱼群状态的每一次完整更新都可视为一次迭代．在理想情况下，每一次迭代都应当产生至少一个更优的状态．然而在实际运行中，由于鱼在离散空间游走的随机性，每次迭代并不一定能产生更优的状态，在此将没有产生更优状态的迭代称为无效迭代．

无效迭代现象在迭代的后期会更加明显，并会产生多次连续的无效迭代．这是由于随着鱼群的迭代，更优的状态往往出现在目前最优状态邻域内的一个较小的范围内，甚至只存在于目前最优状态邻域内的某一特定位置．而由于鱼游走的随机性且更优状态与目前最优状态之间可能并不存在中间状态，因此鱼可能会在最优状态附近迂回搜索但很难找到更优的状态．为此，使用邻域搜索方法来避免多次无效迭代的产生、加速收敛．

已知第i 条鱼当前状态为Xi,now，则所有与Xi,now距离小于 1 的状态 Xi,state_1构成一个集合，称为第i 条鱼的一维邻域．类似地，所有与Xi,now距离小于l 的目标状态Xi,state_l构成一个集合，称为第i 条鱼的l 维邻域．如果对第i 条鱼的l 维邻域按一定规则进行搜索以获得更优状态，则这种行为称为对第i 条鱼的l 维邻域搜索．搜索的维数是从搜索广度上而言的，在搜索深度上，默认是对所有可能状态进行搜索，即遍历搜索．然而，遍历搜索具有很高的算法复杂度，因此可以在找到一个更优状态后结束搜索以减少耗时．

邻域搜索只有在连续无效迭代达到一定的次数(即满足邻域搜索条件)时才会执行，而如果此时邻域搜索仍无法找到更优状态，则在后续的无效迭代中不再执行邻域搜索直至无效迭代被重新计数．当连续无效迭代次数达到停止条件时，则默认无法找到更优的状态，从而不再更新鱼群状态，结束搜索．

邻域搜索条件的判断在公告栏更新函数中执行，改进后的公告栏更新函数伪代码为

Function.Bulletin_update_new()

begin

/*计算鱼群中鱼的最优状态和最差状态*/

Xnew_best：＝Find_best_fishstate()；

Xnew_worst：＝Find_worst_fishstate()；

if(Ynew_best＜Yold_best)

then begin

un_update_count：＝0；/*无效迭代次数置零*/

Xold_best：＝ Xnew_best；

endof if；

else begin

Xnew_worst：＝ Xold_best；

un_update_count：＝un_update_count＋1；/*无效

迭代次数递增*/

if(un_update_count ＝Neighborhood_searching_

condition)/*是否满足邻域搜索条件？*/

then begin

/* 邻域搜索，找到更优状态则返回

SUCCESS*/

return_value：＝Neighborhood_searching()；

if(return_value＝SUCCESS)

then begin

un_update_count：＝0；/*无效迭代次数置零

*/

Xnew_best：＝the best fish in Neighbor

hood_searching()；

Xold_best：＝ Xnew_best；

endof if；

endof if；

else if(un_update_count＝stop_condition)/*是否

满足结束条件？*/

thenexit()；

endof else；

end.

同原始公告栏更新函数类似，在新的公告栏更新函数中，首先统计更新后鱼群中鱼的最优状态Xnew_best与最差状态 Xnew_worst，如果最优状态对应划分方案的耗时 Ynew_best小于原最优状态耗时 Yold_best，则记录 Xnew_best并将无效迭代次数 u n_update_count 清零，否则，首先用原始鱼群的最优状态替换当前鱼群的最差状态并将无效迭代次数 un_update_count 加 1，然后根据 u n_update_count 判断满足的条件并执行相应的运算．如果 un_update_count 等于邻域搜索条件Neighborhood_searching_condition，则进行邻域搜索从而检索邻域内的更优状态，如果更优状态存在，则记录该状态并将 un_update_count 清零．当un_update_count 等于结束条件 s top_condition 时，则认为无法找到更优状态，算法结束．

3 实验结果及分析

尽管软硬件划分方法很多，每种方法都可以在特定的软硬件协同设计环境下取得较好的划分效果，然而由于启发式因子的不同、参数设置的差异以及公认测试集的缺乏，方法间很难进行横向对比[4,13]. TGFF是一个随机图生成工具，可用于软硬件划分的对比测试．本文中以TGFF 工具随机生成的DAG 图作为测试集、以缩短 DAG 图的关键路径为优化目标对原始人工鱼群算法和改进后的人工鱼群算法进行对比测试．测试中共使用 TGFF 生成 4 个 DAG 图，参数设置如表1 所示，其中±表示浮动范围．

表1 TGFF工具参数设置Tab.1 Parameters setting of TGFF tool

由于TGFF 工具默认对结点数的浮动变化，实际生成的结点数分别为 29、49、69、100．实验硬件环境为Intel T2050 1.6,GHz CPU，2.87,G 内存；软件环境为 Windows XP Professional 2002,SP3，Microsoft Visual C++．对鱼群算法的参数设置为：鱼群规模10 ，觅食尝试次数 10，拥挤度因子 0.9，可视范围N/ 2(N为结点数)，最大迭代次数 1,5 0 0 ．此外，对于改进的鱼群算法，附加的参数设置为：步长概率γ = 3 3.3%，搜索维数为 2，邻域搜索条件为 10 次无效迭代，结束条件为 20 次无效迭代．为了降低随机因素的影响，对于每个结点的 DAG 图，两种算法均执行 2 0 次．将平均每次的执行时间记为平均执行时间，得到的实验结果如表2 所示．

表2 原始人工鱼群算法与改进后人工鱼群算法实验结果Tab.2 Experimental results of original and improved AFSA

根据表2 中的数据，从以下4 个方面进行分析．

1) 算法效率

在最优解上，改进后算法得到的最优解等于或优于原始算法；在最优解出现概率上，改进后算法的最优解出现概率为原算法的 5～7 倍．因此改进后算法具有更强的搜索和寻优能力，不仅最优解出现概率高，而且可以得到更优的解．

2) 算法稳定性

平均解和最差解反映了解的分布情况，由于改进后算法的最差解小于等于原始算法，而平均解小于原始算法，因此改进算法的解没有出现大范围扩散的现象，算法相对稳定．

3) 算法资源利用率

在平均硬件面积上，由表 1 的参数设置可知，平均硬件耗时小于软件耗时，所以关键路径耗时降低意味着更多的结点趋向于被划分到硬件，由于改进后的算法最优解出现概率高且可能得到更优的解，因此在满足硬件约束的前提下改进后算法的平均硬件面积高于原始算法，即改进后算法对硬件资源进行了更充分的利用．

4) 算法收敛速度

在迭代次数和平均迭代时间上，由于使用了邻域搜索的方法，因此改进后算法的平均每次迭代耗时大于原始算法．但在总耗时上，改进后算法的平均耗时约为原算法的 6.5%～34.5%，且改进后算法的最优解出现概率高于原始算法，因此改进后算法具有更快的收敛速度.

4 结 语

将人工鱼群算法应用于软硬件划分，从而提出一种新的软硬件划分方法．针对原始的人工鱼群算法在应用于软硬件划分时存在的最优解出现概率低、收敛速度慢等问题，提出了基于随机步长和邻域搜索的改进方法．改进后算法的平均耗时约为原算法的6.5%～34.5%，而最优解出现概率则为原算法的 5～7倍．结果表明，改进后算法具有更高的最优解出现概率和更快的收敛速度，可更高效地完成软硬件划分任务．

［1］Ye Hua，Wu Jigang. Computing models and algorithms for complex co-design systems[J].Journal of University of Electronic Science and Technology of China，2011，40(3)：333-345.

［2］Abdelhalim M B，Habib S E-D. An integrated high-level hardware/software partitioning methodology[J].Des Autom Embed Sys，2011，15(1)：19-50.

［3］于苏东，刘雷波，尹首一，等. 嵌入式粗颗粒度可重构处理器的软硬件协同设计流程[J]. 电子学报，2009，37(5)：1136-1140.Yu Sudong，Liu Leibo，Yin Shouyi，et al. Hardwaresoftware co-design flow for embedded coarse-grained reconfigurable processor[J].Chinese Journal of Electronics，2009，37(5)：1136-1140(in Chinese).

［4］Wu Jigang，Srikanthan T，Guang Chen. Algorithmic aspects of hardware/software partitioning：1D search algorithms[J].IEEE Transactions on Computers，2010，59(4)：532-544.

［5］Arato P，Mann Z A，Orban A. Algorithmic aspects of hardware/software partitioning[J].ACM Transactions on Design Automation of Electronic Systems， 2005 ，10(1)：136-156.

［6］Li Lanying，Song Yanbo，Gao Ming. A new genetic simulated annealing algorithm for hardware-software partitioning[C]// 2010 2nd International Conference on Information Science and Engineering(ICISE). Hangzhou，China，2010：1-4.

［7］Li Lanying，Shi Min. Software-hardware partitioning strategy using hybrid genetic and tabu search[C]// 2008International Conference on Computer Science and Software Engineering(CSSE). Wuhan，China，2008：83-86.

［8］刘 安，冯金富，梁晓龙，等. 基于遗传粒子群优化的嵌入式系统软硬件划分算法[J]. 计算机辅助设计与图形学学报，2010，22(6)：927-933.Liu An，Feng Jinfu，Liang Xiaolong，et al. Algorithm of hardware/software partitioning based on genetic particle swarm optimization[J].Journal of Computer-Aided Design and Computer Graphics，2010，22(6)：927-933(in Chinese).

［9］Eimuri T，Salehi S. Using DPSO and B and B algorithms for hardware/software partitioning in codesign[C]// 2010 2ndInternational Conference on Computer Research and Development(ICCRD). Kuala Lumpur，Malaysia，2010：416-420.

［10］罗胜钦，马萧萧，陆 忆. 基于改进的 NSGA 遗传算法的 SOC 软硬件划分方法[J]. 电子学报，2009，37(11)：2595-2599.Luo Shengqin，Ma Xiaoxiao，Lu Yi. An advanced nondominated sorting genetic algorithm based SOC hardware/software partitioning [J].Chinese Journal of Electronics，2009，37(11)：2595-2599(in Chinese).

［11］李晓磊，邵之江，钱积新. 一种基于动物自治体的寻优模式：鱼群算法[J]. 系统工程理论与实践，2002，22(11)：32-38.Li Xiaolei，Shao Zhijiang，Qian Jixin. An optimizing method based on autonomous animats：Fish-swarm algorithm [J].System Engineering Theory and Practice，2002，22(11)：32-38(in Chinese).

［12］李晓磊，路 飞，田国会，等. 组合优化问题的人工鱼群算法应用[J]. 山东大学学报：工学版，2004，34(5)：64-67.Li Xiaolei，Lu Fei，Tian Guohui，et al. Applications of artificial fish school algorithm in combinatorial optimization problems[J].Journal of Shandong University：Engineering Science， 2004 ， 34(5) ： 64-67(in Chinese).

［13］Lopez-Vallejo M，Lopez J C. On the hardware-software partitioning problem：System modeling and partitioning techniques[J].ACM Transactions on Design Automation of Electronic Systems，2003，8(3)：269-297.