Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Memetic Computing
Erschienen in: Memetic Computing 3/2015

01.09.2015 | Regular Research Paper

Memes as building blocks: a case study on evolutionary optimization + transfer learning for routing problems

verfasst von: Liang Feng, Yew-Soon Ong, Ah-Hwee Tan, Ivor W. Tsang

Erschienen in: Memetic Computing | Ausgabe 3/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

A significantly under-explored area of evolutionary optimization in the literature is the study of optimization methodologies that can evolve along with the problems solved. Particularly, present evolutionary optimization approaches generally start their search from scratch or the ground-zero state of knowledge, independent of how similar the given new problem of interest is to those optimized previously. There has thus been the apparent lack of automated knowledge transfers and reuse across problems. Taking this cue, this paper presents a Memetic Computational Paradigm based on Evolutionary Optimization \(+\) Transfer Learning for search, one that models how human solves problems, and embarks on a study towards intelligent evolutionary optimization of problems through the transfers of structured knowledge in the form of memes as building blocks learned from previous problem-solving experiences, to enhance future evolutionary searches. The proposed approach is composed of four culture-inspired operators, namely, Learning, Selection, Variation and Imitation. The role of the learning operator is to mine for latent knowledge buried in past experiences of problem-solving. The learning task is modelled as a mapping between past problem instances solved and the respective optimized solution by maximizing their statistical dependence. The selection operator serves to identify the high quality knowledge that shall replicate and transmit to future search, while the variation operator injects new innovations into the learned knowledge. The imitation operator, on the other hand, models the assimilation of innovated knowledge into the search. Studies on two separate established NP-hard problem domains and a realistic package collection/deliver problem are conducted to assess and validate the benefits of the proposed new memetic computation paradigm.
Vorheriger Artikel Editorial
Nächster Artikel A hybridization of clonal selection algorithm with iterated local search and variable neighborhood search for the feature selection problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
A meme is defined as the basic unit of cultural transmission in [31] stored in brains. In the context of computational intelligence, memes are defined as recurring real-world patterns or knowledge encoded in computational representations for the purpose of effective problem-solving [33].
 
2
Optimized solution here denotes the best solution found by the evolutionary solvers.
 
3
If a database of knowledge memes that are learned from relevant past problem solving experiences in the same domain is available, it can be loaded and leveraged upon.
 
4
Note that as the learning operation is conducted offline, it does not incur additional cost to the evolutionary optimization of \(\mathbf {p}^j_{new}\).
 
5
Dependency is a measure of the correlation of two random variables [63]. Here our interest on knowledge meme \(\mathbf {M}\) is in the form of a maximization of the statistical dependency, so as to ensure a maximal alignment between the transformed tasks distribution and the tasks distribution of the optimized solution. The trace of \(\mathbf {HKHY}\) is the empirical estimation of HSIC criterion [63], which is a nonlinear statistical dependence measures defined on two sets of random variables \(\mathbf {X}\) and \(\mathbf {Y}\), in their feature spaces, \(\phi (\mathbf {X})\) and \(\psi (\mathbf {Y})\). Mathematically, it tries to measure \(||C_{\mathbf {XY}}||^2\), where \(C_{\mathbf {XY}}:=E_{\mathbf {X,Y}}[(\phi (\mathbf {X})-\mu _{\mathbf {X}})\otimes (\psi (\mathbf {Y})-\mu _{\mathbf {Y}})]\), \(\mu _{\mathbf {X}}\) and \(\mu _{\mathbf {Y}}\) are the mean measures of \(\phi (\mathbf {X})\) and \(\psi (\mathbf {Y})\). A higher HSIC thus implies a higher nonlinear dependence between X and Y in the sense of the \(\phi (\mathbf {X})\) and \(\psi (\mathbf {Y})\) feature spaces.
 
6
From our experimental study, the problems in the benchmark set are mostly verified to be positively correlated.
 
7
Maximum mean discrepancy measures the distribution differences between two data sets, which can come in the form of vectors, sequences, graphs, and other common structured data types.
 
8
Due to page limit constraints, only representatives of each series have been shown.
 
