 |
|
This multi-objective algorithm is based on Game Theory (J.F.Nash), and in particular on Games between competitive players (or objective functions).
The objectives and the variables of the optimization problem are decomposed among the players that, through the application of a defined "number of iterations" of a deterministic mono-objective optimization algorithm, such as Simplex, try to optimize their own objective function, influencing each other by the sharing of the best variables obtained after each step of the game. In other words, each player is forced to optimize his variables following his objective, but is constrained by the value of the variables that have been found at the end of each step by the other players, and that become fixed during his search.
The game continues for a defined number of steps, ("Maximum Number of Players Steps") or until the "Nash Equilibrium Point" is found. In the latter case, each player have completely optimized his objective, thus the variables found by each player represent the best compromise of all the competitive objectives.
The initial decomposition of variables and objectives is random but, in the following steps, it is changed accordingly to statistical analysis. By t-Student test, in fact, it is possible to determine statistically if a variable is really significant for the objective to which it is assigned and, if the significance percentage is lower than a fixed "Threshold Value", it is assigned to another player in the next step.
The algorithm enlarges to multi-objective problems the particular robustness of Simplex in mono-objective problems, and seems to be particularly efficient in highly constrained and non-linear problems. It can be used to find a good set of not-dominated solutions by a very few number of computations if compared to any other multi-objective algorithm, whose post-application using the results obtained by it as initialization can accelerate remarkably the search of the Pareto front.
A full description of this algorithm, completed by some mathematical tests, is available in the paper A new Algorithm based on Game Theory for Robust and Fast Multi-Objective Optimization.
The user must specify:
Maximum Number of Player Steps: the algorithm will stop after the specified number of player steps if the Nash equilibrium is not reached, default is 10.
Significance Threshold of Variable Acceptance: it is the significance percentage, calculated by t-Student statistical test after each step, under which a variable is lost by a player and given to another. Higher is the parameter, and higher and more efficient will be the exploration of possible not-dominated solutions, but the Nash equilibrium point will be found later. The default value is 0.65
Simplex Maximum number of iterations: it is the maximum number of configurations proposed by Simplex for each player step, in addition to the initial n+1 set, n being the number of variables assigned to the player, that can change in the course of the optimization. Simplex may converge before the specified number of iterations if the "Simplex Termination Accuracy" criterion is satisfied. The default value is 10, while the suggested one is 3sqrt(N), N being the total number of variables.
The following advanced parameters can be also specified:
Simplex Termination Accuracy the player step is concluded before the specified maximum number of Simplex iterations if it cannot find solutions with improvements higher than the convergence value, default 1.0E-3. The value is not as low as in the case of mono-objective Simplex scheduler since it is not required a complete convergence in a player step.
Final Termination Accuracy: the algorithm stops when the Nash equilibrium point is found. We define it when, in more than two consecutive player steps, the mean squared relative difference of the best variables found by the players is kept less than the specified value, default is 0.01.
Note:
Only one entry in the DOE table is accepted as initial configuration for the competitive game.
