No description available.

Session ID: TH-F3-4 / SCIS & ISIS 2010, Joint 5th International Conference on Soft Computing and Intelligent Systems and 11th International Symposium on Advanced Intelligent Systems. December 8-12, 2010, Okayama Convention Center, Okayama, Japan

Monte Carlo simulation methods are becoming increasingly important for solving difficult optimization problems. Monte Carlo methods are often used when it is infeasible to determine an exact result via a deterministic algorithm, such as with NP or #P problems. Several recent Monte Carlo techniques employ the idea of importance sampling; examples include the Cross-Entropy method and sequential importance sampling. The Cross-Entropy method is a relatively new Monte Carlo technique that has been successfully applied to a wide range of optimization and estimation problems since introduced by R. Y. Rubinstein in 1997. However, as the problem size increases, the Cross-Entropy method, like many heuristics, can take an exponentially increasing amount of time before it returns a solution. For large problems this can lead to an impractical amount of running time. A main aim of this thesis is to develop the Cross-Entropy method for large-scale parallel computing, allowing the running time of a Cross-Entropy program to be significantly reduced by the use of additional computing resources. The effectiveness of the parallel approach is demonstrated via a number of numerical studies. A second aim is to apply the Cross-Entropy method and sequential importance sampling to biological problems, in particular the multiple change-point problem for DNA sequences. The multiple change-point problem in a general setting is the problem of identifying, given a particular sequence of numbers/characters, a point along that sequence where some property of interest changes abruptly. An example in a biological setting, is identifying points in a DNA sequence where there is a significant change in the proportion of the nucleotides G and C with respect to the nucleotides A and T. We show that both sequential importance sampling and the Cross-Entropy approach yield significant improvements in time and/or accuracy over existing techniques.

The cross-entropy method is an established technique for solving difficult estimation, simulation, and optimisation problems. The method has its origins in an adaptive importance sampling procedure for rare-event estimation published by R. Y. Rubinstein in 1997. In that publication, the adaptive procedure produces a parametric probability density function whose parameters minimise the variance of the associated likelihood ratio estimator. This variance minimisation can also be viewed as minimising a measure of divergence to the minimum-variance importance sampling density over all members of the parametric family in question. Soon thereafter it was realised that the same adaptive importance sampling procedure could be used to solve combinatorial optimisation problems by viewing the set of solutions to the optimisation problem as a rare-event. This realisation led to the debut of the cross-entropy method in 1999, where it was introduced as a modification to the existing adaptive importance sampling procedure, with a different choice of directed divergence measure, in particular, the Kullback-Leibler cross-entropy. The contributions of this thesis are threefold. Firstly, in a review capacity, it provides an up-to-date consolidation of material on the cross-entropy method and its generalisations, as well as a collation of background material on importance sampling and Monte Carlo methods. The reviews are elucidated with original commentary and examples. Secondly, two new major applications of the cross-entropy methodology to optimisation problems are presented, advancing the boundary of knowledge on cross-entropy in the applied arena. Thirdly, two contributions to the methodological front are (a) an original extension of the generalised cross-entropy framework which enables one to construct state- and time-dependent importance sampling algorithms, and (b) a new algorithm for counting solutions to difficult binary-encoded problems.

The cross-entropy method is an established technique for solving difficult estimation, simulation, and optimisation problems. The method has its origins in an adaptive importance sampling procedure for rare-event estimation published by R. Y. Rubinstein in 1997. In that publication, the adaptive procedure produces a parametric probability density function whose parameters minimise the variance of the associated likelihood ratio estimator. This variance minimisation can also be viewed as minimising a measure of divergence to the minimum-variance importance sampling density over all members of the parametric family in question. Soon thereafter it was realised that the same adaptive importance sampling procedure could be used to solve combinatorial optimisation problems by viewing the set of solutions to the optimisation problem as a rare-event. This realisation led to the debut of the cross-entropy method in 1999, where it was introduced as a modification to the existing adaptive importance sampling procedure, with a different choice of directed divergence measure, in particular, the Kullback-Leibler cross-entropy. The contributions of this thesis are threefold. Firstly, in a review capacity, it provides an up-to-date consolidation of material on the cross-entropy method and its generalisations, as well as a collation of background material on importance sampling and Monte Carlo methods. The reviews are elucidated with original commentary and examples. Secondly, two new major applications of the cross-entropy methodology to optimisation problems are presented, advancing the boundary of knowledge on cross-entropy in the applied arena. Thirdly, two contributions to the methodological front are (a) an original extension of the generalised cross-entropy framework which enables one to construct state- and time-dependent importance sampling algorithms, and (b) a new algorithm for counting solutions to difficult binary-encoded problems.

