(373l) Enhancing Stochastic Optimization through Topology Data Analysis: A Novel Approach for Improved Efficiency and Robustness

Stochastic optimization techniques, in contrast to deterministic approaches, offer a high degree of adaptability across various problem domains. They can be adopted to complex, non-linear, and multi-modal objective functions and avoid local optima without explicit mathematical formulations [1-2]. However, stochastic optimization methods face challenges related to parameter sensitivity, requiring fine-tuning of parameters like exploration and exploitation weights in Particle Swarm Optimization [1] or temperature and cooling rate in Simulated Annealing [2] for optimal results. Verifying convergence can be difficult due to their stochastic nature, especially for problems with complex landscapes. To address these issues, our study proposes integrating Topology Data Analysis (TDA) [3] into stochastic optimization methods to enhance their effectiveness.

TDA enhances stochastic optimization techniques by utilizing the inherent topological structure of the search domain. Persistence diagrams [4], graphical representations in TDA, track the lifespan of topological features such as connected components, loops, and voids, capturing essential features across different scales. Additionally, we employ Restricted Gaussian kernel density estimation [5], derived from the persistence diagram, where higher-density regions correspond to areas with more persistent topological features. These features guide the optimization process towards regions with higher topological feature density, usually align with optimal solution locations, improving efficiency and robustness.

Two stochastic methods, Simulated Annealing (SA) and Particle Swarm Optimization (PSO), have been integrated with TDA to demonstrate the utilization of topology information. In SA, the integration of TDA serves as a navigational aid, guiding the stochastic search process toward regions with the most long-lasting topological features. This strategic guidance significantly reduces the chances of converging on suboptimal solutions, especially as the temperature parameter approaches zero. At this point, SA's behavior becomes more akin to a deterministic local search, similar to Monotonic Basin-Hopping [6]. Through utilizing TDA, SA is better equipped to identify and explore promising areas, enhancing its ability to find optimal solutions. In the case of PSO, we utilized the concept of restricted Gaussian kernel density estimation, derived from TDA, to dynamically change the social coefficient (c2) controlling the exploration stage. This approach adjusts the balance between exploration and exploitation based on the density of topological features identified across the search space. High-density regions, indicative of significant topological structures, signal the presence of potentially optimal solutions. Consequently, by increasing the weight of the social coefficient (c2) in these areas, the swarm is encouraged to collectively converge towards these high-interest regions. This strategic adjustment enhances the algorithm's ability to navigate complex landscapes and improves overall optimization efficacy by focusing collective search efforts on promising areas identified through TDA.

We assess the effectiveness of topology-enhanced optimization methods across eight numerical problems [7], spanning low and high-dimensional spaces with various shapes such as Bowl-Shaped, Plate-Shaped, Valley-Shaped, and multiple Local Minima. The findings reveal significant improvements in efficiency and robustness compared to traditional stochastic optimization techniques. Integrating topology features into SA reduces the risk of being trapped at local optima, while dynamically adjusting the exploration-exploitation balance in PSO enhances its performance.

References

[1] Kennedy, J., & Eberhart, R. (1995, November). Particle swarm optimization. In Proceedings of ICNN'95-international conference on neural networks (Vol. 4, pp. 1942-1948). ieee.

[2] Aarts, E., Korst, J., & Michiels, W. (2005). Simulated annealing. Search methodologies: introductory tutorials in optimization and decision support techniques, 187-210.

[3] Dey, T. K., & Wang, Y. (2022). Computational topology for data analysis. Cambridge University Press.

[4] Berry, E., Chen, Y. C., Cisewski-Kehe, J., & Fasy, B. T. (2020). Functional summaries of persistence diagrams. Journal of Applied and Computational Topology, 4(2), 211-262.

[5] Maroulas, V., Mike, J. L., & Oballe, C. (2019). Nonparametric estimation of probability density functions of random persistence diagrams. Journal of Machine Learning Research, 20(151), 1-49.

[6] Baioletti, M., Santucci, V., & Tomassini, M. (2024). A performance analysis of Basin hopping compared to established metaheuristics for global optimization. Journal of Global Optimization, 1-30.

[7] Surjanovic, S., & Bingham, D. (2013). Virtual Library of Simulation Experiments: Test Functions and Datasets. Retrieved from https://www.sfu.ca/~ssurjano/index.html