用c++实现遗传算法

简介

最优解问题,可以想象成生物的进化:生物进化需要一个初始的种群,即对应程序中需要给出一组问题的初始解,初始解的产生应尽可能简单,原则上问题的求解过程不应该依赖于初始解的设定,而应该依赖于进化。生物进行基因突变、基因重组,是生物多样化的基础,因此程序中为了避免陷入局部最优解,也需要引入类似的操作,下面的程序引入了基因突变。大自然对种群进行自然选择,保证了优良个体有更多的机会遗传到下一代,从而实现进化。所以程序中需要大自然这一角色对控制种群的进化方向。

既然有基因,程序中不可避免就涉及到基因的编码与解码。按照更接近于大自然的方式,可以使用二进制编码,更容易实现基因突变和基因重组,但需要不断进行编码解码,运算效率稍低。这里,我采用的是浮点数编码,写的第一个版本,为了简单,这里只引入了基因突变。相当于无性繁殖,比有性繁殖进化慢,故可以加长进化代数,以求更加接近最优解。

源码

以下是遗传算法的c++实现,大自然(Nature)、个体(Individual)、遗传算法引擎(MyGeneticAlgorithm)是本算法的核心。

GeneticAlgorithmEngine.h

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
/********************************************************/
/*遗传算法引擎 */
/********************************************************/

#pragma once

#ifndef _YW_MY_GENETIC_ALGORITHM_GENETIC_ALGORITHM_ENGINE_H_H_
#define _YW_MY_GENETIC_ALGORITHM_GENETIC_ALGORITHM_ENGINE_H_H_

#include "Individual.h"
#include "Math.h"
#include "Nature.h"
#include "Log.h"
#include <stdio.h>


namespace YW{

namespace MyGeneticAlgorithm{

/********************************************************/
/*遗传算法引擎 */
/*负责与客户端进行交互,协调大自然、个体的正常运转 */
/********************************************************/
class GeneticAlgorithmEngine{
public:
/**
*函数名:GeneticAlgorithmEngine
*功能概要:构造函数
*param@1popSize:种群大小
*param@2mutationRate:基因突变的概率
*param@3maxPerturbation:最大的变异步长
*param@4generationCount:种群繁衍的代数
*param@5leftInterval:左区间
*param@6rightInterval:右区间
*param@7assessmentFunction:个体适应度评估函数
*返回值:无
**/
GeneticAlgorithmEngine(int popSize,double mutationRate,int generationCount,double leftInterval,double rightInterval,ASSESSMENT_FUNCTION assessmentFunction){
LOG("GeneticAlgorithmEngine Constructor Invoketion!\n");
this->nature = new Nature(popSize,mutationRate,(rightInterval-leftInterval)/4000,leftInterval,rightInterval,assessmentFunction);
this->generationCount = generationCount;
}

/**
*函数名:OnStart
*功能概要:让种群开始进化
*params无
*返回值:无
**/
void OnStart(){
LOG("GeneticAlgorithmEngine OnStart Method Invoketion!\n");
LOG("-------------------------------------------------\n");
LOG("第0代种群:\n");
LOG("适应度总和:%.10lf\n",nature->totalFitness);
LOG("最优适应度:%.10lf\n",nature->bestFitness);
LOG("平均适应度:%.10lf\n",nature->averageFitness);
LOG("最差适应度:%.10lf\n",nature->worstFitness);

for(int i=0;i<generationCount;i++){
nature->Reproduction();
LOG("-------------------------------------------------\n");
LOG("第%d代种群:\n",i+1);
LOG("适应度总和:%.10lf\n",nature->totalFitness);
LOG("最优适应度:%.10lf\n",nature->bestFitness);
LOG("平均适应度:%.10lf\n",nature->averageFitness);
LOG("最差适应度:%.10lf\n",nature->worstFitness);
}

LOG("最优个体首次出现于于第%d代\n",nature->first);
}

/**
*函数名:GetBeseFitness
*功能概要:获取环境中最优个体的适应度
*params无
*返回值:最优个体的适应度
**/
double GetBeseFitness(){
LOG("GeneticAlgorithmEngine GetBeseFitness Method Invoketion!\n");
return nature->bestIndividual.fitness;
}

/**
*函数名:GetBestChromosome
*功能概要:获取环境中最优个体的基因型
*params无
*返回值:最优个体的基因型
**/
double GetBestChromosome(){
LOG("GeneticAlgorithmEngine GetBestChromosome Method Invoketion!\n");
return nature->bestIndividual.vecChromosome[0];
}
private:
Nature *nature;//大自然、环境
int generationCount;//种群繁衍的代数
};

};

};

