[翻译]原文：Genetic Algorithm for Solving Simple Mathematical Equality Problem

[翻译]地址：https://arxiv.org/ftp/arxiv/papers/1308/1308.4675.pdf

[翻译]目的：文章旨在为新手解释什么是遗传算法。并使用遗传算法这个工具一步步解决一个具体的数学问题——求解数学等式的解。

基本理念

在通过遗传算法寻找问题解的过程中，用染色体来表示一个解，一堆染色体叫做种群。染色体由基因构成，基因可以是数值的、符号的也可以是其他类型数据结构（视所解决的问题来定）。染色体通过环境适应度来衡量这个解对于问题的优劣程度。种群中的染色体通过交叉（交配）遗传到下一代，子代染色体是父代基因的组合。基因还会发生突变，遗传算法中使用交叉率和突变率来控制。

算法步骤

1. 决定染色体数目、循环代数（决定遗传多少代）、突变率和交叉率；
2. 产生染色体种群，并使用随机值初始化染色体中的基因
3. 重复步骤4-8（重复次数等于循环代数）
4. 考量每个染色体的适应值
5. 染色体选取
6. 交叉
7. 变异
8. 产生新的后代染色体
9. 得到最终解

算术问题

以求解多元一次不等式 a+2b+3c+4d=30 为例，使用遗传算法找到a b c d 值满足该等式。很显然可以使用这样一个函数衡量适应度

f (x) = |(a + 2b + 3c + 4d) - 30|

a b c d 初始化为0到30之间的一个自然数。

步骤一 初始化                            （下面步骤不完全和算法步骤对应）

随机生成六个染色体Chromosome[1-6]。

Chromosome[1] = [a;b;c;d] = [12; 5; 23; 8]

Chromosome[2] = [a;b;c;d] = [ 2; 21; 18; 3]

Chromosome[3] = [a;b;c;d] = [10; 4; 13; 14]

Chromosome[4] = [a;b;c;d] = [20; 1; 10; 6]

Chromosome[5] = [a;b;c;d] = [ 1; 4; 13; 19]

Chromosome[6] = [a;b;c;d] = [20; 5; 17; 1]

步骤二 评估

计算每个染色体的适应度。

F_obj[1] = Abs(( 12 + 2*05 + 3*23 + 4*08 ) - 30) = 93

F_obj[2] = Abs((02 + 2*21 + 3*18 + 4*03) - 30) = 80

F_obj[3] = Abs((10 + 2*04 + 3*13 + 4*14) - 30) = 83

F_obj[4] = Abs((20 + 2*01 + 3*10 + 4*06) - 30) = 46

F_obj[5] = Abs((01 + 2*04 + 3*13 + 4*19) - 30) = 94

F_obj[6] = Abs((20 + 2*05 + 3*17 + 4*01) - 30) = 55

步骤三 选择

适应度是越小越好，我们将适应度取倒数（加1避免出现除以0的错误），并归一化得到一个概率P

Fitness[1] = 1 / (1+F_obj[1]) = 1 / 94 = 0.0106

Fitness[2] = 1 / (1+F_obj[2]) = 1 / 81 = 0.0123

Fitness[3] = 1 / (1+F_obj[3]) = 1 / 84 = 0.0119

Fitness[4] = 1 / (1+F_obj[4]) = 1 / 47 = 0.0213

Fitness[5] = 1 / (1+F_obj[5]) = 1 / 95 = 0.0105

Fitness[6] = 1 / (1+F_obj[6]) = 1 / 56 = 0.0179

总计 Total = 0.0106 + 0.0123 + 0.0119 + 0.0213 + 0.0105 + 0.0179 = 0.0845

P[1] = 0.0106 / 0.0845 = 0.1254

P[2] = 0.0123 / 0.0845 = 0.1456

P[3] = 0.0119 / 0.0845 = 0.1408

P[4] = 0.0213 / 0.0845 = 0.2521

