前言
介绍
遗传算法思路最开始来源于达尔文的进化论。可以简单设想成某物种表示某个性状的某条基因，基于变异和自然选择，经过N代的遗传、交叉、变异、复制以及选择等过程，进化出最优或者较优的基因/染色体。其实思路比较简单，就是引入随机的变异，由于染色体基因点位众多，经过多次多代的进化之后，会得到最终的基因表现。
像这样可以适应很多问题的算法还有模拟退火算法、粒子群算法、蚁群算法、禁忌搜索等等，统称为元启发式算法（Meta-heuristic algorithms）。具体遗传算法来说，包括产线排产算法、节点调度类型问题、函数的全局最优解。。。
KeyWords：随机生成、变异、适应函数、终止条件
定义好基因，写好繁衍、变异、评价适应性、淘汰和终止的代码之后，只需要随机产生一个适当大小的种群，然后让它这样一代代的繁衍、变异和淘汰下去，到最后终止我们就会获得一个想要的结果。
概念1 基因、染色体、种群
进行数学建模，这个问题的一个可行解对应一条染色体。一般来讲我们只需要某个问题的一个解决方案，很有可能就是一个一维的数组。
比如对于3x+2Y+4Z<100这个问题来说，[1,2,3]就是一个可行解，就是一条染色体，点位1,2,3就是组成染色体的基因。
基因组成染色体，染色体组成种群。
种群数量我们也假定是不变的，出生率和死亡率保持一致。至于种群数量增长是否影响最终结果，暂时也不考虑。
概念2 适应度函数
自然怎么选择呢，在实际的进化过程中，环境是扮演自然选择的上帝。对应到算法中，我们对这条染色体或者基因有一个判定它好的、适宜的标准。算法的总体目标：选择好的，淘汰差的。
在每次迭代或者进化中，都会计算适应度，基于适应度来评判和选择。
概念3 交叉
交叉的过程保留基因，但是会进行染色体的重组。实际中你可以跟交配过程联系起来，这样的一次过程叫做进化。
交叉的过程：
上一代染色体中选出一条爸爸和一条妈妈，用轮盘赌的算法来选（选择的基准是适应度概率分布）。选择爸爸和妈妈的操作完全平等。
随机一个位置，将爸爸和妈妈的染色体交叉互换，即形成1条完成交叉的下一代染色体。
概念4 变异
对于交叉后得到的染色体，随机选择若干染色体的若干随机位置，进行若干基因的突变。突变的方向在一般问题中也应该是随机的。我的理解，在自然过程中应该也是随机的。
突变的基因比例会对最终的结果造成怎样的影响暂时还没有研究。
概念5 复制/继承
对于上一代种群中适应度最为优秀的若干染色体（适应度最好的），进行完全的继承，模拟适者生存。
对于每一代需要生成的种群中的N个个体/N条染色体，其中需要交叉的M条，那么需要复制的就是N-M条。这个比例怎么约定，暂时不说，我的理解肯定完全遗传的数量要少很多。
概念6 自然选择
这个过程体现在每一代进化过程中，包括复制本身以及交叉的选择策略。核心是适应度函数。
其他知识
介绍相关涉及知识时，包括我在学习过程中看博文遇到最普遍的问题就是。虽然比如轮盘赌这样的算法广泛应用在遗传算法中，但是很多将遗传算法和轮盘赌混着来讲实在是太蠢了，对于我们的目标而言，我们需要轮盘赌算法给我们的输出很简单，我们只需要知道在某一步为什么用这个算法来选择即可，所以独立的介绍轮盘赌的思想才是目标读者最应该也最愿意看到的。
矩阵排序等算法
不再详细介绍。
轮盘赌算法
这个本质上是一个概率学上的样本选择问题。
各个个体被选中的概率与其适应度函数值大小成正比，它是为了防止适应度数值较小的个体被直接淘汰而提出的。
概率分布累计为1的一个空间，要恰当的选择一定数量的样本，来使样本选择反应真实的概率分布（否则，很有可能大概率选择那些分布较宽的概率区间）。
避免小概率的个体被完全淘汰，尽可能还原真实的选择样本最优分布。
[图-轮盘赌]
轮盘赌算法的实现步骤为:
（i）初始化各个个体的适应度值（适应度值就是某个数值，什么数据都可以，只是对于不同的问题，这个适应度值代表的意义不一样）
（ii）根据公式计算各个个体的个体选择概率和累积概率
（iii）在区间[0 1]之间随机生成一个数，判断该数落在哪个区间内，如果落在某个区间，则该区间被选中。
代码如下：1
2
3
4
5
6
7
8
9
10function RWS(selectionProbability) {
var sum = 0;
var rand = Math.random();//0~1
for (var i=0; i<selectionProbability.length; i++) {
sum += selectionProbability[i];
if (sum >= rand) {
return i;
}
}
}
编码问题
待补充。其实就是如果用二进制，会简化运算次数。但是额外的需要进行编解码。比如一个染色体有8位，二进制XXX3bit就可以完全表示。没有十进制直观，但是计算效率高。
算法流程和图示
下面来考虑一个遗传算法最简单的应用案例。这是一个典型的网络请求负载均衡问题。假定我们有N个任务，需要负载均衡器分布给M个服务器节点去处理。模型中每个任务的长度以及节点服务器的处理速度已知。目标是求得一种分配方案，使得任务的总处理时间最短。
初始化和输入
我们假定：
任务，100个，task矩阵，1行100列，随机初始化长度；
服务器处理节点，10个节点，1行10列，随机每个节点的处理速度；
辅助矩阵，timeMatrix，10行100列，分别是每个节点处理每个任务的时间，优化迭代算法效率；
种群数量，20个；
迭代次数，我们设定50次，相对来说基本能较好的收敛。具体动手即可；
复制概率，设置为0.2；
初始种群基因阵列，chromosomeMatrix，20X100列矩阵，随机初始化的初始种群。
每一代的适应度，adapbability，1X20矩阵，每个染色体的适应度 = 1/每条染色体的任务时长；
每一代的选择概率矩阵，selectProbability，1X20矩阵，每个染色体的Pi = ad[i]/Sum(ad[i])；
最后，我们设定一个ResultData矩阵，50行20列，记录每一次进化迭代的结果，元素的值对应的是每个个体-染色体的时长。注意对于每条染色体来说，进行任务处理的长度是，每个节点处处理时间的最大值，因为节点是并行工作的。
处理流程：
画个图
初始化第一代染色体，随机处理即可。每一次迭代计算出适应度矩阵，选择概率矩阵。
Corss
每一代里面，轮盘算法选择出一个baba，一个mama染色体，进行随机位置的交叉换位组合，每代选择出20X(1-0.2)=16条染色体。
Mutation
上一步得出的16条染色体，随机1条染色体1个位置进行变异。
Copy
选择20X0.2=4条适应度概率最大的染色体，复制到下一代。
算法流程
[遗传算法流程图]
进化次数/完成条件
1 限定进化次数
在迭代和进化一定次数后，终止遗传。这个次数可以通过大量的实验来大致确定。
2 限定范围
如果你有一个很明确的目标，比如两次进化将的差异满足一定的条件，就可以终止计算。
实际情况要看具体问题来定。
Code
伪代码流程图：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//javascript+echarts
/** * 遗传算法 *
@param iteratorNum 迭代次数 *
@param chromosomeNum 染色体数量 */
function gaSearch(iteratorNum, chromosomeNum) {
// 初始化第一代染色体
var chromosomeMatrix = createGeneration();
// 迭代繁衍
for (var itIndex=1; itIndex<iteratorNum; itIndex++) {
// 计算上一代各条染色体的适应度
calAdaptability(chromosomeMatrix);
// 计算自然选择概率
calSelectionProbability(adaptability);
// 生成新一代染色体
chromosomeMatrix = createGeneration(chromosomeMatrix);
}
}
/**
* 繁衍新一代染色体
* @param chromosomeMatrix 上一代染色体
*/
function createGeneration(chromosomeMatrix) {
// 第一代染色体，随机生成
if (chromosomeMatrix == null || chromosomeMatrix == undefined) {
var newChromosomeMatrix = [];
for (var chromosomeIndex=0; chromosomeIndex<chromosomeNum; chromosomeIndex++) {
var chromosomeMatrix_i = [];
for (var taskIndex=0; taskIndex<taskNum; taskIndex++) {
chromosomeMatrix_i.push(random(0, nodeNum-1));
}
newChromosomeMatrix.push(chromosomeMatrix_i);
}
//console.log(newChromosomeMatrix);
// 计算当前染色体的任务处理时间
calTime_oneIt(newChromosomeMatrix);
return newChromosomeMatrix;
}
// 交叉生成{crossoverMutationNum}条染色体
var newChromosomeMatrix = cross(chromosomeMatrix);
// 变异
newChromosomeMatrix = mutation(newChromosomeMatrix);
// 复制
newChromosomeMatrix = copy(chromosomeMatrix, newChromosomeMatrix);
// 计算当前染色体的任务处理时间
calTime_oneIt(newChromosomeMatrix);
return newChromosomeMatrix;
}
参考资料
参考链接
https://blog.csdn.net/qq_33649817/article/details/86582420 轮盘赌
https://github.com/bz51/GeneticAlgorithm
https://www.zhihu.com/question/23293449?utm_source=wechat_session&utm_medium=social&utm_oi=34794360537088
其它案例
随机图片组装
设想找到某个图标由三角形组成的最佳选项。
假设我们需要100个这样的三角形，每个三角形都是半透明三角形，初始100个位置方向都随机。然后我们随机选中其中的几个进行颜色或者位置的改变，这样就引入了变异。其它三角形复制到下一代即可。对于每一代我们选择跟目标图片最接近的那些（用最笨的像素逐个比对），复制一部分到下一代，进行交叉组装一部分到下一代。这个过程中一般保持种群的数量不变。这样，经过我们定义好的多少代，或者差异缩小到足够小，完成整个进化过程，得到跟目标图片最接近的组装图片基因，一个最高层一维的数据，每个元素就是这个三角形的颜色和位置。
函数极值
求解函数 f(x) = X+ 10sin(5X) + 7cos(4X) 在区间[0,9]的最大值
负载均衡问题-类似产线排产
假设有N个任务，需要负载均衡器分配给M个服务器节点去处理。每个任务的任务长度、每台服务器节点(下面简称“节点”)的处理速度已知，请给出一种任务分配方式，使得所有任务的总处理时间最短。
python遗传算法库 geatpy 谷歌即可，华人项目
https://github.com/yanshengjia/artificial-intelligence
https://github.com/bz51/GeneticAlgorithm