{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T22:57:29Z","timestamp":1762210649445},"reference-count":60,"publisher":"MIT Press - Journals","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p> Among the most promising and active research areas in heuristic optimisation is the field of adaptive memetic algorithms (AMAs). These gain much of their reported robustness by adapting the probability with which each of a set of local improvement operators is applied, according to an estimate of their current value to the search process. This paper addresses the issue of how the current value should be estimated. Assuming the estimate occurs over several applications of a meme, we consider whether the extreme or mean improvements should be used, and whether this aggregation should be global, or local to some part of the solution space. To investigate these issues, we use the well-established COMA framework that coevolves the specification of a population of memes (representing different local search algorithms) alongside a population of candidate solutions to the problem at hand. Two very different memetic algorithms are considered: the first using adaptive operator pursuit to adjust the probabilities of applying a fixed set of memes, and a second which applies genetic operators to dynamically adapt and create memes and their functional definitions. For the latter, especially on combinatorial problems, credit assignment mechanisms based on historical records, or on notions of landscape locality, will have limited application, and it is necessary to estimate the value of a meme via some form of sampling. The results on a set of binary encoded combinatorial problems show that both methods are very effective, and that for some problems it is necessary to use thousands of variables in order to tease apart the differences between different reward schemes. However, for both memetic algorithms, a significant pattern emerges that reward based on mean improvement is better than that based on extreme improvement. This contradicts recent findings from adapting the parameters of operators involved in global evolutionary search. The results also show that local reward schemes outperform global reward schemes in combinatorial spaces, unlike in continuous spaces. An analysis of evolving meme behaviour is used to explain these findings. <\/jats:p>","DOI":"10.1162\/evco_a_00060","type":"journal-article","created":{"date-parts":[[2011,12,2]],"date-time":"2011-12-02T00:09:17Z","timestamp":1322784557000},"page":"165-188","source":"Crossref","is-referenced-by-count":7,"title":["Estimating Meme Fitness in Adaptive Memetic Algorithms for Combinatorial Problems"],"prefix":"10.1162","volume":"20","author":[{"given":"J. E.","family":"Smith","sequence":"first","affiliation":[{"name":"Department of Computer Science and Creative Technologies, University of the West of England, BS16 1QY, U.K."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"B1","first-page":"263","volume-title":"Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life","author":"B\u00e4ck T.","year":"1992"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1201\/9781420050387.ptb"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1007\/s00500-008-0349-1"},{"key":"B5","first-page":"370","volume-title":"Proceedings of the 7th International Conference on Genetic Algorithms","author":"Bull L.","year":"1997"},{"key":"B6","first-page":"77","author":"Bull L.","year":"1997","journal-title":"Proceedings of the 5th International Workshop on Artificial Life: Synthesis and Simulation of Living Systems (ALIFE-96)"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1109\/59.852110"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1023\/B:HEUR.0000012446.94732.b6"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2010.5586064"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCB.2006.883271"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1007\/s00500-008-0357-1"},{"key":"B12","volume-title":"Proceedings of the 2003 Congress on Evolutionary Computation (CEC 2003).","author":"CEC-2003","year":"2003"},{"key":"B13","first-page":"85","author":"Chen X.","year":"2010","journal-title":"Proceedings of the 2010 International Conference on Computational Problem-Solving (ICCP)"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2011.2132725"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44629-X_11"},{"key":"B16","unstructured":"Eiben, A., and van Hemert, J. (1999). SAW-ing EAs: Adapting the fitness function for solving constrained problems. In D. Corne, M. Dorigo, and F. Glover (Eds.), New ideas in optimization (Chap. 26, pp. 389\u2013402). New York: McGraw-Hill."},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1109\/4235.771166"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69432-8_2"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87700-4_18"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1162\/evco.2008.16.1.31"},{"key":"B23","first-page":"667","author":"Kendall G.","year":"2002","journal-title":"Proceedings of the Fourth Asia-Pacific Conference on Simulated Evolution and Learning (SEAL)"},{"key":"B24","volume-title":"Proceedings of the 1999 Genetic and Evolutionary Computation Conference Workshop Program","author":"Krasnogor N.","year":"1999"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1023\/B:GENP.0000023687.41210.d7"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1023\/B:NACO.0000023419.83147.67"},{"key":"B28","first-page":"987","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000)","author":"Krasnogor N.","year":"2000"},{"key":"B29","first-page":"432","author":"Krasnogor N.","year":"2001","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001)"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45712-7_74"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1007\/s12293-009-0011-1"},{"key":"B33","unstructured":"Moscato, P. (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech Concurrent Computation Program Report 826. Pasadena, CA: Caltech."},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2007.070202"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2007.4424768"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1162\/evco.2009.17.2.231"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2008.2009460"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2003.819944"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCB.2005.856143"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1109\/MCI.2010.936309"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1162\/evco.1994.2.4.369"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2004.1330936"},{"key":"B44","first-page":"36","volume-title":"Proceedings of the 2nd International Conference on Genetic Algorithms and Their Applications","author":"Schaffer J.","year":"1987"},{"key":"B45","volume-title":"Numerical optimisation of computer models","author":"Schwefel H. P.","year":"1981"},{"issue":"3","key":"B46","first-page":"491","volume-title":"Evolutionary Computation","volume":"18","author":"Serpell M.","year":"2010"},{"key":"B47","unstructured":"Smith, J. (2001). Modelling GAs with self-adaptive mutation rates. In L. Spector, E. Goodman, A. Wu, W. Langdon, H. M. Voight, M. Gen, S. Sen, M. Dorigon, S. Pezeshk, M. Garzon, and E. Burke (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2011), pp. 599\u2013606."},{"key":"B48","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45712-7_52"},{"key":"B49","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015579825262"},{"key":"B50","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2003.1299617"},{"key":"B51","first-page":"329","volume":"7","author":"Smith J.","year":"2003","journal-title":"Proceedings of Foundations of Genetic Algorithms"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2003.1299381"},{"key":"B53","first-page":"105","volume-title":"Recent advances in memetic algorithms","author":"Smith J.","year":"2004"},{"key":"B54","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCB.2006.883273"},{"key":"B55","doi-asserted-by":"publisher","DOI":"10.1145\/1276958.1277219"},{"key":"B56","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2010.5586401"},{"key":"B57","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61723-X_1008"},{"key":"B58","doi-asserted-by":"publisher","DOI":"10.1109\/ICEC.1996.542708"},{"key":"B59","doi-asserted-by":"publisher","DOI":"10.1109\/ICEC.1996.542382"},{"key":"B60","doi-asserted-by":"publisher","DOI":"10.1007\/s005000050009"},{"key":"B61","first-page":"586","author":"Stone C.","year":"2002","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002)"},{"key":"B62","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69432-8_4"},{"key":"B63","doi-asserted-by":"publisher","DOI":"10.1109\/MCI.2009.935310"},{"key":"B64","doi-asserted-by":"publisher","DOI":"10.1145\/1143997.1144206"},{"key":"B65","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2007.900327"},{"key":"B66","first-page":"1235","author":"Wiegand R.","year":"2001","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2011)"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/EVCO_a_00060","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:58:07Z","timestamp":1615586287000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/20\/2\/165-188\/921"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":60,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.1162\/EVCO_a_00060"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00060","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6]]}}}