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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
What Makes an Instance Difficult for Black-Box 0–1 Evolutionary Multiobjective Optimizers? Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

Beam-ACO for the Repetition-Free Longest Common Subsequence Problem

verfasst von : Christian Blum, Maria J. Blesa, Borja Calvo

Erschienen in: Artificial Evolution

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In this paper we propose a Beam-ACO approach for a combinatorial optimization problem known as the repetition-free longest common subsequence problem. Given two input sequences \(x\) and \(y\) over a finite alphabet \(\varSigma \), this problem concerns to find a longest common subsequence of \(x\) and \(y\) in which no letter is repeated. Beam-ACO algorithms are combinations between the metaheuristic ant colony optimization and a deterministic tree search technique called beam search. The algorithm that we present is an adaptation of a previously published Beam-ACO algorithm for the classical longest common subsequence problem. The results of the proposed algorithm outperform existing heuristics from the literature.

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
Vorheriges Kapitel Effective Multi-caste Ant Colony System for Large Dynamic Traveling Salesperson Problems
Nächstes Kapitel Medium-Voltage Distribution Network Expansion Planning with Gene-pool Optimal Mixing Evolutionary Algorithms
Literatur
1.
Adi, S.S., Braga, M.D.V., Fernandes, C.G., Ferreira, C.E., Martinez, F.V., Sagot, M.F., Stefanes, M.A., Tjandraatmadja, C., Wakabayashi, Y.: Repetition-free longest common subsquence. Disc. Appl. Math. 158, 1315–1324 (2010)MathSciNetCrossRefMATH
2.
Aho, A., Hopcroft, J., Ullman, J.: Data structures and algorithms. Addison-Wesley, Reading (1983)MATH
3.
Blum, C.: Beam-ACO for the longest common subsequence problem. In: Fogel, G., et al. (eds.) Proceedings of CEC 2010 - Congress on Evolutionary Computation, vol. 2. IEEE Press, Piscataway (2010)
4.
Blum, C., Dorigo, M.: The hyper-cube framework for ant colony optimization. IEEE Trans. Man Syst. Cybern. - Part B 34(2), 1161–1172 (2004)CrossRef
5.
Bonizzoni, P., Della Vedova, G.: Variants of constrained longest common subsequence. Inf. Process. Lett. 110(20), 877–881 (2010)MathSciNetCrossRefMATH
6.
Easton, T., Singireddy, A.: A large neighborhood search heuristic for the longest common subsequence problem. J. Heuristics 14(3), 271–283 (2008)CrossRefMATH
7.
Gusfield, D.: Algorithms on Strings, Trees, and Sequences. Computer Science and Computational Biology, Cambridge University Press, Cambridge (1997)CrossRefMATH
8.
Jiang, T., Lin, G., Ma, B., Zhang, K.: A general edit distance between RNA structures. J. Comput. Biol. 9(2), 371–388 (2002)CrossRef
9.
Julstrom, B.A., Hinkemeyer, B.: Starting from scratch: growing longest common subsequences with evolution. In: Runarsson, T.P., Beyer, H.-G., Burke, E.K., Merelo-Guervós, J.J., Whitley, L.D., Yao, X. (eds.) PPSN 2006. LNCS, vol. 4193, pp. 930–938. Springer, Heidelberg (2006)CrossRef
10.
11.
Shyu, S.J., Tsai, C.Y.: Finding the longest common subsequence for multiple biological sequences by ant colony optimization. Comput. Oper. Res. 36(1), 73–91 (2009)MathSciNetCrossRefMATH
12.
Smith, T., Waterman, M.: Identification of common molecular subsequences. J. Mol. Biol. 147(1), 195–197 (1981)CrossRef
13.
Storer, J.: Data Compression: Methods and Theory. Computer Science Press, Rockville (1988)
Metadaten
Titel
Beam-ACO for the Repetition-Free Longest Common Subsequence Problem
verfasst von
Christian Blum
Maria J. Blesa
Borja Calvo
Copyright-Jahr
2014
Buch
Artificial Evolution

Print ISBN: 978-3-319-11682-2

Electronic ISBN: 978-3-319-11683-9

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-319-11683-9_7