Kombinatorische Explosion
Heuristik
Basiswissen
Man spricht von einer kombinatorischen Explosion wenn eine geringe Erhöhung der Anzahl von Elementen zu einer so katastrophalen[2] Erhöhung der möglichen Kombinationen dieser Elemente führt. Katastrophal ist die Erhöhung deshalb, weil damit verbundene Fragen praktisch rechnerisch nicht mehr beantwortet werden können[2]. Die kombinatorische Explosion spielt unter anderem eine wichtige Rolle in der Bio(Chemie) und der Evolution.
Beispiel I: die Kombination von Zahlen
Es gibt 6 verschiedene Möglichkeiten, die Buchstaben ABC in verschiedenen Reihenfolgen anzuordnen[2]. Die Buchstaben sind hier die Elemente, die kombiniert werden sollen. Hat man die Buchstaben ABCD, so gibt es bereits 24 mögliche Kombinationen. Die Liste zeigt für jede Anzahl von Buchstaben (links) wie viele Kombinationen (rechts) es gibt:
0 -> 1
1 -> 1
2 -> 2
3 -> 6
4 -> 24
5 -> 120
6 -> 720
7 -> 5040
8 -> 40320
9 -> 362880
10 -> 3628800
11 -> 39916800
Beispiel II: das Lateinische Quadrat
Deutlich "katastrophaler" ist der Anstieg der Kombinationen bei einen sogenannten lateinischen Quadrat[3]. Angenommen man hat ein Quadrat mit genau 4 Zeilen und vier Spalten. Zusätzlich hat man Plättchen, die immer auch eine von insgesamt nur vier verschiedenen Farben haben. Ein Plättchen kann also zum Beispiel gelb, grün, rot oder oder blau sein. Die kombinatorische Explosion ergibt sich aus der folgenden Frage: wie viele Möglichkeiten gibt es, die Plättchen von n verschiedenen Farben in dem Quadrat mit n Zeilen und n Spalten anzuordnen?
- n=1 -> 1
- n=2 -> 2
- n=3 -> 12
- n=4 -> 576
- n=5 -> 161,280
- n=6 -> 812,851,200
- n=7 -> 61,479,419,904,000
- n=8 -> 108,776,032,459,082,956,800
- n=9 -> 5,524,751,496,156,892,842,531,225,600
- n=10 -> 9,982,437,658,213,039,871,725,064,756,920,320,000
- n=11 -> 776,966,836,171,770,144,107,444,346,734,230,682,311,065,600,000
Ein Weg, wie die biologische Evolution in der unpraktisch großen Anzahl von Entwicklungsmöglichkeiten die günstigen Pfade findet sind nach Turchin sogenannte Metasystem-Transitionen ↗
Die kombinatorische Explosion in der Biologie
Die beiden Beispiele zeigen einen interessanten Trend. Im ersten Beispiel konnte man die Elemente nur in der Reihenfolge ändern. Das Problem war "eindimensional". Im zweiten Beispiel konnte man die Elemente in der Zeile und der Spalte unterschiedlich platzieren. Das lateinische Quadrat ist "zweidimensional". Macht man gedanklich aus dem lateinischen Quadrat einen lateinischen Würfel, so wird das Problem dreidimensional. Das würde zu einem noch "katastrophalerem" Anstieg der Möglichkeiten führen.
1.0 Je mehr Dimensionen oder Freiheitsgrade, desto ausgeprägter ist die "Explosion".
In der Chemie kann man Atome zu dreidimensionalen Gebilden verbinden. Wie sich die Moleküle dann chemisch verhalten, hängt stark von ihrer genauen Form im dreidimensionalen Raum ab. Das trifft vor allem auf Proteine zu. So besteht ein Molekül des roten Blutstoffs Hämoglobin aus rund 10 tausend Atomen, die wiederum zu einigen Hundert Aminosäuren zusammengesetzt sind[6]. Man denke sich die Liste der Kombinationsmöglichkeiten oben bis zu n=10000 forgesetzt, um die Anzahl der Kombinationsmöglichkeiten abzuschätzen. Die Frage ist nun: wie gelang es der chemischen und biologischen Evolution, aus der praktisch unendlich großen Anzahl möglicher Kombinationen, die wenigen biologisch sinnvollen herauszufinden[5]?
Metasysteme als Lösung?
In der Evolution kam es immer wieder zu einer Art Einfrieren[7] oder Lock-in-Effekt von Bausteinen, die in sich nicht mehr oder nur noch geringfügig variiert wurden. So gibt es nur rund 21 Aminosäuren für alle Lebewesen der Erde. Und alle höheren Lebensformen setzen sich aus Zellen mit einem mehr oder weniger ähnlichem Bauplan zusammen.
2.0 Das Einfrieren von Bausteinen höherer Komplexiät könnte die kombinatorische Explosion handhabbarer machen.
Es entsteht ein Bild von sogenannten Metasystem-Transitionen, bei dem die Bauteile niederer Stufen von Komplexität sozusagen als Elemente höherer Komplexität sozusagen eingefroren werden (lock-in). Ist das Einfrieren der Grundbausteine höherer Komplexität eine Strategie, um eine kombinatorische Explosion handhabbarer zu machen? Siehe dazu den Artikel zur Aminosäure-Barriere ↗
Fußnoten
- [1] Zum Problem der kombinatorischen Explosion in der Evolution: "The number of possible arrangements grows catastrophically with the number of units n. Let us take the simplest case where the units always form a linear structure. Then our arrangements are permutations of n elements, and there are n! of them. If n = 5, the number of arrangements is 120. You can easily try them all. If n = 100, there are some 10⁵⁶ arrangements. Even if there are billions of billions of useful arrangements of 100 units, the probability that you will find one in 10 billion years, is vanishing. Neither can mother nature try all possible arrangements of many units." Die Lösung sind sogenannte Metasystem-Transitionen: "Such is the origin of hierarchical structures in evolution, both biological and post-biological. This is a way to use the geometric and probabilistic factors, but avoid combinatorial explosion." In: Valentin Turchin: A Dialogue on Metasystem Transition. The City College of New York. July 12, 1999. Dort die Seite 34. Online: http://cleamc11.vub.ac.be/Papers/Turchin/dialog.pdf
- [2] Combinatorial explosion "occurs when a small increase in the number of elements that can be combined increase the number of combinations to be computed so fast that it quickly reaches computational limits. E. g., the number of possible coalitions (partitions of unlike individuals into like parts)
- n=[2] Rechnerisch handelt es sich um sogenannte Permutation der Buchstaben. Im Beispiel gäbe es die folgenden Permutationen: A B C ✔ A C B ✔ B A C ✔ B C A ✔ C A B ✔ C B A ✔. Die Anzahl möglicher Permutationen berechnet man mit der sogenannten Fakultät: 3! = 1·2·3 = 6. Siehe mehr dazu unter Permutation ↗
- [3] Ein lateinisches Quadrat ist ein Quadrat mit immer genauso vielen Zeilen (links nach rechts) wie Spalten (oben nach unten). Die Anzahl der Zeilen nennt man kurz n. Man hat dann auch auch Plättchen die mit insgesamt n verschiedenen Farben oder Buchstaben oder sonstigen Eigenschaften. Die Aufgabe ist es nun, die Plättchen so auf die Felder des Quadrates zu legen, dass jedes Symbol nur genau einmal in einer Zeile oder auch in einer Spalte vorkommt.
- [4] Ein Molekül Hämoglobin, also des roten Blutstoffs besteht aus rund 10 Tausend Atomen: "Its 10,000 atoms are assembled into four chains, each a helix with several bends." In: Perutz, M. F. “THE HEMOGLOBIN MOLECULE.” Scientific American, vol. 211, no. 5, 1964, pp. 64–79. JSTOR, http://www.jstor.org/stable/24931693. Accessed 25 Mar. 2024.
- [5] Die kombinatorische Explosion als Problem in der (Bio)Chemie: "Problems of this kind are encountered in biophysical chemistry when biopolymer molecules are built from several classes of monomers, in combinatorial chemistry when new molecules are formed through combination of several reactions, or in molecular genetics when regulation and control networks are considered." Der Artikel betrachtet besonders die Entstehung von Komplexität in der präbiotischen Evolution. In: Peter Schuster: Taming combinatorial explosion. In: PNAS. 97 (14) 7678-7680. Juni 2000. DOI: https://doi.org/10.1073/pnas.150237097
- [6] In der Biologie des Lebens auf unserer Erde kommen rund 21 verschiedene Aminosäuren vor. Chemisch möglich wären tausende von verschiedenen. Die Idee, dass die Beschränkung auf einige wenige der vielen möglichen Aminosäuren das Problem der kombinatorischen Explosion vereinfachen könnte, wird diskutiert im Artikel zur Aminosäure-Barriere ↗
- [7] Zum Einfrieren von Komponenten oder Modulen als Erfolgsstrategie: Stuart Alan Kauffmann: Requirements for evolvability in complex systems: Orderly dynamics and frozen components. In: Physica D: Nonlinear Phenomena. Volume 42, Issues 1–3, June 1990, Pages 135-152. DOI:
- [8] Lock-in als Ausschluss biologischer Möglichkeiten: "any mutation (or sets of mutations) that creates the possibility of new phenotypes can persist for a very long period of time. That is, innovations that make possible a large range of new phenotypes can become frozen in time. By becoming frozen, these novel structures can no longer change, which means a range of phenotypes also become impossible. This opening and closing of phenotypic space is a new mechanism of macro-evolution." In: Julian Z. Xue, Leonid Chindelevich, Frédéric Guichard: Supply-driven evolution explains the locking-in of structures that open new evolutionary possibilities, such as higher hierarchies of organization. In: bioRxiv. 2022.07.18.500397. DOI: doi.org/10.1101/2022.07.18.500397. Siehe auch Lock-in-Effekt ↗
Aminosäure-Barriere ↗
Bernoulli-Kette ↗
Dimension ↗
Evolution ↗
Fakultät [!] ↗
Frozen Components ↗
Genetischer Algorithmus ↗
Heuristik ↗
Kombination [Definition] ↗
Kombinationsproblem [Philosophie des Geistes] ↗
Metasystem-Transitionen ↗
Modularität (Biologie) ↗
Permutation ↗
Physik-Lexikon ↗