Production scheduling is one of the most important issues in the planning and operation of manufacturing systems. Customers increasingly expect to receive the right product at the right price at the right time. Various problems experienced in manufacturing, for example low machine utilization and excessive work-in-process, can be attributed directly to inadequate scheduling. In this dissertation a production scheduling algorithm is developed for Optimatix, a South African-based company specializing in supply chain optimization. To address the complex requirements of the customer, the problem was modeled as a flexible job shop scheduling problem with sequence-dependent set-up times, auxiliary resources and production down time. The algorithm development process focused on investigating the application of both particle swarm optimization (PSO) and differential evolution (DE) to production scheduling environments characterized by multiple machines and multiple objectives. Alternative problem representations, algorithm variations and multi-objective optimization strategies were evaluated to obtain an algorithm which performs well against both existing rule-based algorithms and an existing complex flexible job shop scheduling solution strategy. Finally, the generality of the priority-based algorithm was evaluated by applying it to the scheduling of production and maintenance activities at Centurion Ice Cream and Sweets. The production environment was modeled as a multi-objective uniform parallel machine shop problem with sequence-dependent set-up times and unavailability intervals. A self-adaptive modified vector evaluated DE algorithm was developed and compared to classical PSO and DE vector evaluated algorithms. Promising results were obtained with respect to the suitability of the algorithms for solving a range of multi-objective multiple machine scheduling problems. Copyright / Dissertation (MEng)--University of Pretoria, 2009. / Industrial and Systems Engineering / unrestricted

