免疫遗传算法及其应用研究
VIP免费
摘 要
遗传算法是一种具有生成加检测迭代过程的搜索算法。种群搜索和种群中个
体通过变异算子和交叉算子实现了信息的交换。在算法的迭代进化的过程中，在
一定概率的条件下随机产生了交叉算子和变异算子。因此，种群中的个体在变异
和交叉算子的作用下得到了进化的机会，但是与此同时也不可避免地出现了退化
的现象。通常每一个将要解决的实际问题都会有其自身的一些特征信息，但是在
遗传算法中，交叉和变异算子却是相对固定的，在求解问题的过程之中，灵活程
度的可变性较小。
生物体的免疫系统自身拥有抗原的识别、免疫记忆和维持抗体多样性等特性。
本文通过研究这些特性，从而提出了一种改进的免疫遗传算法，此算法将生物系
统中的免疫思想引入到标准的遗传算法之中，使用先验的知识构造免疫算子，通
过接种疫苗和免疫选择，不但保留了群体中的最优个体，而且还很好的保证了个
体的多样性，从而避免了进化搜索的过早收敛，提高算法的收敛速度。
现今更多的嵌入式平台设计采用软硬件配合方式实现系统功能。软硬件实现
方式的比较是为了在软硬件混合系统设计中综合考虑硬件和软件效率，软硬件联
合设计可以实现协调软硬件开发过程中的并行设计。一方面，在早期可以发现软
件和硬件集成方面的问题，缩短了设计周期；另一方面，根据系统各个部分的特
点和设计的限制，可以选择软件或者硬件实现方式，得到高性能、低代价、可编
程的优化设计方案。软硬件划分将系统行为描述分解成与实现有关的软件部分和
硬件部分，然后确定系统的软硬件界面的设计步骤。在软硬件之间的优化配置功
能是软硬件联合设计中的首要问题。
本文首先简单的介绍了遗传算法的发展历史和遗传算法的理论基础，同时对
遗传算法的研究现状和应用技巧也做了详细的介绍；并在此基础上分析了标准遗
传算法的流程和算法实现过程。其次，简单地介绍了嵌入式协同设计的体系结构，
并在此基础上给出了软硬件划分的形式化的描述；最后，提出了一种软硬件划分
的模型，并通过改进的免疫遗传算法解决在多约束条件下软硬件划分的优化问题。
实验表明，通过将免疫遗传算法应用于软硬件协同设计中的软硬件划分之中，
搜索系统的最优解，算法具有较快的收敛速度，能够有效的减少陷入局部最优解
的可能。为免疫遗传算法在嵌入式设计大家庭中的应用提供了有益的探索和尝试。
关键字：嵌入式系统 软硬件协同 软硬件划分 遗传算法 免疫遗传算
法
ABSTRACT
Genetic algorithm is an iterative process, which has generated additional test search
algorithm. Through crossover and mutation operator, Populations Search and exchange
of information between individuals in Populations can be achieved. Crossover and
mutation operators are randomly generated under certain conditions in the iterative
search process. Not only crossover operator and mutation operator provided
opportunities of Populations evolution for individuals, but also inevitably resulted in
degradation. Usually each practical issue being solved has its own characteristics, but
the genetic algorithm crossover operator and mutation operator are relatively fixed. So
the flexibility is a little smaller in the problem solving process.
Biological immune system has some features, such as antigen recognition, immune
memory and maintaining the diversity of antibodies. This paper studies these features
and proposes an improved immune genetic algorithm, which pulls the knowledge of the
immune into the Genetic Algorithms. Through constructing the immune operator by
using a priori knowledge, vaccination and immune selection, not only retains the best
individual in the group but also guarantees the diversity of individuals, thus avoiding
premature convergence of evolutionary search and improve the convergence speed.
Now, more and more embedded platforms are designed by Hardware and software
co-design to improve the system functions. Comparison of hardware and software
implementation into the design of hybrid systems to account the efficiency of the
hardware and software, Hardware and software co-design can achieve coordinated
development of parallel software and hardware design. On the one hand, we can find
software and hardware integration issues at early and short the design cycle. On the
other hand, according to various parts of the system characteristics and design
constraints, you can choose the software or hardware implementations to get high
performance, low-cost, programmable, optimized designs. Software and hardware
division broken the system behavior down into the software parts and hardware parts,
and then determining the system's hardware and software design steps. The optimal
allocation of functions between hardware and software is the primary problem in the
hardware and software co-design.
In this paper, a brief history of the development of genetic algorithms and genetic
algorithm theory are introduced. At the same time, it introduces the status of genetic
algorithm and application skills and analysis the standard genetic algorithm and its
processes on this basis. Secondly, it introduces embedded architecture co-design and
gives the formal description of software and hardware division. Finally, we propose a
model of software and hardware division and solve the optimization problem under the
constraints of hardware and software in a multi-division by using improved immune
genetic algorithm.
Experiments show that algorithm, which apply immune genetic algorithm to
embedded software and hardware division algorithm, has a faster convergence rate and
can effectively reduce the possibility of falling into local optimal solution. This is a very
good attempt.
Key words: embedded system，software and hardware division，genetic
algorithm，immune genetic algorithm
目 录
中文摘要
ABSTRACT
第一章 绪论 ...................................................... 1
§1.1 课题研究的背景及意义 ..................................... 1
§1.2 国内外研究现状 ........................................... 2
§1.3 本文的主要内容以及章节安排 ............................... 3
第二章 遗传算法及人工免疫系统 .................................... 4
§2.1 遗传算法概述 ............................................. 4
§2.1.2 遗传算法的原理 ....................................... 4
§2.1.2 遗传算法中的基本概念 ................................. 5
§2.1.3 遗传算法的基本特点 ................................... 6
§2.2 基本遗传算法介绍 ......................................... 7
§2.3 遗传算法的全局收敛性和早期收敛问题 ...................... 14
§2.4 人工免疫系统 ............................................ 15
§2.4.1 生物免疫系统基础 .................................... 16
§2.4.2 免疫系统的分类 ...................................... 16
§2.4.3 免疫机制 ............................................ 16
§2.4.4 免疫学基本原理 ...................................... 17
§2.4.5 人工免疫系统模型 .................................... 18
§2.4.6 人工免疫系统算法 .................................... 19
§2.4.7 免疫遗传算法的基本概念 .............................. 22
§2.5 遗传算法实例仿真 ........................................ 22
§2.6 本章小结 ................................................ 24
第三章 嵌入式计算机平台 ......................................... 25
§3.1 嵌入式概述 .............................................. 25
§3.2 嵌入式平台的组成 ........................................ 26
§3.3 嵌入式平台的硬件构成 .................................... 27
§3.3.1 微处理器 ............................................ 27
§3.3.2 存储器 .............................................. 29
§3.3.3 I/O 接口 .............................................32
§3.3.4 总线 ................................................ 33
§3.4 嵌入式平台的软件构成 .................................... 33
§3.4.1 概述 ................................................ 33
§3.4.2 嵌入式操作系统 ...................................... 34
§3.4.3 嵌入式应用软件 ...................................... 36
§3.5 本章小结 ................................................ 36
第四章 软硬件协同技术 ........................................... 37
§4.1 软硬件协同概述 .......................................... 37
§4.2 传统的嵌入式设计 ........................................ 38
§4.3 软硬件协同技术 .......................................... 39
§4.3.1 软硬件协同设计过程 .................................. 39
§4.3.2 软硬件协同设计工具 .................................. 40
§4.3.3 软硬件协同设计的优点 ................................ 41
§4.4 本章小结 ................................................ 42
第五章 免疫遗传算法在软硬件协同设计中软硬件划分之中的应用 ....... 43
§5.1 软硬件协同设计 .......................................... 43
§5.1.1 软硬件协同设计方法 .................................. 43
§5.1.2 软硬件协同设计的基本步骤 ............................ 43
§5.1.3 软硬件划分模型 ...................................... 44
§5.1.4 系统功能描述 ........................................ 44
§5.2 改进的免疫遗传算法划分方法 .............................. 46
§5.2.1 免疫遗传算法 ........................................ 46
§5.2.2 免疫遗传算法中的关键步骤 ............................ 47
§5.3 实验和算法性能分析 ...................................... 51
第六章 总结和展望 ............................................... 53
§6.2 总结 .................................................... 53
§6.3 展望 .................................................... 54
参考文献 ........................................................ 55
在读期间公开发表的论文和承担科研项目及取得成果 .................. 60
致 谢 ........................................................... 61
第一章 绪论
1
第一章 绪论
§1.1 课题研究的背景及意义
Holland 教授于 1975 年提出了一类随机化搜索算法，即遗传算法，它以达尔
文的进化理论和 Mendal 的遗传学说为理论基础，以此来模拟生物自然选择和遗传
变异机制。从上世纪 80 年代起，遗传算法开始广泛应用于复杂系统、自适应控制
和复杂优化过程。作为一种随机的优化搜索算法，遗传算法具有其自身的特性：
它借鉴生物学中染色体和基因等概念，可以对一维和多维的对象进行处理；它同
时使用多个搜索点的搜索信息，其操作对象是一组可行的解，因此具有良好的并
行性、稳健性和全局优化性；遗传算法以目标函数值作为搜索信息，因此没有必
要进行求导操作，在大规模非线性的不连续的多峰值函数的优化中有着良好的应
用。同时遗传算法也存在着很多的不足，它的初始化种群是随机产生的，没有附
加相应的约束条件，导致初始化种群中的多样性不是十分丰富，很容易导致算法
的早期收敛；基本遗传算法使用二进制进行编码，当参数过多或者太大时，二进
制代码将十分庞大，占用了很多的空间，计算精度随之下降；交叉算子和变异算
子的参数相对单一固定，这就降低了算法的灵活性。
免疫算法是基于生物免疫系统原理发展而来的，生物免疫系统由淋巴细胞和
和抗体分子组成，淋巴细胞由 B细胞和 T细胞组成，B细胞分泌血清抗体，T细
胞分泌淋巴细胞活素，它们可以和抗原进行专一的结合而产生抗体。为了维持免
疫系统的平衡，抗体之间还存在着促进和抑制作用。我们把外来侵入抗原和免疫
系统产生的抗体分别与实际求解问题的目标函数和问题的解相对应，这就是免疫
算法的生物学基础。免疫遗传算法就是基于生物免疫机制提出的一种改进的遗传
算法，它具有产生多样性抗体的能力，可以提高遗传算法的全局搜索能力，从而
避免陷入局部最优；它具有自我调节的机构，通过个体浓度的抑制和促进作用，
可以提高遗传算法局部搜索能力。
如今，嵌入式系统设计的规模越来越大，涉及到的软件和硬件资源也越来越
多。在系统的设计过程当中，软件和硬件资源的合理运用成为了很关键的因素，
因此软硬件划分算法就显得尤为重要了。一个良好的划分方案通常要考虑下面的
因素：其中包括系统的运行时间、功耗、整体性能、存储容量等，它属于一个在
多约束条件下的优化组合问题。经过人们的不断努力和大量工作，提出了许多可
行规划算法，如 GA、SA、TS、双向约束算法、分级群聚法等[24]。
本文在基于基本遗传算法的基础上，通过将改进的免疫遗传算法应用在软硬
件划分之中，此算法不但收敛速度快，还能有效地避免传统遗传算法陷入局部最
摘要：
展开>>
收起<<
摘要遗传算法是一种具有生成加检测迭代过程的搜索算法。种群搜索和种群中个体通过变异算子和交叉算子实现了信息的交换。在算法的迭代进化的过程中，在一定概率的条件下随机产生了交叉算子和变异算子。因此，种群中的个体在变异和交叉算子的作用下得到了进化的机会，但是与此同时也不可避免地出现了退化的现象。通常每一个将要解决的实际问题都会有其自身的一些特征信息，但是在遗传算法中，交叉和变异算子却是相对固定的，在求解问题的过程之中，灵活程度的可变性较小。生物体的免疫系统自身拥有抗原的识别、免疫记忆和维持抗体多样性等特性。本文通过研究这些特性，从而提出了一种改进的免疫遗传算法，此算法将生物系统中的免疫思想引入到标准的...
相关推荐
作者：高德中
分类：高等教育资料
价格：15积分
属性：64 页
大小：783.12KB
格式：PDF
时间：2024-11-19
