PolyEDA: Combining Estimation of DistributionAlgorithms and Linear Inequality Constraints

Estimation of distribution algorithms (EDAs) are population-basedheuristic search methods that use probabilistic models and which havebeen successfully applied to continuous optimization problems. When appliedto constrained optimization problems, most EDAs (as well as geneticalgorithms) handle constraints by penalizing invalid solutions. This paperpresents PolyEDA, a new EDA approach that is able to directly considerlinear inequality constraints by using Gibbs sampling. Gibbs samplingallows us to sample new individuals inside the boundaries of the polyhedralsearch space described using a set of linear inequality constraints byiteratively constructing a density approximation that lies entirely insidethe polyhedron.[...] []