Dans cette thèse, nous cherchons à répondre à une problématique formulée par la DGA Techniques navales pour surveiller une zone stratégique : planifier le déploiement spatial et temporel optimal d’un ensemble de capteurs de façon à maximiser les chances de détecter une cible mobile et intelligente. La cible est dite intelligente car elle est capable de détecter sous certaines conditions les menaces que représentent les capteurs et ainsi de réagir en adaptant son comportement. Les déploiements générés pouvant aussi avoir un coût élevé nous devons tenir compte de ce critère lorsque nous résolvons notre problématique. Il est important de noter que la résolution d’un problème de ce type requiert, selon les besoins, l’application d’une méthode d’optimisation mono-objectif voire multiobjectif. Jusqu’à présent, les travaux existants n’abordent pas la question du coût des déploiements proposés. De plus la plupart d’entre eux ne se concentrent que sur un seul aspect à la fois. Enfin, pour des raisons algorithmiques, les contraintes sont généralement discrétisées.Dans une première partie, nous présentons un algorithme qui permet de déterminer le déploiement spatio-temporel de capteurs le plus efficace sans tenir compte de son coût. Cette méthode est une application à l’optimisation de la méthode multiniveau généralisée.Dans la seconde partie, nous montrons d’abord que l’utilisation de la somme pondérée des deux critères permet d’obtenir des solutions sans augmenter le temps de calcul. Pour notre seconde approche, nous nous inspirons des algorithmes évolutionnaires d’optimisation multiobjectif et adaptons la méthode multiniveau généralisée à l’optimisation multiobjectif. / In this work, we propose a solution to a problem issued by the DGA Techniques navales in order to survey a strategic area: determining the optimal spatio-temporal deployment of sensors that will maximize the detection probability of a mobile and smart target. The target is said to be smart because it is capable of detecting the threat of the sensors under certain conditions and then of adapting its behaviour to avoid it. The cost of a deployment is known to be very expensive and therefore it has to be taken into account. It is important to note that the wide spectrum of applications within this field of research also reflects the need for a highly complex theoretical framework based on stochastic mono or multi-objective optimisation. Until now, none of the existing works have dealt with the cost of the deployments. Moreover, the majority only treat one type of constraint at a time. Current works mostly rely on operational research algorithms which commonly model the constraints in both discrete space and time.In the first part, we present an algorithm which computes the most efficient spatio-temporal deployment of sensors, but without taking its cost into account. This optimisation method is based on an application of the generalised splitting method.In the second part, we first use a linear combination of the two criteria. For our second approach, we use the evolutionary multiobjective optimisation framework to adapt the generalised splitting method to multiobjective optimisation. Finally, we compare our results with the results of the NSGA-II algorithm.

This research augments current Multiple Objective Evolutionary Algorithms with methods that dramatically reduce the time required to evolve toward a region of interest in objective space. Multiple Objective Evolutionary Algorithms (MOEAs) are superior to other optimization techniques when the search space is of high dimension and contains many local minima and maxima. Likewise, MOEAs are most interesting when applied to non-intuitive complex systems. But, these systems are often computationally expensive to calculate. When these systems require independent computations to evaluate each objective, the computational expense grows with each additional objective. This method has developed methods that reduces the time required for evolution by reducing the number of objective evaluations, while still evolving solutions that are Pareto optimal. To date, all other Multiple Objective Evolutionary Algorithms (MOEAs) require the evaluation of all objectives before a fitness value can be assigned to an individual. The original contributions of this thesis are: 1. Development of a hierarchical search space description that allows association of crossover and mutation settings with elements of the genotypic description. 2. Development of a method for parallel evaluation of individuals that removes the need for delays for synchronization. 3. Dynamical evolution of thresholds for objectives to allow partial evaluation of objectives for individuals. 4. Dynamic objective orderings to minimize the time required for unnecessary objective evaluations. 5. Application of MOEAs to the computationally expensive flare pattern design domain. 6. Application of MOEAs to the optimization of fielded missile warning receiver algorithms. 7. Development of a new method of using MOEAs for automatic design of pattern recognition systems.