Thesis (MEng)--Stellenbosch University, 2015. / 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.

Thesis (MScEng)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: Society is continually in search of ways to optimise various objectives. When faced with multiple and con icting objectives, humans are in need of solution techniques to enable optimisation. This research is based on a recent venture in the eld of multi-objective optimisation, the use of the cross-entropy method to solve multi-objective problems. The document provides a brief overview of the two elds, multi-objective optimisation and the cross-entropy method, touching on literature, basic concepts and applications or techniques. The application of the method to two problems is then investigated. The rst application is to the multi-objective vehicle routing problem with soft time windows, a widely studied problem with many real-world applications. The problem is modelled mathematically with a transition probability matrix that is updated according to cross-entropy principles before converging to an approximation solution set. The highly constrained problem is successfully modelled and the optimisation algorithm is applied to a set of benchmark problems. It was found that the cross-entropy method for multi-objective optimisation is a valid technique in providing feasible and non-dominated solutions. The second application is to a real world case study in blood management done at the Western Province Blood Transfusion Service. The conceptual model is derived from interviews with relevant stakeholders before discrete event simulation is used to model the system. The cross-entropy method is used to optimise the inventory policy of the system by simultaneously maximising the combined service level of the system and minimising the total distance travelled. By integrating the optimisation and simulation model, the study shows that the inventory policy of the service can improve signi cantly, and the use of the cross-entropy algorithm adequately progresses to a front of solutions. The research proves the remarkable width and simplicity of possible applications of the cross-entropy algorithm for multi-objective optimisation, whilst contributing to literature on the vehicle routing problem and blood management. Results on benchmark problems for the vehicle routing problem with soft time windows are provided and an improved inventory policy is suggested to the Western Province Blood Transfusion Service. / AFRIKAANSE OPSOMMING: Die mensdom is voortdurend op soek na maniere om verskeie doelwitte te optimeer. Wanneer die mens konfrontreer word met meervoudige en botsende doelwitte, is oplossingsmetodes nodig om optimering te bewerkstellig. Hierdie navorsing is baseer op 'n nuwe wending in die veld van multi-doelwit optimering, naamlik die gebruik van die kruisentropie metode om multi-doelwit probleme op te los. Die dokument verskaf 'n bre e oorsig oor die twee velde { multi-doelwit optimering en die kruis-entropie-metode { deur kortliks te kyk na die beskikbare literatuur, basiese beginsels, toepassingsareas en metodes. Die toepassing van die metode op twee onafhanklike probleme word dan ondersoek. Die eerste toepassing is di e van die multi-doelwit voertuigroeteringsprobleem met plooibare tydvensters. Die probleem word eers wiskundig modelleer met 'n oorgangswaarskynlikheidsmatriks. Die matriks word dan deur kruis-entropie beginsels opdateer voor dit konvergeer na 'n benaderingsfront van oplossings. Die oplossingsruimte is onderwerp aan heelwat beperkings, maar die probleem is suksesvol modelleer en die optimeringsalgoritme is gevolglik toegepas op 'n stel verwysingsprobleme. Die navorsing het gevind dat die kruis-entropie metode vir multi-doelwit optimering 'n geldige metode is om 'n uitvoerbare front van oplossings te beraam. Die tweede toepassing is op 'n gevallestudie van die bestuur van bloed binne die konteks van die Westelike Provinsie Bloedoortappingsdiens. Na aanleiding van onderhoude met die relevante belanghebbers is 'n konsepmodel geskep voor 'n simulasiemodel van die stelsel gebou is. Die kruis-entropie metode is gebruik om die voorraadbeleid van die stelsel te optimeer deur 'n gesamentlike diensvlak van die stelsel te maksimeer en terselfdetyd die totale reis-afstand te minimeer. Deur die optimerings- en simulasiemodel te integreer, wys die studie dat die voorraadbeleid van die diens aansienlik kan verbeter, en dat die kruis-entropie algoritme in staat is om na 'n front van oplossings te beweeg. Die navorsing bewys die merkwaardige wydte en eenvoud van moontlike toepassings van die kruis-entropie algoritme vir multidoelwit optimering, terwyl dit 'n bydrae lewer tot die afsonderlike velde van voertuigroetering en die bestuur van bloed. Uitslae vir die verwysingsprobleme van die voertuigroeteringsprobleem met plooibare tydvensters word verskaf en 'n verbeterde voorraadbeleid word aan die Westelike Provinsie Bloedoortappingsdiens voorgestel.

Thesis (PhD)--Stellenbosch University, 2012. / 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.

Information theoretical measures are used to design, from first principles, an objective function that can drive a learning machine process to a solution that is robust to perturbations in parameters. Full analytic derivations are given and tested with computational examples showing that indeed the procedure is successful. The final solution, implemented by a robust learning machine, expresses a balance between Shannon differential entropy and Fisher information. This is also surprising in being an analytical relation, given the purely numerical operations of the learning machine.

Os Sistemas de Distribuição são responsáveis pelo fornecimento da energia elétrica aos consumidores residenciais, industriais e comerciais com padrões de qualidade regulamentados pela Agência Nacional de Energia Elétrica (ANEEL). Assim, as concessionárias monitoram seu sistema para verificar o perfil de tensão na rede elétrica e as perdas técnicas do sistema. Este último critério de desempenho é extremamente relevante, pois representa o desperdício em energia e diminuição na capacidade de receita da empresa. Portanto, há interesse em fornecer a energia elétrica dentro das especificações regidas pela ANEEL e com as menores perdas elétricas possível. Contudo, técnicas como reconfiguração de linhas, recondutoramento, alocação de capacitores e geradores distribuídos são aplicadas. Em especial, a alocação de capacitores é uma técnica que visa identificar a quantidade, localização e tipo dos bancos de capacitores (BCs) que serão alocados no sistema com o intuito de minimizar as perdas, levando em consideração custos de implantação e operação. Para tal, métodos computacionais são utilizados para definir a melhor configuração dos BCs. As metaheurítiscas têm sido aplicadas na solução deste problema, cuja função objetivo é a minimização das perdas técnicas do sistema de distribuição. Desta forma, este trabalho tem o objetivo de propor uma abordagem de solução utilizando a metaheurística Entropia Cruzada implementada no software Python para redução das perdas de sistemas elétricos modelados no OpenDSS. A abordagem se mostrou uma importante ferramenta de análise de sistemas de distribuição, proporcionando resultados extremamente satisfatórios. / The distribution systems are responsible for providing electricity to residential, industrial and commercial consumers under quality standards regulated by the National Electric Energy Agency (ANEEL). Thus, utilities monitor the system to check the voltage profile in the grid and system technical losses. The latter quantity is an extremely important performance criterion, as it represents energy losses and decrease in revenue capacity of the company. Therefore, there is interest in providing electricity within specification stated by ANEEL with the lowest possible electrical losses. Techniques such as topology reconfiguration, reconductoring, allocation of capacitors and distributed generators are usually proposed in technical studies. Particularly, the allocation of capacitors is a technique that aims to identify the amount, location and type of capacitor banks (CBs), which are allocated in the system in order to minimize the losses, taking into consideration the implementation and operation costs. For this purpose, computational methods are used to determine the best configuration of CBs. Metaheuristics have been applied for the solution of this problem, with the objective to minimize the technical losses of distribution systems. This document shows the development of a solution method using the Cross Entropy metaheuristic implemented in Python programming language to reduce the losses of electrical systems modeled in OpenDSS program. The developed approach resulted in an important analysis tool for distribution systems, providing extremely satisfactory results.