Flooding is an important concern for the UK, as evidenced by the many extreme flooding events in the last decade. Improved flood risk intervention strategies are therefore highly desirable. The application of hydroinformatics tools, and optimisation algorithms in particular, which could provide guidance towards improved intervention strategies, is hindered by the necessity of performing flood modelling in the process of evaluating solutions. Flood modelling is a computationally demanding task; reducing its impact upon the optimisation process would therefore be a significant achievement and of considerable benefit to this research area. In this thesis sophisticated multi-objective optimisation algorithms have been utilised in combination with cutting-edge flood-risk assessment models to identify least-cost and most-benefit flood risk interventions that can be made on a drainage network. Software analysis and optimisation has improved the flood risk model performance. Additionally, artificial neural networks used as feature detectors have been employed as part of a novel development of an optimisation algorithm. This has alleviated the computational time-demands caused by using extremely complex models. The results from testing indicate that the developed algorithm with feature detectors outperforms (given limited computational resources available) a base multi-objective genetic algorithm. It does so in terms of both dominated hypervolume and a modified convergence metric, at each iteration. This indicates both that a shorter run of the algorithm produces a more optimal result than a similar length run of a chosen base algorithm, and also that a full run to complete convergence takes fewer iterations (and therefore less time) with the new algorithm.

Most optimisation problems in everyday life are not static in nature, have multiple objectives and at least two of the objectives are in conflict with one another. However, most research focusses on either static multi-objective optimisation (MOO) or dynamic singleobjective optimisation (DSOO). Furthermore, most research on dynamic multi-objective optimisation (DMOO) focusses on evolutionary algorithms (EAs) and only a few particle swarm optimisation (PSO) algorithms exist. This thesis proposes a multi-swarm PSO algorithm, dynamic Vector Evaluated Particle Swarm Optimisation (DVEPSO), to solve dynamic multi-objective optimisation problems (DMOOPs). In order to determine whether an algorithm solves DMOO efficiently, functions are required that resembles real world DMOOPs, called benchmark functions, as well as functions that quantify the performance of the algorithm, called performance measures. However, one major problem in the field of DMOO is a lack of standard benchmark functions and performance measures. To address this problem, an overview is provided from the current literature and shortcomings of current DMOO benchmark functions and performance measures are discussed. In addition, new DMOOPs are introduced to address the identified shortcomings of current benchmark functions. Guides guide the optimisation process of DVEPSO. Therefore, various guide update approaches are investigated. Furthermore, a sensitivity analysis of DVEPSO is conducted to determine the influence of various parameters on the performance of DVEPSO. The investigated parameters include approaches to manage boundary constraint violations, approaches to share knowledge between the sub-swarms and responses to changes in the environment that are applied to either the particles of the sub-swarms or the non-dominated solutions stored in the archive. From these experiments the best DVEPSO configuration is determined and compared against four state-of-the-art DMOO algorithms. / Thesis (PhD)--University of Pretoria, 2012. / Computer Science / unrestricted

