代码 | 自适应大邻域搜索系列之(1) - 使用ALNS代码框架求解TSP问题

前言

上次我们详细介绍了邻域搜索的各种概念，尤其是LNS和ALNS的具体过程。大家都理解了吗？

小编相信大家已经掌握了。不过，有热心网友表示上次没有代码，觉得不过瘾~别急，代码会让你们大饱眼福的……

由于ALNS的代码量庞大，小编计划将其做成一个系列，逐步为大家讲解，让大家彻底掌握这个算法框架的代码。

今天我们先不讲解代码，而是教大家如何使用ALNS框架来求解TSP问题。

01 环境准备

小编的演示基于Windows 10 x64位环境（Linux用户会更简单），其他Windows环境也类似。在此之前，我们需要配置几个东西。

1.1 安装MinGW

单独安装MinGW比较麻烦，但安装devC++会自带MinGW，非常方便。没有安装devC++的朋友请在留言区获取安装包下载链接。

下载并安装后，在电脑上找到devC++的安装位置，将其目录下的MinGW64\bin文件添加到环境变量中。如下图所示：

打开cmd命令行，输入以下命令：mingw32-make。如果出现下面的提示，说明安装成功。

2.1 下载源代码

请在留言区下载源代码，然后解压到某个位置（路径不要包含中文）。

2.2 修改源代码

找到\trunk\src\alns下的OperatorManager.cpp：

打开，在头文件位置加入以下代码，禁用调试模式：

代码小浣熊

代码小浣熊是基于商汤大语言模型的软件智能研发助手，覆盖软件需求分析、架构设计、代码编写、软件测试等环节

51

查看详情

2.3 编译

在命令行下进入\trunk\Release目录，首先输入mingw32-make clean，清理以前编译的中间文件。

然后输入：mingw32-make。进行编译。

得到我们的目标文件：libALNS-framework.so。这是ALNS框架的动态链接库，我们稍后会用到。

可以在该目录下看到：

在命令行下进入\trunk\examples\tsp，将main.cpp替换为小编修改好的main.cpp。

然后照例：首先输入mingw32-make clean，清理以前编译的中间文件。

然后输入：mingw32-make。进行编译。

最终得到我们的程序TSP.exe。还有一步，把刚刚编译好的libALNS-framework.so文件复制到当前目录，TSP程序运行需要用到它。

最后在命令行下输入TSP，运行我们的程序：

至此，已经完成。最后说一下，修改的代码是用于求解Berlin52问题的。如果需要求解其他TSP问题，只需在小编修改好的main.cpp文件中更改城市坐标和CITY_SIZE，然后重新编译tsp文件夹中的内容即可。

最优解是7542，这里得到的解比7542少，是因为代码在计算总距离时没有加上第一个和最后一个城市的距离。

03 小结

最后再多说两句，上述求解的代码是根据ALNS框架定制的。其实，大家想用ALNS算法求解任何问题，只需要对框架内容进行相应的定制即可。在接下来的几篇文章中，小编将详细解析ALNS代码框架的内容，并讲解上述求解TSP例子的代码定制内容。敬请期待我们后续的文章吧~

以上就是代码 | 自适应大邻域搜索系列之(1) - 使用ALNS代码框架求解TSP问题的详细内容，更多请关注php中文网其它相关文章！