Zusammenfassung - Simulierung von Evolvabilität als Lernalgorithmus: Empirische Untersuchungen zur Distributionsempfindlichkeit, Robustheit und Konstruktionskompromissen

Simulierung von Evolvabilität als Lernalgorithmus: Empirische Untersuchungen zur Distributionsempfindlichkeit, Robustheit und Konstruktionskompromissen

2025-07-24 04:32:31

{"Nicholas Fidalgo","Puyuan Ye"}

{cs.CC}

Diese Arbeit untersucht das Konzept der Evolvability, das 2009 von Valiant eingeführt wurde und Evolution als einen beschränkten Lernalgorithmus formalisiert, der ohne markierte Beispiele oder strukturelle Kenntnisse funktioniert. Die Autoren implementieren ein genetisches Algorithmus, der Valiants Modell simuliert und umfangreiche Experimente in sechs Klassen von Booleschen Funktionen durchführt: monotone Konjunktionen, monotone Disjunktionen, Parität, Mehrheit, allgemeine Konjunktionen und allgemeine Disjunktionen. Die Studie untersucht Evolvability unter einheitlichen und nicht-einheitlichen Verteilungen, untersucht die Auswirkungen festgelegter initialer Hypothesen und der Entfernung neutraler Mutationen und hebt hervor, wie diese Beschränkungen das Konvergenzverhalten verändern. Die Autoren bestätigen bekannte Ergebnisse (z.B. die Evolvability von monotonen Konjunktionen, die Nicht-Evolvability von Parität) und bieten das erste empirische Beweismaterial zur Evolvability von Mehrheits- und allgemeinen Booleschen Klassen. Die Ergebnisse zeigen drastische Leistungseinbrüche in mittleren Dimensionen (z.B. n = 10) und betonen die zentrale Rolle neutraler Mutationen bei der Vermeidung von Fitness-Plateaus. Die Autoren zeigen auch, dass Evolvability stark von der Eingangsverteilung abhängen kann. Diese Erkenntnisse klären praktische Grenzen der evolutionären Suche und schlagen neue Richtungen für theoretische Arbeiten vor, einschließlich möglicher Verbesserungen der Definitionen und Grenzen der Evolvability. Die Implementierung bietet einen rigorosen, erweiterbaren Rahmen für empirische Analyse und dient als Testfeld für zukünftige Erkundungen des Lernens durch Evolution. Die Studie trägt zu einer wachsenden Diskussion in der theoretischen Informatik über die Grenzen des möglichen Lernens bei und bietet wertvolle Einblicke in das praktische Verhalten der evolutionären Suche und die Faktoren, die ihren Erfolg beeinflussen.