1.模拟退火算法
可能的情况很多,数据量太大,用模拟退火搜索出需要的解(求最值)(最大值问题可以添加负号转换成求最小值问题)
启发式搜索:利用搜索过程中获取的信息改进搜索策略。启发式搜索有利于找到问题最优解,且有助于加速求解过程。
模拟退火可以说是最简单(应用)的启发式搜索之一
相比起爬山法(找到局部最优解),模拟退火算法有一定概率能接受比当前还要差的解,概率p位于[0,1],旧解和新解的函数值越接近,p值就越大(概率为0对应爬山法,概率为1对应蒙特卡洛算法);时间越长,p值越小;搜索前期p大,后期p小
2.搜索过程
1.随机生成一个解A,计算F(A)
2.在A附近随机生成一个解B,计算F(B)
3.对比F(A)和F(B),进行对比,若F(B)>F(A)(求最大值),B赋值A,F(B)<F(A),计算接受B的概率,接受则B赋值A,且重复以上操作,否则返回第2步,在原来A附近再生成一个B继续下去
如果优化问题有约束条件: 1.生成B是查看是否符合要求 2.使用罚函数
与时间相关的系数Ct如何设置:Ct是温度t的倒数(模拟退火)
如何再A附近随机生成一个解B:没有统一规定,需要具体问题具体分析
停止搜索
1.达到迭代次数 2.达到指定温度 3.找到连续最优解,M(如30次)次迭代还未改变
3.实现
产生新解:
1.matlab内置工具
根据温度不同,新解距离旧解的步长改变,温度高步长高,温度低步长短,由全局缩短为
x_new=x_i+T×z_i 然后检查x_new是否位于上下界
2.旅行商问题
交换法,位移法,倒置法