启发式算法 (Heuristic Algorithm) 是一种基于直观或经验的局部优化算法.。
启发式算法的定义:
人们常常把从大自然的运行规律或者面向具体问题的经验和规则中启发出来的方法称之为启发式算法. 现在的启发式算法也不是全部来自然的规律, 也有来自人类积累的工作经验。
在可接受的花费 (指计算时间和空间) 下给出待解决组合优化问题每一个实例的一个可行解, 该可行解与最优解的偏离程度不一定事先可以预计。
启发式算法是一种技术, 该技术使得能在可接受的计算费用内去寻找尽可能好的解, 但不一定能保证所得解的可行性和最优性, 甚至在多数情况下, 无法描述所得解与最优解的近似程度。
几种启发式算法
1.禁忌搜索 (Tabu Search): 它是对局部领域搜索的一种扩展,是一种全局逐步寻优算法, 是对人类智力过程的一种模拟。
2.模拟退火 (Simulated Annealing): 它是一种通过模拟物理退火过程搜索最优解的方法。
3.遗传算法 (Genetic Algorithms): 它是一种通过模拟自然进化过程搜索最优解的方法。
4.神经网络 (Neural Networks): 它是一种模仿动物神经网络行为特征, 进行分布式并行信息处理的算法数学模型。
5.蚁群算法 (Ant Algorith): 它是一种模仿蚂蚁在寻找食物过程中发现路径的行为来寻找优化路径的机率型算法。
这里面2、3、4种用到的比较多。这里先学习2和3。
启发式算法在最开始的时候要先给出一个或多个解
退火算法
快速模拟退火算法的降温方式
花费函数COST
1.应该能被快速的计算, 花费函数的计算是程序的可能瓶颈。
2.花费函数 COST 一般由目标函数来构造. 目标函数, 或目标函数的倒数/相反数经常直接作为花费函数。
终止条件
1.理论上温度要降为 0 才终止退火算法. 但实际上温度较低时,尝试的接受概率就几乎为 0 了。
2.设置终止温度的阈值, 或设置外循环迭代次数。
3.算法搜索到的最优值连续若干步保持不变。
模拟退火算法的实例
已知中国 34 个省会城市 (包括直辖市) 的经纬度, 要求从北京出
发, 游遍 34 个城市, 最后回到北京. 用模拟退火算法求最短路径。
根据上面几个设计要素：
初始解的生成
随便给以一组顺序就是一组解了。
初始温度设定降温
| 用到的代码 | 说明 |
|---|---|
| randperm(n) | 对1到n进行随机排序 |
| length | 返回矩阵或向量的长度 |
| distance | 对球面两点求解距离 |
| distancematrix | 自定义函数，计算距离矩阵 |
| totaldistance | 自定义函数，路径距离计算 |
| perturb | 自定义函数,产生临解的函数 |
主程序代码
自定义函数
distancematrix
totaldistance
perturb
没有源代码不建议尝试，上面是整个设计的思路，并不是全部的代码。
变异
单点变异、换位变异
依旧是一个随机的排列组合。
适应度函数
距离越短越适应，要想适应度值大，就选取距离的倒数即可。
选择运算
两两竞争、轮盘赌
交叉运算
这里的交叉很复杂，因为当交叉互换了一个点后，很可能在单个染色体上就出现了重复的数（重复去了一个城市），所以需要继续互换，将原来的数再与另一个染色体进行对换，直到每条染色体上午重复数值。
变异运算
可以选择对调两点或全部打乱或分块后打乱。
主程序代码
popSize = 100; % 种群规模max_generation ＝ 1000; % 初始化最大种群代数Pmutation = 0.16; % 变异概率for i = 1:popSize % 初始化种群 pop(i,:) = randperm(numberofcities);endfor generation = 1:max_generation % 主循环开始 fitness = 1/totaldistance(pop,dis);% 计算距离(适应度) [maxfit, bestID] = max(fitness); bestPop = pop(bestID, :); % 找出精英 pop = select(pop,fitness,popSize,'competition');% 选择 pop = crossover(pop); 来源：Temmie1024
声明：本站部分文章及图片转载于互联网，内容版权归原作者所有，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！