免疫遗传算法及其应用研究

VIP免费

3.0 高德中 2024-11-19 5 4 783.12KB 64 页 15积分

侵权投诉

摘要

遗传算法是一种具有生成加检测迭代过程的搜索算法。种群搜索和种群中个

体通过变异算子和交叉算子实现了信息的交换。在算法的迭代进化的过程中，在

一定概率的条件下随机产生了交叉算子和变异算子。因此，种群中的个体在变异

和交叉算子的作用下得到了进化的机会，但是与此同时也不可避免地出现了退化

的现象。通常每一个将要解决的实际问题都会有其自身的一些特征信息，但是在

遗传算法中，交叉和变异算子却是相对固定的，在求解问题的过程之中，灵活程

度的可变性较小。

生物体的免疫系统自身拥有抗原的识别、免疫记忆和维持抗体多样性等特性。

本文通过研究这些特性，从而提出了一种改进的免疫遗传算法，此算法将生物系

统中的免疫思想引入到标准的遗传算法之中，使用先验的知识构造免疫算子，通

过接种疫苗和免疫选择，不但保留了群体中的最优个体，而且还很好的保证了个

体的多样性，从而避免了进化搜索的过早收敛，提高算法的收敛速度。

现今更多的嵌入式平台设计采用软硬件配合方式实现系统功能。软硬件实现

方式的比较是为了在软硬件混合系统设计中综合考虑硬件和软件效率，软硬件联

合设计可以实现协调软硬件开发过程中的并行设计。一方面，在早期可以发现软

件和硬件集成方面的问题，缩短了设计周期；另一方面，根据系统各个部分的特

点和设计的限制，可以选择软件或者硬件实现方式，得到高性能、低代价、可编

程的优化设计方案。软硬件划分将系统行为描述分解成与实现有关的软件部分和

硬件部分，然后确定系统的软硬件界面的设计步骤。在软硬件之间的优化配置功

能是软硬件联合设计中的首要问题。

本文首先简单的介绍了遗传算法的发展历史和遗传算法的理论基础，同时对

遗传算法的研究现状和应用技巧也做了详细的介绍；并在此基础上分析了标准遗

传算法的流程和算法实现过程。其次，简单地介绍了嵌入式协同设计的体系结构，

并在此基础上给出了软硬件划分的形式化的描述；最后，提出了一种软硬件划分

的模型，并通过改进的免疫遗传算法解决在多约束条件下软硬件划分的优化问题。

实验表明，通过将免疫遗传算法应用于软硬件协同设计中的软硬件划分之中，

搜索系统的最优解，算法具有较快的收敛速度，能够有效的减少陷入局部最优解

的可能。为免疫遗传算法在嵌入式设计大家庭中的应用提供了有益的探索和尝试。

关键字：嵌入式系统软硬件协同软硬件划分遗传算法免疫遗传算

法

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 课题研究的背景及意义

Holland 教授于 1975 年提出了一类随机化搜索算法，即遗传算法，它以达尔

文的进化理论和 Mendal 的遗传学说为理论基础，以此来模拟生物自然选择和遗传

变异机制。从上世纪 80 年代起，遗传算法开始广泛应用于复杂系统、自适应控制

和复杂优化过程。作为一种随机的优化搜索算法，遗传算法具有其自身的特性：

它借鉴生物学中染色体和基因等概念，可以对一维和多维的对象进行处理；它同

时使用多个搜索点的搜索信息，其操作对象是一组可行的解，因此具有良好的并

行性、稳健性和全局优化性；遗传算法以目标函数值作为搜索信息，因此没有必

要进行求导操作，在大规模非线性的不连续的多峰值函数的优化中有着良好的应

用。同时遗传算法也存在着很多的不足，它的初始化种群是随机产生的，没有附

加相应的约束条件，导致初始化种群中的多样性不是十分丰富，很容易导致算法

的早期收敛；基本遗传算法使用二进制进行编码，当参数过多或者太大时，二进

制代码将十分庞大，占用了很多的空间，计算精度随之下降；交叉算子和变异算

子的参数相对单一固定，这就降低了算法的灵活性。

免疫算法是基于生物免疫系统原理发展而来的，生物免疫系统由淋巴细胞和

和抗体分子组成，淋巴细胞由 B细胞和 T细胞组成，B细胞分泌血清抗体，T细

胞分泌淋巴细胞活素，它们可以和抗原进行专一的结合而产生抗体。为了维持免

疫系统的平衡，抗体之间还存在着促进和抑制作用。我们把外来侵入抗原和免疫

系统产生的抗体分别与实际求解问题的目标函数和问题的解相对应，这就是免疫

算法的生物学基础。免疫遗传算法就是基于生物免疫机制提出的一种改进的遗传

算法，它具有产生多样性抗体的能力，可以提高遗传算法的全局搜索能力，从而

