差分进化算法和遗传算法

差分进化算法DE-DifferentialEvolution

差分进化算法 (Differential Evolution)

Differential Evolution（DE）是由Storn等⼈于1995年提出的，和其它⼀样，DE是⼀种模拟⽣物进化的，通过反复，使得那些适应环境的个体被保存了下来。但相⽐于进化算

法，DE保留了基于种群的全局搜索策略，采⽤实数编码、基于差分的简单变异操作和⼀对⼀的竞争⽣存策略，降低了遗传操作的复杂性。同时，DE特有的记忆能⼒使其可以动

态跟踪当前的搜索情况，以调整其搜索策略，具有较强的全局收敛能⼒和，且不需要借助问题的特征信息，适于求解⼀些利⽤常规的数学规划⽅法所⽆法求解的复杂环境中的优

化问题。⽬前，DE已经在许多领域得到了应⽤，譬如⼈⼯⽹络、化⼯、电⼒、机械设计、机器⼈、信号处理、⽣物信息、经济学、现代农业、⾷品安全、环境保护和运筹学

等。

DE算法-作者⽹站:

维基百科资料库 :

DE 算法主要⽤于求解的全局优化问题，其主要⼯作步骤与其他基本⼀致，主要包括变异(Mutation)、交叉(Crossover)、选择(Selection)三种操作。算法的基本思想是从某⼀随机

产⽣的初始群体开始，利⽤从种群中随机选取的两个个体的差向量作为第三个个体的随机变化源，将差向量加权后按照⼀定的规则与第三个个体求和⽽产⽣变异个体，该操作称

为变异。然后，变异个体与某个预先决定的⽬标个体进⾏参数混合，⽣成试验个体，这⼀过程称之为交叉。如果试验个体的适应度值优于⽬标个体的适应度值，则在下⼀代中试

验个体取代⽬标个体，否则⽬标个体仍保存下来，该操作称为选择。在每⼀代的进化过程中，每⼀个体⽮量作为⽬标个体⼀次，算法通过不断地迭代计算，保留优良个体，淘汰

劣质个体，引导搜索过程向全局逼近。

算法图解:

算法伪代码:

算法C代码:

1 //********************************************************/

1．差分进化算法背景

差分进化(Differential Evolution，DE)是启发式优化算法的一种，它是基于群体差异的启发式随机搜索算法，该算法是Raincr Stom和Kenneth Price为求解切比雪夫多项式而提出的。差分进化算法具有原理简单、受控参数少、鲁棒性强等特点。近年来，DE在约束优化计算、聚类优化计算、非线性优化控制、神经网络优化、滤波器设计、阵列天线方向图综合及其它方面得到了广泛的应用。

差分算法的研究一直相当活跃，基于优胜劣汰自然选择的思想和简单的差分操作使差分算法在一定程度上具有自组织、自适应、自学习等特征。它的全局寻优能力和易于实施使其在诸多应用中取得成功。

2.差分进化算法简介

差分进化算法采用实数编码方式，其算法原理同遗传算法相似刚，主要包括变异、交叉和选择三个基本进化步骤。DE算法中的选择策略通常为锦标赛选择，而交叉操作方式与遗传算法也大体相同，但在变异操作方面使用了差分策略，即：利用种群中个体间的差分向量对个体进行扰动，实现个体的变异。与进化策略(Es)采用Gauss或Cauchy分布作为扰动向量的概率密度函数不同，DE使用的差分策略可根据种群内个体的分布自动调节差分向量(扰动向量)的大小，自适应好；DE的变异方式，有效地利用了群体分布特性，提高了算法的搜索能力，避免了遗传算法中变异方式的不足。

3.差分进化算法适用情况

差分进化算法是一种随机的并行直接搜索算法，最初的设想是用于解决切比雪夫多项式问题，后来发现差分进化算法也是解决复杂优化问题的有效技术。它可以对非线性不可微连续空间的函数进行最小化。目前，差分进化算法的应用和研究主要集中于连续、单目标、无约束的确定性优化问题，但是，差分进化算法在多目标、有约束、离散和噪声等复杂环境下的优化也得到了一些进展。

4.基本DE算法

