用node实现遗传算法

简介

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

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

源码

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

asgc-ai是傲世孤尘开源的一款基于node的人工智能算法库,本遗传算法集成于其中,本算法调用了一些asgc-ai中的公共方法,下面只给出遗传算法的核心实现,因此要获取完整的代码请点击这里

engine.js

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
var log = require('../../common/log');
var Nature = require('./nature');

/********************************************************/
/*遗传算法引擎 */
/*负责与客户端进行交互,协调大自然、个体的正常运转 */
/********************************************************/



/**
*函数名:Engine
*功能概要:构造函数
*param@1popSize:种群大小
*param@2mutationRate:基因突变的概率
*param@3maxPerturbation:最大的变异步长
*param@4generationCount:种群繁衍的代数
*param@5leftInterval:左区间
*param@6rightInterval:右区间
*param@7assessmentFunction:个体适应度评估函数
*返回值:无
**/
function Engine(popSize,mutationRate,generationCount,leftInterval,rightInterval,assessmentFunction){
if(!(this instanceof Engine)){
throw new Error('调用方式有误!');
}

log.out('Engine Constructor Invoketion!');

//大自然
this.nature = new Nature(popSize,mutationRate,(rightInterval-leftInterval)/4000,leftInterval,rightInterval,assessmentFunction);
//种群进化代数
this.generationCount = generationCount;
}

/**
*函数名:OnStart
*功能概要:让种群开始进化
*params无
*返回值:无
**/
Engine.prototype.OnStart = function(){
log.out("Engine OnStart Method Invoketion!\n");
log.out("-------------------------------------------------\n");
log.out("第0代种群:\n");
log.out("适应度总和:%f\n",this.nature.totalFitness);
log.out("最优适应度:%f\n",this.nature.bestFitness);
log.out("平均适应度:%f\n",this.nature.averageFitness);
log.out("最差适应度:%f\n",this.nature.worstFitness);

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

log.out("最优个体首次出现于于第%d代\n",this.nature.first);
}

/**
*函数名:GetBeseFitness
*功能概要:获取环境中最优个体的适应度
*params无
*返回值:最优个体的适应度
**/
Engine.prototype.GetBeseFitness = function(){
return this.nature.bestIndividual.fitness;
}

/**
*函数名:GetBestChromosome
*功能概要:获取环境中最优个体的基因型
*params无
*返回值:最优个体的基因型
**/
Engine.prototype.GetBestChromosome = function(){
return this.nature.bestIndividual.vecChromosome[0];
}

module.exports = Engine;

nature.js

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
var log = require('../../common/log');
var math = require('../../common/math');
var Individual = require('./individual');

var random = math.random;
var DOUBLE_MIN_VALUE = math.consts.DOUBLE_MIN_VALUE;
var DOUBLE_MAX_VALUE = math.consts.DOUBLE_MAX_VALUE;

/**************************************************************************/
/*大自然 */
/*引导种群的进化方向 */
/**************************************************************************/


/**
*函数名:Nature
*功能概要:构造函数
*param@1popSize:种群大小
*param@2mutationRate:基因突变的概率
*param@3maxPerturbation:最大的变异步长
*param@4leftInterval:左区间
*param@5rightInterval:右区间
*param@6assessmentFunction:个体适应度评估函数
*返回值:无
**/
function Nature(popSize,mutationRate,maxPerturbation,leftInterval,rightInterval,assessmentFunction){
if(!(this instanceof Nature)){
throw new Error('调用方式有误!');
}

//种群大小
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;
//种群
this.population = [];

for(var i=0;i<popSize;i++){
var individual = new Individual();
individual.vecChromosome.push(random.randomIntLCRC(leftInterval,rightInterval));
individual.fitness = assessmentFunction(individual.vecChromosome[0]);
this.population.push(individual);
}

this.CalculateFitness();
}

/**
*函数名:CalculateFitness
*功能概要: 统计整个种群的进化数据
*params无
*返回值:无
**/
Nature.prototype.CalculateFitness = function(){
this.population.sort((a,b) => a.fitness - b.fitness);
this.totalFitness = 0.0;
this.averageFitness = 0.0;
this.worstFitness = DOUBLE_MAX_VALUE;

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

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

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

this.averageFitness = this.totalFitness / this.popSize;
}

/**
*函数名:GetChromoRoulette
*功能概要: 轮盘赌选择
*params无
*返回值:无
**/
Nature.prototype.GetChromoRoulette = function(pop){
var individual = new Individual();
var temp = 0.0;
var slice;

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

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

return individual;
}

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

Nature.prototype.Reproduction = function(){
var temp = this.population.slice(0);
this.population = [];

while(this.population.length < this.popSize){
var individual = this.GetChromoRoulette(temp);
this.Mutate(individual);
individual.fitness = this.assessmentFunction(individual.vecChromosome[0]);
this.population.push(individual);
}

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

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

this.generation++;
this.CalculateFitness();
}

module.exports = Nature;

individual.js

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
/**************************************************************************/
/*个体 */
/*将求解过程模拟成物种的进化、最终经过自然选择存活下来的个体便为"最优解" */
/**************************************************************************/


/**
*函数名:Individual
*功能概要:默认构造函数
*param@1vecChromosome基因型
*param@1fitness适应度
*返回值:无
**/
function Individual(vecChromosome,fitness){
if(!(this instanceof Individual)){
throw new Error('调用方式有误!');
}

//基因型
this.vecChromosome = vecChromosome || [];
//个体适应度
this.fitness = fitness || 0;
}

/**
*函数名:clone
*功能概要:复制对象
*返回值:复制后生成的对象
**/
Individual.prototype.clone = function(){
var individual = new Individual();
individual.fitness = this.fitness;
individual.vecChromosome = this.vecChromosome.slice(0);

return individual;
}

module.exports = Individual;

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var genetic = require('asgc-ai').genetic;

//是否打印进化过程中的日志
genetic.setLog(true);

var engine = new genetic.Engine(500,0.8,300,0,500,function(v){
return 2 * v + 1;
//return Math.sin(v);
});

engine.OnStart();


console.log("种群最优个体适应度:%f",engine.GetBeseFitness());
console.log("种群最优个体基因型:%f",engine.GetBestChromosome());
你的鼓励,是我前进的动力!