Data for "When Frequency Fitness Assignment Fails: Trapped States in Frequency-Guided Local Search"

In this archive, we provide the complete data and code needed to reproduce the experiments discussed in the paper When Frequency Fitness Assignment Fails: Trapped States in Frequency-Guided Local Search. These 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. Both the main experiment as well as the supplementary OneMax plots heavily rely on the Python ecosystem. We use the moptipy package to run the experiments. For the experiment, we use some algorithms already provided in that package. However, we also implement some novel algorithms that are not part of it. Either way, we use the moptipy-API for them. moptipy also offers the benchmark problems that we use. It is also used to evaluate the raw data generated by the experiments and to create the plots. Therefore, we provide the related versions of this package in the file libraries.tar.xz, although they are available both on GitHub and PyPI. Just to be sure. Main Experiment The raw data of the experiments can be found in folder experiment/results presented compressed as results.tar.xz. This data is quite big. We have over one million files that together make up 7.3 GiB of data. The folder structure in experiment/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. We test many different scales of the objective functions, which, too, are generated in a deterministic manner, including linear steps, powers of 2 and 3, square numbers, prime numbers, etc. This means that our data can be plotted both on linear and logarithmic scales and will be smooth and that strange effects like symmetries, factorization artifacts etc. are unlikely to occur. Plus cheery picking is 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 either part of moptipy for standard algorithms or given in the folder experiment/sources for our newly proposed methods. The experiment execution script, experiment.py, can also be found in that folder. With it, you can exactly replicate the contents of the experiment/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 experiment/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 package moptipy for that, which we will describe later on. If you have all the data in the experiment/results folder, you can execute the scripts in the experiment/evaluator/evaluator folder (using again the right version of moptipy), which are contained in file evaluator.tar.xz. Then this will produce the exactly same figures and tables that we are having in the paper. This output is contained in folder experiment/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 a single bit in each step.This algorithm is implemented in the package moptipy as class RLS combined with operator Op1Flip1.The results are in folder results/rls_flip1. (1+1) EA: The (1+1) Evolutionary Algorithm flips a binomially distributed number of bits in each step, but always flips at least one bit. This algorithm is implemented in the package moptipy as class RLS combined with operator Op1MoverNflip.The results are in folder results/rls_flipb1.Notice:RLS and the (1+1) EA use the same basic algorithm implementation, namely class RLS, but different search operators (Op1Flip1, which flips exactly one bit, versus Op1MoverNflip, which flips a binomially distributed number l of bits, conditioned that l≥1). Therefore, their folder names both start with rls_, but have different second parts, namely flip1 versus flipb1. The same structure is also true for the other algorithm setups. 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_flip1. (1+1) FEA: The (1+1) EA, but using Frequency Fitness Assignment. Using this algorithm is like using (1+1) EA above, but we replace class RLS with class FEA1plus1. The results are in folder results/fea1p1_flipb1. EAFEAA: A hybrid algorithm executing the (1+1) EA and the (1+1) FEA in an alternating fashion: First one objective function evaluation (FE) of the (1+1) EA, then one of the (1+1) FEA, then again one of the (1+1) EA, and so on. If the (1+1) FEA discovers a solution with frequency-value 1, it will copy it to the (1+1) EA, thereby overwriting this algorithm's current solution.This code is implemented in file sources/eafeaa_my.py.The results are in folder results/eafeaA_flipB1. EAFEAB: A hybrid algorithm executing the (1+1) EA and the (1+1) FEA in an alternating fashion: First one objective function evaluation (FE) of the (1+1) EA, then one of the (1+1) FEA, then again one of the (1+1) EA, and so on. If the (1+1) FEA discovers a solution which is better or equally good as the current solution of the (1+1) EA-strand, it will copy it to the (1+1) EA, thereby overwriting this algorithm's current solution.This code is implemented in file sources/eafeab_my.py.The results are in folder results/eafeaB_flipB1. EAFEAAX: A hybrid algorithm working like EAFEAA, but instead of overwriting the solution upon transfer, it will use uniform crossover to combine the solutions of the EA and FEA strand. The newly synthesized solution is evaluated, consuming one objective function evaluation.This code is implemented in file sources/eafeaaZ.py. Notice that this will produce data folders having a "Z" in the name instead of "X", as we later decided to rename the algorithm.The results are in folder results/eafeaaz_flipb1. EAFEABX: A hybrid algorithm working like EAFEAB, but instead of overwriting the solution upon transfer, it will use uniform crossover to combine the solutions of the EA and FEA strand. The newly synthesized solution is evaluated, consuming one objective function evaluation.This code is implemented in file sources/eafeaaZ.py. Notice that this will produce data folders having a "Z" in the name instead of "X", as we later decided to rename the algorithm.The results are in folder results/eafeabz_flipb1. Benchmark Problems We apply the algorithms to many different discrete benchmarks. OneMax: The minimization version of the problem where the goal is to find the bit string composed of all True bits.The log files for this problem are in the sub-folders onemax_n inside the algorithm folders, where n stands for the number of bits. LeadingOnes: The minimization version of the problem where the goal is to find the bit string composed of all True bits, but only counting the leading true bits.The log files for this problem are in the sub-folders leadingones_n inside the algorithm folders, where n stands for the number of bits. The linear harmonic function is a form of OneMax where each bit has a linear weight.The log files for this problem are in the sub-folders linharm_n inside the algorithm folders, where n stands for the number of bits. The binary integer problem is a form of OneMax where each bit has an exponential weight.The log files for this problem are in the sub-folders binint_n inside the algorithm folders, where n stands for the number of bits. Trap is a maximally deceptive problem.The log files for this problem are in the sub-folders trap_n inside the algorithm folders, where n stands for the number of bits. TwoMax is a problem with two optima, a local and a global one, of about the same size.The log files for this problem are in the sub-folders twomax_n inside the algorithm folders, where n stands for the number of bits. Jump has a deceptive region of w bits around the optimum.The log files for this problem are in the sub-folders jump_n_k inside the algorithm folders, where n stands for the number of bits and k is the jump width. Plateau has a neutral region of w bits around the optimum.The log files for this problem are in the sub-folders plateau_n_k inside the algorithm folders, where n stands for the number of bits and k is the plateau width. The 1-dimensional Ising model has bits arranged in a 1D-ring and neighboring bits of different values are penalized.The log files for this problem are in the sub-folders ising1d_n inside the algorithm folders, where n stands for the number of bits. The 2-dimensional Ising model has bits arranged in a 2D-torus and neighboring bits of different values are penalized.The log files for this problem are in the sub-folders ising2d_n inside the algorithm folders, where n stands for the number of bits and is necessarily a square number. N-Queens aims to arrange N queens on an N*N chess board so that they cannot beat each other.The log files for this problem are in the sub-folders nqueens_n inside the algorithm folders, where n stands for the number of bits and is a square number, namely N*N. The W-Model offers a set of 19 diverse benchmark instances on which algorithms tend to exhibit different behaviors.The log files for this problem are in the sub-folders wmodel_n inside the algorithm folders, where n stands for index of the W-Model instance and NOT the number of bits. LABS aims to find low-autocoerelation binary sequences.The log files for this problem are in the sub-folders labs_n inside the algorithm folders, where n stands for the number of bits. We generally have 99 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 99 runs in this case, too, in our evaluation. More precisely, for each problem, we use the data generated by the runs using the same 99 random seeds for each algorithm. This is ensured by the script fix_data.py during the evaluation, as explained a bit farther down. We believe that 99 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 experiment/sources (packaged as sources.tar.xz) contains the Python sources needed to run the experiment. The folder experiment/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 experiment/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 experiment/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/experiment/sources. Make sure that you have moptipy of a compatible version installed. If not, you can either do pip install moptipy==0.9.151. 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/experiment/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, 99 runs per setting, for several algorithms, over many problems and problem scales… 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/experiment/evaluator/evaluator. Make sure that you have moptipy of a compatible version installed. If not, you can either do pip install moptipy==0.9.166. Notice that that's a different version from what we used for the experiments. The experiments take a long time, so the library has advanced&hellip Anyway, 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 fix_data.py. This script creates the folder A/experiment/evaluation and inside, it creates two CSV files, namely end_results.txt and end_statistics.txt. They are not of much interest here, but they take care of three things: First, they collect the end results from the log files and compute statistics over them, which will later be used in the figures. Second, they also resolve issues such as name cases (Windows is case insensitive, Linux is not) of algorithm and instance names and folders. Third, if you have partial data only or did more runs on some instance/algorithm combinations (the latter is the case for our data), then this script makes sure that all algorithms get the same number of runs / the same seeds for each instance. The additional runs are ignored. This make sure that all comparisons are 100% fair and equal. Run any of the other Python scripts in the folder A/experiment/evaluator/evaluator, in order to create figures and tables. If you perform these steps, then the output collected in your folder A/experiment/evaluation should be exactly the same as the data we provide in archive evaluation.tar.xz. It should be identical to the figures and tables provided in our paper. Reproducing the OneMax Traces The paper draft contains a figure showing the traces of FRLS and the (1+1) FEA in the objective space of the OneMax problem with 16 bits. These figures can be reproduced with the files given in folder onemax_trace, which is represented by archive onemax_trace.tar.xz. To do so, you can proceed in a manner similar as when reproducing the experiment. You will need Python, install moptipy, and the run python3 algorithm_trace. This one script runs a small experiment and draws the figures.