局部束搜索Local Beam Search

朴素的贪心局部搜索仅保留一个状态，较难找到全局最优解；若同时保留多个状态，则有更大的概率得到全局最优解，即局部束搜索

可以将算法描述如下

0. 初始化：随机产生k个状态
1. 对于每个状态，迭代生成$k$个后继节点，共生成$k^2$个后继状态
2. 从$k^2$个后继状态中选取$k$个最好的状态，回到1循环，直到找到目标状态

局部束搜索的问题在于$k$个状态多样性不足，一个改进的方案是在步骤2中随机选取后继状态增加多样性，即随机束搜索

遗传算法

遗传算法模拟了自然界中生物进化的过程：遗传变异-自然选择

• 个体：一个可能的状态
• 种群：一些个体组成的集合
• 杂交：以两个或更多的个体为基础构造新的个体，参与遗传的个体数目称为混合数，自然界中的混合数一半为2，算法实现中可以更多
• 突变：新生成的个体出现亲本没有的特征
• 适者生存：使得适应度评价函数值更高的个体可以继续在种群中生存下去

遗传算法能够找到问题的最优解，具有足够大的多样性