Abstract
Memetic algorithms (MAs) constitute a metaheuristic optimization paradigm [usually based on the synergistic combination of an evolutionary algorithm (EA) and trajectory-based optimization techniques] that systematically exploits the knowledge about the problem being solved and that has shown its efficacy to solve many combinatorial optimization problems. However, when the search depends heavily on human-expert’s intuition, the task of managing the problem knowledge might be really difficult or even indefinable/impossible; the so-called interactive evolutionary computation (IEC) helps to mitigate this problem by enabling the human user to interact with an EA during the optimization process. Interactive MAs can be constructed as reactive models in which the MA continuously demands the intervention of the human user; this approach has the drawback that provokes fatigue to the user. This paper considers user-centric MAs, a more global perspective of interactive MAs since it hints possibilities for the system to be proactive rather than merely interactive, i.e., to anticipate some of the user behavior and/or exhibit some degree of creativity, and provides some guidelines for the design of two different models for user-centric MAs, namely reactive and proactive search-based schema. An experimental study over two complex NP-hard problems, namely the Traveling Salesman problem and a Gene Ordering Problem, shows that user-centric MAs are in general effective optimization methods although the proactive approach provides additional advantages.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Abu-Mostafa Y (1993) Hints and the VC dimension. Neural Comput 5:278–288
Arnone A, Davidson B (1997) The hardwiring of development: organization and function of genomic regulatory systems. Development 124:1851–1864
Alizadeh A et al (2001) Distinct types of diffuse large B-cell lymphoma identified by gene expression profiling. Nature 403:503–511
Babbar M, Minsker B (2006) A collaborative interactive genetic algorithm framework for mixed-initiative interaction with human and simulated experts: a case study in long-term groundwater monitoring design. In: World environmental and water resources congress
Bonissone PP, Subbu R, Eklund NHW, Kiehl TR (2006) Evolutionary algorithms + domain knowledge = real-world evolutionary computation. IEEE Trans Evol Comput 10(3):256–280
Breukelaar R, Emmerich M, Bck T (2006) On interactive evolution strategies. In: Rothlauf F, Branke J, Cagnoni S, Costa E, Cotta C, Drechsler R, Lutton E, Machado P, Moore J, Romero J, Smith G, Squillero G, Takagi H (eds) Applications of evolutionary computing. Lecture notes in computer science, vol 3907, Springer, Berlin, pp 530–541
Beck JC, Wilson N (2005) Proactive algorithms for scheduling with probabilistic durations. In: Proceedings of the 19th international joint conference on Artificial intelligence. IJCAI’05. Morgan Kaufmann, San Francisco, pp 1201–1206
Beck JC, Wilson N (2007) Proactive algorithms for job shop scheduling with probabilistic durations. J Artif Intell Res 28(1):183–232
Ben-Dor A, Yakhini Z (1999) Clustering gene expression patterns. In: Proceedings of the ACM RECOMB’99, Lyon, France. ACM Press, New York, pp 33–42
Cotta C, Fernández Leiva AJ (2011) Bio-inspired combinatorial optimization: notes on reactive and proactive interaction. In: Cabestany J, Rojas I, Caparrós GJ (eds) Advances in computational intelligence—11th international work-conference on artificial neural networks, Part II (IWANN 2011). Lecture notes in computer science, vol 6692. Springer, Málaga, pp 348–355
Cotta C, Troya JM (2003) Embedding branch and bound within evolutionary algorithms. Appl Intell 18(2):137–153
Cotta C, Mendes A, Garcia V, França P, Moscato P (2003) Applying memetic algorithms to the analysis of microarray data. In: Raidl G et al (eds) Applications of evolutionary computing. Lecture notes in computer science, vol 2611. Springer, Berlin, pp 22–32
Culberson J (1998) On the futility of blind search: an algorithmic view of “no free lunch”. Evol Comput 6(2):109–128
Davis L (1991) Handbook of genetic algorithms. Van Nostrand Reinhold, New York
Dawkins R (1976) The selfish gene. Clarendon Press, Oxford
Dawkins R (1986) The BlindWatchmaker, 1986. Longman, Essex
Deb K, Chaudhuri S (2007) I-mode: an interactive multi-objective optimization and decision-making using evolutionary methods. KanGal report 2007003, Kanpur Genetic Algorithms Laboratory
Deb K, Kumar A (2007) Interactive evolutionary multi-objective optimization and decision-making using reference direction method. KanGal report 2007001, Kanpur Genetic Algorithms Laboratory
De Risi J, Lyer V, Brown P (1997) Exploring the metabolic and genetic control of gene expression on a genomic scale. Science 278:680–686
Dias J, Captivo M, Clímaco J (2008) A memetic algorithm for multi-objective dynamic location problems. J Global Optim 42:221–253
Dozier G (2001) Evolving robot behavior via interactive evolutionary computation: from real-world to simulation. In: 16th ACM symposium on applied computing (SAC2001), Las Vegas, NV. ACM Press, New York, pp 340–344
Eiben AE, Smith JE (2003) Introduction to evolutionary computation. Springer, Berlin
Eisen M, Spellman P, Brown P, Botstein D (1998) Cluster analysis and display of genome-wide expression patterns. Proc Natl Acad Sci USA 95:14863–14868
Espinar J, Cotta C, Fernández-Leiva AJ (2012) User-centric optimization with evolutionary and memetic systems. In: Lirkov I, Margenov S, Wasniewski J (eds) 8th international conference on large-scale scientific computing (LSSC 2011). Lecture Notes in Computer Science, Sozopol, Bulgaria, vol 7116. Springer, Berlin, pp 214–221
Fasulo D (1999) An analysis of recent work on clustering algorithms. Technical Report UW-CSEO1-03-02, University of Washington
Gallardo J, Cotta C, Fernández A (2007) On the hybridization of memetic algorithms with branch-and-bound techniques. IEEE Trans Syst Man Cybern Part B 37(1):77–83
Gong D, Yao X, Yuan J (2009) Interactive genetic algorithms with individual fitness not assigned by human. J Univ Comput Sci 15(13):2446–2462
Hart WE, Belew RK (1991) Optimizing an arbitrary function is hard for the genetic algorithm. In: Belew RK, Booker LB (eds) Proceedings of the fourth international conference on genetic algorithms, San Mateo CA. Morgan Kaufmann, San Francisco, pp 190–195
Hart W, Krasnogor N, Smith J (2005) Recent advances in memetic algorithms. Studies in fuzziness and soft computing, vol 166. Springer, Berlin
Hartuv E, Schmitt A, Lange J, Meier-Ewert S, Lehrach H, Shamir R (1999) An algorithm for clustering cDNAs for gene expression analysis. In: Proceedings of the ACM RECOMB’99, Lyon, France. ACM Press, New York, pp 188–197
Houck C, Joines J, Kay M, Wilson J (1997) Empirical investigation of the benefits of partial lamarckianism. Evol Comput 5(1):31–60
Inoue T, Furuhashi T, Fujii M, Maeda H, Takaba M (1999) Development of nurse scheduling support system using interactive EA. IEEE Int Conf Syst Man Cybern 5:533–537
Jaszkiewicz A (2004) Interactive multiple objective optimization with the pareto memetic algorithm. In: Gottlieb J et al (eds) 4th EU/ME workshop: design and evaluation of advanced hybrid meta-heuristics, Nottingham, UK
Jenner R, Alba M, Boshoff C, Kellam P (2001) Kaposi’s sarcoma-associated herpesvirus latent and lytic gene expression as revealed by DNA arrays. J Virol 75:891–902
Khanna R, Liu H, Chen HH (2008) Proactive power optimization of sensor networks. In: IEEE international conference on communications (ICC), Beijing, China, IEEE, pp 2119–2123
Klau G, Lesh N, Marks J, Mitzenmacher M (2010) Human-guided search. J Heuristics 16:289–310
Kosorukoff A (2001) Human-based genetic algorithm. In: 2001 IEEE international conference on systems, man, and cybernetics. IEEE Press, Tucson, pp 3464–3469
Krasnogor N, Smith J (2005) A tutorial for competent memetic algorithms: model, taxonomy, and design issues. IEEE Trans Evol Comput 9(5):474–488
Kubota N, Nojima Y, Sulistijono I, Kojima F (2003) Interactive trajectory generation using evolutionary programming for a partner robot. In: 12th IEEE international workshop on robot and human interactive communication (ROMAN 2003), Millbrae, California, USA, pp 335–340
Lim S, Cho SB (2005) Language generation for conversational agent by evolution of plan trees with genetic programming. In: Torra V, Narukawa Y, Miyamoto S (eds) Modeling decisions for artificial intelligence. Lecture notes in computer science, vol 3558. Springer, Berlin, pp 305–315
Lim S, Kim KM, Hong JH, Cho SB (2004) Interactive genetic programming for the sentence generation of dialogue-based travel planning system. In: 7th Asia-Pacific conference on complex systems, Cairns, Australia. Asia-Pacific Workshops on Genetic Programming, pp 6–10
Lozano JA, Larrañaga P, Inza I, Bengoetxea E (2006) Towards a new evolutionary computation: advances on estimation of distribution algorithms. Studies in fuzziness and soft computing, vol 192. Springer, Berlin
Mamoun MH (2010) A new proactive routing algorithm for manet. Int J Acad Res 2(2):199–204
Moscato P (1999) Memetic algorithms: a short introduction. In: Corne D, Dorigo M, Glover F (eds) New ideas in optimization, McGraw-Hill, Maidenhead, pp 219–234
Moscato P, Cotta C (2003) A gentle introduction to memetic algorithms. In: Glover F, Kochenberger G (eds) Handbook of Metaheuristics. Kluwer, Boston, pp 105–144
Moscato P, Cotta C (2007) Memetic algorithms. In: Gonzalez TF (eds) Handbook of approximation algorithms and metaheuristics, Chapter 27. Chapman & Hall, London
Moscato P, Cotta C (2010) A modern introduction to memetic algorithms. In: Gendreau M, Potvin JY (eds) Handbook of metaheuristics. International series in operations research and management science. 2nd edn, vol 146. Springer, Berlin, pp 141–183
Moscato P, Mendes A, Cotta C (2004) Memetic algorithms. In: Onwubolu G, Babu B (eds) New optimization techniques in engineering. Springer, Berlin, pp 53–85
Mühlenbein H, Paaß G (1996) From recombination of genes to the estimation of distributions I. Binary parameters. In: PPSN IV: Proceedings of the 4th international conference on parallel problem solving from nature, London, UK. Springer, Berlin, pp 178–187
Neri F, Cotta C (2012) Memetic algorithms and memetic computing optimization: a literature review. Swarm Evol Comput 2:1–14
Neri F, Cotta C, Moscato P (2012) Handbook of memetic algorithms. Studies in computational intelligence, vol 379. Springer, Berlin
Nguyen QH, Ong YS, Krasnogor N (2007) A study on the design issues of memetic algorithm. In: Srinivasan D, Wang L (eds) 2007 IEEE congress on evolutionary computation, Singapore, IEEE Computational Intelligence Society. IEEE Press, New York, pp 2390–2397
Ong YS, Keane A (2004) Meta-lamarckian learning in memetic algorithms. IEEE Trans Evol Comput 8(2):99–110
Ohsaki M, Takagi H, Ohya K (1998) An input method using discrete fitness values for interactive ga. J Intell Fuzzy Syst 6(1):131–145
Ong YS, Lim MH, Zhu N, Wong K (2006) Classification of adaptive memetic algorithms: a comparative study. IEEE Trans Syst Man Cybern Part B 36(1):141–152
Parmee IC (2007) Human-centric evolutionary systems in design and decision-making. In: Rennard JP (eds) Handbook of research on nature-inspired computing for economics and management. IGI Global, pp 395–411
Parmee I, Abraham J (2004) User-centric evolutionary design. In: Marjanovic D (eds) 8th international design conference DESIGN 2004. Decision making workshop, pp 1441–1446
Parmee IC, Abraham JAR, Machwe A (2008) User-centric evolutionary computing: melding human and machine capability to satisfy multiple criteria. In: Knowles J, Corne D, Deb K, Chair DR (eds) Multiobjective problem solving from nature. Natural computing series. Springer, Berlin, pp 263–283
Puchinger J, Raidl GR (2005) Combining metaheuristics and exact algorithms in combinatorial optimization: a survey and classification. In: Mira J, Álvarez JR (eds) Artificial intelligence and knowledge engineering applications: a bioinspired approach. First international work-conference on the interplay between natural and artificial computation, (IWINAC 2005), Part II. LNCS, vol 3562. Springer, Las Palmas, pp 41–53
Quiroz JC, Banerjee A, Louis SJ (2008) Igap: interactive genetic algorithm peer to peer. In: Proceedings of the 10th annual conference on Genetic and evolutionary computation. GECCO ’08. ACM, New York, pp 1719–1720
Quiroz J, Louis S, Banerjee A, Dascalu S (2009) Towards creative design using collaborative interactive genetic algorithms. In: IEEE congress on evolutionary computation (CEC 2009), Singapore, IEEE, pp 1849–1856
Sáez Y, Viñuela PI, Segovia J, Castro JCH (2005) Reference chromosome to overcome user fatigue in IEC. New Gener Comput 23(2)
Smith JE (2008) Self-adaptation in evolutionary algorithms for combinatorial optimisation. In: Cotta C, Sevaux M, Sörensen K (eds) Adaptive and multilevel metaheuristics. Studies in computational intelligence, vol 136. Springer, Berlin, pp 31–57
Sudholt D (2009) The impact of parametrization in memetic evolutionary algorithms. Theor Comput Sci 410(26):2511–2528
Takagi H (2000) Active user intervention in an ec search. In: 5th Joint conference information sciences (JCIS2000), Atlantic City, NJ, pp 995–998
Takagi H (2001) Interactive evolutionary computation: fusion of the capabilities of EC optimization and human evaluation. Proc IEEE 9:1275–1296
Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evol Comput 1(1):67–82
Acknowledgments
This work is partially supported by Spanish MICINN under projects NEMESIS (TIN2008-05941) and ANYSELF (TIN2011-28627-C04-01), and by Junta de Andalucía under project P10-TIC-6083 (DNEMESIS).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Badillo, A.R., Ruiz, J.J., Cotta, C. et al. On user-centric memetic algorithms. Soft Comput 17, 285–300 (2013). https://doi.org/10.1007/s00500-012-0893-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-012-0893-6