A New Criterion for Balancing Global Search and Local Search in Memetic Algorithm
Subject Areas : electrical and computer engineeringMehdi Rezapoor Mirsaleh 1 * , M. R. Meybodi 2
1 -
2 -
Keywords: Global search learning automata (LA) local search memetic algorithm (MA) meme,
Abstract :
One of the problems with traditional genetic algorithms is its premature convergence that makes them incapable of searching good solutions of the problem. A memetic algorithm (MA) which is an extension of the traditional genetic algorithm uses a local search method to either accelerate the discovery of good solutions, for which evolution alone would take too long to discover, or to reach solutions that would otherwise be unreachable by evolution or a local search method alone. In this paper, a memetic algorithm based on learning automata (LA) and memetic algorithm, called LA-MA, is introduced. This algorithm is composed of two parts, genetic section and memetic section. Evolution is performed in genetic section and local search is performed in memetic section. The basic idea of LA-MA is to use learning automata during the process of searching for solutions in order to create a balance between exploration performed by evolution and exploitation performed by local search. To evaluate the efficiency of LA-MA, it has been used to solve two optimization problems: OneMax and graph isomorphism problems. The results of computer experimentations have shown that different versions of LA-MA outperform the others in terms of quality of solution and rate of convergence.
[1] H. Ishibuchi, S. Kaige, and K. Narukawa, "Comparison between Lamarckian and Baldwinian repair on multiobjective 0/1 knapsack problems," in Evolutionary Multi-Criterion Optimization, C. A. C. Coello, A. H. Aguirre, and Eckart Zitzler, Eds., Springer, 2005, pp. 370-385.
[2] H. Wang, D. Wang, and S. Yang, "A memetic algorithm with adaptive hill climbing strategy for dynamic optimization problems," Soft Computing-A Fusion of Foundations, Methodologies, and Applications, vol. 13, no. 8, pp. 763-780, Aug. 2009.
[3] M. Syrjakov and H. Szczerbicka, "Combination of direct global and local optimization methods," in Proc., IEEE Int. Conf. on Evolutionary Computation, vol. 1, pp. 326-333, Dec. 1995.
[4] D. Whitley, V. Gordon, and K. Mathias, "Lamarckian evolution, the Baldwin effect and function optimization," Parallel Problem Solving from Nature-PPSN III, vol. 866, pp. 5-15, Jan. 1994.
[5] D. Molina, M. Lozano, and F. Herrera, "MA-SW-Chains: Memetic algorithm based on local search chains for large scale continuous global optimization," in Proc. IEEE Congress on Evolutionary Computation, CEC'10, 8 pp., 18-23 Jul. 2010.
[6] N. Q. Huy, O. Y. Soon, L. M. Hiot, and N. Krasnogor, "Adaptive cellular memetic algorithms," Evolutionary Computation, vol. 17, no. 2, pp. 231-256, Summer 2009.
[7] W. E. Hart and R. K. Belew, "Optimization with genetic algorithm hybrids that use local searches," in Adaptive Individuals in Evolving Populations, R. K. Belew and M. Mitchell, Ed., Boston: Addison-Wesley Longman Publishing Co., pp. 483-496, 1996.
[8] M. Rezapoor and M. R. Meybodi, "LA-MA: a new memetic model based on learning automata," in Proc. of 18th National Conf. of Computer Society of Iran, 6 pp., Tehran, Iran, 14-16 Mar. 2013.
[9] M. A. Wiering and H. van Hasselt, "Ensemble algorithms in reinforcement learning," IEEE Trans. on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 38, no. 4, pp. 930-936, Aug. 2008.
[10] K. Najim and A. S. Poznyak, Learning Automata: Theory and Applications, Pergamon Press, Inc., 1994.
[11] M. A. L. Thathachar and P. S. Sastry, Networks of Learning Automata: Techniques for Online Stochastic Optimization, Kluwer Academic Publishers, 2004.
[12] P. Foggia, C. Sansone, and M. Vento, "A database of graphs for isomorphism and sub-graph isomorphism benchmarking," in Proc. of the 3rd Int. Workshop on Graph-Based Representations, pp. 176-187, May 2001.
[13] W. Yuan-Kai, F. Kuo-Chin, and H. Jorng-Tzong, "Genetic-based search for error-correcting graph isomorphism," IEEE Trans. on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 27, no. 4, pp. 588-597, Aug. 1997.
[14] J. R. Ullmann, "An algorithm for subgraph isomorphism," J. ACM, vol. 23, no. 1, pp. 31-42, Jan. 1976.
[15] L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, "A (sub) graph isomorphism algorithm for matching large graphs," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 26, no. 10, pp. 1367-1372, Oct. 2004.