北大公开课-人工智能基础 27 局部搜索与群体智能优化和进化算法

模拟退火，有点类似于三维空间中的爬山法

目的在于在这个局部中，逼近全局最优解。

模拟退火的算法，初始节点为随机生成

对于当前节点的后继节点，也随机生成

但是对于由后继节点替换当前节点的规则，既非用最大最小值替换（最陡峭版本爬山法），也非用随机的后继节点替换当前节点（随机爬山法），

而是以概率p来接受价值更高的后继节点替换当前节点，这个概率p，相当于模拟退火算法的温度

直到解具有比当前阈值最低的值，或者迭代次数已经到达设定值，两个状态之一的情况下

类似于凝固状态，则返回该节点作为solution

模拟退火算法逻辑说明

设定初始参数problem，定义为问题状态

参数schedule ，相当于时间t 到 温度T的映射表

将问题的初始状态定义为current 当前节点

循环：以时间t 从1到无穷大，进行循环

        当使用schedule函数，将时间t映射为温度T的函数

        如果温度为0，则返回当前的节点（这里的温度是绝对温度，如果温度为绝对零度，那已经是最小值），退火过程也肯定结束了

        如果温度不为0，则随机选择当前的后继节点最为当前节点

        用后继节点的问题，减去当前节点的温度，记作能量值 E

        如果这个能量值大于0， 则基于概率p，将next 后继节点， 作为curren当前节点，进行下一轮迭代。

模仿自然选择过程的遗传算法

遗传算法，是进化算法的一类

用遗传算法解决8皇后问题

相当于将两个不同解，互相杂交，各取没有问题的一段互相杂交。

直至找到更优的状态解

遗传算法的逻辑

初始设定两个参数， 种群 population，个体的集合

适应性函数 FITNESS-FN，用于度量个体适应性的度量功能函数

循环：

    设置新的种群为空集合

    以种群的规模，作为循环的次数 （从1-种群规模进行循环）

       随机以x，y切分种群，且进行杂交运算，将mutate的xy子节点作为新的种群。