基于Python+MATLAB的智能优化算法设计

Love The Way You Lie 2024-04-07 13:53 33阅读 0赞

目录  
1求解多极小函数 2  
1.1SA 算法 2  
1.1.1算法流程 2  
1.1.220 次随机实验的统计结果 3  
1.1.3目标函数的变化曲线 3  
1.2GA 算法 6  
1.2.1编码 6  
1.2.2算法流程 6  
1.2.3算法参数 7  
1.2.420 次随机实验的统计结果 7  
1.2.5目标函数的变化曲线 7  
2TSP 问题 8  
2.1SA 算法 8  
2.1.1算法流程 8  
2.1.220 次随机实验的统计结果 8  
2.2GA 算法 13  
2.2.1 编码 13  
2.2.2算法流程 13  
2.2.3算法参数 13  
2.2.420 次随机实验的统计结果 13  
2.2.5一次实验结果 13  
3算法特点 17  
3.1 SA 17  
3.2 GA 17  
4TSP 可视化应用程序 17  
5实验分工 18

2TSP 问 题

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

2.1SA 算 法  
2.1.1算法流程  
算法流程与上文基本类似，不同之处在于：  
步骤 1 中，初始温度可以有两种生成方式：按照经验设定固定初温要更大，随机选择指定数量计算方差时指定的元素数目也大得多；初始解在离散的 TSP 问题中为旅行商所经城市的路线。  
步骤 4 为状态更新，在 TSP 问题中，可以通过进行两位置元素交换、两位置之间的元素逆序、把指定某一段序列插到第三个位置之后或者把上述操作按照概率混合的方法产生新的状态， 即新的旅行商路线。

2.1.220 次随机实验的统计结果  
1)30 个城市：  
最短距离为 423.74，0.7-3.6s 可找到最优解。  
如图12，从上到下依次指定外循环迭代 100 次、内循环迭代 200 次；外循环迭代 100 次、  
内循环迭代 400 次；外循环迭代 200 次、内循环迭代 400 次；外循环迭代 200 次、内循环迭代  
500 次，所有参数的设置见图像12左半部分。