Many real-world decision processes require solving optimization problems which may involve different types of constraints such as inequality and equality constraints. The hurdles in solving these Constrained Optimization Problems (COPs) arise from the challenge of searching a huge variable space in order to locate feasible points with acceptable solution quality. Over the last decades Evolutionary Algorithms (EAs) have brought a tremendous advancement in the area of computer science and optimization with their ability to solve various problems. However, EAs have inherent difficulty in dealing with constraints when solving COPs. This thesis presents a new Agent-based Memetic Algorithm (AMA) for solving COPs, where the agents have the ability to independently select a suitable Life Span Learning Process (LSLP) from a set of LSLPs. Each agent represents a candidate solution of the optimization problem and tries to improve its solution through cooperation with other agents. Evolutionary operators consist of only crossover and one of the self-adaptively selected LSLPs. The performance of the proposed algorithm is tested on benchmark problems, and the experimental results show convincing performance. The quality of individuals in the initial population influences the performance of evolutionary algorithms, especially when the feasible region of the constrained optimization problems is very tiny in comparison to the entire search space. This thesis proposes a method that improves the quality of randomly generated initial solutions by sacrificing very little in diversity of the population. The proposed Search Space Reduction Technique (SSRT) is tested using five different existing EAs, including AMA, by solving a number of state-of-the-art test problems and a real world case problem. The experimental results show SSRT improves the solution quality, and speeds up the performance of the algorithms. The handling of equality constraints has long been a difficult issue for evolutionary optimization methods, although several methods are available in the literature for handling functional constraints. In any optimization problems with equality constraints, to satisfy the condition of feasibility and optimality the solution points must lie on each and every equality constraint. This reduces the size of the feasible space and makes it difficult for EAs to locate feasible and optimal solutions. A new Equality Constraint Handling Technique (ECHT) is presented in this thesis, to enhance the performance of AMA in solving constrained optimization problems with equality constraints. The basic concept is to reach a point on the equality constraint from its current position by the selected individual solution and then explore on the constraint landscape. The technique is used as an agent learning process in AMA. The experimental results confirm the improved performance of the proposed algorithm. This thesis also proposes a Modified Genetic Algorithm (MGA) for solving COPs with equality constraints. After achieving inspiring performance in AMA when dealing with equality constraints, the new technique is used in the design of MGA. The experimental results show that the proposed algorithm overcomes the limitations of GA in solving COPs with equality constraints, and provides good quality solutions.

Doctor of Philosophy / Department of Electrical and Computer Engineering / Sanjoy Das / Anil Pahwa / The task of short-term optimal thermal generation scheduling can be cast in the form of a multi-objective optimization problem. The goal is to determine an optimal operating strategy to operate power plants, in such a way that certain objective functions related to economic and environmental issues, as well as transmission losses are minimized, under typical system and operating constraints. Due to the problem’s inherent complexity, and the large number of associated constraints, standard multi-objective optimization algorithms fail to yield optimal solutions. In this dissertation, a novel, two-phase multi-objective evolutionary approach is proposed to address the short-term optimal thermal generation scheduling problem. The objective functions, which are based on operation cost, emission and transmission losses, are minimized simultaneously. During the first phase of this approach, hourly optimal dispatches for each period are obtained separately, by minimizing the operation cost, emission and transmission losses simultaneously. The constraints applied to this phase are the power balance, spinning reserve and power generation limits. Three well known multi-objective evolutionary algorithms, NSGA-II, SPEA-2 and AMOSA, are modified, and several new features are added. This hourly schedule phase also includes a repair scheme that is used to meet the constraint requirements of power generation limits for each unit as well as balancing load with generation. The new approach leads to a set of highly optimal solutions with guaranteed feasibility. This phase is applied separately to each hour long period. In the second phase, the minimum up/down time and ramp up/down rate constraints are considered, and another improved version of the three multi-objective evolutionary algorithms, are used again to obtain a set of Pareto-optimal schedules for the integral interval of time (24 hours). During this phase, the hourly optimal schedules that are obtained from the first phase are used as inputs. A bi-objective version of the problem, as well as a three-objective version that includes transmission losses as an objective, are studied. Simulation results on four test systems indicate that even though NSGA-II achieved the best performance for the two-objective model, the improved AMOSA, with new features of crossover, mutation and diversity preservation, outperformed NSGA-II and SPEA-2 for the three-objective model. It is also shown that the proposed approach is effective in addressing the multi-objective generation dispatch problem, obtaining a set of optimal solutions that account for trade-offs between multiple objectives. This feature allows much greater flexibility in decision-making. Since all the solutions are non-dominated, the choice of a final 24-hour schedule depends on the plant operator’s preference and practical operating conditions. The proposed two-phase evolutionary approach also provides a general frame work for some other multi-objective problems relating to power generation as well as in other real world applications.

