No description available.

MSc(Eng),Faculty of Engineering and the Built Environment, University of the Witwatersrand, 2010 / This dissertation presents two important results: a novel algorithm that approximately solves the optimal assignment problem as well as a novel method of projecting matrices into the doubly stochastic polytope while preserving the optimal assignment. The optimal assignment problem is a classical combinatorial optimisation problem that has fuelled extensive research in the last century. The problem is concerned with a matching or assignment of elements in one set to those in another set in an optimal manner. It finds typical application in logistical optimisation such as the matching of operators and machines but there are numerous other applications. In this document a process of iterative weighted normalization applied to the benefit matrix associated with the Assignment problem is considered. This process is derived from the application of the Computational Ecology Model to the assignment problem and referred to as the OACE (Optimal Assignment by Computational Ecology) algorithm. This simple process of iterative weighted normalisation converges towards a matrix that is easily converted to a permutation matrix corresponding to the optimal assignment or an assignment close to optimality. The document also considers a method of projecting a matrix into the doubly stochastic polytope while preserving the optimal assignment. Various methods of projecting square matrices into the doubly stochastic polytope exist but none that preserve the assignment. This novel result could prove instrumental in solving assignment problems and promises applications in other optimisation algorithms similar to those that Sinkhorn’s algorithm finds.

This thesis describes the investigations undertaken to produce a novel hybrid optimisation technique that combines both global and local searching to produce good solutions quickly. Many evolutionary computation and experimental design methods are considered before genetic algorithms and evolutionary operation are combined to produce novel optimisation algorithms. A novel piece of software is created to run two and three factor evolutionary operation experiments. A range of new hybrid small population genetic algorithms are created that contain evolutionary operation in all generations (static hybrids) or contain evolutionary operation in a controlled number of generations (dynamic hybrids). A large number of empirical tests are carried out to determine the influence of operators and the performance of the hybrids over a range of standard test functions. For very small populations, twenty or less individuals, stochastic universal sampling is demonstrated to be the most suitable method of selection. The performance of very small population evolutionary operation hybrid genetic algorithms is shown to improve with larger generation gaps on simple functions and on more complex functions increasing the generation gap does not deteriorate performance. As a result of the testing carried out for this study a generation gap of 0.7 is recommended as a starting point for empirical searches using small population genetic algorithms and their hybrids. Due to the changing presence of evolutionary operation, the generation gap has less influence on dynamic hybrids compared to the static hybrids. The evolutionary operation, local search element is shown to positively influence the performance of the small population genetic algorithm search. The evolutionary operation element in the hybrid genetic algorithm gives the greatest improvement in performance when present in the middle generations or with a progressively greater presence. A recommendation for the information required to be reported for benchmarking genetic algorithm performance is also presented. This includes processor, platform, software information as well as genetic algorithm parameters such as population size, number of generations, crossover method and selection operators and results of testing on a set of standard test functions.

