基于差分进化的生物地理学优化算法

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

但相⽐于进化算法，DE保留了基于种群的全局搜索策略，采⽤实数编码、基于差分的简单变异操作和⼀对⼀的竞争⽣存策略，降低了遗传操作的复杂性。

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

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

DE算法-作者⽹站:维基百科资料库 :DE 算法主要⽤于求解的全局优化问题，其主要⼯作步骤与其他基本⼀致，主要包括变异(Mutation)、交叉(Crossover)、选择(Selection)三种操作。

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

然后，变异个体与某个预先决定的⽬标个体进⾏参数混合，⽣成试验个体，这⼀过程称之为交叉。

如果试验个体的适应度值优于⽬标个体的适应度值，则在下⼀代中试验个体取代⽬标个体，否则⽬标个体仍保存下来，该操作称为选择。

在每⼀代的进化过程中，每⼀个体⽮量作为⽬标个体⼀次，算法通过不断地迭代计算，保留优良个体，淘汰劣质个体，引导搜索过程向全局逼近。

算法图解:算法伪代码:算法C代码:1//********************************************************/2// DE/rand/1/bin --差分进化算法-(基本类型)3//********************************************************/456 #include <stdlib.h>7 #include <stdio.h>8 #include <time.h>9 #include <float.h>1011/* Function definitions */1213double func(double *);14int usage(char *);1516/* Random number generator defined by URAND should return17double-precision floating-point values uniformly distributed18over the interval [0.0, 1.0) */1920#define URAND ((double)rand()/((double)RAND_MAX + 1.0))2122/* Definition for random number generator initialization */2324#define INITRAND srand(time(0))2526/* Usage for the program */2728int usage(char *str)29 {30 fprintf(stderr, "Usage: %s [-h] [-u] [-s] [-N NP (20*D)] ", str);31 fprintf(stderr, "[-G Gmax (1000)]\n");32 fprintf(stderr, "\t[-C crossover constant, CR (0.9)]\n");33 fprintf(stderr, "\t[-F mutation scaling factor, F (0.9)]\n");34 fprintf(stderr, "\t[-o <outputfile>]\n\n");35 fprintf(stderr, "\t-s does not initialize random number generator\n");36 exit(-1);37 }383940int main(int argc, char **argv)41 {42 register int i, j, k, r1, r2, r3, jrand, numofFE = 0;43extern int D;44extern double Xl[], Xu[];4546int NP = 20 * D, Gmax = 1000, c, index = -1, s = 1;4748double **popul, **next, **ptr, *iptr, *U, CR = 0.9, F = 0.9,4950 min_value = DBL_MAX, totaltime = 0.0;5152char *ofile = NULL;5354 FILE *fid;55 clock_t starttime, endtime;565758/* Parse command line arguments given by user */5960for (i = 1; i < argc; i++)61 {62if (argv[i][0] != '-')63 usage(argv[0]);6465 c = argv[i][1];6667switch (c)68 {69case'N':70if (++i >= argc)71 usage(argv[0]);7273 NP = atoi(argv[i]);74break;75case'G':76if (++i >= argc)77 usage(argv[0]);7879 Gmax = atoi(argv[i]);80break;81case'C':82if (++i >= argc)83 usage(argv[0]);8485 CR = atof(argv[i]);86break;87case'F':88if (++i >= argc)89 usage(argv[0]);9091 F = atof(argv[i]);92break;93case'o':94if (++i >= argc)95 usage(argv[0]);9697 ofile = argv[i];98break;99case's': /* Flag for using same seeds for */100 s = 0; /* different runs */101break;102case'h':103case'u':104default:105 usage(argv[0]);106 }107 }108109if (s) INITRAND;110111/* Printing out information about optimization process for the user */ 112113 printf("Program parameters: ");114 printf("NP = %d, Gmax = %d, CR = %.2f, F = %.2f\n",115 NP, Gmax, CR, F);116117 printf("Dimension of the problem: %d\n", D);118119120/* Starting timer */121122 starttime = clock();123124125/* Allocating memory for current and next populations, intializing126 current population with uniformly distributed random values and127 calculating value for the objective function */128129130// NP:种群⼤⼩, Gmax:迭代次数, CR:交叉概率, F:扰动向量的缩放因⼦131132//当前种群133 popul = (double **)malloc(NP*sizeof(double *));134if (popul == NULL) perror("malloc");135136//下代种群137 next = (double **)malloc(NP*sizeof(double *));138if (next == NULL) perror("malloc");139140//当前种群popul[NP][D+1]141for (i = 0; i < NP; i++)142 {143//个体维度空间分配144 popul[i] = (double *)malloc((D + 1)*sizeof(double));145if (popul[i] == NULL) perror("malloc");146147//初始化维度值148for (j = 0; j < D; j++)149 popul[i][j] = Xl[j] + (Xu[j] - Xl[j])*URAND;150151//最后的元素内存放该个体的适应度值152 popul[i][D] = func(popul[i]);153154 numofFE++;//统计评估次数155156//下⼀代个体空间分配157 next[i] = (double *)malloc((D + 1)*sizeof(double));158if (next[i] == NULL) perror("malloc");159 }160161/* 为实验向量分配空间--Allocating memory for a trial vector U */ 162163 U = (double *)malloc((D + 1)*sizeof(double));164if (U == NULL) perror("malloc");165166167/* The main loop of the algorithm */168169for (k = 0; k < Gmax; k++)170 {171172for (i = 0; i < NP; i++) /* Going through whole population */173 {174175/* Selecting random indeces r1, r2, and r3 to individuls of176 the population such that i != r1 != r2 != r3 */177178//1.选择三个互不相同的随机个体r1,r2,r3179do180 {181 r1 = (int)(NP*URAND);182 } while (r1 == i);183184do185 {186 r2 = (int)(NP*URAND);187 } while (r2 == i || r2 == r1);188do189 {190 r3 = (int)(NP*URAND);191 } while (r3 == i || r3 == r1 || r3 == r2);192193 jrand = (int)(D*URAND);194195/* Mutation and crossover */196//2. 执⾏变异和交叉操作197for (j = 0; j < D; j++)198 {199//执⾏⼆项式交叉200if (URAND < CR || j == jrand)201 {202//试验向量部分来⾃变异后的向量203 U[j] = popul[r3][j] + F*(popul[r1][j] - popul[r2][j]);204 }205else206//试验向量部分来⾃个体i207 U[j] = popul[i][j];208 }209//3. 计算新⽣成向量的适应度值210 U[D] = func(U);211212 numofFE++;213214/* Comparing the trial vector 'U' and the old individual215 'next[i]' and selecting better one to continue in the216 next population.注意:空间的交替变换和使⽤ */217218//贪婪策略从试验向量U和当前个体i中选择⼀个好的放⼊到下⼀代个体中219if (U[D] <= popul[i][D])//新向量好220 {221222//试验向量U⽜逼, next指向当前的试验向量U,u指向next, ⽅法:指针交换223 iptr = U;224 U = next[i];225 next[i] = iptr;226 }227else//原始向量⽜逼, next指向个体i, ⽅法: 直接拷贝228 {229for (j = 0; j <= D; j++)230 next[i][j] = popul[i][j];231 }232233 } /* End of the going through whole population */234235236/* Pointers of old and new populations are swapped */237//指针交换,各指针指向的空间发⽣变化238 ptr = popul;239 popul = next;240 next = ptr;241242 } /* End of the main loop */243244245/* Stopping timer */246247 endtime = clock();248 totaltime = (double)(endtime - starttime);249250251/* If user has defined output file, the whole final population is252 saved to the file */253254if (ofile != NULL)255 {256if ((fid = (FILE *)fopen(ofile, "a")) == NULL)257 {258 fprintf(stderr, "Error in opening file %s\n\n", ofile);259 usage(argv[0]);260 }261262for (i = 0; i < NP; i++)263 {264for (j = 0; j <= D; j++)265 fprintf(fid, "%.15e ", popul[i][j]);266 fprintf(fid, "\n");267 }268 fclose(fid);269 }270271/* Finding best individual */272273for (i = 0; i < NP; i++)274 {275if (popul[i][D] < min_value)276 {277 min_value = popul[i][D];278 index = i;279 }280 }281282/* Printing out information about optimization process for the user */283284 printf("Execution time: %.3f s\n", totaltime / (double)CLOCKS_PER_SEC);285 printf("Number of objective function evaluations: %d\n", numofFE);286287 printf("Solution:\nValues of variables: ");288for (i = 0; i < D; i++)289 printf("%.15f ", popul[index][i]);290291 printf("\nObjective function value: ");292 printf("%.15f\n", popul[index][D]);293294295/* Freeing dynamically allocated memory */296297for (i = 0; i < NP; i++)298 {299free(popul[i]);300free(next[i]);301 }302free(popul);303free(next);304free(U);305306return(0);307 }经典⽂献:[1] Storn, R., "Designing Nonstandard Filters with Differential Evolution, IEEE Signal Processing Magazine, january 2005, pp. 103 - 106.[2] Storn, R., "Sytem Design by Constraint Adaptation and Differential Evolution", IEEE Trans. on Evolutionary Computation, 1999, Vol. 3, No. 1, pp. 22 - 34.[3] Storn, R. and Price, K., "Differential Evolution - a Simple and Efficient Heuristic for Global Optimization over Continuous Spaces", Journal of Global Optimization, Kluwer Academic Publishers, 1997, Vol. 11, pp. 341 - 359.[4] Gitsels, M. and Storn, R., Internet-Videotelephonie nach dem H.323-Standard, ITG-Fachbericht 144, 7. Dortmunder Fernsehseminar, pp. 87 - 92.[5] Storn, R., , Technical Report TR-96-046, ICSI, November 1996, .[6] Storn, R., , Technical Report TR-96-039, ICSI, November 1996, .[7] Price, K. and Storn, R., "Differential Evolution: Numerical Optimization Made Easy", Dr. Dobb's Journal, April 97, pp. 18 - 24.[8] Storn, R., NAFIPS 1996, Berkeley, pp. 519 - 523.[9] Storn, R. and Price, K., IEEE Conference on Evolutionary Computation, Nagoya, 1996, pp. 842 - 844.[10] Storn, R., (IEEE Signal Processing Letters, Vol. 3, No. 8, August 1996, pp. 242 - 244), Technical Report TR-95-061, ICSI, September 1995, .[11] Storn, R., IEEE International Conference on Evolutionary Computation ICEC 96, pp. 268 - 273, Technical Report TR-95-026, ICSI, May 1995, .[12] Storn, R., , Technical Report TR-95-018, ICSI, May 1995, .[13] Storn, R. and Price, K., , Technical Report TR-95-012, ICSI, March 1995, . Anyone who is interested in trying Differential Evolution (DE) might access the .[14] Storn, R., "A Debug/Trace Tool for C SW Projects", Dr. Dobb's Journal, February 1997, pp. 22 - 26.[15] Storn, R., "Constrained Optimization", Dr. Dobb's Journal, May 1995, pp. 119 - 123.[16] Christ, J., Storn, R. and Lueder, E., " New Shortlength DFTs for the Prime Factor Implementation on DSP Architectures", Frequenz, 1995, Band 49, Issue 1-2, pp. 8 - 10.[17] Ballay, H. and Storn, R., "A Tool for Checking C Coding Conventions", C User's Journal, july 94, pp. 41 - 50..[18] Storn, R., "A Hashing Function Based on Algebraic Coding", submitted for publication in the I.E.E. Proceedings~E, Computers and Digital Techniques.[19] Storn, R., "A Radix-2 FFT-Pipeline Architecture With Reduced Noise to Signal Ratio", I.E.E. Proceedings~F, Radar and Signal Processing, 1994.[20] Storn, R. , "Datensicherung mit Prüfsummen", ST-Computer, 1994.[21] Storn, R., "Some Results in Fixed Point Error Analysis of the Bruun-FFT Algorithm, IEEE Trans. on Signal Processing, Vol. 41, No. 7, July 93, pp. 2371 - 2375.[22] Storn, R. , "Statistische Optimierung", ST-Computer, Issues 12/1992 and 1/1993.[23] Storn, R. , "On the Bruun Algorithm and its Inverse", Frequenz, Vol. 3-4, 1992, pp. 110 -116.[24] Storn, R. , "Logische Schaltungen und deren Vereinfachung nach Quine-McCluskey", ST-Computer, Issues 3, 4 and 5, 1990.[25] Storn, R. , "A novel Radix-2 Pipeline Architecture for the Computation of the DFT", IEEE Proc. of the ISCAS 1988, pp. 1899 -1902.[26] Storn, R. , "On the Reduction of Arithmetic Complexity in the Chirp-Transform", Proc. ECCTD, 1987, pp. 239 -244.[27] Storn, R. , "Ein Primfaktor-Algorithmus für die diskrete Hartley-Transformation", 9. DFG-Kolloquium über digitale Signalverarbeitung, 1986, pp. 79 -82.[28] Storn, R. , "Fast Algorithms for the Discrete Hartley Transform", AEÜ, Band 40, Heft 4, 1986, pp. 233 -240.[29] Storn, R. , "Dreieck-Quadratur-Oszillator. Nur ein zeitbestimmendes Glied erforderlich", Elektronik, Issue 5, 1982, p. 74.[30] Storn, R. , "Constant Current Adapter", Elektor, Issue 7/8, 1981.[31] Storn, R. , "De Luxe Transistor Tester", Elektor, Issue 7/8, 1979. (The corresponding circuit was among the winners of the european circuit design contest "EUROTRONIK").BOOKS[1] Price K., Storn R., Lampinen J., Differential Evolution - A Practical Approach to Global Optimization, Springer, Berlin, 2005.[2] Contributor for Babu, B.V., Onwubolu, G. (Editors), New Optimization Techniques in Engineering, Springer, Berlin, 2004.[3] Contributor for Corne, D., Dorigo., M, and Glover., F. (Editors), New Ideas in Optimization, McGraw-Hill, 1999.。