This thesis discusses the development and performance of a novel evolutionary algorithm, the Targeted Estimation of Distribution Algorithm (TEDA). TEDA takes the concept of targeting, an idea that has previously been shown to be effective as part of a Genetic Algorithm (GA) called Fitness Directed Crossover (FDC), and introduces it into a novel hybrid algorithm that transitions from a GA to an Estimation of Distribution Algorithm (EDA). Targeting is a process for solving optimisation problems where there is a concept of control points, genes that can be said to be active, and where the total number of control points found within a solution is as important as where they are located. When generating a new solution an algorithm that uses targeting must first of all choose the number of control points to set in the new solution before choosing which to set. The hybrid approach is designed to take advantage of the ability of EDAs to exploit patterns within the population to effectively locate the global optimum while avoiding the tendency of EDAs to prematurely converge. This is achieved by initially using a GA to effectively explore the search space before transitioning into an EDA as the population converges on the region of the global optimum. As targeting places an extra restriction on the solutions produced by specifying their size, combining it with the hybrid approach allows TEDA to produce solutions that are of an optimal size and of a higher quality than would be found using a GA alone without risking a loss of diversity. TEDA is tested on three different problem domains. These are optimal control of cancer chemotherapy, network routing and Feature Subset Selection (FSS). Of these problems, TEDA showed consistent advantage over standard EAs in the routing problem and demonstrated that it is able to find good solutions faster than untargeted EAs and non evolutionary approaches at the FSS problem. It did not demonstrate any advantage over other approaches when applied to chemotherapy. The FSS domain demonstrated that in large and noisy problems TEDA’s targeting derived ability to reduce the size of the search space significantly increased the speed with which good solutions could be found. The routing domain demonstrated that, where the ideal number of control points is deceptive, both targeting and the exploitative capabilities of an EDA are needed, making TEDA a more effective approach than both untargeted approaches and FDC. Additionally, in none of the problems was TEDA seen to perform significantly worse than any alternative approaches.

Thesis (MSc)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: The goal of this thesis is to present evolutionary algorithms, and demonstrate their applicability in quantum computing. As an introduction to evolutionary algorithms, it is applied to the simple but still challenging (from a computational viewpoint) Travelling Salesman Problem (TSP). This example is used to illustrate the e ect of various parameters like selection method, and maximum population size on the accuracy and e ciency of the evolutionary algorithms. For the sample problem, the 48 continental state capitals of the USA, solutions are evolved and compared to the known optimal solution. From this investigation tournament selection was shown to be the most e ective selection method, and that a population of 200 individuals per generation gave the most e ective convergence rates. In the next part of the thesis, evolutionary algorithms are applied to the generation of optimal quantum circuits for the following cases: The identity transformation : Picked for its simplicity as a test of the correct implementation of the evolutionary algorithm. The results of this investigation showed that the solver program functions correctly and that evolutionary algorithms can indeed nd valid solutions for this kind of problem. The work by Ding et al. [16] on optimal circuits for the two-qubit entanglement gate, controlled-S gate as well as the three qubit entanglement gate are solved by means of EA and the results compared. In all cases similar circuits are produced in fewer generations than the application of Ding et al. [16]. The three qubit quantum Fourier transform gate was also attempted, but no convergence was attained. The quantum teleportation algorithm is also investigated. Firstly the nature of the transformation that leads to quantum teleportation is considered. Next an e ective circuit is sought using evolutionary algorithms. The best result is one gate longer than Brassard [11], and seven gates longer than Yabuki [61]. / AFRIKAANSE OPSOMMING: Die doel van hierdie tesis is om evolusionêre algoritmes te ondersoek en hulle toepaslikheid op kwantumkomputasie te demonstreer. As 'n inleiding tot evolusionêre algoritmes is die eenvoudige, maar steeds komputasioneel uitdagende handelsreisigerprobleem ondersoek. Die invloed van die keuse van 'n seleksie metode, sowel as die invloed van die maksimum aantal individue in 'n generasie op die akkuraatheid en e ektiwiteit van die algoritmes is ondersoek. As voorbeeld is die 48 kontinentale hoofstede van die state van die VSA gekies. Die oplossings wat met evolusionêre algoritmes verkry is, is met die bekende beste oplossings vergelyk. Die resultate van hierdie ondersoek was dat toernooi seleksie die mees e ektiewe seleksie metode is, en dat 200 individue per generasie die mees e ektiewe konvergensie tempo lewer. Evolusionêre algoritmes word vervolgens toegepas om optimale oplossings vir die volgende kwantumalgoritmes te genereer: Die identiteitstransformasie: Hierdie geval is gekies as 'n eenvoudige toepassing met 'n bekende oplossing. Die resultaat van hierdie toepassing van die program was dat dit korrek funksioneer, en vinnig by die korrekte oplossings uitkom. Vervolgens is daar ondersoek ingestel na vier van die gevalle wat in Ding et al. [16] bespreek word. Die spesi eke transformasies waarna gekyk is, is 'n optimale stroombaan vir twee kwabis verstrengeling, 'n beheerde-S hek, 'n drie kwabis verstrengelings hek, en 'n drie kwabis kwantum Fourier transform hek. In die eerste drie gevalle stem die oplossings ooreen met die van Ding et al. [16], en is die konvergensie tempo vinniger. Daar is geen oplossing vir die kwantum Fourier transform verkry nie. Laastens is daar na die kwantumteleportasiealgoritme gekyk. Die eerste stap was om te kyk na die transformasie wat in hierdie geval benodig word, en daarna is gepoog om 'n e ektiewe stroombaan te evolueer. Die beste resultaat was een hek langer as Brassard [11], en sewe hekke langer as Yabuki [61].

