农业人工智能：第6章 时间上的概率推理

第6章复杂环境中的搜索农业决策中最优化问题求解核心要点：·

在线搜索

·局部观测·最优化问题

·爬山算法16.1.1爬山搜索内容局部搜索算法（localsearch）是一种通过从起始状态搜索到其相邻状态来操作的算法，它不会记录路径或已访问状态集。最为常见的爬山搜索算法是最基本的局部搜索技术。在每一步中，当前节点被其最优邻居节点替换。合理的抽象任何抽象解都可以细化为现实世界中的具体解。有用的抽象执行抽象动作比在原始详细描述中搜索更容易。有用的抽象执行抽象动作比在原始详细描述中搜索更容易。目标：局部搜索算法也可用于求解最优化问题（optimizationproblem），其目标是根据目标函数（objectivefunction）找到最优状态。变体：随机爬山（stochastichillclimbing）搜索算法在上升过程中随机选择一个后继状态，选择的概率随着上升的陡度而变化。这种方法通常比最陡上升法收敛得更慢，但在某些状态地形图中能找到更好的解。6.1.2模拟退火内容模拟退火算法是一种允许某些下坡移动的随机爬山法。然而，它不是选择最佳移动，而是选择随机移动。如果该移动导致情况改善，它将始终被接受合理的抽象任何抽象解都可以细化为现实世界中的具体解。有用的抽象执行抽象动作比在原始详细描述中搜索更容易。有用的抽象执行抽象动作比在原始详细描述中搜索更容易。类比：将一个乒乓球放入一个崎岖表面的最深裂缝中。如果只是让球滚动，它会停留在局部极小值处；如果晃动表面，乒乓球会从局部极小值中弹出。模拟退火算法的思路就是开始时用力晃动（即高温），然后逐渐降低晃动的强度（即降低温度）。应用：从20世纪80年代开始，模拟退火算法已被广泛应用于求解超大规模集成电路布图问题。它在工厂调度和其他大规模优化任务中也得到了广泛应用。6.1.3进化算法内容进化算法（evolutionaryalgorithm）可以视为随机束搜索的一种变体：种群由个体（状态）组成，其中适应环境最好的个体（具有最高值）可以生成后代（后继状态）以繁衍下一代，这个过程称为重组（recombination）。合理的抽象任何抽象解都可以细化为现实世界中的具体解。有用的抽象执行抽象动作比在原始详细描述中搜索更容易。有用的抽象执行抽象动作比在原始详细描述中搜索更容易。选择过程：选择确定将成为下一代亲本的个体，一种可能是按照适应度评分的比例从所有个体中进行选择。另一种可能是随机选择n个个体（其中n=ρ），然后从中选择适应度最高的ρ个个体作为亲本。重组过程：一种常见的方法（假设ρ=2）是随机选择一个交叉点来分割每个父串，并将这些部分重新组合以形成两个子串，一个是亲本1的第一部分和亲本2的第二部分的组合，另一个是亲本1的第二部分和亲本2的第一部分的组合。6.2.1无观测信息的搜索内容当智能体的感知根本不提供任何信息时，问题就变成了无传感器（一致性）问题。起初，如果无传感器智能体起始状态未知，那就无法求解问题，但无传感器解不依赖于传感器是否正常工作。合理的抽象任何抽象解都可以细化为现实世界中的具体解。有用的抽象执行抽象动作比在原始详细描述中搜索更容易。有用的抽象执行抽象动作比在原始详细描述中搜索更容易。可观测：在信念状态空间中，问题是完全可观测的，因为智能体始终知道自己的信念状态。路径代价：如果同一动作在不同状态下代价不同，那么在给定信念状态下执行动作的代价是几种不同值中的一种。假定同一动作在所有状态下具有相同代价，因此动作代价可以直接从底层物理问题中转换。6.2.2求解部分可观测问题内容当在给定PERCEPT函数的情况下，如何从底层物理问题推导出非确定性信念状态问题的RESULTS函数。使用这一形式化，可以直接应用搜索算法得到问题的解。合理的抽象任何抽象解都可以细化为现实世界中的具体解。有用的抽象执行抽象动作比在原始详细描述中搜索更容易。有用的抽象执行抽象动作比在原始详细描述中搜索更容易。黑盒：与标准搜索算法应用于无传感器问题的情况一样，与或搜索算法将信念状态看作和任何其他问题状