Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces Limited Monotonical Perfect Surrogates (LyMPuS), a novel surrogate modeling technique that exactly represents the original function for comparing solutions differing by a single variable, addressing the limitations of linear perfect surrogates. LyMPuS is parameterless, trained on-the-fly, and updates incrementally without discarding previous evaluations, making it suitable for expensive local search. The method guarantees missing dependency detection in a maximum of $2\lceil\log_2(n)\rceil$ steps, offering efficient linkage discovery.
Forget approximate surrogates – LyMPuS offers *perfect* representations for single-variable comparisons, unlocking optimization possibilities where direct solution evaluation is unavailable.
Surrogates provide a cheap solution evaluation and offer significant leverage for optimizing computationally expensive problems. Usually, surrogates only approximate the original function. Recently, the perfect linear surrogates were proposed that ideally represent the original function. These surrogates do not mimic the original function. In fact, they are another (correct) representation of it and enable a wide range of possibilities, e.g., discovering the optimized function for problems where the direct transformation of the encoded solution into its evaluation is not available. However, many real-world problems can not be represented by linear models, making the aforementioned surrogates inapplicable. Therefore, we propose the Limited Monotonical Perfect Surrogate (LyMPuS), which overcomes this difficulty and enables the comparison of two solutions that differ by a single variable. Our proposition is suitable for limiting the cost of expensive local search procedures. The proposed surrogate is parameterless and can be trained on the fly without any separate surrogate-building step. It uses only the necessary fitness evaluations, and the already-paid costs are not wasted when the model is updated. Finally, it offers low-cost missing-linkage detection and low-cost linkage discovery, guaranteed to find a missing dependency in no more than $2\lceil\log_2(n)\rceil$ steps.