差分进化算法
source link: https://veviz.github.io/2017/03/02/Differential%20Evolution/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
差分进化算法的简单介绍，学习笔记，记录成长。
一. 算法简介
差分进化算法（Differential Evolution）是一种用于最佳化问题的后设启发式算法。本质上，它是一种基于实数编码的具有保优思想的贪婪算法
差分进化算法类似遗传算法，包含变异、交叉操作，淘汰机制，而差分进化算法与遗传算法不同之处，在于变异的部分是随机选取两个解成员变数的差异，经过伸缩后加入当前解成员的变数上，因此差分进化算法无须使用概率分布产生下一代解成员。1997年，Storn与Price在全域最佳化国际学术期刊（Journal of global optimization）发表了差分进化算法 –维基百科
差分演化算法是演化算法中的一种。演化算法是一种基于种群的启发式算法，其算法过程是模拟生物进化来进行设计的，下面是演化算法的基本结构，其中，t 表示演化代数，P(t) 表示第 t 代群体，每一个个体Xi ( i = 1,2,…,N) 代表一个解，每一个种群代表一组解。
begin
t = 0;
随机初始化种群P(t) = {X1, X2, ... , XN}；
计算 P(t) 中所有个体的适应性；
while(不满足停止条件)
{
将各种遗传算法（如选择、交叉、变异等）作用于群体P(t)，形成新的群体P(t+1);
计算群体P(t+1)中，所有个体的适应性；
t = t + 1;
}
输出结果；
end
总体上看，演化算法主要涉及7个部分的设计：个体的编码表示、初始化种群、适应值函数、遗传操作、选择策略、控制参数以及停止条件。
差分进化算法其整体框架与一般演化算法类似，采用实数编码方式，主要在变异和交叉的遗传操作上略有不同。其变异操作的主要思想是利用种群中其他个体的向量差对目标个体(Target Individual) 进行变异操作，得到变异后的个体–变异个体(Mutant Individual) ；对变异个体和目标个体进行类似一般演化算法的交叉操作，的阿斗一个新个体；通常使用锦标赛策略选择目标个体和新个体中优胜的个体，保留到下一代。
二. 算法详解
差分演化算法的主要操作步骤：
设某优化问题的维度为D，种群规模为N，做一下规定：
第 t 代的第 i 个个体为：Xi(t)Xi(t) ,它变异后的个体为：Hi(t+1)Hi(t+1)，然后二者杂交后的新个体为：Vi(t+1)Vi(t+1)，差分进化算法的基本变异操作可表示为： $$Hi(t+1)=X{p1}(t)+F(X{p2}(t)-X{p3}(t))$$
其中，$X{p1}(t)，X{p2}(t)和和X_{p3}(t)是从种群中随机选择的三个互不相等，且均与是从种群中随机选择的三个互不相等，且均与X_i(t)$不相等的个体。F为缩放因子，用于控制差异化向量对变异操作的影响，取值范围在[0,2]区间内。
差分进化算法的交叉操作主要分为”bin”型和”exp”型两类。“bin”型交叉操作类似于遗传算法中的均匀交叉，每一位都根据概率选择，其概率分布满足二项式，如下公式：
$$V{ij}(t+1)=\left{
\begin{array}{rcl}
H{ij}(t+1) & & { if(rand1{ij}\le CR) or(j==rand(i))}\
X{ij}(t) & & {otherwise}\
\end{array} \right.
$$
其中，CR为交叉概率，$rand1_{ij}$为0到1之间的随机数，rand(i)为1到D之间的随机整数。
而“exp”扩型交叉操作类似于遗传算法中的两点交叉，根据随机生成的交叉点选择对应子串，其概率分布满足指数形式，过程如下：首先随机产生一个交叉起始点，应选择变异个体$H_i(t+1)$中位于点位的分量，保证新个体$V_i(t+1)$中至少有一部分分量与父代个体的不同：然后根据概率选择位于其它各点位的分量来源，如果概率小于交叉概率CR时该点位的值从$H_i(t+1)$中的选取相应分量，否则从$X_i(t)$的中选取。
三. 代码演示
代码主要是从网上看到的，仅限参考。
//********************************************************/
// DE/rand/1/bin --差分进化算法-(基本类型)
//********************************************************/
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <float.h>
/* Function definitions */
double func(double *);
int usage(char *);
/* Random number generator defined by URAND should return
double-precision floating-point values uniformly distributed
over the interval [0.0, 1.0) */
#define URAND ((double)rand()/((double)RAND_MAX + 1.0))
/* Definition for random number generator initialization */
#define INITRAND srand(time(0))
/* Usage for the program */
int usage(char *str)
{
fprintf(stderr, "Usage: %s [-h] [-u] [-s] [-N NP (20*D)] ", str);
fprintf(stderr, "[-G Gmax (1000)]\n");
fprintf(stderr, "\t[-C crossover constant, CR (0.9)]\n");
fprintf(stderr, "\t[-F mutation scaling factor, F (0.9)]\n");
fprintf(stderr, "\t[-o <outputfile>]\n\n");
fprintf(stderr, "\t-s does not initialize random number generator\n");
exit(-1);
}
int main(int argc, char **argv)
{
register int i, j, k, r1, r2, r3, jrand, numofFE = 0;
extern int D;
extern double Xl[], Xu[];
int NP = 20 * D, Gmax = 1000, c, index = -1, s = 1;
double **popul, **next, **ptr, *iptr, *U, CR = 0.9, F = 0.9,
min_value = DBL_MAX, totaltime = 0.0;
char *ofile = NULL;
FILE *fid;
clock_t starttime, endtime;
/* Parse command line arguments given by user */
for (i = 1; i < argc; i++)
{
if (argv[i][0] != '-')
usage(argv[0]);
c = argv[i][1];
switch (c)
{
case 'N':
if (++i >= argc)
usage(argv[0]);
NP = atoi(argv[i]);
break;
case 'G':
if (++i >= argc)
usage(argv[0]);
Gmax = atoi(argv[i]);
break;
case 'C':
if (++i >= argc)
usage(argv[0]);
CR = atof(argv[i]);
break;
case 'F':
if (++i >= argc)
usage(argv[0]);
F = atof(argv[i]);
break;
case 'o':
if (++i >= argc)
usage(argv[0]);
ofile = argv[i];
break;
case 's': /* Flag for using same seeds for */
s = 0; /* different runs */
break;
case 'h':
case 'u':
default:
usage(argv[0]);
}
}
if (s) INITRAND;
/* Printing out information about optimization process for the user */
printf("Program parameters: ");
printf("NP = %d, Gmax = %d, CR = %.2f, F = %.2f\n",
NP, Gmax, CR, F);
printf("Dimension of the problem: %d\n", D);
/* Starting timer */
starttime = clock();
/* Allocating memory for current and next populations, intializing
current population with uniformly distributed random values and
calculating value for the objective function */
// NP:种群大小, Gmax:迭代次数, CR:交叉概率, F:扰动向量的缩放因子
//当前种群
popul = (double **)malloc(NP*sizeof(double *));
if (popul == NULL) perror("malloc");
//下代种群
next = (double **)malloc(NP*sizeof(double *));
if (next == NULL) perror("malloc");
//当前种群popul[NP][D+1]
for (i = 0; i < NP; i++)
{
//个体维度空间分配
popul[i] = (double *)malloc((D + 1)*sizeof(double));
if (popul[i] == NULL) perror("malloc");
//初始化维度值
for (j = 0; j < D; j++)
popul[i][j] = Xl[j] + (Xu[j] - Xl[j])*URAND;
//最后的元素内存放该个体的适应度值
popul[i][D] = func(popul[i]);
numofFE++;//统计评估次数
//下一代个体空间分配
next[i] = (double *)malloc((D + 1)*sizeof(double));
if (next[i] == NULL) perror("malloc");
}
/* 为实验向量分配空间--Allocating memory for a trial vector U */
U = (double *)malloc((D + 1)*sizeof(double));
if (U == NULL) perror("malloc");
/* The main loop of the algorithm */
for (k = 0; k < Gmax; k++)
{
for (i = 0; i < NP; i++) /* Going through whole population */
{
/* Selecting random indeces r1, r2, and r3 to individuls of
the population such that i != r1 != r2 != r3 */
//1.选择三个互不相同的随机个体r1,r2,r3
do
{
r1 = (int)(NP*URAND);
} while (r1 == i);
do
{
r2 = (int)(NP*URAND);
} while (r2 == i || r2 == r1);
do
{
r3 = (int)(NP*URAND);
} while (r3 == i || r3 == r1 || r3 == r2);
jrand = (int)(D*URAND);
/* Mutation and crossover */
//2. 执行变异和交叉操作
for (j = 0; j < D; j++)
{
//执行二项式交叉
if (URAND < CR || j == jrand)
{
//试验向量部分来自变异后的向量
U[j] = popul[r3][j] + F*(popul[r1][j] - popul[r2][j]);
}
else
//试验向量部分来自个体i
U[j] = popul[i][j];
}
//3. 计算新生成向量的适应度值
U[D] = func(U);
numofFE++;
/* Comparing the trial vector 'U' and the old individual
'next[i]' and selecting better one to continue in the
next population.注意:空间的交替变换和使用 */
//贪婪策略从试验向量U和当前个体i中选择一个好的放入到下一代个体中
if (U[D] <= popul[i][D])//新向量好
{
//试验向量U牛逼, next指向当前的试验向量U,u指向next, 方法:指针交换
iptr = U;
U = next[i];
next[i] = iptr;
}
else//原始向量牛逼, next指向个体i, 方法: 直接拷贝
{
for (j = 0; j <= D; j++)
next[i][j] = popul[i][j];
}
} /* End of the going through whole population */
/* Pointers of old and new populations are swapped */
//指针交换,各指针指向的空间发生变化
ptr = popul;
popul = next;
next = ptr;
} /* End of the main loop */
/* Stopping timer */
endtime = clock();
totaltime = (double)(endtime - starttime);
/* If user has defined output file, the whole final population is
saved to the file */
if (ofile != NULL)
{
if ((fid = (FILE *)fopen(ofile, "a")) == NULL)
{
fprintf(stderr, "Error in opening file %s\n\n", ofile);
usage(argv[0]);
}
for (i = 0; i < NP; i++)
{
for (j = 0; j <= D; j++)
fprintf(fid, "%.15e ", popul[i][j]);
fprintf(fid, "\n");
}
fclose(fid);
}
/* Finding best individual */
for (i = 0; i < NP; i++)
{
if (popul[i][D] < min_value)
{
min_value = popul[i][D];
index = i;
}
}
/* Printing out information about optimization process for the user */
printf("Execution time: %.3f s\n", totaltime / (double)CLOCKS_PER_SEC);
printf("Number of objective function evaluations: %d\n", numofFE);
printf("Solution:\nValues of variables: ");
for (i = 0; i < D; i++)
printf("%.15f ", popul[index][i]);
printf("\nObjective function value: ");
printf("%.15f\n", popul[index][D]);
/* Freeing dynamically allocated memory */
for (i = 0; i < NP; i++)
{
free(popul[i]);
free(next[i]);
}
free(popul);
free(next);
free(U);
return(0);
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK