Report

A two-stage approach for multiobjective decision making with applications to system reliability optimization Zhaojun Li, Haitao Liao, David W. Coit Reliability Engineering and System Safety Hui-Yu, Chung Advisor: Frank,Yeong-Sung Lin Agenda Introduction Multi-objective optimization problem ◦ Mathematical formulation ◦ Non-dominated sorting genetic algorithm Statistical classification methods ◦ Unsupervised and supervised data classification ◦ Self-organizing map Reduction of Pareto optimal solutions ◦ Data envelopment analysis Application to multi-objective RAP Conclusions Introduction Though there are multiple design objectives, a decision-maker must ultimately select one or a small set of solutions to consider. In this approach, prospective solutions are clustered, pruned for the decision-maker to consider only a small subset of the promising solutions. Introduction Traditionally, the redundancy allocation problem (RAP) is to maximize the system reliability under various constraints ◦ Single-objective integer programming problem, which is a NP hard Mathematical programming approaches for RAP usually restrict the solution space by considering only one component choice for each subsystem ◦ Without allowing the mixture of those functionally equivalent components Introduction Component mixing in system redundancy increases the problem solution space ◦ May result in higher system reliability values ◦ Need to employ heuristic algorithms such as GA or Tabu search Mixing functionally equivalent components may potentially reduce the variance of system reliability estimate and minimizes the likelihood of common cause failures Introduction To address the multi-objective optimization problem, a new two-stage approach is proposed in this paper. First Stage: ◦ A multiple objective evolutionary algorithm (MOEA) is applied to identify a representative Pareto optimal solution set Second Stage: ◦ Classify the Pareto optimal solutions by selforganizing map (SOM) method ◦ Eliminate the non-efficient solutions using data envelopment analysis (DEA) method Two-stage method for solving multiobjective RAP Agenda Introduction Multi-objective optimization problem ◦ Mathematical formulation ◦ Non-dominated sorting genetic algorithm Statistical classification methods ◦ Unsupervised and supervised data classification ◦ Self-organizing map Reduction of Pareto optimal solutions ◦ Data envelopment analysis Application to multi-objective RAP Conclusions Multi-objective optimization problem Mathematical formulations: Let x be a vector containing p decision variables ◦ The optimization problem with n objective functions is expressed as: What is “Pareto Optimal” Solutions? In multi-objective optimization problems, we cannot expect that every objective being satisfied in the result solutions ◦ The Pareto optimal Solution If we want to improve one of the subobjective, we have to worse some other sub-objectives. Pareto optimal solutions are often continuous, and we can find infinite number of that kind of solutions. What is “Pareto Optimal” Solutions? Mathematical formulations Some approaches to solve the problem: ◦ Transform the original problem into a singleobjective problem ◦ Using Pareto optimal concept based on nondominance Pareto dominance & non-dominance ◦ Determined by multiple pair-wise vector comparison Mathematical formulations x is non-dominated in a p-dimensional set X if there is no other y x in X such that f (y ) f ( x ) . If N is a set containing all the non-dominated solutions in X, then the set N is called the Pareto optimal set. (Pareto frontier in multiobjective optimization problem) The number of solutions in the Pareto optimal solution set is large as the number of conflicting objectives increases Non-dominated sorting genetic algorithm To identify the Pareto optimum solution set, some kinds of MOEA Genetic Algorithms can be applied. ◦ In this paper, non-dominated sorting genetic algorithms (NSGA) or NSGA-II is used NSGA v.s. Simple GA: ◦ The same crossover & mutation as GA ◦ Different selection operator ◦ Ranking method NSGA-II Algorithm Agenda Introduction Multi-objective optimization problem ◦ Mathematical formulation ◦ Non-dominated sorting genetic algorithm Statistical classification methods ◦ Unsupervised and supervised data classification ◦ Self-organizing map Reduction of Pareto optimal solutions ◦ Data envelopment analysis Application to multi-objective RAP Conclusions Statistical classification methods Unsupervised data classification ◦ e.g. k-means and Self-organizing map (SOM) ◦ No or few prior information is available ◦ Labels are not specified beforehand Supervised data classification ◦ e.g. Artificial neural network and SVM ◦ Relationship between the data and its corresponding cluster is known ◦ The label for each input vector needs to be specified first (by training process) Self-organizing map An unsupervised classification method Generates a set of representations for multi-dimensional input vector while preserving the topological properties of similarity Dimensional reduction process Self-organizing map (Training Process) Best Matching Unit (BMU): ◦ The Euclidean distance to all weight vectors is computed ◦ The neuron with the weight vector most similar to the input Adjusted weights ◦ The weight of the input vectors is adjusted according to the distances of the BMUs ◦ The adjustment decreases with time Self-organizing map (Training Process) The weight w(t) is updated iteratively: w(t 1) w(t ) (v , t ) (t )[I(t ) w(t )] ◦ w(t 1) : the weight vector at step t+1 ◦ I(t ) : the input vector ◦ (t ) : the learning coefficient (monotonically decreasing with time) ◦ (v , t ) : the neighborhood function Gaussian neighborhood function is often used (v ,t ) exp(v 2 / 2 ) Self-organizing map Eventually, output nodes are associated with groups or patterns corresponding to the input vectors The input vector is mapped to a specific location on the lattice based on its similarity to the weight vector for a specific neuron Self-organizing map SOM measures the similarity by the Euclidian distance as well as the angle between the input vectors by updating the weight vectors iteratively Agenda Introduction Multi-objective optimization problem ◦ Mathematical formulation ◦ Non-dominated sorting genetic algorithm Statistical classification methods ◦ Unsupervised and supervised data classification ◦ Self-organizing map Reduction of Pareto optimal solutions ◦ Data envelopment analysis Application to multi-objective RAP Conclusions Reduction of Pareto optimal solutions Selecting representative solutions from each cluster can be regarded as a multiobjective solution optimization problem (MOSO) Data Envelopment Analysis ◦ A special MOSO method ◦ Is able to eliminate non-efficient Pareto optimal solution from each cluster Data envelopment analysis A linear programming-based technique for measuring relative performance of decision making units (DMUs) ◦ A unit whose performance can be measured in terms of input-output analysis For MOSO, each alternative solution is treated as a DMU in the DEA method ◦ The DMUs are assumed to be homogeneously comparable (to make the result efficiency meaningful) Data envelopment analysis Relative Efficiency (RE) weighted sumof outputs RE weighted sumof inputs Considering a problem involving l DMUs, each has m inputs and n outputs, the RE of the kth DMU is: weights Data envelopment analysis The RE of a specific DMU k0 can be obtained by: is a small positive quantity Data envelopment analysis Normalized programming problem: Data envelopment analysis When applying DEA, all DMUs are attempting to select their most favorable weights There may be more than one efficient unit whose relative efficiency has the value of one ◦ Efficient frontier Data envelopment analysis In the MOSO formulation for the RAP, all the Pareto Optimal solutions in each cluster can be considered as DMUs A higher relative efficiency value indicates a higher output value (ex. system reliability) Data envelopment analysis In this paper, method are presented when the decision-makers have not expressed any objective function preferences Ordinal ranking of objective function ◦ Used to prune the Pareto optimal set ◦ Weight sets adhering to the stated preferences are randomly and repeatedly elected to identify the best solution Agenda Introduction Multi-objective optimization problem ◦ Mathematical formulation ◦ Non-dominated sorting genetic algorithm Statistical classification methods ◦ Unsupervised and supervised data classification ◦ Self-organizing map Reduction of Pareto optimal solutions ◦ Data envelopment analysis Application to multi-objective RAP Conclusions Application to multi-objective RAP In the Pareto optimal solution identification stage, MOGA is initially applied ◦ 75 Pareto optimal solutions by Taboada and Coit using NSGA-II method Each Pareto optimal solution has three dimensions (input vectors) ◦ System reliability, total cost, system weight A 10 10 output lattice are employed to get the SOM clustering results Application to multi-objective RAP Consider a system consisting of ◦ 3 subsystems (with 5 options) ◦ 4 or 5 types of components in each subsystem ◦ Maximum # of components is 8 per subsystem Application to multi-objective RAP Application to multi-objective RAP Each cluster has its own characteristics The solutions in a specific cluster are topologically similar to each other Application to multi-objective RAP Application to multi-objective RAP Results: ◦ 3 solution achieve the RE to 90% ◦ 2 of the above solutions’ RE is equal to 1 Agenda Introduction Multi-objective optimization problem ◦ Mathematical formulation ◦ Non-dominated sorting genetic algorithm Statistical classification methods ◦ Unsupervised and supervised data classification ◦ Self-organizing map Reduction of Pareto optimal solutions ◦ Data envelopment analysis Application to multi-objective RAP Conclusions Conclusions This paper introduces a two-stage method to get Pareto optimal solutions and classify them to reduce the solution set. In the Solutions pruning stage, SOM is first applied in classification ◦ Basic trade-offs information about the solution set can be observed DEA method is further used to reduce the original solutions ◦ Which makes multi-objective decision making for RAP more easier THANKS FOR YOUR ATTENTION~!!!