Multi-objective Optimization - UCCS

1 IntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAMulti-objective OptimizationJugal K. KalitaUniversity of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GASingle vs. Multi-objective OptimizationSingle vs. Multi-objective OptimizationISingle Objective Optimization :When an optimizationproblem involves only one objective function, the task offinding the optimal solution is called :Find a CAR for me with Minimum Optimization :When an optimizationproblem involves more than one objective function, thetask of finding one or more optimal solutions is known asmulti-objective :Find a CAR for me with minimum cost andmaximum of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAMulti-objective Optimization : IntroductionMulti-objective ProblemsIProblems with more than one objective function, typicallyconflicting objectivesICars Example: Maximize luxury vs.

2 Minimize priceIAnother example: Maximiizef1(x) =x2andf2(x) = (x 2)2whenxis in the range[ 103,103]University of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAMulti-objective Optimization : IntroductionMulti-objective ProblemsIA more complex example: Maximize the following twoobjective functions when the variables are within the range[ , ]:f1(x) =[1+ (A1 B1)2+ (A1 B2)2]f2(x) =[(x1+3)2+ (x2+1)2]A1= (1) 2cos(1) +sin(2) (2)A2= (1) cos(1) +2sin(2) (2)B1= (x1) 2cos(x1) +sin(x2) (x2)B2= (x1) cos(x1) +2sin(x2) (x2)University of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAMulti-objective Optimization : IntroductionGeneral Formulation of a Multi-objective ProblemIMinimiizeF(X)whereF(X) ={fi: i=1,M}X={Xj: j=1,N}subject toC(X) 0 whereC={Ck: k=1,P}H(X) =0 whereH={Hk: k=1,Q}University of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAMulti-objective Optimization .

3 IntroductionMulti-objective OptimizationIMulti-objective Optimization (MOO) is the Optimization ofconflicting some problems, it is possible to find a way of combiningthe objectives into a single , in some other problems, it is not possible to do the differences are qualitative and the relativeimportance of these objectives cannot be , there is no unique solutions, rather there is atrade-off among optimal of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAMulti-objective Optimization : IntroductionConceptual ExampleISuppose you need to fly on a long trip: Should you choosethe cheapest ticket (more connections) or shortest flyingtime (more expensive)?IIt is impossible to put a value on time, so these twoobjectives cannot be , the relative importance will may be a business emergency you need to go , maybe you are on a very tight of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAPareto-optimal SolutionsPareto-Optimal SolutionsIA MOO problem with constraints will have many solutionsin the feasible though we may not be able to assign numericalrelative importance to the multiple objectives , we can stillclassify some possible solutions as better than of Colorado, Colorado Springs.

4 USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAPareto-optimal SolutionsExample of Pareto-Optimal SolutionsISuppose in our airplane-trip example from earlier, we findthe following Time (hrs)Price ($) of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAPareto-optimal SolutionsComparison of SolutionsIIf we compare tickets A and B, we cannot say that either issuperior without knowing the relative importance of TravelTime vs. , comparing tickets B and C shows that C is betterthan B inbothobjectives, so we can say that C dominates , as long as C is a feasible option, there is no reason wewould choose of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAPareto-optimal SolutionsComparison of SolutionsIIf we finish the comparisons, we also see that D isdominated by rest of the options (A, C, and E) have a trade-offassociated with Time vs.

5 Price, so none is clearly superiorto the call{A,C,E}thenon-dominatedset of solutionsbecause none of the solutions are of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAPareto-optimal SolutionsGraph of SolutionsIUsually, solutions of this type form a typical shape, shownin the graph of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAPareto-optimal SolutionsTypes of SolutionsISolutions that lie along the line are non-dominatedsolutions while those that lie inside the line are dominatedbecause there is always another solution on the line thathas at least one objective that is of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAPareto-optimal SolutionsPareto-optimal SolutionsIThe line is called the Pareto front and solutions on it arecalled Pareto-optimal solutions are , it is important in MOO to find the solutions as closeas possible to the Pareto front and as far along it of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAPareto-optimal SolutionsFinding the Pareto FrontIFor the following feasible region with objectivesf1andf2where bothf1andf2are of Colorado, Colorado Springs.