P[5] = 0.0105 / 0.0845 = 0.1243

P[6] = 0.0179 / 0.0845 = 0.2118

从结果可以看出基因4具有最高的适应度。接下来计算累计概率分布CPD：

C[1] = 0.1254

C[2] = 0.1254 + 0.1456 = 0.2710

C[3] = 0.1254 + 0.1456 + 0.1408 = 0.4118

C[4] = 0.1254 + 0.1456 + 0.1408 + 0.2521 = 0.6639

C[5] = 0.1254 + 0.1456 + 0.1408 + 0.2521 + 0.1243 = 0.7882

C[6] = 0.1254 + 0.1456 + 0.1408 + 0.2521 + 0.1243 + 0.2118 = 1.0

然后生成六个随机数R[i=1,2,3,4,5,6]，通过这六个随机数在上图中的位置区间选择新的染色体，比如，当随机数在0.4118到0.6639之间则选择染色体4。不难看出，这种方法反应了适应度好的染色体具有更大概率被选择。

随机生成的六个随机数如果是：

R[1] = 0.201

R[2] = 0.284

R[3] = 0.099

R[4] = 0.822

R[5] = 0.398

R[6] = 0.501

那么相应的六个新的染色体是：

NewChromosome[1] = Chromosome[2] = [ 2; 21; 18; 3]

NewChromosome[2] = Chromosome[3] = [10; 4; 13; 14]

NewChromosome[3] = Chromosome[1] = [12; 5; 23; 8]

NewChromosome[4] = Chromosome[6] = [20; 5; 17; 1]

NewChromosome[5] = Chromosome[3] = [10; 4; 13; 14]

NewChromosome[6] = Chromosome[4] = [20; 1; 10; 6]

 

步骤四 交叉

假设交叉率为25%（0.25），那么生成6个随机数，如果随机数小于交叉数，则对应的染色体被选择用于交叉。比如随机数为：R[1] = 0.191， R[2] = 0.259， R[3] = 0.760， R[4] = 0.006， R[5] = 0.159，R[6] = 0.340。那么得到用于交叉的三对染色体是NewChromosome[1]， NewChromosome[4] 和NewChromosome[5]。交叉方式为：

NewChromosome[1] >< NewChromosome[4]

NewChromosome[4] >< NewChromosome[5]

NewChromosome[5] >< NewChromosome[1]

下面决定从那个位置进行交叉。因为染色体长度为4，则随机生成1-(4-1) 大小的随机数，随机数用于表示基因从哪里开始交叉。

C[1] = 1 C[2] = 1 C[3] = 2

CrossChromosome[1] = [ 2; 21; 18; 3] >< [20; 5; 17; 1] = [ 2; 5; 17; 1]     // C[1] = 1

CrossChromosome[2] = [20; 5; 17; 1] >< [10; 4; 13; 14] = [20; 4; 13; 14]     // C[2] = 1

CrossChromosome[3] = [10; 4; 13; 14] >< [ 2; 21; 18; 3] = [10; 4; 18; 3]    // C[3] = 2

那么剩余的种群中则有染色体：

NewChromosome[2] = [10; 4; 13; 14]

NewChromosome[3] = [12; 5; 23; 8]

NewChromosome[6] = [20; 1; 10; 6]

CrossChromosome[1] = [ 2; 5; 17; 1]

CrossChromosome[2] = [20; 4; 13; 14]

CrossChromosome[3] = [10; 4; 18; 3] 

步骤五 突变

假设突变概率为10%（0.1）。考虑到6个染色体中每个有6个基因，那么将有4×6×0.1= 2.4 ≈ 2个基因发生突变，通过产生两个1-24范围的数值得到突变染色体位置（假设为12和18）。接着还产生两个1-30之间的随机数作为突变后的结果（假设为2 和 5）。那么得到新的种群如下（红色为突变基因）：

Chromosome[1] = [10; 4; 13; 14]

