差分进化算法综述概况

1、差分进化算法 (DE )1是 Storn 和 Price 在 1995 年提出的一种基于种群差异的进化算法， DE 是一种随机的并行搜索算法。差分进化计算和其他进化计算算法一样，都是基于群体智 能理论的优化算法， 利用群体内个体之间的合作与竞争产生的群体智能模式来指导优化搜索 的进行。 与其他进化计算不同的是， 差分进化计算保留了基于种群的全局搜索策略， 采用实 数编码、 基于差分的简单变异操作和一对一的竞争生存策略， 降低了进化操作的复杂性。 差 分进化计算特有的进化操作使得其具有较强的全局收敛能力和鲁棒性， 非常适合求解一些复 杂环境中的优化问题。最初试图使用向量差进行向量种群的混洗， 以

2、此来解决切比雪夫多项式适应性问题。 DE 通 过种群内个体间的合作与竞争来实现对优化问题的求解， 其本质上是一种基于实数编码的具 有保优思想的进化算法。 该算法实现技术简单， 在对各种测试问题的实验中表现优异， 已经 成为近年来进化算法研究中的热点之一。差分进化算法基本原理基本的差分进化算法是基于候选方案种群的算法， 在整个搜索空间内进行方案的搜索， 通过 使用简单的数学公式对种群中的现有方案进行组合实现的。 如果新的方案有所改进， 则被接 受，否则被丢弃，重复这一过程直到找到满意的方案。设 f 是最小化适应度函数， 适应度函数以实数向量的形式取一个候选方案作为参数， 给 出一个实数数值作为候

3、选方案的输出适应值。 其目的是在搜索空间的所有方案 p 中找到 m 使得f(m) w f(p)。最大化是找到一个m使得f(m) > f(p)。设X=(x1, x2,xn£ ?n是种群中一个个体，基本的差分进化算法如下所述：? 在搜索空间中随机地初始化所有的个体。? 重复如下操作直到满足终止条件(最大迭代数或者找到满足适应值的个体)o对于种群中的每个个体：随机地从种群中选择三个彼此不同的个体a， b 和 c。选择一个随机索引 R 1, ., n , n是被优化问题的维数。通过对每个i 1,., n进行如下的迭代计算可能的新个体Y = y1, ., yn生成一个随机数 riU(0,

4、1) ；如果 (i=R) 或者 (ri<CR) ， yi = ai + F(bi - ci )，否则 yi = xi ；如果(f(yi) < f(xi)，则在种群中使用改进的新生成的yi替换原来的xi,否则不变。选择具有最小适应度值的 xi 作为搜索的结果。需要指出的是 F 0,2 称为缩放因子， CR 0,1称为交叉因子，种群大小 NP>3。 差分进化算法作为一种新出现的优化算法在实际应用中表现出了优异的性能，被广泛应用到不同的领域， 已经成为近年来优化算法的研究的热点之一。 研究差分进化算法， 探索提高差 分进化算法性能的新方法， 并将其应用到具体工程问题的解决中， 具有

5、重要的学术意义和应 用价值。差分进化计算的群体智能搜索策略分析1 个体行为及个体之间信息交互方法分析 差分进化的个体表示方式与其他进化计算相同，是模拟生物进化中的关键因素，即生物的染色体和基因， 构造每个解的形式， 构成了算法的基础。 一切的寻优操作都是在个体的基础 上进行的，最优个体是搜寻到的最优的解。差分进化的个体行为主要体现在差分变异算子和交叉算子上。1) 变异算子 在差分进化计算中， 美国基因位的改变值取决于其他个体之间的差值， 充分利用了群体中其 他个体的信息， 达到了扩充种群多样性的同时， 也避免了单纯在个体内部进行变异操作所带 来的随机性和盲目性，在随机向量差分法中每个个体的变异

6、取决于两个随机个体的向量差： 采用最优解加随机向量差分法， 每个个体由当前最优解决定， 分布在当前最优解的邻域范围 内，利用了当前最优种群最优个体的信息，加速了搜索速度，但同时如果种群分布密度高， 可能会导致算法陷入局部最优解； 采用最优解与随机向量差分法， 用个体局部信息和群体全 局信息指导算法进一步搜索的能力，较最优解加随机向量法降低了陷入局部最优解的危险。 当向量偏差大时，导致个体的变异强度高；反之， 个体的变异强度低。 差分进化计算域种群 的分布密度相关，因此如果种群分布密度高，则个体的变异强度较低。2) 交叉算子在差分进化计算中， 进行交叉操作的主体是父代个体和由它经过差分变异操作后

7、得到的 新个体，虽然这种方法看似没有进行个体之间的信息交互，但由于新个体经过差分变异 而来，本身保存有种群中其他个体的信息，因此差分进化的交叉算子同样具有个体之间 信息交互的机制。2 群体进化分析与其他进化计算相同， 差分进化计算模拟生物进化过程， 使得种群的衍化想着更好的方向 前进。 通过每一代群体的变异、 交叉操作产生新的种群， 并通过贪婪选择的方式选择优秀的 个体， 组成下一代的进化群体。 这种方式可以保证群体的优良性， 并加快寻优速度，但也有 其不足，即容易陷入局部最优。差分进化计算的群体在寻优的过程中， 具有协同搜索的特点， 搜索能力强。 最优解加随机向 量差分法充分利用当前最优解来

8、优化每个个体， 利用个体局部信息和群体全局信息指导算法 进一步搜索的能力。 这两种方法的群体具有记忆个体最优解的能力。 在进化过程中， 充分利 用种群繁衍进程中产生的有用信息。差分进化计算作为一种模拟自然进化现象的随机搜索算法，虽然有可能实现全局最优搜 索，但也有出现早熟的弊端。种群在开始时有较分散的随机配置， 但是随着进化的进行，各 代之间种群分布密度偏高， 信息的交换逐渐减少， 使得全局寻优能力逐渐下降。 种群中各个 个体的进化， 采用贪婪选择操作， 依靠适应着的高低做简单的好坏判断， 缺乏深层的理性分 析。参考文献：1Storn R, Price K. Differential Evol

9、ution - A Simple and Efficient Heuristic for GlobalOptimizati on over Contin uous SpacesJ. Journal of Global Optimizatio n. 1997(11): 341 -359.聚类分析的主要目的是通过对数据集的合理划分来发现数据集的结构特征， 利用聚类结 果，我们能够提取数据集中隐藏的信息， 对未来数据进行预测和分类。 例如，在许多具体问 题中，描述问题的实际数据是容易得到的， 但是隐藏在数据中的内在信息或知识却不容易直 接获得。因此， 需要对数据进行分析和分类， 从中提取有效信息。 而随着数据库技术的不断 发展，许多应用领域都会产生远远超出人类的直接处理能力的大量的实际数据。 为了能更方 便的理解和表示这些数据， 需要进行数据压缩， 同时又要尽量保持原数据的隐含信息。 这些具体问题的解决就要用到聚类及相关算法。例如，气象灾害会给国家和人民群众带来很大损失，将差分进化聚类算法应用于灾害性天气预报中，若能达到很好的预报准确率，可以减小气象灾害带给国家和人民的损失，可以造福社会和人民。同时将算法应用到UCI中一些数据的聚类和分类中，女口 lris,WineData,Echocardiogram等数