Find research datasets worth reusing
Search datasets from major research repositories and use ShareScore to quickly assess how well each record supports discovery, access, and reuse.
9
datasets available to search
ShareScore release 0.9.0
Dataset results
9 results for “Frequency Fitness Assignment”
The Experimental Data for the Study "Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function Value"
<p>The Experimental Data for the Study "Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function Value"</p> <p><strong>1. Introduction</strong></p> <p>Frequency Fitness Assignment (FFA) replaces the objective value in the selection step of an optimization method with its encounter frequency in any selection step so far. It turns static problems into dynamic ones. Here we experimentally investigated this approach in two important contexts: First, we integrated it into a basic (1+1)-EA, obtaining the (1+1)-FEA. We applied both algorithms to several well-known benchmark problems with bit-string based search spaces, including the OneMax, LeadingOnes, TwoMax, Jump, Plateau, and W-Model functions. We also applied them to the Max-3-Sat instances from SATLib. We then also integrated FFA into a Memetic Algorithm for the Job Shop Problem.</p> <p><strong>2. Paper</strong></p> <p>This data is used as the basis for the following article: Thomas Weise, Zhize Wu, Xinlu Li, and Yan Chen. Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function Value, originally submitted to <a href="https://arxiv.org/abs/2001.01416">arxiv</a> on 2020-01-06 (under the title Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function), updated with the new data in June 2020, and submitted to the IEEE Transactions on Evolutionary Computation.</p> <p><strong>3. Data</strong></p> <p>This data set contains all the results of these experiments, the source codes used in the experiments (i.e., the algorithm implementations), as well as the scripts used for evaluating the results.</p> <p><strong>4. Version History</strong></p> <p>This is the second version of the data set, including extended experiments and more evaluation results. Most importantly, data for larger scales of OneMax and LeadingOnes has been added. The original version is at <a href="http://dx.doi.org/10.5281/zenodo.3598172">10.5281/zenodo.3598172</a>.</p> <p><strong>5. Contact</strong></p> <p>If you have any questions or suggestions, please contact <a href="http://iao.hfuu.edu.cn/team/director">Prof. Dr. Thomas Weise</a> of the <a href="http://iao.hfuu.edu.cn/">Institute of Applied Optimization</a> at <a href="http://www.hfuu.edu.cn">Hefei University</a> in Hefei, Anhui, China via email to <a href="mailto:tweise@hfuu.edu.cn">tweise@hfuu.edu.cn</a> with CC to <a href="mailto:tweise@ustc.edu.cn">tweise@ustc.edu.cn</a>.</p>
Experiments with Frequency Fitness Assignment based Algorithms on the Traveling Salesperson Problem
<p><strong>1. Introduction</strong></p><p>In this archive, we provide the implementation and experimental results of eight different algorithms to solve Traveling Salesperson Problem (TSP) instances from <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/">TSPLIB</a>.</p><p>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 56 symmetric instances from the well-known <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/">TSPLIB</a>.</p><p>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]).</p><p><strong>2. Directory Structure</strong></p><p>This dataset is split into multiple separate <i>tar.xz</i> archives. These can be unpacked in the same folder and will produce the directory structure described below. Each archive contains this note and the license information, but apart from that, there is no redundancy.</p><p>This archive contains the following directories:</p><ul><li>source contains the Python source codes needed to run the experiment.<ul><li>moptipy-main is a local copy of the <a href="https://thomasweise.github.io/moptipy">moptipy</a> package used for our experiment.</li><li>tsplib contains the <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/">TSPLIB</a> data. This includes the instances used in our experiments as files in text format with suffix .tsp. If an optimal tour is given by TSPLib, 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 <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/">http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/</a>. We also include the documentation of TSPLIB in file <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf">tsp95.pdf</a> documenting them. We further include the <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/TSPFAQ.html">TSPLIB FAQ</a> both as HTML and PDF file (tsplib_faq.html and tsplib_faq.pdf) and the <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html">list of known optimal tour lengths</a> 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 <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf">documentation</a>.</li></ul></li><li>results is the directory with the log files. Each log file contains information of one run, i.e., one execution of one algorithm on one problem instance. All improving moves of a run as well as the final solution are stored in the log file. The direct sub-folders results represent the algorithms and contain one folder per TSP instance, which, in turn, contain the log files.</li><li>evaluation is a folder with the extracted evaluation and figures</li><li>evaluation_edited is a folder with evaluation figures slightly edited for better visual appeal (but obviously without changing any result / scientific content)</li><li>evaluator is a folder with a Python script main.py that generates all the files in evaluation from the data it finds in results. It requires the <a href="https://thomasweise.github.io/moptipy">moptipy</a> package being installed for running in the version given in requirements.txt.</li></ul><p><strong>3. Algorithms</strong></p><p>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. The results of this algorithm are given in folder results/ea_revn.</p><p>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. The results of this algorithm are given in folder results/fea_revn.</p><p>SA is the classical simulated annealing algorithm. In our experiment, it will accept the new solution xn with probability P. If the new solution is better, the acceptance probability P is 1. For worse solutions, the probability is between 0 and 1, i.e., sometimes, worse solution are also accepted. This algorithm has a temperature cooling schedule. It starts at an initial temperature and over time, the temperature decreases. The probability P of accepting the worse solution depends on the temperature and decreases as well. The results of this algorithm are given in folder results/sa_revn.</p><p>An FFA-based version of SA uses the frequency fitness instead of the objective values in all acceptance decisions. The results of this algorithm are given in folder results/fsa_revn.</p><p>EAFEA(A) is a hybrid which alternates between the EA and the FEA and copies a solution from the FEA to the EA if it has an entirely new objective value, i.e., if H[yn] = 1. The results of this algorithm are given in folder results/eafea2_revn.</p><p>SAFEA(A) is a hybrid which alternates between the SA and the FEA and copies a solution from the FEA to the SA if it has an entirely new objective value, i.e., if H[yn] = 1. The results of this algorithm are given in folder results/safea2_revn.</p><p>EAFEA(B) is a hybrid which alternates between the EA and the FEA and copies a solution from the FEA to the EA part if it has a better objective value. The results of this algorithm are given in folder results/eafea_revn.</p><p>SAFEA(B) is a hybrid which alternates between the SA and the FEA and copies a solution from the FEA to the SA part if it has a better objective value. The results of this algorithm are given in folder results/safea_revn.</p><p>We apply all algorithms with the same unary operator reverse, which reverses a randomly chosen subsequence of the tour. This operator is also often called a "2-opt move". It has the advantage that the new objective value of a new solution can be computed in O(1) if the objective value of the solution from which it is derived is known.</p><p><strong>4. How to Run the Experiment</strong></p><p>First, you need to make sure to have all the dependencies installed that this program requires. You can do this by executing the following command in the terminal:</p><p>pip install matplotlib numba numpy psutil scikit-learn moptipy moptipyapps</p><p>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 <i>one</i> of the commands below. (If running the first command returns with an error, just try the next one in the list.)</p><ul><li>python3 -m run</li><li>python -m run</li><li>python run.py</li><li>python3 run.py</li></ul><p>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.</p><p>Side note: This experiment uses the <a href="https://thomasweise.github.io/moptipy">moptipy</a> 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. It also uses moptipyapps to load some data.</p><p><strong>5. Literature</strong></p><ul><li>Frequency Fitness Assignment (FFA):<ol><li>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. IEEE Transactions on Evolutionary Computation (TEVC). 2022. Early Access. doi:<a href="https:doi.org/10.1109/TEVC.2022.3191698">10.1109/TEVC.2022.3191698</a>.</li><li>Thomas Weise, Zhize Wu, Xinlu Li, and Yan Chen. Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function Value. <i>IEEE Transactions on Evolutionary Computation</i> 25(2):307–319. April 2021. Preprint available at <a href="http://arxiv.org/abs/2001.01416">arXiv:2001.01416v5</a> [cs.NE] 15 Oct 2020. doi:<a href="http://dx.doi.org/10.1109/TEVC.2020.3032090">10.1109/TEVC.2020.3032090</a>. Experimental results and source code are available at doi:<a href="http://doi.org/10.5281/zenodo.3899474">10.5281/zenodo.3899474</a>.</li><li>Tianyu Liang, Zhize Wu, Jörg Lässig, Daan van den Berg, and Thomas Weise. Solving the Traveling Salesperson Problem using Frequency Fitness Assignment. In Hisao Ishibuchi, Chee-Keong Kwoh, Ah-Hwee Tan, Dipti Srinivasan, Chunyan Miao, Anupam Trivedi, and Keeley A. Crockett, editors, Proceedings of the IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI'22), part of the IEEE Symposium Series on Computational Intelligence (SSCI 2022). December 4–7, 2022, Singapore, pages 360–367. IEEE. doi:<a href="https://doi.org/10.1109/SSCI51031.2022.10022296">10.1109/SSCI51031.2022.10022296</a>.</li><li>Thomas Weise, Mingxu Wan, Ke Tang, Pu Wang, Alexandre Devert, and Xin Yao. Frequency Fitness Assignment. <i>IEEE Transactions on Evolutionary Computation (IEEE-EC)</i> 18(2):226-243, April 2014. doi:<a href="http://dx.doi.org/10.1109/TEVC.2013.2251885">10.1109/TEVC.2013.2251885</a>.</li><li>Thomas Weise, Xinlu Li, Yan Chen, and Zhize Wu. Solving Job Shop Scheduling Problems Without Using a Bias for Good Solutions. In <i>Genetic and Evolutionary Computation Conference Companion (GECCO'21 Companion),</i> July 10-14, 2021, Lille, France. ACM, New York, NY, USA. ISBN 978-1-4503-8351-6. doi:<a href="http://doi.org/10.1145/3449726.3463124">10.1145/3449726.3463124</a>.</li><li>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. <i>Applied Soft Computing Journal (ASOC)</i>, 92:106269, June 2020. doi:<a href="http://dx.doi.org/10.1016/j.asoc.2020.106269">10.1016/j.asoc.2020.106269</a>.</li><li>Thomas Weise, Mingxu Wan, Ke Tang, and Xin Yao. Evolving Exact Integer Algorithms with Genetic Programming. In <i>Proceedings of the IEEE Congress on Evolutionary Computation (CEC'14), Proceedings of the 2014 World Congress on Computational Intelligence (WCCI'14)</i>, pages 1816-1823, Beijing, China, July 6-11, 2014. Los Alamitos, CA, USA: IEEE Computer Society Press. ISBN: 978-1-4799-1488-3. doi:<a href="http://dx.doi.org/10.1109/CEC.2014.6900292">10.1109/CEC.2014.6900292</a>.</li></ol></li><li>Traveling Salesperson Problem (TSP):<ol><li>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. <i>Artificial Intelligence Review,</i> 13(2):129–170, April 1999. Kluwer Academic Publishers, The Netherlands. doi:<a href="https://doi.org/10.1023/A:1006529012972">10.1023/A:1006529012972</a>.</li><li>Gerhard Reinelt. TSPLIB — A Traveling Salesman Problem Library. <i>ORSA Journal on Computing</i> 3(4):376-384. 1991. <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/">http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/</a>.</li><li>Gerhard Reinelt. TSPLIB95. 1995. Heidelberg, Germany: Universität Heidelberg, Institut für Angewandte Mathematik. <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf">http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf</a>.</li><li>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. <i>IEEE Computational Intelligence Magazine (CIM)</i> 9(3):40-52, August 2014. doi:<a href="http://dx.doi.org/10.1109/MCI.2014.2326101">10.1109/MCI.2014.2326101</a>.</li><li>Eugene Leighton Lawler, Jan Karel Lenstra, Alexander Hendrik George Rinnooy Kan, and David B. Shmoys. <i>The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization.</i> Wiley Interscience. 1985.</li><li>David Lee Applegate, Robert E. Bixby, Vasek Chvatal, and William John Cook. <i>The Traveling Salesman Problem: A Computational Study.</i> Princeton University Press. 2007.</li><li>Gregory Z. Gutin and Abraham P. Punnen, editors. <i>The Traveling Salesman Problem and its Variations.</i> Volume 12 of Combinatorial Optimization. Kluwer Academic Publishers. 2002. doi:<a href="https://dx.doi.org/10.1007/b101971">10.1007/b101971</a>.</li></ol></li><li>Software:<ol><li>The Metaheuristic Optimization in Python Package <a href="https://thomasweise.github.io/moptipy">moptipy</a></li></ol></li></ul><p><strong>6. License</strong></p><p>The files in this repository are under the <a href="https://creativecommons.org/licenses/by/4.0/legalcode">Creative Commons Attribution 4.0 International</a>, with the exception of the files of <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/">TSPLIB</a> 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.txt in this archive.</p><p><strong>7. Contact</strong></p><p>If you have any questions or suggestions, please contact</p><p>Mr. Tianyu LIANG (梁天宇) of the Institute of Applied Optimization (应用优化研究所, <a href="http://iao.hfuu.edu.cn">IAO</a>) of the School of Artificial Intelligence and Big Data (<a href="http://www.hfuu.edu.cn/aibd/">人工智能与大数据学院</a>) at <a href="http://www.hfuu.edu.cn/english/">Hefei University</a> (<a href="http://www.hfuu.edu.cn/">合肥学院</a>) in Hefei, Anhui, China (中国安徽省合肥市) via email to <a href="mailto:liangty@stu.hfuu.edu.cn">liangty@stu.hfuu.edu.cn</a>.</p>
Experimental Data for the Paper "Frequency Fitness Assignment: Optimization without a Bias for Good Solutions can be Efficient"
<p><strong><em>The data for the paper "Frequency Fitness Assignment: Optimization without a Bias for Good Solutions can be Efficient"</em></strong></p> <p>This is the data set with the experimental results for our paper "Frequency Fitness Assignment: Optimization without a Bias for Good Solutions can be Efficient." We conduct more than 56 million runs, consuming more than 6.5*10<sup>14</sup> FEs as well as 150 processor years, ensuring that our results are statistically sound and rigorous. Here, you can find all the results, all the program codes used for obtaining the results, and all the tables and figures produced from the results, and the program codes used to produce them.</p> <p><strong><em>Included Files</em></strong></p> <ul> <li><code>ffa-empirical-complexity_results.tar.xz</code> (size packed 11.7 GiB, unpacked 335.2 GiB): The complete set of log files. For each run of each experiment, one distinct text-based log file is created. The log file contains every improving step of the algorithm, the final result, and the system configuration. This archive is very large and unpacked it will occupy more than 335 GiB of hard disk space.</li> <li><code>ffa-empirical-complexity_end_of_run_results_and_stats.tar.xz</code> (size packed 861.4 MiB, unpacked 6,295.9 MiB): The end-of-run result qualities and consumed runtime as well as statistics thereof. These information have been extracted from the log files and are provided in form of semicolon-separated values text files. These files are much easier to consume. They do not reflect the progress of the single runs, but only their end results.</li> <li><code>ffa-empirical-complexity_sources.tar.xz</code> (size packed 65.5 MiB, unpacked 173.6 MiB): The complete set of <code>Java</code> sources that was used to perform the experiments. Since the random seeds of the random number generators are created in a deterministic way, you could execute this code and obtain the exactly same log files in terms of consumed FEs, improving steps, and end results as we provide in <code>ffa-empirical-complexity_results.tar.xz</code>. (Of course, your systems configuration and measured runtime in milliseconds would probably be different.)</li> <li><code>ffa-empirical-complexity_evaluator.tar.xz</code> (size packed 4,015.8 KiB, unpacked 4,510 KiB): The <code>Java</code> and <code>R</code> source codes that are used to extract the end results from the log files, compute all relevant statistics, and produce the graphics in our article.</li> <li><code>ffa-empirical-complexity_evaluation.tar.xz</code> (size packed 417.3 KiB, unpacked 590.0 KiB): The high-level conclusions produced by the evaluator from the raw data, including tables and figures.</li> <li><code>ffa-empirical-complexity_saga_ffa_on_plateau.tar.xz</code> (size packed 7,238.9 KiB, unpacked 26.8 MiB): We also conducted an additional experiment to better understand the behavior of the SAGA algorithm variants using FFA on the Plateau problem. Here we provide source codes and result log files of this experiment. The result log files are much more comprehensive, as we tried to figure out why these algortihms were able to solve the Plateau problems (and they ultimately helped us to successfully do so).</li> </ul> <p><strong><em>License</em></strong></p> <p>The copyright holder of this dataset is Prof. Dr. Thomas Weise (see <a href="#contact">Contact</a>). The dataset is licensed under the <a href="https://creativecommons.org/licenses/by/4.0/en/legalcode">Creative Commons Attribution 4.0 International License</a>.</p> <p><strong><em>Contact</em></strong></p> <p>If you have any questions or suggestions, please contact the corresponding author of this dataset, Prof. Dr. <a href="http://iao.hfuu.edu.cn/team/director">Thomas Weise</a> of the Institute of Applied Optimization (<a href="http://iao.hfuu.edu.cn/">IAO</a>) at <a href="http://www.hfuu.edu.cn/english/main.htm">Hefei University</a> [<a href="http://www.hfuu.edu.cn">合肥学院</a>] in Hefei, Anhui, China via email to <a href="mailto:tweise@hfuu.edu.cn">tweise@hfuu.edu.cn</a> with CC to <a href="mailto:tweise@ustc.edu.cn">tweise@ustc.edu.cn</a>.</p>
Experiments with Frequency Fitness Assignment in a (1+1) EA on the Traveling Salesperson Problem
<p><strong>1. Introduction</strong></p> <p>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 <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/">TSPLIB</a>.</p> <p>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 <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/">TSPLIB</a>.</p> <p>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><sup>th</sup> 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>.</p> <p>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<=yc</code>, then it will accept the new tour and set <code>xn=xn</code> and <code>yc=yn</code>.</p> <p>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] <= H[yc]</code> and, only in this case, set <code>xn=xn</code> and <code>yc=yn</code>.</p> <p>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.</p> <p><strong>2. Directory Structure</strong></p> <p>This archive contains the following directories:</p> <ul> <li><code>results_and_evaluation</code> contain the results of two experiments as well as their evaluation. <ul> <li><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 <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/">TSPLIB</a>. <ul> <li><code>results</code> is the directory with the log files</li> <li><code>evaluation</code> is a folder with the extracted evaluation and figures</li> <li><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 <a href="https://thomasweise.github.io/moptipy"><code>moptipy</code></a> package being installed for running.</li> </ul> </li> <li><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. <ul> <li><code>results</code> is the directory with the log files</li> <li><code>evaluation</code> is a folder with the extracted evaluation and figures</li> <li><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 <a href="https://thomasweise.github.io/moptipy"><code>moptipy</code></a> package being installed for running.</li> </ul> </li> </ul> </li> <li><code>source</code> contains the Python source codes needed to run the <code>performance</code> experiment. <ul> <li><code>moptipy</code> is a local copy of the <a href="https://thomasweise.github.io/moptipy"><code>moptipy</code></a> package used for our experiment.</li> <li><code>tsplib</code> contains the <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/">TSPLIB</a> 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 <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/">http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/</a>. We also include the documentation of TSPLIB in file <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf"><code>tsp95.pdf</code></a> documenting them. We further include the <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/TSPFAQ.html">TSPLIB FAQ</a> both as HTML and PDF file (<code>tsplib_faq.html</code> and <code>tsplib_faq.pdf</code>) and the <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html">list of known optimal tour lengths</a> 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 <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf">documentation</a>.</li> </ul> </li> </ul> <p><strong>3. What algorithms are included in this experiment?</strong></p> <p>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><sup>th</sup> 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.</p> <ul> <li>(1+1) EA <ul> <li>with <code>swap</code> operator</li> <li>with <code>reverse</code> operator</li> </ul> </li> <li>(1+1) FEA, i.e., the (1+1) EA with Frequency Fitness Assignment (FFA) <ul> <li>with <code>swap</code> operator</li> <li>with <code>reverse</code> operator</li> </ul> </li> </ul> <p><strong>4. How to Run the Experiment</strong></p> <p>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:</p> <pre><code>pip install matplotlib numba numpy pandas psutil scikit-learn</code></pre> <p>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.)</p> <ul> <li><code>python3 -m run</code></li> <li><code>python -m run</code></li> <li><code>python run.py</code></li> <li><code>python3 run.py</code></li> </ul> <p>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.</p> <p>Side note: This experiment uses the <a href="https://thomasweise.github.io/moptipy"><code>moptipy</code></a> 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>.</p> <p><strong>5. Literature</strong></p> <ul> <li>Frequency Fitness Assignment (FFA): <ol> <li>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 <a href="http://arxiv.org/abs/2001.01416">arXiv:2001.01416v5</a> [cs.NE] 15 Oct 2020. doi:<a href="http://dx.doi.org/10.1109/TEVC.2020.3032090">10.1109/TEVC.2020.3032090</a>. Experimental results and source code are available at doi:<a href="http://doi.org/10.5281/zenodo.3899474">10.5281/zenodo.3899474</a>.</li> <li>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. <a href="https://arxiv.org/abs/2112.00229v4">arXiv:2112.00229v4</a> [cs.NE] 25 May 2022.</li> <li>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:<a href="http://dx.doi.org/10.1109/TEVC.2013.2251885">10.1109/TEVC.2013.2251885</a>.</li> <li>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:<a href="http://doi.org/10.1145/3449726.3463124">10.1145/3449726.3463124</a>.</li> <li>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:<a href="http://dx.doi.org/10.1016/j.asoc.2020.106269">10.1016/j.asoc.2020.106269</a>.</li> <li>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:<a href="http://dx.doi.org/10.1109/CEC.2014.6900292">10.1109/CEC.2014.6900292</a>.</li> </ol> </li> <li>Traveling Salesperson Problem (TSP): <ol> <li>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:<a href="https://doi.org/10.1023/A:1006529012972">10.1023/A:1006529012972</a>.</li> <li>Gerhard Reinelt. TSPLIB — A Traveling Salesman Problem Library. <em>ORSA Journal on Computing</em> 3(4):376-384. 1991. <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/">http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/</a>.</li> <li>Gerhard Reinelt. TSPLIB95. 1995. Heidelberg, Germany: Universität Heidelberg, Institut für Angewandte Mathematik. <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf">http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf</a>.</li> <li>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:<a href="http://dx.doi.org/10.1109/MCI.2014.2326101">10.1109/MCI.2014.2326101</a>.</li> <li>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.</li> <li>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.</li> <li>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:<a href="https://dx.doi.org/10.1007/b101971">10.1007/b101971</a>.</li> </ol> </li> <li>Software: <ol> <li>The Metaheuristic Optimization in Python Package <a href="https://thomasweise.github.io/moptipy"><code>moptipy</code></a></li> </ol> </li> </ul> <p><strong>6. License</strong></p> <p>The files in this repository are under the <a href="https://creativecommons.org/licenses/by/4.0/legalcode">Creative Commons Attribution 4.0 International</a>, with the exception of the files of <a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/">TSPLIB</a> 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.</p>
Data for the PPSN 2024 article: "Entropy, Trajectories, and Explainability for Frequency Fitness Assignment"
<p>Dataset for the PPSN 2024 article: "Entropy, Trajectories, and Explainability for Frequency Fitness Assignment"</p>
Implementation and Results of a "Randomized Local Search for Two-Dimensional Bin Packing and a Negative Result for Frequency Fitness Assignment"
<p><strong><em>1. Introduction</em></strong></p> <p>In this archive, we provide the implementation and experimental results of a Randomized Local Search (RLS) applied to the two-dimensional bin packing problem with and without orientation. As benchmark dataset, we use the <code>beng</code>, <code>A</code>, and <code>class</code> instances from <a href="https://site.unibo.it/operations-research/en/research/2dpacklib">2DPackLib</a> as well as the four non-trivial Almost Squares in Almost Squares (<a href="https://math.vu.nl/~sbhulai/publications/data_analytics2016b.pdf"><code>Asqas</code></a>) instances</p> <p>These are the data used in the paper below, which contains the exact specification of all algorithms, objective functions, and the encoding we applied.</p> <p>Rui Zhao, Zhize Wu, Daan van den Berg, Matthias Thürer, Tianyu Liang, Ming Tan, and Thomas Weise. Randomized Local Search for Two-Dimensional Bin Packing and a Negative Result for Frequency Fitness Assignment. In <em>16th International Conference on Evolutionary Computation Theory and Applications (ECTA'24), part of the 16th International Joint Conference on Computational Intelligence (IJCCI'24)</em>. November 20-24, 2024. Porto, Portugal. Setúbal, Portugal: SciTePress.</p> <p>To run the experiments, you need <a href="https://thomasweise.github.io/moptipyapps">moptipyapps</a> and <a href="https://thomasweise.github.io/moptipy">moptipy</a>, which contain the actual algorithm implementations. Both packages are available on GitHub and on PyPI. However, we include several versions of them in the folder <code>source/packages</code>, just in case.</p> <p><strong><em>2. Directory Structure</em></strong></p> <p>This archive contains the following directories:</p> <ul> <li><code>source</code> contains the Python source codes needed to run the experiment.</li> <li><code>source/packages</code> contains the source codes of the Python packages with the actual algorithm implementations.</li> <li><code>source/experiment_execution_scripts</code> contains the scripts to run the experiments.</li> <li><code>results</code> is the directory with the results, i.e., with the log files generated by the experiment.</li> <li><code>evaluator</code> is the folder containing Python scripts that were used to evaluate these results.</li> <li><code>evaluation</code> was generated using the evaluation scripts and contains tables and figures and a result summary in CSV format.</li> </ul> <p><strong><em>3. License</em></strong></p> <p>The files in this repository are under the <a href="https://creativecommons.org/licenses/by/4.0/legalcode">Creative Commons Attribution 4.0 International</a>, with the exception of the files of <a href="https://site.unibo.it/operations-research/en/research/2dpacklib">2DPackLib</a> and other benchmark datasets included, 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.txt</code> in this archive.</p> <p><strong><em>4. Contact</em></strong></p> <p>If you have any questions or suggestions, please contact</p> <p>Mr. Rui ZHAO (赵睿) of the Institute of Applied Optimization (应用优化研究所, <a href="http://iao.hfuu.edu.cn">IAO</a>) of the School of Artificial Intelligence and Big Data (<a href="http://www.hfuu.edu.cn/aibd/">人工智能与大数据学院</a>) at <a href="http://www.hfuu.edu.cn/english/">Hefei University</a> (<a href="http://www.hfuu.edu.cn/">合肥大学</a>) in Hefei, Anhui, China (中国安徽省合肥市) via email to <a href="mailto:zr1329142665@163.com">zr1329142665@163.com</a>.</p>
Implementation and Results of a "Frequency Fitness Assignment: Optimization without Bias for Good Solution outperforms Randomized Local Search on the Quadratic Assignment Problem"
<p><strong><em>1. Introduction</em></strong></p> <p>In this archive, we provide the implementation and experimental results of a Randomized Local Search (RLS) with and without FFA applied to the Quadratic Assignment Problem. These are the data used in the paper below, which contains the exact specification of all algorithms, objective functions, and the encoding we applied.</p> <p>Jiayang Chen, Zhize Wu, Sarah L. Thomson, and Thomas Weise. Frequency Fitness Assignment: Optimization without Bias for Good Solution outperforms Randomized Local Search on the Quadratic Assignment Problem. In <em>16th International Conference on Evolutionary Computation Theory and Applications (ECTA'24), part of the 16th International Joint Conference on Computational Intelligence (IJCCI'24)</em>. November 20-24, 2024. Porto, Portugal. Setúbal, Portugal: SciTePress.</p> <p>To run the experiments, you need <a href="https://thomasweise.github.io/moptipyapps">moptipyapps</a> and <a href="https://thomasweise.github.io/moptipy">moptipy</a>, which contain the actual algorithm implementations. Both packages are available on GitHub and on PyPI. However, we include several versions of them in the folder <code>source/packages</code>, just in case.</p> <p><strong><em>2. Directory Structure</em></strong></p> <p>This archive contains the following directories:</p> <ul> <li><code>source</code> contains the Python source codes needed to run the experiment.</li> <li><code>source/packages</code> contains the source codes of the Python packages with the actual algorithm implementations.</li> <li><code>source/experiment_execution_scripts</code> contains the scripts to run the experiments.</li> <li><code>results</code> is the directory with the results, i.e., with the log files generated by the experiment.</li> <li><code>evaluator</code> is the folder containing Python scripts that were used to evaluate these results.</li> <li><code>evaluation</code> was generated using the evaluation scripts and contains tables and figures and a result summary in CSV format.</li> </ul> <p><strong><em>3. License</em></strong></p> <p>The files in this repository are under the <a href="https://creativecommons.org/licenses/by/4.0/legalcode">Creative Commons Attribution 4.0 International</a>, with the exception of the benchmark datasets included, 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.txt</code> in this archive.</p> <p><strong><em>4. Contact</em></strong></p> <p>If you have any questions or suggestions, please contact</p> <p>Mr. Jiayang CHEN (陈嘉阳) of the Institute of Applied Optimization (应用优化研究所, <a href="http://iao.hfuu.edu.cn">IAO</a>) of the School of Artificial Intelligence and Big Data (<a href="http://www.hfuu.edu.cn/aibd/">人工智能与大数据学院</a>) at <a href="http://www.hfuu.edu.cn/english/">Hefei University</a> (<a href="http://www.hfuu.edu.cn/">合肥大学</a>) in Hefei, Anhui, China (中国安徽省合肥市) via email to <a href="mailto:cjy65820607@163.com">cjy65820607@163.com</a>.</p>
Implementation and Results of a "Randomized Local Search vs. NSGA-II vs. Frequency Fitness Assignment on The Traveling Tournament Problem"
<p><strong><em>1. Introduction</em></strong></p> <p>In this archive, we provide the implementation and experimental results of a Randomized Local Search (RLS) with and without FFA as well as NSGA-II applied to the Traveling Tournament Problem. These are the data used in the paper below, which contains the exact specification of all algorithms, objective functions, and the encoding we applied.</p> <p>Cao Xiang, Zhize Wu, Daan van den Berg, and Thomas Weise. Randomized Local Search vs. NSGA-II vs. Frequency Fitness Assignment on The Traveling Tournament Problem. In <em>16th International Conference on Evolutionary Computation Theory and Applications (ECTA'24), part of the 16th International Joint Conference on Computational Intelligence (IJCCI'24)</em>. November 20-24, 2024. Porto, Portugal. Setúbal, Portugal: SciTePress.</p> <p>To run the experiments, you need <a href="https://thomasweise.github.io/moptipyapps">moptipyapps</a> and <a href="https://thomasweise.github.io/moptipy">moptipy</a>, which contain the actual algorithm implementations. Both packages are available on GitHub and on PyPI. However, we include several versions of them in the folder <code>source/packages</code>, just in case.</p> <p><strong><em>2. Directory Structure</em></strong></p> <p>This archive contains the following directories:</p> <ul> <li><code>source</code> contains the Python source codes needed to run the experiment.</li> <li><code>source/packages</code> contains the source codes of the Python packages with the actual algorithm implementations.</li> <li><code>source/experiment_execution_scripts</code> contains the scripts to run the experiments.</li> <li><code>results</code> is the directory with the results, i.e., with the log files generated by the experiment.</li> <li><code>evaluator</code> is the folder containing Python scripts that were used to evaluate these results.</li> <li><code>evaluation</code> was generated using the evaluation scripts and contains tables and figures and a result summary in CSV format.</li> </ul> <p><strong><em>3. License</em></strong></p> <p>The files in this repository are under the <a href="https://creativecommons.org/licenses/by/4.0/legalcode">Creative Commons Attribution 4.0 International</a>, with the exception of the benchmark datasets included, 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.txt</code> in this archive.</p> <p><strong><em>4. Contact</em></strong></p> <p>If you have any questions or suggestions, please contact</p> <p>Mr. Xiang CAO (曹翔) of the Institute of Applied Optimization (应用优化研究所, <a href="http://iao.hfuu.edu.cn">IAO</a>) of the School of Artificial Intelligence and Big Data (<a href="http://www.hfuu.edu.cn/aibd/">人工智能与大数据学院</a>) at <a href="http://www.hfuu.edu.cn/english/">Hefei University</a> (<a href="http://www.hfuu.edu.cn/">合肥大学</a>) in Hefei, Anhui, China (中国安徽省合肥市) via email to <a href="mailto:452015026@qq.com">452015026@qq.com</a>.</p>
Supplemental material for the paper, "Entropy, Search Trajectories, and Explainability for Frequency Fitness Assignment"
Open the record for dataset details and reuse information.
ScienceDex guides
Understand access before you commit
These curated guides explain access requirements, typical timelines, costs, and reuse considerations for widely used research datasets.
Allen Brain Atlas
Allen Brain Atlas is an Allen Institute collection of brain map atlases, datasets, APIs, and analysis tools covering mouse, human, and non-human primate brain resources.
Annotated Behaviour and Observability Dataset (ABODe)
ABODe is a University of Edinburgh DataShare dataset for behavior classification in group-housed mice using home-cage video, identities, bounding boxes, ground-plate positions, and annotator labels.
DANDI Archive for NWB datasets
DANDI is a BRAIN Initiative archive for publishing and sharing neurophysiology data, including electrophysiology, optophysiology, and behavioral data packaged as NWB and related standards.
International Brain Laboratory public data
The International Brain Laboratory public data releases expose standardized mouse decision-making experiments, including Neuropixels recordings, widefield calcium imaging, behavior, and session metadata accessed through the ONE API.
OpenNeuro
OpenNeuro is a free, open platform for sharing neuroimaging datasets, with public search, dataset pages, and download paths for web, S3, DataLad, and the OpenNeuro CLI.