Data for "Frequency Fitness Assignment and the Quadratic Assignment Problem"

In this archive, we provide the complete data and code needed to reproduce the experiments discussed in the paper Frequency Fitness Assignment and the Quadratic Assignment Problem. The Quadratic Assignment Problem (QAP) is one of the most classical combinatorial optimization problems. We investigate the performance of local search, Frequency Fitness Assignment (FFA), Simulated Annealing (SA), and several different hybrid algorithms combining local search with FFA on the QAP. 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 QAP. Therefore, we provide the related versions of these packages in the file libraries.tar.xz, although they are available both on GitHub and PyPI. Just to be sure.

Experiment

The raw data of the experiments can be found in folder results presented compressed as results.tar.xz. This data is quite big. We have over 90'000 files that together make up over 500 MB of data. The folder structure in results 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 trunc, which is provided sources in file eafean_trunc.py. The experiment execution script, experiment.py, can also be found in that folder. With it, 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 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 results folder, you can execute the scripts in the evaluator folder (using again the right version of moptipy and moptipyapps), which are contained in file evaluator.tar.xz. Then this will produce the figures and tables that we are having in the paper. This output is contained in folder evaluation and 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 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 results/fea1p1_swap2.

EAFEA: 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.This is implemented in class EAFEA.The results are in folder results/eafea_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 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 results/eafeaB_swap2.

EAFEAN: The new hybrid algorithm proposed in the article. It combines the RLS and the FRLS in a more efficient fashion.This is implemented in class EAFEAN.The results are in folder results/eafeaN_swap2.

trunc: This is EAFEAN, but with FFA removed.This is implemented in class Trunc in file sources/trunc.py.The results are in folder results/trunc1_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 class ExponentialScheduleBasedOnBounds.The results are in the folders of the format results/sa**_swap2, where ** stands for the different adaptive temperature schedule definitions.

RS: Random sampling creates a new random solution in each step.This is implemented in class RandomSampling.The results are in folder results/rs.

Benchmark Problems

We apply the algorithms to the instances of QAPLIB, which can be found at https://qaplib.mgi.polymtl.ca and are also implemented in moptipyapps

We generally have at least 47 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 47 runs in this case, too, in our evaluation. More precisely, for each problem, we use the data generated by the runs using the same 47 random seeds for each algorithm. We believe that 47 runs are totally enough to draw meaningful conclusions and to do fair comparisons. 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 199 runs, we include those in the archive results.tar.xz. 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 running, we recommend version 0.9.151. 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. To be on the safe side, we included the library in the archive libraries.tar.xz, which unpacks into libraries.

Reproducing the Experiment

We include the following parts of our experiment:

The folder sources (packaged as sources.tar.xz) contains the Python sources needed to run the experiment.

The folder results (packaged as results.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 evaluator (packaged as evaluator.tar.xz) contains the evaluator code. These programs are executed after the experiment completes. They produce the figures and tables in our paper.

The folder 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 sources.tar.xz to some folder, let's call it A.

Open a terminal and cd into folder A/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 experiment.py.

This will automatically create a folder A/results, which will eventually have the same contents as provided by the archive results.tar.xz. Notice, though, that this takes a very long time. We run 100'000'000 FEs per run, 47 runs per setting, for several algorithms, over many problems…

Reproducing the Evaluation Steps

If you either already have the raw data reproduced or have unpacked our results.tar.xz file, 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/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/evaluator, in order to create figures and tables.

If you perform these steps, then the output collected in your folder A/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.