差分进化算法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//********************************************************/
4
5
6 #include <stdlib.h>
7 #include <stdio.h>
8 #include <time.h>
9 #include <float.h>
10
11/* Function definitions */
12
13double func(double *);
14int usage(char *);
15
16/* Random number generator defined by URAND should return
17double-precision floating-point values uniformly distributed
18over 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
28int 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 }
38
39
40int 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[];
45
46int NP = 20 * D, Gmax = 1000, c, index = -1, s = 1;
47
48double **popul, **next, **ptr, *iptr, *U, CR = 0.9, F = 0.9,
49
50 min_value = DBL_MAX, totaltime = 0.0;
51
52char *ofile = NULL;
53
54 FILE *fid;
55 clock_t starttime, endtime;
56
57
58/* Par command line arguments given by ur */
59
60for (i = 1; i < argc; i++)
61 {
62if (argv[i][0] != '-')
63 usage(argv[0]);
64
65 c = argv[i][1];
66
67switch (c)
68 {
69ca'N':
70if (++i >= argc)
71 usage(argv[0]);
72
73 NP = atoi(argv[i]);
74break;
75ca'G':
76if (++i >= argc)
77 usage(argv[0]);
理想的工作78
79 Gmax = atoi(argv[i]);
80break;
81ca'C':
82if (++i >= argc)
83 usage(argv[0]);
84
85 CR = atof(argv[i]);
86break;
87ca'F':
88if (++i >= argc)
89 usage(argv[0]);
90
91 F = atof(argv[i]);
92break;
93ca'o':
94if (++i >= argc)
95 usage(argv[0]);
96
97 ofile = argv[i];
98break;
99ca's': /* Flag for using same eds for */
100 s = 0; /* different runs */
101break;
102ca'h':
103ca'u':
104default:
105 usage(argv[0]);
106 }
107 }
108
109if (s) INITRAND;
110
111/* Printing out information about optimization process for the ur */ 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, intializing
126 current population with uniformly distributed random values and
127 calculating value for the objective function */
128
129
130// NP：种群⼤⼩, Gmax：迭代次数, CR：交叉概率, F：扰动向量的缩放因⼦131
132//当前种群
133 popul = (double **)malloc(NP*sizeof(double *));
134if (popul == NULL) perror("malloc");
135
136//下代种群
137 next = (double **)malloc(NP*sizeof(double *));
138if (next == NULL) perror("malloc");
爱新觉罗胤礽139
140//当前种群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");
146
147//初始化维度值
148for (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));
158if (next[i] == NULL) perror("malloc");
159 }
160
161/* 为实验向量分配空间--Allocating memory for a trial vector U */ 162
163 U = (double *)malloc((D + 1)*sizeof(double));
164if (U == NULL) perror("malloc");
165
166
167/* The main loop of the algorithm */
168
169for (k = 0; k < Gmax; k++)
170 {
171
172for (i = 0; i < NP; i++) /* Going through whole population */
173 {
174
175/* Selecting random indeces r1, r2, and r3 to individuls of
176 the population such that i != r1 != r2 != r3 */
177
178//1.选择三个互不相同的随机个体r1,r2,r3
179do
180 {
181 r1 = (int)(NP*URAND);
182 } while (r1 == i);
183
184do
185 {
186 r2 = (int)(NP*URAND);
187 } while (r2 == i || r2 == r1);
188do敌意
189 {
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. 执⾏变异和交叉操作
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 }
205el
206//试验向量部分来⾃个体i
207 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 individual
215 'next[i]' and lecting better one to continue in the
216 next population.注意：空间的交替变换和使⽤ */
217
218//贪婪策略从试验向量U和当前个体i中选择⼀个好的放⼊到下⼀代个体中219if (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 }
227el//原始向量⽜逼, next指向个体i, ⽅法: 直接拷贝
228 {
229for (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 ur has defined output file, the whole final population is
252 saved to the file */
253
254if (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 }
261
262for (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 fclo(fid);
269 }
270
271/* Finding best individual */
272
273for (i = 0; i < NP; i++)
274 {
275if (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 ur */
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: ");
288for (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
297for (i = 0; i < NP; i++)
298 {
299free(popul[i]);
300free(next[i]);
301 }
302free(popul);
303free(next);
304free(U);
305
306return(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] Gitls, M. and Storn, R., Internet-Videotelephonie nach dem H.323-Standard, ITG-Fachbericht 144, 7. Dortmunder Fernhminar, 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 Ur's Journal, july 94, pp. 41 - 50..
[18] Storn, R., "A Hashing Function Bad 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 Noi 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 Inver", 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.
