C++遗传算法_遗传算法c++

项目说明
问题描述：对于方程f(x1,x2)=100*(x1^2-x2)2+(1-x1)^2，求出f的最大值并且求出对应的x1和x2（精确到0.001）。
遗传算法描述：随机生成多组等长二进制字符串作为初代祖先，经过多代的繁殖（包括自然选择、基因交叉、基因突变），评价出其适应度最好的基因作为全局最优解。
-自然选择：用的是轮盘法
-基因交叉：参考生物知识，不用我说了吧
-基因突变：随机在某基因的某个基因点将0变1或者1变0（当然有突变概率的，不是想变就变）
-适应度：将基因中x1、x2代入方程f，f值作为他的适应度
运行环境：vs2013可以运行，也可以将文件夹中的源.cpp中的代码复制到你的编译器运行

遗传算法说明

遗传算法流程图

:

基本遗传算法的步骤

：

1、 染色体编码：使用固定长度的二进制符号串来表示群体中的个体，其等位基因值由二值{0，1}组成。包括编码、解码公式。

2、 个体适应度的监测评估：所有个体的适应度必须为非负数。需要预先确定好由目标函数值到个体适应度之间的转换规律，特别是要预先确定好当目标函数为负数时的处理方法。例如：可选取一个适当大的正数C，使个体的适应度为目标函数值加上正数C

3、 遗传算子：

（1） 选择运算使用比例选择算子。比例选择因子是利用比例于各个个体适应度的概率决定其子孙的遗传可能性。

（2） 交叉运算使用单点交叉算子。任意挑选经过选择操作中两个个体作为交叉对象，随机产生一个交叉点位置，两个个体在交叉点位置互换部分基因码，形成两个子个体。

（3） 变异运算使用基本位变异算子或均匀变异算子。为了避免过早收敛，对于二进制的基因码组成的个体种群，实现基因码的小概率翻转，即0变为1，1变为0。

4、 基本遗传算法的运行参数：

（1） 群体大小：一般取为20—100

（2） 遗传算法的终止进化代数：一般取为100—500

（3） 交叉概率：一般取为0.4—0.99

（4） 变异概率：一般取为0.0001—0.1

研究方向

：

1、在遗传算法中，群体规模和遗传算子的控制参数的选取非常困难。存在过早收敛。

2、遗传算法的并行性主要有三个方面：个体适应度评价的并行性、整个群体各个个体适应度评价的并行性和子代群体产生过程的并行性。

3、分类系统属于基于遗传算法的机器学习中的一类，包括一个简单的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统。

4、遗传神经网络包括连接级、网络结构和学习规则的进化。

5、进化算法包括遗传算法、进化规划和进化策略，三种算法是独立发展起来的。
遗传算法的缺点：

1、遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,

2、另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.
3、没有能够及时利用网络的反馈信息,故算法的搜索速度比较慢，要得要较精确的解需要较多的训练时间。
4、算法对初始种群的选择有一定的依赖性，能够结合一些启发算法进行改进。
5、算法的并行机制的潜在能力没有得到充分的利用，这也是当前遗传算法的一个研究热点方向。

遗传算法Github地址

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<stdlib.h>
#include<iostream>
#include<time.h>
using namespace std;

