Adaptive Stochastic Natural Gradient Method for Safe Optimization on Binary Space
This work addresses the underexplored problem of safe optimization in binary spaces, which is relevant for risk-sensitive applications in medical and engineering domains.
The paper introduces safe ASNG, a method for safe optimization in binary search spaces that suppresses unsafe evaluations by estimating Lipschitz constants via Walsh functions and projecting solutions into a safe region. Experiments show it effectively avoids unsafe evaluations while maintaining optimization efficiency, unlike comparative methods.
Optimization problems in real-world applications across the medical and engineering domains often involve potential risks when evaluating candidate solutions. Safe optimization aims to perform optimization while suppressing unsafe solution evaluations in such situations. For continuous search spaces, there exist safe optimization methods based on evolutionary computation. However, the algorithm development of safe optimization methods for binary search spaces has not been adequately addressed. In this study, we incorporate additional mechanisms for safe optimization into a binary optimization method, the adaptive stochastic natural gradient method (ASNG) with a family of Bernoulli distributions. For safety functions that must be kept non-negative during optimization, the proposed method, safe ASNG, estimates the Lipschitz constants with respect to the Hamming distance by constructing surrogate models of safety functions based on discrete Walsh functions. Then, safe ASNG computes a safe region that consists of safe solutions around the previously evaluated safe solutions. By projecting newly generated solutions to their nearest neighbors within the safe region, safe ASNG suppresses unsafe solution evaluations. Experimental results on benchmark problems on binary domains confirm that, while the comparative methods fail to suppress unsafe solution evaluations, safe ASNG achieves efficient optimization while effectively suppressing unsafe solution evaluations.