A Solution to combinatorial Optimization Problem using Memetic Algorithms
Aaquil Bunglowala, B.M. Singhi · 2008
growing complexity in the hardware now necessitates in improving the performance of searching algorithms. The Genetic Algorithm and local heuristics have opened up a whole new paradigm of probability based approaches to complex NP-hard and NP-complete problems of real world. Genetic algorithms do not guarantee global optimum solution to a problem but are generally good at finding acceptable solution to problems. In complex combinatorial spaces, hybridization with other optimization techniques can greatly improve the efficiency of search. Memetic algorithms is an improvisation over genetic algorithms and combines global and local search by using evolutionary algorithms to perform exploration while the local search methods are used for exploitation. Here, exploitation is the process of visiting entirely new regions of a search space where the gain can be high. Recently the concept of grid computing has taken up the task of improving the computational abilities of systems. It is the combination of distributed, high throughput and collaborative systems for the effective sharing and distributed coordination of resources which belong to different control domains. This paper discusses the advent of genetic algorithms (GAs) and memetic algorithms (MAs) as a solution to combinatorial optimization problems and procedures are laid down to strike a balance between genetic search and local search in MAs. The MAs for circuit partitioning in VLSI floor planning have been briefed. We have addressed the complexity issues in context of MAs as part of our research work. The problem of cell assignment to switches in cellular mobile networks is taken as a case.