🤖 AI

A New Approach to Characterising Optimisation Problems Using Programmatic Representation and Complexity Measures

This paper proposes a novel approach to characterizing optimization problems by calculating the Halstead volume and entropy of their programmatic implementations, demonstrating that these code-based complexity measures serve as effective, sampling-free predictive meta-features for algorithm selection.

Original authors: Marcus Gallagher, Katherine M. Malan

Published 2026-08-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Marcus Gallagher, Katherine M. Malan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to solve a maze. Sometimes the maze is a simple, straight hallway; other times, it's a twisting, turning labyrinth with dead ends and traps. In the world of computer science, this is called optimisation: finding the best possible solution to a problem. But here's the tricky part: not all mazes are created equal. Some are easy for a robot to solve, while others make even the smartest algorithms get lost.

To help robots choose the right strategy, scientists try to "characterise" or describe these mazes before the robot even starts running. They look for clues, like how bumpy the ground is or how many dead ends exist. Usually, to find these clues, the robot has to take a few steps, look around, and measure the terrain. This is like sending a scout into the dark to map the cave. But what if the robot could just look at the blueprint of the maze and guess how hard it would be to solve, without ever stepping foot inside? That is the big question this paper asks. It suggests that the way a problem is written in computer code might hold the secret to how difficult it is to solve, just like the complexity of a recipe might hint at how hard the cooking will be.

The Code as a Crystal Ball

In this paper, Marcus Gallagher and Katherine Malan propose a fresh, slightly magical way to look at these difficult problems. Instead of sending a scout to measure the landscape, they suggest we just read the "recipe" the computer uses to create the problem.

Think of an optimisation problem like a video game level. To build the level, a programmer writes code. Some levels are simple: "Move forward, jump over a pit, collect the coin." The code for this is short and uses basic commands. Other levels are chaotic: "If the sky is blue, multiply your speed by the number of stars, then subtract the square root of your health, but only if you are wearing a hat." The code for this is long, messy, and uses a huge variety of commands.

The authors' big idea is this: The messier and more complex the code is, the harder the problem is for an algorithm to solve.

They borrow two tools from the world of software engineering to measure this "messiness."

Halstead Volume: Imagine counting every single word and symbol in a paragraph. If you have a short story with simple words, the count is low. If you have a novel with complex vocabulary and long sentences, the count is high. This measure counts the "operators" (like math symbols) and "operands" (like numbers and variables) in the code.
Shannon Entropy: This is a bit like measuring the surprise factor. If a paragraph uses the same five words over and over, it's predictable (low entropy). If it uses a huge variety of unique words in a random order, it's unpredictable (high entropy).

The Experiment: From Simple Circles to Chaotic Peaks

To test their theory, the authors took a famous set of 24 test problems used by scientists all over the world (known as the BBOB suite). These range from the "Sphere" function (a perfectly smooth, round hill that is easy to roll down) to the "Lunacek bi-Rastrigin" function (a jagged, rocky landscape with thousands of tiny peaks and valleys).

They wrote down the computer code for each of these 24 problems and ran their "messiness" calculators on them. The results were exactly what they hoped for:

The simple, smooth Sphere function had the lowest complexity scores.
The jagged, difficult Lunacek function had the highest complexity scores.
In fact, the Lunacek function was about 9.3 times more complex in its code structure than the Sphere function.

They even tested this on a different kind of problem: training a neural network (a type of AI brain). They found that the code for a network using a "Tanh" activation function was slightly more complex than one using "ReLU," and this matched the idea that the Tanh version is a slightly harder puzzle to solve.

The Magic Connection: Code Complexity Predicts Performance

The real magic happens when they compare these code scores to how well different algorithms actually performed. They looked at data from five different "robot" algorithms trying to solve these 24 problems.

They found a clear pattern: The more complex the code, the worse the robots performed.

It's a negative relationship. When the code was simple (low Halstead volume), the robots solved the problem quickly and easily. When the code was complex (high Halstead volume), the robots struggled, took longer, or got stuck. For example, in 5-dimensional problems, the connection between code complexity and poor performance was quite strong.

However, the authors are careful to note that this isn't a perfect crystal ball. There were a few "outlier" problems where the code was very complex, but the robots didn't perform quite as badly as the code suggested. This suggests that while code complexity is a great hint, it's not the only thing that matters.

Why This Matters

The beauty of this approach is that it's incredibly fast and requires no extra work. Traditional methods to understand a problem often involve running the algorithm thousands of times just to see how the landscape looks. This is like sending a scout to walk the entire maze just to draw a map.

In contrast, the authors' method is like looking at the blueprint of the maze. You can calculate the complexity of the code in a split second, without running the problem once. It doesn't care about the size of the problem or how many dimensions it has; it just looks at the structure of the instructions.