避免陷入局部最优；它具有自我调节的机构，通过个体浓度的抑制和促进作用，

可以提高遗传算法局部搜索能力。

如今，嵌入式系统设计的规模越来越大，涉及到的软件和硬件资源也越来越

多。在系统的设计过程当中，软件和硬件资源的合理运用成为了很关键的因素，

因此软硬件划分算法就显得尤为重要了。一个良好的划分方案通常要考虑下面的

因素：其中包括系统的运行时间、功耗、整体性能、存储容量等，它属于一个在

多约束条件下的优化组合问题。经过人们的不断努力和大量工作，提出了许多可

行规划算法，如 GA、SA、TS、双向约束算法、分级群聚法等[24]。

本文在基于基本遗传算法的基础上，通过将改进的免疫遗传算法应用在软硬

件划分之中，此算法不但收敛速度快，还能有效地避免传统遗传算法陷入局部最

免疫遗传算法及其应用研究

优的可能，可以很好的应用到软硬件协同设计的软硬件划分之中。

§1.2 国内外研究现状

在近代科学的发展过程中，生命科学与工程科学的相互交叉和渗透十分普遍，

在这一过程中产生了很多新颖和有效的设计思想和算法，进化计算就是在这个过

程中诞生的。进化计算以大自然的生物进化论和遗传机制为基本原理，属于随机

的搜索优化算法，这其中主要包括遗传算法、进化规划和进化策略，其中针对遗

传算法的研究成为了热门。

在人工智能领域，很多问题需要在复杂且庞大的搜索空间中寻找最优解。如

旅行商问题中求解最短路径、风洞实验中确定气体流中物体的最优外形、管道设

计确定各个管径等[8]，此类问题的求解过程中，如果不能利用问题的固有知识来缩

小搜索空间，则会产生搜索空间的组合爆炸。与传统算法不同，遗传算法能够在

搜索过程中自动获取和积累搜索空间的相关知识，自适应地指导整个搜索过程，

因此非常适合解决复杂的搜索优化问题。

人们在实际的应用过程之中一直在不断发展、更新和完善遗传算法，其中包

括了使用不同编码方式、控制参数的选择以及遗传算子的改进等。除此以外，人

们还在标准遗传算法中引入了动态策略和自适应策略以改善算法的性能。这些改

进的遗传算法可以统称为变形遗传算法，在解决优化调度、组合优化和自动控制

等方面显示了其良好的优越性能，已经成为人们解决复杂问题的新思路。

为了提高遗传算法的性能，还提出了爬山算法、模拟退火算法等优化算法，

它们具有很强的局部搜索能力，将这些优化算法的思想融入到遗传算法中构成的

VCGA 称作混合遗传算法，混合后的算法能够提高遗传算法的运行效率和求解质

量。如模拟退火遗传算法通过控制退火温度参数来调节遗传算法的进化过程，使

进化后期种群中的个体多样性水平得到提升，在解决最优化问题时，使算法能够

跳出局部最优点。模拟退火遗传算法有着非常广泛的应用，如在函数优化、NP 完

全问题[70]、控制参数决策[3][4]及实际应用领域[5]~[8]等中都获良好的效果。

在生物免疫系统相关概念和理论基础上形成了免疫遗传算法，它是另一种混

合遗传算法，在工程应用上也十分广泛。如通过模拟生物自我免疫行为中的抗体

记忆、抗体的抑制、促进和抗原识别等免疫行为设计出的免疫遗传算法，并将它

们应用在 TSP 优化、BP 网络的辅助设计以及多峰值函数优化等问题上，验证了免

疫遗传算法不仅提高了遗传算法的全局搜索能力和局部搜索能力，而且还可以有

效地避免了标准遗传算法出现早熟的现象[1]~[8]。

在计算机免疫学方面，国内外存在着很多研究性课题和实际的工程应用，如

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要遗传算法是一种具有生成加检测迭代过程的搜索算法。种群搜索和种群中个体通过变异算子和交叉算子实现了信息的交换。在算法的迭代进化的过程中，在一定概率的条件下随机产生了交叉算子和变异算子。因此，种群中的个体在变异和交叉算子的作用下得到了进化的机会，但是与此同时也不可避免地出现了退化的现象。通常每一个将要解决的实际问题都会有其自身的一些特征信息，但是在遗传算法中，交叉和变异算子却是相对固定的，在求解问题的过程之中，灵活程度的可变性较小。生物体的免疫系统自身拥有抗原的识别、免疫记忆和维持抗体多样性等特性。本文通过研究这些特性，从而提出了一种改进的免疫遗传算法，此算法将生物系统中的免疫思想引入到标准的...

展开>> 收起<<

免疫遗传算法及其应用研究.pdf

共64页,预览7页

还剩页未读，继续阅读

免疫遗传算法及其应用研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: