A comparative study on the value of accounting for possible relationships between decision variables when solving multi-objective problems
Date
2014-04
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: The cross-entropy method for multi-objective optimisation (MOO CEM)
was recently introduced by Bekker & Aldrich (2010) and Bekker (2012).
Results presented by both show great promise. The MOO CEM assumes
that decision variables are independent. As a consequence, the question
arises: under which circumstances would an algorithm that accounts for
relationships between decision variables outperform the MOO CEM? Two
algorithms reported to account for relationships between decision variables,
the multi-objective covariance matrix adaptation evolution strategy (MOCMA-
ES) and Pareto di erential evolution (PDE), are selected for comparison.
In addition, two hybrid algorithms (Hybrid 1 and Hybrid 2) based
on the MOO CEM are created. These ve algorithms are applied to a
set of 46 continuous problems, six instances of the mission-ready resource
(MRR) problem, and three instances of a dynamic, stochastic bu er allocation
problem (BAP). Performance is measured using the hypervolume
indicator and Mann-Whitney U-tests. One of the primary ndings is that
accounting for relationships between decision variables is bene cial when
solving small to medium-sized problems. In these cases, the MO-CMA-ES
typically outperforms the other algorithms. However, on large problems,
Hybrid 1 and the MOO CEM typically perform best.
AFRIKAANSE OPSOMMING: Die kruis-entropie metode vir meerdoelige optimering (MOO CEM) is onlangs deur Bekker & Aldrich (2010) en Bekker (2012) bekendgestel. Hul resultate is belowend. Die MOO CEM neem aan dat besluitnemingsveranderlikes onafhanklik is van mekaar. Gevolglik ontstaan die vraag: onder watter omstandighede sal 'n optimeringsalgoritme wat moontlike verhoudings tussen besluitnemingsveranderlikes in ag neem, beter vaar as die MOO CEM? Twee bestaande algoritmes, beide gerapporteer vir hul vermo e om moontlike verhoudings tussen besluitnemingsveranderlikes in ag te neem, naamlik die meerdoelige optimering kovariansiematriksaanpassing-evolusiestrategie (MO-CMA-ES) en Pareto afgeleide evolusie (PDE), word met die MOO CEM vergelyk. Twee nuwe hibriedalgoritmes (Hibried 1 en Hibried 2) word ook ter wille van di e vergelyking geskep. Die vyf algoritmes word op 'n stel van 46 kontinue probleme, ses statiese kombinatoriese gevalle en drie dinamies, stogastiese gevalle toegepas. Die prestasie van die algoritmes word deur middel van die hipervolume-aanwyser en Mann-Whitney U-toetse gemeet. 'n Prim^ere bevinding is dat dit voordelig is om moontlike verhoudings tussen besluitnemingsveranderlikes in ag te neem wanneer klein na medium-grootte probleme opgelos word. Vir hierdie gevalle presteer die MO-CMA-ES tipies beter as die ander algoritmes. Vir groot probleme presteer Hibried 1 en die MOO CEM beter as die ander algoritmes.
AFRIKAANSE OPSOMMING: Die kruis-entropie metode vir meerdoelige optimering (MOO CEM) is onlangs deur Bekker & Aldrich (2010) en Bekker (2012) bekendgestel. Hul resultate is belowend. Die MOO CEM neem aan dat besluitnemingsveranderlikes onafhanklik is van mekaar. Gevolglik ontstaan die vraag: onder watter omstandighede sal 'n optimeringsalgoritme wat moontlike verhoudings tussen besluitnemingsveranderlikes in ag neem, beter vaar as die MOO CEM? Twee bestaande algoritmes, beide gerapporteer vir hul vermo e om moontlike verhoudings tussen besluitnemingsveranderlikes in ag te neem, naamlik die meerdoelige optimering kovariansiematriksaanpassing-evolusiestrategie (MO-CMA-ES) en Pareto afgeleide evolusie (PDE), word met die MOO CEM vergelyk. Twee nuwe hibriedalgoritmes (Hibried 1 en Hibried 2) word ook ter wille van di e vergelyking geskep. Die vyf algoritmes word op 'n stel van 46 kontinue probleme, ses statiese kombinatoriese gevalle en drie dinamies, stogastiese gevalle toegepas. Die prestasie van die algoritmes word deur middel van die hipervolume-aanwyser en Mann-Whitney U-toetse gemeet. 'n Prim^ere bevinding is dat dit voordelig is om moontlike verhoudings tussen besluitnemingsveranderlikes in ag te neem wanneer klein na medium-grootte probleme opgelos word. Vir hierdie gevalle presteer die MO-CMA-ES tipies beter as die ander algoritmes. Vir groot probleme presteer Hibried 1 en die MOO CEM beter as die ander algoritmes.
Description
Thesis (MEng)--Stellenbosch University, 2014.
Keywords
Computer algorithms, Metaheuristic, MOO-CEM, Dissertations -- Industrial engineering, Theses -- Industrial engineering, UCTD