Multiobjective simulation optimization using enhanced evolutionar

University of Central Florida STARS Electronic Theses and Dissertations, 2004-2019 2006 Multiobjective Simulation Optimization Using Enhanced Evolutionary Algorithm Approaches Hamidreza Eskandari University of Central Florida Part of the Engineering Commons Find similar works at: https://stars.edu/etd University of Central Florida Libraries http://library.edu This Doctoral Dissertation (Open Access) is brought to you for free and open access by STARS. It has been accepted for inclusion in Electronic Theses and Dissertations, 2004-2019 by an authorized administrator of STARS. For more information, please contact STARS@ucf. STARS Citation Eskandari, Hamidreza, "Multiobjective Simulation Optimization Using Enhanced Evolutionary Algorithm Approaches" (2006).

Electronic Theses and Dissertations, 2004-2019.edu/etd/968 MULTIOBJECTIVE SIMULATION OPTIMIZATION USING ENHANCED EVOLUTIONARY ALGORITHM APPROACHES by HAMIDREZA ESKANDARI, B., Electrical Engineering, University of Tehran, Tehran, Iran, 1998 M., Socio-Economic Systems Engineering, Iran University of Science and Technology, Tehran, Iran, 2001 A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Industrial Engineering and Management Systems in the College of Engineering and Computer Science at the University of Central Florida Orlando, Florida Summer Term 2006 Major Professor: Christopher D. Geiger © 2006 Hamidreza Eskandari ABSTRACT In today’s competitive business environment, a firm’s ability to make the correct, critical decisions can be translated into a great competitive advantage. Most of these critical real-world decisions involve the optimization not only of multiple objectives simultaneously, but also conflicting objectives, where improving one objective may degrade the performance of one or more of the other objectives. Traditional approaches for solving multiobjective optimization problems typically try to scalarize the multiple objectives into a single objective.

This transforms the original multiple optimization problem formulation into a single objective optimization problem with a single solution. However, the drawbacks to these traditional approaches have motivated researchers and practitioners to seek alternative techniques that yield a set of Pareto optimal solutions rather than only a single solution. The problem becomes much more complicated in stochastic environments when the objectives take on uncertain (or “noisy”) values due to random influences within the system being optimized, which is the case in real-world environments. Moreover, in stochastic environments, a solution approach should be sufficiently robust and/or capable of handling the uncertainty of the objective values.

This makes the development of effective solution techniques that generate Pareto optimal solutions within these problem environments even more challenging than in their deterministic counterparts. Furthermore, many real-world problems involve complicated, “black-box” objective functions making a large number of solution evaluations computationally- and/or financially-prohibitive. This is often the case when complex computer simulation models are used to repeatedly evaluate possible solutions in search of the best solution (or set of i solutions). Therefore, multiobjective optimization approaches capable of rapidly finding a diverse set of Pareto optimal solutions would be greatly beneficial.

This research proposes two new multiobjective evolutionary algorithms (MOEAs), called fast Pareto genetic algorithm (FPGA) and stochastic Pareto genetic algorithm (SPGA), for optimization problems with multiple deterministic objectives and stochastic objectives, respectively. New search operators are introduced and employed to enhance the algorithms’ performance in terms of converging fast to the true Pareto optimal frontier while maintaining a diverse set of nondominated solutions along the Pareto optimal front. New concepts of solution dominance are defined for better discrimination among competing solutions in stochastic environments. SPGA uses a solution ranking strategy based on these new concepts.

Computational results for a suite of published test problems indicate that both FPGA and SPGA are promising approaches. The results show that both FPGA and SPGA outperform the improved nondominated sorting genetic algorithm (NSGA-II), widely-considered benchmark in the MOEA research community, in terms of fast convergence to the true Pareto optimal frontier and diversity among the solutions along the front. The results also show that FPGA and SPGA require far fewer solution evaluations than NSGA-II, which is crucial in computationally-expensive simulation modeling applications. ii To my wife and family, for their love and support.

iii ACKNOWLEDGMENTS I would like to thank all of my dissertation committee members, Dr. Mansooreh Mollaghasemi, Dr. Sepúlveda, Dr. Wu and Dr.

