Data for "Benchmarking Permutation-based Encodings and Metaheuristics for the Traveling Tournament Problem"

This dataset is available at doi:10.5281/zenodo.19842646. In this archive, we provide the complete data and code needed to reproduce the experiments discussed in the paper Benchmarking Permutation-based Encodings and Metaheuristics for the Traveling Tournament Problem. The Traveling Tournament Problem (TTP) asks us to organize a tournament where N teams compete with each other in a fair and efficient way. We focus on the double round robin (2RR) flavor of this problem, where each team plays twice against each other team, once at home and once away, i.e., at the stadium of the other team. Here, efficient means to reduce the total travel length summed up over all teams. The fairness aspect is embodied in constraints that prevent any team from having more than three consecutive home and away games, from two teams playing each other twice in a row, and that enforce a compact 2RR schedule. We approach the TTP using two different permutation-based encodings under diverse metaheuristics, ranging from randomized local search (RLS), RLS with Frequency Fitness Assignment (FFA), Simulated Annealing (SA), two hybrid algorithms combining local search with FFA, and NSGA-II. The experiments take a very long time to conduct, so there are several different steps that can be taken separately to reproduce them to different degrees. All the data elements are packaged in files of the format tar.xz. Under Linux, you can unpack them using tar -xf archive.tar.xz where archive is to be replaced with the archive name. Under Windows, you would probably use a tool like WinRAR. We use the moptipy package to run the experiments. For the experiment, we use some algorithms already provided in that package. We use the moptipy-API for them and we also use it to evaluate the raw data generated by the experiments and to create the plots. We use the moptipyapps package, which provides the benchmark instances, data structures, and components needed for the TTP. Therefore, we provide the related versions of these packages in the file software.tar.xz, although they are available both on GitHub and PyPI. Just to be sure. In our paper, we present two experiments. The main "Experiment 1" applies the algorithms to the TTP. The side-dish "Experiment 2" investigates the runtimes and results of the two different encodings. Experiment 1 The raw data of the experiments can be found in folder main/results presented compressed as two files, main_results_1.tar.xz and main_results_2.tar.xz. They contain the data for the first and second encoding, respectively. This data is quite big. We have over 11'000 files that together make up over 80.1 GB of data in total. You can unpack the files and they will create the folders main/results/gameEncoding_1 and main/results/gameEncoding_2, respectively. The folder structure below these root folders follows the pattern algorithm/instance/algorithm_instance_randseed.txt. Since we use moptipy to execute our experiments, the folder structure and the exact structure of the log files, which contain all improving steps that the algorithms too, the algorithm setup, the system configuration, as well as the final best discovered solution, follows the specification given in: T. Weise and Z. WU: Replicable Self-Documenting Experiments with Arbitrary Search Spaces and Algorithms. Genetic and Evolutionary Computation Conference Companion (GECCO'2023) Companion, July 15-19, 2023, Lisbon, Portugal, pages 1891-1899. New York, NY, USA: ACM. doi:10.1145/3583133.3596306. Expanding upon that, we generate all random seeds in a deterministic manner per instance and all algorithms use the same seeds. This makes cheery picking impossible and our experiments can be replicated also using different implementations of algorithms even in different programming languages. The source code of the algorithm implementations is part of moptipy for the algorithms except for the temperature schedule used with SA, which is provided in folder main/sources packaged as main_sources.tar.xz. There are two experiment execution scripts: run_encoding_1.py for the first encoding and run_encoding_2.py for the second encoding. They can also be found in that folder. With them, you can exactly replicate the contents of the results folder (but your log files would contain other time stamps, system configurations, etc.). Be aware that doing this would take a very very long time. The experiment script will execute the runs in a random order. So you could go and start it, wait for some runs to complete, and compare them with the corresponding log files of the same name and path in our main/results folder. Their content, at least the improving steps and final solutions, should be the same. Then you could start the experiment again, get some other runs, and do the same. This way, you can verify that our data is genuine. Of course, you need to have the right version of the open source packages moptipy and moptipyapps for that, which we will describe later on. If you have all the data in the main/results folder, you can execute the scripts in the main/evaluator folder (using again the right version of moptipy and moptipyapps), which are contained in file main_evaluator.tar.xz. Then this will produce the figures and tables that we are having in the paper. This output is contained in folder main/evaluation provided in main_evaluation.tar.xz, but you can also re-create it by yourself. Algorithms The following algorithms are implemented and used in the main experiment: RLS: The randomized local search flips swaps two elements of a permutation. The algorithm is implemented as class RLS. The search operator is given in class Op1Swap2.The results are given in folder main/results/*/rls_swap2. FRLS: The randomized local search algorithm RLS, but using Frequency Fitness Assignment. Using this algorithm is like using RLS above, but we replace class RLS with class FEA1plus1.The results are in folder main/results/*/fea1p1_swap2. EAFEAA: A hybrid algorithm executing the RLS and the FRLS in an alternating fashion: First one objective function evaluation (FE) of the RLS, then one of the FRLS, then again one of the RLS, and so on. If the FRLS discovers a solution with frequency-value 1, it will copy it to the RLS, thereby overwriting this algorithm's current solution.This is implemented in class EAFEAA.The results are in folder main/results/*/eafeaa_swap2. EAFEAB: A hybrid algorithm executing the RLS and the FRLS in an alternating fashion: First one objective function evaluation (FE) of the RLS, then one of the FRLS, then again one of the RLS, and so on. If the FRLS discovers a solution which is better or equally good as the current solution of the RLS-strand, it will copy it to the RLS, thereby overwriting this algorithm's current solution.This is implemented in class EAFEAB.The results are in folder main/results/*/eafeab_swap2. Simulated Annealing (several setups): Several optimized setups of the classical Simulated Annealing, using adaptive temperature schedules.This is implemented in class SimulatedAnnealing. The adaptive temperature schedules are implemented in a class provided directly in the experiment execution scripts previously mentioned.The results are in the folders of the format main/results/*/sa**_swap2, where ** stands for the different adaptive temperature schedule definitions. Benchmark Problems We apply the algorithms to the compact 2RR instances of RobinX, which can be found at https://robinxval.ugent.be/RobinX/travelRepo.php and are also implemented in moptipyapps We generally have at least 2 runs for each algorithm on each benchmark problem. For some problems and algorithm combinations, we have more runs for historical reasons. However, to ensure absolute fairness between the algorithms, we only use 2 runs in this case, too, in our evaluation. More precisely, for each problem, we use the data generated by the runs using the same 2 random seeds for each algorithm. The runs take a long time, since we provide them with a budget of 109 objective function evaluations (FEs). 2 runs are not much, but over all the instances and based on the numerical results, the outcomes are still quite clear. However, for the sake of completeness, for the interested reader, and maybe for our own future work, we include all runs for all algorithms that we have. This means that, if for some algorithm/instance combination we actually have more runs, we include those in the archives main_results_1.tar.xz and main_results_2.tar.xz (depending on to which encoding they belong). Even though they are not used in the evaluation. Using them in the evaluation would also not change the conclusions in any way, as far as we can see here. Still, fairness is fairness and we try to do a good job to be fair here. External Libraries To run and to evaluate our experiments, you need to install the open source library moptipy. For evaluating, you may use a later, more current version. The required library and its dependencies can be installed from PyPI, via pip install moptipy moptipyapps. To be on the safe side, we included the libraries in the archive software.tar.xz, which unpacks into software. We include the current state of the libraries on GitHub, as well as several historical versions that were used in our experiments. Since our experiments span multiple years, the software has developed further — the code design remains such that even the versions today would produce exactly the same results as those used in the experiments. Reproducing the Experiment We include the following parts of our experiment: The folder main/sources (packaged as main_sources.tar.xz) contains the Python sources needed to run the experiment. The folder main/results (packaged as main_results_1.tar.xz and main_results_2.tar.xz) contains the results folder, i.e., all the log files that will be produced if the experiment is executed. If you would run the experiment again, you would get exactly these files, but maybe with different time stamps and different system configuration data. But the objective values/objective function evaluation indices would be exactly the same. Running the experiment takes a long, long time. The folder main/evaluator (packaged as main_evaluator.tar.xz) contains the evaluator code. These programs are executed after the experiment completes. They load the results from the results folder and extract the evaluation-relevant data. They produce the figures and tables in our paper. The folder main/evaluation is the output folder of the evaluator. It contains the figures and tables in our paper. Reproducing the Raw Data / Log Files To reproduce the raw data, you need to perform the following steps. Unpack main_sources.tar.xz to some folder, let's call it A. Open a terminal and cd into folder A/main/sources. Make sure that you have moptipy and moptipyapps of a compatible version installed. If not, you can either do pip install moptipy moptipyapps. Ideally you should do this in a virtual environment. Discussing how to set up virtual environments and install packages in them goes beyond the scope here, so we refer to https://docs.python.org/3/library/venv.html. Run python3 run_encoding_1.py. Stop it when you have sufficiently many runs with the first encoding. Run python3 run_encoding_2.py. Stop it when you have sufficiently many runs with the second encoding. This will automatically create a folder A/main/results, which will eventually have the same contents as provided by the archives main_results_1.tar.xz and main_results_2.tar.xz. Notice, though, that this takes a very long time even for two runs per setting. We run 1'000'000'000 FEs per run, for several algorithms, over many problems… Reproducing the Evaluation Steps If you either already have the raw data reproduced or have unpacked our main_results_1.tar.xz and main_results_2.tar.xz files, then you can reproduce the evaluation. Unpack evaluator.tar.xz to some folder, let's call it A. Open a terminal and cd into folder A/main/evaluator. Make sure that you have moptipy and moptipyapps of a compatible version installed. If not, you can either do pip install moptipy moptipyapps. Ideally you should do this in a virtual environment. Discussing how to set up virtual environments and install packages in them goes beyond the scope here, so we refer to https://docs.python.org/3/library/venv.html. Run the evaluator.py scripts in the folder A/main/evaluator, in order to create figures and tables. If you perform these steps, then the output collected in your folder A/main/evaluation should be exactly the same as the data we provide in archive evaluation.tar.xz. It should contain the figures and tables provided in our paper. Experiment 2 The second experiment in our work is basically structured exactly like the first one. Here, the goal simply is to figure out how long the two different encodings need and how many different solutions they produce. This experiment can be executed and evaluation in about a hour or two. We include the complete experiment in archive encoding.tar.xz which unpacks the folder encoding. Therein are the files needed to execute the experiment (in folder sources), the results/output (in folder results), the scripts to evaluate the results (in folder sources again), and the evaluation result, i.e., data and figures used in our paper (in folder evaluation). To reproduce this experiment, you can follow the steps discussed above for the first experiment.