Local Search

less than 1 minute read

Local search algorithms are metaheuristics that maintain one single solution and sample a new one in each iteration. The most well-known examples for these algorithms are maybe randomized local search (RLS), hill climbing, and the (1+1) EA.

Posts

Plugging Frequency Fitness Assignment into Metaheuristics

12 minute read

Frequency Fitness Assignment (FFA) is a technique that fundamentally changes how (metaheuristic) optimization algorithms work. The goal of this post is to explore how this technique can be plugged into an existing algorithm. We first discuss optimization and the general pattern of metaheuristics in general. We then discuss the simplest local search algorithm – randomized local search, or RLS for short. We plug FFA into this algorithm and obtain the FRLS. We finally list some properties of FRLS as well as some related works.

Measuring the Runtime of (Optimization) Algorithms

22 minute read

My research area is metaheuristic optimization, i.e., algorithms that can find good approximate solutions for computationally hard problems in feasible time. The Traveling Salesperson Problem (TSP) is an example for such an optimization task. In a TSP, $n$ cities and the distances between them are given and the goal is to find the shortest round-trip tour that goes through each city exactly once and then returns to its starting point. The TSP is $\mathcal{NP}$-hard, meaning that any currently known algorithm for finding the exact / globally best solution for all possible TSP instances will need a time which grows exponentially with $n$ on the worst case instances. And this is unlikely to change. In other words, if a TSP instance has $n$ cities, then the worst-case runtime of any exact TSP solver is in ${\mathcal{O}}(2^n)$. Well, today we have algorithms that can exactly solve a wide range of problems with tens of thousands of nodes and approximate the solution of million-node problems with an error of less than one part per thousand. This is pretty awesome, but the worst-case runtime to find the exact (optimal) solution is still exponential.

Are Black-Box Global Search Methods, such as Metaheuristics like Evolutionary Algorithms, better than Local Search?

15 minute read

Sometimes, when discussing the benefits of Evolutionary Algorithms (EAs), their special variant Genetic Algorithms (GAs) with bit-string based search spaces, or other metaheuristic global search algorithms in general, statements like the following may be made:“If you use a huge population size with a large computational budget for both global search metaheuristics (with enough diversity) and local search metaheuristics, the global search approach will no doubt outperform the local search.” I cannot not really agree to this statement, in particular if it is applied to black box metaheuristics (those that make no use of the problem knowledge).

What is optimization?

18 minute read

The center of my research is optimization. But what is optimization? Basically, optimization is the art of making good decisions. It provides us with a set of tools, mostly from the areas of computer science and mathematics, which are applicable in virtually all fields ranging from business, industry, biology, physics, medicine, data mining, engineering, to even art.

