概述
经典优化算法
- 默认存在唯一最优解，问题是凸优化的
- 对解空间枚举(离散)，对目标函数的微分(连续)求最优解
某些优化问题
- 解空间太大，无法枚举
- 问题不是凸优化的
只能求近似解
- 近似算法、随机算法
- 启发式算法
启发式算法定义(heuristic algorithm)
通过对过去经验的归纳推理以及实验分析来解决问题的方法，借助于某种直观判断或试探的方法，以求得问题的次优解或以一定概率求其最优解
元启发式算法(metaheuristic)
从自然界的一些现象取得灵感，通过这些现象获取的额求解过程来解决实际的问题
启发式算法 = 元启发式算法 + 问题特征
局部搜索方法
局部搜索:2-opt算法
模拟退火(Simulated annealing)
旅行商问题(TSP问题)
禁忌搜索(Tabu search)
邻域
当前解进行一个操作（这个操作就是领域动作）可以得到的所有解的集合
邻域动作
禁忌表
候选集合
评价函数(目标函数)
候选集合元素选取的一个评价公式
特赦规则
Tabu search 算法
旅行商问题(TSP问题)
过程见PPT
遗传算法(Genetic algorithms)
先随机生成一组候选解，候选解中的个体通过交叉和变异产生新的解群，再从中选取较优的个体，重复此过程，直到满足某种收敛指标为止
种群
对应组候选解的集合
个体
对应一个解。在遗传算法中，需要把一个解构造成染色体
基因
染色体由基因构成
交叉
- 单点交叉
- 多点交叉
- 均匀交叉
- 洗牌交叉
变异
按照一定概率将个体中的基因值用其它基因值来替换，从而形成一个新的个体
选择
旅行商问题(TSP问题)
染色体交叉会出现非法解，通过两种方式解决
染色体变异也会出现非法解，通过两种方式
蚁群算法(Ant colonies)
基本蚁群算法
改进的蚁群算法
路径选择采用了利用和探索相结合的方法
信息素的更新采用全局更新和局部更新相结合的方案
