Thesis (MSc (Mathematical Sciences))--Stellenbosch University, 2008. / In this thesis we consider the modelling of a particular layout optimisation problem, namely, the LEGO construction problem. The LEGO construction problem, in short, concerns the optimal layout of a set of LEGO bricks to represent a given object. Our goal is to develop a software package which LEGO enthusiasts can use to construct LEGO sculptures for any real-world object. We therefore not only consider the layout optimisation problem, but also the generation of the input data required by the LEGO construction problem. We show that by using 3D geometric models to represent the real-world object, our implemented voxelisation technique delivers accurate input data for the LEGO construction problem. The LEGO construction problem has previously been solved with optimisation techniques based on simulated annealing, evolutionary algorithms, and a beam search approach. These techniques all indicate that it is possible to generate LEGO building instructions for real-world objects, albeit not necessarily in reasonable time. We show that the LEGO construction problem can be modelled easily with cellular automata, provided that cells are considered as clusters which can merge or split during each time step of the evolution of the cellular automaton. We show that the use of cellular automata gives comparable layout results in general, and improves the results in many respects. The cellular automata method requires substantially less memory and generally uses fewer LEGO bricks to construct the LEGO sculpture when using comparable execution times.

Thesis (MSc)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: see full text for abstract / AFRIKAANSE OPSOMMING: sien volteks vir opsomming

