A hybrid multiple populations evolutionary algorithm for two-stage stochastic mixed-integer disjunctive programs

摘要

This article describes a hybrid multiple populations based evolutionary approach for disjunctive mathematical programs with uncertainties in the problem data. The problems are formulated as two-stage linear disjunctive programming problems which are solved by a stage decomposition based hybrid algorithm using multiple evolutionary algorithms to handle the disjunctive sets of the here-and-now (first stage) decisions and mathematical programming to handle the recourse (second stage) decisions. By an appropriate representation of the first-stage disjunctive solution space, the overall problem is decomposed into smaller subproblems without disjunctions. The resulting decomposed first-stage subproblems are solved independently by evolutionary algorithms, leading to parallel evolutions based on multiple populations. During the progress of the optimization, the number of subproblems is systematically reduced by comparing the current best global solution (upper bound) to lower bounds for the subproblems. This approach guaranties that the global optimal solution remains in the union of solution spaces of the remaining subproblems. A comparison of a classical evolutionary algorithm and the new multiple populations evolutionary algorithm for a real world batch scheduling problem shows that the new approach leads to a significantly improved coverage of the set of feasible solutions such that high quality feasible solutions can be generated faster.