优化算法——差分进化算法(DE)

一、差分进化算法的介绍

   差分进化算法(Differential Evolution, DE)是一种基于群体差异的启发式随机搜索算法,该算法是由R.Storn和K.Price为求解Chebyshev多项式而提出的。DE算法也属于智能优化算法,与前面的启发式算法,如ABC,PSO等类似,都属于启发式的优化算法。DE算法是我在一篇求解盒子覆盖问题论文中使用的一种优化算法。

二、差分进化算法的流程

  1. 初始化种群
  2. 变异
  3. 交叉
  4. 选择
(DE流程)

三、差分进化的具体步骤

   对于无约束优化问题

利用差分进化求解这样的优化问题,主要分为初始化、变异、交叉和选择等几项操作。

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,r3
				r1 = 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();
		}
	}

}

二、收敛曲线

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习那些事儿

利用pytorch实现GAN(生成对抗网络)-MNIST图像-cs231n-assignment3

In 2014, Goodfellow et al. presented a method for training generative models cal...

67950
来自专栏新智元

【一文看尽200篇干货】2018最新机器学习、NLP、Python教程汇总!

【新智元导读】本文收集并详细筛选出了一系列机器学习、自然语言处理、Python及数学基础知识的相关资源和教程,数目多达200种!来源既包括斯坦福、MIT等名校,...

22740
来自专栏小鹏的专栏

tf25: 使用深度学习做阅读理解+完形填空

记的在学生时代,英语考试有这么一种类型的题,叫:阅读理解。首先让你读一段洋文材料,然后回答一些基于这个洋文材料提的问题。 我先给你出一道阅读理解 Big ...

66050
来自专栏人工智能头条

递归神经网络不可思议的有效性(上)

34640
来自专栏量化投资与机器学习

【Python机器学习】系列之特征提取与处理篇(深度详细附源码)

第1章 机器学习基础 将机器学习定义成一种通过学习经验改善工作效果的程序研究与设计过程。其他章节都以这个定义为基础,后面每一章里介绍的机器学习模型都是按照这个...

1.9K70
来自专栏机器学习、深度学习

特征匹配--GMS: Grid-based Motion Statistics for Fast, Ultra-robust Feature Correspondence

GMS: Grid-based Motion Statistics for Fast, Ultra-robust Feature Correspondence ...

43960
来自专栏WOLFRAM

用 Mathematica 玩转环面

30450
来自专栏大数据挖掘DT机器学习

机器学习算法-决策树C4.5练习

决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则对应...

40760
来自专栏AI研习社

教你几招搞定 LSTMs 的独门绝技(附代码)

如果你用过 PyTorch 进行深度学习研究和实验的话,你可能经历过欣喜愉悦、能量爆棚的体验,甚至有点像是走在阳光下,感觉生活竟然如此美好 。但是直到你试着用 ...

73910
来自专栏AI研习社

无监督聚类问题中,如何决定簇的最优数量?

编者按:聚类问题有一大经典难题:没有数据集的真实分类情况,我们怎么才能知道数据簇的最优数目? 本文会谈谈解决该问题的两种流行方法:elbow method(肘子...

37880

扫码关注云+社区

领取腾讯云代金券