差分进化算法 (Differential Evolution)

 

Differential Evolution（DE）是由Storn等人于1995年提出的，和其它一样，DE是一种模拟生物进化的，通过反复，使得那些适应环境的个体被保存了下来。但相比于进化算法，DE保留了基于种群的全局搜索策略，采用实数编码、基于差分的简单变异操作和一对一的竞争生存策略，降低了遗传操作的复杂性。同时，DE特有的记忆能力使其可以动态跟踪当前的搜索情况，以调整其搜索策略，具有较强的全局收敛能力和，且不需要借助问题的特征信息，适于求解一些利用常规的数学规划方法所无法求解的复杂环境中的优化问题。目前，DE已经在许多领域得到了应用，譬如人工网络、化工、电力、机械设计、机器人、信号处理、生物信息、经济学、现代农业、食品安全、环境保护和运筹学等。

 

• DE算法-作者网站: 
• 维基百科资料库  : 

 

DE 算法主要用于求解的全局优化问题，其主要工作步骤与其他基本一致，主要包括变异(Mutation)、交叉(Crossover)、选择(Selection)三种操作。算法的基本思想是从某一随机产生的初始群体开始，利用从种群中随机选取的两个个体的差向量作为第三个个体的随机变化源，将差向量加权后按照一定的规则与第三个个体求和而产生变异个体，该操作称为变异。然后，变异个体与某个预先决定的目标个体进行参数混合，生成试验个体，这一过程称之为交叉。如果试验个体的适应度值优于目标个体的适应度值，则在下一代中试验个体取代目标个体，否则目标个体仍保存下来，该操作称为选择。在每一代的进化过程中，每一个体矢量作为目标个体一次，算法通过不断地迭代计算，保留优良个体，淘汰劣质个体，引导搜索过程向全局逼近。

 

算法图解:

 算法伪代码: 

 

 

 

 

算法C代码:

 

