现代AI基础微课视频版课件 第6章 经典人工智能算法简介

BeyondTechnology现代AI基础第6章经典人工智能算法简介遗传算法（GeneticAlgorithm，GA）是一种基于生物进化原理的全局优化算法。由美国密歇根大学JohnHolland教授于20世纪70年代系统提出，著作《AdaptationinNaturalandArtificialSystems》（1975）奠定数学基础。核心思想●模拟"物竞天择，适者生存"的自然选择过程●从初始种群出发，通过选择、交叉、变异产生新一代种群●不断进化，直到满足目标条件为止6.1遗传算法—概述早期研究（20世纪50-60年代）●少数计算机科学家开展"人工进化系统"研究●Rechenberg、Schwefel等提出进化策略（ES），应用随机变异改善参数●Fogel等提出进化规划（EP），用于有限状态机设计Holland的奠基性贡献（1960年代中期-1975）●提出位串编码技术，适用于交叉和变异两种操作●强调交叉（杂交）为主要遗传操作●1975年出版开创性著作，正式确立遗传算法理论框架近年发展●融合机器学习、大数据技术，应用范围持续扩展●与深度学习结合，用于超参数优化、特征选择等6.1.1遗传算法的产生与发展达尔文自然选择学说三要素●遗传（heredity）：亲代把遗传信息传给子代，物种得以稳定存在●变异（variation）：亲子代之间的差异，是生命多样性的根源●适者生存：具有适应性的个体被保留，不适者被淘汰孟德尔的贡献●提出遗传分离律和自由组合律，奠定现代遗传学基础进化论对算法设计的启示●"代代相传+优胜劣汰"→迭代优化●"基因重组"→算法交叉操作●"随机变异"→算法变异操作6.1.2遗传学基本知识—达尔文进化论关键生物学术语（与算法对应）●染色体（chromosome）：遗传物质载体→解的编码串●DNA/基因（gene）：遗传基本单位→编码中的单个位●种群（population）：个体集合→候选解集合●适应度（fitness）：对环境的适应程度→目标函数值●选择（selection）：适应度高的个体更多繁殖→优秀解被保留●交叉（crossover）：染色体交换重组→解的杂交操作●变异（mutation）：DNA复制偶发错误→随机扰动●进化（evolution）：种群逐代适应环境→反复迭代寻优6.1.2遗传学相关术语基本思路用"生物进化"的方式来求解复杂优化问题：①编码：将问题的解表示为"染色体"（通常为二进制串）②初始化：随机生成一定规模的初始种群

③评估：用适应度函数计算每个个体的优劣④选择：适应度高的个体有更大概率被保留⑤交叉：选中的个体两两交换基因片段⑥变异：以小概率随机改变某些基因位⑦重复④~⑥，直到满足终止条件6.1.3遗传算法概要—算法思想传统优化方法的局限●梯度下降法：需要目标函数可微，容易陷入局部最优●穷举法：搜索空间大时计算爆炸，无法实用●启发式规则：依赖领域知识，通用性差遗传算法的优势●不需要梯度信息，可处理不连续、不可微的目标函数●并行搜索多个候选解，全局搜索能力强●适用性广：连续/离散、单目标/多目标均可处理遗传算法的局限●计算开销大（适应度评估次数多）●参数选择（种群规模、交叉率、变异率）需要经验●对于高精度连续优化问题，收敛速度不如PSO6.1.3遗传算法vs传统优化方法算法主循环：●【开始】→初始化种群→计算适应度●→是否满足终止条件？▷是：输出最优解→【结束】▷否：继续下一步●→选择操作（轮盘赌/锦标赛选择）●→交叉操作（单点/两点/均匀交叉）●→变异操作（位翻转变异）●→生成新种群→重新计算适应度→循环6.1.3遗传算法基本流程选择（Selection）●轮盘赌选择：适应度越高的个体被选中概率越大●锦标赛选择：随机取k个个体，选最优者交叉（Crossover）●单点交叉：在随机位置切断，交换后半段●两点交叉：切断两处，交换中间段变异（Mutation）●以小概率翻转某位（0→1或1→0）●变异概率通常设为0.001~0.01，避免破坏优良基因6.1.3三大遗传操作详解以"背包问题"为例：有5件物品，选择哪些装入背包使总价值最大。二进制编码方案●染色体：[1,0,1,1,0]▷1=选取该物品，0=不选取▷该串表示：选取物品1、3、4，不选2、5适应度函数设计●若总重量不超过背包容量：适应度=所选物品总价值●若超出容量：适应度=0或施加惩罚解码过程●把二进制串还原为具体方案（哪些物品被选）●再代入目标函数计算适应度6.1.3编码与解码示例种群规模（PopulationSize）●典型范围：50~200个体▷太小→早熟收敛，缺乏多样性▷太大→计算开销大，收敛慢交叉概率（Pc）●典型范围：0.6~0.9●较大Pc有助于探索新区域，过大则破坏优秀个体变异概率（Pm）●典型范围：0.001~0.05●适当变异可维持种群多样性，过大则退化为随机搜索6.1.3遗传算法关键参数设置终止条件●达到最大迭代代数（常用100~1000代）●连续若干代最优解不再改善●目标函数值达到预设阈值6.1.3遗传算法关键参数设置工程优化●生产调度优化：汽车制造商用GA优化焊装车间，效率提升12~15%●工艺参数优化：钛合金3D打印参数优化，疲劳寿命提升22~25%路径规划●VLSI布局布线：改进GA使布线长度减少9.7%通信与信号处理●5G天线阵列优化：覆盖盲区减少约35%生物信息学●基因序列分析、蛋白质结构预测等6.1.4遗传算法的典型应用蚁群优化算法（AntColonyOptimization，ACO）由意大利学者MarcoDorigo于1992年提出。灵感来源于蚂蚁觅食时发现最短路径的集体行为。自然现象的启发●蚂蚁在行进时分泌信息素（pheromone），形成化学信号●较短路径上信息素积累更快，吸引更多蚂蚁跟随●挥发机制防止次优路径永久占据优势●通过正反馈最终整个蚁群都走最短路径ACO的重要里程碑●1997年：提出蚁群系统（AntColonySystem），效果大幅提升●2004年：Dorigo因此获得ACMAAAI经典人工智能奖6.2蚁群算法—概述信息素机制（核心）●蚂蚁路径越短→往返越快→信息素积累越多●信息素越多→吸引更多蚂蚁走此路径（正反馈）●信息素随时间挥发（负反馈）→避免陷入局部最优状态转移概率●蚂蚁选择下一节点的概率=信息素浓度×启发信息（距离倒数）●信息素浓度越高、距离越短，被选中概率越大信息素更新规则●每次迭代后：τ(t+1)=(1-ρ)·τ(t)+Δτ▷ρ：挥发系数（0<ρ<1）▷Δτ：本轮蚂蚁在此路径上新增的信息素6.2.1蚁群算法的核心机制6.2.2

