一、差分进化算法的介绍
差分进化算法(Differential Evolution, DE)是一种基于群体差异的启发式随机搜索算法,该算法是由R.Storn和K.Price为求解Chebyshev多项式而提出的。DE算法也属于智能优化算法,与前面的启发式算法,如ABC,PSO等类似,都属于启发式的优化算法。DE算法是我在一篇求解盒子覆盖问题论文中使用的一种优化算法。
二、差分进化算法的流程
初始化种群变异交叉选择(DE流程)
三、差分进化的具体步骤
对于无约束优化问题
利用差分进化求解这样的优化问题,主要分为初始化、变异、交叉和选择等几项操作。
1、初始化
如前面的的群智能优化算法一样,差分进化也需要初始化种群:
其中,是第个个体,表示第维。
其中,和分别为第维的下界和上界,表示在区间上的随机数。
2、变异
DE算法通过差分策略实现个体变异,常见的差分策略是随机选取种群中两个不同的个体,将其向量差缩放后与待变异个体进行向量合成。
其中,,和是三个随机数,区间为,称为缩放因子,为一个确定的常数。表示第代。
3、交叉
交叉操作的目的是随机选择个体,因为差分进化也是一种随机算法,交叉操作的方法是:
其中,称为交叉概率。通过概率的方式随机生成新的个体。
4、选择
在DE中采用的是贪婪选择的策略,即选择较优的个体作为新的个体。
四、实际的优化问题
求解优化问题:
一、Java实现
package org.zzy.de;import java.util.Random;public class Population {public static int NP = 1000;// 种群规模public static int size = 10;// 个体的长度public static int xMin = -10;// 最小值public static int xMax = 10;// 最大值public static double F = 0.5;// 变异的控制参数public static double CR = 0.8;// 杂交的控制参数private double X[][] = new double[NP][size];// 个体private double XMutation[][] = new double[NP][size];private double XCrossOver[][] = new double[NP][size];private double fitness_X[] = new double[NP];// 适应值public double[][] getX() {return X;}/*** 矩阵的复制* * @param x把x复制给个体*/public void setX(double x[][]) {for (int i = 0; i < NP; i++) {for (int j = 0; j < size; j++) {this.X[i][j] = x[i][j];}}}public double[] getFitness_X() {return fitness_X;}public void setFitness_X(double[] fitness_X) {for (int i = 0; i < NP; i++) {this.fitness_X[i] = fitness_X[i];}}public double[][] getXMutation() {return XMutation;}public void setXMutation(double xMutation[][]) {for (int i = 0; i < NP; i++) {for (int j = 0; j < size; j++) {this.XMutation[i][j] = xMutation[i][j];}}}public double[][] getXCrossOver() {return XCrossOver;}public void setXCrossOver(double xCrossOver[][]) {for (int i = 0; i < NP; i++) {for (int j = 0; j < size; j++) {this.XCrossOver[i][j] = xCrossOver[i][j];}}}/*** 适应值的计算* * @param XTemp根据个体计算适应值* @return返回适应值*/public double CalculateFitness(double XTemp[]) {double fitness = 0;for (int i = 0; i < size; i++) {fitness += XTemp[i] * XTemp[i];// 做一个X的平方相加的函数}return fitness;}/*** 初始化:随机初始化种群,计算个体的适应值*/public void Initialize() {double XTemp[][] = new double[NP][size];double FitnessTemp[] = new double[NP];Random r = new Random();for (int i = 0; i < NP; i++) {for (int j = 0; j < size; j++) {XTemp[i][j] = xMin + r.nextDouble() * (xMax - xMin);}// 计算适应值FitnessTemp[i] = CalculateFitness(XTemp[i]);}this.setX(XTemp);this.setFitness_X(FitnessTemp);}/******** 变异操作 ***********/public void Mutation() {double XTemp[][] = new double[NP][size];double XMutationTemp[][] = new double[NP][size];XTemp = this.getX();Random r = new Random();for (int i = 0; i < NP; i++) {int r1 = 0, r2 = 0, r3 = 0;while (r1 == i || r2 == i || r3 == i || r1 == r2 || r1 == r3|| r2 == r3) {// 取r1,r2,r3r1 = r.nextInt(NP);r2 = r.nextInt(NP);r3 = r.nextInt(NP);}for (int j = 0; j < size; j++) {XMutationTemp[i][j] = XTemp[r1][j] + F* (XTemp[r2][j] - XTemp[r3][j]);}}this.setXMutation(XMutationTemp);}/*** 交叉操作*/public void CrossOver() {double XTemp[][] = new double[NP][size];double XMutationTemp[][] = new double[NP][size];double XCrossOverTemp[][] = new double[NP][size];XTemp = this.getX();XMutationTemp = this.getXMutation();// 交叉操作Random r = new Random();for (int i = 0; i < NP; i++) {for (int j = 0; j < size; j++) {double rTemp = r.nextDouble();if (rTemp <= CR) {XCrossOverTemp[i][j] = XMutationTemp[i][j];} else {XCrossOverTemp[i][j] = XTemp[i][j];}}}this.setXCrossOver(XCrossOverTemp);}/*** 选择操作:使用贪婪选择策略*/public void Selection() {double XTemp[][] = new double[NP][size];double XCrossOverTemp[][] = new double[NP][size];double FitnessTemp[] = new double[NP];double FitnessCrossOverTemp[] = new double[NP];XTemp = this.getX();XCrossOverTemp = this.getXCrossOver();// 交叉变异后的个体FitnessTemp = this.getFitness_X();// 对群体进行重新设置for (int i = 0; i < NP; i++) {FitnessCrossOverTemp[i] = CalculateFitness(XCrossOverTemp[i]);if (FitnessCrossOverTemp[i] < FitnessTemp[i]) {for (int j = 0; j < size; j++){XTemp[i][j] = XCrossOverTemp[i][j];}FitnessTemp[i] = FitnessCrossOverTemp[i];}}this.setX(XTemp);this.setFitness_X(FitnessTemp);}/*** 保存每一代的全局最优值*/public void SaveBest() {double FitnessTemp[] = new double[NP];FitnessTemp = this.getFitness_X();int temp = 0;// 找出最小值for (int i = 1; i < NP; i++) {if (FitnessTemp[temp] > FitnessTemp[i]) {temp = i;}}System.out.println(FitnessTemp[temp]);}}
测试
package org.zzy.test;import org.zzy.de.Population;public class DETest {public static void main(String args[]) {int gen = 0;int maxCycle = 1000;Population p = new Population();p.Initialize();// 初始化while (gen <= maxCycle) {p.Mutation();p.CrossOver();p.Selection();gen++;p.SaveBest();}}}
二、收敛曲线
如果觉得《优化算法——差分进化算法(DE)》对你有帮助,请点赞、收藏,并留下你的观点哦!