Thomas Weise (汤卫思)

A professor at Hefei University.

12 minute read

Frequency Fitness Assignment (, 频率适应度分配) 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 for short. We plug FFA into this algorithm and obtain the . We finally list some properties of FRLS as well as some related works.

Optimization

If we try to solve an optimization problem, then we have at least the following components available:

  • a data structure called the solution space $\mathbb{X}$, which contains the possible candidate solutions $x\in\mathbb{X}$,
  • the objective function $f:\mathbb{X}\mapsto\mathbb{R}$, which rates the candidate solutions and which we here consider to be subject to minimization, i.e., smaller values are better, i.e., $f(x_1)<f(x_2)$ means that $x_1$ is better than $x_2$, and
  • some way to instantiate the data structure $\mathbb{X}$, usually either fully randomly or by copying and slightly (randomly) an existing instance $x$.

We then try to find the values $x^{\star}$ for which the objective function $f$ takes on the smallest possible value. Of course, finding such points is very hard and may not be possible within reasonable time if $\mathbb{X}$ is big. Therefore, at least we try to find some $x$ for which $f(x)$ gets as small as possible.

Metaheuristic Optimization

Metaheuristic algorithms, like Evolutionary Algorithms (), , Simulated Annealing (), or do this by proceeding iteratively according to the cycle given in Algorithm 1. At each iteration $i$, they maintain a collection $S_i$ of interesting candidate solutions $x\in S_i$ from the solution space $\mathbb{X}$. They use these selected solutions in one way or another to sample a collection $N_i$ of new solutions. This may happen via a unary search operator (called “mutation” in EA-lingo) or a binary operator (often called “crossover” or “recombination”) or by using any other imaginable method. Either way, we get a collection of new solutions $N_i$. Then, $S_i$ and $N_i$ are combined into a collection $P_i=S_i\cup N_i$ and the collection $S_{i+1}\subseteq P_i$ for the next iteration is chosen from it. Now, normally, the better a solution $x\in P_i$ relative to the other members of $P_i$, meaning the smaller its corresponding objective value $f(x)$, the higher its chance to be selected into $S_{i+1}$.

Algorithm 1. The normal cycle of metaheuristic algorithms.
Sample collection $S_1$ of initial solutions from the solution space $\mathbb{X}$.
For $i$ from 1 to$\dots$
 Create collection $N_i$ of new solutions based on $S_i$.
 $P_i\gets S_i\cup N_i$.
 Select collection $S_{i+1}$ from $P_i$ according to some policy.

And this makes a lot of sense. This is how trial-and-error works: We try different solutions for problem and look how good they work. Then we continue with slightly modified versions the solution that we liked best in order to find even better. This iterative procedure of trial and error with a bias for better solutions is foundation of metaheuristic optimization.

Frequency Fitness Assignment () is a technique that breaks with this bias. It thus redefines how we do metaheuristic optimization. FFA is a modification that can be introduced into existing algorithms. In order to see how that works, we first look at one concrete metaheuristic method and then plug FFA into it.

Randomized Local Search (RLS)

Let us thus consider the simplest metaheuristic, namely Randomized Local Search (). RLS begins by sampling one candidate solution $x_c$ from the solution space $\mathbb{X}$ uniformly at random. It computes the objective value $y_c$ of $x_c$ by evaluating the objective function $f:\mathbb{X}\mapsto\mathbb{R}$. Let’s assume that $f$ is subject to minimization, i.e., represents some sort of cost or amount of consumed resource. $y_c\gets f(x_c)$ then is the quality of the current solution $x_c$ and $x_c$ is the better, the smaller $y_c$ is. In the scheme given in Algorithm 1, we would basically have $S_i={x_c}$.

Now, in its main loop, RLS creates a slightly modified copy $x_n$ of the $x_c$. It does so by applying a unary operator $\mathit{op1}$ to $x_c$. $\mathit{op1}$ is usually randomized, meaning that it first copies $x_c$ and then randomly changes one or multiple components of that copy. Either way, we get a new solution $x_n\gets\mathit{op1}(x_n)$. This solution is then also evaluated and we obtain its objective value $y_n\gets f(x_n)$. In the scheme given in Algorithm 1, we would basically have $N_i={x_n}$.

In its selection step, RLS retains $x_n$ if it is not worse than $x_c$. This means that, if $y_n\leq y_c$, $x_c\gets x_n$ and $y_c\gets y_n$. After the complete computational budget is exhausted, the algorithm returns the best solution that it has discovered (namely $x_c$) as well as its quality $y_c$. This process is illustrated as Algorithm 2.