Publications

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.
FFA, RLS, local search, packing, moptipy, Python, more infos.
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.
FFA, RLS, local search, moptipy, Python, more infos.
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.
TSP, logistics, RLS, FFA, local search, moptipy, Python, more infos.
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.
TTP, logistics, RLS, FFA, local search, moptipy, Python, more infos.
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.
RLS, FFA, local search, moptipy, Python, more infos.
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.
TSP, logistics, RLS, FFA, local search, moptipy, Python, more infos.
Rui ZHAO (赵睿), Tianyu LIANG (梁天宇), Zhize WU (吴志泽), Daan van den Berg, Matthias Thürer, and Thomas Weise (汤卫思): Randomized Local Search on the 2D Rectangular Bin Packing Problem with Item Rotation. Genetic and Evolutionary Computation Conference (GECCO'2024) Companion, July 14-18, 2024, Melbourne, VIC, Australia, pages 235-238. New York, NY, USA: ACM.
RLS, packing, local search, moptipy, Python, more infos.
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.
FFA, local search, aitoa-code, more infos.
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.
TSP, logistics, FFA, local search, RLS, moptipy, Python, more infos.
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: ACM.
FFA, local search, aitoa-code, scheduling, more infos.
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.
FFA, local search, scheduling, aitoa-code, more infos.
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.
benchmarking, aitoa-code, local search, FFA, more infos.
Thomas Weise (汤卫思), Yuezhong WU (吴越钟), Weichen LIU (刘伟臣), and Raymond Chiong: Implementation Issues in Optimization Algorithms: Do they matter? Journal of Experimental & Theoretical Artificial Intelligence (JETAI) 31(4):533-554. 2019.
TSP, logistics, local search, TSP Suite, benchmarking, more infos.
Thomas Weise (汤卫思), Zijun WU (吴自军), and Markus Wagner: An Improved Generic Bet-and-Run Strategy with Performance Prediction for Stochastic Local Search. 33rd AAAI Conference on Artificial Intelligence (AAAI'2019), January 27 - February 1, 2019, Honolulu, Hawaii, USA, pages 2395-2402. Palo Alto, CA, USA: AAAI Press.
TSP, logistics, local search, more infos.
Thomas Weise (汤卫思), Xiao-Feng WANG (王晓峰), Qi QI (齐琪), Bin LI (李斌), and Ke TANG (唐珂): Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features. Applied Soft Computing Journal (ASOC), 73:366–382, December 2018.
TSP, logistics, benchmarking, optimizationBenchmarking, ACO, EAs, local search, more infos.
Weichen LIU (刘伟臣), Thomas Weise (汤卫思), Yuezhong WU (吴越钟), and Qi QI (齐琪): Combining Two Local Searches with Crossover: An Efficient Hybrid Algorithm for the Traveling Salesman Problem. Genetic and Evolutionary Computation Conference (GECCO'2017), July 15-19, 2017, Berlin, Germany, New York, NY, USA: ACM Press, pages 298-305.
TSP, TSP Suite, logistics, local search, more infos.
Qi QI (齐琪), Thomas Weise (汤卫思), and Bin LI (李斌): Modeling Optimization Algorithm Runtime Behavior and its Applications. Genetic and Evolutionary Computation Conference (GECCO'2017) Companion, July 15-19, 2017, Berlin, Germany, New York, NY, USA: ACM Press, pages 115-116.
benchmarking, local search, more infos.
Thomas Weise (汤卫思), Yuezhong WU (吴越钟), Raymond Chiong, Ke TANG (唐珂), and Jörg Lässig: Global versus Local Search: The Impact of Population Sizes on Evolutionary Algorithm Performance. Journal of Global Optimization (JOGO) 66(3):511-534. November 2016.
TSP Suite, TSP, logistics, EAs, benchmarking, local search, more infos.
Yuezhong WU (吴越钟), Thomas Weise (汤卫思), and Weichen LIU (刘伟臣): Hybridizing Different Local Search Algorithms with Each Other and Evolutionary Computation: Better Performance on the Traveling Salesman Problem. 18th Genetic and Evolutionary Computation Conference (GECCO'2016), Denver, Colorado, USA, July 20-24, 2016, pages 57-58, New York, NY, USA: ACM.
TSP Suite, TSP, logistics, local search, more infos.
Weichen LIU (刘伟臣), Thomas Weise (汤卫思), Yuezhong WU (吴越钟), Dan XU (许丹), and Raymond Chiong: An Improved Ejection Chain Method and Its Hybrid Versions for Solving the Traveling Salesman Problem. Journal of Computational and Theoretical Nanoscience 13(6):3601-3610. June 2016.
TSP Suite, TSP, logistics, local search, more infos.
Chao GAO, Xin YAO (姚新), Thomas Weise (汤卫思), and Jinlong LI (李金龙): An Efficient Local Search Heuristic with Row Weighting for the Unicost Set Covering Problem. European Journal of Operational Research (EJOR) 246(3):750-761. November 2015.
local search, more infos.
Dan XU (许丹), Thomas Weise (汤卫思), Yuezhong WU (吴越钟), Jörg Lässig, and Raymond Chiong: An Investigation of Hybrid Tabu Search for the Traveling Salesman Problem. 10th International Conference on Bio-Inspired Computing — Theories and Applications (BIC-TA'2015), September 25-28, 2015, Hefei, Anhui, China, Communications in Computer and Information Science, volume 562. Berlin/Heidelberg: Springer-Verlag, pages 523-537.
TSP, TSP Suite, logistics, local search, more infos.
Weichen LIU (刘伟臣), Thomas Weise (汤卫思), Yuezhong WU (吴越钟), and Raymond Chiong: Hybrid Ejection Chain Methods for the Traveling Salesman Problem. 10th International Conference on Bio-Inspired Computing — Theories and Applications (BIC-TA'2015), September 25-28, 2015, Hefei, Anhui, China, Communications in Computer and Information Science, volume 562. Berlin/Heidelberg: Springer-Verlag, pages 268-282.
TSP, TSP Suite, logistics, local search, more infos.
Yuezhong WU (吴越钟), Thomas Weise (汤卫思), and Raymond Chiong: Local Search for the Traveling Salesman Problem: A Comparative Study. 14th IEEE Conference on Cognitive Informatics & Cognitive Computing (ICCI*CC'2015), July 6-8, 2015, Beijing, China, pages 213-220, Los Alamitos, CA, USA: IEEE Computer Society Press.
TSP, TSP Suite, logistics, local search, benchmarking, more infos.
Yan JIANG (江炎), Thomas Weise (汤卫思), Jörg Lässig, Raymond Chiong, and Rukshan Athauda: Comparing a Hybrid Branch and Bound Algorithm with Evolutionary Computation Methods, Local Search and their Hybrids on the TSP. IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS'2014), part of the IEEE Symposium Series on Computational Intelligence (SSCI'2014), December 9-12, 2014, Orlando, FL, USA, pages 148-155. Los Alamitos, CA, USA: IEEE Computer Society Press.
TSP, TSP Suite, logistics, local search, EAs, MAs, more infos.
Chao GAO, Thomas Weise (汤卫思), and Jinlong LI (李金龙): Improve the 3-flip Neighborhood Local Search by Random Flat Move for the Set Covering Problem. Advances in Swarm Intelligence Proceedings of the 5th International Conference on Swarm Intelligence (ICSI'2014), Part 1, October 17-20, 2014, Hefei, Anhui, China, pages 27-35, Lecture Notes in Computer Science (LNCS), volume 8794. Berlin, Germany: Springer-Verlag GmbH.
local search, more infos.
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.
TSP, TSP Suite, logistics, local search, EAs, MAs, ACO, EDAs, FFA, more infos.
Chao GAO, Thomas Weise (汤卫思), and Jinlong LI (李金龙): A Weighting-Based Local Search Heuristic Algorithm for the Set Covering Problem. IEEE Congress on Evolutionary Computation (CEC'2014), part of the World Congress on Computational Intelligence (WCCI'2014), pages 826-831, July 6-11, 2014, Beijing, China. Los Alamitos, CA, USA: IEEE Computer Society Press.
local search, more infos.
Thomas Weise (汤卫思) and Raymond Chiong: A Novel Extremal Optimization Approach for the Template Design Problem. International Journal of Organizational and Collective Intelligence (IJOCI) 2(2):1-17. April-June 2011.
local search, packing, more infos.
Raymond Chiong, Thomas Weise (汤卫思), and Bee Theng Lau: Template Design using Extremal Optimization with Multiple Search Operators. International Conference on Soft Computing and Pattern Recognition (SoCPaR'2009), December 4-7, 2009, Malacca, Malaysia, pages 202-207. Piscataway, NJ, USA: IEEE.
packing, local search, more infos.
Thomas Weise (汤卫思): Global Optimization Algorithms — Theory and Application. self-published, free e-book. 2009.
optimization, metaheuristics, local search, GP, more infos.

Thomas Weise (汤卫思)