Ferenc Szidarovszky for their useful comments, suggestions, and help in producing a high quality research document. I would like to thank Dr. Mansooreh Mollaghasemi and Dr. Rabelo for their financial support during the early stages of this research investigation.

To my research advisor, Dr. Geiger, without your guidance, work ethic, motivation, and support I would not be at this juncture in life. Your support in submitting papers and attending many conferences has helped me gain the insight and knowledge necessary to complete this research. I value your opinions and thank you for expanding my horizons.

I would also like to thank God and my family, especially my parents. Without their great support and example I could not have made it to where I am today. Finally and most importantly I would like to thank my wife. Without her support, understanding, and motivation to never give up I could not have completed the PhD.

Over the last three years you raised our daughter, kept our family together, and motivated me to complete this challenge while I remained locked in a room somewhere studying or typing on the computer. To my wife and daughter who helped me realize what is truly important in life. iv TABLE OF CONTENTS LIST OF FIGURES. viii LIST OF TABLES.

Solution Dominance in Multiobjective (Deterministic) Problem Environments 3 1. Systems Simulation Modeling. Optimization via Simulation. Simulation Optimization of Multiple Stochastic Objectives.

Objectives of This Research. Organization of this Dissertation. 8 CHAPTER 2 : OVERVIEW OF SIMULATION OPTIMIZATION THEORY AND APPROACHES. Classical Approaches for Simulation Optimization.

Sample Path Optimization. Response Surface Methodology. Random Search Method. Statistical Selection Procedures.

Metaheuristic Search Approaches for Simulation Optimization. Evolutionary Algorithms for Multiobjective Optimization. Vector Evaluated Genetic Algorithm. Multiple Objective Genetic Algorithm.

Nondominated Sorting Genetic Algorithm. Niched Pareto Genetic Algorithm. Multiobjective Evolutionary Algorithms under Uncertainty. Multiobjective Simulation Optimization.

44 v CHAPTER 3 : PROPOSED METHODOLOGY. A Proposed Methodology – Fast Pareto Genetic Algorithm (FPGA). FPGA Initialization and Solution Evaluation. Solution Ranking and Fitness Assignment.

Distance Crowding Operation. Elitism and Expansion Operations. Crossover and Mutation Operations. Screening Nondominated Solutions Set by Clustering.

Computational Complexity of FPGA. 60 CHAPTER 4 : FPGA COMPUTATIONAL RESULTS. Benchmark Test Problems. MOEA Parameter Settings.

Distance from the Pareto Optimal Front. Diversity of Nondominated Solutions. Delineation of Pareto Optimal Front. FPGA Computational Results.

Termination of the Search. Discussion of the Results. A Discussion on FPGA Population Regulation. 82 CHAPTER 5 : PROPOSED METHODOLOGY FOR STOCHASTIC ENVIRONMENTS.

Redefinition of Solution Dominance in Multiobjective Stochastic Environments 85 5. Stochastic Solution Ranking Strategy and Fitness Assignment. SPGA Computational Study. Discussion of Computational Results.

KUR Test Problem. ZDT1 Test Problem. ZDT4 Test Problem. ZDT6 Test Problem.

104 CHAPTER 6 : SUMMARY AND FUTURE RESEARCH DIRECTIONS. Summary and Conclusions. Future Research Directions. Expanded Suite of Test Problems with Different Properties.

Additional MOEA Performance Metrics. Statistical Comparative Analysis of Performance Metrics. Integration of the Proposed Methodology with Commercial Simulation Software 110 LIST OF REFERENCES. 111 vii LIST OF FIGURES Figure 1.1: Illustration of strict dominance in a deterministic problem domain.2: Illustration of the classical approach and nondomination-based approach for minimization problem with two objectives (Deb, 2001).3: General process of simulation optimization.

Taxonomy of existing simulation optimization approaches. Flow diagram of NSGA (obtained from Srinivas and Deb (1994)). Pseudocode of the proposed fast Pareto genetic algorithm (FPGA). Logic flow of the fast Pareto genetic algorithm (FPGA).3: Illustration of crowding distance calculation.

