Frequency Fitness Assignment
Frequency Fitness Assignment (FFA, 频率适应度分配) is a novel approach to metaheuristic optimization. Actually, it abandons the very core principles of metaheuristic optimization. And yet, it works.
Introduction
Many important problems in optimization and operations research are NP-hard, which means that algorithms that can guarantee to always find their optimal solution may take a runtime exponential in the problem size in the worst case. In layman’s terms, this simply means “If an algorithm guarantees you to find the best possible solution for a given problem, it might take waaaaay to long on some instances of these problems.” Metaheuristic optimization algorithms are methods that do not guarantee to find the optimal solutions. However, they tend to be quite fast in giving us good solutions and sometimes even find the optimal solutions anyway.
They are based on the simple principle of “trial and error.” All of them have in common that they repeatedly sample candidate solutions in one way or another, pick the better ones of these candidates with higher probability, and use those as basis to sample new solutions similar to them. Regardless if you have a local search, an Evolutionary Algorithm, Simulated Annealing, Tabu Search or even Estimation of Distribution algorithms — they all adopt this principle to prefer better solutions as basis for sampling new solutions.
Frequency Fitness Assignment (FFA) abandons this bias toward better solutions. Instead, it prefers solutions whose objective values (or costs, or quality rating, whatever you prefer) have been encountered less frequently in the selection decisions during the search. In other words, it does no longer matter whether one solution is better. Matter of fact, algorithms using FFA may “optimize” toward worse solutions half of their time.
Dropping the bias towards better solutions has an interesting consequence: Algorithms that use FFA are invariant under all injective transformations of the objective function value. This is the strongest theoretically possible invariance property. The only other algorithms that have it are random sampling, random walks, and exhaustive enumeration. These methods, however, are pretty awful approaches to optimization. Not FFA, though, as it turned out to work quite well in domains such as MaxSat, the Traveling Salesperson Problem, the Quadratic Assignment Problem, and on discrete benchmark functions.
Publications
Here you can find a talk introducing FFA from the perspective of invariance properties.
Core Papers
- 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) 27(4):980-992. August 2023.
- 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 (TEVC) 25(2):307-319. April 2021.
- Thomas Weise (汤卫思), Mingxu WAN (万明绪), Ke TANG (唐珂), Pu WANG, Alexandre Devert, and Xin YAO (姚新): Frequency Fitness Assignment. IEEE Transactions on Evolutionary Computation (IEEE-TEVC) 18(2):226-243. April 2014.
Complete List
- Rui ZHAO (赵睿), Zhize WU (吴志泽), Daan van den Berg, Matthias Thürer, Tianyu LIANG (梁天宇), Tan MING (檀明), and Thomas Weise (汤卫思): Randomized Local Search for Two-Dimensional Bin Packing and a Negative Result for Frequency Fitness Assignment. International Conference on Evolutionary Computation Theory and Applications (ECTA'2024), part of 16th International Joint Conference on Computational Intelligence (IJCCI'2024), November 20-22, 2024, Porto, Portugal, pages 15-26. Setúbal, Portugal: SciTePress.
- Jiayang CHEN (陈嘉阳), Zhize WU (吴志泽), Sarah Louise Thomson, and Thomas Weise (汤卫思): Frequency Fitness Assignment: Optimization Without Bias for Good Solution Outperforms Randomized Local Search on the Quadratic Assignment Problem. International Conference on Evolutionary Computation Theory and Applications (ECTA'2024), part of 16th International Joint Conference on Computational Intelligence (IJCCI'2024), November 20-22, 2024, Porto, Portugal, pages 27-37. Setúbal, Portugal: SciTePress.
- Tianyu LIANG (梁天宇), Zhize WU (吴志泽), Matthias Thürer, Markus Wagner, and Thomas Weise (汤卫思): Generating Small Instances with Interesting Features for the Traveling Salesperson Problem. International Conference on Evolutionary Computation Theory and Applications (ECTA'2024), part of 16th International Joint Conference on Computational Intelligence (IJCCI'2024), November 20-22, 2024, Porto, Portugal, pages 173-180. Setúbal, Portugal: SciTePress.
- Xiang CAO (曹翔), Zhize WU (吴志泽), Daan van den Berg, and Thomas Weise (汤卫思): Randomized Local Search vs. NSGA-II vs. Frequency Fitness Assignment on The Traveling Tournament Problem. International Conference on Evolutionary Computation Theory and Applications (ECTA'2024), part of 16th International Joint Conference on Computational Intelligence (IJCCI'2024), November 20-22, 2024, Porto, Portugal, pages 38-49. Setúbal, Portugal: SciTePress.
- Sarah Louise Thomson, Gabriela Ochoa, Daan van den Berg, Tianyu LIANG (梁天宇), and Thomas Weise (汤卫思): Entropy, Search Trajectories, and Explainability for Frequency Fitness Assignment. 18th International Conference on Parallel Problem Solving from Nature (PPSN XVIII), September 14-18, 2024, Hagenberg, Austria, pages 377-392. Lecture Notes in Computer Science (LNCS), volume 15148. Berlin/Heidelberg, Germany: Springer.
- Tianyu LIANG (梁天宇), Zhize WU (吴志泽), Jörg Lässig, Daan van den Berg, Sarah Louise Thomson, and Thomas Weise (汤卫思): Addressing the Traveling Salesperson Problem with Frequency Fitness Assignment and Hybrid Algorithms. Soft Computing 28(17-18):9495-9508. September 2024.
- 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) 27(4):980-992. August 2023.
- Tianyu LIANG (梁天宇), Zhize WU (吴志泽), Jörg Lässig, Daan van den Berg, and Thomas Weise (汤卫思): Solving the Traveling Salesperson Problem using Frequency Fitness Assignment. IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI'2022), part of the IEEE Symposium Series on Computational Intelligence (SSCI'2022), December 4-7, 2022, Singapore. IEEE.
- Thomas Weise (汤卫思), Xinlu LI (李新路), Yan CHEN (陈岩), and Zhize WU (吴志泽): Solving Job Shop Scheduling Problems Without Using a Bias for Good Solutions. Genetic and Evolutionary Computation Conference Companion (GECCO'21) Companion, July 10-14, 2021, Lille, France. New York, NY, USA:&nbso;ACM.
- 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 (TEVC) 25(2):307-319. April 2021.
- 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.
- Thomas Weise (汤卫思), Raymond Chiong, Jörg Lässig, Ke TANG (唐珂), 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.
- Thomas Weise (汤卫思), Mingxu WAN (万明绪), Ke TANG (唐珂), and Xin YAO (姚新): Evolving Exact Integer Algorithms with Genetic Programming. IEEE Congress on Evolutionary Computation (CEC'2014), part of the World Congress on Computational Intelligence (WCCI'2014), pages 1816-1823, July 6-11, 2014, Beijing, China. Los Alamitos, CA, USA: IEEE Computer Society Press.
- Thomas Weise (汤卫思), Mingxu WAN (万明绪), Ke TANG (唐珂), Pu WANG, Alexandre Devert, and Xin YAO (姚新): Frequency Fitness Assignment. IEEE Transactions on Evolutionary Computation (IEEE-TEVC) 18(2):226-243. April 2014.