🐼差分进化算法DE
2021-10-15
| 2023-8-6
0  |  阅读时长 0 分钟
type
status
date
slug
summary
tags
category
icon
password
Property

原理

差分进化算法是基于群体智能理论的优化算法,是通过群体内个体间的合作与竞争而产生的智能优化搜索算法。但相比于进化计算,它保留了基于种群的全局搜索策略,采用实数编码、基于差分的简单变异操作和“一对一”的竞争生存策略,降低了进化计算操作的复杂性。同时,差分进化算法特有的记忆能力使其可以动态跟踪当前的搜索情况,以调整其搜索策略,它具有较强的全局收敛能力和稳健性,且不需要借助问题的特征信息,适用于求解–些利用常规的数学规划方法很难求解甚至无法求解的复杂优化问题。因此,差分进化算法作为一种高效的并行搜索算法,对其进行理论和应用研究具有重要的学术意义和工程价值。 差分进化算法是一种自组织最小化方法,用户只需很少的输入。它的关键思想与传统进化方法不同:传统方法是用预先确定的概率分布函数决定向量扰动;而差分进化算法的自组织程序利用种群中两个随机选择的不同向量来干扰一个现有向量,种群中的每一个向量都要进行干扰。差分进化算法利用一个向量种群,其中种群向量的随机扰动可独立进行,因此是并行的。如果新向量对应函数值的代价比它们的前辈代价小,它们将取代前辈向量。同其他进化算法一样,差分进化算法也是对候选解的种群进行操作,但其种群繁殖方案与其他进化算法不同:它通过把种群中两个成员之间的加权差向量加到第三个成员上来产生新的参数向量,该操作称为“变异”;然后将变异向量的参数与另外预先确定的目标向量参数按一定规则混合来产生试验向量,该操作称为“交叉”;最后,若试验向量的代价函数比目标向量的代价函数低,试验向量就在下一代中代替目标向量,该操作称为“选择”。种群中所有成员必须当作目标向量进行一次这样的操作,以便在下一代中出现相同个数竞争者。在进化过程中对每一代的最佳参数向量都进行评价,以记录最小化过程。这样利用随机偏差扰动产生新个体的方式,可以获得一个收敛性非常好的结果,引导搜索过程向全局最优解逼近。

差分进化引入的意义

遗传算法的变异操作,就是对个体的某个或某段基因进行随机变换,得到新的个体,也就是新的一组解。它的目的是通过生成新的解,来试图找到更优的选择。
但是,直观上能想到的是,经过变异之后,新的那段基因,可能是和原先种群中所有的个体中,所对应的所有基因中,有重合的。这就意味着,这次变异是没有意义的变异,并没有产生新的解,还是和原来的有的解一样。
造成的后果也不难想到。当到了优化的后期,整个种群有可能陷入了局部最优。这时候,就需要让解能够跑出那个局部最优的圈圈中,而“无效”的变异,并不能达成目的。因此,我们希望,变异操作后的解,是能够“与众不同”的,和当前的所有解区分开来,从而有可能碰上全局最优。
实现方法的核心公式如下:
个个体, 是缩放因子, 是新生成的解, 表示第几代
可以直观看出,这个算法,通过将某两个现有个体的差,进行缩放后,再加到另一个个体中,从而达到变异的目的。
通过缩放,就能确保新的解,离原来的几个解都有一定的距离,保证其探索能力。
 
这个公式只涉及到三个个体,那如果新的个体跟这三个个体之外的其它个体,发生雷同呢,不是也就没有用了吗?
这个情况,在算法执行初,是有可能存在的。但是当算法执行到后期时,显然大部分的解都是较为接近的。因此通过这方法,产生的新个体,只要和这三个差异大,就基本是和全部个体差异都比较大。因此,是能达到预期效果的。

基本差分进化算法流程

notion image

初始化

