Boost the effectiveness of our algorithms by determining which algorithm hyper parameters work best for different types of problems. As a result, we can develop a machine learning model that can predict the optimal algorithm configuration in real time.
During the last years, research on integrating Machine Learning (ML) into designing efficient and robust meta-heuristics became very popular. As former scientists and academics at Solvice, we believe in keeping up with the state-of-the-art. In [1] the authors make a distinction between 3 classes of ML methods for improving metaheuristics:
On top of that distinction, we can generalize between offline and online learning time. In offline data-driven metaheuristics, the ML process occurs a priori before starting to solve the problem. In online data driven-metaheuristics, ML gathers knowledge during the search while solving the problem.
At Solvice, we build APIs around solvers that solve different challenging planning and optimisation problems resulting in a route optimization API and a workforce scheduling API. These APIs are being used by many different companies ranging from logistic providers, field service providers, warehouses, retail stores, to independent software vendors and software-as-a-service providers for planning systems. Our solver platform never “knows in advance” what the next request will be, so we are dealing with dynamic inputs of all sizes and forms. That is why our solvers need to be robust, next to being efficient and fast. How can a solver be robust? There are two levels that define this:
Both robustness criteria should hold for any optimization service, but are rarely achieved.
One way to achieve this is by continuously examining every optimization request that enters the system and offline testing for optimal parameterization in order to be always aware of the best parameter combination.
This approach typically falls under the 2nd category of “Low-level data-driven metaheuristic” as we are optimizing the hyperparameters and predicting the ideal hyperparameter set for any new solve request.
Algorithm selection is not new. As early as 1976, researchers have proposed a framework for the so-called algorithm selection problem (ASP), which predicts which algorithm from a portfolio is likely to perform best based on measurable features from a collection of problem instances. There are the four essential components of that model (Fig 1):
However, that research provides no advice about the mapping from the problem instance space P to the feature space F. To our understanding, this is by far the most challenging task in this study.
Next to user and API generated solve requests, there is a library of problem instances whose goal is to cover all possible flavors of an optimization problem that our solver platform can handle. So generating instances for that problem space that should cover most of that space is the real challenge.
For instance, for a VRP (Vehicle Routing Problem) problem there are plenty of flavors such as capacitated, time windowed, pickup and deliveries, multi period and many others. So how can we automatically generate all possible flavors of a certain problem type? By introducing a feature set that can define a specific flavor.
For the sake of simplicity, we’ll introduce our problem instance generator only for the VRP problems type that is covered by our OnRoute route optimization API. How can we define instances by a feature set? Most research defines instance generation based upon structural characteristics of the problem. We suggest using constraint definitions as features for identification. Examples are:
For every constraint, we can define the level of constraintness between 0% and 100%. For instance, the broader the time window for an order, the more flexibility the solver has to plan this order. The definition of a feature’s constraintness level is not to generate instances that are harder to solve, merely to generate different instances.
Sure, ML can offer us improved suggestions of the ideal algorithm, but what is the level of that benefit?
We have seen that problem instance size is one of the key discriminators regarding a feature set definition. Let’s take a closer look at what a very typical benchmarking strategy would look like when it comes to comparing different construction heuristics within a metaheuristic. For VRP’s greedy First Fit (FF) assignment, heuristics are usually very fast and performant for small instances up to a few hundreds of orders/locations. However, when calculating larger sized instances, an alternative k-Nearest Neighbor (k-NN) algorithm greatly improves both computation time as well as solution quality.
In figure 2 we compare these two algorithms Greedy FF and k-NN based on their solution quality compared to the final solution quality as a percentage deviation. Clearly, for large instances, k-NN outperforms greedy FF with almost double the performance.
To obtain an ML layer that suggests the ideal algorithm (here: hyper parameter combination) for an instance, we need to:
Our input variables are all categorical and the goal is to predict the ideal algorithm configuration which is a vector of categorical variables as well. Clearly, this is the case of multi-class multi-level classification for which we can use well-known algorithms such as multinomial logistic regression.
Figure 3 shows that this ML classifier can suggest ideal algorithm configuration in real-time for a new instance based upon the feature set that identifies this instance. Then, the correct solver is chosen to process this solve request.
Enriching our Solver API with a ML layer to predict the optimal algorithm configuration set allows us to learn from our customer’s requests and greatly improve the solution quality as well as performance of the solver continuously.
In the future, we will improve upon our problem feature set definition to encompass more of the potential space of problems and thus be able to predict new instances better. Secondly, by improving our ML algorithm we aim to have higher accuracy in the prediction.
Stay tuned!
[1] El-Ghazali Talbi. Machine learning into metaheuristics: A survey and taxonomy of data-driven metaheuristics. 2020. ffhal-02745295f
