| 遗传算法 | 您所在的位置：网站首页 › 遗传算法的设计 › 遗传算法 |
遗传算法
|
首先了解一下达尔文进化论：人类在繁衍过程中，通过交配产生基因重组和变异，从而产生更好的个体，也可能是更差的个体， 每一代人接受大自然的考验，优胜略汰，适应能力强的被保存下来，差的被淘汰，使得人类对环境的适应能力越来越强；
遗传算法就是借鉴了人类的进化过程，更好地适应环境就是我们的目标（y），每一代人就是我们的可行解（取值范围内的一组 x），遗传算法就是通过不断交叉变异 x 来获取最优的 y，也可以理解为一种启发式搜索算法 基本概念 粘过来的，主要看加粗的，废话比较多 基因型(genotype)：性状染色体的内部表现； 表现型(phenotype)：染色体决定的性状的外部表现，或者说，根据基因型形成的个体的外部表现； 进化(evolution)：种群逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的。
个体（individual）：指染色体带有特征的实体； 种群（population）：个体的集合，该集合内个体数称为种群的大小。 适应度(fitness)：度量某个物种对于生存环境的适应程度。 选择(selection)：以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程。 复制(reproduction)：细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。 交叉(crossover)：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交； 变异(mutation)：交叉时可能（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状。 编码(coding)：DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。 【对 x 的另一种表达，方便交叉变异】 解码(decoding)：基因型到表现型的映射。 【把编码重新换算成 x，方便计算适应度】 算法框架 本图是遗传算法的整体流程，学会了之后看图会比较清晰
以下为专业术语，吹牛逼专用 以决策变量的编码作为运算对象，使得优化过程借鉴生物学中的概念成为可能 直接以目标函数作为搜索信息，确定搜索方向和范围，属于无导数优化 同时使用多个搜索点的搜索信息，算是一种隐含的并行性 是一种基于概率的搜索技术 具有自组织，自适应和自学习等特性 具体步骤--干货 星表示重要度以及难度 编码 ****核心是 解码后 能够 覆盖 x 的取值范围； 编码的方式对模型影响非常大，包括 算子的设计难度、模型的收敛效果等； 常用方法有 二进制编码（110110）、浮点数编码（12.3）、字符编码（AcDa） 种群初始化 **1. 最好保证初始编码为可行解，这样可以加速收敛，当然你也可以不保证，具体根据业务难易而定 2. 注意每个个体之间不能一样，个体要有区别 适应度 *****遗传算法的核心，相当于达尔文进化论中的环境，负责对可行解进行筛选； 适应度分为 单目标和多目标函数，需要根据业务进行人工设计； 适应度变换 ** 适应度变换主要是对适应度的一个衡量，如越大越好，还是越小越好，如果想求最小值，那就给适应度加个负号 生成新种群核心思想是保证好的基因尽可能保留，并存在交叉和突变； 操作思路是通过选择、交叉、变异，产生期望的可行解，淘汰不符合要求的可行解 注意事项 1. 演变过程中种群大小始终不变（如200个），每轮选择+交叉+变异共同生成 200个 个体 2. 其实还有一个环节叫 复制，也就是说 直接选择为 下一代，不做任何变化，其实和 选择 作用差不多 3. 选择比复制的功能更强大一点，比如我可以添加各种选择策略，选上的才 复制 4. 一般来说先交叉再变异，直接复制的不会变异 5. 先选择还是先交叉，视具体情况而定 6. 选择、交叉、变异的方式都可自行设计，当然有一些常用的方法
7. 在编程时，一定要注意 可变变量，避免处理过程中，改变原个体，这样会导致模型不稳定等各种小问题 【实战中很容易出错】
遗传算子-选择 **** 选择的目的是让 适应度高 的个体有更大概率保存下来，注意是更大概率保存，不是一定保存； 【也就是说选 200次，适应度最高的可能被选中 50次，但也可能选中了适应度最低的】 最常用的是 轮盘赌 选择法； 更多请参考 我的博客；
遗传算子-交叉 ** 常用的有：单点交叉、多点交叉、均匀交叉、算术交叉等，都很简单，也可自行设计 单点交叉
一般单点交叉加上合适的交叉概率就够用了 多点交叉
均匀交叉（也称一致交叉，Uniform Crossover）：两个配对个体的每个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新个体。 算术交叉（Arithmetic Crossover）：由两个个体的线性组合而产生出两个新的个体。该操作对象一般是由浮点数编码表示的个体 更多请参考 参考资料
遗传算子-变异 ** 基本位变异（Simple Mutation）：对个体编码串中以变异概率、随机指定的某一位或某几位基因座上的值做变异运算。
均匀变异（Uniform Mutation）：分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。（特别适用于在算法的初级运行阶段） 边界变异（Boundary Mutation）：随机的取基因座上的两个对应边界基因值之一去替代原有基因值。特别适用于最优点位于或接近于可行解的边界时的一类问题。 非均匀变异：对原有的基因值做一随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后，相当于整个解向量在解空间中作了一次轻微的变动。 高斯近似变异：进行变异操作时用符号均值为Ｐ的平均值，方差为P**2的正态分布的一个随机数来替换原有的基因值。 实战总结 一）需要区分不可行解和非最优解，不可行解是不满足约束的解，非最优解是满足约束但y非最优的解，对待他们的方式是不同的 二）遗传算法的难点是 适应度函数 和 遗传算子的设计，无固定套路，但可遵循如下原则 三）要注意交叉和变异的概率，以及交叉、变异、选择的顺序，目的是避免变换太频繁，或者破坏最优解 四）要注意解空间的大小，解空间大很难收敛，或者模型不稳定，尽量把解空间大的问题分解成解空间小的问题，例如把 24小时规划 变成 24 个 1小时规划 时刻关注不可行解 1. 演变过程中要监控 解是否是可行解，过程产生的不可行解，可采用拒绝法直接淘汰，也可进行人工修复，对于可行但非最优解，可采取适当（小惩或者不惩）的淘汰策略 2. 交叉和变异 最好不要 产生不可行解，因为这种操作很可能被直接淘汰，这样就没有起到样本多样化的作用，白白浪费了一次迭代 约束处理1. 拒绝法：直接拒绝所有不可行解，这种方式简单粗暴，大部分时间效果不错，但丧失了一定的样本多样性，适用于要求极其严格的约束 2. 人工修复法：把不可行解变成可行解，常用于 组合优化 问题 3. 奖惩函数法：类似于机器学习中的正则化，如
该方法直接把有约束问题变成了无约束问题，但该方法允许部分 不可行解 的存在 应用场景 遗传算法的有趣应用很多，诸如寻路问题，8数码问题，囚犯困境，动作控制，找圆心问题（在一个不规则的多边形中，寻找一个包含在该多边形内的最大圆圈的圆心），TSP问题，生产调度问题，人工生命模拟等 示例代码 求一个表达式的最大值 import numpy as np import matplotlib.pyplot as plt from matplotlib import cm from mpl_toolkits.mplot3d import Axes3D DNA_SIZE = 24 POP_SIZE = 200 CROSSOVER_RATE = 0.8 MUTATION_RATE = 0.005 N_GENERATIONS = 50 X_BOUND = [-3, 3] Y_BOUND = [-3, 3] def F(x, y): # 目标函数 z = 3 * (1 - x) ** 2 * np.exp(-(x ** 2) - (y + 1) ** 2) - 10 * (x / 5 - x ** 3 - y ** 5) * np.exp( -x ** 2 - y ** 2) - 1 / 3 ** np.exp(-(x + 1) ** 2 - y ** 2) return z def plot_3d(ax): X = np.linspace(*X_BOUND, 100) Y = np.linspace(*Y_BOUND, 100) X, Y = np.meshgrid(X, Y) Z = F(X, Y) ax.plot_surface(X, Y, Z, rstride=1, cstride=1, cmap=cm.coolwarm) ax.set_zlim(-10, 10) ax.set_xlabel('x') ax.set_ylabel('y') ax.set_zlabel('z') plt.pause(3) plt.show() def get_fitness(pop): # 适应度 x, y = translateDNA(pop) # 解码 DNA pred = F(x, y) ### 求最大值 # 减去最小的适应度是为了防止适应度出现负数，通过这一步fitness的范围为[0, np.max(pred)-np.min(pred)],最后在加上一个很小的数防止出现为0的适应度 # return (pred - np.min(pred)) + 1e-3 # 适应度函数变换 ### 求最小值 return (np.max(pred) - pred) + 1e-3 def translateDNA(pop): # pop表示种群矩阵，一行表示一个二进制编码表示的DNA，矩阵的行数为种群数目 print(pop) x_pop = pop[:, 1::2] # 奇数列表示X y_pop = pop[:, ::2] # 偶数列表示y # pop:(POP_SIZE,DNA_SIZE)*(DNA_SIZE,1) --> (POP_SIZE,1) x = x_pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / float(2 ** DNA_SIZE - 1) * (X_BOUND[1] - X_BOUND[0]) + X_BOUND[0] y = y_pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / float(2 ** DNA_SIZE - 1) * (Y_BOUND[1] - Y_BOUND[0]) + Y_BOUND[0] return x, y def crossover_and_mutation(pop, CROSSOVER_RATE=0.8): # 复制、交叉、变异 new_pop = [] for father in pop: # 遍历种群中的每一个个体，将该个体作为父亲 child = father # 孩子先得到父亲的全部基因（这里我把一串二进制串的那些0，1称为基因） if np.random.rand() < CROSSOVER_RATE: # 产生子代时不是必然发生交叉，而是以一定的概率发生交叉 mother = pop[np.random.randint(POP_SIZE)] # 再种群中选择另一个个体，并将该个体作为母亲 cross_points = np.random.randint(low=0, high=DNA_SIZE * 2) # 随机产生交叉的点 child[cross_points:] = mother[cross_points:] # 孩子得到位于交叉点后的母亲的基因 mutation(child) # 每个后代有一定的机率发生变异 new_pop.append(child) return new_pop def mutation(child, MUTATION_RATE=0.003): if np.random.rand() < MUTATION_RATE: # 以MUTATION_RATE的概率进行变异 mutate_point = np.random.randint(0, DNA_SIZE) # 随机产生一个实数，代表要变异基因的位置 child[mutate_point] = child[mutate_point] ^ 1 # 将变异点的二进制为反转 def select(pop, fitness): # nature selection wrt pop's fitness # 轮盘赌选择：适应度高的被选择的概率更大 idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True, p=(fitness) / (fitness.sum())) # p实际是个数组，大小（size）应该与指定的a相同，用来规定选取a中每个元素的概率，默认为概率相同 return pop[idx] def print_info(pop): fitness = get_fitness(pop) max_fitness_index = np.argmax(fitness) print("max_fitness:", fitness[max_fitness_index]) x, y = translateDNA(pop) print("最优的基因型：", pop[max_fitness_index]) print("(x, y):", (x[max_fitness_index], y[max_fitness_index])) if __name__ == "__main__": fig = plt.figure() ax = Axes3D(fig) plt.ion() # 将画图模式改为交互模式，程序遇到plt.show不会暂停，而是继续执行 plot_3d(ax) pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE * 2)) # matrix (POP_SIZE, DNA_SIZE) for _ in range(N_GENERATIONS): # 迭代N代 x, y = translateDNA(pop) print(locals()) if 'sca' in locals(): sca.remove() sca = ax.scatter(x, y, F(x, y), c='black', marker='o') plt.show() plt.pause(0.1) pop = np.array(crossover_and_mutation(pop, CROSSOVER_RATE)) # 生成新种群 # F_values = F(translateDNA(pop)[0], translateDNA(pop)[1])#x, y --> Z matrix fitness = get_fitness(pop) # 计算适应度 pop = select(pop, fitness) # 选择生成新的种群 print_info(pop) # 计算最后种群的适应度，并取适应度最大的个体DNA，解码成 xy plt.ioff() plot_3d(ax)
参考资料： https://blog.csdn.net/daydream13580130043/article/details/87916668 遗传算法 与 作业车间调度问题(C++实现) https://blog.csdn.net/daydream13580130043/article/details/95927841 作业车间调度与遗传算法Python/Java实现及应用：BitMES，基于Electron的作业车间调度系统
https://blog.csdn.net/u010451580/article/details/51178225 遗传算法详解（GA） https://www.jianshu.com/p/ae5157c26af9 【算法】超详细的遗传算法(Genetic Algorithm)解析
https://blog.csdn.net/u012750702/article/details/54563515 遗传算法中几种交叉算子小结 https://www.omegaxyz.com/2018/04/21/crossover_mutation/ 遗传算法的交叉变异详解 |
【本文地址】