Nothing Special   »   [go: up one dir, main page]

Skip to main content

Advertisement

Log in

On user-centric memetic algorithms

  • Focus
  • Published:
Soft Computing Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. http://www.cs.gmu.edu/~eclab/projects/ecj/.

  2. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.

References

  • Abu-Mostafa Y (1993) Hints and the VC dimension. Neural Comput 5:278–288

    Article  Google Scholar 

  • Arnone A, Davidson B (1997) The hardwiring of development: organization and function of genomic regulatory systems. Development 124:1851–1864

    Google Scholar 

  • Alizadeh A et al (2001) Distinct types of diffuse large B-cell lymphoma identified by gene expression profiling. Nature 403:503–511

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    MathSciNet  MATH  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • 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

    Article  Google Scholar 

  • Davis L (1991) Handbook of genetic algorithms. Van Nostrand Reinhold, New York

    Google Scholar 

  • Dawkins R (1976) The selfish gene. Clarendon Press, Oxford

    Google Scholar 

  • Dawkins R (1986) The BlindWatchmaker, 1986. Longman, Essex

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Dias J, Captivo M, Clímaco J (2008) A memetic algorithm for multi-objective dynamic location problems. J Global Optim 42:221–253

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Book  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Mamoun MH (2010) A new proactive routing algorithm for manet. Int J Acad Res 2(2):199–204

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Neri F, Cotta C, Moscato P (2012) Handbook of memetic algorithms. Studies in computational intelligence, vol 379. Springer, Berlin

    Book  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Google Scholar 

  • Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evol Comput 1(1):67–82

    Article  Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to Carlos Cotta.

Rights and permissions

Reprints 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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-012-0893-6

Keywords

Navigation