6 USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAPareto-optimal SolutionsGraphical ExampleIOne way to imagine finding points on the Pareto front is byusing a combination of numerical weights for the , we have a weight ofw1onf1and equation of a slanted line isw1f1+w2f2for variousvalues ofw1andw2such thatw1+w2= of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAPareto-optimal SolutionsFinding the Pareto FrontIIf this is done for a 90 span of lines, all the points on thePareto front will be of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAPareto-optimal SolutionsRealistic ProceduresIThere are different methods used in practice, but one is touse a genetic algorithm to enumerate points along thePareto front over several iterations, then use some methodto rank the quality of the trade-offs based on the particularapplication being of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAPareto-optimal SolutionsPracticality of this ProcedureIActually, this is not the procedure that is used in practice.

7 But it is a good illustration of the procedure would require finding all possible points inthe feasible region and then using many combinations more than two objectives , the complexities and thenumber of combinations make this of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAPareto-optimal SolutionsFinding a Point on the Pareto FrontIIt should be remembered that each point on the Paretofront is found by solving an Optimization the problem is nonlinear or very complex, the simple stepof getting just one solution may not be is the case whether we a genetic algorithm or someother method. We have to find points on the Pareto of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAMutli-objective GA ReferencesDevelopment of Multiobjective GAsIThe 1st generation:Vector Evaluation approach VectorEvaluated Genetic Algorithm (VEGA)IJ.

8 D. Schaffer: Multiple objective Optimization with vectorevaluated genetic algorithms ,Proc. of 1st Inter. Conf. onGAs and Their Applic., 2nd generation: Pareto ranking + DiversityIMultiobjective Genetic Algorithm (MOGA)Fonseca, C. M. and Fleming, P. J: Genetic algorithms formultiobjective Optimization : formulation, discussion andgeneralization , Proc. of the 5th Inter. Conf. on GAs, Sorting Genetic Algorithm(NSGA)Srinivas, N. and Deb, K.: Multiobjective functionoptimization using nondominated sorting geneticalgorithms , Evolutionary Computation, of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAMutli-objective GA ReferencesDevelopment of Multiobjective GAsIThe 3rd generation: Weighted Sum + Elitist PreserveIRandom-weight Approach (RWA): Ishibuchi, H and : A multiobjective genetic local search algorithmand its application to flowshop scheduling , IEEE Trans.

9 OnSys., Man & Cyber., Pareto Evolutionary Algorithm (SPEA): E. Zitzlerand L. Thiele: Multiobjective Evolutionary Algorithms: AComparative Case Study and the Strength ParetoApproach , IEEE Trans. on Evolutionary Comput., Weight Approach (AWA): Gen M,. and Cheng, R. :Genetic Algorithms and Engineering Optimization , JohnWiley & Sons, New York, Sorting Genetic Algorithm II (NSGAII): Deb,K., A. Pratap, S. Agarwal & T. Meyarivan: A Fast and ElitistMultiobjective Genetic Algorithm: NSGA-II IEEE Trans. onEvolutionary Comput., 2002 University of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAVEGAV ector Evaluated Genetic Algorithms (Schaffer, 1985)IVEGA is the first notable work to solve MOO problems inwhich it uses a vector fitness measure to create the selection step in each generation becomes a time through the loop the appropriate fraction of thenext generation, or subpopulation, is selected on the basisof each entire population is shuffled thoroughly to applycrossover and mutation operators.

10 This is performed toachieve the mating of individuals of of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAVEGAVEGA 1985 IDivide population into M equal blocks for M objectives atevery each block with one objective population participates in crossover proportionate selection reduce the positional bias in the population, shuffle thepopulation before of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAVEGAVEGA 1985 University of Colorado, Colorado Springs, USAM ulti-objective OptimizationIntroductionPareto-Optimal SolutionsEvolution of Multi-objective GAApproaches to Multi-objective GAPareto RankingPareto Ranking ApproachIPareto ranking approach consists of assigning fitnessranks to chromosomes based on the level ranked chromosomes have better chance Pareto ranking-based fitness assignment method wasfirst suggested byIGoldberg, D.