The authors suggest that this new "code complexity" measure could be a helpful addition to the toolbox of scientists who design algorithms. It doesn't replace the old ways of looking at problems, but it adds a new, super-fast way to guess how hard a problem will be before you even start solving it. It's a promising step toward helping computers choose the right tool for the job, simply by reading the instructions.

Technical Summary: Characterising Optimisation Problems Using Programmatic Representation

Problem Statement
Characterising optimisation problem instances is fundamental to understanding algorithm behaviour, facilitating algorithm selection, and configuring optimisers. Existing approaches, such as Exploratory Landscape Analysis (ELA), rely on sampling the search space to extract features. However, these methods face practical limitations: they consume expensive objective function evaluations, are sensitive to sample size and strategy, and may fail to provide robust representations of complex landscapes. Furthermore, different feature sets often provide complementary rather than overlapping information, suggesting a need for diverse characterisation approaches.

Methodology
The authors propose a novel approach that characterises optimisation problems based on the programmatic representation of their objective functions, rather than sampling the search space. The core intuition is that the complexity of the code required to implement an objective function correlates with the complexity of the resulting search landscape. Simple mathematical structures yield simple code and smooth landscapes, while complex functions require longer, more operator-heavy code and manifest as irregular landscapes.

The study utilises two specific measures of program complexity derived from software engineering and information theory:

Halstead Volume ( $V_H$ ): A measure of program size and complexity defined as $V_H = (N_1 + N_2) \log_2(\eta_1 + \eta_2)$ , where $N$ represents the total number of operators/operands and $\eta$ represents the number of distinct operators/operands.
Shannon Entropy ( $H$ ): A measure of information content per token, scaled by the total number of tokens ( $N$ ). The authors note that under uniform probability assumptions, $H$ approximates $V_H$ .

These metrics are calculated statically from the source code (specifically C implementations) of objective functions. The study evaluates these measures on:

The BBOB (Black-Box Optimisation Benchmarking) noiseless test suite (24 functions).
Neural network weight optimisation tasks (training feed-forward networks with ReLU and Tanh activation functions).

Key Contributions and Results

Static, Sampling-Free Characterisation: The proposed method requires no sampling of the search space and no objective function evaluations. It is invariant to transformations (e.g., rotation, conditioning) and problem dimensionality (as dimensionality is treated as a loop count or single operand in the code structure).
Correlation with Algorithm Performance: When applied to the BBOB suite, the Halstead volume and entropy were found to be negatively correlated with algorithm performance (measured by the normalized Area Under the Curve of the empirical cumulative distribution function).
- Higher complexity values (e.g., for $f_{24}$ , Lunacek bi-Rastrigin) corresponded to lower algorithm performance.
- Lower complexity values (e.g., for $f_1$ , Sphere) corresponded to higher performance.
- Spearman's rank correlation coefficients were negative across all tested algorithms (dCMA, COBYLA, DE, mCMA, L-SHADE) and dimensions (2D and 5D), though the strength of correlation varied (ranging from weak to moderate).
Differentiation of Problem Types: The measures successfully distinguished between problem classes. For instance, in neural network training, the complexity metrics differentiated between networks using ReLU versus Tanh activation functions, aligning with previous findings that activation functions are key differentiators in landscape features, independent of the specific regression task or network size.
Limitations Observed: The metrics did not capture specific problem parameters that do not alter the code structure significantly, such as the number of peaks in the Gallagher functions ( $f_{21}, f_{22}$ ) or the dimensionality of the problem. Additionally, outliers with very high $V_H$ values (e.g., $f_7, f_{21}, f_{22}, f_{24}$ ) showed a less clear trend in the scatter plots of complexity vs. performance.

Significance and Claims
The paper positions these programmatic complexity measures as complementary to existing landscape analysis approaches rather than a replacement. The authors claim the approach offers distinct advantages:

Efficiency: It is very quick to calculate automatically.
Invariance: It is invariant to search space transformations and does not depend on sampling strategies.
Predictive Potential: The negative correlation with algorithm performance suggests these measures have potential as predictive meta-features for algorithm selection and configuration.

The authors conclude that while programmatic representation cannot capture every property of a problem landscape relevant to performance, it provides a unique, static perspective that avoids the computational overhead of sampling. They suggest future work should explore these measures on real-world problems involving extensive code execution (e.g., numerical simulations) and investigate their utility in improving algorithm selection "wizards."

The Code as a Crystal Ball

The Experiment: From Simple Circles to Chaotic Peaks

The Magic Connection: Code Complexity Predicts Performance

Why This Matters

Technical Summary: Characterising Optimisation Problems Using Programmatic Representation

More like this