Chromosome[2] = [12; 5; 23; 8]

Chromosome[3] = [20; 1; 10; 2]

Chromosome[4] = [ 2; 5; 17; 1]

Chromosome[5] = [20; 5; 13; 14]

Chromosome[6] = [10; 4; 18; 3] 

步骤六 回到步骤二进行迭代

步骤七 至循环代数次结束

步骤六和步骤七类似，不再赘述。

整个过程如下图所示：

赫布学习（Hebb  Learning）基于赫布规则（Hebb Rule）:

When an axon of cell A is near enough to excite a cell B and repeatedly or persistently takes part in firing it, some growth process or metabolic change takes place in one or both cells such that A’s efficiency, as one of cells firing B, is increase.

赫布规则大致说的是如果神经细胞刺激不断加强，两者联系加强。

首先看看一个简单的神经网络的结构（以识别为例）：

左边P（R×1的向量） 是输入，表示待识别物体的R 个特征。W是权重矩阵，通过计算特征和权重矩阵的乘法，用于形成S 个结果，S是判别函数。最终形成a （S×1向量）的结果。下面以位矩阵的数字识别为例：

问题：有6×5大小的像素矩阵用于表示数字0,1,2，如下图所示

每个数字矩阵用一个一维的特征向量表示，比如0 对应的特征向量为p1：

p1 = [-1 1 1 1 -1 1,-1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]^T

其中-1代表这个像素不上色，1反之，t1-t3分表代表结果是0,1,2。那我们的问题是如果识别带有误差，或者只有部分像素的例子。如下面图中应该识别为多少呢？

 

 

 

 

分析：使用如下的神经网络，

权重矩阵W通过下面等式计算：

W = p1·p1^T + p2·p2^T + p3·p3^T

在我们这个例子里，权重函数如下

S判别函数我们使用hardlims，当输入大于0则结果为1，当小于0 则结果为-1. 针对一个特定识别过程（如下图）：

下面是实现这个过程的Python 代码，使用到numpy 库。

#_*_coding:utf-8_*_
import os
import sys
import numpy as np
mat0 = np.matrix([-1,1,1,1,-1,\
1,-1,-1,-1,1,\
1,-1,-1,-1,1,\
1,-1,-1,-1,1,\
1,-1,-1,-1,1,\
-1,1,1,1,-1])
mat1 = np.matrix([-1,1,1,-1,-1,\
-1,-1,1,-1,-1,\
-1,-1,1,-1,-1,\
-1,-1,1,-1,-1,\
-1,-1,1,-1,-1,\
-1,-1,1,-1,-1])
mat2 = np.matrix([1,1,1,-1,-1,\
-1,-1,-1,1,-1,\
-1,-1,-1,1,-1,\
-1,1,1,-1,-1,\
-1,1,-1,-1,-1,\
-1,1,1,1,1])
mat0t = mat0.getT()
mat0p = mat0t.dot(mat0)
mat1t = mat1.getT()
mat1p = mat1t.dot(mat1)
mat2t = mat2.getT()
mat2p = mat2t.dot(mat2)
print "===============matrix 0===================="
print(mat0p)
print "===============matrix 1===================="
print(mat1p)
print "===============matrix 2===================="
print(mat2p)
matw = mat0p+mat1p+mat2p
print "===============matrix sum===================="
print matw
testa0 = np.matrix([-1,1,1,1,-1,\
1,-1,-1,-1,1,\
1,-1,-1,-1,1,\
-1,-1,-1,-1,-1,\
-1,-1,-1,-1,-1,\
-1,-1,-1,-1,-1])
mata0 = matw.dot(testa0.getT())
print "=========== raw mata0 =============="
print mata0
for ii in xrange(mata0.size):
if mata0[ii] > 0:
mata0[ii] = 1
else:
mata0[ii] = -1
print "============= After testa0 ================="
print mata0


备注：这是Neural Network Design 的一个例子，作者用python 代码实现了下。