The velocity measure PPR on KUR. The velocity measure PPR on ZDT6. The populations with FPGA and NSGA-II on KUR. The populations with FPGA and NSGA-II on ZDT1.

The populations with FPGA and NSGA-II on ZDT2. The populations with FPGA and NSGA-II on ZDT3. The populations with FPGA and NSGA-II on ZDT4. The populations with FPGA and NSGA-II on ZDT6.

The populations with FPGA having poor diversity in few replications and NSGA-II on ZDT3. Population regulation behavior of FPGA on ZDT6. Plot of normally-distributed random variable t. The populations with SPGA-s, SPGA-r and NSGA-II on KUR.

The populations with SPGA-s, SPGA-r and NSGA-II on ZDT1. The populations with SPGA-s, SPGA-r and NSGA-II on ZDT4. The populations with SPGA-s, SPGA-r and NSGA-II on ZDT6. 102 ix LIST OF TABLES Table 2.1: Gradient estimation techniques for stochastic approximation (summarized from Fu (2002)).

Commercial implementation of metaheuristic search strategies for simulation optimization (obtained from Law and Kelton (2000)). Summary of simulation optimization approaches (obtained from Fu (2002)).1: Benchmark test problems.2: Parameter settings for FPGA and NSGA-II. Mean, standard deviation and 95% confidence interval of distance and diversity metrics for FPGA and NSGA-II over the 30 random replications. Mean, standard deviation and 95% confidence interval of delineation Φ and hypervolume ratio HVR metrics for FPGA and NSGA-II over the 30 random replications.1: Parameter settings for SPGA and NSGA-II.

Mean, standard deviation and 95% confidence interval of distance ϒ and diversity ∆ metrics for SPGA-s, SPGA-r and NSGA-II over 50 random replications. Mean, standard deviation and 95% confidence interval of delineation Φ and hypervolume ratio HVR metrics for SPGA-s, SPGA-r and NSGA-II over 50 random replications. Multiobjective Optimization In today’s competitive global business environment, a firm’s ability to make the most appropriate critical decisions can be translated into a great competitive advantage. Most of these critical decisions are multiple objective problems in which management should be able to handle the challenges of conflicting objectives.

For example, in supply chain management, the objective of reducing total costs typically opposes the objective of decreasing lead times, and improving product quality. These conflicting objectives are also encountered in other problem settings including job shop scheduling, inventory control, facility location, portfolio management and project management. In recent years, multiple objective problems have begun to draw the attention of practitioners and academicians alike. Several methods exist that one could use to solve problems involving multiple objectives (Szidarovszky et al., 1986; Mollaghasemi and Pet-Edwards, 1992).

A naïve way is to select the most important performance objective and ignore the other less important objectives. This treatment of neglecting some objectives will undoubtedly result in poor solutions. Another method is to select a single objective for optimization and constrain the values of the other objectives to be within certain levels. The main drawback of this method is that the constrained objectives usually restrict the feasible solution space resulting in no feasible solution being found.

1 Other more traditional approaches for solving multiobjective optimization problems (MOPs) typically try to scalarize the multiple objectives into a single objective. This transforms the original multiple objective optimization problem formulation into a single objective optimization problem with a single solution. The major drawbacks of traditional methods that serve as motivation for using these alternative techniques include: ƒ The priority (or weight) vector used in the scalarization process greatly influences the final solution; ƒ Alternative solutions will not be available to decision-makers without at least changing some parameters such as the priority vector; ƒ Some optimal solutions may never be found if the objective space is not convex for minimization problems (Szidarovszky et al. 34-39); real-world problems are seldom convex (Silva and Biscaia, 2003); ƒ There are implications in the homogenization of different performance measures (such as cost, quality of products, and cycle times) to a common unit of measure; and ƒ Traditional approaches may not work effectively if objectives are noisy or have discontinuous variable space.

For example, consider the first drawback. A small perturbation in the priority vector values can greatly influence the obtained solution. Each certain pair of weights w1 and w2 (w2 = 1 – w1 for biobjective problem) results in single nondominated point in the tradeoff curve. However, the drawbacks of this class of approaches have motivated researchers and practitioners to seek alternative techniques to find a set of Pareto optimal 2 (nondominated) solutions rather than just a single solution (e.