This thesis presents a novel evolutionary optimisation algorithm that can improve the quality of solutions in simulation-based optimisation. Simulation-based optimisation is the process of finding optimal parameter settings without explicitly examining each possible configuration of settings. An optimisation algorithm generates potential configurations and sends these to the simulation, which acts as an evaluation function. The evaluation results are used to refine the optimisation such that it eventually returns a high-quality solution. The algorithm described in this thesis integrates multi-objective optimisation, parallelism, surrogate usage, and noise handling in a unique way for dealing with simulation-based optimisation problems incurred by these characteristics. In order to handle multiple, conflicting optimisation objectives, the algorithm uses a Pareto approach in which the set of best trade-off solutions is searched for and presented to the user. The algorithm supports a high degree of parallelism by adopting an asynchronous master-slave parallelisation model in combination with an incremental population refinement strategy. A surrogate evaluation function is adopted in the algorithm to quickly identify promising candidate solutions and filter out poor ones. A novel technique based on inheritance is used to compensate for the uncertainties associated with the approximative surrogate evaluations. Furthermore, a novel technique for multi-objective problems that effectively reduces noise by adopting a dynamic procedure in resampling solutions is used to tackle the problem of real-world unpredictability (noise). The proposed algorithm is evaluated on benchmark problems and two complex real-world problems of manufacturing optimisation. The first real-world problem concerns the optimisation of a production cell at Volvo Aero, while the second one concerns the optimisation of a camshaft machining line at Volvo Cars Engine. The results from the optimisations show that the algorithm finds better solutions for all the problems considered than existing, similar algorithms. The new techniques for dealing with surrogate imprecision and noise used in the algorithm are identified as key reasons for the good performance.