#endif

Individual.h

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
/********************************************************/
/*个体 */
/********************************************************/

#pragma once

#ifndef _YW_MY_GENETIC_ALGORITHM_INDIVIDUAL_H_H_
#define _YW_MY_GENETIC_ALGORITHM_INDIVIDUAL_H_H_

#include<vector>


namespace YW{

namespace MyGeneticAlgorithm{

using namespace std;

/**************************************************************************/
/*个体 */
/*将求解过程模拟成物种的进化、最终经过自然选择存活下来的个体便为"最优解" */
/**************************************************************************/
class Individual{
public:
friend class Nature;
friend class Reproduction;
friend class GeneticAlgorithmEngine;

public:
/**
*函数名:Individual
*功能概要:复制构造函数
*param@1individual:复制的对象
*返回值:无
**/
Individual(const Individual &individual){
this->fitness = individual.fitness;
this->vecChromosome = individual.vecChromosome;
}

/**
*函数名:Individual
*功能概要:默认构造函数
*param@1无
*返回值:无
**/
Individual():fitness(0){

}

/**
*函数名:Individual
*功能概要:构造函数
*param@1vec基因型
*param@1value适应度
*返回值:无
**/
Individual(vector<double> vec,double value = 0):vecChromosome(vec),fitness(value){

}

/**
*函数名:<
*功能概要:个体之间优劣性的比较,依据适应度
*param@1individual参与比较的个体
*返回值:bool比较结果
**/
bool operator <(Individual &individual){
return this->fitness < individual.fitness;
}


private:
vector<double> vecChromosome;//染色体序列,采用浮点数对基因进行编码
double fitness;//个体适应度
};

};

};


#endif

Nature.h

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
/********************************************************/
/*大自然、环境 */
/********************************************************/

#pragma once

#ifndef _YW_MY_GENETIC_ALGORITHM_NATURE_H_H_
#define _YW_MY_GENETIC_ALGORITHM_NATURE_H_H_

#include<vector>
#include <algorithm>
#include "Math.h"
#include "Individual.h"
#include "Random.h"

