Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Statistics of Critical Avalanches in Vertical Nanopillar Arrays Read chapter Read first chapter

2014 | OriginalPaper | Chapter

Island-Model-Based Distributed Modified Extremal Optimization for Reducing Crossovers in Reconciliation Graph

Authors : Keiichi Tamura, Hajime Kitakami, Akihiro Nakada

Published in: Transactions on Engineering Technologies

Publisher: Springer Netherlands

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

To determine the mechanism of molecular evolution, molecular biologists need to carry out reconciliation work. In reconciliation work, they compare the relation between two heterogeneous phylogenetic trees and the relation between a phylogenetic tree and a taxonomic tree. Phylogenetic trees and taxonomic trees are referred to as ordered trees and a reconciliation graph is constructed from two ordered trees. In the reconciliation graph, the leaf nodes of the two ordered trees face each other. Furthermore, leaf nodes with the same label name are connected to each other by an edge. To perform reconciliation work efficiently, it is necessary to find the state with the minimum number of crossovers of edges between leaf nodes. Reducing crossovers in a reconciliation graph is the combinatorial optimization problem that finds the state with the minimum number of crossovers. In this chapter, a novel bio-inspired heuristic called island-model-based distributed modified extremal optimization (IDMEO) is presented. This heuristic is a hybrid of population-based modified extremal optimization (PMEO) and the distributed genetic algorithm using the island model that is used for reducing crossovers in a reconciliation graph.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Investigating Polling Cycle Time with Waited-Based DBA in GPONs
next chapter Early-Warning System in Bridge Monitoring Based on Acceleration and Displacement Data Domain
Literature
1.
Goodman M, Czelusniak J, Moore G, Romero-Herrera A, Matsuda G (1979) Fitting the gene lineage into its species lineage, a parsimony strategy illustrated bycladograms constructed from globin sequences. Syst Zoo 28:132–163CrossRef
2.
Page RDM (1998) Genetree: comparing gene and species phylogenies using reconciled trees. Bioinformatics 14(9):819–820CrossRef
3.
Page RDM, Charleston MA (1997) Reconciled trees and incongruent gene and species trees. Discr Math Theor Comput Sci 37:57–70MathSciNet
4.
Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning, Addison-Wesley Professional
5.
Kitakami H, Mori Y (2002) Reducing crossovers in reconciliation graphs using the coupling cluster exchange method with a genetic algorithm. Active mining. IOS press 79:163–174
6.
Kitakami H, Nishimoto M (2000) Constraint satisfaction for reconciling heterogeneous tree databases. In: Proceedings of DEXA 2000, pp 624–633
7.
Boettcher S (2000) Extremal optimization: heuristics via coevolutionary avalanches. Comput Sci Eng 2(6):75–82CrossRef
8.
Boettcher S, Percus A (2000) Nature’s way of optimizing. Artif Intell 119(1–2):275–286CrossRefMATH
9.
Boettcher S, Percus AG (1999) Extremal optimization: methods derived from co-evolution. In: Proceedings of GECCO 1999, pp 825–832
10.
Tamura K, Mori Y, Kitakami H (2008) Reducing crossovers in reconciliation graphs with extremal optimization (in japanese). Trans Inf Process Soc Japan 49(4(TOM 20)):105–116
11.
Hara N, Tamura K, Kitakami H (2010) Modified eo-based evolutionary algorithm for reducing crossovers of reconciliation graph. In: Proceedings of NaBIC 2010, pp 169–176
12.
Bak P, Tang C, Wiesenfeld K (1987) Self-organized criticality. an explanation of 1/f noise. Phys Rev Lett 59:381–384MathSciNetCrossRef
13.
Tamura K, Kitakami H, Nakada A (2013) Distributed modified extremal optimization for reducing crossovers in reconciliation graph. In: Tecture Notes in engineering and computer science. Proceedings of the international multiConference of engineers and computer scientists 2013, 13–15 Mar 2013, Hong Kong, pp 1–6
14.
Belding TC (1995) The distributed genetic algorithm revisited. In: Proceedings of the 6th international conference on genetic algorithms, pp 114–121
15.
Whitley WD, Rana SB, Heckendorn RB (1997) Island model genetic algorithms and linearly separable problems. In: Selected papers from AISB workshop on evolutionary, computing, pp 109–125
16.
Boettcher S, Percus AG (2004) Extremal optimization at the phase transition of the 3-coloring problem. Phys Rev E 69:066703CrossRef
17.
Duch J, Arenas A (2005) Community detection in complex networks using extremal optimization. Physi Rev E 72:027104CrossRef
18.
Meshoul S, Batouche M (2002) Robust point correspondence for image registration using optimization with extremal dynamics. In: Proceedings of DAGM-symposium 2002, pp 330–337
19.
Zhou T, Bai WJ, Cheng LJ, Wang BH (2005) Continuous extremal optimization for lennard-jones clusters. Phys Rev E 72:016702CrossRef
20.
Chen MR, Li X, Zhang X, Lu YZ (2010) A novel particle swarm optimizer hybridized with extremal optimization. Appl Soft Comput 10(2):367–373CrossRef
21.
Chen MR, Lu YZ, Yang G (2008) Multiobjective optimization using population-based extremal optimization. Neural Comput Appl 17(2):101–109CrossRef
22.
Randall M, Lewis A (2006) An extended extremal optimisation model for parallel architectures. In: Proceedings of E-SCIENCE ’06, p 114
23.
Hiroshi S, Isao O, Shigenobu K (1997) A new generation alternation model of genetic algorithms and its assessment. J Jap Soc Artif Intell 12(5):734–744
Metadata
Title
Island-Model-Based Distributed Modified Extremal Optimization for Reducing Crossovers in Reconciliation Graph
Authors
Keiichi Tamura
Hajime Kitakami
Akihiro Nakada
Copyright Year
2014
Publisher
Springer Netherlands
Book
Transactions on Engineering Technologies

Print ISBN: 978-94-007-7683-8

Electronic ISBN: 978-94-007-7684-5

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-94-007-7684-5_11

Premium Partners

    Image Credits