差分进化算法的算法设计研究.pdfVIP

差分进化算法的算法设计研究

优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。

而作为一种优化算法，差分进化算法因其有效性，在现代优化技术和工程实践应

用中的作用越来越凸显。阐述了差分进化算法的基本概念，对差分简化算法的原

理进行了介绍，对算法步骤进行了论述，并结合一物流配送路径优化例子，重点

围绕该算法的设计进行分析，为差分进化算法的应用提供了思路。

标签：差分进化算法；算法设计；应用

0引言

差分进化算法（DifferentialEvolution，DE）是一种新兴的进化计算技术。

它是由R.Storn和K.Price于1995年提出的，最初的设想是用于解决切比雪夫

多项式问题，后来发现DE也是解决复杂优化问题的有效技术。DE特有的记

忆能力使其可以动态跟踪当前的搜索情况，以调整其搜索策略，具有较强的全局

收敛能力和鲁棒性，且不需要借助问题的特征信息，适于求解一些利用常规的数

学规划方法所无法求解的复杂环境中的优化问题。近年来，DE已经在许多领域

得到了应用，譬如人工神经元网络、化工、电力、机械设计、信号处理、路径优

化等。

1差分进化算法概述

1.1概念

差分进化算法是一种强调在全局中寻找最优解的技术，即通过种群内个体间

的合作与竞争来实现对优化问题的求解，其本质是一种基于实数编码的具有保优

思想的贪婪遗传算法，是一种以“适者生存”的理念来进行“优胜劣汰”的智能型算

法，同时，差分进化算法在对问题的求解过程中采用了并行搜索的实现方式，通

过该方式，大大减少了对问题求解过程中所需要的时间。差分进化算法通过非常

简单的算法结构，趋于智能化的适应条件判断来进行新一代种群的生成，并最终

通过适应条件判断来选出全局的最优方案。

1.2优点

差分进化计算是一种具有鲁棒性的方法，能适应不同的环境不同的问题，而

且在大多数情况下都能得到比较满意的有效解。它对问题的整个参数空间给出一

种编码方案，而不是直接对问题的具体参数进行处理，不是从某个单一的初始点

开始搜索，而是从一组初始点搜索。搜索中用到的是目标函数值的信息，可以不

必用到目标函数的导数信息或与具体问题有关的特殊知识。因而进化算法具有广

泛的应用性，高度的非线性，易修改性和可并行性。

2差分进化算法的原理

2.1差分进化算法

差分进化算法具备适应性较高的特征，在求解过程中寻找最优解的问题上，

即使进化机制存在一定的不规则性、适应度不合适的问题，但进化的本身是对全

局进行搜索来实现的，容易实现全局上的最优解。同时，差分进化算法在求解最

优解的过程中运用了并行的搜索方式，大大提高问题的求解速度。其中，初始种

群中的每一个染色体则看作是一个解。在每一代的染色体间进行变异、交叉、选

择实现生成下一代染色体，并保证染色体种群的整体质与量。通过不断的迭代，

通过适应值的评估选择最优的解来作为问题最终的答案。

2.2差分进化算法步骤

遗传算法的主要步骤可分为以下几个步骤：

（1）染色体编码。

在利用差分进化算法解决相关问题的最优解之前，需要把实际应用问题中的

相关数据转换为差分进化算法中的染色体数据。染色体编码就是将实际所求解的

问题向基因编码的映射。染色体是数据的外在表现形式，良好的编码能够直接影

响到对问题求解的过程。

（2）初始化种群。

在差分进化算法中，初始化种群是由一定数量的染色体构成的。通过将基因

进行编码，形成染色体，随机生成一定数量的染色体，使其构成一个一定数量的

种群。

（3）适应值函数。

差分进化算法中的适应值函数是算法中至关重要的一个参数，是评判种群中

个体好坏的最基本也是最重要的条件，更是评判差分进化算法是否继续进行下去

的一个标识，只有适应值高的个体才能够进入下一代算法操作，利用适应值来淘

汰不适应的个体，使得最优解的获取更迅速，也更容易。

（4）变异。

差分进化算法中的变异操作是最为重要的一个步骤，实现过程为在种群中随

机选择三个染色体，将两个适应值较低的2个染色体进行计算，再将结果与适应

值最高的染色体进行计算，获取的结果作为“变异体”供下一步骤使用。

（5）交叉。

差分进化算中的交叉操作是对产生下一代染色体的一个重要的操作步骤，实

现过程为将参与变异操作步骤中的“优秀染色体”与变异操作过程后产生的“变异

体