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

邹文俊

摘 要：优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。而作为一种优化算法，差分进化算法因其有效性，在现代优化技术和工程实践应用中的作用越来越凸显。阐述了差分进化算法的基本概念，对差分简化算法的原理进行了介绍，对算法步骤进行了论述，并结合一物流配送路径优化例子，重点围绕该算法的设计进行分析，为差分进化算法的应用提供了思路。

关键词：差分进化算法；算法设计；应用

中图分类号：G4 文献标识码：Adoi：10.19311/j.cnki.1672-3198.2018.08.072

0 引言

差分进化算法 （Differential Evolution ，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）交叉。

差分进化算中的交叉操作是对产生下一代染色体的一个重要的操作步骤，实现过程为将参与变异操作步骤中的“优秀染色体”与变异操作过程后产生的“变异体”进行交叉产生“试验体”，为了保证变异体的延续性，将“变异体”中的随机一个基因位上的基因作为固定的交叉基因。

（6）选择。

差分进化算法中的选择操作决定了下一代染色体种群中的个体，实现过程为将参与交叉操作的“优秀染色体”与交叉操作后的“试验体”通过适应值评估，选择适应值最优秀的那一个，即是说，下一代染色体的新的个体可能为上一代染色体的个体直接保留下来。

（7）终止条件。

差分进化算法中的终止条件是判断循环迭代次数结束的一个标识，在优化问题的求解过程中，是判断最优解诞生的一个重要依据。如果满足设定的循环迭代终止條件，则代表了最优解的诞生，如果未产生最优解则继续返回步骤（3），进入新一轮的计算。

3 差分进化算法分析

3.1 背景介绍

车辆路径的问题是一种NP-hard的问题，在NP-hard的问题中，车辆路径问题属于最经典也是相对较难的问题。由于车辆路径问题存在的模糊因素以及不定因素较多，因此解决该问题大多采用的是启发式的算法。本文所阐述的差分进化算法就属于启发式的算法中的一种，在解决复杂的全局优化问题方面， 差分进化算法的性能更加优秀，过程也更为简单，受控参数少，可有效用以解决车辆路径的问题。

现某物流有限公司的服务项目以产品配送为主，秉承以客户需求为导向，为客户提供优质的物流配送服务。现配送中心需完成8家客户的配送任务。如何选择最优路径，从而降低配送成本，提升配送效率，是企业需要解决的问题。

3.2 算法设计

差分进化算法的算法设计主要包括编码设计，初始化种群，确定适应值函数，变异，交叉运算和选择这几个步骤。

（1）编码设计。

在利用差分进化算法解决物流配送车辆路径优化问题的最优解之前，需要把配送过程中的相关数据转换为染色体数据。

染色体编码表示需要配送的客户信息，每个自然数代表一个待配送客户。设定染色体表示为：R1=（i1，i2，...，in），（n为自然数）例如：经过计算染色体的编码为：

R1=2 5 6 7 8 3 1 4

那么，这条染色体表示为8个终端客户进行物流配送，自然数的排序表示这8个客户的配送路径。

（2）初始化种群。

差分进化算法的随机搜寻起始于随机构成的初代种群，通过不断的一次一次的迭代操作，最终产生最优的结果。初始化种群的数量为X，则每一个染色体对应着3.1中随机产生的结果。此例中的初始化种群，由一定数量的配送路径构成。

（3）确定适应值函数。

差分进化算法中的适应值函数是算法中至关重要的一个参数，是评判种群中个体好坏的最基本也是最重要的条件，更是评判差分进化算法是否继续进行下去的一个标识。本文中，用车辆配送成本作为适应值函数，用以判断配送路径是否最合理。

（4）变异。

差分进化算法中，变异是必定会进行的一个过程。利用从种群中随机选取的两个个体的差向量作为第三个个体的随机变化源，将差向量加权后按照一定的规则与第三个个体求和而产生“变异体”。差分进化算法中，变异有两种方式，第一种是差分离散运算算法：

通过公式V = R1 | F×（R2 & R3）计算得出变异体V。其中，设定D=R2&R3，即V = R1 | F×D。