9
Similar trends on enhancements in search efficiency of CAMA-M over CAMA has been obtained on all the other problem instances. However, due to the page limit constraint, only representatives of instances in each benchmark problem class can be presented in this paper.
 
10
Due to page limit constraints, only representatives of each series have been shown.
 
Literatur
1.
Bransford JD, Brown AL, Cocking RR (2000) How people learn: brain, mind, experience, and school. National Academies Press, Washington
2.
Byrnes JP (1996) Cognitive development and learning in instructional contexts. Allyn and Bacon, Boston
3.
Reif M, Shafait F, Dengel A (2012) Meta-learning for evolutionary parameter optimization of classifiers. Mach Learn 87(3):357–380MathSciNet
4.
Ishibuchi H, Kwon K, Tanaka H (1995) A learning algorithm of fuzzy neural networks with triangular fuzzy weights. Fuzzy Sets Syst 71(3):277–293
5.
Tan KC, Chen YJ, Tan KK, Lee TH (2005) Task-oriented developmental learning for humanoid robots. IEEE Trans Ind Electron 52(3):906–914
6.
Tan KC, Liu DK, Chen YJ, Wang LF (2005) Intelligent sensor fusion and learning for autonomous robot navigation. Appl Artif Intell 19(5):433–456
7.
Nojima Y, Ishibuchi H (2009) Incorporation of user preference into multi-objective genetic fuzzy rule selection for pattern classification problems. Artif Life Robot 14(3):418–421
8.
Pan SJ, Yang Q (2010) A survey on transfer learning. IEEE Trans Knowl Des Eng 22(10):1345–1359
9.
Taylor ME, Stone P (2009) Transfer learning for reinforcement learning domains: a survey. J Mach Learn Res 10:1633–1685
10.
Pelikan M, Hauschild MW, Lanzi PL (2012) Transfer learning, soft distance-based bias, and the hierarchical boa. In: Proceedings of the 12th international conference on parallel problem solving from nature—volume part I, PPSN’12, pp 173–183
11.
Bahceci E, Miikkulainen R (2008) Transfer of evolved pattern-based heuristics in games. In: IEEE symposium on computational intelligence and games, 2008. CIG ’08, pp 220–227
12.
Asta S, Ozcan E, Parkes AJ, Etaner-Uyar AS (2013) Generalizing hyper-heuristics via apprenticeship learning. In: Middendorf M, Blum C (eds) EvoCOP, volume 7832 of Lecture Notes in Computer Science. Springer, Berlin, pp 169–178
13.
Iqbal M, Browne W, Zhang MJ (2014) Reusing building blocks of extracted knowledge to solve complex, large-scale boolean problems. IEEE Trans Evol Comput 18:465–580
14.
Jin YC (2010) Knowledge incorporation in evolutionary computation. Studies in fuzziness and soft computing. Springer, Berlin
15.
Wang H, Kwong S, Jin YC, Wei W, Man K (2005) Agent-based evolutionary approach to interpretable rule-based knowledge extraction. IEEE Trans Syst Man Cybern C 29(2):143–155
16.
Tang K, Mei Y, Yao X (2009) Memetic algorithm with extended neighborhood search for capacitated arc routing problems. IEEE Trans Evol Comput 13(5):1159–1166
17.
Calian D, Bacardit J (2013) Integrating memetic search into the biohel evolutionary learning system for large-scale datasets. Memetic Comput 5(2):95–130
18.
Tang LX, Wang XP (2013) A hybrid multiobjective evolutionary algorithm for multiobjective optimization problems. IEEE Trans Evol Comput 17(1):20–45
19.
Tayarani-N MH, Prugel-Bennett A (2013) On the landscape of combinatorial optimization problems. IEEE Trans Evol Comput 18(3):420–434
20.
Cheng R, Zhang X, Tian Y, Jin Y (2014) An efficient approach to nondominated sorting for evolutionary multiobjective optimization. IEEE Trans Evol Comput 19:201–213
21.
Sutcliffe AG, Wang D (2014) Memetic evolution in the development of proto-language. Memetic Comput 6(1):3–18
22.
Ray T, Asafuddoula M, Sarker R (2014) A decomposition-based evolutionary algorithm for many objective optimization. IEEE Trans Evol Comput 19(3):445–460
23.
Patvardhan C, Bansal S, Srivastav A (2015) Quantum-inspired evolutionary algorithm for difficult knapsack problems. Memetic Comput 7(2):135–155
24.
Ong YS, Keane AJ (2004) Meta-Lamarckian learning in memetic algorithms. IEEE Trans Evol Comput 8(2):99–110
25.
Nguyen QC, Ong YS, Lim MH (2009) A probabilistic memetic framework. IEEE Trans Evol Comput 13(3):604–623
26.
Gupta A, Ong YS, Feng L (2015) Multifactorial evolution: towards evolutionary multitasking. IEEE Trans Evol Comput (accepted)
27.
Neri F, Cotta C, Moscato P (2011) Handbook of memetic algorithms. Studies in computational intelligence. Springer, Berlin
28.
Kramer O (2010) Iterated local search with powell’s method: a memetic algorithm for continuous global optimization. Memetic Comput 2(1):69–83
29.
Tang K, Mei Y, Yao X (2009) Memetic algorithm with extended neighborhood search for capacitated arc routing problems. IEEE Trans Evol Comput 13(5):1151–1166
30.
Chen XS, Ong YS, Lim MH, Tan KC (2011) A multi-facet survey on memetic computation. IEEE Trans Evol Comput 5:591–607
31.
Dawkins R (1976) The selfish gene. Oxford University Press, Oxford
32.
Blackmore S (1999) The meme machine. Oxford University Press, Oxford
33.
Ong YS, Lim MH, Chen XS (2010) Research frontier: memetic computation—past, present and future. IEEE Comput Intell Mag 5(2):24–36
34.
Chu PC, Beasley JE (1997) A genetic algorithm for the generalised assignment problem. Comput Oper Res 24(1):17–23MathSciNet
35.
Jensen MT (2003) Generating robust and flexible job shop schedules using genetic algorithms. IEEE Trans Evol Comput 7(3):275–288
36.
Neri F, Toivanen J, Cascella GL et al (2007) An adaptive multimeme algorithm for designing HIV multidrug therapies. IEEE/ACM Trans Comput Biol Bioinform 4(2):264–278
37.
Elsayed S, Sarker R, Essam D (2012) Memetic multi-topology particle swarm optimizer for constrained optimization. In: IEEE congress on evolutionary computation
38.
Louis SJ, McDonnell J (2004) Learning with case-injected genetic algorithms. IEEE Trans Evol Comput 8(4):316–328
39.
Cunningham P, Smyth B (1997) Case-based reasoning in scheduling:reusing solution components. Int J Prod Res 35(4):2947–2961
40.
Yang SX, Yao X (2008) Population-based incremental learning with associative memory for dynamic environments. IEEE Trans Evol Comput 12(5):542–561
41.
Pelikan M, Hauschild MW (2012) Learn from the past: improving model-directed optimization by transfer learning based on distance-based bias. Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri in St. Louis, MO, USA. Tech. Rep, 2012007
42.
Santana R, Mendiburu A, Lozano JA (2012) Structural transfer using edas: An application to multi-marker tagging snp selection. In: 2012 IEEE congress on evolutionary computation (CEC), pp 1–8
43.
Santana R, Armañanzas R, Bielza C, Larrañaga P (2013) Network measures for information extraction in evolutionary algorithms. International Journal of Computational Intelligence Systems 6(6):1163–1188
44.
Lynch A (1991) Thought contagion as abstract evolution. J Ideas 2:3–10
45.
Brodie R (1996) Virus of the mind: the new science of the meme. Integral Press, Seattle
46.
Grant G (1990) Memetic lexicon. In: Principia Cybernetica Web
47.
Situngkir H (2004) On selfish memes: culture as complex adaptive system. J Soc Complex 2(1):20–32
48.
Heylighen F, Chielens K (2008) Cultural evolution and memetics. In: Meyers B (ed) Encyclopedia of complexity and system science. Springer, Berlin
49.
Nguyen QH, Ong YS, Lim MH (2008) Non-genetic transmission of memes by diffusion. In: Proceedings of the 10th annual conference on genetic and evolutionary computation (GECCO ’08), (8):1017–1024
50.
Meuth R, Lim MH, Ong YS, Wunsch D (2009) A proposition on memes and meta-memes in computing for higher-order learning. Memetic Comput 1:85–100
51.
52.
Minsky M (1986) The society of mind. Simon & Schuster, New York
53.
Dantzig G, Ramser JH (1959) The truck dispatching problem. Manag Sci 6:80–91MathSciNet
54.
Golden B, Wong R (1981) Capacitated arc routing problems. Networks 11(3):305–315MathSciNet
55.
Chen XS, Ong YS, Lim MH, Yeo SP (2011) Cooperating memes for vehicle routing problems. Int J Innov Comput 7(11):1–10
56.
Cordeau JF, Laporte G, Mercier A (2001) A unified tabu search heuristic for vehicle routing problems with time windows. J Oper Res Soc 52:928–936
57.
Prins C (2004) A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Oper Res 31:1985–2002MathSciNet
58.
Reimann M, Doerner K, Hartl RF (2004) D-ants: savings based ants divide and conquer the vehicle routing problem. Comput Oper Res 31:563–591
59.
Lin SW, Lee ZJ, Ying KC, Lee CY (2009) Applying hybrid meta-heuristics for capacitated vehicle routing problem. Expert Syst Appl 36(2, Part 1):1505–1512
60.
Lacomme P, Prins C, Ramdane-Chérif W (2004) Competitive memetic algorithms for arc routing problem. Ann Oper Res 141(1–4):159–185
61.
Mei Y, Tang K, Yao X (2009) Improved memetic algorithm for capacitated arc routing problem. In: IEEE congress on evolutionary computation, pp 1699–1706
62.
Feng L, Ong YS, Nguyen QH, Tan AH (2010) Towards probabilistic memetic algorithm: an initial study on capacitated arc routing problem. In: IEEE congress on evolutionary computation, pp 18–23
63.
Gretton A, Bousquet O, Smola A, Schölkopf B (2005) Measuring statistical dependence with hilbert-schmidt norms. In: Proceedings algorithmic learning theory, pp 63–77
64.
Zhuang J, Tsang I, Hoi SCH (2011) A family of simple non-parametric kernel learning algorithms. J Mach Learn Res (JMLR) 12:1313–1347MathSciNet
65.
Song L, Smola A, Gretton A, Borgwardt KM (2007) A dependence maximization view of clustering. In: Proceedings of the 24th international conference on machine learning, pp 815–822
66.
Runco MA, Pritzker S (1999) Encyclopedia of creativity. Academic Press, London
67.
Chen XS, Ong YS (2012) A conceptual modeling of meme complexes in stochastic search. IEEE Trans Syst Man Cybern C Appl Rev 99:1–8
68.
Dijkstra EW (1959) A note on two problems in connection with graphs. Numerische Mathematik 1:269–271MathSciNet
69.
Borg I, Groenen PJF (2005) Modern multidimensional scaling: theory and applications. Springer, Berlin
70.
Chen X, Feng L, Ong YS (2012) A self-adaptive memeplexes robust search scheme for solving stochastic demands vehicle routing problem. Int J Syst Serv 43(7):1347–1366MathSciNet
Metadaten
Titel
Memes as building blocks: a case study on evolutionary optimization + transfer learning for routing problems
verfasst von
Liang Feng
Yew-Soon Ong
Ah-Hwee Tan
Ivor W. Tsang
Publikationsdatum
01.09.2015
Verlag
Springer Berlin Heidelberg
Erschienen in
Memetic Computing / Ausgabe 3/2015
Print ISSN: 1865-9284
Elektronische ISSN: 1865-9292
DOI
https://doi.org/10.1007/s12293-015-0166-x

Weitere Artikel der Ausgabe 3/2015

Memetic Computing 3/2015 Zur Ausgabe

Regular Research Paper

On composing an algorithm portfolio

Regular Research Paper

Accelerating Artificial Bee Colony algorithm with adaptive local search

Regular Research Paper

Finite-time synchronization of chaotic neural networks with mixed time-varying delays and stochastic disturbance

Editorial

Editorial

Regular Research Paper

A hybridization of clonal selection algorithm with iterated local search and variable neighborhood search for the feature selection problem

Premium Partner

    Bildnachweise