基于遗传和蚂蚁混合的软硬件划分方法研究

摘要

随着微电子技术的快速发展，大量的嵌入式产品进入到百姓的生活之中，高效的开发产品具有成本低、体积小、功耗低的特点。软硬件协同设计是软硬件划分的主流方法，这种方法避免了传统产品开发带来的错误定位、周期时间长和成本过高的不足。为了满足嵌入式系统开发，需要考虑的因素包括系统建模、系统描述、软硬件划分以及划分算法的选择。考虑到系统成本和系统性能因素，有效的、合理的软硬件划分是本课题的主要研究内容。在软硬件划分过程中，划分算法是整个过程的重点，合理的算法对于在软硬件划分过程中寻找最优解起到决定性的作用。
　　本文充分地介绍了软硬件划分的理论知识，分析了软硬件划分在国内外的研究情况和应用领域，考虑传统设计方法的不足，重点介绍了软硬件划分中的算法以及系统模型。遗传算法(Genetic Algorithm，GA)和蚂蚁算法(Ant Algorithm)是本文主要研究的划分算法，通过分析比较出两种算法的优点和缺点，综合两种算法的优势，创新地提出遗传-蚂蚁混合算法(Genetic Algorithm and Ant Algorithm，GAAA)并应用到软硬件双路划分中，利用TGFF(Task Graph for Free)工具生成有向无环图(DAG)作为系统模型，新混合算法从遗传算法开始，利用遗传算子操作得到若干优化解，并将得到的优化解作为蚂蚁算法的初始信息素，蚂蚁算法通过初始化信息素分布进行搜索过程，本算法充分利用遗传算法的选择、交叉、变异以及蚂蚁算法的正反馈特性，在寻找最优解过程中具有良好的性能。
　　根据TGFF生成的数据，将GA、AA算法和GAAA算法分别进行编程，最后将得出的实验数据进行对比分析，结果表明GAAA算法能克服GA局部搜索能力差、AA初始信息素不足的缺点，从而能寻找出精度更高、适应性更强的解集。

目录

声明

摘要

第1章 引言

1．1 课题研究背景及意义

1．1．1 嵌入式系统概述

1．1．2 传统嵌入式系统设计

1．2 软硬件协同设计

1．3 软硬件划分算法的国内外研究现状

1．3．1 国外研究现状

1．3．2 国内研究现状

1．4 课题的研究内容

1．4．1 课题来源

1．4．2 课题的主要研究内容

第2章 软硬件划分技术综述

2．1 软硬件划分涉及的主要内容

2．1．1 组合优化问题

2．1．2 软硬件划分基本概念

2．1．3 软硬件划分种类

2．1．4 IP核

2．1．5 划分中需要注意的几个问题

2．2 系统建模方法

2．2．1 数据流图建模

2．2．2 Petri网建模

2．2．3 UML建模

2．2．4 任务流图

2．3 本章小结

第3章 遗传和蚂蚁算法研究与分析

3．1 引言

3．2 遗传算法简介

3．2．1 遗传算法的主要特点

3．2．2 遗传算法的应用领域

3．2．3 遗传算法的基本原理

3．2．4 遗传算法的编码方式

3．2．5 遗传算法的适应度函数

3．2．6 遗传算法的操作算子

3．2．7 遗传算法的实现步骤

3．3 蚂蚁算法

3．3．1 蚂蚁算法基本思想

3．3．2 蚂蚁算法的机制原理

3．3．3 蚂蚁算法的特点

3．3．4 蚂蚁算法的应用领域

3．3．5 蚂蚁算法的算法流程

3．4 遗传算法和蚂蚁算法的混合算法

3．5 本章小结

第4章 GAAA软硬件划分算法的实现

4．1 引言

4．2 遗传和蚂蚁算法对比分析

4．2．1 遗传算法GA优缺点

4．2．2 蚂蚁算法AA优缺点

4．3 算法实现

4．3．1 软硬件划分模型

4．3．2 软硬件划分功能描述

4．3．3 目标系统结构

4．3．4 GAAA问题描述

4．3．5 适应度函数

4．3．6 蚂蚁算法信息素的改进

4．3．7 遗传、蚂蚁的混合策略(GAAA)

4．4 本章小结

第5章 GAAA算法验证及结果分析

5．1 实验样本与实验环境

5．2 算法的参数设置

5．3 实验结果对比

5．3．1 比较试验生成数据

5．3．2 GA，AA和GAAA在不同节点数下的运行结果比较

5．4 本章小结

结论

参考文献

攻读硕士学位期间发表的学术论文

致谢