On the Use of Biased-Randomized Transformers as Data-Driven Heuristics for Agile Optimization

This paper proposes the concept of biased-randomized transformers, a novel methodology that combines biased-randomized techniques and transformer-based deep learning for ‘agile’ optimization (i.e., real-time optimization that is carried out iteratively in dynamic systems). On the one hand, biased-randomization techniques have been used in the past to inject controlled randomness into greedy heuristics, thus converting them into probabilistic algorithms capable of generating thousands of good-quality solutions while preserving heuristic logic. On the other hand, transformer models can capture complex patterns across thousands of variables. Once trained, these models can be seen as data-driven heuristics able to provide fast solutions to new instances and adapt to changing inputs. The combination of biased-randomization techniques with trained transformers allows for a fast exploration and selection of the high-quality solutions to NP-hard combinatorial optimization problems. The paper includes two case studies that illustrate the potential of these biased-randomized transformers.