 |
|
This multi-objective scheduler is based on the Normal-Boundary Intersection (NBI) method, developed by I. Das and J. E. Dennis (1998).
The NBI method applies to any generic smooth multi-objective problem, and it reduces the problem to many single-objective constrained subproblems (the so called "NBI subproblems"). So the NBI method has to be coupled with a single-objective solver in order to get the solutions of these subproblems. This NBI-NLPQLP scheduler uses the NLPQLP algorithm as the single-objective solver.
Note:
The problem to be solved is at least subject to the restrictions imposed by the single-objective solver coupled with the NBI method, in this case the NLPQLP algorithm. So it has to be at least smooth and well scaled.
The NBI subproblems are characterized by the introduction of one new variable and N constraints, with respect to the original multi-objective problem, where N is the number of objectives.
After the evaluation of the designs provided with the DOE table, the scheduler starts solving each single-objective problem separately, starting for each objective subproblem from the most favorable DOE. This preliminary step is requested by the NBI method, in order to set properly the internal parameters of the scheduler and permitting the subsequent search for the Pareto set in its wholeness. These subproblems of optimizing the individual objectives can be regarded as particular NBI subproblems. Afterwards all the NBI subproblems are solved; the knowledge about the solution of the previous subproblem is used as the starting point for the next subproblem, in order to improve the algorithm convergence speed.
A better description of the algorithm is available in the paper NBI-NLPQLP Scheduler.
A comparison between this algorithm and MOGA-II upon some common test functions is available in the paper Bench-marking NBI-NLPQLP.
A detailed description of the hole test problem cited in the above-mentioned papers is available in the report Hole functions problem.
The NBI-NLPQLP scheduler, being a method coupled with the NLPQLP single-objective solver, comes with all the NLPQLP parameters, plus its own ones.
The user must specify:
Maximum Number of Iterations per Subproblem: the algorithm will always stop when the maximum number of designs have been evaluated. This is done independently from any other convergence limits. This applies separately for each single subproblem.
Approximate Derivatives With: Central or Forward differences. Central Differences are more accurate but more expensive, a gradient computation requires in fact NV computations in case of Forward differences and 2*NV computations in case of Central differences (where NV is the number of variables).
Number of Pareto Points (Subproblems): this parameter determines the number of NBI subproblems to be solved, including the starting search for the global minima of each single objective. Thus the number of subproblems has to be at least equal to the number of objectives. Larger values imply a better resolution of the Pareto frontier, at the cost of demand for more and more design evaluations. (This one is the only parameter proper to the NBI-NLPQLP scheduler, with respect to the NLPQLP parameters.)
Final Termination Accuracy: the algorithm stops when it cannot find solution with improvements higher that the convergence value. The default is set to 1.0E-5.
Finite Difference Relative Perturbation: the value is the fraction of the variable value that is used to perturb the starting point in order to compute the derivatives. The default is set to 1.0E-7. For local refinements low values should be used.
Finite Difference Minimum Perturbation Policy: it is possible to choose between two different policies: Constant or Range Percentage.
Constant Minimum Perturbation: this field is active only when the Finite Difference Minimum Perturbation Policyis Constant. The value is the minimal value that is used to perturb the starting point. The perturbation step is then given by the maximum value between the Finite Difference Relative Perturbation and this Constant Minimum Perturbation.
Range Percentage Minimum Perturbation: this field is active only when the Finite Difference Minimum Perturbation Policyis Range Percentage. This percentage gives the minimal value that is used to perturb the starting point. For each variable this value is equal to:
Minimum_Perturbation = (Upper_bound - Lower_bound) * (Range_Percentage_Minimum_Perturbation)The perturbation step is then given by the maximum value between the Finite Difference Relative Perturbation and the Minimum_Perturbation.
Note:
The number of concurrent designs evaluation can be set in the Run Project Dialog. The entries of the DOE table are used as a sequence of initial points for different local optimization problems.
[1] Das, I., and Dennis, J. E. 1998, Normal-Boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems, SIAM Journal on Optimization, 8(3), 631