Thesis (MSc (Mathematical Sciences)--University of Stellenbosch, 2010. / ENGLISH ABSTRACT: Binary Decision Diagrams (BDDs) are data structures that have been used to solve various problems in different aspects of computer aided design and formal verification. The large memory and time requirements of BDD applications are the major constraints that usually prevent the use of BDDs since there is a limited amount of memory available on a machine. One way of overcoming this resource limitation problem is to utilize the memory available on a network of workstations (NOW). This requires the distribution of the computation and memory requirements involved in the manipulation of BDDs over a NOW. In this thesis, an algorithm for manipulating BDDs on a NOW is presented. The algorithm makes use of the breadth-first technique to manipulate BDDs so that various BDD operations can be started concurrently on the different workstations on the NOW. The design and implementation details of the distributed BDD package are described. The various approaches considered in order to optimize the performance of the algorithm are also discussed. Experimental results demonstrating the performance and capabilities of the distributed package and the benefits of the different optimization approaches are given. / AFRIKAANSE OPSOMMING: Binêre besluitnemingsbome (BBBs) is data strukture wat gebruik word om probleme in verskillende areas van Rekenaarwetenskap, soos by voorbeeld rekenaargesteunde ontwerp en formele verifikasie, op te los. Die tyd- en spasiekoste van BBB-gebaseerde toepassings is die hoofrede waarom BBBs nie altyd gebruik kan word nie; die geheue van ’n enkele is ongelukkig te beperkend. Een manier om hierdie hulpbronprobleem te omseil, is om die gedeelde geheue van die werkstasies in ’n netwerk van werkstasies (Engels: “network of workstations”, oftewel, ’n NOW) te benut. Dit is dus nodig om die berekening en geheuevoorvereistes van die BBB bewerking oor die NOW te versprei. Hierdie tesis bied ’n algoritme aan om BBBs op ’n NOW te hanteer. Die algoritme gebruik die breedte-eerste soektegniek, sodat BBB operasies gelyklopend kan uitvoer. Die details van die ontwerp en implementasie van die verspreide BBB bilbioteek word beskryf. Verskeie benaderings om die gedrag van die biblioteek te optimeer word ook aangespreek. Empiriese resultate wat die werkverrigting en kapasiteit van die biblioteek meet, en wat die uitwerking van die onderskeie optimerings aantoon, word verskaf.

Thesis (MSc)--Stellenbosch University, 2004. / ENGLISH ABSTRACT: It is possible to improve on the accuracy of a single neural network by using an ensemble of diverse and accurate networks. This thesis explores diversity in ensembles and looks at the underlying theory and mechanisms employed to generate and combine ensemble members. Bagging and boosting are studied in detail and I explain their success in terms of well-known theoretical instruments. An empirical evaluation of their performance is conducted and I compare them to a single classifier and to each other in terms of accuracy and diversity. / AFRIKAANSE OPSOMMING: Dit is moontlik om op die akkuraatheid van 'n enkele neurale netwerk te verbeter deur 'n ensemble van diverse en akkurate netwerke te gebruik. Hierdie tesis ondersoek diversiteit in ensembles, asook die meganismes waardeur lede van 'n ensemble geskep en gekombineer kan word. Die algoritmes "bagging" en "boosting" word in diepte bestudeer en hulle sukses word aan die hand van bekende teoretiese instrumente verduidelik. Die prestasie van hierdie twee algoritmes word eksperimenteel gemeet en hulle akkuraatheid en diversiteit word met 'n enkele netwerk vergelyk.

Thesis (MSc) -- Stellenbosch University, 2004. / ENGLISH ABSTRACT: The Internet is fast evolving into a commercial platform that carries a mixture of narrow- and broadband applications such as voice, video, and data. Users expect a certain level of guaranteed service from their service providers and consequently the need exists for efficient Internet traffic engineering to enable better Quality of Service (QoS) capabilities. Multi-protocol Label Switching (MPLS) is a label switching protocol that has emerged as an enabling technology to achieve efficient traffic engineering for QoS management in IP networks. The ability of the MPLS protocol to create explicit virtual connections called Label Switched Paths (LSPs) to carry network traffic significantly enhances the traffic engineering capabilities of communication networks. The MPLS protocol supports two options for explicit LSP selection: offline LSP computation using an optimization method and dynamic route selection where a single node makes use of current available network state information in order to compute an explicit LSP online. This thesis investigates various methods for the selection of explicit bandwidth guaranteed LSPs through dynamic route selection. We address the problem of computing a sequence of optimal LSPs where each LSP can carry a specific traffic demand and we assume that no prior information regarding the future traffic demands are available and that the arrival sequence of LSP requests to the network is unknown. Furthermore, we investigate the rerouting abilities of the online LSP selection methods to perform MPLS failure restoration upon link failure. We propose a new online routing framework known as Least Interference Optimization (LIO) that utilizes the current bandwidth availability and traffic flow distribution to achieve efficient traffic engineering. We present the Least Interference Optimization Algorithm (LIOA) that reduces the interference among competing network flows by balancing the number and quantity of flows carried by a link for the setup of bandwidth guaranteed LSPs in MPLS networks. The LIOA routing strategy is evaluated and compared against well-known routing strategies such as the Minimum Hop Algorithm (MHA), Minimum Interference Routing Algorithm (MIRA), Open Shortest Path First (OSPF) and Constraint Shortest Path First (CSPF) by means of simulation. Simulation results revealed that, for the network topologies under consideration, the routing strategies that employed dynamic network state information in their routing decisions (LIOA, CSPF and MIRA) generally outperformed the routing strategies that only rely on static network information (OSPF and MHA). In most simulation experiments the best performance was achieved by the LIOA routing strategy while the MHA performed the worse. Furthermore we observed that the computational complexity of the MIRA routing strategy does not translate into equivalent performance gains. We employed the online routing strategies for MPLS failure recovery upon link failure. In particular we investigated two aspects to determine the efficiency of the routing strategies for MPLS rerouting: the suitability of the LSP configuration that results due to the establishment of LSPs prior to link failure and the ability of the online routing strategy to reroute failed LSPs upon link failure. Simulation results revealed similar rerouting performance for all online routing strategies under investigation, but a LSP configuration most suitable for online rerouting was observed for the LIOA routing strategy. / AFRIKAANSE OPSOMMING:Die Internet is voordurend besig om te evoleer in 'n medium wat 'n wye reeks moderne kommunikasietegnologiee ondersteun, insluitende telefoon, video en data. Internet gebruikers verwag gewaarborgde diens van hul diensverskaffers en daar bestaan dus 'n vraag na doeltreffende televerkeerbeheer vir gewaarborgde Internet diensgehalte. Multiprotokol Etiketskakeling (MPLS) is 'n etiketskakeling protokol wat doeltreffende televerkeerbeheer en diensgehalte moontlik maak deur die eksplisiete seleksie van virtuele konneksies vir die transmissie van netwerkverkeer in Internetprotokol (IP) netwerke. Hierdie virtuele konneksies staan bekend as etiketgeskakelde paaie. Die MPLS protokol ondersteun tans twee moontlikhede vir eksplisiete seleksie van etiketgeskakelde paaie: aflyn padberekening met behulp van optimeringsmetodes en dinamiese aanlyn padseleksie waar 'n gekose node 'n eksplisiete pad bereken deur die huidige stand van die netwerk in ag te neem. In hierdie tesis word verskeie padseleksiemetodes vir die seleksie van eksplisiete bandwydte-gewaarborgde etiketgeskakelde paaie deur mid del van dinamiese padseleksie ondersoek. Die probleem om 'n reeks optimale etiketgeskakelde paaie te bereken wat elk 'n gespesifeerde verkeersaanvraag kan akkommodeer word aangespreek. Daar word aanvaar dat geen informasie in verband met die toekomstige verkeersaanvraag bekend is nie en dat die aankomsvolgorde van etiketgeskakelde pad verso eke onbekend is. Ons ondersoek verder die herroeteringsmoontlikhede van die aanlyn padseleksiemetodes vir MPLS foutrestorasie in die geval van skakelonderbreking. Vir hierdie doel word 'n nuwe aanlyn roeteringsraamwerk naamlik Laagste Inwerking Optimering (LIO) voorgestel. LIO benut die huidige beskikbare bandwydte en verkeersvloeidistribusie van die netwerk om doeltreffende televerkeerbeheer moontlik te maak. Ons beskryf 'n Laagste Inwerking Optimering Algoritme (LIOA) wat die inwerking tussen kompeterende verkeersvloei verminder deur 'n balans te handhaaf tussen die aantal en kwantiteit van die verkeersvloeistrome wat gedra word deur elke netwerkskakel. Die LIOA roeteringstrategie word geevalueer met behulp van simulasie en die resultate word vergelyk met ander bekende roeteringstrategiee insluitende die Minimum Node Algorithme (MHA), die Minimum Inwerking Algoritme (MIRA), die Wydste Kortste Pad Eerste Algoritme (OSPF) en die Beperkte Kortste Pad Eerste Algoritme (CSPF). Die resultate van die simulasie-eksperimente to on dat, vir die netwerk topologiee onder eksperimentasie, die roeteringstratgiee wat roeteringsbesluite op dinamiese netwerk informasie baseer (LIOA, MIRA, CSPF) oor die algemeen beter vaar as die wat slegs staatmaak op statiese netwerkinformasie (MHA, OSPF). In die meeste simulasie-eksperimente vaar die LIOA roeteringstrategie die beste en die MHA roeteringstrategie die slegste. Daar word verder waargeneem dat die komputasiekomplesiteit van die MIRA roeteringstrategie nie noodwendig weerspieel word in die sukses van roeteringsuitkoms nie. In die geval waar die aanlyn roeteringstrategiee aangewend word vir MPLS foutrestorasie, toon die resultate van simulasie-eksperimente dat al die roeteringstrategiee min of meer dieselfde uitkoms lewer ten opsigte van herroetering van onderbreekte verkeersvloei. Die konfigurasie van etiketgeskakelde paaie deur die LIOA roeteringstrategie voor skakelonderbreking is egter die geskikste vir televerkeer herroetering na skakelonderbreking

Thesis (MSc)--Stellenbosch University, 2002. / ENGLISH ABSTRACT: The Internet is evolving into a commercial platform requiring enhanced protocols and an expanded physical infrastructure allowing a better delivery from IP. Multi-protocol Label Switching (MPLS) is a technology enabling traffic engineering and virtual private network (VPN) provisioning. MPLS achieves traffic engineering by carrying the traffic over virtual connections called Label Switched Paths (LSPs) which are engineered based on QoS requirements such as delay, jitter and packet loss minimization or throughput maximization. This thesis proposes path finding and traffic distribution methods to be deployed in MPLS networks for traffic engineering LSPs. A flow optimization model based on a pre-planned routing approach separating path finding and traffic distribution is presented. This model is augmented by a threshold routing approach which routes the traffic based on thresholds expressing the maximum load level reached by network links. This routing approach moves the traffic away from thresholdmarked links to achieve low-utilized links/paths. The performance and routing capabilities of these methods are evaluated through designed software. A routing architecture implementing a two-layer signalling model for MPLS network is proposed and evaluated through simulation. v / AFRIKAANSE OPSOMMING:Die verandering van die Internet in 'n kommersiele platform met verbeterde protokolle en 'n uitgebreide fisieke infrastruktuur stel die internetprotokol (IP) in staat tot beter lewering. Multiprotokol- etiketskakeling (MPLS), is 'n tegnologie vir die voorsiening van televerkeerbeheer en virtuele privaatnetwerke (VPN). MPLS verskaf televerkeerbeheer deur die verkeer te dra oar virtuele konneksies, wat bekend staan as etiketgeskakelde paaie, waarvan die ontwerp gebaseer is op vereistes vir diensgehalte soos vertraging, ritteling en die minimering van pakketverlies of maksimering van deurvoer. Hierdie tesis stel nuwe padvind- en verkeerdistribusiemetodes voor wat aangewend word in MPLSnetwerke om etiketgeskakelde paaie te beheer. 'n Model vir vloei-optimering-gebaseer op voorafbeplande roetering wat padvinding en verkeerdistribusie skei-word aangebied. Hierdie model word uitgebrei deur 'n benadering van drempelroetering wat die verkeer roeteer en gebaseer is op drempels wat die maksimum ladingsvlak voorstel wat bereik kan word deur netwerkskakels. Hierdie roeteringsbenadering skuif die verkeer weg van drempelgemerkte skakels en bereik daardeur laaggebruikte skakelsjpaaie. Die prestasie en roeteringsvaardigheid van hierdie metodes word gevalueer deur selfontwikkelde programmatuur. 'n Argitektuur vir roetering wat 'n dubbellaagseinmodel implementeer vir 'n MPLS-netwerk, word aangebied en gevalueer met simulasie.

Thesis (MSc) -- Stellenbosch University , 2003. / ENGLISH ABSTRACT: The integration of symbolic knowledge with artificial neural networks is becoming an increasingly popular paradigm for solving real-world problems. This paradigm named knowledge-based neurocomputing, provides means for using prior knowledge to determine the network architecture, to program a subset of weights to induce a learning bias which guides network training, and to extract refined knowledge from trained neural networks. The role of neural networks then becomes that of knowledge refinement. It thus provides a methodology for dealing with uncertainty in the initial domain theory. In this thesis, we address several advantages of this paradigm and propose a solution for the open question of determining the strength of this learning, or inductive, bias. We develop a heuristic for determining the strength of the inductive bias that takes the network architecture, the prior knowledge, the learning method, and the training data into consideration. We apply this heuristic to well-known synthetic problems as well as published difficult real-world problems in the domain of molecular biology and medical diagnoses. We found that, not only do the networks trained with this adaptive inductive bias show superior performance over networks trained with the standard method of determining the strength of the inductive bias, but that the extracted refined knowledge from these trained networks deliver more concise and accurate domain theories. / AFRIKAANSE OPSOMMING: Die integrasie van simboliese kennis met kunsmatige neurale netwerke word 'n toenemende gewilde paradigma om reelewereldse probleme op te los. Hierdie paradigma genoem, kennis-gebaseerde neurokomputasie, verskaf die vermoe om vooraf kennis te gebruik om die netwerkargitektuur te bepaal, om a subversameling van gewigte te programeer om 'n leersydigheid te induseer wat netwerkopleiding lei, en om verfynde kennis van geleerde netwerke te kan ontsluit. Die rol van neurale netwerke word dan die van kennisverfyning. Dit verskaf dus 'n metodologie vir die behandeling van onsekerheid in die aanvangsdomeinteorie. In hierdie tesis adresseer ons verskeie voordele wat bevat is in hierdie paradigma en stel ons 'n oplossing voor vir die oop vraag om die gewig van hierdie leer-, of induktiewe sydigheid te bepaal. Ons ontwikkel 'n heuristiek vir die bepaling van die induktiewe sydigheid wat die netwerkargitektuur, die aanvangskennis, die leermetode, en die data vir die leer proses in ag neem. Ons pas hierdie heuristiek toe op bekende sintetiese probleme so weI as op gepubliseerde moeilike reelewereldse probleme in die gebied van molekulere biologie en mediese diagnostiek. Ons bevind dat, nie alleenlik vertoon die netwerke wat geleer is met die adaptiewe induktiewe sydigheid superieure verrigting bo die netwerke wat geleer is met die standaardmetode om die gewig van die induktiewe sydigheid te bepaal nie, maar ook dat die verfynde kennis wat ontsluit is uit hierdie geleerde netwerke meer bondige en akkurate domeinteorie lewer.

Thesis (MscEng)--Stellenbosch University, 2003. / ENGLISH ABSTRACT: Outliers may be defined as observations that are sufficiently aberrant to arouse the suspicion of the analyst as to their origin. They could be the result of human error, in which case they should be corrected, but they may also be an interesting exception, and this would deserve further investigation. Identification of outliers typically consists of an informal inspection of a plot of the data, but this is unreliable for dimensions greater than two. A formal procedure for detecting outliers allows for consistency when classifying observations. It also enables one to automate the detection of outliers by using computers. The special case of univariate data is treated separately to introduce essential concepts, and also because it may well be of interest in its own right. We then consider techniques used for detecting multiple outliers in a multivariate normal sample, and go on to explain how these may be generalized to include cluster analysis. Multivariate outlier detection is based on the Minimum Covariance Determinant (MCD) subset, and is therefore treated in detail. Exact bivariate algorithms were refined and implemented, and the solutions were used to establish the performance of the commonly used heuristic, Fast–MCD. / AFRIKAANSE OPSOMMING: Uitskieters word gedefinieer as waarnemings wat tot s´o ’n mate afwyk van die verwagte gedrag dat die analis wantrouig is oor die oorsprong daarvan. Hierdie waarnemings mag die resultaat wees van menslike foute, in welke geval dit reggestel moet word. Dit mag egter ook ’n interressante verskynsel wees wat verdere ondersoek benodig. Die identifikasie van uitskieters word tipies informeel deur inspeksie vanaf ’n grafiese voorstelling van die data uitgevoer, maar hierdie benadering is onbetroubaar vir dimensies groter as twee. ’n Formele prosedure vir die bepaling van uitskieters sal meer konsekwente klassifisering van steekproefdata tot gevolg hˆe. Dit gee ook geleentheid vir effektiewe rekenaar implementering van die tegnieke. Aanvanklik word die spesiale geval van eenveranderlike data behandel om noodsaaklike begrippe bekend te stel, maar ook aangesien dit in eie reg ’n area van groot belang is. Verder word tegnieke vir die identifikasie van verskeie uitskieters in meerveranderlike, normaal verspreide data beskou. Daar word ook ondersoek hoe hierdie idees veralgemeen kan word om tros analise in te sluit. Die sogenaamde Minimum Covariance Determinant (MCD) subversameling is fundamenteel vir die identifikasie van meerveranderlike uitskieters, en word daarom in detail ondersoek. Deterministiese tweeveranderlike algoritmes is verfyn en ge¨ımplementeer, en gebruik om die effektiwiteit van die algemeen gebruikte heuristiese algoritme, Fast–MCD, te ondersoek.

Thesis (MSc)--Stellenbosch University, 2003. / ENGLISH ABSTRACT: Routing policies for packet-switched communication networks must be able to adapt to changing traffic patterns and topologies. We study the feasibility of implementing an adaptive routing policy using the Q-Learning algorithm which learns sequences of actions from delayed rewards. The Q-Routing algorithm adapts a network's routing policy based on local information alone and converges toward an optimal solution. We demonstrate that Q-Routing is a viable alternative to other adaptive routing methods such as Bellman-Ford. We also study variations of Q-Routing designed to better explore possible routes and to take into consideration limited buffer size and optimize multiple objectives. / AFRIKAANSE OPSOMMING:Die roetering in kommunikasienetwerke moet kan aanpas by veranderings in netwerktopologie en verkeersverspreidings. Ons bestudeer die bruikbaarheid van 'n aanpasbare roeteringsalgoritme gebaseer op die "Q-Learning"-algoritme wat dit moontlik maak om 'n reeks besluite te kan neem gebaseer op vertraagde vergoedings. Die roeteringsalgoritme gebruik slegs nabygelee inligting om roeteringsbesluite te maak en konvergeer na 'n optimale oplossing. Ons demonstreer dat die roeteringsalgoritme 'n goeie alternatief vir aanpasbare roetering is, aangesien dit in baie opsigte beter vaar as die Bellman-Ford algoritme. Ons bestudeer ook variasies van die roeteringsalgoritme wat beter paaie kan ontdek, minder geheue gebruik by netwerkelemente, en wat meer as een doelfunksie kan optimeer.

Thesis (MSc)--Stellenbosch University, 2003. / ENGLISH ABSTRACT: The Internet has experienced tremendous growth in the last three decades and has emerged as a platform to carryall forms of communications including voice, video and data. Along with this growth came the urgency for quality of service (QoS) controls in IP networks as different types of traffics have different service requirements. Although the IP protocol is able to scale to very large networks, it does not provide sufficient functionality for traffic engineering in order to enable QoS control. Multi-protocol label switching (MPLS) is a new routing technology that enhances IP with some QoS concepts from ATM and uses relatively simple packet forwarding mechanisms. MPLS has the ability to perform traffic engineering and QoS control by routing traffic flowson virtual connections called label switched paths (LSPs) which are assigned capacity. A large portion of the traffic carried on the Internet consists of data traffic in the form of TCP traffic. This thesis investigates several TCP models to find the ones most suitable to represent TCP traffic in MPLS networks. The models consist of three types. The first type models a single TCP source and the second type models a fixed number of TCP sources. The third type models an infinite number of TCP sources. The models were evaluated by comparing their throughput predictions and results obtained from simulation experiments that were done with the widely-used simulator ns. We also present a simple derivation of the 1/,;e law for the TCP congestion window size where e is the packet loss probability. / AFRIKAANSE OPSOMMING:In die afgelope drie dekades het die Internet beduidende groei ervaar, soveel so dat dit ontluik het as 'n medium om alle tipes van moderne kommunikasies te hanteer insluitend telefoon, video en data. Hierdie groei het gepaard gegaan met die behoefte na diensvlak (QoS) meganismes in IP netwerke aangesien verskillende tipe kommunikasies verskillende diens vereistes het. Alhoewel die IP protokol skalleerbaar is tot baie groot netwerke, voorsien dit nie voldoende funksionaliteit om QoS beheer toe te pas nie. "Multi-protocol label switching" (MPLS) is 'n nuwe roeterings tegnologie wat IP aanvul met QoS konsepte van ATM en dit maak gebruik van relatief eenvoudige pakkie versendings-meganismes. MPLS het die vermoe om netwerk-verkeer reeling en QoS beheer toe te pas deur verkeers-strome te roeteer op virtuele roetes genaamd "label switched paths" (LSPs) aan wie kapasiteit toegeken is. 'n Beduidende gedeelte van Internet-verkeer bestaan uit TCP-verkeer. Hierdie tesis ondersoek verskillende modelle van TCP om die te vind wat die mees geskik is om TCP verkeer in MPLS netwerke te verteenwoordig. Drie tipes modelle is ondersoek. Die eerste tipe moduleer 'n enkele TCP verkeersbron en die tweede tipe moduleer 'n vasgestelde aantal TCP verkeersbronne. Die derde tipe moduleer 'n oneindige aantal verkeersbronne. Die modelle is geevalueer deur hul voorspellings van die tempo van data transmissie te vergelyk met resultate van simulasies. Die simulasies is gedoen met die veelgebruikte simulator ns. Hierdie tesis bevat ook 'n eenvoudige afleiding vir die 1/,;e wet vir die TCP oorlading venster grootte met e die verlies waarskeinlikheid van 'n netwerk pakkie.