Pablo Moscato coined the term "memetic algorithm" (MA) in his technical report in 1989, drawing inspiration from Darwinian principles of natural evolution and Richard Dawkins' meme concept. He saw MA as similar to a population-based hybrid genetic algorithm (GA) combined with an individual learning procedure capable of performing local refinements.

Computer science and operations research's memetic algorithm extends the genetic or evolutionary algorithm (EA). It might give a good enough answer to an optimisation problem. It uses an excellent heuristic or local search method to improve the quality of the solutions that the EA comes up with and lower the chance that it will converge too soon.

Memetic algorithms are one area of study in evolutionary computing that has been growing recently. MA often describes a problem-solving method combining an evolutionary or population-based approach with separate processes for individual learning or local improvement. MAs are also called Baldwinian evolutionary algorithms (BEAs), Lamarckian evolutionary algorithms (LEAs), cultural algorithms, or genetic local search.

Computer-Aided Chemical Engineering

Urselmann devised a memetic method in 2011 to solve a chemical process optimisation problem. An evolutionary algorithm, like an evolution strategy (ES), is combined with a local responder (meme) to make a memetic algorithm. The NLP problem's first stage, or ES, fixes the discrete design variables and sets the starting values for the continuous optimisation variables. 

Repair-Based Memetic Algorithm

The Walters, MA-W, memetic algorithm for the TSP differs from many other memetic algorithms in several fundamental ways. In particular, MA-W doesn't use the permutation model of tours, and instead of using specialised operators for the TSP, it uses a standard recombination operator. MA-W uses a method called "nearest neighbour indexing" to figure out how to show potential solutions. 

Source: Wikipedia

Applications

Memetic algorithms have been used to solve many problems in the real world. Even though many people use methods similar to memetic algorithms, they also use methods with different names, such as hybrid genetic algorithms. Many famous NP problems have been solved by researchers with the help of memetic algorithms. 

Some are 

• graph splitting, 
• multidimensional knapsack, 
• travelling salesman problem, 
• quadratic assignment problem, 
• the set cover problem, 
• minimal graph colouring, 
• the max independent set problem, 
• bin packing problem, and 
• generalised assignment problem.

Recent applications:

• business analytics and data science, 
• training of artificial neural networks, 
• pattern recognition, 
• robotic motion planning, 
• beam orientation, 
• circuit design, 
• electric service restoration, 
• medical expert systems, 
• single machine scheduling, 
• automatic timetabling, 
• manpower scheduling, 
• nurse rostering optimisation, 
• processor allocation, 
• maintenance scheduling, and 
• scheduling of multiple workflows to constrained heterogeneous environments.

Conclusion

Memetic algorithms have become an essential part of solvers that can handle big optimisation problems in the real world. Research institutions are constantly looking into them, and are also used widely in business. 

The no-free-lunch theorems of optimisation and search say that all methods for solving optimisation problems are as good as each other. On the other hand, this means that the following is likely to happen: The less general an algorithm is and the more problem-specific information it builds on, the better it is at solving a problem or group of problems. This realisation goes directly to the suggestion that application-specific methods or heuristics should be added to general-purpose metaheuristics. It fits well with the idea of MAs.

Image source: Unsplash