DOI: 10.5281/zenodo.7851754
title: Experiments with Frequency Fitness Assignment based Algorithms on the Traveling Salesperson Problem

description: <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&lt;=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] &lt;= 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.