A week ago, I tried some simple idea of what is called Memetic Algorithm with my friend, Ali Reza. He is working on Vehicle Routing Problem (VRP) for his MS thesis (industrial engineering) using evolutionary techniques. I told him about MA and its benefits; he became eager about the approach; we find a computer and we implemented a local search to put in the [cultural] evolution cycle. My local search was something like this:
Suppose that we have a route specified by R: c(1)c(2)…c(n) in which c(i) is the index of the ith city (or delivery position). I suggested this simple search:
For every position in the sequence, swap two adjacent cities and calculate the fitness, i.e. R: …c(i-1)c(i)c(i+1)… —> R’: …c(i-1)c(i+1)c(i)… and comparing f(R’) and f(R). If this change was better, accept it as the new individual.
This is very simple and I dare to say it is really mine. I guess someone might discovered (or used) this heuristic in their combinatorial optimization problems. However, I am not aware of such a search. Is there any in the literature?
We did not test it very much on many different problems. We have tested it in a single problem two or three times and in all cases, we got a better results comparing simple genetic algorithm. How much better?! I don’t know what amount is significant in this problem, but we reached (~)8.5 score when simple GA reached 9.5-10.
All of these has been done in less than an hour!
Mmm … As I told before, I do not believe in this type of interpretation of meme. However, I have tested it too!