namespace YW{

namespace MyGeneticAlgorithm{

using namespace std;
using namespace YW::MyLiBrary::Math;
typedef double (*ASSESSMENT_FUNCTION)(double value);

/**************************************************************************/
/*大自然 */
/*引导种群的进化方向 */
/**************************************************************************/
class Nature{
public:
friend class GeneticAlgorithmEngine;

public:
/**
*函数名:Nature
*功能概要:构造函数
*param@1popSize:种群大小
*param@2mutationRate:基因突变的概率
*param@3maxPerturbation:最大的变异步长
*param@4leftInterval:左区间
*param@5rightInterval:右区间
*param@6assessmentFunction:个体适应度评估函数
*返回值:无
**/
Nature(int popSize,double mutationRate,double maxPerturbation,double leftInterval,double rightInterval,ASSESSMENT_FUNCTION assessmentFunction){
this->popSize = popSize;
this->mutationRate = mutationRate;
this->maxPerturbation = maxPerturbation;
this->leftInterval = leftInterval;
this->rightInterval = rightInterval;
this->assessmentFunction = assessmentFunction;

this->totalFitness = 0.0;
this->bestFitness = DOUBLE_MIN_VALUE;
this->averageFitness = 0.0;
this->worstFitness = DOUBLE_MAX_VALUE;
this->generation = 0;

for(int i=0;i<popSize;i++){
Individual individual;
individual.vecChromosome.push_back(random.GetRandom(leftInterval,rightInterval));
individual.fitness = assessmentFunction(individual.vecChromosome[0]);
population.push_back(individual);
}

CalculateFitness();
}

/**
*函数名:CalculateFitness
*功能概要: 统计整个种群的进化数据
*params无
*返回值:无
**/
void CalculateFitness(){

sort(population.begin(),population.end());
this->totalFitness = 0.0;
this->averageFitness = 0.0;
this->worstFitness = DOUBLE_MAX_VALUE;

for(int i=0;i<popSize;i++){
totalFitness += population[i].fitness;

if(population[i].fitness>bestFitness){
bestFitness = population[i].fitness;
bestIndividual = population[i];
first = generation;
}

if(population[i].fitness<worstFitness){
worstFitness = population[i].fitness;
}
}

averageFitness = totalFitness / popSize;
}

/**
*函数名:GetChromoRoulette
*功能概要: 轮盘赌选择
*params无
*返回值:无
**/
Individual GetChromoRoulette(vector<Individual>&pop){

Individual individual;
double temp = 0.0;
double slice;

if(worstFitness>=0){
slice = random.GetRandom(0,1)*totalFitness;
for(int i=0;i<popSize;i++){
temp += pop[i].fitness;
if(temp>=slice){
individual = pop[i];
break;
}
}
}else{
double pseudoTotalFitness = totalFitness + (-1)*popSize*worstFitness;
slice = random.GetRandom(0,1)*pseudoTotalFitness;

for(int i=0;i<popSize;i++){
temp += pop[i].fitness+(-1)*worstFitness;
if(temp>=slice){
individual = pop[i];
break;
}
}
}
//避免因浮点数的精度误差造成错误
if(individual.fitness == 0){
individual = pop[popSize-1];
}

return individual;
}

/**
*函数名:Mutate
*功能概要: 基因突变
*params无
*返回值:无
**/
void Mutate(Individual &individual){
if(random.GetRandom(0,1)<= mutationRate){
individual.vecChromosome[0] += (random.GetRandom(0,1)-0.5)*maxPerturbation;
if(individual.vecChromosome[0]>rightInterval){
individual.vecChromosome[0] = rightInterval;
}
if(individual.vecChromosome[0]<leftInterval){
individual.vecChromosome[0] = leftInterval;
}
}
}

/**
*函数名:Reproduction
*功能概要: 繁殖、产生下一代种群
*params无
*返回值:无
**/
void Reproduction(){

vector<Individual> temp = population;
population.clear();

while(population.size()<popSize){
Individual individual = GetChromoRoulette(temp);
Mutate(individual);
individual.fitness = assessmentFunction(individual.vecChromosome[0]);
population.push_back(individual);
}

bool flag = true;
for(int i=0;i<popSize;i++){
if(population[i].fitness>=bestIndividual.fitness){
flag = false;
break;
}
}

if(flag){
population[(int)random.GetRandom(0,popSize-1)] = bestIndividual;
}

generation++;
CalculateFitness();
}

private:
vector<Individual>population;//种群
int popSize;//种群大小(人口数量)
ASSESSMENT_FUNCTION assessmentFunction;//评估函数
double totalFitness;//种群的适应度总和
double bestFitness;//种群中最优个体的适应度
double averageFitness;//种群的平均适应度
double worstFitness;//种群的最低适应度
Individual bestIndividual;//适应度最高的个体
double mutationRate;//基因突变的概率
int generation;//当前种群的代数
double maxPerturbation;//最大变异步长
double leftInterval;//左区间
double rightInterval;//右区间
int first;//最优个体首次出现的代数
};

};
};

#endif

Log.h

1
2
3
4
5
6
7
8
9
10
11
12
#pragma once

#ifndef _YW_MY_LOG_H_H_
#define _YW_MY_LOG_H_H_

