Session details: Track 5: estimation of distribution algorithms

Benchmarking parameter-free AMaLGaM on functions with and without noise.

We describe a parameter-free estimation-of-distribution algorithm (EDA) called the adapted maximum-likelihood Gaussian model iterated density-estimation evolutionary algorithm (AMaLGaM-ID[Formula: see text]A, or AMaLGaM for short) for numerical optimization. AMaLGaM is benchmarked within the 2009 black box optimization benchmarking (BBOB) framework and compared to a variant with incremental model building (iAMaLGaM). We study the implications of factorizing the covariance matrix in the Gaussian distribution, to use only a few or no covariances. Further, AMaLGaM and iAMaLGaM are also evaluated on the noisy BBOB problems and we assess how well multiple evaluations per solution can average ou…

Decomposition of Dynamic Single-Product and Multi-product Lotsizing Problems and Scalability of EDAs

In existing theoretical and experimental work, Estimation of Distribution Algorithms (EDAs) are primarily applied to decomposable test problems. State-of-the-art EDAs like the Hierarchical Bayesian Optimization Algorithm (hBOA), the Learning Factorized Distribution Algorithm (LFDA) or Estimation of Bayesian Networks Algorithm (EBNA) solve these problems in polynomial time. Regarding this success, it is tempting to apply EDAs to real-world problems. But up to now, it has rarely been analyzed which real-world problems are decomposable. The main contribution of this chapter is twofold: (1) It shows that uncapacitated single-product and multi-product lotsizing problems are decomposable. (2) A s…

AMaLGaM IDEAs in noiseless black-box optimization benchmarking

This paper describes the application of a Gaussian Estimation-of-Distribution (EDA) for real-valued optimization to the noiseless part of a benchmark introduced in 2009 called BBOB (Black-Box Optimization Benchmarking). Specifically, the EDA considered here is the recently introduced parameter-free version of the Adapted Maximum-Likelihood Gaussian Model Iterated Density-Estimation Evolutionary Algorithm (AMaLGaM-IDEA). Also the version with incremental model building (iAMaLGaM-IDEA) is considered.

Publication Network Analysis of an Academic Family in Information Systems

The study of scientific collaboration through network analysis can give interesting conclusions about the publication habits of a scientific community. Co-authorship networks represent scientific collaboration as a graph: nodes correspond to authors, edges between nodes mark joint publications (Newman 2001a,b). Scientific publishing is decentralized. Choices of co-authors and research topics are seldomly globally coordinated. Still, the structure of co-authorship networks is far from random. Co-authorship networks are governed by principles that are similar in other complex networks such as social networks (Wasserman and Faust 1994), networks of citations between scientific papers (Egghe an…

Scalability of using Restricted Boltzmann Machines for Combinatorial Optimization

Abstract Estimation of Distribution Algorithms (EDAs) require flexible probability models that can be efficiently learned and sampled. Restricted Boltzmann Machines (RBMs) are generative neural networks with these desired properties. We integrate an RBM into an EDA and evaluate the performance of this system in solving combinatorial optimization problems with a single objective. We assess how the number of fitness evaluations and the CPU time scale with problem size and complexity. The results are compared to the Bayesian Optimization Algorithm (BOA), a state-of-the-art multivariate EDA, and the Dependency Tree Algorithm (DTA), which uses a simpler probability model requiring less computati…

An implicitly parallel EDA based on restricted boltzmann machines

We present a parallel version of RBM-EDA. RBM-EDA is an Estimation of Distribution Algorithm (EDA) that models dependencies between decision variables using a Restricted Boltzmann Machine (RBM). In contrast to other EDAs, RBM-EDA mainly uses matrix-matrix multiplications for model estimation and sampling. Hence, for implementation, standard libraries for linear algebra can be used. This allows an easy parallelization and leads to a high utilization of parallel architectures. The probabilistic model of the parallel version and the version on a single core are identical. We explore the speedups gained from running RBM-EDA on a Graphics Processing Unit. For problems of bounded difficulty like …

A problem-adjusted genetic algorithm for flexibility design

Many present markets for goods and services have highly volatile demand due to short life cycles and strong competition in saturated environments. Determination of capacity levels is difficult because capacities often need to be set long before demand realizes. In order to avoid capacity-demand mismatches, operations managers employ mix-flexible resources which allow them to shift excess demands to unused capacities. The Flexibility Design Problem (FDP) models the decision on the optimal configuration of a flexible (manufacturing) network. FDP is a difficult stochastic optimization problem, for which traditional exact approaches are not able to solve but the smallest instances in reasonable…