Experiments with Frequency Fitness Assignment in a (1+1) EA on the Traveling Salesperson Problem

<strong>1. Introduction</strong> The implementation and experimental results of the (1+1) EA with and without Frequency Fitness Assignment (FFA) 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>^th 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>. 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>. 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>. We apply both EAs with two operators. <code>swap</code> exchanges two randomly chosen cities in the permutation. <code>reverse</code> reverses a randomly chosen subsequence of the tour. <strong>2. Directory Structure</strong> This archive contains the following directories: <code>results_and_evaluation</code> contain the results of two experiments as well as their evaluation. <code>performance</code> contains the results and evaluation of the main experiment, namely the 21 runs on 18 <code>EUC_2D</code> Traveling Salesperson Problem (TSP) instances from TSPLIB. <code>results</code> is the directory with the log files <code>evaluation</code> is a folder with the extracted evaluation and figures <code>evaluation.py</code> is a Python script 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. <code>H</code> contains the results of the experiment conducting single runs on the instances and gathering the data of the frequency table <code>H</code> at different objective function evaluations in the log files. <code>results</code> is the directory with the log files <code>evaluation</code> is a folder with the extracted evaluation and figures <code>evaluation.py</code> is a Python script 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. <code>source</code> contains the Python source codes needed to run the <code>performance</code> experiment. <code>moptipy</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, 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. <strong>3. What algorithms are included in this experiment?</strong> We implement the simple local search with (1+1) EA with and without Frequency Fitness Assignment. We use the common path representation for the TSP with <code>n</code> cities, which encodes each solution as a permutation of the numbers <code>1..n</code>. The value <code>i</code> at position <code>j</code>, i.e., <code>x[j] = i</code>, in such a permutation indicates that the <code>j</code>^th city to be visited by <code>i</code>. We implement two search operators, namely <code>reverse</code>, which reverses a subsequence of the tour, and <code>swap</code> which swaps two cities. (1+1) EA with <code>swap</code> operator with <code>reverse</code> operator (1+1) FEA, i.e., the (1+1) EA with Frequency Fitness Assignment (FFA) with <code>swap</code> operator with <code>reverse</code> operator <strong>4. How to Run the Experiment</strong> First, you must make sure to have all the dependencies installed that this program requires. You can do this by executing the following command in the terminal: <pre><code>pip install matplotlib numba numpy pandas psutil scikit-learn</code></pre> 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, 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. 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. arXiv:2112.00229v4 [cs.NE] 25 May 2022. 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</code> in this archive.