基于Python实现GA和SA求解函数优化问题及TSP问题【100010267】

> # ♻️ 资源 > **大小：** 3.72MB > **文档链接：**[**https://www.yuque.com/sxbn/ks/100010267**](https://www.yuque.com/sxbn/ks/100010267) > **➡️ 资源下载：**[**https://download.csdn.net/download/s1t16/87354481**](https://download.csdn.net/download/s1t16/87354481) > **注：更多内容可关注微信公众号【神仙别闹】，如当前文章或代码侵犯了您的权益，请私信作者删除！** >  # 智能优化算法 大作业 # 一、求解多极小函数 求解多极值函数问题中，我们需要求出函数的最值，我们以函数 f(x0,x1) = -x1_sin(x0)- x0 _ cos(x1) 为例，求它在 x0,x1 ∈ [10,10] 区间内的最小值。 使用 MATLAB 画出的函数图像如图 1 所示，其最小值可用 matlab 库函数求出，约为-17.394，同时该函数有多个局部极小值。  图 1: 函数 f(x) 图像 ## 1.1 SA 算法 ### 1.1.1 算法流程 如步骤图 2、参数设置图 3、流程图 4，步骤 1 中，初始温度可以有两种生成方式：按照经验设定固定初温或随机选择指定数量的状态计算目标值并把方差作为初温；初始解在连续函数中为函数值。 步骤 2 中，在外循环中，温度随着迭代而发生变化，收敛准则分为基于时间的收敛（指定迭代次数，需要指定迭代次数）和基于性能的收敛（连续若干步的目标值之差小于阈值，需要指定阈值和迭代步数）。 步骤 3 中，抽样稳定准则是在内循环中用来决定同一个温度下产生解的个数，温度不随着内循环迭代而发生改变。收敛准则分为基于时间的收敛（指定迭代次数，需要指定迭代次数）和基于性能的收敛（连续若干步的目标值之差小于阈值，需要指定阈值和迭代步数）。 步骤 4 为状态更新，在连续函数的优化问题中，需要指定自变量更新的步长和移动长度的分布类型（高斯分布或柯西分布其中退温为对外循环的温度进行降温，分为指数退温（需要指定温度衰减系数）和对数退温。 步骤 5 为状态判断，如果新解的目标值更优，则用它来替换当前解，否则保持当前状态不变，并继续循环。  图 2: 模拟退火算法流程  图 3: 模拟退火算法参数设置 ### 1.1.2 次随机实验的统计结果 由于可选择的参数较多，这里的演示为指定了部分模式和参数来进行比较。不建议使用基于优化的收敛准则，因为需要指定阈值和迭代步数，在未知目标值范围的情况下随意迭代难以找到理想的解，有可能无法跳出循环。（改进思路：或许可以采用自适应阈值的算法。） 如图 1.1.2, 修改外循环迭代次数，依次为 50、100、150。在状态转换步骤中，即使新状态并非最优，也有一定的概率可以跳转到新状态上。在这里，外循环迭代次数设置得不宜过高，因为最终温度会变得非常小，导致跳转概率的计算超过计算机所能存储的 64 位，故在退温步骤中设置温度不能小于 1e-4。 在迭代次数为 50 时，20 次循环也找不到最小值；迭代次数为 100 和 150 时能够找到最小值，说明适当增加迭代次数有助于进行更大范围的搜索；但 150 次的平均性能未必比 100 次好，找到的最差解和平均解都不如 100 次。这可能是因为在循环中设置了温度的下限，在 (130，150] 次中进行迭代时，温度一直被限制在 1e-4, 使得在出现了性能并非更优的解时的跳转概率很大，即无论解如何都要跳转，导致性能相对于 100 次时发生下降。 ### 1.1.3 目标函数的变化曲线 如图 8，算法在 35 个回合之后趋向于收敛。  图 4: 模拟退火算法流程图  图 5: 外循环迭代 50 次  图 6: 外循环迭代 100 次  图 7: 外循环迭代 150 次 图 8: 连续优化问题，SA, 目标函数的变化曲线 ## 1.2 GA 算法 ### 1.2.1 编码 遗传算法需要对问题的解进行编码，对此，我们使用 32 位二进制码表示问题的解，前 16 位表示 x0，后 16 位表示 x1。x0,x1 的取值范围都为 [10,10]，使用 16 位二进制码表示可以使解精确到小数点后 3 位。二进制码 [S]2 与实数 x 的关系为