教程人工智能机器学习深度学习【免费下载链接】AI-For-Beginners12 Weeks, 24 Lessons, AI for All!项目地址https://gitcode.com/GitHub_Trending/ai/AI-For-Beginners点击查看免费下载本文是微软 AI 入门课程AI-For-Beginners第 21 课「遗传算法Genetic Algorithms」的中文技术指南基于 课程西班牙语文档 及其配套 notebook Genetic.ipynb、Diophantine.ipynb 编写。遗传算法属于课程第六部分「其他主题」6-Other中进化计算方向的代表性内容也是后续 22 深度强化学习 课程的先导知识。读完本文你将掌握遗传算法的四大核心要素基因编码、适应度函数、交叉、变异、完整演化主循环的算法结构并能直接运行两个经典实战案例——「宝藏公平分割」与「N 皇后问题」——以及完成「丢番图方程」课后作业。一、算法背景基于进化思想的 AI 求解范式遗传算法Genetic AlgorithmsGA采用进化式evolutionaryAI 方法它不是直接搜索解空间而是通过模拟种群population的进化过程来逼近给定问题的最优解。该算法由 John Henry Holland 于 1975 年提出课程文档 README.md 明确记载了这一年份与出处其灵感来自同时涉及心理学与计算机科学的交叉研究领域。遗传算法建立在一组相互配合的核心思想之上这也是本课文档首先强调的四个要点核心要素作用基因genes把问题的有效解编码成可操作的数据结构构成解空间 Γ交叉crossover组合两个解产生一个新的合法解选择selection借助某种**适应度函数fitness function**挑选更优的解变异mutation主动扰动优化过程帮助算法跳出局部最小值local minimum二、实现一个遗传算法需要定义的四件事课程文档明确指出要落地一个遗传算法必须解决以下四个形式化问题以数学记号表达配合 notebook 中的代码一一对应基因编码找到将问题解表示为基因g ∈ Γ 的方法。例如将解编码为数值序列或二进制向量bit vector。适应度函数在基因集合 Γ 上定义fit: Γ → ℝ。函数值越小对应的解越好——注意本课程采用越小越优的约定与许多教材中适应度越大越好的方向相反。交叉机制定义crossover: Γ² → Γ将两个基因组合成一个新的合法解。变异机制定义mutate: Γ → Γ对单个基因施加扰动。在实际工程中交叉与变异往往实现得非常简单正如课程文档所说在多数情况下交叉和变异就是把基因当作数值序列或位向量来操作。三、遗传算法的主循环结构不同问题可以有不同的具体实现但课程文档给出了一个通用的演化框架共 5 步选择初始种群 G ⊂ Γ。随机选择本步要执行的操作交叉或变异。交叉随机选出两个基因 g₁, g₂ ∈ G计算交叉结果 g crossover(g₁, g₂)若 fit(g) fit(g₁) 或 fit(g) fit(g₂)则用 g 替换种群中对应的那个基因。变异随机选一个基因 g ∈ G用 mutate(g) 替换它。从第 2 步循环直到 fit 值足够小或达到最大步数上限。这套循环正是 notebook 中两个示例所共用的骨架接下来逐一拆解。四、实战一宝藏公平分割Fair Treasure Split这是 Genetic.ipynb 中的第一个示例对应课程文档练习小节中的第 1 个用例。4.1 问题定义两个人发现了一批由不同尺寸因而价格不同的钻石组成的宝藏需要把宝藏分成两份使得两份价格之差为 0或尽可能小。形式化描述为给定数集 S将其划分为两个不相交子集 S₁ 与 S₂使得|Σ_{i∈S₁} i − Σ_{j∈S₂} j| → min且满足 S₁ ∪ S₂ S、S₁ ∩ S₂ ∅。4.2 基因编码二进制向量notebook 中随机生成了 N 200 个取值范围在 [1, 10000] 的钻石价格N 200 S np.array([random.randint(1,10000) for _ in range(N)])每个可行解被编码为一个二进制向量 B ∈ {0,1}^N第 i 位表示原集合 S 中的第 i 个数属于 S₁1还是 S₂0。生成随机个体的generate函数即随机掷 0/1def generate(S): return np.array([random.randint(0,1) for _ in S])4.3 适应度函数两份价格之差fit函数计算两个子集和的差的绝对值作为代价——差越小解越优最小值 0 即完美平分def fit(B,SS): c1 (B*S).sum() c2 ((1-B)*S).sum() return abs(c1-c2)4.4 变异与交叉的极简实现变异随机选一个位取反0 变 1、1 变 0def mutate(b): x b.copy() i random.randint(0,len(b)-1) x[i] 1-x[i] return x交叉复用generate随机生成一个 0/1 掩码 x逐位决定从 b₁ 还是 b₂ 取值相当于从两个父本各取一部分位def xover(b1,b2): x generate(b1) return b1*xb2*(1-x)4.5 演化主循环 evolve先构造规模为 pop_size 30 的初始种群然后进入演化循环pop_size 30 P [generate(S) for _ in range(pop_size)] def evolve(P,SS,n2000): res [] for _ in range(n): f min([fit(b) for b in P]) res.append(f) if f0: break if random.randint(1,10)3: # 30% 概率执行变异 i random.randint(0,len(P)-1) b mutate(P[i]) i np.argmax([fit(z) for z in P]) P[i] b else: # 70% 概率执行交叉 i random.randint(0,len(P)-1) j random.randint(0,len(P)-1) b xover(P[i],P[j]) if fit(b)fit(P[i]): P[i]b elif fit(b)fit(P[j]): P[j]b else: pass i np.argmin([fit(b) for b in P]) return (P[i],res)值得注意的实现细节这些细节并未在课程文档正文中展开属于源码级佐证操作概率分配random.randint(1,10)3使每次迭代约有30% 概率做变异、70% 概率做交叉变异后的替换策略变异产生的新个体直接替换种群中**适应度最差fit 值最大**的个体对应np.argmax交叉后的替换策略只有当新个体 fit 值优于任一父本时才替换否则丢弃pass严格遵循了课程文档第 3 步若 fit(g) 更优则替换的规则提前终止一旦出现 fit 0完美平分立即跳出循环返回值返回最优基因 s 及其 fit 值并记录每轮种群最小 fit 的演化历史hist可直接用 matplotlib 绘制收敛曲线notebook 中通过plt.plot(hist); plt.show()验证收敛过程。运行后即可看到 fit 值从初始的数万量级大幅下降到极小值验证了遗传算法对组合优化问题的求解能力。五、实战二N 皇后问题N Queens Problem这是 notebook 的第二个示例对应课程文档练习小节中的第 2 个用例。其要点是展示如何用遗传算法加速穷举搜索——这正是课程文档典型任务中列出的第 4 类任务。5.1 穷举搜索基线先把棋盘状态表示为列表 L第 i 个元素是第 i 行皇后所在的列号每行恰好一个皇后因此天然满足行不冲突。checkbeats检查新皇后是否与已有皇后同列或同对角线def checkbeats(i_new,j_new,l): for i,j in enumerate(l,start1): if jj_new: return False else: if abs(j-j_new) i_new-i: return False return Truenqueens采用经典回溯逐行放置、冲突则回溯找到第一组解即返回def nqueens(l,N8,dispTrue): if len(l)N: if disp: print(l) return True else: for j in range(1,N1): if checkbeats(len(l)1,j,l): l.append(j) if nqueens(l,N,disp): return True else: l.pop() return Falsenotebook 中实测 8 皇后很快出解但对20 皇后问题穷举回溯耗时约10.6 s ± 2.17 snotebook 中的%timeit nqueens([],20,False)实测输出这正是引入遗传算法的动机。5.2 基因编码与适应度函数遗传算法版仍用长度为 N 的列表表示解基因是 1..N 的一个随机排列generate_one用np.random.shuffle打乱。适应度函数定义为互相攻击的皇后对数def fit(L): x0 for i1,j1 in enumerate(L,1): for i2,j2 in enumerate(L,1): if i2i1: if j2j1 or (abs(j2-j1)i2-i1): x1 return x当 fit 0 时即得到无冲突的合法布局。为提高性能种群中的每个个体以(基因, fit 值)元组形式缓存适应度避免重复计算这一耗时步骤。5.3 随机单点断点交叉与随机位变异交叉在随机断点处把两个父本切开后拼接def mutate(G): xrandom.randint(0,len(G)-1) G[x]random.randint(1,len(G)) return G def xover(G1,G2): xrandom.randint(0,len(G1)) return np.concatenate((G1[:x],G2[x:]))5.4 适应度比例选择Fitness-Proportional Selection这里引入了一个课程文档未详细展开、但工程上极其重要的机制——按适应度比例随机选择父本。choose_rand把最大攻击对数 mf N(N-1)/2减去个体实际 fit 值作为权重 z再归一化得到概率 w用np.random.choice按权重采样两个父本。fit 值越小越优的个体被选中的概率越大def choose_rand(P): Nlen(P[0][0]) mf N*(N-1)//2 # 理论最大攻击对数即最差适应度 z [mf-x[1] for x in P] tf sum(z) # 总权重 w [x/tf for x in z] p np.random.choice(len(P),2,False,pw) return p[0],p[1]5.5 新一代生成与整体演化与宝藏分割每步随机选一个操作不同N 皇后示例采用**逐代整体更替generational**策略展示了同一种算法可以有不同的编排方式。nxgeneration完成一次代际更替mutation_prob 0.1 def discard_unfit(P): P.sort(keylambda x:x[1]) return P[:len(P)//3] # 淘汰最差的 2/3 def nxgeneration(P): gen_sizelen(P) P discard_unfit(P) P.extend(generate(len(P[0][0]),3)) # 补充 3 个随机个体保持多样性 new_gen [] for _ in range(gen_size): p1,p2 choose_rand(P) n xover(P[p1][0],P[p2][0]) if random.random()mutation_prob: nmutate(n) nf fit(n) new_gen.append((n,nf)) return new_gen外层genetic(N, pop_size100)不断调用nxgeneration直到种群中出现 fit 0 的完美解。genetic(8)即可快速求出 8 皇后的一组解。notebook 中还记录了一个重要的工程经验虽然多数情况下遗传算法很快收敛但偶尔会陷入局部最小值导致长时间停滞——实测%timeit genetic(10)出现最慢一次比最快一次慢 18.71 倍的现象。因此文档建议设定最大代数上限若超限未解出直接重启从头再来。这是把遗传算法用于生产环境时的关键兜底策略。六、典型应用场景课程文档列出的、通常由遗传算法解决的任务包括调度优化Schedule optimization如排课、排班、任务排程最优装箱Optimal packing如何把物品尽可能紧凑地装入容器最优切割Optimal cutting材料切割方案的损耗最小化加速穷举搜索Speeding up exhaustive searchN 皇后、背包等组合搜索问题的加速。文档同时指出遗传算法广泛应用于物流与搜索类问题其研究灵感来自心理学与计算机科学的交叉领域。七、课后作业丢番图方程Diophantine Equation课程文档的作业对应 Diophantine.ipynb该作业受 2012 年的一篇技术博客启发要求用遗传算法求解丢番图方程——具有整数系数与整数根的方程。示例方程为a 2b 3c 4d 30需要找出满足该方程的一组整数根。文档给出两条关键提示恰好呼应了本文第 2 节的形式化定义解空间约束可把根限定在区间[0; 30]内缩小搜索范围基因编码把根值的列表 [a, b, c, d] 直接当作基因——这与 N 皇后示例中列表即基因的编码方式一脉相承无需额外设计复杂的位向量编码。完成本作业需要自行设计适应度函数例如 |a 2b 3c 4d − 30| 或更精妙的组合、交叉与变异算子并复用课程文档第 3 节给出的主循环框架以 Diophantine.ipynb 作为编码起点。八、挑战与延伸学习Challenge挑战课程文档引用维基百科的一句话——遗传算法易于实现但其行为难以理解。文档建议自行调研一个遗传算法实现例如求解数独并用草图或流程图解释其工作原理。这既锻炼代码阅读能力也训练对演化过程的抽象表达能力。延伸学习本课位于课程6-Other目录下一节是 22 深度强化学习Deep Reinforcement Learning。遗传算法训练神经网络的思路与强化学习通过试错改进策略的范式有深刻关联课程推荐观看计算机用遗传算法训练的神经网络学会玩 Super Mario的相关视频作为过渡。仓库根目录的 requirements.txt 已包含 numpy、matplotlib、pandas 等本课 notebook 所需的 Python 依赖可直接搭建环境运行示例。九、小结通过本课你应当掌握遗传算法的完整实现链条基因编码二进制向量 / 整数排列 / 根值列表→ 适应度函数越小越优→ 交叉算子掩码逐位混血 / 单点断点拼接→ 变异算子位取反 / 随机重设→ 演化主循环随机选操作、按 fit 值替换、适应度比例选择、淘汰最差个体、限定代数重启。配套的 Genetic.ipynb 完整呈现了两个可运行案例Diophantine.ipynb 提供了动手练习的起点非常适合作为理解进化计算与组合优化的入门实操。赞分享教程人工智能机器学习深度学习【免费下载链接】AI-For-Beginners12 Weeks, 24 Lessons, AI for All!项目地址https://gitcode.com/GitHub_Trending/ai/AI-For-Beginners点击查看免费下载相关推荐AI for Beginners 遗传算法实战指南从基因编码到宝藏分配与 N 皇后问题AI for Beginners 遗传算法实战指南从基因编码到宝藏分配与 N 皇后问题 导读 本文是 AI for Beginners 课程中《遗传算法Ge教程人工智能机器学习深度学习AI-For-Beginners 遗传算法Genetic Algorithms实战指南从基因编码到宝藏均分与八皇后求解AI For Beginners 遗传算法Genetic Algorithms实战指南从基因编码到宝藏均分与八皇后求解 遗传算法Genetic Algo教程人工智能机器学习深度学习AI-For-Beginners 课程第 21 课用遗传算法求解优化问题——从公平分宝到 8 皇后AI For Beginners 课程第 21 课用遗传算法求解优化问题——从公平分宝到 8 皇后 遗传算法Genetic Algorithms, GA是教程人工智能机器学习深度学习创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考