在外循环迭代 100 次、内循环迭代 200 次中，虽然随机 20 次实验中能够找到最优解（距离 423.741）, 但从图中可以看出这样的次数并不多，且距离方差很大。增大内循环迭代次数到400，明显在 20 次实验中找到最优解的次数增加，距离方差也变小很多。  
在外循环迭代 200 次、内循环迭代 400 次中，20 次随机试验中能够找到最优解的次数高于  
外循环迭代 100 次、内循环迭代 400 次；而将内循环迭代次数继续提高到 500 次时，性能又有了明显提升——最差距离与最优解仅仅相差不到 2 个单位，方差迅速降低到 0.24。  
上述实验说明，在一定范围之内提高迭代次数有利于提升性能，但迭代次数设置得是否合理，是需要结合初始温度来进行考虑。迭代次数越多耗时越长，需要在性能与耗时方面做出权衡。  
2)50 个城市：  
最短距离为 428.10，0.9-9.6s 内可找到最优解。  
如图13，参数设置与 30 个城市基本相同，仅改变内外循环次数进行实验。从上到下依次为  
外循环 100 次、内循环 200 次；外循环 100 次、内循环 400 次；外循环 200 次、内循环 400 次；  
外循环 200 次、内循环 1000 次。图中右半部分为 20 次实验中的最优路径，均没有发生路径交叉。随着迭代次数的增加，搜寻到的最短路径在减小，平均搜寻路径和方差也在减小，运行时间在增加。但由于状态更新的随机性，有时候未必能够得到性能优化。  
2)75 个城市：  
最短距离为 544.20，37-173s 内可找到最优解。  
如图14，从上到下依次为初始温度 700、外循环迭代 200 次、内循环迭代 3000 次；初始温度 700、外循环迭代 200 次、内循环迭代 5000 次; 初始温度 700，温度收敛到 1e-5、内循环迭代 5000 次。图中左侧为 20 次实验所得结果，右图为每 20 次实验的最短路径。到了 75 个城市时，使用之前的参数已经无法获取最优解，本文转载自http://www.biyezuopin.vip/onews.asp?id=15254因此需要进行参数调整。为了增加搜寻的路径范围， 此时设置的参数值较 TSP30、TSP50 有大幅度增加。尽管如此，搜寻到最优解的概率仍然很小， 运行多次也只能得到一次 544.20，连 546、547、548 这样的数值都很少能够搜寻得到。  
4) 总结：  
在 50 个城市与 75 个城市中，由于城市较多，形成闭合路径的方法有很多，此时已经无法  
通过目测来判断每 20 次实验的最优解是否为最短路径。增加内循环次数的本质是在状态转换概率没有太大改变的情况下增加尝试的路径，以便尽可能覆盖较优解。增加外循环次数的本质是改变解的跳转概率，能够跳出局部最优，继续寻找全局最优解。  
随着城市数量的增加，问题的复杂度变得很高，每次实验的运行时间变得很长，更难以搜寻到最优解，也无法通过肉眼判断是否搜寻到了最优，因为每次实验的路径都没有出现交叉。如图15，随着问题规模的增长，距离开始明显下降的迭代次数开始上升 (TSP30 在 25 前后，TSP50 在 30-40 之间，TSP75 在 30-40 之间)，距离趋向于收敛的次数也在上升 (TSP30 在 50 之前， TSP50 在 50-60 之间，TSP75 大于 60)。说明盲目增大外循环迭代次数意义不大。问题规模对于 SA 算法的影响很大，在较复杂的问题下，SA 性能并不算理想；中小规模下 SA 算是一种兼顾了时间和性能的算法。  
![在这里插入图片描述][f46ba4fde56c4d3e886abf4745b41bd7.png_pic_center]  
![在这里插入图片描述][fa11227d20474528bc5c4696edc87c85.png_pic_center]  
![在这里插入图片描述][7f72d583f0e24d60bc0fc58d73190b9f.png_pic_center]  
![在这里插入图片描述][9d2978a4456642af815631efded009a9.png_pic_center]  
![在这里插入图片描述][0642193414464e5b9d9aadacc1ce6594.png_pic_center]  
![在这里插入图片描述][fc9fd5d5b8ef41cc98d510c9d0f73991.png_pic_center]  
![在这里插入图片描述][e4e70584997f489f882b9d8dfca9142d.png_pic_center]  
![在这里插入图片描述][242fd24c3e6b4551b818351c3447f12b.png_pic_center]  
![在这里插入图片描述][0ceb8ab4654a4f829b6d5706709c1bbc.png_pic_center]  
![在这里插入图片描述][c6c3847d58b948ae9cca66a4aff74dcc.png_pic_center]  
![在这里插入图片描述][60d5d3e9a9e34c2885f16c28812d5483.png_pic_center]

[f46ba4fde56c4d3e886abf4745b41bd7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/fc9a1424a3354654b181d560ba86989d.png
[fa11227d20474528bc5c4696edc87c85.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/61201daf84d34f118c0d68af302c2c1f.png
[7f72d583f0e24d60bc0fc58d73190b9f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/f27ba135e9184929accc1b18359537da.png
[9d2978a4456642af815631efded009a9.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/b48cf9aa2cd44999b604299e3713a843.png
[0642193414464e5b9d9aadacc1ce6594.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/cd73332edca54ae0a9308d1ccdf0dc69.png
[fc9fd5d5b8ef41cc98d510c9d0f73991.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/2058cb1938174c0899b4d319b7f91092.png
[e4e70584997f489f882b9d8dfca9142d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/82038aca99214a8bbd1ec3a63b664844.png
[242fd24c3e6b4551b818351c3447f12b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/f1a07a4517fb4fe59f7380f44e82caaf.png
[0ceb8ab4654a4f829b6d5706709c1bbc.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/c58838ec2a7f49bfad5faafc1483837c.png
[c6c3847d58b948ae9cca66a4aff74dcc.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/523bf75d88ba4ce28060826b547fe6d6.png
[60d5d3e9a9e34c2885f16c28812d5483.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/07e82342cd02403c9fc3152fb6aacead.png