Un-evaluated Solutions May Be Valuable in Expensive Optimization
Hao Hao, Xiaoqun Zhang, Aimin Zhou · 2024
Read Un-evaluated Solutions May Be Valuable in Expensive Optimization by Hao Hao, Xiaoqun Zhang, Aimin Zhou (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-03858.txt.
Introduction
Hao Hao and co-authors argue that unevaluated solutions still hold value in costly optimization tasks. In such tasks, testing one solution can consume huge resources. Surrogate models stand in for most tests to save cost.
Evolution guided only by tested solutions loses diversity fast. Populations grow too alike across successive generations. That sameness weakens the operators that breed new candidates. The team adds top predicted but untested solutions to selection. Surrogate scores pick which untested candidates join the pool. Better spread then yields stronger next generations. Tests across operators and surrogate types confirm the gain. The trick is cheap and broad in scope. It asks for no new tests and no extra gear, which makes it easy to add to tools that labs already run each day.
Catalog record
| CREATOR | Hao Hao, Xiaoqun Zhang, Aimin Zhou |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-03858
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Un-evaluated Solutions May Be Valuable in Expensive Optimization Hao Hao, Xiaoqun Zhang, Aimin Zhou Abstract Expensive optimization problems (EOPs) are prevalent in real-world applications, where the evaluation of a single solution requires a significant amount of resources. In our study of surrogate-assisted evolutionary algorithms (SAEAs) in EOPs, we discovered an intriguing phenomenon. Because only a limited number of solutions are evaluated in each iteration, relying solely on these evaluated solutions for evolution can lead to reduced disparity in successive populations. This, in turn, hampers the reproduction operators’ ability to generate superior solutions, thereby reducing the algorithm’s convergence speed. To address this issue, we propose a strategic approach that incorporates high-quality, un-evaluated solutions predicted by surrogate models during the selection phase. This approach aims to improve the distribution of evaluated solutions, thereby generating a superior next generation of solutions. This work details specific implementations of this concept across various reproduction operators and validates its effectiveness using multiple surrogate models. Experimental results demonstrate that the proposed strategy significantly enhances the performance of surrogate-assisted evolutionary algorithms. Compared to mainstream SAEAs and Bayesian optimization algorithms, our approach incorporating the un-evaluated solution strategy shows a marked improvement. 1 Introduction Expensive optimization problems (EOPs) are common in various real-world scenarios where assessing a single solution requires a considerable amount of computational resources [ 1 , 2 ] . Evolutionary algorithms (EAs) have gained widespread acceptance for solving a diverse array of problems across different domains, thanks to their ability to perform global searches and adapt to specific problem characteristics [ 3 ] . The assumption in most EAs is that the fitness of all solutions within a population can be evaluated. Typically, this is done using an explicit fitness function, computational simulations [ 4 ] , or through direct experimentation [ 5 ] . Nevertheless, practical challenges arise when fitness evaluations are costly, as seen in EOPs where each assessment demands a resource-intensive simulation or experimental procedure [ 6 ] . Under these conditions, conventional EAs become inefficient, requiring a large number of evaluations to identify an optimal solution. Surrogate-assisted evolutionary algorithms (SAEAs) have been developed to mitigate these inefficiencies. In SAEAs, surrogate models are employed to approximate the true fitness landscape, thereby minimizing the need for expensive solution evaluations. These models serve as estimators for the actual fitness function, enabling the algorithm to efficiently explore the search space. By leveraging surrogate models, SAEAs retain the comprehensive search abilities of traditional EAs while significantly speeding up the optimization process. This makes SAEAs particularly well-suited for tackling intricate real-world problems that have limited computational budgets. The fundamental paradigm of SAEAs involves utilizing surrogate models to predict solution quality before applying the selection operator within the evolutionary algorithm (EA) framework. By using these computational cheap models to identify promising solutions for actual evaluation, the number of costly evaluations per iteration can be significantly reduced, thereby enhancing the algorithm’s efficiency. Based on the number \gamma of solutions selected for real evaluations with the assistance of the surrogate model, SAEAs can be categorized into three types: 1. \gamma=1 : In each generation, only the best predicted solution is selected for real function evaluation and preserved in an archive. This strategy notably decreases the real evaluation budget. However, the downside is that only one solution in the next-generation population will be modified, which might limit the enhancement of population distribution and keep new solutions confined to the current search space. To tackle this issue, some studies have utilized acquisition functions to promote solution diversity. For instance, GPEME [ 7 ] and SADE-Sammon [ 8 ] leverage the lower confidence bound (LCB) [ 9 ] to guide the search. Similarly, efficient global optimization (EGO) [ 10 ] employs the expected improvement (EI) method [ 11 ] , and SA-EDA [ 12 ] combines multiple acquisition strategies using the GP-Hedge method [ 13 ] to enhance the robustness of the selection process. 2. \gamma=N : Some methods use surrogate-assisted selection as a pre-selection step, generating more trial solutions than the population size N during the reproduction phase. The model then predicts the outcomes, selecting the approximately best N solutions for real evaluation. Although this approach effectively improves the quality of each generation’s offspring, it does not significantly reduce the number of real evaluations. Examples include methods based on binary and fuzzy classification [ 14 , 15 ] , approaches using relation models for selection [ 16 ] , and techniques that introduce some solutions directly into the next generation without model evaluation [ 17 ] . 3. 1<\gamma<N : Customized approaches have been proposed to balance the number of real evaluations and solution diversity. For instance, SAMSO [ 4 ] and SACOSO [ 18 ] employ multi-particle swarm optimization to enhance diversity through interactions among swarms. Meanwhile, LLSO [ 19 ] and DFC-MOEA [ 20 ] use hierarchical strategies for solution selection. LLSO increases population diversity by introducing random solutions, whereas DFC-MOEA selects solutions with medium membership degrees using a classifier. Through the carefully designed model-assisted selection strategies introduced above, the evaluation overhead can be effectively reduced. When dealing with EOPs, it is preferable to choose a smaller \gamma to enable more iterations and explorations with a limited number of fitness evaluations (FEs). However, an important phenomenon to note is that during the algorithmic iterations, only a limited number of solutions are evaluated. Relying solely on these evaluated solutions to generate new offspring often fails to significantly improve the distribution of new solutions. This limitation can adversely affect the ability of reproduction operators to produce high-quality solutions, thereby reducing the algorithm’s convergence speed. The work presented in [ 21 ] demonstrates a phenomenon akin to “standing still” during the algorithm’s evolution process via low-dimensional visualization. This issue is prevalent in SAEAs, yet it is often unaddressed by existing reproduction operators, thus limiting the practical performance of SAEAs. Even the most accurate surrogate models cannot select high-quality individuals from low-quality evaluated solutions alone. To address this problem, we propose a general conceptual strategy. During the algorithm iteration, high-quality un-evaluated solutions ( \mathcal{P}_{u} ) predicted by the surrogate models are combined with the evaluated solutions ( \mathcal{P}_{e} ) to form the next generation. These un-evaluated solutions, although not directly selected for real evaluations due to their slightly lower predicted quality, still have the potential to enhance the overall population and should not be discarded outright. This strategy aims to moderately increase the population’s diversity compared to the previous generation, improve the effectiveness of reproduction operators, and thereby accelerate the optimization process. To the best of our knowledge, Jin [ 22 ] in their review summarized a method known as the (\mu+\lambda) -Best strategy, which involves evaluating fewer than \lambda individuals, while substituting the others with predictions from surrogate models. This method bears some similarity to our work. However, it emphasizes a specific model management strategy, whereas our work investigates the impact of unevaluated solutions on the quality of the offspring. Moreover, we implement this approach on three typical reproduction operators: genetic algorithm (GA) [ 23 , 24 ] operators, differential evolution (DE) [ 25 ] operators, and estimation of distribution algorithm (EDA) [ 26 ] operators. This method is intended to improve the diversity of