Applying the cross-entropy method in multi-objective optimisation of dynamic stochastic systems

Bekker, James (2012-12)

Thesis (PhD)--Stellenbosch University, 2012.

Thesis

ENGLISH ABSTRACT: A difficult subclass of engineering optimisation problems is the class of optimisation problems which are dynamic and stochastic. These problems are often of a non-closed form and thus studied by means of computer simulation. Simulation production runs of these problems can be time-consuming due to the computational burden implied by statistical inference principles. In multi-objective optimisation of engineering problems, large decision spaces and large objective spaces prevail, since two or more objectives are simultaneously optimised and many problems are also of a combinatorial nature. The computational burden associated with solving such problems is even larger than for most single-objective optimisation problems, and hence an e cient algorithm that searches the vast decision space is required. Many such algorithms are currently available, with researchers constantly improving these or developing more e cient algorithms. In this context, the term \e cient" means to provide near-optimised results with minimal evaluations of objective function values. Thus far research has often focused on solving speci c benchmark problems, or on adapting algorithms to solve speci c engineering problems. In this research, a multi-objective optimisation algorithm, based on the cross-entropy method for single-objective optimisation, is developed and assessed. The aim with this algorithm is to reduce the number of objective function evaluations, particularly when time-dependent (dynamic), stochastic processes, as found in Industrial Engineering, are studied. A brief overview of scholarly work in the eld of multiobjective optimisation is presented, followed by a theoretical discussion of the cross-entropy method. The new algorithm is developed, based on this information, and assessed considering continuous, deterministic problems, as well as discrete, stochastic problems. The latter include a classical single-commodity inventory problem, the well-known buffer allocation problem, and a newly designed, laboratory-sized recon gurable manufacturing system. Near multi-objective optimisation of two practical problems were also performed using the proposed algorithm. In the rst case, some design parameters of a polymer extrusion unit are estimated using the algorithm. The management of carbon monoxide gas utilisation at an ilmenite smelter is complex with many decision variables, and the application of the algorithm in that environment is presented as a second case. Quality indicator values are estimated for thirty-four test problem instances of multi-objective optimisation problems in order to quantify the quality performance of the algorithm, and it is also compared to a commercial algorithm. The algorithm is intended to interface with dynamic, stochastic simulation models of real-world problems. It is typically implemented in a programming language while the simulation model is developed in a dedicated, commercial software package. The proposed algorithm is simple to implement and proved to be efficient on test problems.

AFRIKAANSE OPSOMMING: 'n Moeilike deelklas van optimeringsprobleme in die ingenieurswese is optimeringsprobleme van 'n dinamiese en stogastiese aard. Sulke probleme is dikwels nie-geslote en word gevolglik met behulp van rekenaarsimulasie bestudeer. Die beginsels van statistiese steekproefneming veroorsaak dat produksielopies van hierdie probleme tydrowend is weens die rekenlas wat genoodsaak word. Groot besluitnemingruimtes en doelwitruimtes bestaan in meerdoelige optimering van ingenieursprobleme, waar twee of meer doelwitte gelyktydig geoptimeer word, terwyl baie probleme ook 'n kombinatoriese aard het. Die rekenlas wat met die oplos van sulke probleme gepaard gaan, is selfs groter as vir die meeste enkeldoelwit optimeringsprobleme, en 'n doeltre ende algoritme wat die meesal uitgebreide besluitnemingsruimte verken, is gevolglik nodig. Daar bestaan tans verskeie sulke algoritmes, terwyl navorsers steeds poog om hierdie algoritmes te verbeter of meer doeltre ende algoritmes te ontwikkel. In hierdie konteks beteken \doeltre end" dat naby-optimale oplossings verskaf word deur die minimum evaluering van doelwitfunksiewaardes. Navorsing fokus dikwels op oplossing van standaard toetsprobleme, of aanpassing van algoritmes om 'n spesi eke ingenieursprobleem op te los. In hierdie navorsing word 'n meerdoelige optimeringsalgoritme gebaseer op die kruis-entropie-metode vir enkeldoelwit optimering ontwikkel en geassesseer. Die mikpunt met hierdie algoritme is om die aantal evaluerings van doelwitfunksiewaardes te verminder, spesi ek wanneer tydafhanklike (dinamiese), stogastiese prosesse soos wat dikwels in die Bedryfsingenieurswese te egekom word, bestudeer word. 'n Bondige oorsig van navorsing in die veld van meerdoelige optimering word gegee, gevolg deur 'n teoretiese bespreking van die kruis-entropiemetode. Die nuwe algoritme se ontwikkeling is hierop gebaseer, en dit word geassesseer deur kontinue, deterministiese probleme sowel as diskrete, stogastiese probleme benaderd daarmee op te los. Laasgenoemde sluit in 'n klassieke enkelitem voorraadprobleem, die bekende buffer-toedelingsprobleem, en 'n nuut-ontwerpte, laboratorium-skaal herkon gureerbare vervaardigingstelsel. Meerdoelige optimering van twee praktiese probleme is met die algoritme uitgevoer. In die eerste geval word sekere ontwerpparameters van 'n polimeer-uittrekeenheid met behulp van die algoritme beraam. Die bestuur van koolstofmonoksiedbenutting in 'n ilmeniet-smelter is kompleks met verskeie besluitnemingveranderlikes, en die toepassing van die algoritme in daardie omgewing word as 'n tweede geval aangebied. Verskeie gehalte-aanwyserwaardes word beraam vir vier-en-dertig toetsgevalle van meerdoelige optimeringsprobleme om die gehalte-prestasie van die algoritme te kwanti seer, en dit word ook vergelyk met 'n kommersi ele algoritme. Die algoritme is veronderstel om te skakel met dinamiese, stogastiese simulasiemodelle van regtew^ereldprobleme. Die algoritme sal tipies in 'n programmeertaal ge mplementeer word terwyl die simulasiemodel in doelmatige, kommersi ele programmatuur ontwikkel sal word. Die voorgestelde algoritme is maklik om te implementeer en dit het doeltre end gewerk op toetsprobleme.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/71717
This item appears in the following collections: