教程人工智能机器学习深度学习【免费下载链接】AI-For-Beginners12 Weeks, 24 Lessons, AI for All!项目地址https://gitcode.com/GitHub_Trending/ai/AI-For-Beginners点击查看免费下载导读本文是 AI for Beginners 课程中《遗传算法Genetische Algorithmen》一课的完整技术指南对应的课程文档位于 translations/de/lessons/6-Other/21-GeneticAlgorithms/README.md配套源码为 Genetic.ipynb 与 Diophantine.ipynb。本指南将带你理解遗传算法这一进化式 AI 方法的核心思想基因、适应度、交叉、变异掌握实现一个完整遗传算法所需的四大组件与标准流程并通过「宝藏公平分配」「N 皇后问题」「丢番图方程」三个仓库内真实可运行的实验与作业获得从零手写进化算法的实战能力。一、进化思想什么是遗传算法遗传算法Genetic AlgorithmsGA是一种基于进化式方法evolutionary approach的人工智能技术它借鉴自然界中种群population进化的机制来寻找给定问题的最优解。该算法由 John Henry Holland 于 1975 年提出是启发式搜索与优化领域的经典方法。遗传算法的出发点建立在以下四条核心思想上基因Gene表示问题的合法解可以被表示为一组基因交叉Crossover允许将两个解组合起来得到一个新的合法解选择Selection借助某种适应度函数fitness function从种群中挑选出更优的解变异Mutation引入随机扰动来「打破」当前优化方向使算法能够跳出局部最小值local minimum。这四条思想在仓库的 Genetic.ipynb 中有着一一对应的代码实现generate、fit、xover、mutate四个函数下文将逐一展开。二、实现遗传算法的四大必备组件若要在代码中实现一个遗传算法Genetic.ipynb 的理论部分指出需要具备以下四个要素基因编码方法找到一种将问题解编码为基因 $g \in \Gamma$ 的方式。基因的形式取决于问题——可以是数字序列也可以是位向量bit vector。适应度函数在基因集合 $\Gamma$ 上定义适应度函数 $\mathrm{fit}: \Gamma \to \mathbb{R}$函数值越小表示解越优注意本课程统一约定「越小越好」这与部分教材中「适应度越大越好」的约定相反阅读其他资料时需留意。交叉机制定义一个映射 $\mathrm{crossover}: \Gamma^2 \to \Gamma$将两个基因组合产生一个新的合法解。变异机制定义一个映射 $\mathrm{mutate}: \Gamma \to \Gamma$对单个基因施加随机扰动。在许多实际问题中交叉与变异都是相当简单的算法——它们本质上只是把基因当作数字序列或位向量进行截取、拼接与翻转操作。以本课的 Genetic.ipynb 为例宝藏分配问题把基因编码为 0/1 位向量变异就是随机翻转一位交叉就是按随机掩码从两个父代中取位而 N 皇后问题把基因编码为排列列表变异是随机改写一个位置的值交叉则是单点断点拼接。三、标准算法流程五个步骤遗传算法的具体实现可以因问题而异但总体结构是一致的。课程文档给出了如下标准流程初始化选择初始种群 $G \subseteq \Gamma$例如随机生成若干基因。选择操作在每一步随机选择本次要执行的操作——交叉或变异。交叉Crossover随机从种群 $G$ 中选择两个基因 $g_1, g_2$计算交叉结果 $g \mathrm{crossover}(g_1, g_2)$若 $\mathrm{fit}(g) \mathrm{fit}(g_1)$ 或 $\mathrm{fit}(g) \mathrm{fit}(g_2)$则用 $g$ 替换种群中对应的基因。变异Mutation随机选择一个基因 $g \in G$用 $\mathrm{mutate}(g)$ 将其替换。终止重复步骤 2直到 $\mathrm{fit}$ 达到足够小或达到设定的最大步数上限。该流程在 Genetic.ipynb 的evolve函数中有直接体现每一步先记录当前种群的最优适应度若已找到最优解fit0则提前终止否则以 30% 概率执行变异、70% 概率执行交叉详见下文实战。四、典型任务遗传算法能解决什么问题课程文档列举了遗传算法最常见的四类应用场景调度优化Schedule optimization如排课、排班、生产计划等组合调度问题最优打包Optimal packing如装箱问题、背包问题的变体最优切割Optimal cutting如板材/布料的最优下料问题加速穷举搜索Speeding up exhaustive search在搜索空间巨大、无法全量枚举时用进化搜索快速逼近可行解。下文两个实战案例恰好覆盖了最后一类加速穷举搜索——N 皇后问题正是一个典型的搜索问题遗传算法能够在有限代数内逼近甚至找到最优解。五、实战一宝藏公平分配Fair Treasure Split5.1 问题定义两位探险者发现了一批大小因而价格各异的钻石需要将宝藏分成两份使得两堆总价的差值最小理想为 0。形式化地给定数字集合 $S$要将其划分为两个不相交的子集 $S_1$ 与 $S_2$$S_1 \cup S_2 S$$S_1 \cap S_2 \emptyset$使得$$\left|\sum_{i \in S_1}i - \sum_{j \in S_2}j\right| \to \min$$5.2 基因编码位向量Genetic.ipynb 首先生成 200 个 1 到 10000 之间的随机整数作为钻石集合 $S$然后用一个二进制向量 $B \in {0,1}^N$ 编码每个可能的解向量第 $i$ 位表示原始集合 $S$ 中第 $i$ 个数属于 $S_1$ 还是 $S_2$。随机生成初始基因的实现如下N 200 S np.array([random.randint(1,10000) for _ in range(N)]) def generate(S): return np.array([random.randint(0,1) for _ in S])5.3 适应度函数两份宝藏的价值差适应度函数fit计算两个子集之和的差绝对值这正是需要最小化的目标def fit(B,SS): c1 (B*S).sum() # S1 的总价值 c2 ((1-B)*S).sum() # S2 的总价值 return abs(c1-c2)初始随机基因的fit值通常在十万量级需要通过进化不断压缩。5.4 变异与交叉针对位向量基因变异与交叉的实现极为简洁变异随机选择一位并取反0→1 或 1→0交叉借助generate随机生成一个掩码决定每一位取自哪个父代。def mutate(b): x b.copy() i random.randint(0,len(b)-1) x[i] 1-x[i] return x def xover(b1,b2): x generate(b1) return b1*xb2*(1-x)5.5 进化主循环种群大小设为 30pop_size 30进化主函数evolve每步执行 2000 次迭代n2000以30%的概率执行变异随机选一个基因变异后用它替换种群中fit值最差的个体np.argmax([fit(z) for z in P])定位最差个体以70%的概率执行交叉随机选两个基因交叉若后代比其中任一父代更优fit(b)fit(P[i])或fit(b)fit(P[j])则替换对应父代否则丢弃后代保持种群规模稳定。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)运行evolve(P)后Notebook 输出显示适应度已被大幅压缩且hist记录了每一代种群中最优fit的下降轨迹可直接用plt.plot(hist)绘制进化收敛曲线。六、实战二N 皇后问题8 Queens Problem6.1 问题与全搜索基线在 $N \times N$ 的棋盘上放置 $N$ 个皇后使它们互不攻击。在引入遗传算法之前Genetic.ipynb 先用穷举回溯给出基线实现用列表 $L$ 表示棋盘状态第 $i$ 个元素是第 $i$ 行皇后的列坐标每行恰有一个皇后。回溯函数nqueens配合攻击检查函数checkbeats找出第一个可行解N 8 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 True 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 中用%timeit nqueens([],20,False)实测求解20 皇后问题的耗时约为10.6 s ± 2.17 s7 次运行均值——这为遗传算法的加速效果提供了对比基线。6.2 GA 基因表示与适应度遗传算法解法灵感来自 kushalvyas 的博客文章同样使用长度为 $N$ 的列表表示解但适应度函数改为统计相互攻击的皇后对数攻击包含同行同列值与对角线两种情况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由于适应度计算开销较大种群中每个个体都存为(基因, 适应度值)二元组避免反复重算。初始种群通过generate_one生成对np.arange(1,N1)随机洗牌得到排列基因并当场计算适应度。6.3 变异、交叉与适应度加权选择变异随机选一个位置改为 1 到 $N$ 之间的随机列号交叉单点交叉——随机选断点将两个父代的前后两段拼接。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:]))与宝藏分配「随机选择父代」不同N 皇后版本引入适应度加权选择choose_rand先计算理论最大攻击对数 $N(N-1)/2$用mf - fit把适应度反转适应度越小、权重越大归一化后作为np.random.choice的抽样权重从而让更优的基因有更高概率被选中繁殖。6.4 换代式进化循环主循环genetic(N, pop_size100)采用「换代generational」策略而非逐个体替换discard_unfit(P)按适应度排序后丢弃最差的 1/3 个体补充 3 个随机生成的新个体维持多样性nxgeneration(P)生成与种群等规模的新一代每个新个体由加权随机选出的两个父代交叉产生并以mutation_prob 0.1的概率施加变异随后计算适应度存入新种群。mutation_prob 0.1 def nxgeneration(P): gen_sizelen(P) P discard_unfit(P) P.extend(generate(len(P[0][0]),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 def genetic(N,pop_size100): P generate(N,pop_size) mf min([x[1] for x in P]) n0 while mf0: n1 mf min([x[1] for x in P]) P nxgeneration(P) mi np.argmin([x[1] for x in P]) return P[mi]genetic(8)在 Notebook 中输出(array([4, 7, 5, 3, 1, 6, 8, 2]), 0)即找到适应度为 0皇后互不攻击的完美解。6.5 局部最小值与调优注意点Notebook 特别指出一个重要现象大多数情况下遗传算法能很快找到解但少数情况下优化会陷入局部最小值长时间卡住。实测%timeit genetic(10)的结果为26.4 s ± 28.7 s且最慢的一次运行耗时是最快的一次的 18.71 倍——方差极大。因此在测量平均耗时、评估算法表现时必须考虑这种长尾分布工程上的应对手段包括限制最大代数若超时未找到解则重新开始这与课程文档中「直到 fit 足够小或达到步数上限」的终止条件设计是一致的。七、课后作业丢番图方程Diophantine Equation作业以 Diophantine.ipynb 为起点要求用遗传算法求解丢番图方程——即带整数系数、整数解的方程。以方程$$a 2b 3c 4d 30$$为例需要找出满足该方程的整数根 $a, b, c, d \in \mathbb{N}$。课程给出的两条提示根的取值范围可限定在区间 $[0; 30]$ 内基因可以用根值的列表来表示即基因形如[a, b, c, d]的四元整数列表。该作业的完整形式化定义与上述提示均收录于 Diophantine.ipynb可结合前两节实战中的generate / fit / xover / mutate模式自行实现例如用fit定义方程两边差值的绝对值用单点交叉拼接列表用随机改写某个根值实现变异。八、挑战与延伸学习课程文档还布置了一个开放挑战遗传算法「实现简单但行为难以理解」。建议研究一个具体实现例如用遗传算法求解Sudoku 数独并用草图或流程图解释它如何工作——这正好可以检验你是否真正理解了「编码 → 适应度 → 选择 → 交叉 → 变异 → 收敛」的完整回路。在深入强化学习之前可以观看「用遗传算法训练神经网络学会玩 Super Mario」的经典视频直观感受进化搜索与神经网络的结合后续的深度强化学习章节将进一步讲解计算机如何学会玩这类游戏。九、总结遗传算法被广泛用于解决物流、搜索等各类优化问题其思想源于心理学与计算机科学交叉领域的研究。通过本课你应该掌握遗传算法的四大组件——基因编码、适应度函数、交叉、变异以及「适应度越小越优」的约定标准进化流程——初始化种群、随机选择交叉/变异、择优替换、迭代直至收敛两种典型基因操作——位向量的随机翻转/掩码交叉以及排列列表的单点交叉/随机改写两个可运行的实战案例Genetic.ipynb 中的宝藏公平分配与 N 皇后问题包括适应度加权选择、换代式种群管理与局部最小值等进阶技巧一个完整作业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 http教程人工智能机器学习深度学习AI-For-Beginners 课程第 21 课用遗传算法求解优化问题——从公平分宝到 8 皇后AI For Beginners 课程第 21 课用遗传算法求解优化问题——从公平分宝到 8 皇后 遗传算法Genetic Algorithms, GA是教程人工智能机器学习深度学习CHIPSEC配置系统完全解析从XML配置到平台检测的完整流程CHIPSEC配置系统完全解析从XML配置到平台检测的完整流程 CHIPSEC作为Platform Security Assessment Framework应用安全渗透测试上一篇Java字节码操作终极指南ASM与Javassist实战解析下一篇从0到1掌握Efficient Teacher半监督目标检测新手入门教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考