信息素机制工作原理示意图算法步骤●①初始化：设定蚂蚁数量、信息素初值、启发函数参数●②构建解：每只蚂蚁按转移概率逐步构建一条路径（完整解）●③评估解：计算各路径长度（适应值）●④更新信息素：挥发旧信息素，较优路径补充新信息素●⑤终止判断：达到最大迭代次数或解不再改善则停止●⑥输出最优路径关键参数●α：信息素重要程度权重●β：启发信息（距离倒数）权重●ρ：信息素挥发系数6.2.2蚁群算法基本流程问题描述：找到访问所有城市且仅访问一次、路程最短的路径。ACO求解过程●将每个城市视为节点，蚂蚁从随机城市出发●根据信息素浓度和距离倒数，选择下一城市●每只蚂蚁完成一轮游历后，根据路径长度更新信息素●短路径积累信息素→吸引更多蚂蚁→路径逐步优化算法特点与优势●正反馈机制使得优质路径能被快速发现●分布式并行搜索，鲁棒性强●适合动态变化的路径规划问题6.2.3应用实例：旅行商问题（TSP）以6城市TSP为例，演示蚁群算法一次迭代过程：初始状态●6个城市（节点），城市间连线为候选路径●初始信息素均匀分布：τij=τ₀蚂蚁构建路径（以蚂蚁1为例）●从城市A出发，根据转移概率选择下一城市●完成一次游历，记录总路程信息素更新●路程短的路径：Δτ大→信息素增加多●路程长的路径：信息素因挥发而减少多轮迭代后●最短路径的信息素浓度最高，形成"信息素主干"●所有蚂蚁趋向于走同一条最优路径6.2.3ACO求解TSP—图示说明精英蚂蚁策略●最优解的蚂蚁额外增加信息素，加速向最优路径收敛最大-最小蚁群系统（MAX-MINAS）●限制信息素浓度范围[τmin,τmax]，防止某路径垄断多信息素类型●不同蚂蚁使用不同类型信息素，解决多目标优化候选列表策略●蚂蚁只考虑距离最近的k个候选城市，降低计算复杂度并行蚁群算法●多个蚂蚁种群同时搜索，定期交换最优路径信息自适应信息素挥发●根据解的质量动态调整ρ，避免信息素过早收敛6.2.4蚁群算法的改进策略交通物流●智慧物流：改进并行ACO在标准测试集上配送时效提升15~18%通信网络●互联网路由优化：蚂蚁算法自然适配网络拓扑结构生物信息学●蛋白质折叠预测：多信息素ACO在CASP14测试中精度达0.79ÅRMSD●基因序列比对：比对速度提升4.8倍能源与工业●光伏阵列重构：在阴影条件下发电效率提升8.7%6.2.4蚁群算法的典型应用粒子群优化算法（ParticleSwarmOptimization，PSO）由Kennedy和Eberhart于1995年提出。灵感来源：鸟群觅食时通过观察同伴位置协同寻找食物。自然现象的启发●每只鸟记住自己找到的最佳位置（个体经验）●整个鸟群共享发现的最好位置（群体智慧）●每只鸟通过这两个信息不断调整飞行方向●最终整个鸟群收敛到食物最丰富的区域算法特点●实现简单，参数少，收敛速度快●特别适合连续空间的优化问题6.3粒子群优化算法—概述理论基础●Reynolds（1987）：建立简化社会行为模型，识别邻近个体并匹配速度●Heppner&Grenander（1990s）：研究鸟群三大典型特征▷大规模同步运动▷突然的集体转向行为▷有序的分散与重组Kennedy&Eberhart的创新（1995）●将社会心理学概念（社会影响、认知）融入优化工具●每个粒子维护两个关键信息：▷pBest：个体历史最优位置（个人最佳）▷gBest：全局最优位置（群体最佳）6.3.1算法思想渊源6.3.2粒子群算法基本原理粒子群优化算法的模拟示意图6.3.2粒子群算法基本原理表6.11