Algorithm 2. The randomized local search (RLS).
Sample solution $x_c$ uniformly at random from $\mathbb{X}$.
$y_c\gets f(x_c)$.
Until $\lnot$ should terminate repeat
 $x_n\gets\mathit{op1}(x_c)$; $y_n\gets f(x_n)$.
 If $y_n \leq y_c$ then
 $x_c\gets x_n$; $y_c\gets y_n$.
Return $x_c, y_c$.

Randomized Local Search with FFA (FRLS)

Now let’s plug FFA into the RLS algorithm and we obtain the . We first provide FRLS as Algorithm 3 and then discuss it step-by-step. It should be noted upfront that this algorithm will only work if the objective function is discrete, i.e., takes on a finite (and ideally small) number of different values.

Algorithm 3. The randomized local search with FFA, i.e., the FRLS algorithm.
$H\gets (0, 0, \dots, 0)$.
Sample solution $x_c$ uniformly at random from $\mathbb{X}$.
$y_c\gets f(x_c)$.
$x_b\gets x_c$; $y_b\gets y_c$.
Until $\lnot$ should terminate repeat
 $x_n\gets\mathit{op1}(x_c)$; $y_n\gets f(x_n)$.
 $H[y_c]\gets H[y_c]+1$; $H[y_n]\gets H[y_n]+1$.
 If $H[y_n] \leq H[y_c]$ then
 $x_c\gets x_n$; $y_c\gets y_n$.
 If $y_n < y_b$ then
 $x_b\gets x_n$; $y_b\gets y_n$.
Return $x_b, y_b$.

Let us first discuss the core changes when transitioning to FFA, which are marked with violet color. The algorithm now uses a frequency table $H$. $H$ counts how often each objective value was encountered during the selection step. It could be implemented a simple array or a hash map. We denote the initialization of this data structure by symbolically writing $H\gets (0, 0, \dots, 0)$.

The creation and evaluation of the initial solution $x_c$ and the new solution $x_n$ sampled in each iteration stay exactly the same. However, before the selection step, i.e., before we decide which of the two we want to keep, a new line appears: $H[y_c]\gets H[y_c]+1$ and $H[y_n]\gets H[y_n]+1$ increment the frequency counters of the objective values $y_c$ and $y_n$ of $x_c$ and $x_n$, respectively. In other words, $H[y_c]$ now represents how often a solution with objective value $y_c$ took place in the selection. And, of course, $H[y_n]$ now represents how often a solution with objective value $y_n$ took place in the selection.

The selection decision is also changed: Instead of comparing $y_n\leq y_c$, we now compare $H[y_n] \leq H[y_c]$. If this comparison yields true, then $x_n$ replaces $x_c$ and $y_c$ is overwritten with $y_n$. What does this mean? In RLS, we select the new solution $x_n$ if it is either better than the current solution $x_c$ or equally good. In FRLS, we select the new solution $x_n$ if its objective value $y_n$ was encountered more rarely or equally often in the selection decisions compared to the objective value $y_c$ of the current solution $x_c$. From a simplified perspective, this means that we accept the new solution if its objective value appears to be more rare than the objective value of the current solution.

This means that, in FRLS, it does not really matter whether the new solution is better than the current solution. Indeed, the algorithm may well accept worse solutions and in experiments “optimizes” into the “wrong” direction about half of the time. This waste of time facilitates its exploration capability, though.

It also means that the best solution that this algorithm discovers is likely to get lost and overwritten. This can never happen in RLS. But in FRLS, it can. And thus, we need the blue part. We remember the best-ever encountered solution in an additional variable $x_b$ and its objective value in a variable $y_b$. These two values are returned when the algorithm has finished, e.g., exhausted its computational budget. They are initialized right at the beginning of the algorithm. We check whether they should be updated when $H[y_n] \leq H[y_c]$, because only if $y_n$ was encountered less often than $y_c$, it can represent a new best-so-far solution. Otherwise, it has been encountered already at least once before, so it might have corresponded to a new best-so-far solution back then, but not now.

Neither $x_b$ nor $y_b$ influence the search in any way. They are strictly used to remember the best-so-far solutions, but have no impact on where the search will take us next. That is entirely decided by the frequency table $H$.

Basic References

Bit-String based Search Spaces

First, let us consider the problem type where all solutions $x$ are bit strings of length $n$.

  • 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.
    , , , 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.
    , , , , more infos.

