蚁群算法

• 蚁群算法是一种用来寻找优化路径的概率型算法。这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种启发式全局优化算法。

• 将蚁群算法应用于解决优化问题的基本思路为：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，蚂蚁会在正反馈的作用下集中到最佳的路径上**，此时对应的便是待优化问题的最优解。

• 正反馈使优良信息保存下来，是一种学习强化能力。

• 多样性过剩，系统过于活跃，会导致过多的随机运动，陷入混沌状态；如果多样性不够，正反馈过强，会导致僵化，当环境变化时蚁群不能相应调整。

• 1. 感知范围
  2. 环境信息
     • 蚂蚁所在环境中有障碍物、其他蚂蚁、信息素，其中信息素包括食物信息素(找到食物的蚂蚁留下的)、窝信息素(找到窝的蚂蚁留下的)，信息素以一定速率消失。
  3. 觅食规则
     • 蚂蚁在感知范围内寻找食物，如果感知到就会过去；否则朝信息素多的地方走，每只蚂蚁会以小概率犯错误，并非都往信息素最多的方向移动。
  4. 移动规则
     • 蚂蚁朝信息素最多的方向移动，当周围没有信息素指引时，会按照原来运动方向惯性移动。而且会记住最近走过的点，防止原地转圈。
  5. 避障规则
     • 当蚂蚁待移动方向有障碍物时，将随机选择其他方向；当有信息素指引时，将按照觅食规则移动。
  6. 散发信息素规则
     • 在刚找到食物或者窝时，蚂蚁散发的信息素最多；当随着走远时，散发的信息素将逐渐减少。

神经网络算法

• 思维学普遍认为，人类大脑的思维分为抽象（逻辑）思维、形象（直观）思维和灵感（顿悟）思维三种基本方式。

• 人工神经网络就是模拟人形象思维。这是一个非线性动力学系统，其特色在于信息的分布式存储和并行协同处理。

  • 每层由单元（units）组成
  • 输入层是有训练集的实例特征向量传入
  • 经过连接接点的权重（weight）传入下一层，一层的输出是下一层的输入
  • 隐藏层的个数可以是任意的，输入层有一层，输出层有一层
  • 每个单元也可以称之为神经结点，根据生物学来源定义
  • 作为多层向前神经网络，理论上，如果有足够的隐藏层，和足够的训练集，可以模拟出任何方程
  • 一层中加权求和，然后根据非线性方程转化输出

• 交叉验证方法（cross-Validation）

  • 这里有一堆数据，我们把他切成3个部分（当然还可以分的更多）
    • 第一部分做测试集，二三部分做训练集，算出准确度；
    • 第二部分做测试集，一三部分做训练集，算出准确度；
    • 第三部分做测试集，一二部分做训练集，算出准确度；
    • 算出三个准确度的平均值，作为最后的准确度

• 人工神经元

  • 自然神经元是一个信号处理器，在神经元输入端有一个信号接收器，在输出端有一个响应单元。

  • 

  • f称为激活函数或激励函数（Activation Function），激活函数的主要作用是加入非线性因素，解决线性模型的表达、分类能力不足的问题。

• backpropagation算法

  • 通过迭代性来处理训练集中的实例，对比经过神经网络后，输人层预测值与真实值之间的误差，再通过反向法（从输出层=>隐藏层=>输入层）以最小化误差来更新每个连接的权重。

遗传算法

• 遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

• 遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。

• 1. 直接对结构对象进行操作，不存在求导和函数连续性的限定；
  2. 具有内在的隐并行性和更好的全局寻优能力；
  3. 选择、交叉和变异构成了遗传算法的遗传操作；
  4. 参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容；
  5. 采用概率化的寻优方法，不需要确定的规则就能自动获取和指导优化的搜索空间，自适应地调整搜索方向。

• 初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。

• 

模拟退火算法

• 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。

• 模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合一定的概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。

  • 

• 它是基于Monte-Carlo 迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。

• • 爬山算法

    • 爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。

    • 

  • 假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解

  • • 爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。
    • 模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。

• 模拟退火的流程

  • 

  • 假设开始状态在A，随着迭代次数更新到B局部最优解，这时发现更新到B时，能量比A要低，则说明接近最优解了，因此百分百转移，状态到达B后，发现下一步能量上升了，如果是梯度下降则是不允许继续向前的，而这里会以一定的概率跳出这个坑，这个概率和当前的状态、能量等都有关系，如果B最终跳出来了到达C，又会继续以一定的概率跳出来，直到到达D后，就会稳定下来。

  • 

  • 算法实质分两层循环，在任一温度水平下，随机扰动产生新解，并计算目标函数值的变化，决定是否被接受。由于算法初始温度比较高，这样，使E增大的新解在初始时也可能被接受，因而能跳出局部极小值，然后通过缓慢地降低温度，算法就最终可能收敛到全局最优解。

  • • 初始点的选取对算法结果有一定的影响，最好是多次运行对结果进行综合判断。
    • 在算法运行初期，温度下降快，避免接受过多的差结果。当运行时间增加，温度下降减缓，以便于更快稳定结果。
    • 当迭代次数增加到一定次数时，结果可能已经达到稳定，但是距离算法结束还有一段时间。在设计程序时应该加入适当的输出条件，满足输出条件即可结束程序。

• 模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。

• 模拟退火算法详解 - 知乎 (zhihu.com)

旅行商问题

• TSP问题（Travel Salesperson Problem，即旅行商问题或者称为中国邮递员问题），是一种NP-hard问题，此类问题用一般的算法是很难得到最优解的，所以一般需要借助一些启发式算法求解，例如遗传算法（GA），蚁群算法（ACO），微粒群算法（PSO）等等。

  • 多项式时间算法，能用多项式时间算法解决的问题被称为P问题( Polynomial)。

  • 随着问题规模n的增长，计算量的增长速度是非常恐怖的。这类问题被称为NP问题（Non-deterministic Polynomial），即非确定多项式问题。

  • 在NP问题之间，也可以存在归约关系。我们把众多的NP问题层层归约，必定会得到一个或多个“终极问题”，这些归约的终点就是所谓的NPC问题（NP-complete），也可以翻译成NP完全问题。

    • 

  • 就数量上而言，NP问题远比P问题要多，而NP之中的NPC问题也仅占极少数

    • 

• • 有一个商品推销员，要去若干个城市推销商品。该推销员从一个城市出发，需要经过所有城市后，回到出发地。每个城市之间都有道路连通，且距离各不相同，推销员应该如何选择路线，使得总行程最短呢？

    • 其中最容易想到的，是使用穷举法：

      • 排列组合，从所有路线中找出总行程最短的路线。显然，这个方法的时间复杂度是O(n！)，随着城市数量的增长，花费的运算时间简直不可想象！

    • 动态规划法、分枝定界法…

      • 这些算法的时间复杂度仍然是指数级的，并没有让性能问题得到根本的解决。

    • 贪心算法：

      • 又称贪婪算法（greedy algorithm）,该算法是指：在对问题求解时，总是做出当前情况下的最好选择，否则将来可能会后悔，故名“贪心”。这是一种算法策略，每次选择得到的都是局部最优解。选择的策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

      • 针对TSP问题，使用贪心算法的求解的过程为：

        1. 从某一个城市开始，每次选择一个城市，直到所有的城市被走完。
        2. 每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距离最小。

    • 启发式解法

    • …