四大算法指的是遗传算法GA、粒子群优化算法PSO、蚁群算法ACA、模拟退火算法SA，这里不记录遗传算法

🔥粒子群优化算法

• 粒子群优化(PsOparticle swarm optimization)算法是计算智能领域，除了蚁群算法，鱼群算法之外的一种群体智能的优化算法，该算法源自对鸟类捕食问题的研究
• PSO算法首先在可行解空间中初始化一群粒子，每个粒子都代表极值优化问题的一个潜在最优解，用位置、速度和适应度值三项指标表示该粒子特征
• 粒子在解空间中运动，通过跟踪个体极值Pbest和群体极值Gbest更新个体位置，个体极值Pbest是指个体所经历位置中计算得到的适应度值最优位置，群体极值Gbest是指种群中的所有粒子搜索到的适应度最优位置
• 粒子每更新一次位置，就计算一次适应度值，并且通过比较新粒子的适应度值和个体极值、群体极值的适应度值更新个体极值Pbest和群体极值Gbest位置
• 简单来说，粒子群算法PSO，通过个体极值Pbest和群体极值Gbest传递信息，最佳个体告诉其他个体自己的信息使得其他个体也会趋向于他移动。
• 与遗传算法不同点：

1. PSO算法没有选择、交叉、变异等操作算子
2. PSO有记忆的功能
3. 信息共享机制不同，遗传算法是互相共享信息，整个种群的移动是比较均匀地向最优区域移动，而在PSO中，只有gBest或lBest给出信息给其他粒子，属于单向的信息流动，整个搜索更新过程是跟随当前最优解的过程。因此在一般情况下，PSO的收敛速度更快

• 信息更新：如上图，每个个体的速度V和位置X按照上述公式进行不断迭代，其中两个P代表这个体极值和群体极值。
  
• PSO流程(初始化后)：速度更新(公式)-种群更新(原值加上速度)-适应度更新-个体最优更新-群体最优更新-将两个最优带回速度更新公式如此循环迭代
• 速度更新的权值变化，先大后小，利于先全局搜索再局部搜索，类似学习率下降的思路。

🔥蚁群算法

• 一种用于最优路径规划、网络路由的算法，“走的人多了也便成了路”
• 蚂蚁在寻找食物源时，会在其经过的路径上释放一种信息素，并能够感知其它蚂蚁释放的信息素。信息素浓度的大小表征路径的远近，信息素浓度越高，表示对应的路径距离越短
• 通常，蚂蚁会以较大的概率优先选择信息素浓度较高的路径，并释放一定量的信息素，以增强该条路径上的信息素浓度，这样，会形成一个正反馈最终，蚂蚁能够找到一条从巢穴到食物源的最佳路径，即距离最短。
• 值得一提的是，生物学家同时发现，路径上的信息素浓度会随着时间的推进而逐渐衰减
• 三种模型：

1. ant cycle system，蚂蚁从i到j全路程释放的信息素总量不变，越长的路线，信息素浓度越低。
2. ant quantity system，蚂蚁从i到j（相邻两地）释放的信息素总量不变，也就是信息素浓度分段变化，同路段信息素浓度相同
3. ant density system，蚂蚁全程信息素释放浓度不变，越长信息素总量越大

流程：

1. 初始化：蚁群规模m，信息素重要程度因子α，启发函数重要程度因子β，信息素总量Q，最大迭代次数iter_max，迭代次数初值iter=1
2. 构建解空间：每个蚂蚁放到不同起点，对每个蚂蚁求得下一个待访问城市，直到所有蚂蚁访问完所有城市
3. 更新信息素：计算每次迭代中的最优解（暂时的最短路径），更新每个路径段上信息素浓度
4. 判断终止否

特点：

1. 正反馈机制，不断收敛；
2. 每个个体既可以改变环境也能感知环境，个体间以此间接地通信；
3. 分布式计算，多个个体并行计算，效率高；
4. 启发式概率搜索，和遗传算法的轮盘堵一样，不易陷入局部最优。

• 旅行商问题TSP：找到一个遍历所有城市的最短路径，是一种用于验证优化算法的标准

🔥模拟退火算法

• 模拟退火算法(Simulated Annealing,简称SA)最早是由Metropolis等提出的。其出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性。模拟退火法是一种通用的优化算法，其物理退火过程由以下三部分组

1. 加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。温度足够高时，固体将熔为液体，从而消除系统原先存在的非均匀状态
2. 等温过程。对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行的，当自由能达到最小时，系统达到平衡状态
3. 冷却过程。使粒子热运动减弱，系统能量下降，得到晶体结构。

• 加温过程对算法设定初温，等温过程对应算法的Metropolis抽样过程，冷却过程对应控制参数的下降。这里能量的变化就是目标函数，我们要得到的最优解就是能量最低态。其中Metropolis准则是SA算法收敛于全局最优解的关键所在，Metropolis准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱

• 简单来说，模拟退火算法，在加温过程中允许接受非更优解，防止局部最优，在冷却过程中逐渐不接受非更优解

• 流程：

1. 初始化:取初始温度TO足够大，令T=T，任取初始解S1。
2. 对当前温度T，重复第(3)~(6)步。
3. 对当前解S1随机扰动产生一个新解S2。
4. 计算S2的增量df= f(S2)-f(S1)，其中f(S1)为S1的代价函数（代价低者好）。
5. 若df<0，则接受S2作为新的当前解，即S1=S2;否则计算S2的接受概率exp(-df/T)， 即随机产生(0,1)区间上均匀分布的随机数rand，若exp(-df/T)>rand，也接受S2作为新的当前解S1=S2，否则保留当前解S1。通过这个指数函数可以看出，温度高的时候接受概率更接近1，很容易接受非优解，反之亦然。
6. 如果满足终止条件Stop，则输出当前解S1为最优解，结束程序，终止条件Stop通常取为在连续若千个Metropolis链中新解S2都没有被接受时终止算法或者是设定结束温度；否则按衰减函数衰减T后返回第(2)步。

• 上面是模拟退火算法求最优解的过程，可以看到刚开始，波动变化大，说明易于接受更多的可能性，减少局部最优的出现可能性，后期则趋于稳定。