差分进化算法入门差分进化算法（Differential Evolution, DE）是一种优化算法，用于解决连续优化问题。

它由Storn和Price在1995年提出，是一种基于种群的演化算法，采用迭代的方式逐步优化目标函数。

差分进化算法相比一些其他优化算法具有简单、高效和易于实现的特点，因此在实际应用中得到了广泛的应用。

差分进化算法的基本思想是通过模拟自然界中物种的进化过程来寻找最优解。

在差分进化算法中，解决问题的空间被划分成一系列个体，每个个体代表一个潜在的解。

算法的核心是个体间的差分和变异运算，通过变异和交叉操作生成新的解，并根据目标函数的评价指标选择出较优的个体。

这种迭代的过程不断演化，直到找到满足停止条件的解。

1.初始化种群：随机生成若干个体作为初始种群，并计算每个个体的适应度。

2.变异操作：随机选择三个不同的个体，通过变异操作生成新的解。

变异操作基于当前种群中的个体进行，并引入随机扰动来增加范围。

3.交叉操作：将变异得到的新解与原个体进行交叉操作，并生成一个交叉后的个体。

4.选择操作：根据目标函数的评价指标选择较优的个体作为下一代种群的成员。

5.终止条件检测：判断是否满足终止条件，如果满足则停止迭代，输出最优解；否则返回第2步。