鸟群觅食与PSO算法的概念对应表鸟群觅食过程粒子群优化算法鸟群搜索空间内的一组可行解(表现为种群规模N)觅食空间最优化问题的搜索空间(表现为维数D)第i(i=1,2,…,N)只鸟的飞行速度可行解的速度向量vi=(vi1,vi2,…,viD)第i只鸟的所在位置可行解的位置向量xi=(xi1,xi2,…,xiD)第i只鸟的个体认知与社会影响第i个粒子根据自身历史最优位置以及群体所处的全局最优位置不断地调整自己当前的速度和位置鸟群觅到食物算法结束并且输出(近似)全局最优解粒子的两个核心属性●位置向量x=(x₁,x₂,…,xD)：表示候选解●速度向量v=(v₁,v₂,…,vD)：控制搜索方向和步长速度更新公式（核心）v(t+1)=w·v(t)+c₁·r₁·(pBest-x)+c₂·r₂·(gBest-x)▷w：惯性权重—保持当前飞行惯性▷c₁：自我认知因子—向自身历史最优学习▷c₂：社会影响因子—向群体最优学习▷r₁,r₂：[0,1]上的随机数位置更新公式x(t+1)=x(t)+v(t+1)6.3.2粒子群算法基本原理6.3.3粒子群算法基本流程算法步骤①初始化：随机设定各粒子位置和速度，令pBest=初始位置②计算适应值：用目标函数评估各粒子当前位置③更新pBest：若当前适应值优于历史最优，更新pBest④更新gBest：从所有pBest中找全局最优，更新gBest⑤更新速度：按速度更新公式计算新速度（限制在Vmax内）⑥更新位置：按位置更新公式计算新位置⑦终止判断：达到最大迭代次数或精度要求则停止，否则回到②关键参数w∈[0.4,0.9]，c=c≈2.0，粒子数30~1006.3.3粒子群算法基本流程惯性权重w的影响●w大（接近1→粒子保持原飞行方向→全局搜索能力强●w小（接近0）→粒子迅速转向最优方向→局部搜索能力强▷工程实践：通常从0.9线性递减到0.4认知因子c₁的影响●c₁大→粒子更相信自身经验→多样性好，收敛慢●c₁小→粒子容易忽略个人历史最优社会因子c₂的影响●c₂大→粒子快速向群体最优聚集→收敛快，易早熟●c₂小→群体学习效果弱，搜索效率低推荐参数设置w=0.7~0.9，c₁=c₂=2.0，粒子数30~50（低维），100+（高维）6.3.3PSO控制参数的影响分析求f(x₁,x₂,x₃)=x₁²+x₂²+x₃²的最小值，约束-10≤xᵢ≤10参数设置粒子数量：5个；最大迭代次数：3次c₁=c₂=1.5，w=0.7，r₁=r₂=0.5迭代过程第1次：初始化适应值，粒子1最优（f=14），确定gBest第2次：所有粒子均找到更优位置，全局最优更新（f=2.90）第3次迭代：粒子继续向原点收敛，全局最优（f≈1.45）结论●经3次迭代，所有粒子均向原点（最优点）稳定收敛●若继续迭代，解将进一步趋近(0,0,0)6.3.4应用实例：三维函数优化6.3.4PSO三维函数优化—初始化阶段表6.12

5粒子初始阶段表粒子编号初始位置

