在一个非确定性的世界中，智能体将需要一个条件规划，并根据它所观测到的情况执行不同的动作。
之前的搜索问题关注于找到一条通过搜索空间的路径，但有时只需要关心最终状态，而不是到达状态的路径。局部搜索（$local$ $search$）算法的操作是从一个起始状态搜索到其相邻状态，它不记录路径，也不记录已达状态集。
这意味着局部搜索不是系统性的——可能永远不会探索问题的解实际所在的那部分搜索空间。但是，它们有两个主要优点：（1）使用很少的内存；（2）通常可以在系统性算法不适用的大型或无限状态空间中找到合理的解。
离散空间
爬山搜索算法是最基本的局部搜索技术，其思想是每次移动都朝最陡上升的方向前进，不考虑超出当前状态的直接邻居之外的状态，当它到达一个没有邻居具有更高值的“峰值”时，算法终止。
在离散空间通常使用一个完整状态形式化（$complete$-$state$ $formulation$）进行搜索，即每个状态都包含解的所有组成部分，但它们可能并不都在正确的位置。
爬山法有时被称为贪心局部搜索，因为它只是选择最优的邻居状态，而不事先考虑下一步该如何走，但事实证明，贪心算法往往相当有效。爬山法可能会由于以下原因而陷入困境，在每种情况下，算法都会到达一个无法再取得进展的点：
（1）局部最大值：局部极大值是一个比它每个相邻状态都高但比全局极大值低的峰顶。爬山法到达局部极大值附近就会被向上拉向峰顶，但随后将困在局部极大值处无路可走。
（2）岭：岭的存在将导致一系列局部极大值，对于贪心算法，这是很难处理的。
（3）平台区：平台区是指状态空间地形图中的平坦区域。它可能是一块平坦的局部极大值，不存在上坡的出口；也可能是一个山肩，从山肩出发还有可能继续前进。爬山搜索可能会迷失在平台区上。一个解决策略是：到达一个平台区时继续前进——允许横向移动，希望这个平台区真的是一个山肩。但如果实际上位于一块平坦的局部极大值上，那么算法就会陷入死循环。因此可以限制连续横向移动的次数，如在 100 次连续横向移动之后停止。
随机爬山法（$stochastic$ $hill$ $climbing$）在上坡行动中随机选择一个；被选中的概率随着上坡陡度的变化而变化。这种方法通常比最陡上升法收敛得更慢，但在某些状态地形图中，它能找到更好的解。
首选爬山法（$first$-$choice$ $hill$ $climbing$）通过不断随机地生成后继直到生成一个比当前状态更好的后继为止来实现随机爬山。当一个状态存在众多（如数千个）后继时，这是一个很好的策略。
另一种变体是随机重启爬山法（$random$-$restart$ $hill$ $climbing$），它从随机生成的初始状态开始，执行一系列爬山搜索，直到找到目标。算法完备的概率为 1，因为它最终会生成一个目标状态作为初始状态。
爬山法是否能成功在很大程度上取决于状态空间地形图的形状：如果几乎不存在局部极大值和平台区，那么随机重启爬山法可以很快找到一个好的解。NP 困难问题通常存在指数级数量的局部极大值。尽管如此，在几次重启后，通常也可以找到相当好的局部极大值。
从不“下坡”，即从不向值较低（或代价较高）的状态移动的爬山算法总是很容易陷入局部极大值。相比之下，纯粹的随机游走算法不考虑状态值，而是随机移动到一个后继状态，它最终能够找到全局极大值，但它的效率非常低。因此，尝试将爬山法和随机游走结合起来以同时获得高效性和完备性，似乎是合理的。
模拟退火算法的总体结构与爬山法类似。然而，它不是选择最佳移动，而是选择随机移动。如果该移动使得情况改善，那么它总是会被接受。否则，算法以小于 1 的概率接受该移动。概率随着该移动的“坏的程度”——评估值变差的量$\varDelta E$——呈指数级下降。概率也会随“温度”$T$的降低而减小：开始时$T$较高，“坏”的移动更有可能被接受，当$T$降低时，可能性也逐渐降低。如果$schedule$所设置的$T$降到 0 的速度足够慢，那么玻尔兹曼分布$e^{\varDelta E/t}$的一个性质是所有概率都集中在全局极大值上，即算法将以接近 1 的概率找到全局极大值。
对于内存限制问题，在内存中只保存一个节点似乎有些极端。局部束搜索算法记录$k$个状态而不是只记录一
个。它从$k$个随机生成的状态开始。在每一步中，生成全部$k$个状态的所有后继状态。如果其中任意一个是目标状态，那么算法停止。否则，它将从完整列表中选择$k$个最佳后继并重复上述操作。
在局部束搜索中，有用信息将在并行的搜索线程之间传递，而非简单的并行地运行$k$次随机重启。如果$k$个状态之间缺乏多样性，局部束搜索可能会受到影响——$k$个状态可能聚集在状态空间的一块小区域内，导致搜索只不过是$k$倍慢版本的爬山法。
一种被称作随机束搜索的变体可以帮助缓解这个问题，它类似于随机爬山法。随机束搜索不是选择最佳的$k$个后继状态，而是选择概率与它对应的目标函数值成正比的后继状态，从而增加了多样性。
遗传算法可以看作随机束搜索的变体，算法的动机明显来自生物学中自然选择的隐喻：一个由个体（状态）组成的种群，其中最适应环境（值最高）的个体可以生成后代（后继状态）来繁衍下一代，这个过程被称为重组（recombination）。进化算法存在无数种形式，它们按照以下方式变化。
1、种群规模。
2、每个个体的表示。在遗传算法中，每个个体都是有限字母表上的一个字符串（通常是一个完整状态形式化），就像$DNA$是字母表$ACGT$上的一个字符串一样。在进化策略中，个体是实数序列。
3、混合数，$\rho $ ，是一起形成后代的亲本的数量。最常见的情况是$\rho =2$：双亲结合它们的“基因”（它们表示的一部分）来形成后代。当$\rho =1$时，为随机束搜索（可以看作无性繁殖）。$\rho > 2$也是可能的，这在自然界中很少发生，但很容易在计算机上进行模拟。
4、选择过程。选择将成为下一代亲本的个体：一种可能是从所有个体中选择，被选中的概率与其适应度得分成正比。另一种可能是随机选择$n$个($n > \rho $)个体，然后选择最适合的$\rho > 2$个个体作为亲本。
5、重组过程。一种常见的方法（假设$\rho =2$）是随机选择一个杂交点来分割每个父字符串，并将这些部分重新组合以形成两个子串，一个是亲本 1 的第一部分和亲本 2 的第二部分的组合；另一个是亲本 1 的第二部分和亲本 2 的第一部分的组合。
6、突变率，它决定了后代在其表示上发生随机突变的频率。一旦产生了一个后代，其组成中的每位都将以与突变率相等的概率被翻转。
7、下一代的构成。可能只包括新形成的后代，也可能还包括一些上一代中得分最高的个体［这种做法被称为精英主义，它确保总体适应度永远不会随着时间的推移而下降］。而淘汰，即丢弃所有分数低于给定阈值的个体，会使得进化加速。
通常情况下，早期的种群是多样化的，所以在搜索过程的早期阶段，杂交常常在状态空间中采取较大的步调（类似于模拟退火）。在经过许多代选择提高了适应度后，种群的多样性减少，步调也随之变小。遗传算法类似于随机束搜索，但增加了杂交操作。如果存在可以执行有用功能的区域，杂交操作是有利的。
遗传算法理论用模式思想来解释它是如何运作的，模式是指其中某些位未确定的子串。可以证明，如果某模式实例的平均适应度高于平均值，那么该模式的实例数量将随着时间推移而不断增加。当模式对应于解中有意义的组件时，遗传算法效果最优。这表明，遗传算法的成功依赖于精细的表示工程。实际上，遗传算法在广泛的最优化方法中占有一席之地，尤其是复杂结构问题。
连续空间的局部搜索
处理连续状态空间的一种方法是离散化，然后就可以对离散化后的空间应用任意局部搜索算法。或者通过随机采样后继状态，即在随机方向上移动一个小量$\delta $，使分支因子变为有限值。通过两个相邻点之间目标函数值的变化来衡量进度的方法称为经验梯度。经验梯度搜索与离散化状态空间中的最陡上升爬山法相同。随着时间逐渐减小$\delta $的值可以得到更准确的解，但不一定在极限范围内收敛到全局最优值。通常有一个以数学形式表达的目标函数，这样就可以用微积分来解析地而非经验地求解问题。
给定一个局部正确的梯度表达式，可以根据下式来更新当前状态从而实现最陡上升爬山法：
$$
x\gets x+\alpha \nabla f\left( x \right)
$$
其中$\alpha $是一个很小的常数，通常称为步长（step size）。存在很多调整$\alpha $的方法。基本问题是，如果$\alpha $太小，需要的迭代步太多；如果$\alpha $太大，搜索可能会越过最大值。线搜索技术试图通过不断延伸当前梯度方向——通常通过对反复加倍——直到$f$再次开始减小来克服上述困境。出现上述现象的点成为新的当前状态。在这点上如何选择新的方向，有几种不同的方法。
局部搜索方法在连续状态空间和离散状态空间中一样，同样受到局部极大值、岭和平台区的影响。随机重启和模拟退火通常很有用。然而，高维连续空间非常大，算法很容易陷入困境。
如果一个优化问题的解必须满足对变量值的一些硬性约束，那么这个问题就是受约束的。约束优化问题的难度
取决于约束和目标函数的性质。最著名的一类问题是线性规划问题，其约束必须是能构成凸集的线性不等式，目标函数也必须是线性的。线性规划的时间复杂性是关于变量数目的多项式。
线性规划可能是最广泛研究和最有用的优化方法。它是更一般的凸优化问题的一种特例，允许约束区域为任意凸区域，目标函数为约束区域内的任意凸函数。在一定条件下，凸优化问题也是多项式时间内可解的，即使有上千个变量，也可能是实际可行的。机器学习和控制理论中的几个重要问题可以形式化为凸优化问题。
