摘要
针对单处理器嵌入式系统软硬件划分问题,采用带权有向无环图进行建模,并将之约简,进而转换为多约束条件的0/1背包问题求解.由于基本粒子群优化算法无法求解0/1背包问题,故将遗传算法中的交叉、变异思想引入粒子群优化算法,提出了求解离散组合优化问题的遗传粒子群优化(GPSO)算法,采用两点交叉算子和非均匀变异算子对粒子的位置和速度更新方法进行了重新定义.实验结果表明,采用文中算法能有效地解决软硬件划分问题,具有良好的全局搜索能力,其寻优能力和执行时间优于遗传算法和模拟退火算法.
Aiming at hardware/software partitioning problem of single CPU embedded system,a directed acyclic graph（DAG）model was constructed.The model was then reduced and converted to a constrained 0/1 knapsack problem.A genetic particle swarm optimization（GPSO）algorithm was presented where both crossover and mutation of genetic algorithm were introduced into basic PSO algorithm to solve the 0/1 knapsack problem.Both double point crossover and non-uniform mutation were adopted to update the positions and velocities of particles.Experimental results show that GPSO algorithm can solve the hardware/software partitioning problem effectively.GPSO algorithm has better optimization ability and shorter execution time than genetic algorithm and simulated annealing algorithm.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
2010年第6期927-933,942,共8页
Journal of Computer-Aided Design & Computer Graphics
基金
国家"八六三"高技术研究发展计划(2007A×××27
2007A×××10)
关键词
软硬件划分
有向无环图
遗传算法
粒子群优化算法
两点交叉
非均匀变异
hardware/software partitioning
directed acyclic graph
genetic algorithm
particle swarm optimization
double point crossover
non-uniform mutation
