Solving optimization problems using learnable evolution model

Abstract

Optimization problems playa vital role in today's fast growing high-tech industrial society. For many real world optimization problems, finding an optimal solution in polynomial time is impossible. There are approximate approaches to solve these problems that can find near optimal solutions within reasonable amount of time. Evolutionary computation is one such approximate approach. Although evolutionary computation approaches can find very good quality solutions, they are relatively slow. The Learnable Evolution Model or LEM is a new class of evolutionary computation approach- that intends to make the evolution process faster than other conventional approaches. The main difference between LEM and other evolutionary computation approaches is that LEM applies machine learning to evolve new population, rather than simple recombination and mutation operators. LEM has been tested on different function optimization problems and heat exchanger design. Results from these experiments indicate a significant speed-up of the evolutionary process by LEM over conventional approaches in terms of number of generations needed to reach an optimal solution. In our work, we explore the capabilities of LEM in solving complex optimization problems. We implement our own version of the LEM and test its performance in solving several instances of the p-median problem and capacitated p-median problem, collected from the Operations Research Library. We compare the results with a Genetic Algorithm approach and other heuristic approaches in solving these problems. We find that LEM performs comparatively better than other approaches when the search space is smaller, while it performs worse in larger search spaces. We identify the reasons behind this behavior and find out possible solutions. We propose our new model, called the Combined Evolution Model or CEM, and claim that this model must perform better than LEM and other conventional approaches. Our claims are supported by the results obtained from applying CEM to the same instances of p-median problem.