Information Utilization Ratio in Heuristic Optimization Algorithms

Junzhi Li, Ying Tan

TL;DR

This paper introduces the "Information Utilization Ratio" (IUR), a novel metric to quantify how effectively heuristic optimization algorithms leverage information about the objective function. By defining and calculating IUR for various algorithms, the authors demonstrate its strong correlation with performance, suggesting it can guide the design and improvement of future optimization techniques.

What Problem Does This Paper Address?

Heuristic optimization algorithms are widely used to tackle complex problems where finding exact solutions is infeasible. The effectiveness of these algorithms hinges on their ability to intelligently use information about the objective function. However, the concept of "information utilization" has remained vague and abstract, lacking a reliable, quantifiable metric. This makes it difficult to objectively assess how well an algorithm is designed or to guide the development of more efficient ones. While performance is the ultimate goal, understanding why an algorithm performs well (or poorly) often comes down to how it processes and uses available data.

Methods

The core contribution of this paper is the formal definition of the Information Utilization Ratio (IUR). Drawing from information theory, IUR is defined as the ratio of "utilized information quantity" to "acquired information quantity" within the search process.

The authors define key information-theoretic concepts like Information Entropy and Conditional Entropy as foundational elements. They then introduce a specific lemma and function ($\pi(g)$) to aid in calculating IURs.

The paper defines an Optimization Algorithm formally and then presents the Information Utilization Ratio (IUR) formula (Equation 4). This formula, while complex, essentially compares the entropy of the algorithm's actions (what it does with information) to the entropy of the objective function's evaluations (what information it acquires).

To demonstrate the practical application of IUR, the authors calculate it for several well-known heuristic algorithms:

  • Monte Carlo (MC): A baseline, non-heuristic approach.
  • Luus-Jaakola (LJ): A direct search method.
  • (μ, λ)-Evolution Strategy ((μ, λ)-ES): A popular evolutionary algorithm.
  • Covariance Matrix Adaptation Evolution Strategy (CMA-ES): An advanced evolutionary strategy.
  • Particle Swarm Optimization (PSO) and Standard PSO (SPSO): Swarm intelligence algorithms.
  • Differential Evolution (DE) and JADE: Evolutionary algorithms with mutation strategies.

The calculation of IUR for these algorithms involves analyzing how their internal parameters and decision-making processes relate to the information they receive from function evaluations.

Datasets

The paper uses the CEC 2013 benchmark suite for evaluating the performance of the algorithms. This suite contains 28 different test functions, considered representative of black-box optimization problems. The authors do not introduce any new datasets.

Key Insights and Ideas

  • Quantifying "Smartness": The IUR provides a concrete way to measure how "smart" an optimization algorithm is in its use of information, moving beyond subjective assessments.
  • IUR as a Performance Predictor: The paper strongly suggests a positive correlation between a higher IUR and better algorithm performance. Algorithms that utilize information more thoroughly tend to perform better.
  • Guiding Algorithm Design: IUR can serve as a valuable tool for researchers to guide the design of new heuristics and the improvement of existing ones by focusing on mechanisms that increase information utilization.
  • Parameter Tuning: For algorithms with tunable parameters (like (μ, λ)-ES), IUR can help in selecting parameter values that lead to better information utilization and, consequently, better performance, potentially saving significant experimental effort.
  • Understanding Algorithm Families: By comparing IURs within algorithm families (e.g., (μ, λ)-ES vs. CMA-ES), the paper highlights how advancements in design lead to more sophisticated information utilization.
  • Upper Bound for Comparison-Based Algorithms: The paper establishes an upper bound for the IUR of comparison-based algorithms, indicating inherent limitations in how much information can be extracted solely from function value comparisons.

Key Results

  • IUR is Well-Defined: The paper theoretically proves that the defined IUR is well-defined and falls within the range (0, 1].
  • Empirical Correlation: Experiments on the CEC 2013 benchmark suite show that algorithms with higher IURs (like LJ compared to MC, and CMA-ES compared to (μ, λ)-ES) generally exhibit better performance, as evidenced by average rankings and statistical tests.
  • Parameter Influence: For (μ, λ)-ES, the ratio μ/λ significantly impacts IUR, with values around 0.5 yielding higher IURs and better performance.
  • CMA-ES vs. (μ, λ)-ES: CMA-ES, with its rank-based weighted recombination, achieves a higher IUR and superior performance compared to (μ, λ)-ES.
  • PSO Variants: SPSO, with its local ring topology, shows a higher IUR than standard PSO, correlating with its improved performance.
  • DE Variants: JADE demonstrates a higher IUR than basic DE, aligning with its superior performance.

Limitations and Future Work

  • Correlation vs. Causation: While a strong correlation between IUR and performance is observed, the paper acknowledges that the manner of information utilization is also crucial. An algorithm with a high IUR might not perform well if its information usage is not aligned with the objective function's distribution.
  • Complexity of Calculation: Calculating IUR can be complex, especially for the numerator, and the paper suggests that for practical purposes, it might be more feasible to analyze the information required for intermediate parameters.
  • Future Work: The authors suggest extending the IUR metric to other fields in artificial intelligence, such as classification and time series prediction, as an interesting avenue for future research. They also emphasize the need for more theoretical work to fully understand the relationship between information utilization and performance, particularly concerning how different utilization manners fit underlying distributions.

Summary updated

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 sophisticated an algorithm is designed and guide the invention of new heuristics and the improvement of existing ones.
BibTeX
@inproceedings{li2022information,
  author = {Junzhi Li and Ying Tan},
  title = {{Information Utilization Ratio in Heuristic Optimization Algorithms}},
  booktitle = {Icsi},
  year = {2022},
  doi = {10.1007/978-3-031-09677-8\_1},
}
Figure