差分进化算法的核心是变异和交叉操作，通过这两个操作可以生成新的解，并引导算法向全局最优解方向。

其中，变异操作决定了新解的探索能力，而交叉操作决定了新解与原个体之间的关系，从而在不同个体之间交换优秀特征。

综合这两个操作的影响，差分进化算法能够在解空间中进行有效的，找到最优解。

1.简单易懂：算法原理较为简单，易于理解和实现。

2.高效性：算法运行效率较高，在解决连续优化问题时能够找到接近全局最优解的解。

3.鲁棒性：算法对于问题的初始条件不敏感，能够适用于多种不同类型的优化问题。

4.可扩展性：算法可以通过调整参数和运算操作进行扩展和优化，适用于不同规模和复杂度的问题。

总之，差分进化算法是一种简单、高效和易于实现的优化算法。

基于差分进化算法的自动化约束优化问题在当今科技飞速发展的时代，自动化技术在各个领域的应用日益广泛，而其中的约束优化问题更是备受关注。

约束优化问题是指在满足一系列约束条件的前提下，寻找最优的解决方案。

这些约束条件可能涉及资源限制、技术要求、法律法规等多个方面，使得问题的求解变得复杂而具有挑战性。

差分进化算法作为一种强大的优化算法，为解决自动化约束优化问题提供了有效的途径。

