论文总字数：29297字

摘 要

09015414 黄河

指导老师：蒋嶷川

差分进化算法(Differential Evolution，DE)是一种以遗传算法等进化思想上为基础的一种基于种群的随机优化方法。由于其易于实现、便于理解、较少的控制参数、较快的收敛速度以及较强的鲁棒性等优点，受到许多相关领域专家和学者极大的关注，并被广泛应用于各个领域。尽管差分进化算法己广泛应用于许多重要领域，但是它确实还是存在一些缺点：难以确定合适的参数值、容易产生早熟现象、容易陷入最优。

为了使算法的搜索能力更强、收敛性能更好，并让算法更加适用于更多的领域，本文对差分进化算法从控制参数和变异策略两方面进行了研究，提出了如下两种改进算法：

1. 从变异算子的角度，本文提出了一种基于自适应变异算子的改进算法，在搜索过程中通过个体自身所处的位置来自适应地调整搜索步长，加快了算法的收敛速度。
2. 从变异策略的角度，本文提出了一种基于种群相似度的双变异策略，根据当前种群的相似度来选择合适的变异策略，从而解决了局部搜素和全局搜索的平衡问题，有效地提高算法性能。

通过4个测试函数分别对两个改进算法进行对比实验，实验结果验证了两种改进算法都能有效地加快算法的收敛速度，提高算法的收敛精度。

关键词：差分进化算法，收敛速度，自适应，变异算子，变异策略，种群相似度

Abstract

09015414 He Huang

Advisor: Yichuan Jiang

Differential evolutionary algorithm is a population-based stochastic optimization method based on genetic algorithm and other evolutionary ideas. Because it is easy to implement, easy to understand, less control parameters, higher convergence accuracy, faster convergence speed and stronger robustness, differential evolution algorithm has attracted great attention from many experts and scholars in related fields and has been widely used in various fields. Although differential evolution algorithm has been widely used in many important fields, it does have some shortcomings: it is difficult to determine the appropriate parameters, easy to produce premature phenomena, easy to fall into the optimal.

In order to make the algorithm more searchable, convergent and applicable to more fields, this paper studies the differential evolution algorithm from two aspects of control parameters and mutation strategy, and proposes the following two improved algorithms:

1. From the perspective of mutation operator, an improved algorithm based on adaptive mutation operator is proposed in this paper. In the process of searching, the search step is adjusted adaptively by the position of the individual, which speeds up the convergence speed of the algorithm.

2. From the perspective of mutation strategy, this paper proposes a dual mutation strategy based on population similarity, and chooses the appropriate mutation strategy according to the current population similarity, which solves the problem of balance between local search and global search, improves the performance of the algorithm.

Four test functions are used to compare the two improved algorithms. The experimental results show that the two improved algorithms can effectively accelerate the convergence speed and improve the convergence accuracy of the algorithm.

KEY WORDS: Differential evolutionary algorithm; convergence rate; self-adaption;

Mutation operator; Mutation strategy; Population similarity.

目 录

摘 要 I

Abstract II

第一章 绪论 1

1.1. 课题的背景及意义 1

1.2. 几种典型的智能优化算法 2

1.3. 差分进化算法发展历程及研究现状 4

1.4. 本文的研究内容 6

1.5. 本文的章节安排 6

第二章 差分进化算法 9

2.1. 传统的差分进化算法 9

2.1.1. 种群初始化 10

2.1.2. 变异操作 10

2.1.3. 交叉操作 11

2.1.4. 选择操作 11

2.1.5. 差分进化算法伪代码 12

2.2. 改进的差分进化算法 12

2.2.1. 基于控制参数的改进 13

2.2.2. 基于操作策略的改进 16

2.2.3. 基于混合算法的改进 17

2.3. 本章小结 18

第三章 基于自适应变异算子的改进算法及实验测试 19

3.1. 基于自适应变异算子的改进算法 19

3.1.1. 引言 19

