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.