Thesis (MPhil)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: Tonality cognition incorporates a number of diverse and multidisciplinary aspects, including music cognition, acoustics, culture, computer-aided modelling, music theory and brain science. Current research shows growing emphasis on the use of computational models implemented on digital computers for music analysis, particularly with reference to the analysis of statistical properties, form and tonal properties. The applications of these analytical techniques are numerous, including the classification of genre and style, Music Information Retrieval (MIR), data mining and algorithmic composition. The research described in this document focuses on three aspects of tonality analysis, namely music cognition, computational modelling and music theory, particularly from the perspectives of statistical analysis and key-finding. Mathematical formulations are presented for a number of computational algorithms for analysing the statistical and tonal properties of music encoded in symbolic format. These include algorithms for determining the distributions of note durations, pitch intervals and pitch classes for statistical analysis and for template-based key-finding for tonal analysis. The implementation and validation of these computational algorithms on the Matlab software platform are subsequently discussed. The software application is used to determine whether a more optimal combination of pitch class weighing model and key profile template for the template-based key-finding algorithm can be derived, using the 24 preludes from Bach’s Well-tempered Clavier Book I, the Courante from Bach's Cello Suite in C major and the Gavotte from Bach's French Suite No. 5 in G major (BWV 816) as test material. Four pitch class weighing models, namely histogram weighing, flat weighing, linear durational weighing and durational accent weighing, are investigated. Two prominent key profile templates proposed in literature are considered, namely a key profile derived from tonality cognition experiments and a key profile based on classical music theory principles. The results show that the key-finding performances of all the combinations of the pitch class weighing models and existing key profile templates depend on the nature of the test material and that none of the combinations perform optimally for all test material. The software application is subsequently used to determine whether a more optimal key profile template can be derived using a pattern search parameter estimation algorithm. This investigation was conducted for diverse sets of search conditions, including unconstrained and constrained key profile coefficients, different pitch class weighing models, various key resolutions and different search algorithm parameters. Using the same sample material as for the key-finding evaluations, the investigation showed that a more optimal key profile, compared to existing profiles, can be derived. In comparing the average key-finding scores for all of the test material, the optimised profiles outperform the existing profiles substantially. The optimised key profiles introduce new pitch class hierarchies where the supertonic and the subdominant rate higher at the expense of the mediant in the major profile to improve the tracking of key modulations. / AFRIKAANSE OPSOMMING: Kognitiewe tonaliteit behels 'n aantal uiteenlopende en multidissiplinêre aspekte, insluitende musiek, akoestiek, kultuur, rekenaargesteunde modelering, musiekteorie en breinwetenskap. Huidige navorsing toon toenemende klem op die gebruik van berekenende modelering wat op digitale rekenaars geimplimenteer is vir musiekanalise, veral met verwysing na die analise van statistiese eienskappe, vorm en tonale eienskappe. Die aanwending van hierdie analitiese tegnieke is veelvoudig, insluitende die klassifikasie van genre of styl, onttrekking van musiekinformasie, dataversameling en algoritmiese komposisie. Die navorsing wat in hierdie dokument beskryf word fokus op drie aspekte van tonaliteit analise, naamlik musiekkognisie, berekenende modelering en musiekteorie, veral vanuit die perspektiewe van statistiese analise and toonsoortsoek. Wiskundige formulerings word aangebied vir 'n aantal berekeningalgoritmes vir die analise van die statistiese en tonale eienskappe van musiek wat in simboliese formaat ge-enkodeer is. Hierdie sluit algoritmes in vir die bepaling van die verspreidings van nootlengtes, toonintervalle en toonklasse vir statistiese analise en vir templaatgebaseerde toonsoortsoek vir tonale analise. Die implementering en validering van hierdie berekeningalgoritmes op die Matlab programmatuur platvorm word vervolgens bespreek. Die programmatuur toepassing word vervolgens gebruik om te bepaal of 'n meer optimale kombinasie van toonklas weegmodel en toonsoortprofiel templaat vir die templaat-gebaseerde toonsoortsoek algoritme afgelei kan word, deur gebruik te maak van Bach se Well-tempered Clavier Book I, die Courante van Bach se Cello Suite in C major en die Gavotte van Bach se French Suite No. 5 in G major (BWV 816) as toetsmateriaal. Vier toonklas weegmodelle, naamlik histogram weging, plat weging, lineêre duurtyd weging en duurtyd aksent weging, word ondersoek. Twee prominente toonsoortprofiel template uit die literatuur word oorweeg, naamlik 'n toonsoortprofiel wat van tonaliteit kognisie eksperimente afgelei is en 'n toonsoortprofiel gebaseer op klassieke musiekteoretiese beginsels. Die resultate wys dat die toonsoortsoek prestasies van al die kombinasies van die toonklas weegmodelle en bestaande toonsoortprofiel template afhang van die aard van die toetsmateriaal en dat geen van die kombinasies optimaal presteer vir alle toetsmateriaal nie. Die programmatuur toepassing word vervolgens aangewend om vas te stel of 'n meer optimale toonsoortprofiel afgelei kan word deur gebruik te maak van 'n patroonsoek parameterestimasie algoritme. Hierdie ondersoek is uitgevoer vir uiteenlopende stelle soektoestande, insluitende onbeperkte en beperkte toonsoortprofiel koëffisiënte, verskillende toonklas weegmodelle, 'n verskeidenheid toonsoort resolusies en verskillende soekalgoritme parameters. Deur gebruik te maak van dieselfde toetsmateriaal as vir die toonsoortsoek evaluerings, toon die ondersoek dat 'n meer optimale toonsoortprofiel, in vergelyking met bestaande profiele, afgegelei kan word. In 'n vergelyking van die gemiddelde toonsoortsoek prestasie vir al die toetsmateriaal, presteer die geoptimeerde profiele aansienlik beter as die bestaande profiele. The ge-optimeerde toonsoortprofiele lei tot nuwe toonklas hiërargiee waar die supertonikum en die subdominant hoër rangposissies beklee ten koste van die mediant in die majeur profiel, ten einde die navolg van toonsoort modulasies te verbeter.