Ces travaux de recherche abordent un problème de défense anti-aérien, usuellement appelé problème d'allocation d'armes à des cibles dans la littérature. L'allocation d'armes à des cibles est un problème bien connu de la recherche opérationnelle militaire qui a rencontré un franc succès parmi la communauté des chercheurs, et qui aujourd'hui encore suscite un large engouement puisque sa propriété démontrée NP-difficile en fait un problème qui reste irrésolu. Que ce soit par des méthodes analytiques ou meta-heuristiques, le problème d'allocation d'armes à des cibles a fait l'objet de nombreuses propositions de résolution. Cependant, il est assez surprenant de voir que la modélisation proposée pour ce problème n'a guère évolué depuis qu'il est apparu pour la première fois dans la littérature en 1950. Cette modélisation peut être considérée comme obsolète aujourd'hui et ne répond plus aux exigences qui accompagnent les technologies modernes. En effet, en 60 ans le champ de bataille a complètement changé, et dans la littérature seulement un nombre limité d'études proposent de prendre en compte ces évolutions. L'étude menée dans cette thèse propose de s'intéresser aux systèmes de Commandes et Contrôles (C2) pour des applications anti-aériennes. Habituellement un système C2 est composé de senseurs, d'un centre d'opérations tactiques et d'un ou plusieurs lanceurs. Les senseurs alimentent le centre d'opérations tactiques à partir des informations qu'ils recueillent, puis, une fois ces informations reçues, le centre d'opérations tactiques va interpréter ces données afin de calculer l'atteignabilité des menaces. Enfin, un plan d'engagement qui comprend l'allocation des munitions disponibles aux cibles et une date de tir sont proposés à un opérateur humain qui aura pour mission de valider cette proposition en totalité ou partiellement, puis va procéder à l'engagement des menaces. Pour remplir cet objectif, une approche innovante et faisant l'objet d'un dépôt de brevet a été développée afin de répondre aux difficultés relatives aux problèmes d'optimisation multi-objectifs. Ensuite, un algorithme d'optimisation continue basé sur la combinaison de l'optimisation par essaim particulaires avec la théorie des jeux évolutionnaires est proposé pour optimiser les dates de tirs. L'allocation optimale, elle, est obtenue en adaptant cette méthode continue au cas discret. La preuve que l'algorithme développé est localement convergent est donnée dans cette thèse. D'autre part, l'aspect temps-réel a également fait l'objet d'une recherche attentive et l'algorithme précédemment cité a été hybridé avec les réseaux de neurones afin d'accélérer le temps de calcul des composants identifiés comme "lourds" en termes de charge de calcul. Enfin, cette étude ne se limite pas à une application de recherche opérationnelle militaire, mais inclut quelques concepts élémentaires de guidage et de navigation pour le calcul d'atteignabilité des menaces. Finalement, cette thèse permet d'identifier que les points suivants doivent faire l'objet d'une attention très particulière afin de développer un outil d'aide à la décision efficace. D'abord, la métrique d'évaluation d'un bon plan d'engagement doit être clairement analysée. Ensuite, le plan d'engagement proposé doit être stable et ne pas proposer de changements soudains qui pourraient perturber l'opérateur. Le troisième point concerne la robustesse de la solution proposée et sa capacité à faire face aux situations les plus compliquées. Quatrièmement, le temps et la charge de calcul sont des contraintes techniques qui ne peuvent pas être outrepassées. Finalement, les exigences posées lors de la préparation de mission et qui dépendent du contexte doivent faire l'objet d'une attention particulière. C'est pourquoi, l'outil d'aide à la décision proposé doit permettre un allègement significatif de la charge de travail de l'opérateur ainsi que la réduction considérable du stress lié à ce contexte / This research investigates a practical air defence problem, usually named Weapon Target Assignment (WTA) in the literature. The WTA problem is a well-known problem of military operation research that encountered a wide success in the research community, but still nowadays since it remains an unsolved problem because of its NP-hardness property. From analytical to heuristic methods, the WTA was deeply investigated and many attempts to solve this problem have been proposed. However, the proposed modelling of this problem is consistent with the 1950's technologies. Thus, the proposed modelling found in the literature can be considered as obsolete and cannot fit the requirement of the current technology advances. Indeed, the battle field dramatically changes over 60 years, and the recent literature proposes only few studies taking into account these amendments. The herein study proposes to investigate a Command & Control system (C2) in air defence applications. Usually a C2 system includes sensors, a Tactical Operation Centre (TOC) and one or more launchers. The sensors provide information about aerial tactical situation to the TOC. This TOC is in charge of evaluating the received information in order to compute the attainability of the targets, then an engagement plan that includes the assignment of the available weapons to the incoming targets and a date to fire for each assignment. This engagement plan is then proposed to one human operator in charge of accepting whole or part of this engagement plan and engage the targets following the received instructions. To achieve this goal, an innovative and patented approach to mitigate the issues related to multi-objective optimisation is proposed. Then, a continuous optimisation algorithm based on the combination of the Particle Swarm Optimisation and the Evolutionary Game Theory was proposed to determine the best dates to fire. The optimal assignment was obtained by adapting the aforementioned algorithm to the discrete case. This thesis also gives the proof that the designed algorithms are locally convergent and intensive benchmarking confirms the developed theory. In order to respect the real-time requirement, it was also devised to use the Neural Networks to lighten the identified burdensome parts of the algorithm and decrease computational time. Not limited to the military operation research field, the herein study reuse some basic concepts of missile guidance and navigation to compute the attainability of the targets. From this thesis, it can be identified that following aspects need to be carefully considered to provide an efficient decision making support to a human operator: First, clearly define what a good engagement plan is. Second, the engagement plan must be steady to avoid high rate changing in the assignments that could significantly disturb the operator. Third, the proposed engagement also must be reliable and robust to face any possible situations. Fourth, the computation time and computation load are technical constraints that cannot be overstepped. Finally, the operational constraints related to the mission context defined during a pre-mission stage must also be taken into account. Therefore, the proposed decision making support must help and significantly reduce the operator's work load in this situation of high stress and sensitive context

