UMDA with Random Affine Maps

This chapter delves into the enhancement of the Univariate Marginal Distribution Algorithm (UMDA) through the integration of random affine maps, aiming to implicitly generate statistical dependencies between variables while maintaining low computational complexity. The study explores two versions of UMDA with random affine maps (RAMU): one that samples bit vectors in the latent space using a single probability vector and another that employs two probability vectors, one in the latent space and one in the solution space, with the option for crossover. The research conducts fixed-budget experiments to compare the performance of RAMU against traditional UMDA across 19 fitness functions, primarily in dimension 100. Key findings include RAMU's ability to often find better solutions than UMDA, sometimes even faster, particularly with functions like nk, max-3sat, labs, walsh, and ising. However, the slower dynamics of RAMU are evident with functions such as OneMax or LeadingOnes. The chapter also investigates the influence of sequence length modes, crossover probability, and sampling probability from the latent space on RAMU's performance. The conclusion highlights the potential of RAMU to outperform traditional UMDA in certain scenarios, suggesting further experiments with larger dimensions and other low-complexity algorithms to confirm these early results. Additionally, the chapter discusses the applicability of random affine maps to other estimation-of-distribution algorithms (EDAs) and the need for modifications for incremental EDAs like PBIL.