This thesis is to study the optimisation problems in autonomous vehicles, especially the modelling and optimisation of collision avoidance, and to develop some optimisation algorithms based on genetic algorithms and neural networks to operate autonomous vehicles without any collision. Autonomous vehicles, also called self-driving vehicles or driverless vehicles are completely robotised driving frameworks to allow the vehicle to react to outside conditions within a bunch of calculations to play out the undertakings. This thesis summarised artificial intelligence and optimisation techniques for autonomous driving systems in the literature. The optimisation problems related to autonomous vehicles are categorised into four groups: lane change, motion planner, collision avoidance, and artificial intelligence. A chart had been developed to summarise those research and related optimisation methods to help future researchers in the selection of optimisation methods Collision Avoidance is one of streamlining issues in autonomous vehicles. Several sensors had been used to identify position and dangers and collision avoidance algorithms had been developed to analyse the dangers and to use vehicles to avoid a collision. In this thesis, the current research on collision avoidance has been reviewed and some challenges and future works were presented to select the research direction of this thesis, the aim of this research will be the development of optimisation methods to avoid collisions in a predefined environment. The contributions of this thesis are that (1) a simulation model had been developed using Matlab for collision avoidance and serval scenarios were proposed and experimented with. The sensors are used as the inputs to determine collision in the learning preparation of the algorithm; (2) a neural network was used for collision avoidance of autonomous vehicles; (3) a new method was proposed with the combination of genetic algorithm and neural network. In the proposed frame, the neural network is used for decision making and a genetic algorithm is used for the training of the neural network. The results and experimentation show that the proposed strategies are well in the designed environment.

Recent years have seen a growing tendency that a large number of generators are connected to the electricity distribution networks, including renewables such as solar photovoltaics, wind turbines and biomass-fired power plants. Meanwhile, on the demand side, there are also some new types of electric loads being connected at increasing rates, with the most important of them being the electric vehicles (EVs). Uncertainties both from generation and consumption of electricity mentioned above are thereby being introduced, making the management of the system more challenging. With the proportion of electric vehicle ownership rapidly increasing, uncontrolled charging of large populations may bring about power system issues such as increased peak demand and voltage variations, while at the same time the cost of electricity generation, as well as the resulting Greenhouse Gases (GHG) emissions, will also rise. The work reported in this PhD Thesis aims to provide solutions to the three significant challenges related to EV integration, namely voltage regulation, generation cost minimisation and GHG emissions reduction. A novel, high-resolution, bottom-up probabilistic EV charging demand model was developed, that uses data from the UK Time Use Survey and the National Travel Survey to synthesise realistic EV charging time series based on user activity patterns. Coupled with manufacturers' data for representative EV models, the developed probabilistic model converts single user activity profiles into electrical demand, which can then be aggregated to simulate larger numbers at a neighbourhood, city or regional level. The EV charging demand model has been integrated into a domestic electrical demand model previously developed by researchers in our group at the University of Edinburgh. The integrated model is used to show how demand management can be used to assist voltage regulation in the distribution system. The node voltage sensitivity method is used to optimise the planning of EV charging based on the influence that every EV charger has on the network depending on their point of connection. The model and the charging strategy were tested on a realistic "highly urban" low voltage network and the results obtained show that voltage fluctuation due to the high percentage of EV ownership (and charging) can be significantly and maintained within the statutory range during a full 24-hour cycle of operation. The developed model is also used to assess the generation cost as well as the environmental impact, in terms of GHG emissions, as a result of EV charging, and an optimisation algorithm has been developed that in combination with domestic demand management, minimises the incurred costs and GHG emissions. The obtained results indicate that although the increased population of EVs in distribution networks will stress the system and have adverse economic and environmental effects, these may be minimised with careful off-line planning.

Estimation of Distribution Algorithms (EDAs) belong to the class of population based optimisation algorithms. They are motivated by the idea of discovering and exploiting the interaction between variables in the solution. They estimate a probability distribution from population of solutions, and sample it to generate the next population. Many EDAs use probabilistic graphical modelling techniques for this purpose. In particular, directed graphical models (Bayesian networks) have been widely used in EDA. This thesis proposes an undirected graphical model (Markov Random Field (MRF)) approach to estimate and sample the distribution in EDAs. The interaction between variables in the solution is modelled as an undirected graph and the joint probability of a solution is factorised as a Gibbs distribution. The thesis describes a model of fitness function that approximates the energy in the Gibbs distribution, and shows how this model can be fitted to a population of solutions to estimate the parameters of the MRF. The estimated MRF is then sampled to generate the next population. This approach is applied to estimation of distribution in a general framework of an EDA, called Distribution Estimation using Markov Random Fields (DEUM). The thesis then proposes several variants of DEUM using different sampling techniques and tests their performance on a range of optimisation problems. The results show that, for most of the tested problems, the DEUM algorithms significantly outperform other EDAs, both in terms of number of fitness evaluations and the quality of the solutions found by them. There are two main explanations for the success of DEUM algorithms. Firstly, DEUM builds a model of fitness function to approximate the MRF. This contrasts with other EDAs, which build a model of selected solutions. This allows DEUM to use fitness in variation part of the evolution. Secondly, DEUM exploits the temperature coefficient in the Gibbs distribution to regulate the behaviour of the algorithm. In particular, with higher temperature, the distribution is closer to being uniform and with lower temperature it concentrates near some global optima. This gives DEUM an explicit control over the convergence of the algorithm, resulting in better optimisation.

