The growing complexity in the electronic hardware now necessitates in improving the performance of searching algorithms. Genetic algorithms do not guarantee global optimum solution to NP-Hard problems 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 algorithm (MA) is an improvisation over genetic algorithms (GA) that 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 also be high.

1. Beumont, O., Legrand, A. and Robert, Y., “Optimal algorithms for scheduling divisible workloads on heterogeneous systems”, Proceedings of The International Parallel and Distributed Processing Symposium, 2003
2. Areibi, S., Bao, X., Grewal, G., Banerji, D., Du, P., “A Comparison of Heuristics for FPGA Placement”, ACTA International Journal of Computers and Applications
3. Bunglowala, A., Singhi, B.M. et. al, “Performance Evaluation and Comparison and Improvement of Standard Cell Placement in VLSI Design”, International Conference on Emerging Trends in Engineering and Technology, July 2008 [also published on CSDL, IEEE]
4. Bunglowala, A., Singhi, B.M., “A Solution to combinatorial Optimization Problem using Memetic Algorithms”, International Journal of Computer System Applications [IJCSA], ICAC, February 2008.
5. Casanova, H., Legrand, A., Zagorodnov, D. and Berman, F., “Heuristics for scheduling parameter sweep applications in Grid environments”, Heterogeneous Computing Workshop 2000, IEEE Computer Society Press, pp. 349-363.
6. Cohoon, J.P. and Paris, W.D., “Genetic Placement”, Proceedings of IEEE International Conference on Computer Aided Design, Santa Clara, 1986, p.p. 422-425
7. Donath, W.E., “Complexity Theory and Design Automation”, Proceedings of 17th Design Automation Conference, 1980
8. Dutt, N.D. and Gajski, D.D., “Design Synthesis and Silicon Compilation”, IEEE Design and Test of Computers, 1990, p.p. 8-23
9. “First workshop on memetic algorithms (WOMA I),” Proc. 2000 Genetic and Evolutionary Computation Conference Workshop Program, pp. 95–130, July 8, 2000
10. Gajski, D.D., “New VLSI Tools” Guest Editor’s Introduction, IEEE Computers, 1983, p.p. 11-14
11. Garey, M.R. and Johnson, D.S., “Computers and Intractability”, A Guide to the Theory of NP-Completeness, San Francisco, 1979
12. Goldberg, D. E. and Voessner, S., “Optimizing global-local search hybrids,” in Proc. 1999 Genetic and Evolutionary Computation Conf., Orlando, FL, July 13–17, 1999, pp. 220–228.
13. Land, M.W.S., “Evolutionary algorithms with local search for combinatorial optimization,” Ph.D. dissertation, Univ. of California, San Diego, 1998.
14. Leighton, F.T., “Complexity Issues in VLSI”, Cambridge, 1983
15. Lengauer, T. “Combinatorial Algorithm for Integrated Circuit Layout”, Chichester, New York, 1990
16. Sahni, S. and Bhatt, A., “The Complexity of Design Automation Problems”, Proceedings of 17th Design Automation Conference, 1980, p.p. 402-411
17. Shahookar, K. and Mazumder, P. “VLSI Placement Techniques”, ACM Computing Serveys 1991, p.p. 143-220
18. Shewani, N.A., “Algorithms for VLSI Physical Design Automation”, Boston, 1993
19. Tagliarini, G.A., Christ, J.F. and Page, E.W., “Optimization using Neural Networks”, IEEE Transaction on Computers, 1991, p.p. 1347-1358

SCP Memetic Algorithm (MA) NP-hard