AI算法09-遗传算法Genetic Algorithm | GA - 酸梨子-专注技术分享

什么是遗传算法

遗传算法的科学定义

遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，不需要确定的规则就能自动获取和指导优化的搜索空间，自适应地调整搜索方向。

遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

遗传算法的执行过程

遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。

染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。

初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。

这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

遗传算法过程图解

遗传算法思想

借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解。这样进化N代后就很有可能会进化出适应度函数值很高的个体。

举个例子，使用遗传算法解决“0-1背包问题”的思路：0-1背包的解可以编码为一串0-1字符串（0：不取，1：取）；首先，随机产生M个0-1字符串，然后评价这些0-1字符串作为0-1背包问题的解的优劣；然后，随机选择一些字符串通过交叉、突变等操作产生下一代的M个字符串，而且较优的解被选中的概率要比较高。这样经过G代的进化后就可能会产生出0-1背包问题的一个“近似最优解”。

遗传算法的特点

遗传算法是模拟生物在自然环境中的遗传和进化的过程而形成的一种并行、高效、全局搜索的方法，它主要有以下特点：

遗传算法以决策变量的编码作为运算对象。这种对决策变量的编码处理方式，使得在优化计算过程中可以借鉴生物学中染色体和基因等概念，模仿自然界中生物的遗传和进化等的机理，方便地应用遗传操作算子。特别是对一些只有代码概念而无数值概念或很难有数值概念的优化问题，编码处理方式更显示出了其独特的优越性。
遗传算法直接以目标函数值作为搜索信息。它仅使用由目标函数值变换来的适应度函数值，就可确定进一步的搜索方向和搜索范围，而不需要目标函数的导数值等其他一些辅助信息。实际应用中很多函数无法或很难求导，甚至根本不存在导数，对于这类目标函数的优化和组合优化问题，遗传算法就显示了其高度的优越性，因为它避开了函数求导这个障碍。
遗传算法同时使用多个搜索点的搜索信息。遗传算法对最优解的搜索过程，是从一个由很多个体所组成的初始群体开始的，而不是从单一的个体开始的。对这个群体所进行的选择、交叉、变异等运算，产生出新一代的群体，其中包括了很多群体信息。这些信息可以避免搜索一些不必搜索的点，相当于搜索了更多的点，这是遗传算法所特有的一种隐含并行性。
遗传算法是一种基于概率的搜索技术。遗传算法属于自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。虽然这种概率特性也会使群体中产生一些适应度不高的个体，但随着进化过程的进行，新的群体中总会更多地产生出优良的个体。与其他一些算法相比，遗传算法的鲁棒性使得参数对其搜索效果的影响尽可能小。
遗传算法具有自组织、自适应和自学习等特性。当遗传算法利用进化过程获得信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。同时，遗传算法具有可扩展性，易于同别的算法相结合，生成综合双方优势的混合算法。

遗传算法的实现

编码

遗传算法的编码有浮点编码和二进制编码两种，我们介绍二进制编码规则（因为二进制编码方便染色体进行遗传、变异和突变等操作）。设某个参数的取值范围为（L，U），使用长度为k的二进制编码表示该参数，则此时的对应关系为：

解码

解码的目的是为了将不直观的二进制数据还原成十进制。个体的二进制编码对应的解码公式如下所示：

遗传算法的编码和解码过程在宏观上可以对应生物的基因型和表现型，微观上可以对应基因的转录和翻译。

交配

“交配运算”是使用单点或多点进行交叉的算子。首先随机产生一个或多个交配点的位置，然后两个个体在交配点互换部分基因编码从而形成子个体。例如，染色体S1=0100101和染色体S2=1010010交换后三位的基因，则会形成两个子个体S3=0100010和S4=1010101

突变

“突变运算”是使用基本的位运算进行基因突变。为了避免算法在迭代过程中种群过早收敛，对于二进制的基因编码组成的个体种群，实行基因码的小几率翻转。例如染色体S=1101101，将其第四位上的1变成0得到S’=1100101，S’可以看做原染色体通过变异产生的子染色体。

个体适应度评估

进化论中的适应度，是表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。

遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数来评估个体或解的优劣，并作为以后进行遗传操作的依据。由于遗传算法中，适应度函数要比较排序并在此基础上计算选择该利率，所以适应度函数的值要取正值。

复制

复制运算是根据个体的适应度大小决定下代遗传的可能性，设个体i的适应度为 fi，则个体i被选取的概率为

若个体适应度高，则被选取的几率大，它的基因在种群中扩散的概率就会比较大。个体复制几率比较小的个体，在遗传的过程中会逐渐被淘汰。

伪代码

#染色体的类

class Chrom:

    chrom = []

    fitness = 0


    def showChrom(self):

        print(self.chrom)


    def showFitness(self):

        print(self.fitness)



#基础参数

N = 200  #种群内个体数目

mut = 0.2  #突变概率

acr = 0.2  #交叉概率



pop = {}  #存储染色体的字典

for i in range(N):

    pop['chrom' + str(i)] = Chrom()

chromNodes = 2  #染色体节点数（变量个数）

iterNum = 10000  #迭代次数

chromRange = [[0, 10], [0, 10]]  #染色体范围

aveFitnessList = []  #平均适应度

bestFitnessList = []  #最优适应度



#初始染色体

pop = Genetic.initialize(pop, chromNodes, chromRange)

pop = Fitness.calFitness(pop)  #计算适应度

bestChrom = Genetic.findBest(pop)  #寻找最优染色体

bestFitnessList.append(bestChrom[1])  #将当前最优适应度压入列表中

aveFitnessList.append(Genetic.calAveFitness(pop, N))  #计算并存储平均适应度



#开始迭代

for t in range(iterNum):

    #染色体突变

    pop = Genetic.mutChrom(pop, mut, chromNodes, bestChrom, chromRange)

    #染色体交换

    pop = Genetic.acrChrom(pop, acr, chromNodes)

    #寻找最优

    nowBestChrom = Genetic.findBest(pop)

    #比较前一个时间的最优和现在的最优

    bestChrom = Genetic.compareChrom(nowBestChrom, bestChrom)

    #寻找与替换最劣

    worseChrom = Genetic.findWorse(pop)

    pop[worseChrom[0]].chrom = pop[bestChrom[0]].chrom.copy()

    pop[worseChrom[0]].fitness = pop[bestChrom[0]].fitness

    #存储最优与平均

    bestFitnessList.append(bestChrom[1])

    aveFitnessList.append(Genetic.calAveFitness(pop, N))