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

1. Introduction

The implementation and experimental results of the (1+1) EA with and without Frequency Fitness Assignment (FFA) to solve the EUC_2D Traveling Salesperson Problem (TSP) instances from TSPLIB.

A TSP is defined by a fully-connected weighted graph of n 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 x of the numbers 1 to n, each identifying a city. If a city appears at index j in the permutation x, then it will be the jth city to be visited. This means that a tour x will pass the following edges: (x[1], x[2]), (x[2], x[3]), (x[3], x[4]), … (x[n-1], x[n]), (x[n], x[1]).

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 xc and computes its length yc=f(xc). In each iteration, it applies a unary search operator op to obtain a new tour xn=op(xc) and computes its length yn=f(xn). If yn<=yc, then it will accept the new tour and set xn=xn and yc=yn.

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 H which counts, for any tour length y, how often it has been seen during the search so far. After the new tour xn is created and its objective value yn is computed, the (1+1) FEA sets H[yc] = H[yc] + 1 and H[yn] = H[yn] + 1. It will accept xn if and only if H[yn] <= H[yc] and, only in this case, set xn=xn and yc=yn.

We apply both EAs with two operators. swap exchanges two randomly chosen cities in the permutation. reverse reverses a randomly chosen subsequence of the tour.

2. Directory Structure

This archive contains the following directories:

results_and_evaluation contain the results of two experiments as well as their evaluation.

performance contains the results and evaluation of the main experiment, namely the 21 runs on 18 EUC_2D Traveling Salesperson Problem (TSP) instances from TSPLIB.

results is the directory with the log files

evaluation is a folder with the extracted evaluation and figures

evaluation.py is a Python script that generates all the files in evaluation from the data it finds in results. It requires the moptipy package being installed for running.

H contains the results of the experiment conducting single runs on the instances and gathering the data of the frequency table H at different objective function evaluations in the log files.

results is the directory with the log files

evaluation is a folder with the extracted evaluation and figures

evaluation.py is a Python script that generates all the files in evaluation from the data it finds in results. It requires the moptipy package being installed for running.

source contains the Python source codes needed to run the performance experiment.

moptipy is a local copy of the moptipy package used for our experiment.

tsplib contains the TSPLIB data. This includes the instances used in our experiments as files in text format with suffix .tsp. If an optimal tour is given, it is stored in a text format file with suffix .opt.tour and name prefix identical to the instance file. In other words, the file eil51.tsp contains the TSP instance eil51 and the file eil51.opt.tour 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 tsp95.pdf documenting them. We further include the TSPLIB FAQ both as HTML and PDF file (tsplib_faq.html and tsplib_faq.pdf) and the list of known optimal tour lengths as HTML and PDF file (optimal_tour_lengths_of_symmetric_tsps.html, optimal_tour_lengths_of_symmetric_tsps.pdf). Notice that, while the TSP instances we used are Euclidean, all distances are converted to integers as prescribed by the documentation.

3. What algorithms are included in this experiment?

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 n cities, which encodes each solution as a permutation of the numbers 1..n. The value i at position j, i.e., x[j] = i, in such a permutation indicates that the jth city to be visited by i. We implement two search operators, namely reverse, which reverses a subsequence of the tour, and swap which swaps two cities.

(1+1) EA

with swap operator

with reverse operator

(1+1) FEA, i.e., the (1+1) EA with Frequency Fitness Assignment (FFA)

with swap operator

with reverse operator

4. How to Run the Experiment

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:

pip install matplotlib numba numpy pandas psutil scikit-learn

Now enter the source directory, i.e., the directory containing the run.py file, in your terminal. Depending on your system configuration and whether you run Windows or Linux, you can start the program with one of the commands below. (If running the first command returns with an error, just try the next one in the list.)

python3 -m run

python -m run

python run.py

python3 run.py

Then the experiment will run. It will automatically create a sub-folder results in source 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 moptipy package for implementing its algorithms, running the experiments, and gathering their results. If you want to install moptipy on your system instead of using the version supplied here, you can install it via pip install moptipy.

5. Literature

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. 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. 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. IEEE Transactions on Evolutionary Computation (IEEE-EC) 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 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.

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.

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.

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. Artificial Intelligence Review, 13(2):129–170, April 1999. Kluwer Academic Publishers, The Netherlands. doi:10.1023/A:1006529012972.

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/.

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. IEEE Computational Intelligence Magazine (CIM) 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. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley Interscience. 1985.

David Lee Applegate, Robert E. Bixby, Vasek Chvatal, and William John Cook. The Traveling Salesman Problem: A Computational Study. Princeton University Press. 2007.

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.

Software:

The Metaheuristic Optimization in Python Package moptipy

6. License

The files in this repository are under the Creative Commons Attribution 4.0 International, with the exception of the files of TSPLIB in directory source/tsplib, 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 LICENSE in this archive.