Cette thèse a pour objectif principal le développement de nouveaux algorithmes globaux pour la résolution de problèmes d’optimisation mono et multi-objectif, en se basant sur des formules de représentation ayant la tâche principale de générer des points initiaux appartenant à une zone proche du minimum globale. Dans ce contexte, une nouvelle approche appelée RFNM est proposée et testée sur plusieurs fonctions non linéaires, non différentiables et multimodales. D’autre part, une extension à la dimension infinie a été établie en proposant une démarche pour la recherche du minimum global. Par ailleurs, plusieurs problèmes de conception mécanique, à caractère aléatoire, ont été considérés et résolus en utilisant cette approche, avec amélioration de la méthode multi-objectif NNC. Enfin, une contribution à l'optimisation multi-objectif par une nouvelle approche a été proposée. Elle permet de générer un nombre suffisant de points pour représenter la solution optimale de Pareto. / The main objective of this work is to develop new global algorithms to solve single and multi-objective optimization problems, based on the representation formulas with the main task to generate initial points belonging to an area close to the global minimum. In this context, a new approach called RFNM is proposed and tested on several nonlinear, non-differentiable and multimodal finctions. On the other hand, an extension to the infinite dimension was established by proposing an approach for finding the global minimum. Moreover,several random mechanical design problems were considered and resolved using this approach, and improving the NNC multi-objective method. Finally, a new multi-objective optimization method called RSMO is presented. It solves the multi-objective optimization problems by generating a sufficient number o fpoints in the Pareto front.

In the building automation domain, there are gaps among various tasks related to design engineering. As a result created system designs must be adapted to the given requirements on system functionality, which is related to increased costs and engineering effort than planned. For this reason standards are prepared to enable a coordination among these tasks by providing guidelines and unified artifacts for the design. Moreover, a huge variety of prefabricated devices offered from different manufacturers on the market for building automation that realize building automation functions by preprogrammed software components. Current methods for design creation do not consider this variety and design solution is limited to product lines of a few manufacturers and expertise of system integrators. Correspondingly, this results in design solutions of a limited quality. Thus, a great optimization potential of the quality of design solutions and coordination of tasks related to design engineering arises. For given design requirements, the existence of a high number of devices that realize required functions leads to a combinatorial explosion of design alternatives at different price and quality levels. Finding optimal design alternatives is a hard problem to which a new solution method is proposed based on heuristical approaches. By integrating problem specific knowledge into algorithms based on heuristics, a promisingly high optimization performance is achieved. Further, optimization algorithms are conceived to consider a set of flexibly defined quality criteria specified by users and achieve system design solutions of high quality. In order to realize this idea, optimization algorithms are proposed in this thesis based on goal-oriented operations that achieve a balanced convergence and exploration behavior for a search in the design space applied in different strategies. Further, a component model is proposed that enables a seamless integration of design engineering tasks according to the related standards and application of optimization algorithms.

