武汉大学研究生课程：探索启发式算法：遗传、模拟退火等

启发式算法是一种在解决复杂问题时，人们根据以往经验和直觉，而非严格遵循系统步骤或算法的策略。它主要应用于优化问题，特别是在面对没有确定解法、解空间庞大或非凸的复杂问题时。这些问题可能包括求解近似最优解，因为并非所有问题都能通过传统方法找到全局最优。 经典优化算法通常依赖于遍历解空间或目标函数的微分，假设存在唯一最优解。然而，现实中的许多问题由于非凸性、解空间过大，使得这种方法难以应用。因此，启发式算法应运而生，如： 1. **构造方法（Construction methods）**：例如贪心算法，这种策略从局部最优选择出发，每次决策都试图达到当前状态下最好的结果，但不能保证全局最优。 2. **局部搜索方法（Local search methods）**：这类算法强调在有限时间内通过局部调整来逼近全局最优解。它们避免了全局搜索的高时间复杂度，但需防止陷入局部最优陷阱。常见的局部搜索算法包括： - **模拟退火（Simulated Annealing）**：灵感来源于金属冷却过程的退火现象，允许算法在搜索过程中接受低于当前最优解的解，以增加探索未知区域的可能性，从而跳出局部最优。 - **禁忌搜索（Tabu Search）**：类似于烹饪中的禁忌（如某些香料组合），算法限制或禁止在搜索过程中访问已被标记为"禁忌"的状态，以避免重复或陷入局部最优。 - **遗传算法（Genetic Algorithms）**：模拟生物进化过程，通过选择、交叉和变异操作来改进解的质量，寻找全局最优解。 - **蚁群算法（Ant Colony Optimization）**：模仿蚂蚁寻找食物的行为，通过释放信息素来引导搜索路径，寻找最有效的解决方案。 这些启发式算法的目标是找到接近最优的解，但并不保证一定能找到全局最优。它们广泛应用于人工智能领域，尤其是在组合优化、机器学习、游戏策略等领域，因它们能够在复杂问题上提供可行且高效的解决方案。然而，它们通常适用于大规模问题，且需要结合具体问题的特性进行调整和优化。