UMDA with Random Affine Maps

Dieses Kapitel vertieft sich in die Verbesserung des Univariate Marginal Distribution Algorithm (UMDA) durch die Integration zufallsaffiner Karten, wobei das Ziel darin besteht, implizit statistische Abhängigkeiten zwischen Variablen zu erzeugen und gleichzeitig die Rechenkomplexität gering zu halten. Die Studie untersucht zwei Versionen von UMDA mit Random Affine Maps (RAMU): eine, die Bitvektoren im latenten Raum mithilfe eines einzigen Wahrscheinlichkeitsvektors abtastet, und eine andere, die zwei Wahrscheinlichkeitsvektoren einsetzt, einen im latenten Raum und einen im Lösungsraum, mit der Option für Crossover. Die Forschung führt Fixed-Budget-Experimente durch, um die Leistung von RAMU mit der traditionellen UMDA in 19 Fitnessfunktionen zu vergleichen, hauptsächlich in Dimension 100. Zu den wichtigsten Erkenntnissen gehört die Fähigkeit von RAMU, oft bessere Lösungen als UMDA zu finden, manchmal sogar schneller, insbesondere mit Funktionen wie nk, max-3sat, labs, walsh und ising. Die langsamere Dynamik von RAMU zeigt sich jedoch bei Funktionen wie OneMax oder LeadingOnes. Das Kapitel untersucht auch den Einfluss von Sequenzlängenmodi, Crossover-Wahrscheinlichkeit und Abtastwahrscheinlichkeit aus dem latenten Raum auf die Leistung von RAMU. Die Schlussfolgerung unterstreicht das Potenzial von RAMU, in bestimmten Szenarien die traditionelle UMDA zu übertreffen, was weitere Experimente mit größeren Dimensionen und anderen Algorithmen niedriger Komplexität nahelegt, um diese frühen Ergebnisse zu bestätigen. Darüber hinaus wird in diesem Kapitel die Anwendbarkeit zufälliger affiner Karten auf andere Schätzalgorithmen (EDAs) und die Notwendigkeit von Modifikationen für inkrementelle EDAs wie PBIL diskutiert.