Loading…
Das zentrale Thema der Dissertation ist "Probabilistic Incremental Program Evolution" (PIPE). PIPE ist ein neuer, evolutionärer Algorithmus, der stochastische Modelle verwendet um Computerprogramme zu finden, die eine Lösung zu gegebenen Problemen darstellen. Insbesondere Probleme mit Regularitäten in ihren Lösungen sind für die Programmsuche interessant. Regularitäten ermöglichen kurze algorithmische Lösungsbeschreibungen. Kürzere Beschreibungen werden im Allgemeinen schneller gefunden. Programmsuche kann daher effizient sein, wenn die Abbildung des Lösungsraumes in den Programmraum den Suchraum verkleinert. Der Programmraum ist jedoch normalerweise ein diskontinuierlicher Raum. Gradientenabstiegsbasierte Optimierungsverfahren sind daher für die Programmsuche im Allgemeinen nicht anwendbar. Übrig bleiben verschiedene zufallsbasierte Verfahren, unter anderem auch evolutionäre Algorithmen. Das Ziel dieser Arbeit ist es PIPE vorzustellen und Methoden zu definieren, die PIPE auf ein breites Spektrum von Problemen anwendbar machen. Zuerst präsentieren wir PIPE und zeigen, dass PIPE für verschiedene Anwendungen eingesetzt werden kann, unter anderem auch für komplexe Anwendungen, wie z.B. das Lernen in Multiagentensystemen. Dann erhöhen wir mittels strukturierter Programme, wo die Programminstruktionsabfolge zum Teil fest vorgegeben ist, PIPE's Leistungsfähigkeiten. Programme ohne internen Speicher können keine Probleme lösen, die der Markov Eigenschaft nicht genügen, d.h. deren Output nicht nur vom Input abhängt, sondern auch vom zeitlichen Kontext des Inputs. Um das Anwendungsgebiet von PIPE zu erweitern, zeigen wir, wie PIPE Programme mit internem Speicher finden kann. Dabei scheint PIPE für Probleme mit sehr langen Zeitspannen zwischen relevanten Inputs und ihren korrespondierenden Outputs besonders gut geeignet zu sein. Mit der Lösung von hochkomplexen Aufgaben, d.h. wenn z.B. viele Datenabhängigkeiten in Programmen abgebildet werden müssen, kann der PIPE Algorithmus überfordert werden. Um PIPE auch für solche Probleme konkurrenzfähiger zu machen, haben wir "filtering" entwickelt. Filtering ist ein optimierungsalgorithmusunabhängiges, automatisches Aufgabenteilungsverfahren. Es teilt nicht nur die eigentliche Aufgabe in weniger komplexe Teilaufgaben, sondern zerlegt auch das Problem des Zusammenführens der Teillösungen in Teilaufgaben.
Probabilistic Incremental Program Evolution (PIPE) is a machine learning (ML) technique. Just like other ML techniques such as, e.g., neural networks, reinforcement learning, or evolutionary algorithms, PIPE tries to enable computers to solve problems automatically, i.e. to find solutions by ?learning? from experience (examples), rather than being explicitly programmed to solve a task. PIPE is an evolutionary optimization algorithm, which employs stochastic models to search for computer programs that embody solutions to given problems.