L'objectif principal de cette thèse est le dimensionnement et l'optimisation de la production d'une petite installation d'énergie renouvelable dans une zone isolée. Afin de déterminer la taille de l'installation, une étude de la capacité de production du site et du type d'énergie à utiliser doit être effectuée. Un programme est réglé afin de minimiser le coût d'une installation de production d’énergie hybride photovoltaïque et éolienne dans des sites différents. L’étape suivante est l'optimisation de la production d'énergie de chacun de ces systèmes individuellement, en utilisant un contrôleur de logique floue pour la poursuite du point de puissance maximale. Cette technique est basée sur l'approche directe, imitant le « Perturb & Observe » algorithme et surmontant ses limites, comme l'oscillation autour du PPM. Le système flou nécessite un réglage fin pour maximiser son efficacité, il est donc combiné avec différents algorithmes d'optimisation pour définir les fonctions d'appartenance et de modifier les règles. Cinq approches ont été testées : la logique floue type 1 a été combinée d'abord avec un algorithme génétique, deuxièmement avec l’optimisation par essaim de particules, la troisième approche a appliqué la logique flou type 2 et ensuite l’a combiné avec les mêmes algorithmes d'optimisation précédemment utilisés, pour les deux dernières approches. La dernière partie de ce travail présente un superviseur basé sur la logique floue qui est adapté pour une installation hybride photovoltaïque éolienne isolée, pour obtenir un fonctionnement optimal du système en fonction des changements des conditions atmosphériques et de la demande d'énergie, en tenant compte de l'état de charge des batteries et la dissipation de la surcharge d’énergie. Les simulations sont effectuées pour tous les systèmes afin de montrer leur efficacité. / The main objective of this thesis is to size and optimise the production of a small renewable energy installation in a remote isolated area. In order to determine the size of the installation a study of the site capacities and the type of energy to be used must be carried out. A program is set in order to minimize the cost of a hybrid wind and solar energy installation in different sites. The next step is the optimisation of the energy production of each of these systems individually using a fuzzy logic controller to track the maximum power point. This technique is based on the direct approach, mimicking the Perturb & Observe algorithm and overcoming its limitations, such as oscillation around the MPP.The FLC requires fine tuning to maximise its efficiency, therefore it is combined with different optimisation algorithms to set the membership function and modify the rules. Five approaches were tested: type one fuzzy logic was combined first with genetic algorithm, second with particle swarm optimisation, the third approach applied type two fuzzy logic and then combined it with the same optimisation algorithms as previously used, for the final two approaches. The last part of this work introduces a fuzzy logic based supervisor that is adapted for an isolated remote hybrid PV Wind installation, to obtain an optimal functioning of the system according to the changes in atmospheric conditions and energy demand, taking into account the state of charge of the batteries and energy overflow dissipation. Simulations are run for all of the systems to show their efficiency and effectiveness.

Water distribution networks are a fundamental part of any modern city and their daily operations constitute a significant expenditure in terms of energy and maintenance costs. Careful scheduling of pump operations may lead to significant energy savings and prevent wear and tear. By means of computer simulation, an optimal schedule of pumps can be found by an optimisation algorithm. The subject of this thesis is the study of pump scheduling as an optimisation problem. New representations of pump schedules are investigated for restricting the number of potential schedules. Recombination and mutation operators are proposed, in order to use the new representations in evolutionary algorithms. These new representations are empirically compared to traditional representations using different network instances, one of them being a large and complex network from UK. By means of the new representations, the evolutionary algorithm developed during this thesis finds new best-known solutions for both networks. Pump scheduling as the multi-objective problem of minimising energy and maintenance costs in terms of Pareto optimality is also investigated in this thesis. Two alternative surrogate measures of maintenance cost are considered: the minimisation of the number of pump switches and the maximisation of the shortest idle time. A single run of the multi-objective evolutionary algorithm obtains pump schedules with lower electrical cost and lower number of pump switches than those found in the literature. Alternatively, schedules with very long idle times may be found with slightly higher electrical cost. Finally, ant colony optimisation is also adapted to the pump scheduling problem. Both Ant System and Max-Min Ant System are tested. Max-Min Ant System, in particular, outperforms all other algorithms in the large real-world network instance and obtains competitive results in the smallest test network. Computation time is further reduced by parallel simulation of pump schedules.