数学建模篇——遗传算法
- 2019 年 10 月 6 日
- 筆記
智能算法简介
智能算法是智能技术领域的一个分支。智能算法出现的原因是，人们在知识新陈代谢速度快和知识繁杂的社会里，需要用高效的数据挖掘工具从各类数据中提取有用的信息和知识，以便于提高生产效率降低生产成本。以前这些工作都是人来操作的，但后来出现了一些模仿人脑力劳动的的算法出现减少了人类的工作量，这些算法被称为智能算法，智能算法都有一个显著的特征——机械性。常用的智能算法有遗传算法、粒子群算法、蚁群算法、模拟退火算法、神经网络算法等等，今天我们介绍遗传算法。
什么是遗传算法？
遗传算法是一类借鉴生物界的进化规律（适者生存、优胜劣汰的遗传机制）演化而来的随机化搜索方法；是模拟达尔文进化论和孟德尔遗传学机理的计算模型。主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法由编码、适应度评估和遗传运算三部分组成，其中遗传运算又包括染色体的复制、变异、交叉等。
遗传算法的实现
1、编码
遗传算法的编码有浮点编码和二进制编码两种，我们介绍二进制编码规则（因为二进制编码方便染色体进行遗传、变异和突变等操作）。设某个参数的取值范围为 （L，U），使用长度为k的二进制编码表示该参数，则此时的对应关系为：
2、解码
解码的目的是为了将不直观的二进制数据还原成十进制。个体的二进制编码对应的解码公式如下所示
遗传算法的编码和解码过程在宏观上可以对应生物的基因型和表现型，微观上可以对应基因的转录和翻译。
3、交配
“交配运算”是使用单点或多点进行交叉的算子。首先随机产生一个或多个交配点的位置，然后两个个体在交配点互换部分基因编码从而形成子个体。例如，染色体S1=0100101和染色体S2=1010010交换后三位的基因，则会形成两个子个体S3=0100010和S4=1010101
4、突变
“突变运算”是使用基本的位运算进行基因突变。为了避免算法在迭代过程中种群过早收敛，对于二进制的基因编码组成的个体种群，实行基因码的小几率翻转。例如染色体S=1101101，将其第四位上的1变成0得到S’=1100101，S’可以看做原染色体通过变异产生的子染色体。
5、个体适应度评估
进化论中的适应度，是表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。
遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数来评估个体或解的优劣，并作为以后进行遗传操作的依据。由于遗传算法中，适应度函数要比较排序并在此基础上计算选择该利率，所以适应度函数的值要取正值。
6、复制
复制运算是根据个体的适应度大小决定下代遗传的可能性，设个体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))