/*The Definition of Constant*/
#define POPSIZE 500 //population size
#define MAXIMIZATION 1 //maximization flag
#define MINIMIZATION 2 //minimization flag
/*The Definition of User Data*/
#define Cmax 100//certain maximal value
#define Cmin 0 //certain minimun value
#define LENGTH1 10//the chromosome length of 1st variable
#define LENGTH2 10//the chromosome length of 2nd variable
#define CHROMLENGTH LENGTH1 + LENGTH2 //total length of chromosome
int FunctionMode = MAXIMIZATION;//optimization type
int PopSize = 80;//population size
int MaxGeneration = 200;//max number of generation
double Pc = 0.6;//probability of crossover
double Pm = 0.001;//probability of mutation
/*The Definition of Data Structure*/
struct individual//data structure of individual
{
	char chrom[CHROMLENGTH + 1];//a string of code representing
	double value;//object value of this individual
	double fitness;//fitness value of this individual
};
/*the Definition of Global Variables*/
int generation;//number of generation
int best_index;//index of best individual
int worst_index;//index of worst individua
struct individual bestindividual;//best individual of current generation
struct individual worstindividual;//worst individual of current generation
struct individual currentbest;//best individual by now
struct individual population[POPSIZE];//population
/*Declaration of Prototype*/
void GenerateInitialPopulation();
void GenerateNextPopulation();
void EvaluatePopulation();
long DecodeChromosome(char *, int, int);
void CalculateObjectValue();
void CalculateFitnessValue();
void FindBestAndWorstIndividual();
void PerformEvolution();
void SelectionOperator();
void CrossoverOperator();
void MutationOperator();
void OutputTextReport();
int main()
{
	generation = 0;
	GenerateInitialPopulation();
	EvaluatePopulation();
	while (generation < MaxGeneration){
		generation++;
		GenerateNextPopulation();
		EvaluatePopulation();
		PerformEvolution();
		OutputTextReport();
	}
	return 0;
}
/*Function:Generate the first population.
Variable:None.*/
void GenerateInitialPopulation()
{
	int i, j;
	int flag = 1;
	srand((unsigned)time(NULL));
	for (i = 0; i < PopSize; i++)
	{
		for (j = 0; j < CHROMLENGTH; j++)
		{
			population[i].chrom[j] = (rand()%10 < 5) ? '0' : '1';
		}
		population[i].chrom[CHROMLENGTH] = '\0';
	}
}
/*Function:Initialize the first generation
Variable:None*/
void GenerateNextPopulation()
{
	SelectionOperator();
	CrossoverOperator();
	MutationOperator();
}
/*Function:Evaluate population according to certain formula
Variable:None*/
void EvaluatePopulation()
{
	CalculateObjectValue();//calculate object value
	CalculateFitnessValue();//calculate fitness value
	FindBestAndWorstIndividual();//find the best and worst individual
}
/*Function:To decode a binary chromosome into a decimal integer.
Variable:None.
Note:The returned value may be plus,or minus.For different coding method,this 
value may be changed into "unsigned int".*/
long DecodeChromosome(char * string, int point, int length)
{
	int i;
	long decimal = 0L;
	char * pointer;
	for (i = 0, pointer = string + point; i < length; i++, pointer++)
	{
		decimal += (*pointer - '0') << (length - 1 - i);
	}
	return (decimal);
}
/*Function:To calcluate object value.
Variable:None.
note:For different problem, user must change these code.
This example is dealing with Rosenbrock function.
Rosenbrock function is defined as:
f(x1,x2)=100*(x1^2-x2)^2+(1-x1)^2
Its maximal value is:
f(-2.048,-2.048)=3905.926227*/
void CalculateObjectValue()
{
	int i;
	long temp1, temp2;
	double x1, x2;
	//Rosenbrock function
	for (i = 0; i < PopSize; i++)
	{
		temp1 = DecodeChromosome(population[i].chrom, 0, LENGTH1);
		temp2 = DecodeChromosome(population[i].chrom, LENGTH1, LENGTH2);
		x1 = 4.096*temp1 / 1023.0 - 2.048;
		x2 = 4.096*temp2 / 1023.0 - 2.048;
		population[i].value = 100 * (x1*x1 - x2)*(x1*x1 - x2) + (1 - x1)*(1 - x1);
	}
}
/*Function:To calculate fitness value.
Variable:None.*/
void CalculateFitnessValue()
{
	int i;
	double temp;
	for (i = 0; i < PopSize; i++)
	{
		if (FunctionMode == MAXIMIZATION)//maximization
		{
			if ((population[i].value + Cmin) > 0.0)
			{
				temp = Cmin + population[i].value;
			}
			else
			{
				temp = 0.0;
			}
		}
		else if (FunctionMode == MINIMIZATION)//minimization
		{
			if (population[i].value < Cmax)
			{
				temp = Cmax - population[i].value;
			}
			else
			{
				temp = 0.0;
			}
		}
		population[i].fitness = temp;
	}
}
/*Function:To Find out the best individual so far current generation.
Variable:None.*/
void FindBestAndWorstIndividual()
{
	int i;
	double sum = 0.0;
	//find out the best and worst individual of this generation
	bestindividual = population[0];
	worstindividual = population[0];
	for (i = 1; i < PopSize; i++)
	{
		if (population[i].fitness > bestindividual.fitness)
		{
			bestindividual = population[i];
			best_index = i;
		}
		else if (population[i].fitness < worstindividual.fitness)
		{
			worstindividual = population[i];
			worst_index = i;
		}
		sum += population[i].fitness;
	}
	//find out the best individual so far
	if (generation == 0)
	{
		//initialize the best individual
		currentbest = bestindividual;
	}
	else
	{
		if (bestindividual.fitness>currentbest.fitness)
		{
			currentbest = bestindividual;
		}
	}
}
/*Function:To perform evolution operation based on elitise
model.Elitist model is to replace the worst
individual of this generation by the current
best one.
Variable:None.*/
void PerformEvolution()
{
	if (bestindividual.fitness > currentbest.fitness)
	{
		currentbest = population[best_index];
	}
	else
	{
		population[worst_index] = currentbest;
	}
}
/*Function:To reproduce a chromosome by
proportional selection.
Variable:None.*/
void SelectionOperator()
{
	int i, index;
	double p, sum = 0.0;
	double cfitness[POPSIZE];//cumulative fitness value
	struct individual newpopulation[POPSIZE];
	//calculate relative fitness
	for (i = 0; i < PopSize; i++)
	{
		sum += population[i].fitness;
	}
	for (i = 0; i < PopSize; i++)
	{
		cfitness[i] = population[i].fitness / sum;
	}
	//calculate cumulative fitness
	for (i = 1; i < PopSize; i++)
	{
		cfitness[i] = cfitness[i - 1] + cfitness[i];
	}
	//selection operation
	for (i = 0; i < PopSize; i++)
	{
		p = rand() % 1000 / 1000.0;
		index = 0;
		while (p>cfitness[index])
		{
			index++;
		}
		newpopulation[i] = population[index];
	}
	for (i = 0; i < PopSize; i++)
	{
		population[i] = newpopulation[i];
	}
}
/*Function:Crossover two chromosome by means 
 of one point crossover.
 Variable:None.*/
