局部搜索算法是一类用于寻找优化问题解决方案的算法。在许多情况下,由于问题空间的大小或复杂性,找到全局最优解是不切实际的。局部搜索算法专注于通过小的、逐步的改进来迭代地提升候选解的质量。在每一步中,算法评估当前解的邻近解,并选择能够改善目标函数或满足特定条件的解。这些算法持续这一过程,直到找到满意的解或满足终止条件。
爬山算法是一种局部搜索算法,它通过贪婪策略来寻找最优解。这种算法遵循生成和测试变体的方法,不进行回溯,因为它不记录先前的状态。爬山算法不需要维护状态的树或图。爬山算法为旅行商问题提供了最好的解决方案,其中需要最小化旅行商所行进的距离。
function hill_climbing(problem) {
current = make_node(problem.initial_state) // 取初始节点作为当前节点
do { // 使用do-while循环直到返回
neighbor = highest_valued_successor_of(current) // 只考虑当前节点的最高价值后继者
if value[neighbor] <= value[current] // 如果其价值不优于当前节点,
return current // 返回当前节点
current = neighbor // 否则,将邻居作为当前节点并再次循环。
}
}
爬山算法的问题包括可能会在局部最大值处停止,假设它是最佳解,而实际上存在更好的解;在平坦区域停止,因为算法假设前方没有上坡;在山脊处,每个邻居看起来都是下坡,但状态空间搜索实际上有上坡,算法无法改变方向并向上走。
遗传算法是一种局部搜索技术,用于计算中寻找优化和状态空间搜索问题的真正或近似解。这种算法是进化算法的一类,使用遗传、变异、选择和交叉等技术,灵感来自进化生物学。遗传算法的核心思想是自然选择,即有利的特征在连续的代中变得普遍,不利的特征变得不普遍。解决方案由适者生存(最佳解)给出。
遗传算法的工作步骤如下:
交叉和变异是遗传算法中的两个关键操作。交叉可以通过选择一个个体的二进制子串并将其与另一个个体的二进制子串交换来执行。变异是通过以一定的概率改变每个基因来执行的。