- 模拟退火算法
- 遗传算法
- 比较
来源点击这里
简介
模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小
算法主体
概括
该算法有两个循环条件,一个是依据种群规模而定的L,一个是最低温度,达到L或者达到最低温度则结束循环，在循环内进行的操作是,我们有一个初始解，对初始解进行扰动产生新解，如果新解优于初始解，则用新解继续循环，在一定概率内接受较差解，防止局部最优，接受差解的概率随着温度的降低而降低，在整个算法过程中，温度由初始温度和温度衰减系数决定逐渐降低，整个解逐步稳定
算法难点
如何扰动产生新解是整个算法的难点,本文对此问题采取的方法是，我们对于该TSP问题的目标函数是总路程最短,比如有10个我们要经过的城市，路线为0->1->2->3->4->5->6->7->8->9->10->0,0表示的是初始点和结束点,我们对其产生的扰动是,在起始点和终点之间随机选取两个下标，在其中间的路线逆序,比如我们选择2和7,扰动过后路线为0->1->2->6->5->4->3->7->8->9->10->0,路线变化后整个总路程变化为d(2,3)+d(6,7)-d(2,6)-d(3,7).其中d(x,y)表示x到y的距离,如果该路程变化小于0,则接受新路线
各个变量设置
T:初始温度，可直接同本文直接设置为1
（？？？有的地方设置1000，要不折中一下，下次设100）
L:循环终止条件之一,一般为问题规模*100
at:温度衰减系数,可直接同本文0.99
e:最低温度,循环终止条件之一，可直接同本文10^(-30)
算法总结
该算法的最难点就是如何产生新解，其余几乎都一样，没啥太大变化，就是不断迭代，求最优的过程，还要稍微关注一下接受较差解的条件，本算法可以做的图也有两个，一个是最终结果图，一个是不断迭代，目标函数值趋近最优的变化图像，该算法也是个优化算法，每次运行的结果可能不同，进行该算法时，对初值稍微筛选一下，效果更好
好的博客
题目理解
遗传算法遗传算法作为现代优化算法之一，其主要特点是对非线性极值问题能以概率1跳出局部最优解，找到全局最优解
————————————————
以下为CSDN博主「jjb-coder」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接
算法主体
概括
随机产生50个初始种群(50是可以变的，不过一般可以直接取50,该种群也可以用一定的算法进行择优选择)，这些种群构成了我们的初始种群群体，然后我们对这些初始种群群体进行操作不断迭代出更优的新解，这些操作包括交叉、变异、遗传等，然后经过一定的迭代次数之后，就会的到我们最终的解，也是50个种群，我们从50个种群中选出最优的种群，即我们问题的答案
编码格式
一般在选择编码格式时，要结合具体问题具体分析，这个是需要自己设计的，常用的编码格式有二进制编码、十进制编码等，可以往下翻翻看看本文要解决的问题，本文程序中采用的是十进制编码，通过十进制编码，我们可以这样表示一个种群，1->4-79->5->…->6->10->102,1和102表示我们的起点和终点，它们中间包含2~101的一个随机排列，表示我们中间要经过的100个点,通过这个一维矩阵我们可以很好的表示我们的行走路线，通过距离矩阵我们也能很轻易的求出每段路程进而求出总路程,能很好的表示问题的解，这是我们选择编码格式最重要的一点
适应度函数
这个就是我们比较两个解，哪个解较优的一种判别方法，然后我们将保留较优的那个解，这个也是自己依据问题自己设计的，本文程序中较为简单，它的目标函数就是比较二者整个行驶路线的总距离，较短的那个就是较优的
交叉操作
这个是我们选定了初始种群群体以后，产生新种群的一种方式，随机选择种群两两进行交叉，这个也是自己设计的，本文程序中是这样进行交叉操作的，随机选择好两个种群之后，随机产生一个下标，把这两个种群中，该下标到该种群末尾整个进行互换形成交叉操作
变异操作
变异操作是我们为了防止局部最优解而进行的操作，在较小概率内，随机选择种群进行变异操作，本文程序选取的概率是10%，进行变异操作的原理是在一个种群内随机形成三个下标，三个下标，夹杂着两个区间段，该变异操作就是直接把两个区间段进行互换
各个变量设置
种群规模: 20~200都可，一般直接取50
交叉系数: 系数较大会破坏整个种群优良的结构，较小则产生新个体的速度较慢。一般设置在0.4~0.99，本文采用的是随机概率
变异概率: 系数较小则可能产生局部最优，系数较大则会随机性过强，一般取0.0005~0.01，本文以10%概率选出种群，然后在种群内部随机选出片段进行变异
终止迭代次数: 100以上都行，具体看整个问题规模，迭代次数过大唯一的缺点就是程序运行时间长，没有这个顾虑的话可以设大点，本文取得是100
算法总结
该算法最大的难点就是编码格式的设计和适应度函数的选取，编码格式设计好了，整个交叉操作和变异操作都迎刃而解，编码格式设计的要能表示整个解，适应度函数要能比较两个解的优劣，在数学建模中，可以写到论文中去的两个图片，一个是最终的运行结果图，一个是整个迭代次数内整个种群的优化过程,该算法准确来说是求出较优解，每次运行的结果可能不同
遗传算法具有较强的全局搜索能力，但早熟容易收敛慢，模拟退火算法具有较强的局部搜索能力，但能随机行走，缺乏全局搜索能力
