求解多极小函数

求解多极值函数问题中，我们需要求出函数的最值，我们以函数 f(x0,x1) = x1sin(x0) x0 cos(x1) 为例，求它在 x0,x1 ∈ [10,10] 区间内的最小值。

使用 MATLAB 画出的函数图像如图 1 所示，其最小值可用 matlab 库函数求出，约为-17.394，同时该函数有多个局部极小值。

图 1: 函数 f(x) 图像

SA 算法

算法流程

如步骤图 2、参数设置图 3、流程图 4，步骤 1 中，初始温度可以有两种生成方式：按照经验设定固定初温或随机选择指定数量的状态计算目标值并把方差作为初温；初始解在连续函数中为函数值。

步骤 2 中，在外循环中，温度随着迭代而发生变化，收敛准则分为基于时间的收敛（指定迭代次数，需要指定迭代次数）和基于性能的收敛（连续若干步的目标值之差小于阈值，需要指定阈值和迭代步数）。

步骤 3 中，抽样稳定准则是在内循环中用来决定同一个温度下产生解的个数，温度不随着内循环迭代而发生改变。收敛准则分为基于时间的收敛（指定迭代次数，需要指定迭代次数）和基于性能的收敛（连续若干步的目标值之差小于阈值，需要指定阈值和迭代步数）。

步骤 4 为状态更新，在连续函数的优化问题中，需要指定自变量更新的步长和移动长度的分布类型（高斯分布或柯西分布其中退温为对外循环的温度进行降温，分为指数退温（需要指定温度衰减系数）和对数退温。

步骤 5 为状态判断，如果新解的目标值更优，则用它来替换当前解，否则保持当前状态不变，并继续循环。

图 2: 模拟退火算法流程

图 3: 模拟退火算法参数设置

2.1.2 次随机实验的统计结果

由于可选择的参数较多，这里的演示为指定了部分模式和参数来进行比较。不建议使用基于优化的收敛准则，因为需要指定阈值和迭代步数，在未知目标值范围的情况下随意迭代难以找到理想的解，有可能无法跳出循环。（改进思路：或许可以采用自适应阈值的算法。）

如图 1.1.2, 修改外循环迭代次数，依次为 50、100、150。在状态转换步骤中，即使新状态并非最优，也有一定的概率可以跳转到新状态上。在这里，外循环迭代次数设置得不宜过高，因为最终温度会变得非常小，导致跳转概率的计算超过计算机所能存储的 64 位，故在退温步骤中设置温度不能小于 1e-4。

在迭代次数为 50 时，20 次循环也找不到最小值；迭代次数为 100 和 150 时能够找到最小值，说明适当增加迭代次数有助于进行更大范围的搜索；但 150 次的平均性能未必比 100 次好，找到的最差解和平均解都不如 100 次。这可能是因为在循环中设置了温度的下限，在 (130，150] 次中进行迭代时，温度一直被限制在 1e-4, 使得在出现了性能并非更优的解时的跳转概率很大，即无论解如何都要跳转，导致性能相对于 100 次时发生下降。

2.1.3 目标函数的变化曲线

如图 8，算法在 35 个回合之后趋向于收敛。

图 4: 模拟退火算法流程图

图 5: 外循环迭代 50 次

图 6: 外循环迭代 100 次

图 7: 外循环迭代 150 次

图 8: 连续优化问题，SA, 目标函数的变化曲线

GA 算法

编码

遗传算法需要对问题的解进行编码，对此，我们使用 32 位二进制码表示问题的解，前 16 位表示 x0，后 16 位表示 x1。x0,x1 的取值范围都为 [10,10]，使用 16 位二进制码表示可以使解精确到小数点后 3 位。二进制码 [S]2 与实数 x 的关系为：

算法流程

算法流程与标准的 GA 算法相同，步骤与课件中相同，如图 9 所示。其中，适配值为函数值。

在产生新种群时，步骤 5 之前，先将上一代种群排序，保留一部分较优个体，再从中生成下一代种群。

图 9: 遗传算法流程

算法的选择步骤中，我们使用基于排名的方法，先将种群个体按适配值排名，以线性关系给每个排名的个体分配一个概率值，然后归一化。倒数排名为 i 的个体被选择的概率值为

此外，选择操作之前，父代种群中的适配值最高的两个个体会直接继承到子代种群。

交叉操作中，我们对 x0 染色体和 x1 染色体分别进行交叉。为交叉一对染色体，我们随机产生一个交叉点，交换该点左右的基因，生成一对新染色体。变异操作中，我们对染色体中的每个基因（01 二进制数）按变异概率进行随机改变。

我们采用保优操作，即保存算法出现过的适配值最高的解。如果保优值在若干回合中一直保持不变，认为算法收敛，提前结束迭代，同时我们也有最高迭代次数的限制。

算法参数

最大迭代次数：2000
种群规模：30
交叉概率：0.95
变异概率：0.1
保优值保持不变提前结束迭代的回合数：100
产生新种群时先从上一代种群选出一部分较优个体，其比例：1.0

次随机实验的统计结果

