New multi-objective ranking and selection procedures for discrete stochastic simulation problems
Date
2018-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: In stochastic simulation optimisation, several system designs are considered.
These designs are ranked in order and the best is selected based on one or more performance measures. Any ranking and selection (R&S) procedure must ensure that the correct system design is chosen, and this is a challenging task in the stochastic environment.
This dissertation discusses the design and development of a new multiobjective ranking and selection (MORS) procedure, called Procedure MMY, and two variants of it, called Procedures MMY1 and MMY2.
Single-objective ranking and selection procedures endeavour to find the best system, i.e., the system with the minimum or maximum output, out of a
limited number of feasible solutions. There are two important approaches in the single-objective R&S area: the indifference-zone (IZ) approach and the optimal computing budget allocation (OCBA) framework. While the OCBA procedure has been extended to the multi-objective domain, an MORS procedure with the IZ approach has not yet appeared in the literature. The
MMY family procedures have been developed in an attempt to fill this gap, therefore they take the IZ approach.
Indifference-zone procedures should guarantee that the probability of correct selection is at least a prespecified value P*, denoted by P(CS) * P*, where `correct selection' denotes the event that the system with the minimum output is selected for a single-objective minimisation problem. In the multi-objective context, Pareto optimality is employed to define `correct
selection'.
The concept of relaxed Pareto optimality is proposed in this research to accommodate the indifference-zone concept properly in the multi-objective domain.
Thus, Procedure MMY guarantees P(CS) * P* considering the event of identifying a relaxed Pareto set as a correct selection. Procedure MMY1 tries to find the normal Pareto optimal set while Procedure MMY2 focuses on identifying Pareto optimal solutions with the IZ concept.
The statistical validity of the MMY family procedures is proved through rigorous mathematical analyses in this dissertation. A Bayesian probability model was used in the P(CS) formulation in the proofs. Using a Bayesian
model in the P(CS) formulation in IZ R&S procedures is a novel approach even in the single-objective context. The researcher therefore proposed a new single-objective R&S procedure, called Procedure MY, in addition to
the multi-objective MMY family procedures. The MY procedure is discussed prior to the discussion of the MMY family procedures, verifying the effectiveness of the Bayesian model, thereby laying the theoretical foundation
for employing it for the MMY family procedures.
The performance of the proposed MMY family procedures was demonstrated using four simulation case studies. These simulation case studies provided various types of test beds to understand the behaviour of the
proposed procedures. In all four cases the estimated probability of correct selection was observed to be greater than P* for all three procedures, proving the statistical validity of them empirically, too. In addition, the performance of the proposed MMY family procedures was compared to that of the MOCBA procedure, which is the only existing MORS procedure.
The result showed the superiority of the MMY procedure over the MOCBA procedure in many cases.
AFRIKAANSE OPSOMMING: In stogastiese simulasie-optimering word verskeie stelselontwerpe oorweeg. Hierdie ontwerpe word in rangorde rangskik en die beste gekies, gebaseer op een of meer prestasiemaatstawwe. Enige rangskik-en-kies prosedure moet verseker dat die korrekte stelselontwerp gekies word, en hierdie is 'n uitdagende taak in die stogastiese omgewing. Hierdie proefskrif bespreek die ontwerp en ontwikkeling van 'n nuwe multidoelwit rangskik-en-kies (MDRK) prosedure in stogastiese optimering. Die prosedure word MMY genoem, met twee variante genaamd MMY1 en MMY2. Enkeldoelwit rangskik-en-kies prosedures (R&K) poog om die beste stelsel, dit wil s^e, die stelsel met die minimum of maksimum afvoer, uit 'n beperkte aantal gangbare oplossings te vind. Daar is twee belangrike benaderings in die enkeldoelwit R&K area: die geen-verskilsone (GS) benadering en die optimum-rekenbegroting toedeling (ORBT) raamwerk. Hoewel die ORBT prosedure uitgebrei is na die multi-doelwitdomein, bestaan daar tans nie 'n MDRK prosedure in die GS domein nie. Die MMY familie van prosedures is geskep om hierdie gaping te vul, dus gebruik die prosedures die GS benadering tot R&K. GS prosedures behoort te waarborg dat die waarskynlikheid van korrekte keuse 'n voorafgestelde waarde P* bevredig, aangedui met P(CS) ≥ P*. Die term `korrekte keuse' dui op die gebeurtenis dat die stelsels met die minimum uitsetwaarde gekies word in 'n enkeldoelwitoptimeringprobleem, terwyl Pareto-optimaliteit in die multi-doelwitkonteks gebruik word om `korrekte keuse' te definieer. Die konsep van verslapte Pareto-optimaliteit word in hierdie navorsing voorgestel om die geen-verskilkonsep voldoende in die multidoelwitdomein te akkommodeer. Prosedure MMY waarborg P(CS) ≥ P* as 'n verslapte Pareto-versameling as korrekte keuse aanvaar word. Prosedure MMY1 poog om die streng-korrekte Paretostel te vind, terwyl Prosedure MMY2 fokus op die vind van Pareto-optimale oplossings met die GS konsep. Die statistiese geldigheid van die MMY familie van prosedures word in hierdie proefskrif bewys deur streng wiskundige analise. 'n Bayes-waarskynlikheidsmodel is gebruik in die formulering van P(CS) in die bewyse. Die gebruik van 'n Bayes-model in die formulering van P(CS) in GS R&K prosedures is uniek, selfs in die enkeldoelwit geval. Die navorser het dus 'n nuwe enkeldoelwit R&K prosedure, naamlik MY, tesame met die multidoelwit MMY familie van prosedures voorgestel. Die MY prosedure word eerste aangebied en bespreek, en daardeur word die effektiwiteit van die Bayes-model bevestig. Sodoende is die teoretiese basis vir gebruik van die Bayes-model in die MMY familie van prosedures gelê. Die prestasie van die MMY familie van prosedures word aan die hand van vier simulasiegevallestudies demonstreer. Hierdie gevallestudies verskaf verskillende tipes toetsplatforms wat bydra om die gedrag van die voorgestelde prosedures te verstaan. In al vier gevalle is die beraamde waarskynlikheid van korrekte keuse groter as P* vir al drie prosedures, wat die statistiese geldigheid daarvan empiries ondersteun. Verder is die prestasie van die voorgestelde familie van MMY prosedures met die van die ORBT prosedure vergelyk, wat die enigste multidoelwit R&K prosedure tot op hede is. Die resultate toon dat die MMY prosedures in verskeie gevalle die ORBT prosedure oorheers.
AFRIKAANSE OPSOMMING: In stogastiese simulasie-optimering word verskeie stelselontwerpe oorweeg. Hierdie ontwerpe word in rangorde rangskik en die beste gekies, gebaseer op een of meer prestasiemaatstawwe. Enige rangskik-en-kies prosedure moet verseker dat die korrekte stelselontwerp gekies word, en hierdie is 'n uitdagende taak in die stogastiese omgewing. Hierdie proefskrif bespreek die ontwerp en ontwikkeling van 'n nuwe multidoelwit rangskik-en-kies (MDRK) prosedure in stogastiese optimering. Die prosedure word MMY genoem, met twee variante genaamd MMY1 en MMY2. Enkeldoelwit rangskik-en-kies prosedures (R&K) poog om die beste stelsel, dit wil s^e, die stelsel met die minimum of maksimum afvoer, uit 'n beperkte aantal gangbare oplossings te vind. Daar is twee belangrike benaderings in die enkeldoelwit R&K area: die geen-verskilsone (GS) benadering en die optimum-rekenbegroting toedeling (ORBT) raamwerk. Hoewel die ORBT prosedure uitgebrei is na die multi-doelwitdomein, bestaan daar tans nie 'n MDRK prosedure in die GS domein nie. Die MMY familie van prosedures is geskep om hierdie gaping te vul, dus gebruik die prosedures die GS benadering tot R&K. GS prosedures behoort te waarborg dat die waarskynlikheid van korrekte keuse 'n voorafgestelde waarde P* bevredig, aangedui met P(CS) ≥ P*. Die term `korrekte keuse' dui op die gebeurtenis dat die stelsels met die minimum uitsetwaarde gekies word in 'n enkeldoelwitoptimeringprobleem, terwyl Pareto-optimaliteit in die multi-doelwitkonteks gebruik word om `korrekte keuse' te definieer. Die konsep van verslapte Pareto-optimaliteit word in hierdie navorsing voorgestel om die geen-verskilkonsep voldoende in die multidoelwitdomein te akkommodeer. Prosedure MMY waarborg P(CS) ≥ P* as 'n verslapte Pareto-versameling as korrekte keuse aanvaar word. Prosedure MMY1 poog om die streng-korrekte Paretostel te vind, terwyl Prosedure MMY2 fokus op die vind van Pareto-optimale oplossings met die GS konsep. Die statistiese geldigheid van die MMY familie van prosedures word in hierdie proefskrif bewys deur streng wiskundige analise. 'n Bayes-waarskynlikheidsmodel is gebruik in die formulering van P(CS) in die bewyse. Die gebruik van 'n Bayes-model in die formulering van P(CS) in GS R&K prosedures is uniek, selfs in die enkeldoelwit geval. Die navorser het dus 'n nuwe enkeldoelwit R&K prosedure, naamlik MY, tesame met die multidoelwit MMY familie van prosedures voorgestel. Die MY prosedure word eerste aangebied en bespreek, en daardeur word die effektiwiteit van die Bayes-model bevestig. Sodoende is die teoretiese basis vir gebruik van die Bayes-model in die MMY familie van prosedures gelê. Die prestasie van die MMY familie van prosedures word aan die hand van vier simulasiegevallestudies demonstreer. Hierdie gevallestudies verskaf verskillende tipes toetsplatforms wat bydra om die gedrag van die voorgestelde prosedures te verstaan. In al vier gevalle is die beraamde waarskynlikheid van korrekte keuse groter as P* vir al drie prosedures, wat die statistiese geldigheid daarvan empiries ondersteun. Verder is die prestasie van die voorgestelde familie van MMY prosedures met die van die ORBT prosedure vergelyk, wat die enigste multidoelwit R&K prosedure tot op hede is. Die resultate toon dat die MMY prosedures in verskeie gevalle die ORBT prosedure oorheers.
Description
Thesis (PhD)--Stellenbosch University, 2018.
Keywords
Stochastic models, Mathematical optimization, UCTD, Ranking and selection (Statistics)