(x₁,x₂,x₃)初始速度

(v₁,v₂,v₃)1(2,3,-1)(0.5,-0.5,0.3)2(-4,1,2)(-0.2,0.3,-0.1)3(0,-2,5)(0.1,0.4,-0.6)4(3,0,-3)(-0.3,0,0.5)5(-1,-5,1)(0.2,-0.2,0.1)6.3.4PSO三维函数优化—第一次迭代后表6.13

5粒子更新后状态表粒子编号新位置新速度新函数值1(2.35,2.65,−0.79)(0.35,−0.35,0.21)13.172(0.36,2.71,−0.32)(4.36,1.71,−2.32)7.683(1.57,2.03,0.08)(1.57,4.03,−4.92)6.534(2.04,2.25,−1.15)(−0.96,2.25,1.85)10.085(1.39,0.86,−0.43)(2.39,5.86,−1.43)2.90惯性权重改进●线性递减权重：初期大探索→后期小开发●自适应惯性权重：根据收敛状态动态调节拓扑结构改进●全局版：所有粒子共享gBest，收敛快但易早熟●局部版：粒子只与邻居共享，多样性好但收敛慢混合策略●引入遗传算子（交叉/变异）增强种群多样性●量子PSO：引入量子隧穿效应，避免局部最优多目标扩展●MOPSO：基于拥挤距离保留精英解，解决多目标权衡问题6.3.5算法改进方向工业工程●智能制造调度：改进PSO使汽车焊接生产线效率提升12.3%●光伏阵列重构：混沌PSO在阴影条件下提高发电效率8.7%人工智能●深度学习超参数调优：PSO优化CNN，ImageNet准确率提升1.5%●机器人路径规划：实时优化，复杂地形通过速度提高60%金融领域●PSO-RBF混合模型用于高频量化交易策略6.3.6粒子群算法的典型应用遗传算法（GA）●生物原型：达尔文进化论+孟德尔遗传学●数学基础：离散数学、概率论、模式定理m）蚁群算法（ACO）●生物原型：蚂蚁觅食的信息素通信行为●数学基础：概率图模型+正反馈系统粒子群算法（PSO）●生物原型：鸟群/鱼群的群体协作觅食●数学基础：连续动力学系统理论共同特点●均源于自然界的生物智慧，通过群体协作涌现全局智能●均无需梯度信息，适合黑箱优化问题6.4.1三种算法理论基础对比6.4.1三种算法对比分析表6.16

三种智能算法数学范式差异表特征遗传算法蚁群算法粒子群算法解空间表达离散组合空间图路径空间连续欧氏空间核心数学工具组合数学/模式理论概率论/马尔可夫过程动力学系统/梯度近似收敛性证明基于马尔可夫链分析随机近似理论Lyapunov稳定性分析典型操作交叉/变异概率转移/信息素更新速度-位置更新收敛特性GA：阶梯式进化，多样性好，适合复杂多峰问题，速度较慢ACO：正反馈强化，初期快速逼近，易陷入局部最优PSO：快速趋近+精细调整两阶段，参数鲁棒性最好最佳适用场景GA：离散组合优化（车间调度、电路布局、多模态问题）ACO：图路径优化（物流配送、网络路由、动态环境）PSO：连续参数优化（机械设计、神经网络训练、高维问题）鲁棒性6.4.1收敛特性与适用场景对比6.4.1三种算法结构对比表6.17

三种智能算法的结构对比表算法个体表示信息交互方式典型种群规模GA二进制串全局交叉变异50-200ACO虚拟蚂蚁局部信息素更新20-50PSO多维粒子邻域拓扑连接30-100问题类型判断●问题是离散/组合优化（排列、选择）→首选GA●问题是图路径/路由规划→首选ACO●问题是连续参数优化、高维搜索→首选PSO实时性要求●对实时性要求高（毫秒级）→PSO（计算最轻量）●允许较长计算时间→GA（深度搜索，解质量高）环境特点●动态变化的环境→ACO（信息素自然适应）●存在大量噪声的环境→GA（种群多样性最强）混合策略建议●复杂问题可用GA初步搜索+PSO精细优化的两阶段策略6.4.1如何选择合适的优化算法①混合智能算法●GA-PSO：上层GA保持多样性，下层PSO精细搜索●ACO-SA：融合模拟退火温度调控，解决早熟问题②自适应参数调控●PSO惯性权重非线性衰减：根据收敛状态自动调节●GA交叉率基于种群熵值实时调整③并行化与分布式计算●GPU并行GA：基因序列比对实现100倍加速●云计算ACO：可处理百万级城市物流优化④多目标优化扩展●NSGA-III：高维多目标，可同时平衡6个冲突目标●MOPSO：无人机航迹能耗与时间同步优化6.4.2经典算法