3.1.2. 自适应算子 19

3.1.3. 算法设计 20

3.2. 数值实验 20

3.2.1. 实验设置 20

3.2.2. 实验结果及分析 21

第四章 基于种群相似度的双变异策略改进算法及实验测试 24

4.1. 基于种群相似度的双变异策略改进算法 24

4.1.1. 双变异策略 24

4.1.2. 种群相似度 24

4.1.3. 算法设计 24

4.2. 数值实验 25

4.2.1. 实验设置 25

4.2.2. 实验结果及分析 26

第五章 总结与展望 28

5.1. 总结 28

5.2. 未来展望 28

参考文献 30

致 谢 33

绪论

课题的背景及意义

伴随着在人工智能及工程技术等领域中生物学中的进化论的广泛应用，逐渐出现了一种全新的优化算法，即进化计算。这种算法是受到了达尔文提出的“适者生存、优胜劣汰”的思想所产生的。首先在规定范围内初始化种群，然后通过变异、交叉、重组以及选择这一系列步骤，将生物学中的遗传过程融入于算法中，用这样的方式产生候选解，一步步地逼近问题的最优解。

进化计算借助了优化搜索技术，首先初始化种群，紧接着对种群进行变异和重组操作，然后从每一代种群中挑选出适应度值最优对应的解。进化计算中有进化算法及群体智能算法这两类算法。作为进化计算的子领域之一，进化算法是模拟生物界的遗传变异来求解实际问题和处理信息的一种优化算法。总而言之，它是受到繁衍、变异、重组、自然选择和适者生存这些生物进化论的启发而出现的一种执行模式。关于进化算法的研究开始于20世纪50年代末。大家普遍认为，进化算法大致分为三个组成部分：遗传算法、进化规划和进化策略。遗传算法是由美国学者J. Holland于20世纪70年代提出的^[1,2]。而进化规划是是由来自美国学者的L. J. Fogel等与20世纪60年代提出的一种用来求解目标函数最小化的有限状态机的进化模型^[3]。此外，在20世纪90年代D.B.Fogel拓展了进化规划^[4]从而让它的适用范围扩展至于实数空间。而德国的科学家I. Rechenberg 和 Hans-Paul chwefel 也于20世纪60年代提出了一种优化算法，即进化策略^[5]。然后，来自德国的 Schwefel 对原本单一的进化策略和进化操作进行了拓展与改进，使其不再只有突变，还包含重组，并且进化的对象也从一开始的单个个体发展为包含所有个体的整个种群^[6]。自从1985年第一届国际进化算法的会议中正式确立了进化算法独立发展的地位后，进化算法开始迅速发展起来。随着研究的深入，在1995年Rainer Storn和Kenneth 基于遗传算法等进化思想上提出了一种基于种群的随机优化方法——差分进化算法(Differential Evolution，DE)^[7]。由于进化算法对于最优化问题的要求极少，因此被视为一种后设启发式算法。虽然后设启发式算法适用于多种最优化问题，但是并不保证可以找到全局最优解。差分进化算法常常运用在多维度实数编码的最优化问题，因为此算法不使用问题的梯度信息，故可解不可微分的最优化问题。也正因为如此，差分进化算法可以用于不连续的，时变的最优化问题。与其它进化算法相比，DE算法主要通过变异算子和交叉算子以及选择策略来对来自父代种群中的个体进行扰动变化从而生成新的子群体，经过不断地迭代最后使种群在迭代完成时获得最优解。由于其易于实现、便于理解、较少的控制参数、较高的收敛精度和较快的收敛速度以及较强的鲁棒性等优点^[8,9]，因此差分进化算法自提出以来就受到许多相关领域专家和学者极大的关注，被广泛应用于图像处理^[10]、组合优化^[11]、数值优化^[12]等领域，也成为进化算法这个领域的一个研究热点。

剩余内容已隐藏，请支付后下载全文，论文总字数：29297字