统计结果如图 10 所示，平均性能: 17.394，最佳性能: 17.394，最差性能: 17.393，方差:

。

图 10: 函数优化问题中，GA 算法 20 次随机实验的统计结果

目标函数的变化曲线

在一次实验中目标函数的变化曲线如图 11 所示。

图 11: 函数优化问题中，GA 算法目标函数的变换曲线

TSP 问题

我们以网络学堂中 TSP30 文件中的点信息做测试。

SA 算法

算法流程

算法流程与上文基本类似，不同之处在于：

步骤 1 中，初始温度可以有两种生成方式：按照经验设定固定初温要更大，随机选择指定数量计算方差时指定的元素数目也大得多；初始解在离散的 TSP 问题中为旅行商所经城市的路线。

步骤 4 为状态更新，在 TSP 问题中，可以通过进行两位置元素交换、两位置之间的元素逆序、把指定某一段序列插到第三个位置之后或者把上述操作按照概率混合的方法产生新的状态，即新的旅行商路线。

次随机实验的统计结果

30个城市：

最短距离为 423.74，0.7-3.6s 可找到最优解。

如图 12，从上到下依次指定外循环迭代 100 次、内循环迭代 200 次；外循环迭代 100 次、内循环迭代 400 次；外循环迭代 200 次、内循环迭代 400 次；外循环迭代 200 次、内循环迭代，所有参数的设置见图像 12 左半部分。

在外循环迭代 100 次、内循环迭代 200 次中，虽然随机 20 次实验中能够找到最优解（距离 423.741）, 但从图中可以看出这样的次数并不多，且距离方差很大。增大内循环迭代次数到，明显在 20 次实验中找到最优解的次数增加，距离方差也变小很多。

在外循环迭代 200 次、内循环迭代 400 次中，20 次随机试验中能够找到最优解的次数高于外循环迭代 100 次、内循环迭代 400 次；而将内循环迭代次数继续提高到 500 次时，性能又有了明显提升——最差距离与最优解仅仅相差不到 2 个单位，方差迅速降低到 0.24。

上述实验说明，在一定范围之内提高迭代次数有利于提升性能，但迭代次数设置得是否合理，是需要结合初始温度来进行考虑。迭代次数越多耗时越长，需要在性能与耗时方面做出权衡。

50个城市：

最短距离为 428.10，0.9-9.6s 内可找到最优解。

如图 13，参数设置与 30 个城市基本相同，仅改变内外循环次数进行实验。从上到下依次为外循环 100 次、内循环 200 次；外循环 100 次、内循环 400 次；外循环 200 次、内循环 400 次；外循环 200 次、内循环 1000 次。图中右半部分为 20 次实验中的最优路径，均没有发生路径交叉。随着迭代次数的增加，搜寻到的最短路径在减小，平均搜寻路径和方差也在减小，运行时间在增加。但由于状态更新的随机性，有时候未必能够得到性能优化。

75个城市：

最短距离为 544.20，37-173s 内可找到最优解。

如图 14，从上到下依次为初始温度 700、外循环迭代 200 次、内循环迭代 3000 次；初始温度 700、外循环迭代 200 次、内循环迭代 5000 次; 初始温度 700，温度收敛到 1e-5、内循环迭代 5000 次。图中左侧为 20 次实验所得结果，右图为每 20 次实验的最短路径。到了 75 个城市时，使用之前的参数已经无法获取最优解，因此需要进行参数调整。为了增加搜寻的路径范围，此时设置的参数值较 TSP30、TSP50 有大幅度增加。尽管如此，搜寻到最优解的概率仍然很小，运行多次也只能得到一次 544.20，连 546、547、548 这样的数值都很少能够搜寻得到。

总结：

在 50 个城市与 75 个城市中，由于城市较多，形成闭合路径的方法有很多，此时已经无法通过目测来判断每 20 次实验的最优解是否为最短路径。增加内循环次数的本质是在状态转换概率没有太大改变的情况下增加尝试的路径，以便尽可能覆盖较优解。增加外循环次数的本质是改变解的跳转概率，能够跳出局部最优，继续寻找全局最优解。

随着城市数量的增加，问题的复杂度变得很高，每次实验的运行时间变得很长，更难以搜寻到最优解，也无法通过肉眼判断是否搜寻到了最优，因为每次实验的路径都没有出现交叉。如图 15，随着问题规模的增长，距离开始明显下降的迭代次数开始上升 (TSP30 在 25 前后，TSP50 在 30-40 之间，TSP75 在 30-40 之间)，距离趋向于收敛的次数也在上升 (TSP30 在 50 之前，TSP50 在 50-60 之间，TSP75 大于 60)。说明盲目增大外循环迭代次数意义不大。问题规模对于 SA 算法的影响很大，在较复杂的问题下，SA 性能并不算理想；中小规模下 SA 算是一种兼顾了时间和性能的算法。

注：实验表明，在产生新状态的过程中，新状态应当基于前一个产生的新状态而不是当前状态来产生，即使前一个新状态没有被接受，不能成为当前状态。这样运行多次，新状态与当前状态将有较大不同，更有可能找到最优路径。若所有新状态都是基于当前状态产生，则路径