计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (20): 81-83.DOI: 10.3778/j.issn.1002-8331.2009.20.025

• 研发、设计、测试 • 上一篇    下一篇

基于遗传和禁忌搜索混合的软硬件划分算法

纪 颖,李兰英,石 敏,张雷雷   

  1. 哈尔滨理工大学 计算机学院,哈尔滨 150080
  • 收稿日期:2008-06-12 修回日期:2008-10-23 出版日期:2009-07-11 发布日期:2009-07-11
  • 通讯作者: 纪 颖

Hardware/software partitioning algorithm using hybrid genetic and tabu search

JI Ying,LI Lan-ying,SHI Min,ZHANG Lei-lei   

  1. School of Computer,Harbin University of Science and Technology,Harbin 150080,China
  • Received:2008-06-12 Revised:2008-10-23 Online:2009-07-11 Published:2009-07-11
  • Contact: JI Ying

摘要: 针对嵌入式系统软硬件划分问题,在比较了遗传算法(GA)和禁忌搜索(TS)各自优缺点的基础上,提出采用遗传/禁忌混合算法(GATS)的策略,用遗传算法提供并行搜索的主框架,用禁忌搜索作为遗传算法的变异算子,遗传算法中变异过程解空间的搜索由禁忌搜索实现。实验结果表明,GATS具有多出发点和记忆功能强、爬山能力强的优势,能够克服GA爬山能力差、TS单点出发的弱点。最后与单纯的遗传算法和禁忌搜索算法进行对比实验,证明GATS更有优势,得到的划分结果也更优秀。

关键词: 嵌入式系统, 软硬件划分, 遗传算法, 禁忌搜索, 变异算子

Abstract: To solve the hardware/software partitioning problem in embedded system,based on the comparison of Genetic Algorithm(GA) and Tabu Search(TS),a hybrid algorithm is proposed on the basis of genetic algorithm and tabu search,where the main frame of the algorithm is provided by genetic algorithm and tabu search is taken as the mutation operator.Here the tabu search is used for the solution space in the process of mutation.And the results show that GATS has multiple starting-points,strong mountain-climbing ability and memory function instead of the weak mountain-climbing ability of GA and the single starting-point feature of TS.Experimental results also indicate that the hybrid algorithm is superior to the pure GA and TS in ability and gets better partitioning results.

Key words: embedded system, hardware/software partitioning, genetic algorithm, tabu search, mutation operator