Integration of ranking and selection methods with the multi-objective optimisation cross-entropy method
Date
2015-03
Authors
Von Lorne von Saint Ange, Chantel
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: A method for multi-objective optimisation using the cross-entropy
method (MOO CEM) was recently developed by Bekker & Aldrich
(2010) and Bekker (2012). The method aims to identify the nondominated
solutions of multi-objective problems, which are often dynamic
and stochastic. The method does not use a statistical ranking
and selection technique to account for the stochastic nature of the
problems it solves. The research in this thesis aims to investigate
possible techniques that can be incorporated into the MOO CEM.
The cross-entropy method for single-objective optimisation is studied
first. It is applied to an interesting problem in the soil sciences and
water management domain. The purpose of this was for the researcher
to grasp the fundamentals of the cross-entropy method, which will be
needed later in the study.
The second part of the study documents an overview of multi-objective
ranking and selection methods found in literature. The first method
covered is the multi-objective optimal computing budget allocation
algorithm. The second method extends upon the first to include the
concept of an indifference-zone. Both methods aim to maximise the
probability of correctly selecting the non-dominated scenarios, while
intelligently allocating simulation replications to minimise required
sample sizes. These techniques are applied to two problems that
are represented by simulation models, namely the buffer allocation
problem and a classic single-commodity inventory problem. Performance
is measured using the hyperarea indicator and Mann-Whitney
U-tests. It was found that the two techniques have significantly different
performances, although this could be due to the different number
of solutions in the Pareto set.
In the third part of the document, the aforementioned multi-objective
ranking and selection techniques are incorporated into the MOO CEM.
Once again, the buffer allocation problem and the inventory problem
were chosen as test problems. The results were compared to experiments
where the MOO CEM without ranking and selection was used.
Results show that the MOO CEM with ranking and selection has
various affects on different problems. Investigating the possibility of
incorporating ranking and selection differently in the MOO CEM is
recommended as future research. Additionally, the combined algorithm
should be tested on more stochastic problems.
AFRIKAANSE OPSOMMING: 'n Metode vir meerdoelige optimering wat gebruik maak van die kruisentropie- metode (MOO CEM) is onlangs deur Bekker & Aldrich (2010) en Bekker (2012) ontwikkel. Die metode mik om die nie-gedomineerde oplossings van meerdoelige probleme te identifiseer, wat dikwels dinamies en stogasties is. Die metode maak nie gebruik van 'n statistiese orden-en-kies tegniek om die stogastiese aard van die problem aan te spreek nie. Die navorsing in hierdie tesis poog om moontlike tegnieke wat in die MOO CEM opgeneem kan word, te ondersoek. Die kruis-entropie-metode vir enkeldoelwit optimering is eerste bestudeer. Dit is toegepas op 'n interessante probleem in die grondwetenskappe en waterbestuur domein. Die doel hiervan was om die navorser die grondbeginsels van die kruis-entropie metode te help verstaan, wat later in die studie benodig sal word. Die tweede gedeelte van die studie verskaf 'n oorsig van meerdoelige orden-en-kies metodes wat in die literatuur aangetref word. Die eerste metode wat bespreek word, is die optimale toedeling van rekenaarbegroting vir multi-doelwit optimering algoritme. Die tweede metode brei uit oor die eerste metode wat die konsep van 'n neutrale sone insluit. Beide metodes streef daarna om die waarskynlikheid dat die nie-gedomineerde oplossings korrek gekies word te maksimeer, terwyl dit ook steekproefgroottes probeer minimeer deur die aantal simulasieherhalings intelligent toe te ken. Hierdie tegnieke word toegepas op twee probleme wat verteenwoordig word deur simulasiemodelle, naamlik die buffer-toedelingsprobleem en 'n klassieke enkelitem voorraadprobleem. Die prestasie van die algoritmes word deur middel van die hiperarea-aanwyser en Mann Whitney U-toetse gemeet. Daar is gevind dat die twee tegnieke aansienlik verskillend presteer, alhoewel dit as gevolg van die verskillende aantal oplossings in die Pareto versameling kan wees. In die derde gedeelte van die dokument, is die bogenoemde meerdoelige orden-en-kies tegnieke in die MOO CEM geïnkorporeer. Weereens is die buffer-toedelingsprobleem en die voorraadprobleem as toetsprobleme gekies. Die resultate was met die eksperimente waar die MOO CEM sonder orden-en-kies gebruik is, vergelyk. Resultate toon dat vir verskillende probleme, tree die MOO CEM met orden-en-kies anders op. 'n Ondersoek oor 'n alternatiewe manier om orden-en-kies met die MOO CEM te integreer is as toekomstige navorsing voorgestel. Bykomend moet die gekombineerde algoritme op meer stogastiese probleme getoets word.
AFRIKAANSE OPSOMMING: 'n Metode vir meerdoelige optimering wat gebruik maak van die kruisentropie- metode (MOO CEM) is onlangs deur Bekker & Aldrich (2010) en Bekker (2012) ontwikkel. Die metode mik om die nie-gedomineerde oplossings van meerdoelige probleme te identifiseer, wat dikwels dinamies en stogasties is. Die metode maak nie gebruik van 'n statistiese orden-en-kies tegniek om die stogastiese aard van die problem aan te spreek nie. Die navorsing in hierdie tesis poog om moontlike tegnieke wat in die MOO CEM opgeneem kan word, te ondersoek. Die kruis-entropie-metode vir enkeldoelwit optimering is eerste bestudeer. Dit is toegepas op 'n interessante probleem in die grondwetenskappe en waterbestuur domein. Die doel hiervan was om die navorser die grondbeginsels van die kruis-entropie metode te help verstaan, wat later in die studie benodig sal word. Die tweede gedeelte van die studie verskaf 'n oorsig van meerdoelige orden-en-kies metodes wat in die literatuur aangetref word. Die eerste metode wat bespreek word, is die optimale toedeling van rekenaarbegroting vir multi-doelwit optimering algoritme. Die tweede metode brei uit oor die eerste metode wat die konsep van 'n neutrale sone insluit. Beide metodes streef daarna om die waarskynlikheid dat die nie-gedomineerde oplossings korrek gekies word te maksimeer, terwyl dit ook steekproefgroottes probeer minimeer deur die aantal simulasieherhalings intelligent toe te ken. Hierdie tegnieke word toegepas op twee probleme wat verteenwoordig word deur simulasiemodelle, naamlik die buffer-toedelingsprobleem en 'n klassieke enkelitem voorraadprobleem. Die prestasie van die algoritmes word deur middel van die hiperarea-aanwyser en Mann Whitney U-toetse gemeet. Daar is gevind dat die twee tegnieke aansienlik verskillend presteer, alhoewel dit as gevolg van die verskillende aantal oplossings in die Pareto versameling kan wees. In die derde gedeelte van die dokument, is die bogenoemde meerdoelige orden-en-kies tegnieke in die MOO CEM geïnkorporeer. Weereens is die buffer-toedelingsprobleem en die voorraadprobleem as toetsprobleme gekies. Die resultate was met die eksperimente waar die MOO CEM sonder orden-en-kies gebruik is, vergelyk. Resultate toon dat vir verskillende probleme, tree die MOO CEM met orden-en-kies anders op. 'n Ondersoek oor 'n alternatiewe manier om orden-en-kies met die MOO CEM te integreer is as toekomstige navorsing voorgestel. Bykomend moet die gekombineerde algoritme op meer stogastiese probleme getoets word.
Description
Thesis (MEng)--Stellenbosch University, 2015.
Keywords
Multi-objective optimisation, Ranking and selection, Cross-entropy method, UCTD