遗传算法精讲与实践
一、遗传算法的定义
遗传算法的基本思想是参考生物学中物种“物竞天择，适者生存”的思想。在计算机中，通过给定约束条件，使初始参数不断迭代，从而接近最优解。
遗传算法可描述为：
Initialize population process-chromosome loop-while(no-solution OR generations < max-gen)crossovermutateselect new generations according to fitness end-of-loop 1234567
对于一个最优化问题，一定数量的候选解（称为个体）可抽象表示为染色体，使种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代又一代变异。在每一代中评价整个种群的适应度，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。
二、遗传算法应用（一）：计算一元函数区间最值
问题描述：计算函数f(x)=xsin10x+xcos2x在[0,5]上的最大值。
分析：
该问题中，采用二进制串来编码染色体，来表示自变量x的值，用函数的因变量作为适应度。因此，二进制转十进制的过程就是种群个体转化为解的过程，假设二进制串长度为10，转为[0,5]内的十进制的语法为：
import numpy as np bytes = 0000000001 value = np.dot(bytes, 2 ** np.arange(10)[::-1]) / float(2 ** 10 - 1) * 5 123
交叉繁衍操作如下：假设父母DNA分别为DNA1与DNA2，以F代表继承父亲DNA，M代表继承母亲DNA，那么就生成了子代DNA3。
DNA1 = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0] DNA2 = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1] [F, F, M, M, F, M, M, M, F, M] DNA3 = [1, 0, 0, 1, 1, 1, 0, 1, 1, 1] 1234
变异即随机将DNA中的一位取反，0变1，1变0。
选择操作也代表了适者生存的思想，这里将适应度作为淘汰条件，适应度越高的个体越有可能交叉繁衍。
完整代码：
import numpy as np class GA(object): def __init__(self, DNA_SIZE, POP_SIZE, CROSS_RATE, MUTATION_RATE, N_GENERATIONS, X_BOUND): self.DNA_size = DNA_SIZE self.pop_size = POP_SIZE self.cross_rate = CROSS_RATE self.mutate_rate = MUTATION_RATE self.generations = N_GENERATIONS self.bounds = X_BOUND self.populations = np.random.randint(2, size=(POP_SIZE, DNA_SIZE)) def fitness(self, y): return y + 1e-3 - np.min(y) def crossover(self, parent, pop): if np.random.rand() < self.cross_rate: i_ = np.random.randint(0, self.pop_size, size=1) cross_points = np.random.randint(0, 2, self.DNA_size).astype(np.bool) parent[cross_points] = pop[i_, cross_points] return parent def mutate(self, child): for point in range(self.DNA_size): if np.random.rand() < self.mutate_rate: child[point] = 1 if child[point] == 0 else 0 return child def select(self, pop, fit): idx = np.random.choice(np.arange(self.pop_size), size=self.pop_size, replace=True, p=fit/fit.sum()) return pop[idx] def translateDNA(self, pop): return np.dot(pop, 2 ** np.arange(self.DNA_size)[::-1]) / float(2 ** self.DNA_size - 1) * self.bounds[1] def F(self, x): return np.sin(10 * x) * x + np.cos(2 * x) * x if __name__ == '__main__': ga = GA(DNA_SIZE=10, POP_SIZE=100, CROSS_RATE=0.8, MUTATION_RATE=0.03, N_GENERATIONS=200, X_BOUND=[0, 5]) fit_DNA = [] for _ in range(ga.generations): F_values = ga.F(ga.translateDNA(ga.populations)) fit = ga.fitness(F_values) fit_DNA.append(ga.translateDNA(ga.populations[np.argmax(fit), :])) ga.populations = ga.select(ga.populations, fit) pop_copy = ga.populations.copy() for parent in ga.populations: child = ga.crossover(parent, pop_copy) child = ga.mutate(child) parent[:] = child print('最大值自变量x=', max(fit_DNA)) print('最大值y=', ga.F(max(fit_DNA)))
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253 演示
三、遗传算法应用（二）：猜句子
问题描述：给定目标句子，例如目标句为Genetic algorithm is a search algorithm used in computational mathematics to solve optimization.，由随机字符组成的句子演化成目标句。分析 基因编码对于该问题，需要一个基础字符集合，也需要一个目标字符串，如下所示：
geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!." target = "Genetic algorithm is a search algorithm used in computational mathematics to solve optimization." 12 geneSet表示所有包含的字符组成的集合，target表示目标字符串。生成初始个体
接下来需要生成初始个体，即由字符集合随机生成一个与目标字符串长度相等的字符串。适应度
遗传算法提供的适应度值是引擎获得的唯一反馈，可以引导其走向一个解决方案。在这个问题中，适应度值为当前字符串与目标字符串匹配的字符个数。变异
将字符串的任意两个位置字符调换，即可完成变异操作。展示 完整代码
import datetime import random geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!." target = "Genetic algorithm is a search algorithm used in computational mathematics to solve optimization." def generate_parent(length): genes = [] while len(genes) < length: sampleSize = min(length - len(genes), len(geneSet)) genes.extend(random.sample(geneSet, sampleSize)) return ''.join(genes) def get_fitness(guess): return sum(1 for expected, actual in zip(target, guess) if expected == actual) def mutate(parent): idx = random.randrange(0, len(parent)) childGenes = list(parent) newGene, alternate = random.sample(geneSet, 2) childGenes[idx] = alternate if childGenes[idx] == newGene else newGene return ''.join(childGenes) def display(guess, startTime): timeDiff = datetime.datetime.now() - startTime fitness = get_fitness(guess) print("{}t{}t{}".format(guess, fitness, timeDiff)) random.seed() startTime = datetime.datetime.now() bestParent = generate_parent(len(target)) bestFitness = get_fitness(bestParent) while True: child = mutate(bestParent) childFitness = get_fitness(child) if bestFitness >= childFitness: continue display(child, startTime) if childFitness >= len(bestParent): break bestFitness = childFitness bestParent = child
123456789101112131415161718192021222324252627282930313233343536373839404142 演示附上GitHub地址：遗传算法应用
相关知识
遗传算法原理与详解
遗传算法
遗传算法的基本原理与流程
人工智能 6.1遗传算法
遗传算法Python 教程（1）
多目标遗传算法NSGA2.c++源码
定稿【精编】生物信息学
使用p5.js实现神经网络与遗传算法示例
遗传算法Matlab代码实现及其在推荐系统中的应用
花卉园艺技术知识精讲课件
网址: 遗传算法精讲与实践 https://m.huajiangbk.com/newsview1388543.html
| 上一篇: 数据挖掘算法和实践（二）：决策树 |
下一篇: 乐昌市工青妇新时代文明实践所： |