差分进化算法把种群中两个成员之间的加权差向量加到第三个成员上以产生新的参数向量，这一操作称为“变异”。然后，变异向量的参数与另外事先确定的目标向量按一定规则混合产生试验向量，称为“交叉”。如果实验向量代价函数比目标向量代价函数低，则实验向量则在下代中替代目标向量。这一操作称为“选择”，种群中所有与成员必须作为目标向量按这样操作一次，以在下代中出现相同个竞争者。进化过程中对每一代都评价最佳参数向量，以记录最小化过程，以这种方式利用随机偏差扰动产生新个体可以获得有较好收敛性的结果。

差分进化算法入门

1 / 91

差分进化算法-入门差分进化算法入门

2 / 92

差分进化算法入门

3 / 93

———————————————————————————————— 作者：

———————————————————————————————— 日期： 差分进化算法入门

4 / 94

基本差分进化算法

１基本差分进化算法的基本思想 ＤE算法是一种鉴于实数编码的用于优化函数最小值的进化算法，是在求解相关切比雪夫多项式的问题时提出来的,是鉴于集体差别的进化计算方法。它的整体构造近似于遗传算法，同样都存在变异、交错和选择操作，可是它又不一样于遗传算法。与基本遗传算法的主要差别在于变异操作上,如： 1、传统的遗传算法采纳二进制编码 ,而差分进化算法采纳实数编码。 2、在遗传算法中经过两个父代个体的交错产生两个子个体，而在差分进化 算法中经过第两个或几个个体的差分矢量做扰动来产生新个体。 3、在传统的遗传算法中，子代个体以必定概率代替其父代个体，而在差分 进化中新产生的个体只有当它比种群中的个体优秀时才替代种群中的个体。 变异是DE算法的主要操作，它是鉴于集体的差别向量来修正各个体的值,其基来源理是经过把种群中两个个体的向量差加权后,按必定的规划与第三个个体乞降来产生新个体，而后将新个体与今世种群中某个早先决定的个体对比较， 假如新个体的目标值优于与之对比较的个体的目标值,则在下一代中就用新个体代替,不然,旧个体仍保存下来。 差分进化算法其基本思想是:第一由父代个体间的变异操作组成变异个体；接着按必定的概率,父代个体与变异个体之间进行交错操作，生成一试验个体;而后 在父代个体与试验个体之间依据适应度的大小进行贪心选择操作,保存较优者，实现种群的进化。 差分进化算法的基本操作 设目行进化代数为t，集体规模为NP,空间维数为D，目前种群为

X(t)x1t,x2t,,xNPt ，xit xit 1,xit 2,,xiDt T

MOGA

ix是第t代种群中个体，其rank值定义为：

()(,)1tiirankxtp

()tip为第t代种群中所有支配ix的个体数目

适应值（fitness value）分配算法：

1、 将所有个体依照rank值大小排序分类；

2、 利用插值函数给所有个体分配适应值（从rank1到

rank *nN），一般采用线性函数

3、 适应值共享:rank值相同的个体拥有相同的适应值，

保证后期选择时同一rank值的个体概率相同

最后采用共享适应值随机选取的方法选择个体进入下一代

一种改进的排序机制（ranking scheme)：

向量,1,(,,)aaaqyyy和,1,(,,)bbbqyyy比较

goal vector：1,,qggg

分为以下三种情况:

1、,,1,,1; 1,,;1,,; aiiajjkqikjkqygyg

2、,1,,; aiiiqyg

当ay支配by时,选择ay

3、,1,,; ajjjqyg

当by支配ay时，选择by

优点:算法思想容易，效率优良

缺点：算法容易受到小生境的大小影响

理论上给出了参数share的计算方法

NPGA

基本思想：

1、初始化种群Pop

2、锦标赛选择机制:随机选取两个个体1x和2x和一个Pop的

子集CS（Comparison Set）做参照系。若1x被CS中不少于一

个个体支配,而2x没有被CS中任一个体支配,则选择2x。

3、其他情况一律称为死结（Tie），采用适应度共享机制选择.

个体适应度:if

小生境计数(Niche Count）：,ijPopmShdij

共享函数:1-,()0,shareshareshareddShdd

共享适应度(the shared fitness）:iifm