1 //********************************************************/  2 //      DE/rand/1/bin --差分进化算法-(基本类型)         3 //********************************************************/  4   5   6 #include 
      
         7 #include 
       
          8 #include 
        
           9 #include 
         
           10  11 /* Function definitions        */ 12  13 double func(double *); 14 int usage(char *); 15  16 /* Random number generator defined by URAND should return 17 double-precision floating-point values uniformly distributed 18 over the interval [0.0, 1.0)                    */ 19  20 #define URAND    ((double)rand()/((double)RAND_MAX + 1.0)) 21  22 /* Definition for random number generator initialization    */ 23  24 #define INITRAND srand(time(0)) 25  26 /* Usage for the program    */ 27  28 int 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 
          
           ]\n\n"); 35     fprintf(stderr, "\t-s does not initialize random number generator\n"); 36     exit(-1); 37 } 38  39  40 int main(int argc, char **argv) 41 { 42     register int i, j, k, r1, r2, r3, jrand, numofFE = 0; 43     extern int D; 44     extern double Xl[], Xu[]; 45  46     int NP = 20 * D, Gmax = 1000, c, index = -1, s = 1; 47  48     double **popul, **next, **ptr, *iptr, *U, CR = 0.9, F = 0.9, 49  50         min_value = DBL_MAX, totaltime = 0.0; 51  52     char *ofile = NULL; 53  54     FILE *fid; 55     clock_t starttime, endtime; 56  57  58     /* Parse command line arguments given by user    */ 59  60     for (i = 1; i < argc; i++) 61     { 62         if (argv[i][0] != '-') 63             usage(argv[0]); 64  65         c = argv[i][1]; 66  67         switch (c) 68         { 69         case 'N': 70             if (++i >= argc) 71                 usage(argv[0]); 72  73             NP = atoi(argv[i]); 74             break; 75         case 'G': 76             if (++i >= argc) 77                 usage(argv[0]); 78  79             Gmax = atoi(argv[i]); 80             break; 81         case 'C': 82             if (++i >= argc) 83                 usage(argv[0]); 84  85             CR = atof(argv[i]); 86             break; 87         case 'F': 88             if (++i >= argc) 89                 usage(argv[0]); 90  91             F = atof(argv[i]); 92             break; 93         case 'o': 94             if (++i >= argc) 95                 usage(argv[0]); 96  97             ofile = argv[i]; 98             break; 99         case 's':    /* Flag for using same seeds for        */100             s = 0;    /* different runs                */101             break;102         case 'h':103         case 'u':104         default:105             usage(argv[0]);106         }107     }108 109     if (s) INITRAND;110 111     /* Printing out information about optimization process for the user    */112 113     printf("Program parameters: ");114     printf("NP = %d, Gmax = %d, CR = %.2f, F = %.2f\n",115         NP, Gmax, CR, F);116 117     printf("Dimension of the problem: %d\n", D);118 119 120     /* Starting timer    */121 122     starttime = clock();123 124 125     /* Allocating memory for current and next populations, intializing126     current population with uniformly distributed random values and127     calculating value for the objective function    */128 129 130     // NP:种群大小, Gmax:迭代次数, CR:交叉概率, F:扰动向量的缩放因子131 132     //当前种群133     popul = (double **)malloc(NP*sizeof(double *));134     if (popul == NULL) perror("malloc");135 136     //下代种群137     next = (double **)malloc(NP*sizeof(double *));138     if (next == NULL) perror("malloc");139 140     //当前种群popul[NP][D+1] 141     for (i = 0; i < NP; i++)142     {143         //个体维度空间分配144         popul[i] = (double *)malloc((D + 1)*sizeof(double));145         if (popul[i] == NULL) perror("malloc");146 147         //初始化维度值148         for (j = 0; j < D; j++)149             popul[i][j] = Xl[j] + (Xu[j] - Xl[j])*URAND;150 151         //最后的元素内存放该个体的适应度值152         popul[i][D] = func(popul[i]);153 154         numofFE++;//统计评估次数155 156         //下一代个体空间分配157         next[i] = (double *)malloc((D + 1)*sizeof(double));158         if (next[i] == NULL) perror("malloc");159     }160 161     /* 为实验向量分配空间--Allocating memory for a trial vector U    */162 163     U = (double *)malloc((D + 1)*sizeof(double));164     if (U == NULL) perror("malloc");165 166 167     /* The main loop of the algorithm    */168 169     for (k = 0; k < Gmax; k++)170     {171 172         for (i = 0; i < NP; i++)    /* Going through whole population    */173         {174 175             /* Selecting random indeces r1, r2, and r3 to individuls of176             the population such that i != r1 != r2 != r3    */177 178             //1.选择三个互不相同的随机个体r1,r2,r3179             do180             {181                 r1 = (int)(NP*URAND);182             } while (r1 == i);183 184             do185             {186                 r2 = (int)(NP*URAND);187             } while (r2 == i || r2 == r1);188             do189             {190                 r3 = (int)(NP*URAND);191             } while (r3 == i || r3 == r1 || r3 == r2);192 193             jrand = (int)(D*URAND);194 195             /* Mutation and crossover    */196             //2. 执行变异和交叉操作197             for (j = 0; j < D; j++)198             {199                 //执行二项式交叉200                 if (URAND < CR || j == jrand)201                 {202                     //试验向量部分来自变异后的向量203                     U[j] = popul[r3][j] + F*(popul[r1][j] - popul[r2][j]);204                 }205                 else206                     //试验向量部分来自个体i207                     U[j] = popul[i][j];208             }209             //3. 计算新生成向量的适应度值210             U[D] = func(U);211 212             numofFE++;213 214             /* Comparing the trial vector 'U' and the old individual215             'next[i]' and selecting better one to continue in the216             next population.注意:空间的交替变换和使用    */217 218             //贪婪策略从试验向量U和当前个体i中选择一个好的放入到下一代个体中219             if (U[D] <= popul[i][D])//新向量好220             {221 222                 //试验向量U牛逼, next指向当前的试验向量U,u指向next, 方法:指针交换223                 iptr = U;224                 U = next[i];225                 next[i] = iptr;226             }227             else//原始向量牛逼, next指向个体i, 方法: 直接拷贝228             {229                 for (j = 0; j <= D; j++)230                     next[i][j] = popul[i][j];231             }232 233         }    /* End of the going through whole population    */234 235 236         /* Pointers of old and new populations are swapped    */237         //指针交换,各指针指向的空间发生变化238         ptr = popul;239         popul = next;240         next = ptr;241 242     }    /* End of the main loop        */243 244 245     /* Stopping timer    */246 247     endtime = clock();248     totaltime = (double)(endtime - starttime);249 250 251     /* If user has defined output file, the whole final population is252     saved to the file                        */253 254     if (ofile != NULL)255     {256         if ((fid = (FILE *)fopen(ofile, "a")) == NULL)257         {258             fprintf(stderr, "Error in opening file %s\n\n", ofile);259             usage(argv[0]);260         }261 262         for (i = 0; i < NP; i++)263         {264             for (j = 0; j <= D; j++)265                 fprintf(fid, "%.15e ", popul[i][j]);266             fprintf(fid, "\n");267         }268         fclose(fid);269     }270 271     /* Finding best individual    */272 273     for (i = 0; i < NP; i++)274     {275         if (popul[i][D] < min_value)276         {277             min_value = popul[i][D];278             index = i;279         }280     }281 282     /* Printing out information about optimization process for the user    */283 284     printf("Execution time: %.3f s\n", totaltime / (double)CLOCKS_PER_SEC);285     printf("Number of objective function evaluations: %d\n", numofFE);286 287     printf("Solution:\nValues of variables: ");288     for (i = 0; i < D; i++)289         printf("%.15f ", popul[index][i]);290 291     printf("\nObjective function value: ");292     printf("%.15f\n", popul[index][D]);293 294 295     /* Freeing dynamically allocated memory    */296 297     for (i = 0; i < NP; i++)298     {299         free(popul[i]);300         free(next[i]);301     }302     free(popul);303     free(next);304     free(U);305 306     return(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, ftp.icsi.berkeley.edu.

[6] Storn, R., , Technical Report TR-96-039, ICSI, November 1996, ftp.icsi.berkeley.edu.

[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, ftp.icsi.berkeley.edu.

[11] Storn, R., IEEE International Conference on Evolutionary Computation ICEC 96, pp. 268 - 273, Technical Report TR-95-026, ICSI, May 1995, ftp.icsi.berkeley.edu.

[12] Storn, R., , Technical Report TR-95-018, ICSI, May 1995, ftp.icsi.berkeley.edu.

[13] Storn, R. and Price, K., , Technical Report TR-95-012, ICSI, March 1995, ftp.icsi.berkeley.edu. 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.