This thesis is primarily concerned with a description of four types of stochastic algorithms, namely the genetic algorithm, the continuous parameter genetic algorithm, the particle swarm algorithm and the differential evolution algorithm. Each of these techniques is presented in sufficient detail to allow the layman to develop her own program upon examining the text. All four algorithms are applied to the optimization of a certain set of unconstrained problems known as the extended Dixon-Szegö test set. An algorithm's performance at optimizing a set of problems such as these is often used as a benchmark for judging its efficacy. Although the same thing is done here, an argument is presented that shows that no such general benchmarking is possible. Indeed, it is asserted that drawing general comparisons between stochastic algorithms on the basis of any performance criterion is a meaningless pursuit unless the scope of such comparative statements is limited to specific sets of optimization problems. The idea is a result of the no free lunch theorems proposed by Wolpert and Macready. Two methods of presenting the results of an optimization run are discussed. They are used to show that judging an optimizer's performance is largely a subjective undertaking, despite the apparently objective performance measures which are commonly used when results are published. An important theme of this thesis is the observation that a simple paradigm shift can result in a different decision regarding which algorithm is best suited to a certain task. Hence, an effort is made to present the proper interpretation of the results of such tests (from the author's point of view). Additionally, the four abovementioned algorithms are used in a modelling environment designed to determine the structure of a Magnetic Cataclysmic Variable. This 'real world' modelling problem contrasts starkly with the well defined test set and highlights some of the issues that designers must face in the optimization of physical systems. The particle swarm optimizer will be shown to be the algorithm capable of achieving the best results for this modelling problem if an unbiased <font face="symbol">c</font>2 performance measure is used. However, the solution it generates is clearly not physically acceptable. Even though this drawback is not directly attributable to the optimizer, it is at least indicative of the fact that there are practical considerations which complicate the issue of algorithm selection. / Dissertation (MEng (Mechanical Engineering))--University of Pretoria, 2006. / Mechanical and Aeronautical Engineering / unrestricted

Temporal data is common in real-world datasets. Analysis of such data, for example by means of clustering algorithms, can be difficult due to its dynamic behaviour. There are various types of changes that may occur to clusters in a dataset. Firstly, data patterns can migrate between clusters, shrinking or expanding the clusters. Additionally, entire clusters may move around the search space. Lastly, clusters can split and merge. Data clustering, which is the process of grouping similar objects, is one approach to determine relationships among data patterns, but data clustering approaches can face limitations when applied to temporal data, such as difficulty tracking the moving clusters. This research aims to analyse the ability of particle swarm optimisation (PSO) and differential evolution (DE) algorithms to cluster temporal data. These algorithms experience two weaknesses when applied to temporal data. The first weakness is the loss of diversity, which refers to the fact that the population of the algorithm converges, becoming less diverse and, therefore, limiting the algorithm’s exploration capabilities. The second weakness, outdated memory, is only experienced by the PSO and refers to the previous personal best solutions found by the particles becoming obsolete as the environment changes. A data clustering algorithm that addresses these two weaknesses is necessary to cluster temporal data. This research describes various adaptations of PSO and DE algorithms for the purpose of clustering temporal data. The algorithms proposed aim to address the loss of diversity and outdated memory problems experienced by PSO and DE algorithms. These problems are addressed by combining approaches previously used for the purpose of dealing with temporal or dynamic data, such as repulsion and anti-convergence, with PSO and DE approaches used to cluster data. Six PSO algorithms are introduced in this research, namely the data clustering particle swarm optimisation (DCPSO), reinitialising data clustering particle swarm optimisation (RDCPSO), cooperative data clustering particle swarm optimisation (CDCPSO), multi-swarm data clustering particle swarm optimisation (MDCPSO), cooperative multi-swarm data clustering particle swarm optimisation (CMDCPSO), and elitist cooperative multi-swarm data clustering particle swarm optimisation (eCMDCPSO). Additionally, four DE algorithms are introduced, namely the data clustering differential evolution (DCDE), re-initialising data clustering differential evolution (RDCDE), dynamic data clustering differential evolution (DCDynDE), and cooperative dynamic data clustering differential evolution (CDCDynDE). The PSO and DE algorithms introduced require prior knowledge of the total number of clusters in the dataset. The total number of clusters in a real-world dataset, however, is not always known. For this reason, the best performing PSO and best performing DE are compared. The CDCDynDE is selected as the winning algorithm, which is then adapted to determine the optimal number of clusters dynamically. The resulting algorithm is the k-independent cooperative data clustering differential evolution (KCDCDynDE) algorithm, which was compared against the local network neighbourhood artificial immune system (LNNAIS) algorithm, which is an artificial immune system (AIS) designed to cluster temporal data and determine the total number of clusters dynamically. It was determined that the KCDCDynDE performed the clustering task well for problems with frequently changing data, high-dimensions, and pattern and cluster data migration types. / Dissertation (MSc)--University of Pretoria, 2015. / Computer Science / Unrestricted

The work presented here is a continuation of Spacecraft Trajectory Optimization Suite (STOpS), a master’s thesis written by Timothy Fitzgerald at California Polytechnic State University, San Luis Obispo. Low-thrust spacecraft engines are becoming much more common due to their high efficiency, especially for interplanetary trajectories. The version of STOpS presented here optimizes low-thrust trajectories using the Island Model Paradigm with three stochastic evolutionary algorithms: the genetic algorithm, differential evolution, and particle swarm optimization. While the algorithms used here were designed for the original STOpS, they were modified for this work. The low-thrust STOpS was successfully validated with two trajectory problems and their known near-optimal solutions. The first verification case was a constant-thrust, variable-time Earth orbit to Mars orbit transfer where the thrust was 3.787 Newtons and the time was approximately 195 days. The second verification case was a variable-thrust, constant-time Earth orbit to Mercury orbit transfer with the thrust coming from a solar electric propulsion model equation and the time being 355 days. Low-thrust STOpS found similar near-optimal solutions in each case. The final result of this work is a versatile MATLAB tool for optimizing low-thrust interplanetary trajectories.

The task of this thesis was focused on comparison selected evolutionary algorithms for their success and computing needs. The paper discussed the basic principles and concepts of evolutionary algorithms used for optimization problems. Author programmed selected evolutionary algorithms and subsequently tasted on various test functions with exactly the given input conditions. Finally the algorithms were compared and evaluated the results obtained for different settings.

Many real world problems in science and engineering can be treated as optimization problems with multiple objectives or criteria. The demand for fast and robust stochastic algorithms to cater to the optimization needs is very high. When the cost function for the problem is nonlinear and non-differentiable, direct search approaches are the methods of choice. Many such approaches use the greedy criterion, which is based on accepting the new parameter vector only if it reduces the value of the cost function. This could result in fast convergence, but also in misconvergence where it could lead the vectors to get trapped in local minima. Inherently, parallel search techniques have more exploratory power. These techniques discourage premature convergence and consequently, there are some candidate solution vectors which do not converge to the global minimum solution at any point of time. Rather, they constantly explore the whole search space for other possible solutions. In this thesis, we concentrate on benchmarking three popular algorithms: Real-valued Genetic Algorithm (RGA), Particle Swarm Optimization (PSO), and Differential Evolution (DE). The DE algorithm is found to out-perform the other algorithms in fast convergence and in attaining low-cost function values. The DE algorithm is selected and used to build a model for forecasting auroral oval boundaries during a solar storm event. This is compared against an established model by Feldstein and Starkov. As an extended study, the ability of the DE is further put into test in another example of a nonlinear system study, by using it to study and design phase-locked loop circuits. In particular, the algorithm is used to obtain circuit parameters when frequency steps are applied at the input at particular instances.

No description available.

Trading contracts with future commitments requires posting a collateral, called initial margin requirement, to cover associated risks. Differences in estimating those risks and varying risk appetites can however lead to identical contracts having different initial margin requirements at different market places. This creates a potential for minimizing those requirements by reallocating contracts. The task of minimizing the requirement is identified as a black-box optimization problem with constraints. The aim of this project was to investigate that optimization problem, how it can best be tackled, and comparing different techniques for doing so. Based on the results and obstacles encountered along the way, some guidelines are then outlined to provide assistance for whomever is interested in solving this or similar problems. The project consisted both of a literature study to examine existing knowledge within the subject of optimization, and an implementation phase to empirically test how well that knowledge can be put to use in this case. During the latter various algorithms were tested in a number of different scenarios. Focus was put on practical aspects that could be important in a real situation, such as how much they could decrease the initial margin requirement, execution time, and ease of implementation. As part of the literature study, three algorithms were found which were evaluated further: simulated annealing, differential evolution, and particle swarm optimization. They all work without prior knowledge of the function to be optimized, and are thus suitable for black-box optimization. Results from the implementation part showed largely similar performance between all three algorithms, indicating that other aspects such as ease of implementation or parallelization potential can be more important to consider when choosing which one to use. They were all well able to optimize different portfolios in a number of different cases. However, in more complex situations they required much more time to do so, showing a potential need to speed up the process.

The automatic synthesis of embodied creatures through artificial evolution has become a key area of research in robotics, artificial life and the cognitive sciences. However, the research has mainly focused on genetic encodings and fitness functions. Considerably less has been said about the role of controllers and how they affect the evolution of morphologies and behaviors in artificial creatures. Furthermore, the evolutionary algorithms used to evolve the controllers and morphologies are pre-dominantly based on a single objective or a weighted combination of multiple objectives, and a large majority of the behaviors evolved are for wheeled or abstract artifacts. In this thesis, we present a systematic study of evolving artificial neural network (ANN) controllers for the legged locomotion of embodied organisms. A virtual but physically accurate world is used to simulate the evolution of locomotion behavior in a quadruped creature. An algorithm using a self-adaptive Pareto multi-objective evolutionary optimization approach is developed. The experiments are designed to address five research aims investigating: (1) the search space characteristics associated with four classes of ANNs with different connectivity types, (2) the effect of selection pressure from a self-adaptive Pareto approach on the nature of the locomotion behavior and capacity (VC-dimension) of the ANN controller generated, (3) the effciency of the proposed approach against more conventional methods of evolutionary optimization in terms of computational cost and quality of solutions, (4) a multi-objective approach towards the comparison of evolved creature complexities, (5) the impact of relaxing certain morphological constraints on evolving locomotion controllers. The results showed that: (1) the search space is highly heterogeneous with both rugged and smooth landscape regions, (2) pure reactive controllers not requiring any hidden layer transformations were able to produce sufficiently good legged locomotion, (3) the proposed approach yielded competitive locomotion controllers while requiring significantly less computational cost, (4) multi-objectivity provided a practical and mathematically-founded methodology for comparing the complexities of evolved creatures, (5) co-evolution of morphology and mind produced significantly different creature designs that were able to generate similarly good locomotion behaviors. These findings attest that a Pareto multi-objective paradigm can spawn highly beneficial robotics and virtual reality applications.

Thesis (MScEng)--Stellenbosch University, 2013. / ENGLISH ABSTRACT: In this study we consider the lack of rotational invariance of three different population based optimization methods, namely the particle swarm optimization (PSO) algorithm, the differential evolution (DE) algorithm and the continuous-parameter genetic algorithm (CPGA). We then propose rotationally invariant versions of these algorithms. We start with the PSO. The so-called classical PSO algorithmis known to be variant under rotation, whereas the linear PSO is rotationally invariant. This invariance however, comes at the cost of lack of diversity, which renders the linear PSO inferior to the classical PSO. The previously proposed so-called diverse rotationally invariant (DRI) PSO is an algorithm that aims to combine both diversity and invariance. This algorithm is rotationally invariant in a stochastic sense only. What is more, the formulation depends on the introduction of a random rotation matrix S, but invariance is only guaranteed for ‘small’ rotations in S. Herein, we propose a formulation which is diverse and strictly invariant under rotation, if still in a stochastic sense only. To do so, we depart with the linear PSO, and then we add a self-scaling random vector with a standard normal distribution, sampled uniformly from the surface of a n-dimensional unit sphere. For the DE algorithm, we show that the classic DE/rand/1/bin algorithm, which uses constant mutation and standard crossover, is rotationally variant. We then study a previously proposed rotationally invariant DE formulation in which the crossover operation takes place in an orthogonal base constructed using Gramm-Schmidt orthogonalization. We propose two new formulations by firstly considering a very simple rotationally invariant formulation using constant mutation and whole arithmetic crossover. This rudimentary formulation performs badly, due to lack of diversity. We then introduce diversity into the formulation using two distinctly different strategies. The first adjusts the crossover step by perturbing the direction of the linear combination between the target vector and the mutant vector. This formulation is invariant in a stochastic sense only. We add a self-scaling random vector to the unaltered whole arithmetic crossover vector. This formulation is strictly invariant, if still in a stochastic sense only. In this study we consider the lack of rotational invariance of three different population based optimization methods, namely the particle swarm optimization (PSO) algorithm, the differential evolution (DE) algorithm and the continuous-parameter genetic algorithm (CPGA). We then propose rotationally invariant versions of these algorithms. We start with the PSO. The so-called classical PSO algorithmis known to be variant under rotation, whereas the linear PSO is rotationally invariant. This invariance however, comes at the cost of lack of diversity, which renders the linear PSO inferior to the classical PSO. The previously proposed so-called diverse rotationally invariant (DRI) PSO is an algorithm that aims to combine both diversity and invariance. This algorithm is rotationally invariant in a stochastic sense only. What is more, the formulation depends on the introduction of a random rotation matrix S, but invariance is only guaranteed for ‘small’ rotations in S. Herein, we propose a formulation which is diverse and strictly invariant under rotation, if still in a stochastic sense only. To do so, we depart with the linear PSO, and then we add a self-scaling random vector with a standard normal distribution, sampled uniformly from the surface of a n-dimensional unit sphere. For the DE algorithm, we show that the classic DE/rand/1/bin algorithm, which uses constant mutation and standard crossover, is rotationally variant. We then study a previously proposed rotationally invariant DE formulation in which the crossover operation takes place in an orthogonal base constructed using Gramm-Schmidt orthogonalization. We propose two new formulations by firstly considering a very simple rotationally invariant formulation using constant mutation and whole arithmetic crossover. This rudimentary formulation performs badly, due to lack of diversity. We then introduce diversity into the formulation using two distinctly different strategies. The first adjusts the crossover step by perturbing the direction of the linear combination between the target vector and the mutant vector. This formulation is invariant in a stochastic sense only. We add a self-scaling random vector to the unaltered whole arithmetic crossover vector. This formulation is strictly invariant, if still in a stochastic sense only. For the CPGA we show that a standard CPGA using blend crossover and standard mutation, is rotationally variant. To construct a rotationally invariant CPGA it is possible to modify the crossover operation to be rotationally invariant. This however, again results in loss of diversity. We introduce diversity in two ways: firstly using a modified mutation scheme, and secondly, following the same approach as in the PSO and the DE, by adding a self-scaling random vector to the offspring vector. This formulation is strictly invariant, albeit still in a stochastic sense only. Numerical results are presented for the variant and invariant versions of the respective algorithms. The intention of this study is not the contribution of yet another competitive and/or superior population based algorithm, but rather to present formulations that are both diverse and invariant, in the hope that this will stimulate additional future contributions, since rotational invariance in general is a desirable, salient feature for an optimization algorithm. / AFRIKAANSE OPSOMMING: In hierdie studie bestudeer ons die gebrek aan rotasionele invariansie van drie verskillende populasiegebaseerde optimeringsmetodes, met name die partikel-swerm optimerings (PSO) algoritme, die differensi¨ele evolusie (DE) algoritme en die kontinue-parameter genetiese algoritme (KPGA). Ons stel dan rotasionele invariante weergawes van hierdie algoritmes voor. Ons beginmet die PSO. Die sogenaamde klassieke PSO algoritme is bekend dat dit variant is onder rotasie, terwyl die lineˆere PSO rotasioneel invariant is. Hierdie invariansie lei tot ’n gebrek aan diversiteit in die algoritme, wat beteken dat die lineˆere PSO minder goed presteer as die klassieke PSO. Die voorheen voorgestelde sogenaamde diverse rotasionele invariante (DRI) PSO is ’n algoritme wat beoog om beide diversiteit en invariansie te kombineer. Hierdie algoritme is slegs rotasioneel invariant in ’n stogastiese sin. Boonop is die formulering afhanklik van ’n willekeurige rotasie matriks S, maar invariansie is net gewaarborg vir ’klein’ rotasies in S. In hierdie studie stel ons ’n formulering voor wat divers is en streng invariant onder rotasie, selfs al is dit steeds net in ’n stogastiese sin. In hierdie formulering, vertrek ons met die lineˆere PSO, en voeg dan ’n self-skalerende ewekansige vektor met ’n standaard normaalverdeling by, wat eenvormig van die oppervlakte van ’n n-dimensionele eenheid sfeer geneem word. Vir die DE algoritme toon ons aan dat die klassieke DE/rand/1/bin algoritme, wat gebruik maak van konstante mutasie en standaard kruising rotasioneel variant is. Ons bestudeer dan ’n voorheen voorgestelde rotasionele invarianteDE formulering waarin die kruisingsoperasie plaasvind in ’n ortogonale basis wat gekonstrueer wordmet behulp van die Gramm-Schmidt ortogonalieseringsproses. Verder stel ons dan twee nuwe formulerings voor deur eerstens ’n baie eenvoudige rotasionele invariante formulering te oorweeg, wat konstante mutasie en volledige rekenkundige kruising gebruik. Hierdie elementˆere formulering onderpresteer as gevolg van die afwesigheid van diversiteit. Ons voeg dan diversiteit by die formulering toe, deur gebruik te maak van twee afsonderlike strategie ¨e. Die eerste verander die kruisings stap deur die rigting van die lineˆere kombinasie tussen die teiken vektor en die mutasie vektor te perturbeer. Hierdie formulering is slegs invariant in ’n stogastiese sin. In die ander formulering, soos met die nuwe rotasionele invariante PSO, voeg ons bloot ’n self-skalerende ewekansige vektor by die onveranderde volledige rekenkundige kruisingsvektor. Hierdie formulering is streng invariant onder rotasie, selfs al is dit steeds net in ’n stogastiese sin. Vir die KPGA wys ons dat die standaard KPGA wat gemengde kruising en standaard mutasies gebruik, rotasioneel variant is. Om ’n rotasionele invariante KPGA te konstrueer is dit moontlik om die kruisingsoperasie aan te pas. Dit veroorsaak weereens ’n verlies aan diversiteit. Ons maak die algoritmes divers op twee verskillende maniere: eerstens deur gebruik te maak van ’n gewysigde mutasie skema, en tweedens deur die selfde aanslag te gebruik as in die PSO en die DE, deur ’n self-skalerende ewekansige vektor by die nageslag vektor te voeg. Hierdie formulering is streng invariant onder rotasie, selfs al is dit steeds net in ’n stogastiese sin. Numeriese resultate word vir die variante en invariante weergawe van die onderskeie algoritmes verskaf. Die doel van hierdie studie is nie die bydrae van bloot nog ’n kompeterend en/of beter populasiegebaseerde optimeringsmetode nie, maar eerder om formulerings voor te lê wat beide divers en invariant is, met die hoop dat dit in die toekoms bykomende bydraes sal stimuleer, omdat rotasionele invariansie in die algemeen ’n aantreklike, belangrike kenmerk is vir ’n optimerings algoritme.