Chapter 1: Introduction to Global Optimization

Global optimization algorithms are a critical area of applied mathematics and numerical analysis focused on efficiently finding the global minima or maxima of a function ( f(x) ) within a specified hyper-space. These algorithms initiate their processes by generating a randomly sampled population of ( N ) individuals, each of dimension ( D ). Each individual serves as a potential solution to the optimization challenge at hand.

Research indicates that the initial spatial distribution of candidate solutions can significantly influence the optimization algorithm's efficiency. Much like the butterfly effect in chaos theory, minor changes during the initialization phase can lead to vastly different results.

In this article, we will explore a specific type of "random" number generator that can improve the convergence rate of optimization algorithms towards the global optimum. When I began developing Evolutionary Algorithms, I was initially skeptical about the impact of this straightforward technique. However, it soon became evident that the butterfly effect also applies to global optimization challenges, leading us into the fascinating realm of randomness.

> "Welcome to the chaotic and beautiful world of randomness."

Chapter 2: The Nature of Randomness in Computers

In our chaotic universe, randomness is omnipresent, yet accurately simulating it in computer programs is challenging. Standard computers are inherently deterministic, meaning they produce the same output for identical inputs. While random values are commonly used for tasks like statistical analysis and random selections, achieving true randomness—akin to physical objects like dice or coins—is difficult in computational settings.

Computers generate random numbers through mathematical algorithms, which can lead to patterns that diminish true randomness over time. Although physical processes can yield genuine random numbers, computers primarily produce pseudo-random numbers, which are not entirely random but rather appear to be so.

Thus, while we can strive for unpredictability, true randomness remains an elusive goal in computational contexts.

Chapter 3: Limitations of Pseudo-Random Numbers

In population-based global optimization algorithms—such as PSO, CMA-ES, GA, and DE—the initial sampling of ( N ) individuals from a uniform probability distribution ( U(0,1) ) using a pseudo-random number generator often results in sparse distributions in certain areas.

This sparse distribution is a significant drawback of pseudo-random numbers, as they fail to uniformly fill the sampled hyper-space. This inefficiency can severely hinder optimization performance. However, there is a straightforward solution: quasi-random numbers, which can alleviate the uneven distribution seen with pseudo-random numbers.

Section 3.2: The Halton Sequence and Hammersley Set

The Halton sequence and the Hammersley set provide deterministic methods for sampling a ( D )-dimensional space, ensuring that consecutive points are spaced as widely apart as possible.

To illustrate, the Halton sequence generalizes the Van der Corput sequence to multiple dimensions by utilizing different prime bases for each axis.

Both these sequences serve as foundational examples of low-discrepancy generators and can significantly impact optimization algorithms.

Chapter 4: The Sobol Sequence

Another prominent quasi-random generator is the Sobol sequence, developed by Ilya M. Sobol in 1967. This sequence creates uniform partitions of the interval ( [0, 1] ) and then applies a specific reordering for each dimension of the sampled hyper-space.

When comparing the Sobol sequence to pseudo-random samples, it becomes clear that Sobol sequences cover the space more effectively.

Chapter 5: Application in Particle Swarm Optimization (PSO)

To demonstrate the impact of initialization strategies on optimization performance, we will analyze the Particle Swarm Optimization (PSO) algorithm. We will compare three initialization methods:

1. U-PSO: Uniform initialization with a pseudo-random generator.
2. H-PSO: Initialization with a Halton sequence.
3. S-PSO: Initialization with a Sobol sequence.

The evaluation metric will be the average number of function evaluations needed to locate the global minimum across various dimensions ( D = 10, 20, 30 ).

The first video discusses how to tackle challenging global optimization problems.

The results demonstrate that S-PSO consistently outperformed U-PSO and H-PSO, indicating the effectiveness of quasi-random sequences in enhancing optimization performance.

The second video explores global optimization techniques using Python.

Chapter 6: Conclusion

In summary, transitioning from pseudo-random to quasi-random initialization can enhance the performance of optimization algorithms. Implementing this straightforward approach involves replacing calls to the rand() function with a low-discrepancy sequence generator.

While this adjustment may not guarantee improvements in every scenario, it is certainly worth exploring, as it does not detract from the optimizer's overall effectiveness.

References

[1] Maaranen, H., Miettinen, K., & Mäkelä, M. M. (2004). A Quasi-Random Initial Population for Genetic Algorithms. Computers and Mathematics with Applications, 47, 1885–1895.

[2] Morokov, W. J., & Caflish, R. E. (1994). Quasi-random sequences and their discrepancies. SIAM J. Sci. Comput., 15(6), 1251-1279.

[3] Mascagni, M., & Chi, H. (2004). On the scrambled Halton sequence. Monte Carlo Methods Appl., 10(3), 435–442.

[4] van der Corput, J.G. (1935). Verteilungsfunktionen. I. Mitt. Proc. Akad. Wet. Amsterdam, 38, 813–821.

[5] Pausinger, F., & Topuzoglu, A. Van der Corput sequences and permutation polynomials. Preprint.