In the two papers above, we introduce FFA into the (1+1) EA. The RLS and the (1+1) EA are basically the same algorithm but differ in their unary search operator $\mathit{op1}$. Usually, when we talk about the (1+1) EA, the search or solution space $\mathbb{X}$ corresponds to bit strings of length $n$, i.e., ${0,1}^n$. Here, each decision variable is either 0 (meaning False) or 1 (meaning True). When we consider this domain, the terms “RLS” and “(1+1) EA” have the following meaning:

  • In the RLS, the unary operator $\mathit{op1}(x_c)$ creates a copy of $x_c$, then randomly chooses one bit and flips it.
  • In the (1+1) EA, the unary operator $\mathit{op1}(x_c)$ creates a copy of $x_c$ and then, for each of the $n$ bits, decides randomly whether it should be flipped. Usually, the per-bit flipping probability is $1/n$. Usually, it is ensured that at least one bit is flipped.

Otherwise, both algorithms have exactly the same procedure as detailed in Algorithm 2. Either way, we plugged FFA into this (1+1) EA and obtained the (1+1) FEA, which is basically equivalent to the Algorithm 3. And then we did lots of experiments with it. And found that it actually works quite well. And more you can read in the papers.

Other Domains

If the search domain is not bit strings, then we can use the terms RLS and (1+1) EA more or less synonymously. Sometimes, one may use “RLS” to indicate that the search operator $\mathit{op1}(x_c)$ has a fixed neighborhood from which solutions are sampled uniformly. Then, “(1+1) EA” may be used for situations where basically every possible solution can be reached within a single step, albeit at different probabilities.

Some examples, i.e., a subset of our work on FFA, can be found here:

  • Permutations: The Search Space $\mathbb{X}$ corresponds to permutations of the first $n$ natural numbers.
    • Traveling Salesperson Problem ()
    • Quadratic Assignment Problem (QAP)
      • 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.
        , , , , , , 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.
        , , , , , , , , more infos.
    • Traveling Tournament Problem ()
      • 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.
        , , , , , , , , more infos.
  • Permutations with Repetitions: Each one of the first $n$ natural numbers occurs exactly a per-number specific amount of times in the permutations.
    • Job Shop Scheduling Problem(JSSP)
      • 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.
        , , , , 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.
        , , , , more infos.
    • Two-Dimensional Bin ()

Features of FRLS

The has several interesting features.

  1. Its search is unbiased. The probability of being selected of a solution depends on how often its objective value has entered the selection stage before. It does not depend on whether the objective value is good or bad.
  2. The path that the algorithm takes through the search space remains the same if we replace $f(x)$ with any $g(f(x))$ as long as $g$ is an injective function. The objective values are only used as indices into the frequency table $H$. It does not matter whether they are high or low, only their identity matters.
  3. Since the FRLS algorithm does not care whether a solution is good or bad, it tends to optimize into the “wrong direction” half of the time and oscillate between searching good and bad solutions.
  4. This makes the search much slower, but it also adds a very strong explorative character.
  5. If there are many different possible objective values, the search will degenerate to a random walk. FRLS can only work if there is only a relatively small set of possible objective values.

More

Here you can learn more about FFA and the latest research that we do on this odd topic. We also provide implementations of the (1+1) EA/RLS as well as of the (1+1) FEA/FRLS in our Python framework .

You May Also Enjoy

Updating all Packages and Snaps

2 minute read

I use for my work and try to keep my system up-to-date. This means that, whenever I shut down my computer, I run a little Here I post a small script update.sh that updates all installed packages, both deb and snap packages. Sometimes, for whatever reason, there may be a problem with some inconsistent package state. My script basically applies all methods I know to fix such state. The script is very heavy-handed and loops over the update process four times. If for whatever reason one update would require another first and that could only be done by multiple updates, then that’s no problem. I usually run something like sudo update.sh && shutdown now, which then shuts down my computer. So I do not really need to care how long the script needs anyway.

Repeating a Command until it Succeeds under Linux

2 minute read

Assume that we have a command that we want to execute in a terminal. We know that the command may sometimes fail, but it should actually succeed. So we would try the command again and again until this happens. An example is, for instance, a download process. If we know that the URL is reachable, then the command should succeed. However, maybe there is a lost connection or other temporary disturbance. Another such command could be a build process which downloads and installs dependencies.

Recursively Deleting Empty Files and Directories under Linux

1 minute read

Sometimes, we have the need to delete empty files and empty directories under . This happens, for example, when we want to restart an experiment with . Here I post a small script that you may store as file deleteZeroSizedFiles.sh. It will do exactly that: It will search the current directory and all subdirectories for empty files, i.e., files of size zero. It will delete all of them. Then, it will recursively look for empty directories, i.e., directories that do not contain files or other directories. It will delete them as well.