那么，什么是差分进化算法呢？简单来说，它是一种基于群体的随机搜索算法，通过模拟生物进化过程中的变异、交叉和选择操作，来不断优化解的质量。

与传统的优化算法相比，差分进化算法具有许多独特的优势。

首先，它对问题的初始解不敏感，这意味着即使初始解的质量较差，算法也能够通过不断的迭代逐步找到更好的解。

其次，差分进化算法具有较强的全局搜索能力，能够避免陷入局部最优解，从而提高获得最优解的可能性。

此外，它的参数设置相对简单，易于实现和应用。

在自动化约束优化问题中，我们常常面临各种各样的约束条件。

例如，在生产制造领域，可能需要在有限的时间、材料和人力等资源约束下，最大化生产效率或产品质量；在物流配送中，需要在满足车辆载重、行驶时间和路线限制等条件下，最小化运输成本；在工程设计中，要在满足结构强度、尺寸限制和性能要求等约束的同时，优化设计方案的成本和性能。

为了有效地应用差分进化算法解决这些约束优化问题，我们需要对算法进行适当的改进和调整。

一种常见的方法是引入惩罚函数，将约束违反的情况转化为目标函数的惩罚项。

这样，在算法的迭代过程中，违反约束的解会受到相应的惩罚，从而引导搜索朝着满足约束的方向进行。