#ifdef DEBUG
#define LOG printf
#else
#define LOG
#endif

#endif

Math.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/********************************************************/
/*数学函数、常量 */
/********************************************************/

#pragma once

#ifndef _YW_MY_LIBRARY_MATH_H_H_
#define _YW_MY_LIBRARY_MATH_H_H_

namespace YW{

namespace MyLiBrary{
namespace Math{
#define PI 3.14159265358979
#define DOUBLE_MAX_VALUE 1.7976931348623158e+308
#define DOUBLE_MIN_VALUE (-DOUBLE_MAX_VALUE+1)
};
};

};

#endif

Random.h

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
/********************************************************/
/*随机数 */
/********************************************************/

#pragma once

#ifndef _YW_MY_LIBRARY_MATH_RANDOM_H_H_
#define _YW_MY_LIBRARY_MATH_RANDOM_H_H_

#include <time.h>
#include <stdlib.h>

namespace YW{

namespace MyLiBrary{

namespace Math{
class Random{
public:
/**
*函数名:Random
*功能概要:构造函数
*params 无
*返回值:无
**/
Random();

/**
*函数名:GetRandom
*功能概要:产生一个随机数
*params@1 start左区间
*params@2 end右区间
*返回值: 产生的随机数
**/
double GetRandom(double start,double end);

}random;

Random::Random(){
srand(unsigned(time(0)));
}

double Random::GetRandom(double start,double end){
return start+(end-start)*rand()/RAND_MAX;
}

};

};

};

#endif

测试1

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
/********************************************************/
/*遗传算法练习 傲世孤尘 2014-10-12 */
/********************************************************/
#include <windows.h>
#include <iostream>
#include "GeneticAlgorithmEngine.h"
#include "Individual.h"
#include "Math.h"
#include <math.h>

using namespace std;
using namespace YW::MyGeneticAlgorithm;
using namespace YW::MyLiBrary::Math;

/**
*函数名:func
*功能概要: 评估个体的适应度
*param@1value基因型
*返回值:double适应度
**/
double func(double value){
//return value*sin(10*PI*value)+2.0;
//return 2*value+1;
//return (-2)*value-1;
return sin(value);
}

/**
*函数名:main
*功能概要: 程序入口
*params无
*返回值:int进程结束代码
**/
int main(){
/**
*种群大小:500
*基因突变的概率:0.8
*繁衍代数:300
*左区间:0
*右区间:4
*个体适应度评估函数:func
**/
GeneticAlgorithmEngine engine(500,0.8,300,0,4,func);
engine.OnStart();

printf("%lf\n",engine.GetBeseFitness());
printf("%lf\n",engine.GetBestChromosome());


printf("%lf\n",func(engine.GetBestChromosome()));

return 0;
}

测试2

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
/********************************************************/
/*遗传算法练习 傲世孤尘 2017-08-01 */
/********************************************************/

//#define DEBUG

#include <windows.h>
#include <iostream>
#include "GeneticAlgorithmEngine.h"
#include "Individual.h"
#include "Math.h"
#include <math.h>

using namespace std;
using namespace YW::MyGeneticAlgorithm;
using namespace YW::MyLiBrary::Math;

/**
*函数名:func
*功能概要: 评估个体的适应度
*param@1value基因型
*返回值:double适应度
**/
double func(double value){
return value*sin(15*PI*value)+2.0;
}

/**
*函数名:main
*功能概要: 程序入口
*params无
*返回值:int进程结束代码
**/
int main(){
/**
*种群大小:500
*基因突变的概率:0.8
*繁衍代数:300
*左区间:0
*右区间:4
*个体适应度评估函数:func
**/
GeneticAlgorithmEngine engine(1000,0.8,600,0,200,func);
engine.OnStart();

printf("最优个体适应度:%lf\n",engine.GetBeseFitness());
printf("最优个体基因:%lf\n",engine.GetBestChromosome());


printf("最优解:%lf\n",func(engine.GetBestChromosome()));

return 0;
}
你的鼓励,是我前进的动力!