④离散算法后的验证。

在得出最终结果后，需要进行一次验证，因为在进行计算后，可能得出的路径中会出现超出取值范围的数值。比如只有8条路径，但最终得出的结果为1 12 2 3 4 5 6 8。其中出现了12的数值，则该条变异路径为废解，需要剔除。

差分进化算法变异的第二种方式是差分向量加减运算法：

通过公式V=R1+F×（R2-R3），计算得出变异体V。

由于客户是由一个个自然数表示，所以对计算结果中的小数点需要进行修正。因为与8位客户，所以将结果中最大值和最小值改为8和1，将带有小数的数字按照排序大小优先变为大数值，形成新的路径，如下：

从离散差分算法和加减差分算法的算法设计中来看，虽然离散差分算法的复杂度较高，但是它更接容易进行计算机编码。其中变异步骤使用离散算法可以省略将小数数字转换成整数的步骤，减少不必要的操作和误差。

（5）交叉运算。

变异个体与某个预先决定的目标个体进行参数混合，生成试验个体，这一过程称之为交叉。从之前变异运算的3个父染色体中取得一个适应值最高的出来作为“优选体”。将优选体与变异体进行交叉，交叉完成后的染色体成为“试验体”。

为了将变异体的基因有效的传递下去，所以试验体的一个基因必须先从变异体中随机选取。

从上可以看到，变异体中的随机选取位是7，所以“试验体”的同位素也为7。之后其它位置的基因可以随机从“优选体”和“试验体”中进行选择，形成了一个完整的试验体17675218。

可以发现交叉后的试验体是有重复的数值的，是一条不合格的染色体，所以需要进行一次修正。修正的手法采用逐个基因验证，由上至下进行随机选取，当产生重复数值则往前查找是否某个基因位可以进行替换。比如基因位来源于“变异体”，则尝试替换为“优选体”的基因。再继续往下进行，直至“试验体”的每一个基因位都不重复。

（6）选择。

在交叉运算完成后，会产生一个优选体，一个试验体。此时需要进行一个适应值的评估，使得适应值高的那一个染色体得意被保留，成为下一代种群中的一员。所以下一代种群中的一员可能是优选体，也可能是试验。

4 结束语

智能优化是将人工智能技术与运筹学、控制理论、大系统理论中静态优化、动态优化、多级优化等方法相结合，寻求解决传统优化方法难以解决的多目标、局部解、不确定、未确知、维数灾难等问题的新途径。差分进化算法作为一种新颖的智能优化算法，容易理解，实现简单，具有良好的优化性能，已广泛应用于各种优化问题中。但差分进化算法跟其它进化算法一样存在早熟悉收敛等问题，因此对差分进化算法进行改进，提高其全局搜索能力和收斂速率，使之适应于各种工程实际问题中，是一个值得深入研究的方向。本文以物流配送路径优化为切入点，分析了差分进化算法的基本概念和算法步骤。但是对算法设计的分析还比较浅显，尚未涉及算法在具体案例中应用，将在今后的学习研究中加以完善。

参考文献

[1]Storn R，Price K. Differential evolution — A simple andefficient adaptive scheme for global optimization overcontinuous spaces [R]. Berkeley： University ofCalifornia，2006.

[2]Lampinen J. A bibliography of differential evolutionalgorithm[EB/ OL]. （2002-10-14） . http ：/ / www. lut.fi/ ～ jlampine/ debiblio. htm.

[3]刘波.差分进化算法研究进展[J].控制与决策，2007，22（7）：721-722.

[4]周谦.差分进化算法的应用研究[D].郑州：中原工学院， 2016.

[5]张果果.物流配送路径优化标准的实证研究[J].北京交通大学学报（社会科学版），2016，（03）.

[6]王东健.水产品冷链物流配送中心选址及配送路径优化研究[D].吉林：吉林大学，2015.

[7]袁菁穗.差分演化算法研究综述[J].科技信息， 2010 （26） ：130-131.

[8]杨丹婷.冷链物流配送路径优化研究[D].大连：大连海事大学，2014.