Hybrid evolutionary algorithms for the efficient solution of planning problems under uncertainty

An importaIlt aspect of real-world planning problems is the presence of uneertainty in the problem data. The information and deeision strueture of planning under uncertainty enables recourse actions which correet the here-and-now decisions. This situation is refleeted by arecourse model with a finite number of uncertainty scenarios in the form of a two-stage stochastie mixed-integer linear progranl. A stage decomposition based hybrid evolutionary algorithm employs an evolutionary algorithm to determine the here-andnow decisions and a standard mathematical method to optimize the recourse decisions. Empirical investigations exhibit that for problems with a high number of scenarios the hybrid algorithm generates good feasible solutions more quickly than a state-of-the-art exact algorithm. New systematic initialization techniques for the evolutionary algorithms are proposed which exploit thc two-stage stochastic mixed-integer linear program in a preprocessing step. Three initialization approaches are presented which generate solutions of different quality in different preprocessing times. Two approaches are based on solutions of integer relaxations of the corresponding two-stage stochastic mixed-integer linear program. While the first approach uses the integer relaxation of all decisions, the second approach is based on integer relaxation of all recoUl'se decisions only. The third initialization method uses the solution obtained by solving the so-called expected value problem. Numerical experiments show that the new initialization mcthods signifieantly improve the results in terms of faster eonvergence to solutions with better objective values. A seareh space analysis for a case study shows that complex constraints and disjunctive deeisions ean lead to solution spaees of thc evolutionary algorithm whieh consist of many disjoint polyhedral subsets. From the analysis it is concluded that generic evolutionary algorithms are not suitable for search spaces with disjoint subsets of feasible solutions. The evolution of the population sometimes stagnates at solutions with not satisfactory quality. To overcome this problem, a generic search space decomposition based approach is introduced. The first-stage disjoint solution space is decomposed into smaller subproblems and each subproblem is tackled by an independent evolutionary algorithm. The number of parallel evolutions is reduced systematically by abounding approach which guaranties that the global optimal solution remains in the search space. Decision makers frequently try to avoid the occurrence of very unfavorable situations, e. g. heavy losses. Naturally, they aim at a compromise between expected profit and accepted risk. In order to solve risk conscious planning problems nnder uncertainty, a multi-objective evolutionary algorithm is applied to the stage decomposition based hybrid framework. The multi-objective evolutionary algorithm optimizes the expected profit and the risk criterion with respect to the here-and-now decisions. The results show that the application of multi-objective evolutionary algorithms may have a great benefit on the risk conscious planning under nncertainty. The planner gets a set of solution alternatives aIllong which he or she can choose according to his or her risk aversion.