A Stage Decomposition Based Evolutionary Algorithm

This section presents a new stage decomposition based hybrid evolutionary algorithm for 2S-MILPs that was proposed by Till et al. [7, 18]. 

The evaluation of the implicit second-stage value junction Q, (x) for a given x requires the solution of ST independent MILP subproblems  

When the second stage decisions are real-valued variables, the value function Qu(x) is piecewise-linear and convex in x. However, when some of the second stage variables are integer-valued, the convexity property is lost. The value function Qafx) is in general non-convex and non-differentiable in x. The latter property prohibits the use of gradient-based search methods for solving (MASTER). 

The term evolutionary algorithm (EA) refers to a class of population based metaheuristic (probabilistic) optimization algorithms which imitate the Darwinian evolution ( survival ofthe fittest ). However, the biological terms are used as metaphors rather than in their exact meaning. The population of individuals denotes a set of solution candidates or points of the solution space. Each individual represents a point in the search space which is coded in the individual s representation (genome). The fitness of an individual is usually defined on the basis of the value of the objective function and determines its chances to stay in the population and to be used to generate new solution points. 

The hybrid evolutionary algorithm for 2S-MILPs is realized by using an evolution strategy (ES) to solve the master problem of the intensive 2S-MILP. Each individual of the ES represents a first-stage candidate solution x. The object parameters are encoded by a mixed-integer vector. The fitness of an individual is evaluated by the objective function of the master problem (MASTER),/ (x). 

---