【2017年整理】4局域随机搜索.ppt

局域搜索与随机搜索;概要;搜索问题;实例;实例;挑战性;实例：旅行推销商问题（TSP）;实例：旅行推销商问题（TSP）;实例：可满足性问题（SAT）;实例：可满足性问题（SAT）;实例：N个皇后;实例：N个皇后;局域搜索;局域搜索;最简单的实例;最简单的实例;最基本的算法：爬山法(Hill Climbing)（局域贪婪搜索(GLS)）;更有趣的实例;议题;议题;贪婪爬山vs.随机爬山;随机搜索：随机爬山法;TSP移动;3边改变，产生O(N3)的邻域;爬山法：TSP示例;爬山法：N个皇后;爬山法：SAT;爬山法：SAT;模拟退火法（SA）;怎样给p赋值？;怎样给p赋值？;选择p：模拟退火法;选择p：模拟退火法;模拟退火法;模拟退火法;模拟退火法;示例;示例;基本示例;模拟退火法起源;TSP示例1;TSP示例;迭代次数;TSP示例2;TSP示例2;迭代次数;什么是收敛？;模拟退火法;SA讨论;SA讨论;SA讨论;局域射线搜索（LBS）;遗传算法（GA）;遗传算法：实现;遗传算法：复制;遗传???法：变异;基本GA概述;遗传算法：选择;GA和爬山法的比较;怎样用GA来解决问题？;变异例子：TSP;交叉例子：TSP;变异例子：8个皇后;TSP实例1;群体中最好的组元;15代时的群体;35代时的群体;TSP实例2;40代时的群体;更激进的想法; 在上面有关交叉定义的基础上，应用遗传算法。 应用示例：机器人控制、信号处理、电路设计。 有启发性，但对大多数应用还存在其它替代方案，因此不是首选应考虑的方法。;GA讨论;GA讨论;总结