Urban watershed management poses a very challenging problem due to the varioussources of pollution and there is a need to develop optimal management models that canfacilitate the process of identifying optimal water quality management strategies. Ascreening level, comprehensive, and integrated computational methodology is developedfor the management of point and non-point sources of pollution in urban watersheds. Themethodology is based on linking macro-level water quality simulation models withefficient nonlinear constrained optimization methods for urban watershed management.The use of macro-level simulation models in lieu of the traditional and complexdeductive simulation models is investigated in the optimal management framework forurban watersheds. Two different types of macro-level simulation models are investigatedfor application to watershed pollution problems namely explicit inductive models andsimplified deductive models. Three different types of inductive modeling techniques areused to develop macro-level simulation models ranging from simple regression methodsto more complex and nonlinear methods such as artificial neural networks and geneticfunctions. A new genetic algorithm (GA) based technique of inductive modelconstruction called Fixed Functional Set Genetic Algorithm (FFSGA) is developed andused in the development of macro-level simulation models. A novel simplified deductivemodel approach is developed for modeling the response of dissolved oxygen in urbanstreams impaired by point and non-point sources of pollution. The utility of this inverseloading model in an optimal management framework for urban watersheds isinvestigated.In the context of the optimization methods, the research investigated the use of parallelmethods of optimization for use in the optimal management formulation. These includedan evolutionary computing method called genetic optimization and a modified version ofthe direct search method of optimization called the Shuffled Box Complex method ofconstrained optimization. The resulting optimal management model obtained by linkingmacro-level simulation models with efficient optimization models is capable ofidentifying optimal management strategies for an urban watershed to satisfy waterquality and economic related objectives. Finally, the optimal management model isapplied to a real world urban watershed to evaluate management strategies for waterquality management leading to the selection of near-optimal strategies.

The purpose of this research project is the design and optimization of complex chemical engineering problems, by employing evolutionary algorithms (EAs). EAs are optimization techniques which mimic the principles of genetics and natural selection. Given their population-based approach, EAs are well suited for solving multiobjective optimization problems (MOOPs) to determine Pareto-optimal solutions. The Pareto front refers to the set of non-dominated solutions which highlight trade-offs among the different objectives. A broad range of applications have been studied, all of which are drawn from the chemical engineering field. The design of an industrial packed bed styrene reactor is initially studied with the goal of maximizing the productivity, yield and selectivity of styrene. The dual population evolutionary algorithm (DPEA) was used to circumscribe the Pareto domain of two and three objective optimization case studies for three different configurations of the reactor: adiabatic, steam-injected and isothermal. The Pareto domains were then ranked using the net flow method (NFM), a ranking algorithm that incorporates the knowledge and preferences of an expert into the optimization routine. Next, a multiobjective optimization of the heat transfer area and pumping power of a shell-and-tube heat exchanger is considered to provide the designer with multiple Pareto-optimal solutions which capture the trade-off between the two objectives. The optimization was performed using the fast and elitist non-dominated sorting genetic algorithm (NSGA-II) on two case studies from the open literature. The algorithm was also used to determine the impact of using discrete standard values of the tube length, diameter and thickness rather than using continuous values to obtain the optimal heat transfer area and pumping power. In addition, a new hybrid algorithm called the FP-NSGA-II, is developed in this thesis by combining a front prediction algorithm with the fast and elitist non-dominated sorting genetic algorithm-II (NSGA-II). Due to the significant computational time of evaluating objective functions in real life engineering problems, the aim of this hybrid approach is to better approximate the Pareto front of difficult constrained and unconstrained problems while keeping the computational cost similar to NSGA-II. The new algorithm is tested on benchmark problems from the literature and on a heat exchanger network problem.

Satellite formation missions allow for scientific measurement opportunities that are only otherwise possible with the use of unrealistically large satellites. This work applies the Evolutionary Algorithm (EA), Differential Evolution (DE), to a 4-satellite mission design that borrows heavily from the mission specifications for Phase 1 of NASA's Magnetospheric Multi-Scale Mission (MMS). This mission specifies goals for formation "quality" and size over the arc when scientific measurements are to be taken known as the Region of Interest (ROI). To apply DE to this problem a novel definition of fitness is developed and tailored to trajectory problems of the parameter scales of this mission. This method uses numerical integration of evolved initial conditions for trajectory determination. This approach allows for the inclusion of gravitational perturbations without altering the method. Here, the J2 oblateness correction is considered but other inclusions such as solar radiation pressure and other gravitational bodies are readily possible by amending the governing equations of integration which are stored outside of the method and called only during evaluation. A set of three launch conditions is evaluated using this method. Due to computational limitation, the design is restricted to only single-impulse maneuvers at launch and the ROI is initially restricted but then expanded through a process known here as "staging". The ROIs of tests are expanded until they fail to meet performance criteria; no result was able to stage to the full MMS specified $\pm20^\circ$ ROI but this is a result of the single-impulse restriction. The number of orbits a launch condition is able to meet performance criteria is also investigated. Revolutions considered and the ROIs therein contained are staged to investigate if the method is able to handle this additional problem space. Evidence of suitable formation trajectories found by this method is here presented.