Evolutionary solver

An evolutionary algorithm is included in the current release of Frontline Systems Premium Excel Solver (for current information, see www.frontsys.com). It is invoked by choosing Standard Evolutionary from the Solver dropdown list in the Solver Parameters Dialog Box. The other nonlinear solver is Standard GRG Nonlinear, which is the GRG2 solver described in Section 8.7. As discussed there, GRG2 is a gradient-based local solver, which will find the nearest local solution to its starting point. The evolutionary solver is much less likely to stop at a local minimum, as we illustrate shortly. 

Options dialog for the evolutionary solver. Permission by Microsoft. 

This problem is very small, however, with only two decision variables. As the number of decision variables increases, the number of iterations required by evolutionary solvers to achieve high accuracy increases rapidly. To illustrate this, consider the linear project selection problem shown in Table 10.9. The optimal solution is also shown there, found by the LP solver. This problem involves determining the optimal level of investment for each of eight projects, labeled A through H, for which fractional levels are allowed. Each project has an associated net present value (NPV) of its projected net profits over the next 5 years and a different cost in each of the 5 years, both of which scale proportionately to the fractional level of investment. Total costs in each year are limited by forecasted budgets (funds available in... 

Final objective values obtained by evolutionary solver... 

Table 10.10 shows the performance of the evolutionary solver on this problem in eight runs, starting from an initial point of zero. The first seven runs used the iteration limits shown, but the eighth stopped when the default time limit of 100 seconds was reached. For the same number of iterations, different final objective function values are obtained in each run because of the random mechanisms used in the mutation and crossover operations and the randomly chosen initial population. The best value of 811.21 is not obtained in the run that uses the most iterations or computing time, but in the run that was stopped after 10,000 iterations. This final value differs from the true optimal value of 839.11 by 3.32%, a significant difference, and the final values of the decision variables are quite different from the optimal values shown in Table 10.9. 

In this section, the hybrid evolutionary algorithm described above is applied to a real-world scheduling problem under uncertainty. The performance of this algorithm is compared to that of the state-of-the-art MILP solver CPLEX and to that of... 

By a comparison of the new evolutionary algorithm s performance with state-of-the-art solvers for a real-world scheduling problem it was found that the new algorithm shows a competitive performance. In contrast to the other algorithms the evolutionary algorithm was able to provide relatively good solutions in short computation times. 

Using the Evolutionary Algorithm in the Premium Excel Solver... 

B, and E are also shown. Although B is reasonably near its optimal value, A and E are far from theirs. This performance is comparable to that of the evolutionary algorithm in the Extended Excel Solver, shown in Table 10.10. If the decision variables in this problem must be binary, however, then OPTQUEST finds the optimal solution, whose objective value is 767, in only 116 iterations. The evolutionary algorithm found this same optimal solution in one of two runs using 1000 iterations. 

Select th< GRG Nonlinear engine for Solver Problenis that ere smooth norrlinear Select the IP SimpieM engine for linear Solver Problems, and lelect the Evolutionary engine for SoNer problems that are non smooUL. 

Select the GRG Nonbiear engine for Saker Problems that are smooth nonhtear. Select the LP Simplex en ie for kiear Solver Problems, and select the Evolutionary en te for Salver problems that are non Mthv... 

---