差分进化算法利用 个维数为 的实数值参数向量,将它们作为每–代的种群,每个个体表示为:
表示个体在种群中的序列; 表示进化代数; 表示种群规模,在最小化过程中保持不变。 一般初始化,设置数值为上下界限之间的随机数

变异

对于每个目标向量 ,基本差分进化算法的变异向量由下式产生:
式中:随机选择的序号 互不相同,且 与目标向量序号 也应不同,所以必须满足NP≥4;变异算子 是一个实常数因数,它控制偏差变量的放大作用。

交叉

为了增加干扰参数向量的多样性,引入交叉操作,则试验向量变为:
式中: 表示产生 之间随机数发生器的第个估计值; 表示一个随机选择的序列,用它来确保 至少从 获得一个参数: CR 表示交叉算子,其取值范围为

选择

为决定试验向量 是否会成为下一代中的成员,差分进化算法按照贪婪准则将试验向量与当前种群中的目标向量 进行比较。如果目标函数要被最小化,那么具有较小目标函数值的向量将在下一代种群中出现。下一代中的所有个体都比当前种群的对应个体更佳或者至少一样好。注意:在差分进化算法选择程序中,试验向量只与一个个体相比较,而不是与现有种群中的所有个体相比较

边界条件处理

判断是否满足约束条件,如果不满足,有两个策略:超出边界的放到边界上。或者超出边界的,重新初始化。

其他差分算法

变异形式
notion image
交叉形式:如指数交叉等
 

改进的差分进化算法

自适应的差分算法

自适应的变异算子可设置为
式中: 表示变异算子, 表示最大进化代数, 表示当前进化代数。在算法开始时自适应变异算子为 ,具有较大值,在初期保持个体多样性,避免“早熟”;随着算法的进展,变异算子逐步降低,到后期变异率接近 ,保留优良信息,避免最优解遭到破坏,增加搜索到全局最优解的概率。
还可设计一个随机范围的交叉算子CR: 0.5*[1 + rand(0,1)],这样交叉算子的平均值保持在0.75,考虑到了差分向量放大中可能的随机变化,有助于在搜索过程中保持群体多样性。

离散差分算法

差分进化算法采用浮点数编码,在连续空间进行优化计算,是一种求解实数变量优化问题的有效方法。要将差分进化算法用于求解整数规划或混合整数规划问题,必须对差分进化算法进行改进。差分进化算法的基本操作包括变异、交叉和选择操作,与其他进化算法一样也是依据适应度值大小进行操作。根据差分进化算法的特点,只要对变异操作进行改进就可以将差分进化算法用于整数规划和混合整数规划。对于整数变量,可对差分进化算法变异操作中的差分矢量进行向下取整运算,从而保证整数变量直接在整数空间进行寻优,即:

代码

求函数 的最小值,其中 的取值范围为 , 的取值范围为 。 这是一个有多个局部极值的函数
notion image
notion image
 
 
用离散差分进化算法求函数 f(x,y)= -((x^2 +y- 1)+(x+y^3- -7)^2) /200+10的最大值,其中x的取值为-100~ 100之间的整数, y的取值为-100~ 100之间的整数
notion image
notion image
 
 
 
notion image
 

调库实现DE

notion image
 
DE输入参数
入参
默认值
意义
func
-
目标函数
n_dim
-
目标函数的维度
size_pop
50
种群规模
max_iter
200
最大迭代次数
prob_mut
0.001
变异概率
F
0.5
变异系数
lb
-1
每个自变量的最小值
ub
1
每个自变量的最大值
constraint_eq
空元组
等式约束
constraint_ueq
空元组
不等式约束
DE输出参数
  • de.generation_best_Y 每一代的最优函数值
  • de.generation_best_X 每一代的最优函数值对应的输入值
  • de.all_history_Y 每一代每个个体的函数值
  • de.best_y 最优函数值
  • de.best_x 最优函数值对应的输入值
 
 
  • Scikit-opt
  • 遗传算法GA粒子群算法PSO
    目录