void CrossoverOperator()
{
	int i, j;
	int index[POPSIZE];
	int point, temp;
	double p;
	char ch;
	//make a pair of individual randomly
	for (i = 0; i < PopSize; i++)
	{
		index[i] = i;
	}
	for (i = 0; i < PopSize; i++)
	{
		point = rand() % (PopSize - i);
		temp = index[i];
		index[i] = index[i + point];
		index[point + i] = temp;
	}
	//one point crossover operation
	for (i = 0; i < PopSize - 1; i += 2)
	{
		p = rand() % 1000 / 1000.0;
		if (p < Pc)
		{
			point = rand() % (CHROMLENGTH - 1) + 1;
			for (j = point; j < CHROMLENGTH; j++)
			{
				ch = population[index[i]].chrom[j];
				population[index[i]].chrom[j] = population[index[i + 1]].chrom[j];
				population[index[i + 1]].chrom[j] = ch;
			}
		}
	}
}
/*Function:Mutation of a chromosome.
Variable:None*/
void MutationOperator()
{
	int i, j;
	double p;
	//bit mutation
	for (i = 0; i < PopSize; i++){
		for (j = 0; j < CHROMLENGTH; j++){
			p = rand() % 1000 / 1000.0;
			if (p < Pm){
				population[i].chrom[j] = (population[i].chrom[j] == '0') ? '1' : '0';
			}
		}
	}

}
/*Function:Output the results of current population.
Variable:None.*/
void OutputTextReport()
{
	int i;
	double sum;//temporary sum
	double average;//average of population object value
	//calculate average object value
	sum = 0.0;
	for (i = 0; i < PopSize; i++)
	{
		sum += population[i].value;
	}
	average = sum / PopSize;
	//print results of this population
	printf("gen=%d,avg=%f,best=%f,", generation, average, currentbest.value);
	printf("chromosome=");
	for (i = 0; i < CHROMLENGTH; i++)
	{
		printf("%c", currentbest.chrom[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338