另一种方法是采用约束处理技术，如可行性规则和修复策略。

可行性规则通过判断解是否满足约束条件，只允许可行解参与后续的进化操作。

而修复策略则是对不可行解进行修正，使其满足约束条件。

除了上述方法，还可以结合其他优化算法或技术，形成混合算法，以提高求解自动化约束优化问题的性能。

差分进化算法介绍1．差分进化算法背景差分进化(Differential Evolution，DE)是启发式优化算法的一种，它是基于群体差异的启发式随机搜索算法，该算法是Raincr Stom和Kenneth Price为求解切比雪夫多项式而提出的。

差分进化算法具有原理简单、受控参数少、鲁棒性强等特点。

近年来，DE在约束优化计算、聚类优化计算、非线性优化控制、神经网络优化、滤波器设计、阵列天线方向图综合及其它方面得到了广泛的应用。

差分算法的研究一直相当活跃，基于优胜劣汰自然选择的思想和简单的差分操作使差分算法在一定程度上具有自组织、自适应、自学习等特征。

它的全局寻优能力和易于实施使其在诸多应用中取得成功。

2.差分进化算法简介差分进化算法采用实数编码方式，其算法原理同遗传算法相似刚，主要包括变异、交叉和选择三个基本进化步骤。

DE算法中的选择策略通常为锦标赛选择，而交叉操作方式与遗传算法也大体相同，但在变异操作方面使用了差分策略，即：利用种群中个体间的差分向量对个体进行扰动，实现个体的变异。

与进化策略(Es)采用Gauss或Cauchy 分布作为扰动向量的概率密度函数不同，DE使用的差分策略可根据种群内个体的分布自动调节差分向量(扰动向量)的大小，自适应好；DE 的变异方式，有效地利用了群体分布特性，提高了算法的搜索能力，避免了遗传算法中变异方式的不足。

3.差分进化算法适用情况差分进化算法是一种随机的并行直接搜索算法，最初的设想是用于解决切比雪夫多项式问题，后来发现差分进化算法也是解决复杂优化问题的有效技术。

它可以对非线性不可微连续空间的函数进行最小化。

目前，差分进化算法的应用和研究主要集中于连续、单目标、无约束的确定性优化问题，但是，差分进化算法在多目标、有约束、离散和噪声等复杂环境下的优化也得到了一些进展。

4.基本DE算法差分进化算法把种群中两个成员之间的加权差向量加到第三个成员上以产生新的参数向量，这一操作称为“变异”。