前言一、局部搜索算法(local search )二、爬山法(HILL-CLIMBING )模拟退火(SIMULATED ANNEALING )聚焦搜索(Beam Search )遗传算法
前言局部搜索算法综述
局部搜索算法是一种能有效解决优化问题的通用算法。 其基本原理是在邻近解中迭代，逐步优化目标函数，直到不能进一步优化。
局部搜索算法假设问题的解空间表示为s，局部搜索算法从一个初始解iS开始，然后根据具体问题定义的具体邻域结构，在当前解I的邻域Si内按照一定的规则找到新解，用该新解替换I 可以这样描述：判断是否满足算法终止条件，如果不满足，则继续将算法应用于当前解，如果满足，则算法终止，当前解成为算法的最终解。
本地搜索算法具有以下特征：
算法是通用的，容易实现。 如果定义与具体问题相关的邻域，就可以有效地解决该问题。
算法的性能与邻域的定义和初始状态有关。 邻域定义的不同和初始状态选择的不同会对算法的性能产生决定性的影响。
算法的局部优化特性。 算法容易陷入局部最优解，难以达到全局最优。
本地搜索算法主要有五个要素。
目标函数：用于判断解的优劣。
邻域定义：根据问题的不同，有不同的邻域定义。
初始解的生成规则
新解的生成和接受规则
算法终止准则(常见三个准则：求解时间； 迭代次数； 和解质量提高的比例)
本地搜索的算法如下所示。
局部搜索算法(local search )局部搜索是一种解决优化问题的启发式算法。 对于计算非常复杂的优化问题(例如，各种NP完全问题)，找到最佳解所需的时间根据问题的规模而指数地增加。 因此，各种启发式算法应运而生，求解后寻找最优解的是近似算法(Approximate algorithms )，是一种随时间变化精度的思想。 本地搜索是其中的一种方法。
局部搜索算法由爬山法改进而来。
简单地说，局部搜索算法是一种简单的贪婪搜索算法，每次从当前解的邻域解空间中选择最优解作为当前解，到达局部最优解。
在计算机科学中，局部搜索是一种解决优化问题的启发式算法。 局部搜索从一个初始解出发，搜索解的附近，如果有更好的解的话移动到该解并继续搜索，否则返回当前的解。
局部搜索算法的基本思想：在搜索过程中，总是选择当前点近邻中最接近目标者的方向进行搜索。
局部搜索的优点：简单、灵活、容易实现。 缺点是容易陷入局部最优，解的质量与初始解和邻域的结构密切相关。
二、爬山算法(hill-climbing algorithm )爬山算法是一种简单的贪婪搜索算法，每次该算法都从当前位置邻域中选择一个最优解作为当前解，从而得到一个局部最优解。
登山算法的输入是已定义的两个局部变量，一个是当前状态(当前节点)，另一个是用于保存相邻节点的neighbor。 我们从初始节点，也就是我们现在的节点出发，开始往前爬山。 首先，根据当前节点可以建立多少后续节点，然后从这些后续节点中选择用你定义的评估函数评估的最大值的后续节点，将其放入neighbor中，将后续节点的值与当前节点的值进行比较如果发现当前节点的值大于后续节点的值，则当前节点是本地最大值点，所以不需要移动，而是对应于当前节点。然而，如果当前节点的值小于后续节点的值，则前进到下一节点。 这样一步一步地反复进行直到达到局部最高值点。
我们可以类比成一个兔子爬山的例子，为了找出地球上最高的山，一群有志气的兔子们开始想办法。
爬山算法就像失忆的兔子在浓雾中爬山一样。 这里明确了登山算法的两个问题：
失忆:也就是说，这只兔子不记得他去了哪里，只记得他现在所在的位置和周边的情况。
所以，他说他随时只保存一个现在的状态，不记得之前的所有状态。 可以看出，登山算法很大程度上依赖于该初始状态(如果初始状态接近全局最高值点，则容易检索全局最高值点)。
浓雾:当他到达局部最高值点时，他看到了远处是否有更大的最高值点，所以把现在的这个局部最高值点还给你。 爬山算法的返回返回的是状态而不是路径。 这种状态是局部最高值点。
因此，登山算法的主要缺点是有可能陷入局部最优解，不一定能检索全局最优解。
为了防止陷入模拟退火局部最优，模拟退火算法在一定概率上接受比当前解更差的解，接受坏解的概率随着迭代次数的增加而降低。
该算法开始于初始解，该初始解可随机选择或启发式获得，并可对温度进行初始化。 每次迭代时，从当前解的邻居解中随机选择一个解，如果随机选择的一个邻居解比当前解质量好，则替换当前解，如果质量比当前解差，则以一定概率接受
这个差解，来替换当前解。最后更新温度T，进行下一次迭代。同样类比成兔子爬山，模拟退火方法是一群喝醉的兔子。
兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。
1.简介
Beam Search（集束搜索）是一种启发式图搜索算法，通常用在图的解空间比较大的情况下，为了减少搜索所占用的空间和时间，在每一步深度扩展的时候，剪掉一些质量比较差的结点，保留下一些质量较高的结点。这样减少了空间消耗，并提高了时间效率，但缺点就是有可能存在潜在的最佳方案被丢弃，因此Beam Search算法是不完全的，一般用于解空间较大的系统中。
2.流程
Beam Search（集束搜索）使用广度优先策略建立搜索树，在树的每一层，按照启发代价对节点进行排序，然后仅留下预先确定的个数（Beam Width-集束宽度）的节点，仅这些节点在下一层次继续扩展，其他节点就被剪掉了。如果集束宽度无穷大，那该搜索就是宽度优先搜索。
集束宽度可以是预先定好的，也可以是变动的，可以先按照一个最小的集束宽度进行搜索，如果没有找到合适的解，再扩大集束宽度再找一遍。
Ps. 个人认为集束搜索方法其实提供了一种找最优解的思路，就是说在适当的情况下，可以剪掉一些可信度低的路径，在实际使用中，可以每一层的集束宽度不一致，比如在初始的一些层次中多保留一些结果，在后边就可以放心大胆的进行剪枝。当然也可以活学活用，可以结合深度优先算法，通过回溯，可以找到最优解。
3.应用
Beam Search（集束搜索）多用在一些大型系统中，比如机器翻译系统，语音识别系统等，因为这些系统中的数据集可能非常大，而且结果也没有唯一正确的解，系统用最快的方式找到最接近正确的解才是系统的目标。
遗传算法（Genetic algorithm）遗传算法实际上是随机束搜索的变形, 通过吧两个父状态结合生成后继。
种群：种群中的每个个体都是潜在解
个体表示： 染色体， 实际就是状态的表示
适应度函数：表示解的好坏程度
选择（利用）：根据适应度选取比较好的解优先进行两两繁殖
交叉（利用为主+探索）： 选取一个杂交点， 两边染色体互相交换
变异（探索）：每个位置都会小概率发生变异
类比成兔子，遗传算法是一群吃了失忆药片随机分布在地球上的某些地方的兔子们。
他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。
总结
提示：这里对文章进行总结：
方法还未介绍完全。暂无，待更新。