Experiments with Frequency Fitness Assignment based Algorithms on the Traveling Salesperson Problem
收藏资源简介：
<strong>1. Introduction</strong> In this archive, we provide the implementation and experimental results of eight different algorithms to solve the <code>EUC_2D</code> Traveling Salesperson Problem (TSP) instances from TSPLIB. A TSP is defined by a fully-connected weighted graph of <code>n</code> cities. The goal is to find the overall shortest tour that visits each cities exactly once and returns to its starting point. The TSP is NP-hard. We consider 18 symmetric Euclidean instances from the well-known TSPLIB. Solutions in our work are stored in the path representation, where such a tour is encoded as a permutation <code>x</code> of the numbers <code>1</code> to <code>n</code>, each identifying a city. If a city appears at index <code>j</code> in the permutation <code>x</code>, then it will be the <code>j</code><sup>th</sup> city to be visited. This means that a tour <code>x</code> will pass the following edges: <code>(x[1], x[2])</code>, <code>(x[2], x[3])</code>, <code>(x[3], x[4])</code>, … <code>(x[n-1], x[n])</code>, <code>(x[n], x[1])</code>. <strong>2. Directory Structure</strong> This archive contains the following directories: <code>source</code> contains the Python source codes needed to run the experiment. <code>moptipy-main</code> is a local copy of the <code>moptipy</code> package used for our experiment. <code>tsplib</code> contains the TSPLIB data. This includes the instances used in our experiments as files in text format with suffix <code>.tsp</code>. If an optimal tour is given by TSPLib, it is stored in a text format file with suffix <code>.opt.tour</code> and name prefix identical to the instance file. In other words, the file <code>eil51.tsp</code> contains the TSP instance <code>eil51</code> and the file <code>eil51.opt.tour</code> contains the corresponding optimal tour. Both the TSP instances and optimal tours can be downloaded from http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/. We also include the documentation of TSPLIB in file <code>tsp95.pdf</code> documenting them. We further include the TSPLIB FAQ both as HTML and PDF file (<code>tsplib_faq.html</code> and <code>tsplib_faq.pdf</code>) and the list of known optimal tour lengths as HTML and PDF file (<code>optimal_tour_lengths_of_symmetric_tsps.html</code>, <code>optimal_tour_lengths_of_symmetric_tsps.pdf</code>). Notice that, while the TSP instances we used are Euclidean, all distances are converted to integers as prescribed by the documentation. <code>results</code> is the directory with the log files. Each log file contains information of one run, i.e., one execution of one algorithm on one problem instance. All improving moves of a run as well as the final solution are stored in the log file. The direct sub-folders <code>results</code> represent the algorithms and contain one folder per TSP instance, which, in turn, contain the log files. <code>evaluation</code> is a folder with the extracted evaluation and figures <code>evaluation_edited</code> is a folder with evaluation figures slightly edited for better visual appeal (but obviously without changing any result / scientific content) <code>evaluator</code> is a folder with a Python script <code>main.py</code> that generates all the files in <code>evaluation</code> from the data it finds in <code>results</code>. It requires the <code>moptipy</code> package being installed for running in the version given in <code>requirements.txt</code>. <strong>3. Algorithms</strong> The (1+1) EA is the most basic evolutionary algorithm and also be considered as a randomized local search. It starts with one random solution/permutation <code>xc</code> and computes its length <code>yc=f(xc)</code>. In each iteration, it applies a unary search operator <code>op</code> to obtain a new tour <code>xn=op(xc)</code> and computes its length <code>yn=f(xn)</code>. If <code>yn<=yc</code>, then it will accept the new tour and set <code>xn=xn</code> and <code>yc=yn</code>. The results of this algorithm are given in folder <code>results/ea_revn</code>. FFA is a fitness assignment process that takes place before this last step in the EA. We integrate FFA into the (1+1) EA and obtain the (1+1) FEA. This algorithm uses an additional table <code>H</code> which counts, for any tour length <code>y</code>, how often it has been seen during the search so far. After the new tour <code>xn</code> is created and its objective value <code>yn</code> is computed, the (1+1) FEA sets <code>H[yc] = H[yc] + 1</code> and <code>H[yn] = H[yn] + 1</code>. It will accept <code>xn</code> if and only if <code>H[yn] <= H[yc]</code> and, only in this case, set <code>xn=xn</code> and <code>yc=yn</code>. The results of this algorithm are given in folder <code>results/fea_revn</code>. SA is the classical simulated annealing algorithm. In our experiment, it will accept the new solution <code>xn</code> with probability <code>P</code>. If the new solution is better, the acceptance probability <code>P</code> is 1. For worse solutions, the probability is between 0 and 1, i.e., sometimes, worse solution are also accepted. This algorithm has a temperature cooling schedule. It starts at an initial temperature and over time, the temperature decreases. The probability <code>P</code> of accepting the worse solution depends on the temperature and decreases as well. The results of this algorithm are given in folder <code>results/sa_revn</code>. An FFA-based version of SA uses the frequency fitness instead of the objective values in all acceptance decisions. The results of this algorithm are given in folder <code>results/fsa_revn</code>. EAFEA(A) is a hybrid which alternates between the EA and the FEA and copies a solution from the FEA to the EA if it has an entirely new objective value, i.e., if <code>H[yn] = 1</code>. The results of this algorithm are given in folder <code>results/eafea2_revn</code>. SAFEA(A) is a hybrid which alternates between the SA and the FEA and copies a solution from the FEA to the SA if it has an entirely new objective value, i.e., if <code>H[yn] = 1</code>. The results of this algorithm are given in folder <code>results/safea2_revn</code>. EAFEA(B) is a hybrid which alternates between the EA and the FEA and copies a solution from the FEA to the EA part if it has a better objective value. The results of this algorithm are given in folder <code>results/eafea_revn</code>. SAFEA(B) is a hybrid which alternates between the SA and the FEA and copies a solution from the FEA to the SA part if it has a better objective value. The results of this algorithm are given in folder <code>results/safea_revn</code>. We apply all algorithms with the same unary operator <code>reverse</code>, which reverses a randomly chosen subsequence of the tour. This operator is also often called a "2-opt move". It has the advantage that the new objective value of a new solution can be computed in O(1) if the objective value of the solution from which it is derived is known. <strong>4. How to Run the Experiment</strong> First, you need to make sure to have all the dependencies installed that this program requires. You can do this by executing the following command in the terminal: <code>pip install matplotlib numba numpy psutil scikit-learn</code> Now enter the <code>source</code> directory, i.e., the directory containing the <code>run.py</code> file, in your terminal. Depending on your system configuration and whether you run Windows or Linux, you can start the program with <em>one</em> of the commands below. (If running the first command returns with an error, just try the next one in the list.) <code>python3 -m run</code> <code>python -m run</code> <code>python run.py</code> <code>python3 run.py</code> Then the experiment will run. It will automatically create a sub-folder <code>results</code> in <code>source</code> and place all log files that are generated into it. Be careful: The experiment will take a long time. However, if you have multiple CPUs, you can simply start several instances of this program in independent terminals. Each instance will then conduct different runs. This also works if this folder is shared over the network, in which case you can run multiple processes on multiple PCs. Side note: This experiment uses the <code>moptipy</code> package for implementing its algorithms, running the experiments, and gathering their results. If you want to install <code>moptipy</code> on your system instead of using the version supplied here, you can install it via <code>pip install moptipy</code>. <strong>5. Literature</strong> Frequency Fitness Assignment (FFA): Thomas Weise, Zhize Wu, Xinlu Li, Yan Chen, and Jörg Lässig. Frequency Fitness Assignment: Optimization without Bias for Good Solutions can be Efficient. IEEE Transactions on Evolutionary Computation (TEVC). 2022. Early Access. doi:10.1109/TEVC.2022.3191698. Thomas Weise, Zhize Wu, Xinlu Li, and Yan Chen. Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function Value. <em>IEEE Transactions on Evolutionary Computation</em> 25(2):307–319. April 2021. Preprint available at arXiv:2001.01416v5 [cs.NE] 15 Oct 2020. doi:10.1109/TEVC.2020.3032090. Experimental results and source code are available at doi:10.5281/zenodo.3899474. Tianyu Liang, Zhize Wu, Jörg Lässig, Daan van den Berg, and Thomas Weise. Solving the Traveling Salesperson Problem using Frequency Fitness Assignment. In Hisao Ishibuchi, Chee-Keong Kwoh, Ah-Hwee Tan, Dipti Srinivasan, Chunyan Miao, Anupam Trivedi, and Keeley A. Crockett, editors, Proceedings of the IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI'22), part of the IEEE Symposium Series on Computational Intelligence (SSCI 2022). December 4–7, 2022, Singapore, pages 360–367. IEEE. doi:10.1109/SSCI51031.2022.10022296. Thomas Weise, Mingxu Wan, Ke Tang, Pu Wang, Alexandre Devert, and Xin Yao. Frequency Fitness Assignment. <em>IEEE Transactions on Evolutionary Computation (IEEE-EC)</em> 18(2):226-243, April 2014. doi:10.1109/TEVC.2013.2251885. Thomas Weise, Xinlu Li, Yan Chen, and Zhize Wu. Solving Job Shop Scheduling Problems Without Using a Bias for Good Solutions. In <em>Genetic and Evolutionary Computation Conference Companion (GECCO'21 Companion),</em> July 10-14, 2021, Lille, France. ACM, New York, NY, USA. ISBN 978-1-4503-8351-6. doi:10.1145/3449726.3463124. Thomas Weise, Yan Chen, Xinlu Li, and Zhize Wu. Selecting a diverse set of benchmark instances from a tunable model problem for black-box discrete optimization algorithms. <em>Applied Soft Computing Journal (ASOC)</em>, 92:106269, June 2020. doi:10.1016/j.asoc.2020.106269. Thomas Weise, Mingxu Wan, Ke Tang, and Xin Yao. Evolving Exact Integer Algorithms with Genetic Programming. In <em>Proceedings of the IEEE Congress on Evolutionary Computation (CEC'14), Proceedings of the 2014 World Congress on Computational Intelligence (WCCI'14)</em>, pages 1816-1823, Beijing, China, July 6-11, 2014. Los Alamitos, CA, USA: IEEE Computer Society Press. ISBN: 978-1-4799-1488-3. doi:10.1109/CEC.2014.6900292. Traveling Salesperson Problem (TSP): Pedro Larrañaga, Cindy M. H. Kuijpers, Roberto H. Murga, I. Inza, and S. Dizdarevic. Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. <em>Artificial Intelligence Review,</em> 13(2):129–170, April 1999. Kluwer Academic Publishers, The Netherlands. doi:10.1023/A:1006529012972. Gerhard Reinelt. TSPLIB — A Traveling Salesman Problem Library. <em>ORSA Journal on Computing</em> 3(4):376-384. 1991. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/. Gerhard Reinelt. TSPLIB95. 1995. Heidelberg, Germany: Universität Heidelberg, Institut für Angewandte Mathematik. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf. Thomas Weise, Raymond Chiong, Ke Tang, Jörg Lässig, Shigeyoshi Tsutsui, Wenxiang Chen, Zbigniew Michalewicz, and Xin Yao. Benchmarking Optimization Algorithms: An Open Source Framework for the Traveling Salesman Problem. <em>IEEE Computational Intelligence Magazine (CIM)</em> 9(3):40-52, August 2014. doi:10.1109/MCI.2014.2326101. Eugene Leighton Lawler, Jan Karel Lenstra, Alexander Hendrik George Rinnooy Kan, and David B. Shmoys. <em>The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization.</em> Wiley Interscience. 1985. David Lee Applegate, Robert E. Bixby, Vasek Chvatal, and William John Cook. <em>The Traveling Salesman Problem: A Computational Study.</em> Princeton University Press. 2007. Gregory Z. Gutin and Abraham P. Punnen, editors. <em>The Traveling Salesman Problem and its Variations.</em> Volume 12 of Combinatorial Optimization. Kluwer Academic Publishers. 2002. doi:10.1007/b101971. Software: The Metaheuristic Optimization in Python Package <code>moptipy</code> <strong>6. License</strong> The files in this repository are under the Creative Commons Attribution 4.0 International, with the exception of the files of TSPLIB in directory <code>source/tsplib</code>, which are under copyright of their respective owner (we believe that they are in the public domain, as they are provided by many sources, included in many software packages under various open source licenses, and on many websites). The license is contained as file <code>LICENSE.txt</code> in this archive. <strong>7. Contact</strong> If you have any questions or suggestions, please contact Mr. Tianyu LIANG (梁天宇) of the Institute of Applied Optimization (应用优化研究所, IAO) of the School of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University (合肥学院) in Hefei, Anhui, China (中国安徽省合肥市) via email to liangty@stu.hfuu.edu.cn.
1. 引言 本数据集档案提供了8种不同算法的实现与实验结果，用于求解TSPLIB（Traveling Salesman Problem Library，旅行商问题库）中的EUC_2D旅行商问题（EUC_2D Traveling Salesperson Problem, TSP）实例。旅行商问题（TSP）由包含`n`个城市的全连接加权图定义，目标是找到一条遍历每个城市恰好一次并返回起点的最短总行程。TSP属于NP难问题（NP-hard）。本研究选用了知名TSPLIB中的18个对称欧几里得实例。本研究中的解采用路径表示（path representation）存储：一条行程被编码为1到`n`的排列（permutation）`x`，每个数字对应一个城市。若城市在排列`x`中的索引为`j`，则该城市为第`j`个被访问的城市。即行程`x`将依次经过如下边：`(x[1], x[2])`、`(x[2], x[3])`、`(x[3], x[4])`、……`(x[n-1], x[n])`、`(x[n], x[1])`。 2. 目录结构 本数据集档案包含如下目录： - `source`：存放运行实验所需的Python源代码。 - `moptipy-main`：本实验所用`moptipy`包的本地副本。 - `tsplib`：存放TSPLIB数据集，包含本实验使用的所有实例，均为后缀为`.tsp`的文本格式文件。若TSPLIB提供了某实例的最优行程，则其存储于后缀为`.opt.tour`的文本文件中，且文件名前缀与对应实例文件一致。例如，`eil51.tsp`包含TSP实例`eil51`，而`eil51.opt.tour`则包含其对应的最优行程。TSP实例与最优行程均可从 http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/ 下载。本档案还包含TSPLIB的官方文档`tsp95.pdf`，以及TSPLIB常见问题解答（FAQ）的HTML与PDF版本（`tsplib_faq.html`和`tsplib_faq.pdf`），还有已知对称TSP最优行程长度列表的HTML与PDF版本（`optimal_tour_lengths_of_symmetric_tsps.html`和`optimal_tour_lengths_of_symmetric_tsps.pdf`）。请注意：尽管本研究使用的TSP实例为欧几里得型，所有距离均已按照文档要求转换为整数。 - `results`：存放日志文件的目录。每个日志文件对应一次算法运行，即单算法在单问题实例上的一次执行。运行过程中的所有改进步骤与最终解均存储于日志文件中。`results`的直接子目录对应不同算法，每个子目录下又包含对应每个TSP实例的文件夹，其中存放该算法在该实例上运行的日志文件。 - `evaluation`：存放提取后的评估结果与可视化图表的目录。 - `evaluation_edited`：存放经过小幅美化的评估图表的目录（仅优化视觉效果，未更改任何结果或科学内容）。 - `evaluator`：包含Python脚本`main.py`的目录，该脚本可从`results`目录读取数据并生成`evaluation`目录下的所有文件。运行该脚本需要安装`requirements.txt`中指定版本的`moptipy`包。 3. 算法 (1+1)进化算法（(1+1) Evolutionary Algorithm, (1+1) EA）是最基础的进化算法，也可视为随机局部搜索算法。该算法从一个随机解/排列`xc`开始，计算其行程长度`yc=f(xc)`。在每次迭代中，它通过一元搜索算子（unary search operator）`op`生成新行程`xn=op(xc)`，并计算其长度`yn=f(xn)`。若`yn≤yc`，则接受新行程，并将`xc`更新为`xn`、`yc`更新为`yn`。该算法的实验结果存储于`results/ea_revn`目录中。 频率适应度分配（Frequency Fitness Assignment, FFA）是一种在进化算法最后一步前执行的适应度分配机制。我们将FFA集成至(1+1) EA中，得到(1+1) FEA。该算法使用额外的统计表`H`，用于记录搜索过程中各行程长度`y`的出现次数。在生成新行程`xn`并计算其目标值`yn`后，(1+1) FEA会执行`H[yc] = H[yc] + 1`与`H[yn] = H[yn] + 1`。当且仅当`H[yn] ≤ H[yc]`时，算法接受新行程，并更新`xc`与`yc`。该算法的实验结果存储于`results/fea_revn`目录中。 SA即经典模拟退火算法（Simulated Annealing, SA）。在本实验中，算法以概率`P`接受新解`xn`：若新解更优，则接受概率`P=1`；若新解更差，则接受概率介于0到1之间，即算法有时也会接受更差的解。该算法带有温度冷却进度表（temperature cooling schedule），从初始温度开始随时间降低温度，接受更差解的概率`P`也会随温度降低而减小。该算法的实验结果存储于`results/sa_revn`目录中。 基于FFA的SA版本在所有接受决策中使用频率适应度而非目标值。该算法的实验结果存储于`results/fsa_revn`目录中。 EAFEA(A)是一种混合算法，在EA与FFA之间交替运行：若新解的目标值为全新值（即`H[yn]=1`），则将该解从FFA复制至EA。该算法的实验结果存储于`results/eafea2_revn`目录中。 SAFEA(A)是一种混合算法，在SA与FFA之间交替运行：若新解的目标值为全新值（即`H[yn]=1`），则将该解从FFA复制至SA。该算法的实验结果存储于`results/safea2_revn`目录中。 EAFEA(B)是一种混合算法，在EA与FFA之间交替运行：若新解的目标值更优，则将该解从FFA复制至EA模块。该算法的实验结果存储于`results/eafea_revn`目录中。 SAFEA(B)是一种混合算法，在SA与FFA之间交替运行：若新解的目标值更优，则将该解从FFA复制至SA模块。该算法的实验结果存储于`results/safea_revn`目录中。 本研究为所有算法采用了相同的一元搜索算子`reverse`，该算子会反转行程中随机选取的子序列，也常被称为2-opt移动（2-opt move）。该算子的优势在于：若已知原解的目标值，则新解的目标值可在O(1)时间内计算得到。 4. 如何运行实验 首先需确保安装了本程序所需的所有依赖项，可通过在终端执行如下命令完成： `pip install matplotlib numba numpy psutil scikit-learn` 随后进入`source`目录（即包含`run.py`文件的目录）。根据系统配置与操作系统（Windows或Linux），可通过以下命令之一启动程序（若第一条命令报错，请尝试列表中的下一条）： `python3 -m run` `python -m run` `python run.py` `python3 run.py` 启动后实验将自动运行，并会在`source`目录下自动创建`results`子目录，所有生成的日志文件均会存入该目录。请注意：本实验耗时较长。但若您拥有多核CPU，可在多个独立终端中同时启动多个程序实例，每个实例将执行不同的运行任务。若该目录通过网络共享，该方法同样适用，此时可在多台PC上同时运行多个进程。 补充说明：本实验使用`moptipy`包实现算法、运行实验并收集结果。若您希望自行安装`moptipy`而非使用本档案提供的版本，可通过`pip install moptipy`命令安装。 5. 参考文献 ### 频率适应度分配（FFA）相关文献 1. Thomas Weise, Zhize Wu, Xinlu Li, Yan Chen, and Jörg Lässig. Frequency Fitness Assignment: Optimization without Bias for Good Solutions can be Efficient. *IEEE Transactions on Evolutionary Computation (TEVC)*. 2022. Early Access. doi:10.1109/TEVC.2022.3191698. 2. Thomas Weise, Zhize Wu, Xinlu Li, and Yan Chen. Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function Value. *IEEE Transactions on Evolutionary Computation* 25(2):307–319. April 2021. Preprint available at arXiv:2001.01416v5 [cs.NE] 15 Oct 2020. doi:10.1109/TEVC.2020.3032090. 3. 实验结果与源代码可访问 doi:10.5281/zenodo.3899474. 4. Tianyu Liang, Zhize Wu, Jörg Lässig, Daan van den Berg, and Thomas Weise. Solving the Traveling Salesperson Problem using Frequency Fitness Assignment. In Hisao Ishibuchi, Chee-Keong Kwoh, Ah-Hwee Tan, Dipti Srinivasan, Chunyan Miao, Anupam Trivedi, and Keeley A. Crockett, editors, Proceedings of the IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI'22), part of the IEEE Symposium Series on Computational Intelligence (SSCI 2022). December 4–7, 2022, Singapore, pages 360–367. IEEE. doi:10.1109/SSCI51031.2022.10022296. 5. Thomas Weise, Mingxu Wan, Ke Tang, Pu Wang, Alexandre Devert, and Xin Yao. Frequency Fitness Assignment. *IEEE Transactions on Evolutionary Computation (IEEE-EC)* 18(2):226-243, April 2014. doi:10.1109/TEVC.2013.2251885. 6. Thomas Weise, Xinlu Li, Yan Chen, and Zhize Wu. Solving Job Shop Scheduling Problems Without Using a Bias for Good Solutions. In *Genetic and Evolutionary Computation Conference Companion (GECCO'21 Companion),* July 10-14, 2021, Lille, France. ACM, New York, NY, USA. ISBN 978-1-4503-8351-6. doi:10.1145/3449726.3463124. 7. Thomas Weise, Yan Chen, Xinlu Li, and Zhize Wu. Selecting a diverse set of benchmark instances from a tunable model problem for black-box discrete optimization algorithms. *Applied Soft Computing Journal (ASOC)*, 92:106269, June 2020. doi:10.1016/j.asoc.2020.106269. 8. Thomas Weise, Mingxu Wan, Ke Tang, and Xin Yao. Evolving Exact Integer Algorithms with Genetic Programming. In *Proceedings of the IEEE Congress on Evolutionary Computation (CEC'14), Proceedings of the 2014 World Congress on Computational Intelligence (WCCI'14)*, pages 1816-1823, Beijing, China, July 6-11, 2014. Los Alamitos, CA, USA: IEEE Computer Society Press. ISBN: 978-1-4799-1488-3. doi:10.1109/CEC.2014.6900292. ### 旅行商问题（TSP）相关文献 9. Pedro Larrañaga, Cindy M. H. Kuijpers, Roberto H. Murga, I. Inza, and S. Dizdarevic. Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. *Artificial Intelligence Review,* 13(2):129–170, April 1999. Kluwer Academic Publishers, The Netherlands. doi:10.1023/A:1006529012972. 10. Gerhard Reinelt. TSPLIB — A Traveling Salesman Problem Library. *ORSA Journal on Computing* 3(4):376-384. 1991. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/. 11. Gerhard Reinelt. TSPLIB95. 1995. Heidelberg, Germany: Universität Heidelberg, Institut für Angewandte Mathematik. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf. 12. Thomas Weise, Raymond Chiong, Ke Tang, Jörg Lässig, Shigeyoshi Tsutsui, Wenxiang Chen, Zbigniew Michalewicz, and Xin Yao. Benchmarking Optimization Algorithms: An Open Source Framework for the Traveling Salesman Problem. *IEEE Computational Intelligence Magazine (CIM)* 9(3):40-52, August 2014. doi:10.1109/MCI.2014.2326101. 13. Eugene Leighton Lawler, Jan Karel Lenstra, Alexander Hendrik George Rinnooy Kan, and David B. Shmoys. *The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization.* Wiley Interscience. 1985. 14. David Lee Applegate, Robert E. Bixby, Vasek Chvatal, and William John Cook. *The Traveling Salesman Problem: A Computational Study.* Princeton University Press. 2007. 15. Gregory Z. Gutin and Abraham P. Punnen, editors. *The Traveling Salesman Problem and its Variations.* Volume 12 of Combinatorial Optimization. Kluwer Academic Publishers. 2002. doi:10.1007/b101971. ### 软件相关 16. 元启发式优化Python包`moptipy` 6. 许可协议 本档案中的所有文件均采用知识共享署名4.0国际许可协议（Creative Commons Attribution 4.0 International），但`source/tsplib`目录下的TSPLIB文件除外：我们认为该部分文件已进入公有领域，因为它们可从多种来源获取，被众多软件包以各类开源许可证收录，并发布于多个网站。本许可协议的完整内容存储于档案中的`LICENSE.txt`文件。 7. 联系方式 若您有任何疑问或建议，请联系中国安徽省合肥市合肥学院人工智能与大数据学院应用优化研究所（IAO）的梁天宇先生，邮箱：liangty@stu.hfuu.edu.cn。
