Tweaking the search heuristic based on benchmark data is a necessary evil when building and testing an OR model intended for production. But this approach has a problem: we are able to beat benchmarks but are not able to consistently get acceptable results in production, where the input data can vary for each run. One solution is to train the OR model in more benchmarks, but it is expensive for businesses to create the right benchmarks and to verify results when there's a lot of variation possible in the data, or they are not sure of what variation can potentially happen, or the amount of work that goes into building the benchmark is high.
Does a solution exist that can adapt to any data input as long as the fundamentals it is built on are sound?
Evolutionary algorithms (EAs) — when they work well — may be an answer. We decide the chromosome, mating and mutation methods, and let the EA "evolve" into a good solution. Unlike procedural heuristics ("if a happens, do b"), we have no control over how the EA evolves. This is both a weakness and a strength: a weakness because it might miss on obvious improvements (worse convergence), but a strength because it is agnostic to the state of the solution and relies purely on the evolutionary mechanism to improve results (more robust, less dependent on problem characteristics). Thus, for example, an EA might perform worse than a MIP on a linear problem, but can work well on a non-linear problem whereas an approach with a MIP at its core will need a lot of heuristics around it.
EAs have been around for a very long time but have not gained much traction, because their weakness has proved to be a bigger factor in the face of more precise analytical techniques. However, as hardware has improved in the last 5 years (and has enabled us to use AI and machine learning in unforeseen ways), I believe EAs may be able to leverage hardware to address their weakness and might be a viable solution method once more.
I started looking at EAs in my previous job, where I wanted to use it to find the KPI weights for the optimizer (perhaps a topic for a different post). I started looking at how I could evaluate what EA could do for me using off-the-shelf (and free) libraries. I found DEAP through this book and was able to get started quickly.
Note that when I say EA, I really mean Genetic Algorithms, and not one of the myriad other approaches (one of the swam intelligence approaches like Ant Colony optimization, for example).
The problem I picked was one I was familiar with: the Solomon benchmarks. These problems are well researched and have near-optimal (or optimal) solutions published. Getting close to these results would tell me that EAs are worth considering as a solution approach.
One last thing I did was to buy a desktop (AMD Ryzen 4750G with 8 cores at 3.6-4.4 GHz), as my 2013 MacBook Air with 1.3 GHz processor was not going to cut it.
My new computer running at full tilt
I got close to some (but not all) of the best known results (click to see bigger images).
Result for C101: matched the best known result of 828.94
Result for R101: best result is 1650 (4% gap)
Result for RC105: best result is not even close (1377.11)
I worked on this for about 5 weeks from Feb 20 to March 30, for around 6 - 8 hours a week. Given the (lack of) effort I put in, I would call this a success.
If I had the opportunity to do so, I would implement a faster and more robust sub optimizer (in say Go or C++), perhaps using LKH. I had other ideas I wanted to try before I wrote this (I wanted to let the EA do sequencing as well) but I decided to close the loop and move on.
This is the design that worked best for me. It's not the first design I came up with, and it isn't the best one. More on this later.