差分进化算法的算法设计研究
优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。而作为一种优化算法，差分进化算法因其有效性，在现代优化技术和工程实践应用中的作用越来越凸显。阐述了差分进化算法的基本概念，对差分简化算法的原理进行了介绍，对算法步骤进行了论述，并结合一物流配送路径优化例子，重点围绕该算法的设计进行分析，为差分进化算法的应用提供了思路。
标签：差分进化算法；算法设计；应用
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为自然数）例如：经过计算染色体的编码为：
