advertisement

Multi-objective Optimization Introduction Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Objectives To discuss and formulate Multi-objective optimization problems To define pareto-optimal or non-inferior solutions 2 Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Introduction In a real world problem single objective and multiple constraints problems are not common The rigidity provided by the General Problem (GP) is, many a times, far away from the practical design problems. In many of the water resources optimization problems maximizing aggregated net benefits is a common objective. At the same time maximizing water quality, regional development, resource utilization, and various social issues are other objectives which are to be maximized. 3 Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Introduction… There may be conflicting objectives along with the main objective like irrigation, hydropower, recreation etc. Multiple objectives or parameters have to be met before any acceptable solution can be obtained. The word “acceptable” implicates that there is normally no single solution to the problems of the above type Methods of multi-criteria or multi-objective analysis are not designed to identify the best solution, but only to provide information on the tradeoffs between given sets of quantitative performance criteria. 4 Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Multi-objective Problem A multi-objective analysis is a vector optimization The objective function is a vector A multi-objective optimization problem with inequality (or equality) constraints may be formulated as: Find which minimizes 5 x1 x 2 . X . . xn (1) f1(X), f2(X), … , fk(X) (2) Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Multi-objective Problem… subject to g j ( X ) 0, j= 1, 2 , … , m (3) where k denotes the number of objective functions to be minimized and m is the number of constraints. The objective functions and constraints need not be linear Linear objective functions and constraints - Multi-objective Linear Programming (MOLP). For the problems of the type mentioned above the very notion of optimization changes Good trade-offs are to be found rather than a single solution. 6 Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Multi-objective Problem… The most commonly adopted notion of the “optimum” proposed by Pareto is A vector of the decision variable X is called Pareto Optimal (efficient) if there does not exist another Y such that for i = 1, 2, … , k with for at least one j. In other words a solution vector X is called optimal if there is no other vector Y that reduces some objective functions without causing simultaneous increase in at least one other objective function. 7 Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Non-inferior Solutions The various objectives of a multi-objective problem are often non-commensurate and may be in conflict. Trade-offs are necessary to reach consensus or compromise solutions If there are two solutions, one solution may achieve higher levels of certain objectives and lower levels of other objectives For example, a multipurpose reservoir serving for irrigation and hydropower generation can have two conflicting objectives: maximize benefits from power generation and maximize irrigation benefits. 8 Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Non-inferior Solutions… There are three objectives i, j, k. k Direction of their increment is also indicated. i j Surface (which is formed based on constraints) is efficient because no objective can be reduced without a simultaneous increase in at least one of the other objectives 9 Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Non-inferior Solutions… Values of objective functions and Infeasible region B decision variables can be visualized by plotting them an enveloping curve A f1(x) Indifference curves E F C Solution X’ is considered non-inferior if and only if there does not exist Feasible region Transformation curve another solution X” such that fi(x”) ≥ fi(x’) where i = 1,2,…, no:of objective D f2(x) functions. The collection of all non-inferior solutions is termed as the set of non-inferior solutions. 10 Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Non-inferior Solutions… Each point in the feasible region gives a Infeasible region B particular set of values for the decision variable, satisfying all the constraints A f1(x) Indifference curves E F C Each point in the transformation curve gives the maximum value of objective Transformation curve Feasible region function given a particular value to the other objective function. D f2(x) Point F should not be considered, since one can get a better value of f1(x) by moving towards B, or a better value of f2(x) by moving towards C. Portion BECD is the efficient one since a further increase in any objective function is not possible without the decrease of the other. 11 Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Non-inferior Solutions… Solutions on AB portion are inferior in Infeasible region B the current case. These solutions are of interest only A f1(x) Indifference curves E F C when some objectives are to be minimized. Feasible region Final goal is to identify the plans which lie in the transformation curve Transformation curve D f2(x) which is the set of efficient trade-offs Curve corresponds to a specific trade-off or marginal rate of substitution between the objectives. The points B, E and C are points with three different marginal rate of substitution between the two objective functions. 12 Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Non-inferior Solutions… Indifference curves are the curves of equal preference of a decision-maker. Optimal plan or the ‘best compromise solution’ is the one which achieves the highest level of preference of the decision-maker, i.e., point E in the figure. Slope of the transformation curve at point E gives the optimal trade-off. In order to identify the non-inferior solutions in the decision space as well the objective space in which the best compromise solution lie, methods used are (i) weighing method (ii) constraint method 13 Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Example Maximize subject to Z1 x 10 x1 3x2 Z 2 x 2 x1 6 x2 g1 x : x1 x 2 2 0 g 2 x : g 3 x : g 4 x : g 5 x : g 6 x : 14 x1 x 2 7 0 x1 5 0 x2 4 0 x1 0 x2 0 Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Example… Solution: Two decision variables and two objective functions Feasible region can be found by plotting all the extreme points and the objective function values at each point Feasible region in the decision space and the set of noninferior solutions 15 Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Example… Feasible region in the objective space and the set of noninferior solutions 16 Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Example… Set of noninferior solutions: Four extreme points, Z(x2), Z(x3), Z(x4) and Z(x5) Among these the identification of any particular noninferior solution as the best compromise solution is not possible without any preference information If any preference is available as represented by an indifference surface (as shown in the figure), then one of the point (here point ] can be identified as the best compromise solution. 17 Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc Thank You Water Resources Planning and Management: M5L1 D Nagesh Kumar, IISc