In the building automation domain, there are gaps among various tasks related to design engineering. As a result created system designs must be adapted to the given requirements on system functionality, which is related to increased costs and engineering effort than planned. For this reason standards are prepared to enable a coordination among these tasks by providing guidelines and unified artifacts for the design. Moreover, a huge variety of prefabricated devices offered from different manufacturers on the market for building automation that realize building automation functions by preprogrammed software components. Current methods for design creation do not consider this variety and design solution is limited to product lines of a few manufacturers and expertise of system integrators. Correspondingly, this results in design solutions of a limited quality. Thus, a great optimization potential of the quality of design solutions and coordination of tasks related to design engineering arises. For given design requirements, the existence of a high number of devices that realize required functions leads to a combinatorial explosion of design alternatives at different price and quality levels. Finding optimal design alternatives is a hard problem to which a new solution method is proposed based on heuristical approaches. By integrating problem specific knowledge into algorithms based on heuristics, a promisingly high optimization performance is achieved. Further, optimization algorithms are conceived to consider a set of flexibly defined quality criteria specified by users and achieve system design solutions of high quality. In order to realize this idea, optimization algorithms are proposed in this thesis based on goal-oriented operations that achieve a balanced convergence and exploration behavior for a search in the design space applied in different strategies. Further, a component model is proposed that enables a seamless integration of design engineering tasks according to the related standards and application of optimization algorithms.:1 Introduction 17 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3 Goals and Use of the Thesis . . . . . . . . . . . . . . . . . . . . . 21 1.4 Solution Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.5 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . 24 2 Design Creation for Building Automation Systems 25 2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2 Engineering of Building Automation Systems . . . . . . . . . . . 29 2.3 Network Protocols of Building Automation Systems . . . . . . . 33 2.4 Existing Solutions for Design Creation . . . . . . . . . . . . . . . 34 2.5 The Device Interoperability Problem . . . . . . . . . . . . . . . . 37 2.6 Guidelines for Planning of Room Automation Systems . . . . . . 38 2.7 Quality Requirements on BAS . . . . . . . . . . . . . . . . . . . 41 2.8 Quality Requirements on Design . . . . . . . . . . . . . . . . . . 42 2.8.1 Quality Requirements Related to Project Planning . . . . 42 2.8.2 Quality Requirements Related to Project Implementation 43 2.9 Quality Requirements on Methods . . . . . . . . . . . . . . . . . 44 2.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3 The Design Creation Task 47 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.2 System Design Composition Model . . . . . . . . . . . . . . . . . 49 3.2.1 Abstract and Detailed Design Model . . . . . . . . . . . . 49 3.2.2 Mapping Model . . . . . . . . . . . . . . . . . . . . . . . . 51 3.3 Formulation of the Problem . . . . . . . . . . . . . . . . . . . . . 53 3.3.1 Problem properties . . . . . . . . . . . . . . . . . . . . . . 54 3.3.2 Requirements on Algorithms . . . . . . . . . . . . . . . . 56 3.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4 Solution Methods for Design Generation and Optimization 59 4.1 Combinatorial Optimization . . . . . . . . . . . . . . . . . . . . . 59 4.2 Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.3 Examples for Metaheuristics . . . . . . . . . . . . . . . . . . . . . 62 4.3.1 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . 62 4.3.2 Tabu Search . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.3.3 Ant Colony Optimization . . . . . . . . . . . . . . . . . . 65 4.3.4 Evolutionary Computation . . . . . . . . . . . . . . . . . 66 4.4 Choice of the Solver Algorithm . . . . . . . . . . . . . . . . . . . 69 4.5 Specialized Methods for Diversity Preservation . . . . . . . . . . 70 4.6 Approaches for Real World Problems . . . . . . . . . . . . . . . . 71 4.6.1 Component-Based Mapping Problems . . . . . . . . . . . 71 4.6.2 Network Design Problems . . . . . . . . . . . . . . . . . . 73 4.6.3 Comparison of Solution Methods . . . . . . . . . . . . . . 74 4.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5 Automated Creation of Optimized Designs 79 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.2 Design Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.3 Component Model . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.3.1 Presumptions . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.3.2 Integration of Component Model . . . . . . . . . . . . . . 87 5.4 Design Generation . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.4.1 Component Search . . . . . . . . . . . . . . . . . . . . . . 88 5.4.2 Generation Approaches . . . . . . . . . . . . . . . . . . . 100 5.5 Design Improvement . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.5.1 Problems and Requirements . . . . . . . . . . . . . . . . . 107 5.5.2 Variations . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5.5.3 Application Strategies . . . . . . . . . . . . . . . . . . . . 121 5.6 Realization of the Approach . . . . . . . . . . . . . . . . . . . . . 122 5.6.1 Objective Functions . . . . . . . . . . . . . . . . . . . . . 122 5.6.2 Individual Representation . . . . . . . . . . . . . . . . . . 123 5.7 Automated Design Creation For A Building . . . . . . . . . . . . 124 5.7.1 Room Spanning Control . . . . . . . . . . . . . . . . . . . 124 5.7.2 Flexible Rooms . . . . . . . . . . . . . . . . . . . . . . . . 125 5.7.3 Technology Spanning Designs . . . . . . . . . . . . . . . . 129 5.7.4 Preferences for Mapping of Function Blocks to Devices . . 132 5.8 Further Uses and Applicability of the Approach . . . . . . . . . . 133 5.9 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 6 Validation and Performance Analysis 137 6.1 Validation Method . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.2 Performance Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.3 Example Abstract Designs and Performance Tests . . . . . . . . 139 6.3.1 Criteria for Choosing Example Abstract Designs . . . . . 139 6.3.2 Example Abstract Designs . . . . . . . . . . . . . . . . . . 140 6.3.3 Performance Tests . . . . . . . . . . . . . . . . . . . . . . 142 6.3.4 Population Size P - Analysis . . . . . . . . . . . . . . . . 151 6.3.5 Cross-Over Probability pC - Analysis . . . . . . . . . . . 157 6.3.6 Mutation Probability pM - Analysis . . . . . . . . . . . . 162 6.3.7 Discussion for Optimization Results and Example Designs 168 6.3.8 Resource Consumption . . . . . . . . . . . . . . . . . . . . 171 6.3.9 Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . 172 6.4 Optimization Framework . . . . . . . . . . . . . . . . . . . . . . . 172 6.5 Framework Design . . . . . . . . . . . . . . . . . . . . . . . . . . 174 6.5.1 Components and Interfaces . . . . . . . . . . . . . . . . . 174 6.5.2 Workflow Model . . . . . . . . . . . . . . . . . . . . . . . 177 6.5.3 Optimization Control By Graphical User Interface . . . . 180 6.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 7 Conclusions 185 A Appendix of Designs 189 Bibliography 201 Index 211