Abstract: Heuristic algorithms are able to optimize objective functions efficiently because they use intelligently the information about the objective functions. Thus, information utilization is critical to the performance of heuristics. However, the concept of information utilization has remained vague and abstract because there is no reliable metric to reflect the extent to which the information about the objective function is utilized by heuristic algorithms. In this paper, the metric of information utilization ratio (IUR) is defined, which is the ratio of the utilized information quantity over the acquired information quantity in the search process. The IUR proves to be well-defined. Several examples of typical heuristic algorithms are given to demonstrate the procedure of calculating the IUR. Empirical evidences on the correlation between the IUR and the performance of a heuristic are also provided. The IUR can be an index of how finely an algorithm is designed and guide the invention of new heuristics and the improvement of existing ones.
Introduction
In the field of heuristic optimization—encompassing Genetic Algorithms, Particle Swarm Optimization, and Evolution Strategies—researchers often characterize certain algorithms as being "better designed" or "more intelligent" than others. Historically, these characterizations have been largely empirical, based on performance benchmarks rather than theoretical quantification. While it is understood that an algorithm acquires information every time it evaluates a point on a landscape, there has been no formal way to measure how much of that data is actually utilized to guide the search process versus how much is discarded.
This paper introduces the Information Utilization Ratio (IUR), a metric derived from Shannon’s Information Theory, to quantify the efficiency of information processing within heuristic algorithms. By defining a formal relationship between acquired and utilized information, the IUR provides a theoretical framework to explain performance disparities between algorithms.
The IUR Framework
To define the IUR, we must first establish a formal structure for heuristic optimization. As shown in Algorithm 1, a typical heuristic iteratively samples points, evaluates them, and updates its internal state based on the results.
The IUR is defined as the ratio of Utilized Information Quantity to Acquired Information Quantity.
- Acquired Information: This is the entropy of the evaluation values ($Y_i$) the algorithm observes. It represents the raw data gained from the objective function.
- Utilized Information: This is the entropy of the algorithm's "action"—specifically, the change in its internal state or sampling distribution ($Z_i$) based on those evaluations.
As illustrated in Figure 1, the process involves a cycle where the current distribution $Z_i$ leads to samples $X_i$, which yield evaluations $Y_i$. These evaluations, along with the structure of the objective function, are then used to generate the subsequent distribution $Z_{i+1}$. The IUR measures how effectively the entropy in $Y_i$ is translated into the update for $Z_{i+1}$.
Theoretical Analysis of Heuristics
The authors derived IUR formulas for several classic algorithms, revealing a spectrum of information efficiency:
- Monte Carlo Sampling: IUR = 0. Because it ignores all previous results to sample the next point, it utilizes zero information.
- Luus-Jaakola (LJ): This algorithm uses simple "better or worse" comparisons, resulting in a low but non-zero IUR.
- $(\mu, \lambda)$-Evolution Strategy (ES): This utilizes the identity of the best individuals, increasing its IUR.
- CMA-ES: By utilizing both the identity and the rankings of the best individuals, CMA-ES achieves a significantly higher IUR, theoretically explaining its superior performance in complex landscapes.
One notable theoretical insight is the "0.5 Rule" in Evolution Strategies. The paper provides a mathematical explanation for why setting the number of parents ($\mu$) to roughly half the offspring ($\lambda$) is often optimal: this ratio maximizes the information entropy of the selection process, thereby maximizing the IUR.
Key Results and Empirical Validation
To validate the IUR metric, the authors utilized the CEC 2013 single objective optimization benchmark suite, which includes 28 functions ranging from simple unimodal landscapes to complex composition functions.
The experimental results confirmed a strong correlation between IUR and algorithmic performance. Specifically:
- CMA-ES vs. ES: The theoretical prediction that $IUR_{CMA-ES} \ge IUR_{(\mu, \lambda)-ES}$ was mirrored in the benchmarks, where CMA-ES outperformed standard ES on 14 out of 28 functions.
- Performance Correlation: Across various parameter settings, the average ranking of an algorithm's performance closely tracked its IUR curve. As the IUR increased, the optimization error generally decreased.
Conclusion
The Information Utilization Ratio (IUR) serves as a "performance ceiling" for heuristic algorithms. While a high IUR does not guarantee success (as information could be used incorrectly), a high-performance algorithm cannot exist without a high IUR. This metric allows researchers to move beyond trial-and-error design, providing a formal index to evaluate how finely an algorithm is constructed and guiding the development of more information-efficient optimization techniques.
Summary updated