Dissertations / Theses on the topic 'Multi-Objective'

In this thesis, we investigate and develop a number of online learning selection choice function based hyper-heuristic methodologies that attempt to solve multi-objective unconstrained optimisation problems. For the first time, we introduce an online learning selection choice function based hyperheuristic framework for multi-objective optimisation. Our multi-objective hyper-heuristic controls and combines the strengths of three well-known multi-objective evolutionary algorithms (NSGAII, SPEA2, and MOGA), which are utilised as the low level heuristics. A choice function selection heuristic acts as a high level strategy which adaptively ranks the performance of those low-level heuristics according to feedback received during the search process, deciding which one to call at each decision point. Four performance measurements are integrated into a ranking scheme which acts as a feedback learning mechanism to provide knowledge of the problem domain to the high level strategy. To the best of our knowledge, for the first time, this thesis investigates the influence of the move acceptance component of selection hyper-heuristics for multi-objective optimisation. Three multi-objective choice function based hyper-heuristics, combined with different move acceptance strategies including All-Moves as a deterministic move acceptance and the Great Deluge Algorithm (GDA) and Late Acceptance (LA) as a nondeterministic move acceptance function. GDA and LA require a change in the value of a single objective at each step and so a well-known hypervolume metric, referred to as D metric, is proposed for their applicability to the multi-objective optimisation problems. D metric is used as a way of comparing two non-dominated sets with respect to the objective space. The performance of the proposed multi-objective selection choice function based hyper-heuristics is evaluated on the Walking Fish Group (WFG) test suite which is a common benchmark for multi-objective optimisation. Additionally, the proposed approaches are applied to the vehicle crashworthiness design problem, in order to test its effectiveness on a realworld multi-objective problem. The results of both benchmark test problems demonstrate the capability and potential of the multi-objective hyper-heuristic approaches in solving continuous multi-objective optimisation problems. The multi-objective choice function Great Deluge Hyper-Heuristic (HHMO_CF_GDA) turns out to be the best choice for solving these types of problems.

In this thesis, we address the route selection problem for Unmanned Air Vehicles (UAV) under multiple objectives. We consider a general case for this problem where the UAV has to visit several targets and return to the base. For this case, there are multiple combinatorial problems to be considered. First, the paths to be followed between any pairs of targets should be determined. This part can be considered as a multi-objective shortest path problem. Additionally, we need to determine the order of the targets to be visited. This in turn, is a multi-objective traveling salesperson problem. The overall problem is a combination of these two combinatorial problems. The route selection for UAVs has been studied by several researchers, mainly in the military context. They considered a linear combination of the two objectives
minimizing distance traveled and minimizing radar detection threat
and proposed heuristics for the minimization of the composite single objective problem. We treat these two objectives separately. We develop an evolutionary algorithm to determine the efficient tours. We also consider an exact interactive approach to identify the best paths and tours of a decision maker. We tested the two solution approaches on both small-sized and large-sized problem instances.

Performance and redundancy requirements imposed on state-of-the-art unmmaned combat aerial vehicles often lead to over-actuated systems with a mix of conventional and novel moment generators. Consequently, control allocation schemes have become a crucial part of the flight control architecture and their design is now a growing problem. This thesis presents a four control allocation scheme designed to meet multiple objectives and resolve objective conflicts by finding the ‘Pareto’ optimal solution, namely; Weighted Control Allocation, Minimax Control Allocation, Canonical Control Allocation and Classical. This is defined as a solution to the multi-objective optimisation problem which is non-dominated for all objectives. The scheme is applied to a six degrees of freedom nonlinear simulation of an aircraft equipped with conventional control surfaces as well as fluidic thrust vectoring and circulation control. The results indicate a perfect allocation of the total control demand onto the actuator suite.

This thesis aims to produce a novel multi-objective algorithm that is based on Cuckoo Search by Dr. Xin-She Yang. Cuckoo Search is a promising nature-inspired meta-heuristic optimization algorithm, which currently is only able to solve single-objective optimization problems. After an introduction, a number of theoretical points are presented as a basis for the decision of which algorithms to hybridize Cuckoo Search with. These are then reviewed in detail and verified against current benchmark algorithms to evaluate their efficiency. To test the proposed algorithm in a new setting, a real-world combinatorial problem is used. The proposed algorithm is then used as an optimization engine for a simulation-based system and compared against a current implementation.

As a result of the increase in accessibility of computational resources and the increase in the power of the computers during the last two decades, designers are able to create computer models to simulate the behavior of a complex products. To address global competitiveness, companies are forced to optimize their designs and products. Optimizing the design needs several runs of computationally expensive simulation models. Therefore, using metamodels as an efficient and sufficiently accurate approximate of the simulation model is necessary. Radial basis functions (RBF) is one of the several metamodeling methods that can be found in the literature. The established approach is to add a bias to RBF in order to obtain a robust performance. The a posteriori bias is considered to be unknown at the beginning and it is defined by imposing extra orthogonality constraints. In this thesis, a new approach in constructing RBF with the bias to be set a priori by using the normal equation is proposed. The performance of the suggested approach is compared to the classic RBF with a posteriori bias. Another comprehensive comparison study by including several modeling criteria, such as problem dimension, sampling technique and size of samples is conducted. The studies demonstrate that the suggested approach with a priori bias is in general as good as the performance of RBF with a posteriori bias. Using the a priori RBF, it is clear that the global response is modeled with the bias and that the details are captured with radial basis functions. Multi-objective optimization and the approaches used in solving such problems are briefly described in this thesis. One of the methods that proved to be efficient in solving multi-objective optimization problems (MOOP) is the strength Pareto evolutionary algorithm (SPEA2). Multi-objective optimization of a disc brake system of a heavy truck by using SPEA2 and RBF with a priori bias is performed. As a result, the possibility to reduce the weight of the system without extensive compromise in other objectives is found. Multi-objective optimization of material model parameters of an adhesive layer with the aim of improving the results of a previous study is implemented. The result of the original study is improved and a clear insight into the nature of the problem is revealed.

The initial question addressed in this thesis is how to take into account the multi-objective aspect of decision problems in inverse optimization. The most straightforward extension consists of finding a minimal adjustment of the objective functions coefficients such that a given feasible solution becomes efficient. However, there is not only a single question raised by inverse multi-objective optimization, because there is usually not a single efficient solution. The way we define inverse multi-objective

optimization takes into account this important aspect. This gives rise to many questions which are identified by a precise notation that highlights a large collection of inverse problems that could be investigated. In this thesis, a selection of inverse problems are presented and solved. This selection is motivated by their possible applications and the interesting theoretical questions they can rise in practice.
Doctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished

This thesis is concerned with multi-objective sequential decision making (MOSDM). The motivation is twofold. On the one hand, many decision problems in the domains of e.g., robotics, scheduling or games, involve the optimization of sequences of decisions. On the other hand, many real-world applications are most naturally formulated in terms of multi-objective optimization (MOO). The proposed approach extends the well-known Monte-Carlo tree search (MCTS) framework to the MOO setting, with the goal of discovering several optimal sequences of decisions through growing a single search tree. The main challenge is to propose a new reward, able to guide the exploration of the tree although the MOO setting does not enforce a total order among solutions. The main contribution of the thesis is to propose and experimentally study two such rewards, inspired from the MOO literature and assessing a solution with respect to the archive of previous solutions (Pareto archive): the hypervolume indicator and the Pareto dominance reward. The study shows the complementarity of these two criteria. The hypervolume indicator suffers from its known computational complexity; however the proposed extension thereof provides fine-grained information about the quality of solutions with respect to the current archive. Quite the contrary, the Pareto-dominance reward is linear but it provides increasingly rare information. Proofs of principle of the approach are given on artificial problems and challenges, and confirm the merits of the approach. In particular, MOMCTS is able to discover policies lying in non-convex regions of the Pareto front, contrasting with the state of the art: existing Multi-Objective Reinforcement Learning algorithms are based on linear scalarization and thus fail to sample such non-convex regions. Finally MOMCTS honorably competes with the state of the art on the 2013 MOPTSP competition.

In this thesis, we develop an evolutionary algorithm for approximating the Pareto frontier of multi-objective continuous and combinatorial optimization problems. The algorithm tries to evolve the population of solutions towards the Pareto frontier and distribute it over the frontier in order to maintain a well-spread representation. The fitness score of each solution is computed with a Tchebycheff distance function and non-dominating sorting approach. Each solution chooses its own favorable weights according to the Tchebycheff distance function. Some seed solutions at initial population and a crowding measure also help to achieve satisfactory results. In order to test the performance of our evolutionary algorithm, we use some continuous and combinatorial problems. The continuous test problems taken from the literature have special difficulties that an evolutionary algorithm has to deal with. Experimental results of our algorithm on these problems are provided. One of the combinatorial problems we address is the multi-objective knapsack problem. We carry out experiments on test data for this problem given in the literature. We work on two bi-criteria p-hub location problems and propose an evolutionary algorithm to approximate the Pareto frontiers of these problems. We test the performance of our algorithm on Turkish Postal System (PTT) data set (TPDS), AP (Australian Post) and CAB (US Civil Aeronautics Board) data sets. The main contribution of this thesis is in the field of developing a multi-objective evolutionary algorithm and applying it to a number of multi-objective continuous and combinatorial optimization problems.

This dissertation work builds upon the theoretical and experimental studies of radio frequency micro- and nano-electromechanical systems (RF M/NEMS) integrated multifunctional reconfigurable antennas (MRAs). This work focuses on three MRAs with an emphasis on a wireless local area network (WLAN), 5-6 GHz, beam tilt, and polarization reconfigurable parasitic layer-based MRA with inset micro-strip feed. The other two antennas are an X band (8-12 GHz) beam steering MRA with aperture-coupled micro-strip fed and wireless personal area network (WPAN), 60 GHz, inset micro-strip fed MRA for dual frequency and dual polarization operations. For the WLAN (5-6 GHz) MRA, a detailed description of the design methodology, which is based on the joint utilization of electromagnetic (EM) full-wave analysis and multi-objective genetic algorithm, and fundamental theoretical background of parasitic layer-based antennas are given. Various prototypes of this MRA have been fabricated and measured. The measured and simulated results for both impedance and radiation characteristics are given. The work on the MRAs operating in the X band and 60 GHz region focuses on the theoretical aspects of the designs. Different than the WLAN MRA, which uses inset fed structure, the aperture-coupled feed mechanism has been investigated with the goal of improving the bandwidth and beam-tilt capabilities of these MRAs. The simulated results are provided and the working mechanisms are described. The results show that the aperture-coupled feed mechanism is advantageous both in terms of enhanced bandwidth and beam-steering capabilities. Finally, this dissertation work concludes with plans for future work, which will build upon the findings and the results presented herein.

Many real-life optimization problems are combinatorial, i.e. they concern a choice of the best solution from a finite but exponentially large set of alternatives. Besides, the solution quality of many of these problems can often be evaluated from several points of view (a.k.a. criteria). In that case, each criterion may be described by a different objective function. Some important and well-known multicriteria scenarios are: · In investment optimization one wants to minimize risk and maximize benefits. · In travel scheduling one wants to minimize time and cost. · In circuit design one wants to minimize circuit area, energy consumption and maximize speed. · In knapsack problems one wants to minimize load weight and/or volume and maximize its economical value. The previous examples illustrate that, in many cases, these multiple criteria are incommensurate (i.e., it is difficult or impossible to combine them into a single criterion) and conflicting (i.e., solutions that are good with respect one criterion are likely to be bad with respect to another). Taking into account simultaneously the different criteria is not trivial and several notions of optimality have been proposed. Independently of the chosen notion of optimality, computing optimal solutions represents an important current research challenge. Graphical models are a knowledge representation tool widely used in the Artificial Intelligence field. They seem to be specially suitable for combinatorial problems. Roughly, graphical models are graphs in which nodes represent variables and the (lack of) arcs represent conditional independence assumptions. In addition to the graph structure, it is necessary to specify its micro-structure which tells how particular combinations of instantiations of interdependent variables interact. The graphical model framework provides a unifying way to model a broad spectrum of systems and a collection of general algorithms to efficiently solve them. In this Thesis we integrate multi-objective optimization problems into the graphical model paradigm and study how algorithmic techniques developed in the graphical model context can be extended to multi-objective optimization problems. As we show, multiobjective optimization problems can be formalized as a particular case of graphical models using the semiring-based framework. It is, to the best of our knowledge, the first time that graphical models in general, and semiring-based problems in particular are used to model an optimization problem in which the objective function is partially ordered. Moreover, we show that most of the solving techniques for mono-objective optimization problems can be naturally extended to the multi-objective context. The result of our work is the mathematical formalization of multi-objective optimization problems and the development of a set of multiobjective solving algorithms that have been proved to be efficient in a number of benchmarks.
Muchos problemas reales de optimización son combinatorios, es decir, requieren de la elección de la mejor solución (o solución óptima) dentro de un conjunto finito pero exponencialmente grande de alternativas. Además, la mejor solución de muchos de estos problemas es, a menudo, evaluada desde varios puntos de vista (también llamados criterios). Es este caso, cada criterio puede ser descrito por una función objetivo. Algunos escenarios multi-objetivo importantes y bien conocidos son los siguientes: · En optimización de inversiones se pretende minimizar los riesgos y maximizar los beneficios. · En la programación de viajes se quiere reducir el tiempo de viaje y los costes. · En el diseño de circuitos se quiere reducir al mínimo la zona ocupada del circuito, el consumo de energía y maximizar la velocidad. · En los problemas de la mochila se quiere minimizar el peso de la carga y/o el volumen y maximizar su valor económico. Los ejemplos anteriores muestran que, en muchos casos, estos criterios son inconmensurables (es decir, es difícil o imposible combinar todos ellos en un único criterio) y están en conflicto (es decir, soluciones que son buenas con respecto a un criterio es probable que sean malas con respecto a otra). Tener en cuenta de forma simultánea todos estos criterios no es trivial y para ello se han propuesto diferentes nociones de optimalidad. Independientemente del concepto de optimalidad elegido, el cómputo de soluciones óptimas representa un importante desafío para la investigación actual. Los modelos gráficos son una herramienta para la represetanción del conocimiento ampliamente utilizados en el campo de la Inteligencia Artificial que parecen especialmente indicados en problemas combinatorios. A grandes rasgos, los modelos gráficos son grafos en los que los nodos representan variables y la (falta de) arcos representa la interdepencia entre variables. Además de la estructura gráfica, es necesario especificar su (micro-estructura) que indica cómo interactúan instanciaciones concretas de variables interdependientes. Los modelos gráficos proporcionan un marco capaz de unificar el modelado de un espectro amplio de sistemas y un conjunto de algoritmos generales capaces de resolverlos eficientemente. En esta tesis integramos problemas de optimización multi-objetivo en el contexto de los modelos gráficos y estudiamos cómo diversas técnicas algorítmicas desarrolladas dentro del marco de los modelos gráficos se pueden extender a problemas de optimización multi-objetivo. Como mostramos, este tipo de problemas se pueden formalizar como un caso particular de modelo gráfico usando el paradigma basado en semi-anillos (SCSP). Desde nuestro conocimiento, ésta es la primera vez que los modelos gráficos en general, y el paradigma basado en semi-anillos en particular, se usan para modelar un problema de optimización cuya función objetivo está parcialmente ordenada. Además, mostramos que la mayoría de técnicas para resolver problemas monoobjetivo se pueden extender de forma natural al contexto multi-objetivo. El resultado de nuestro trabajo es la formalización matemática de problemas de optimización multi-objetivo y el desarrollo de un conjunto de algoritmos capaces de resolver este tipo de problemas. Además, demostramos que estos algoritmos son eficientes en un conjunto determinado de benchmarks.

In this thesis, the basic principles and concepts of single and multi-objective Genetic Algorithms (GA) are reviewed. Two algorithms, one for single objective and the other for multi-objective problems, which are believed to be more efficient are described in details. The algorithms are coded with MATLAB and applied on several test functions. The results are compared with the existing solutions in literatures and shows promising results. Obtained pareto-fronts are exactly similar to the true pareto-fronts with a good spread of solution throughout the optimal region. Constraint handling techniques are studied and applied in the two algorithms. Constrained benchmarks are optimized and the outcomes show the ability of algorithm in maintaining solutions in the entire pareto-optimal region. In the end, a hybrid method based on the combination of the two algorithms is introduced and the performance is discussed. It is concluded that no significant strength is observed within the approach and more research is required on this topic. For further investigation on the performance of the proposed techniques, implementation on real-world engineering applications are recommended.

Receiver operating characteristic (ROC) curves are widely used for evaluating classifier performance, having been applied to e.g. signal detection, medical diagnostics and safety critical systems. They allow examination of the trade-offs between true and false positive rates as misclassification costs are varied. Examination of the resulting graphs and calcu- lation of the area under the ROC curve (AUC) allows assessment of how well a classifier is able to separate two classes and allows selection of an operating point with full knowledge of the available trade-offs. In this thesis a multi-objective evolutionary algorithm (MOEA) is used to find clas- sifiers whose ROC graph locations are Pareto optimal. The Relevance Vector Machine (RVM) is a state-of-the-art classifier that produces sparse Bayesian models, but is unfor- tunately prone to overfitting. Using the MOEA, hyper-parameters for RVM classifiers are set, optimising them not only in terms of true and false positive rates but also a novel measure of RVM complexity, thus encouraging sparseness, and producing approximations to the Pareto front. Several methods for regularising the RVM during the MOEA train- ing process are examined and their performance evaluated on a number of benchmark datasets demonstrating they possess the capability to avoid overfitting whilst producing performance equivalent to that of the maximum likelihood trained RVM. A common task in bioinformatics is to identify genes associated with various genetic conditions by finding those genes useful for classifying a condition against a baseline. Typ- ically, datasets contain large numbers of gene expressions measured in relatively few sub- jects. As a result of the high dimensionality and sparsity of examples, it can be very easy to find classifiers with near perfect training accuracies but which have poor generalisation capability. Additionally, depending on the condition and treatment involved, evaluation over a range of costs will often be desirable. An MOEA is used to identify genes for clas- sification by simultaneously maximising the area under the ROC curve whilst minimising model complexity. This method is illustrated on a number of well-studied datasets and ap- plied to a recent bioinformatics database resulting from the current InChianti population study. Many classifiers produce “hard”, non-probabilistic classifications and are trained to find a single set of parameters, whose values are inevitably uncertain due to limited available training data. In a Bayesian framework it is possible to ameliorate the effects of this parameter uncertainty by averaging over classifiers weighted by their posterior probabil- ity. Unfortunately, the required posterior probability is not readily computed for hard classifiers. In this thesis an Approximate Bayesian Computation Markov Chain Monte Carlo algorithm is used to sample model parameters for a hard classifier using the AUC as a measure of performance. The ability to produce ROC curves close to the Bayes op- timal ROC curve is demonstrated on a synthetic dataset. Due to the large numbers of sampled parametrisations, averaging over them when rapid classification is needed may be impractical and thus methods for producing sparse weightings are investigated.

Industrial robots are the most widely manufactured and utilized type of robots in industries. Improving the design process of industrial robots would lead to further developments in robotics industries. Consequently, other dependant industries would be benefited. Therefore, there is an effort to make the design process more and more efficient and reliable. The design of industrial robots requires studies in various fields. Engineering softwares are the tools which facilitate and accelerate the robot design processes such as dynamic simulation, structural analysis, optimization, control and so forth. Therefore, designing a framework to automate the robot design process such that different tools interact automatically would be beneficial. In this thesis, the goal is to investigate the feasibility of integrating tools from different domains such as geometry modeling, dynamic simulation, finite element analysis and optimization in order to obtain an industrial robot design and optimization framework. Meanwhile, Meta modeling is used to replace the time consuming design steps. In the optimization step, various optimization algorithms are compared based on their performance and the best suited algorithm is selected. As a result, it is shown that the objectives are achievable in a sense that finite element analysis can be efficiently integrated with the other tools and the results can be optimized during the design process. A holistic framework which can be used for design of robots with several degrees of freedom is introduced at the end.

Despite the tremendous popularity of mobile applications, mobile testing still relies heavily on manual testing. This thesis presents mobile test automation approaches based on multi-objective search. We introduce three approaches: Sapienz (for native Android app testing), Octopuz (for hybrid/web JavaScript app testing) and Polariz (for using crowdsourcing to support search-based mobile testing). These three approaches represent the primary scientific and technical contributions of the thesis. Since crowdsourcing is, itself, an emerging research area, and less well understood than search-based software engineering, the thesis also provides the first comprehensive survey on the use of crowdsourcing in software testing (in particular) and in software engineering (more generally). This survey represents a secondary contribution. Sapienz is an approach to Android testing that uses multi-objective search-based testing to automatically explore and optimise test sequences, minimising their length, while simultaneously maximising their coverage and fault revelation. The results of empirical studies demonstrate that Sapienz significantly outperforms both the state-of-the-art technique Dynodroid and the widely-used tool, Android Monkey, on all three objectives. When applied to the top 1,000 Google Play apps, Sapienz found 558 unique, previously unknown crashes. Octopuz reuses the Sapienz multi-objective search approach for automated JavaScript testing, aiming to investigate whether it replicates the Sapienz’ success on JavaScript testing. Experimental results on 10 real-world JavaScript apps provide evidence that Octopuz significantly outperforms the state of the art (and current state of practice) in automated JavaScript testing. Polariz is an approach that combines human (crowd) intelligence with machine (computational search) intelligence for mobile testing. It uses a platform that enables crowdsourced mobile testing from any source of app, via any terminal client, and by any crowd of workers. It generates replicable test scripts based on manual test traces produced by the crowd workforce, and automatically extracts from these test traces, motif events that can be used to improve search-based mobile testing approaches such as Sapienz.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Civil and Environmental Engineering, 2017.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 83-84).
Trussed arch bridges are commonly used to attain big spans. They are efficient structures that offer a wide range of geometries, materials, and topologies. This thesis studies the influence of the geometry and topology of arch bridges on both their structural performance relayed by the maximum deflection and their structural weight. Various materials are also considered to calculate the embodied carbon emission and investigate the environmental impact of arch bridges. Gustave Eiffel's Garabit Viaduct is used as a design precedent for this study. 2-D and 3-D parametric models of the arch bridge are realized using Grasshopper [8]. Changing the geometric parameters in addition to the topology enables the investigation of the bridge's performance. The cross sections are automatically optimized in each case. Furthermore, a multi-objective optimization process was run on the bridge to examine the tradeoffs between the deflection and the self-weight. The weight-oriented optimization allows saving more than 60% of the weight compared to the original structure. Analyzing the different resulting designs proves that increasing the depth at the arch's crown and the depth at the base of the arch leads to better deflection results. It also demonstrates that using a denser truss structure leads to a lighter structure.
by Khaoula Msaaf.
M. Eng.

Les problèmes multi-objectifs se posent dans plusieurs scénarios réels dans le monde où on doit trouver une solution optimale qui soit un compromis entre les différents objectifs en compétition. Dans cette thèse, on étudie et on propose des algorithmes pour traiter les problèmes des machines d’apprentissage multi-objectif. On étudie deux méthodes d’apprentissage multi-objectif en détail. Dans la première méthode, on étudie le problème de trouver le classifieur optimal pour réaliser des mesures de performances multivariées. Dans la seconde méthode, on étudie le problème de classer des informations diverses dans les missions de recherche des informations
Multi-objective problems arise in many real world scenarios where one has to find an optimal solution considering the trade-off between different competing objectives. Typical examples of multi-objective problems arise in classification, information retrieval, dictionary learning, online learning etc. In this thesis, we study and propose algorithms for multi-objective machine learning problems. We give many interesting examples of multi-objective learning problems which are actively persuaded by the research community to motivate our work. Majority of the state of the art algorithms proposed for multi-objective learning comes under what is called “scalarization method”, an efficient algorithm for solving multi-objective optimization problems. Having motivated our work, we study two multi-objective learning tasks in detail. In the first task, we study the problem of finding the optimal classifier for multivariate performance measures. The problem is studied very actively and recent papers have proposed many algorithms in different classification settings. We study the problem as finding an optimal trade-off between different classification errors, and propose an algorithm based on cost-sensitive classification. In the second task, we study the problem of diverse ranking in information retrieval tasks, in particular recommender systems. We propose an algorithm for diverse ranking making use of the domain specific information, and formulating the problem as a submodular maximization problem for coverage maximization in a weighted similarity graph. Finally, we conclude that scalarization based algorithms works well for multi-objective learning problems. But when considering algorithms for multi-objective learning problems, scalarization need not be the “to go” approach. It is very important to consider the domain specific information and objective functions. We end this thesis by proposing some of the immediate future work, which are currently being experimented, and some of the short term future work which we plan to carry out

Dans cette thèse, nous nous intéressons à l'optimisation simultanée de fonctions coûteuses à évaluer et dépendant d'un grand nombre de paramètres. Cette situation est rencontrée dans de nombreux domaines tels que la conception de systèmes en ingénierie au moyen de simulations numériques. L'optimisation bayésienne, reposant sur des méta-modèles (processus gaussiens) est particulièrement adaptée à ce contexte.La première partie de cette thèse est consacrée au développement de nouvelles méthodes d'optimisation multi-objectif assistées par méta-modèles. Afin d'améliorer le temps d'atteinte de solutions Pareto optimales, un critère d'acquisition est adapté pour diriger l'algorithme vers une région de l'espace des objectifs plébiscitée par l'utilisateur ou, en son absence, le centre du front de Pareto introduit dans nos travaux. Outre le ciblage, la méthode prend en compte le budget d'optimisation, afin de restituer un éventail de solutions optimales aussi large que possible, dans la limite des ressources disponibles.Dans un second temps, inspirée par l'optimisation de forme, une approche d'optimisation avec réduction de dimension est proposée pour contrer le fléau de la dimension. Elle repose sur la construction, par analyse en composantes principales de solutions candidates, de variables auxiliaires adaptées au problème, hiérarchisées et plus à même de décrire les candidats globalement. Peu d'entre elles suffisent à approcher les solutions, et les plus influentes sont sélectionnées et priorisées au sein d'un processus gaussien additif. Cette structuration des variables est ensuite exploitée dans l'algorithme d'optimisation bayésienne qui opère en dimension réduite
This thesis focuses on the simultaneous optimization of expensive-to-evaluate functions that depend on a high number of parameters. This situation is frequently encountered in fields such as design engineering through numerical simulation. Bayesian optimization relying on surrogate models (Gaussian Processes) is particularly adapted to this context.The first part of this thesis is devoted to the development of new surrogate-assisted multi-objective optimization methods. To improve the attainment of Pareto optimal solutions, an infill criterion is tailored to direct the search towards a user-desired region of the objective space or, in its absence, towards the Pareto front center introduced in our work. Besides targeting a well-chosen part of the Pareto front, the method also considers the optimization budget in order to provide an as wide as possible range of optimal solutions in the limit of the available resources.Next, inspired by shape optimization problems, an optimization method with dimension reduction is proposed to tackle the curse of dimensionality. The approach hinges on the construction of hierarchized problem-related auxiliary variables that can describe all candidates globally, through a principal component analysis of potential solutions. Few of these variables suffice to approach any solution, and the most influential ones are selected and prioritized inside an additive Gaussian Process. This variable categorization is then further exploited in the Bayesian optimization algorithm which operates in reduced dimension

Most of the decisions in real-life problems need to be made in the absence of complete knowledge about the consequences of the decision. Furthermore, in some of these problems, the probability and/or the number of different outcomes are also unknown (named deep uncertainty). Therefore, all the probability-based approaches (such as stochastic programming) are unable to address these problems. On the other hand, involving various stakeholders with different (possibly conflicting) criteria in the problems brings additional complexity. The main aim and primary motivation for writing this thesis have been to deal with deep uncertainty in Multi-Criteria Decision-Making (MCDM) problems, especially with long-term decision-making processes such as strategic planning problems. To achieve these aims, we first introduced a two-stage scenario-based structure for dealing with deep uncertainty in Multi-Objective Optimisation (MOO)/MCDM problems. The proposed method extends the concept of two-stage stochastic programming with recourse to address the capability of dealing with deep uncertainty through the use of scenario planning rather than statistical expectation. In this research, scenarios are used as a dimension of preference (a component of what we term the meta-criteria) to avoid problems relating to the assessment and use of probabilities under deep uncertainty. Such scenario-based thinking involved a multi-objective representation of performance under different future conditions as an alternative to expectation, which fitted naturally into the broader multi-objective problem context. To aggregate these objectives of the problem, the Generalised Goal Programming (GGP) approach is used. Due to the capability of this approach to handle large numbers of objective functions/criteria, the GGP is significantly useful in the proposed framework. Identifying the goals for each criterion is the only action that the Decision Maker (DM) needs to take without needing to investigate the trade-offs between different criteria. Moreover, the proposed two-stage framework has been expanded to a three-stage structure and a moving horizon concept to handle the existing deep uncertainty in more complex problems, such as strategic planning. As strategic planning problems will deal with more than two stages and real processes are continuous, it follows that more scenarios will continuously be unfolded that may or may not be periodic. "Stages", in this study, are artificial constructs to structure thinking of an indefinite future. A suitable length of the planning window and stages in the proposed methodology are also investigated. Philosophically, the proposed two-stage structure always plans and looks one step ahead while the three-stage structure considers the conditions and consequences of two upcoming steps in advance, which fits well with our primary objective. Ignoring long-term consequences of decisions as well as likely conditions could not be a robust strategic approach. Therefore, generally, by utilising the three-stage structure, we may expect a more robust decision than with a two-stage representation. Modelling time preferences in multi-stage problems have also been introduced to solve the fundamental problem of comparability of the two proposed methodologies because of the different time horizon, as the two-stage model is ignorant of the third stage. This concept has been applied by a differential weighting in models. Importance weights, then, are primarily used to make the two- and three-stage models more directly comparable, and only secondarily as a measure of risk preference. Differential weighting can help us apply further preferences in the model and lead it to generate more preferred solutions. Expanding the proposed structure to the problems with more than three stages which usually have too many meta-scenarios may lead us to a computationally expensive model that cannot easily be solved, if it all. Moreover, extension to a planning horizon that too long will not result in an exact plan, as nothing in nature is predictable to this level of detail, and we are always surprised by new events. Therefore, beyond the expensive computation in a multi-stage structure for more than three stages, defining plausible scenarios for far stages is not logical and even impossible. Therefore, the moving horizon models in a T-stage planning window has been introduced. To be able to run and evaluate the proposed two- and three-stage moving horizon frameworks in longer planning horizons, we need to identify all plausible meta-scenarios. However, with the assumption of deep uncertainty, this identification is almost impossible. On the other hand, even with a finite set of plausible meta-scenarios, comparing and computing the results in all plausible meta-scenarios are hardly possible, because the size of the model grows exponentially by raising the length of the planning horizon. Furthermore, analysis of the solutions requires hundreds or thousands of multi-objective comparisons that are not easily conceivable, if it all. These issues motivated us to perform a Simulation-Optimisation study to simulate the reasonable number of meta-scenarios and enable evaluation, comparison and analysis of the proposed methods for the problems with a T-stage planning horizon. In this Simulation-Optimisation study, we started by setting the current scenario, the scenario that we were facing it at the beginning of the period. Then, the optimisation model was run to get the first-stage decisions which can implement immediately. Thereafter, the next scenario was randomly generated by using Monte Carlo simulation methods. In deep uncertainty, we do not have enough knowledge about the likelihood of plausible scenarios nor the probability space; therefore, to simulate the deep uncertainty we shall not use anything of scenario likelihoods in the decision models. The two- and three-stage Simulation-Optimisation algorithms were also proposed. A comparison of these algorithms showed that the solutions to the two-stage moving horizon model are feasible to the other pattern (three-stage). Also, the optimal solution to the three-stage moving horizon model is not dominated by any solutions of the other model. So, with no doubt, it must find better, or at least the same, goal achievement compared to the two-stage moving horizon model. Accordingly, the three-stage moving horizon model evaluates and compares the optimal solution of the corresponding two-stage moving horizon model to the other feasible solutions, then, if it selects anything else it must either be better in goal achievement or be robust in some future scenarios or a combination of both. However, the cost of these supremacies must be considered (as it may lead us to a computationally expensive problem), and the efficiency of applying this structure needs to be approved. Obviously, using the three-stage structure in comparison with the two-stage approach brings more complexity and calculations to the models. It is also shown that the solutions to the three-stage model would be preferred to the solutions provided by the two-stage model under most circumstances. However, by the "efficiency" of the three-stage framework in our context, we want to know that whether utilising this approach and its solutions is worth the expense of the additional complexity and computation. The experiments in this study showed that the three-stage model has advantages under most circumstances(meta-scenarios), but that the gains are quite modest. This issue is frequently observed when comparing these methods in problems with a short-term (say less than five stages) planning window. Nevertheless, analysis of the length of the planning horizon and its effects on the solutions to the proposed frameworks indicate that utilising the three-stage models is more efficient for longer periods because the differences between the solutions of the two proposed structures increase by any iteration of the algorithms in moving horizon models. Moreover, during the long-term calculations, we noticed that the two-stage algorithm failed to find the optimal solutions for some iterations while the three-stage algorithm found the optimal value in all cases. Thus, it seems that for the planning horizons with more than ten stages, the efficiency of the three-stage model be may worth the expenses of the complexity and computation. Nevertheless, if the DM prefers to not use the three-stage structure because of the complexity and/or calculations, the two-stage moving horizon model can provide us with some reasonable solutions, although they might not be as good as the solutions generated by a three-stage framework. Finally, to examine the power of the proposed methodology in real cases, the proposed two-stage structure was applied in the sugarcane industry to analyse the whole infrastructure of the sugar and bioethanol Supply Chain (SC) in such a way that all economics (Max profit), environmental (Min CO₂), and social benefits (Max job-creations) were optimised under six key uncertainties, namely sugarcane yield, ethanol and refined sugar demands and prices, and the exchange rate. Moreover, one of the critical design questions - that is, to design the optimal number and technologies as well as the best place(s) for setting up the ethanol plant(s) - was also addressed in this study. The general model for the strategic planning of sugar- bioethanol supply chains (SC) under deep uncertainty was formulated and also examined in a case study based on the South African Sugar Industry. This problem is formulated as a Scenario-Based Mixed-Integer Two-Stage Multi-Objective Optimisation problem and solved by utilising the Generalised Goal Programming Approach. To sum up, the proposed methodology is, to the best of our knowledge, a novel approach that can successfully handle the deep uncertainty in MCDM/MOO problems with both short- and long-term planning horizons. It is generic enough to use in all MCDM problems under deep uncertainty. However, in this thesis, the proposed structure only applied in Linear Problems (LP). Non-linear problems would be an important direction for future research. Different solution methods may also need to be examined to solve the non-linear problems. Moreover, many other real-world optimisation and decision-making applications can be considered to examine the proposed method in the future.

Virtual Reality is a growing sector with applications in cybertherapy, video games, and entertainment. There exist several locomotion techniques that al low movement in the virtual environment. A joystick, treadmill, or gestures that mimic walking are some techniques used. However, none of these approaches are as intuitive and immersive as real walking in Virtual Reality. How far a user can walk in Virtual Reality is limited by ones’ surroundings. The virtual environments need to fit inside the Tracked Space in which the trackers of the VR-headset reach. Impossible Spaces introduced the concept of overlap ping layouts. A side effect of using overlapping layouts is that users perceive the Tracked Space to be larger. Flexible Spaces is a procedural approach for redirection as it generates walkable corridors inside the virtual environment. The corridors are randomly generated and connect rooms inside the virtual environment. The features of the corridors impact the users’ sensation of space inside the Tracked Space. This research investigates the properties of Flexi ble Spaces and examines if it is advantageous to extend it with multi-objective optimization. It does so by giving designers the ability to have preferences over the corridors concerning length and amount of corners and optimize to decrease the overlap perception. It was evaluated with rectangular and com plex layouts. Initial findings suggest that Flexible Spaces are appropriate to extend with multi-objective optimization. The generated corridors for the testing environment decreased overlapping close to doors and lied within the given preferences. In an unoptimized state, it was able to produce more than 25 optimal, or near-optimal corridors in a second. Extending Flexible Spaces with multi-objective optimization shows potential as it restricts the randomness of the generated corridors. However, it is important to understand what the algorithm is optimizing towards, and the trade-offs of the objectives concerning spatial perception on overlapping layouts.
Virtual Reality är en växande sektor med tillämpningar inom terapi, spel och underhållning. Det finns flertalet förflyttningstekniker som möjliggör förflyttning i virtuella miljöer. Handkontroll, gångband och gester som imiterar gång, är beprövade tekniker. Men ingen är lika intuitiv och uppslukande som naturlig gång. Dock så begränsas den naturliga gången av den fysiska omgivning en, vilket även gäller för virtuella miljöer. Impossible Spaces introducerade konceptet med överlappande planlösningar i virtuella miljöer. En bieffekt av överlappande planlösningar är att den begränsade ytan kan upplevas större. Flexible Spaces är en procedurell förflyttningsteknik. Användaren förflyttas mellan olika rum i den virtuella miljön genom att gå i virtuella korridorer. Planlösningen och korridorens utformning har en inverkan i användarens upp levda rymd. Den här uppsatsen undersöker egenskaperna i Flexible Spaces och utvidgar den med flermålsoptimering. Optimeringsalgoritmen är utformad att ge designers förmågan att ha preferenser över korridorens längd, antal hörn, samtidigt som den optimerar mot att minska den upplevda överlappningen. Algoritmen testades mot en rektangulär och en komplex planlösning. Inledande resultat föreslår att Flexible Spaces är lämplig att utvidga med flermålsoptimering. De genererade korridorerna efterliknade den föreslagna designen och minskade överlappningen nära rummens dörrar. I ett ooptimerat tillstånd, så genererade den mer än 25 korridorer under en sekund. Notera att det är av hög relevans att förstå de underliggande principerna som algoritmen optimerar mot, samt att vara medveten om avvägningen mellan de olika målen relaterat till upplevelsen av överlappande planlösningar.

Additive Manufacturing (AM) has demonstrated great potential to advance product design and manufacturing, and has showed higher flexibility than conventional manufacturing techniques for the production of small volume, complex and customised components. In an economy focused on the need to develop customised and hi-tech products, there is increasing interest in establishing AM technologies as a more efficient production approach for high value products such as aerospace and biomedical products. Nevertheless, the use of AM processes, for even small to medium volume production faces a number of issues in the current state of the technology. AM production is normally used for making parts with complex geometry which implicates the assessment of numerous processing options or choices; the wrong choice of process parameters can result in poor surface quality, onerous manufacturing time and energy waste, and thus increased production costs and resources. A few commonly used AM processes require the presence of cellular support structures for the production of overhanging parts. Depending on the object complexity their removal can be impossible or very time (and resources) consuming. Currently, there is a lack of tools to advise the AM operator on the optimal choice of process parameters. This prevents the diffusion of AM as an efficient production process for enterprises, and as affordable access to democratic product development for individual users. Research in literature has focused mainly on the optimisation of single criteria for AM production. An integrated predictive modelling and optimisation technique has not yet been well established for identifying an efficient process set up for complicated products which often involve critical building requirements. For instance, there are no robust methods for the optimal design of complex cellular support structures, and most of the software commercially available today does not provide adequate guidance on how to optimally orientate the part into the machine bed, or which particular combination of cellular structures need to be used as support. The choice of wrong support and orientation can degenerate into structure collapse during an AM process such as Selective Laser Melting (SLM), due to the high thermal stress in the junctions between fillets of different cells. Another issue of AM production is the limited parts’ surface quality typically generated by the discrete deposition and fusion of material. This research has focused on the formation of surface morphology of AM parts. Analysis of SLM parts showed that roughness measured was different from that predicted through a classic model based on pure geometrical consideration on the stair step profile. Experiments also revealed the presence of partially bonded particles on the surface; an explanation of this phenomenon has been proposed. Results have been integrated into a novel mathematical model for the prediction of surface roughness of SLM parts. The model formulated correctly describes the observed trend of the experimental data, and thus provides an accurate prediction of surface roughness. This thesis aims to deliver an effective computational methodology for the multi- objective optimisation of the main building conditions that affect process efficiency of AM production. For this purpose, mathematical models have been formulated for the determination of parts’ surface quality, manufacturing time and energy consumption, and for the design of optimal cellular support structures. All the predictive models have been used to evaluate multiple performance and costs objectives; all the objectives are typically contrasting; and all greatly affected by the part’s build orientation. A multi-objective optimisation technique has been developed to visualise and identify optimal trade-offs between all the contrastive objectives for the most efficient AM production. Hence, this thesis has delivered a decision support system to assist the operator in the "process planning" stage, in order to achieve optimal efficiency and sustainability in AM production through maximum material, time and energy savings.

In this thesis, robust and multi-objective portfolio selection problem will be studied. New models and computational algorithms will be developed to solve the proposed models. In particularly, we have studied multi-objective portfolio selection with inexact information on investment return and covariance matrix. The problems have been transformed into easily solvable problems through theoretical analysis. Numerical experiments are presented to validate the methods.

In this thesis, we develop two exact algorithms and a heuristic procedure for Multiobjective Combinatorial Optimization Problems (MOCO). Our exact algorithms guarantee to generate all nondominated solutions of any MOCO problem. We test the performance of the algorithms on randomly generated problems including the Multiobjective Knapsack Problem, Multi-objective Shortest Path Problem and Multi-objective Spanning Tree Problem. Although we showed the algorithms work much better than the previous ones, we also proposed a fast heuristic method to approximate efficient frontier since it will also be applicable for real-sized problems. Our heuristic approach is based on fitting a surface to approximate the efficient frontier. We experiment our heuristic on randomly generated problems to test how well the heuristic procedure approximates the efficient frontier. Our results showed the heuristic method works well.

ABSTRACT PERFORMANCE MEASUREMENT IN MULTI OBJECTIVE COMBINATORIAL OPTIMIZATION Bozkurt, Bilge M.Sc., Department of Industrial Engineering Supervisor: Prof. Dr. Murat Kö
ksalan September 2007, 96 pages In this study we address the problem of measuring the quality of different sets of nondominated solutions obtained by different approaches in multi objective combinatorial optimization (MOCO). We propose a new measure that quantitatively compares the sets of nondominated solutions, without needing an efficient frontier. We develop the measure for bi-criteria and more than two criteria cases separately. Rather than considering only the supported solutions in the evaluation, the measure captures both supported and unsupported solutions through utilizing weighted Tchebycheff function characteristics. We also adapt this method for determining the neighborhood relations on the weight space for both bi-criteria and more than two criteria cases. We check the consistency of the neighborhood assumption on the objective space with the neighborhood relations on the weight space by this measure and obtain highly good results. Keywords: Multi objective combinatorial optimization, performance measurement

Public debt managers have a certain range of borrowing instruments varying in their interest rate type, currency, maturity etc. at their disposal and have to find an appropriate combination of those while raising debt on behalf of the government. In selecting the combination of instruments to be issued, i.e. the borrowing strategy to be pursued for a certain period of time, debt managers need to consider several objectives that are conflicting by their nature, and the uncertainty associated with the outcomes of the decisions made. The objective of this thesis is to propose an approach to support the decision making process regarding sovereign debt issuance. We incorporate Multi-Criteria Decision Making (MCDM) tools using a multi-period stochastic programming model that takes into account sequential decisions concerned with debt issuance policies. The model is then applied for public debt management in Turkey.

Due to the complexity of multi-objective combinatorial optimization problems (MOCO), metaheuristics like multi-objective evolutionary algorithms (MOEA) are gaining importance to obtain a well-converged and well-dispersed Pareto-optimal frontier approximation. In this study, of the well-known MOCO problems, single-dimensional multi-objective knapsack problem and multi-objective assignment problem are taken into consideration. We develop a steady-state and elitist MOEA in order to approximate the Pareto-optimal frontiers. We utilize a territory concept in order to provide diversity over the Pareto-optimal frontiers of various problem instances. The motivation behind the territory definition is to attach the algorithm the advantage of fast execution by eliminating the need for an explicit diversity preserving operator. We also develop an interactive preference incorporation mechanism to converge to the regions that are of special interest for the decision maker by interacting with him/her during the optimization process.

Path planning is a crucial issue for virtual environments where autonomous agents try to navigate from a specific location to a desired one. There are several algorithms developed for path planning, but several domain requirements make engineering of these algorithms difficult. In complex environments, considering single objective for searching and finding optimal or sub-optimal paths becomes insufficient. Thus, multi objective cases are distinguished and more complicated algorithms to be employed is required. It can be seen that more realistic and robust results can be obtained with these algorithms because they expand solution perspective into more than one criteria. Today, they are used in various games and simulation applications. On the other hand, most of these algorithms are off-line and delimitate interactive behaviours and dynamics of real world into a stationary virtuality. This situation reduces the solution quality and boundaries. Hence, the necessity of solutions where multi objectivity is considered in a dynamic environment is obvious. With this motivation, in this work, a novel multi objective incremental algorithm, MOD* Lite, is proposed. It is based on a known complete incremental search algorithm, D* Lite. Solution quality and execution time requirements of MOD* Lite are compared with existing complete multi objective off-line search algorithm, MOA*, and better results are obtained.

A reconfigurable manufacturing system (RMS) is designed for rapid adjustment of manufacturing capacity and functionality in response to market changes. An RMS consists of a number of reconfigurable machine tools (RMTs) which can process different jobs by quickly changing processing modules. The potential benefits of an RMS may not be achieved if an RMS is not properly designed. Most of the related studies focus on a few individual technical issues, in particular on modularity or configurability of individual RMTs. Other important concerns such as cost and processing accuracy have not been adequately addressed. As a result, many highly reconfigurable manufacturing systems turn out to be unprofitable. For the above reason, this study focuses on optimization of RMT design, including the design of modules and module warehouse, with consideration of three factors: configurability, cost and accuracy. (Abstract shortened by UMI.)

This thesis explores how to use Multi-Objective Evolutionary Algorithms (MOEA)to solve problems that are not explicitly defined as multi-objective problems. Aneuroevolution technique consisting of combining a multi-objective evolutionaryalgorithm called NSGA-II and artificial neural networks (ANN) based on Neu-roEvolution of Augmented Topoligies (NEAT) were used to develop a systemthat created controllers for a version of the Super Mario Bros game called MarioAI. Experiments were conducted to measure different ways to define objectivesfor MOEAs in Mario AI, how using these objectives as a basis for a scalar fitnessfunction would affect a genetic algorithm and to examine how to use ensemblesto combine individuals of a pareto front into a single controller that would beable to display the strengths of all of the individual controllers.The results show that adding sub-goals as objectives together with the main goalcould have a positive effect for a MOEA and that the same sub-goals could alsogive a positive effect when applied to the scalar fitness of a genetic algorithm.It is however not trivial to decide which sub-goals to use, as most of the chosenobjectives were found to have a negative impact on the controllers, even whenselected based on the authors? expert knowledge about the game domain. Usingbasic behaviours that the controller has to use in order to play well as objectiveshad a negative effect on the controllers and the controllers were able to learnthese behaviors even without using them as objectives.

This thesis contains several contributions to the theory of optimality conditions in single- and multi-objective optimization. The main result provides an answer to the following, apparently open, question in mathematical welfare economics: Given a feasible decision, find a saddle-point condition which is both necessary and sufficient that the decision is Pareto optimal for convex objectives and convex constraints. This result is then extended to convex multi-objective parametric optimization and to a large class of nonconvex multi-objective programs.

In the real world, there are many problems requiring the best solution to satisfy numerous objectives and therefore a need for suitable Multi-Objective Optimisation methods. Various Multi-Objective solvers have been developed recently. The classical method is easily implemented but requires repetitive program runs and does not generate a true "Pareto" optimal set. Intelligent methods are increasingly employed, especially population-based optimisation methods to generate the Pareto front in a single run. The Bees Algorithm is a newly developed population-based optimisation algorithm which has been verified in many fields. However, it is limited to solving single optimisation problems. To apply the Bees Algorithm to a Multi- Objective Optimisation Problem, either the problem is converted to single objective optimisation or the Bees Algorithm modified to function as a Multi- Objective solver. To make a problem into a single objective one, the weighted sum method is employed. However, due to failings of this classical method, a new approach is developed to generate a true Pareto front by a single run. This work also introduces an enhanced Bees Algorithm. A new dynamic selection procedure improves the Bees Algorithm by reducing the number of parameters and new neighbourhood search methods are adopted to optimise the Pareto front. The enhanced algorithm has been tested on Multi-Objective benchmark functions and the classical Environmental/Economic power Dispatch Problem (EEDP). The results obtained compare well with those produced by other population- based algorithms. Due to recent trends in renewable energy systems, it is necessary to have a new model of the EEDP. Therefore, the EEDP was amended in conjunction with the Bees Algorithm to identify the best design in terms of energy performance and carbon emission reduction by adopting zero and low carbon technologies. This computer-based tool supports the decision making process in the design of a Low-Carbon City.

Safety systems are designed to prevent the occurrence of certain conditions and their future development into a hazardous situation. The consequence of the failure of a safety system of a potentially hazardous industrial system or process varies from minor inconvenience and cost to personal injury, significant economic loss and death. To minimise the likelihood of a hazardous situation, safety systems must be designed to maximise their availability. Therefore, the purpose of this thesis is to propose an effective safety system design optimization scheme. A multi-objective genetic algorithm has been adopted, where the criteria catered for includes unavailability, cost, spurious trip and maintenance down time. Analyses of individual system designs are carried out using the latest advantages of the fault tree analysis technique and the binary decision diagram approach (BDD). The improved strength Pareto evolutionary approach (SPEA2) is chosen to perform the system optimization resulting in the final design specifications. The practicality of the developed approach is demonstrated initially through application to a High Integrity Protection System (HIPS) and subsequently to test scalability using the more complex Firewater Deluge System (FDS). Computer code has been developed to carry out the analysis. The results for both systems are compared to those using a single objective optimization approach (GASSOP) and exhaustive search. The overall conclusions show a number of benefits of the SPEA2 based technique application to the safety system design optimization. It is common for safety systems to feature dependency relationships between its components. To enable the use of the fault tree analysis technique and the BDD approach for such systems, the Markov method is incorporated into the optimization process. The main types of dependency which can exist between the safety system component failures are identified. The Markov model generation algorithms are suggested for each type of dependency. The modified optimization tool is tested on the HIPS and FDS. Results comparison shows the benefit of using the modified technique for safety system optimization. Finally the effectiveness and application to general safety systems is discussed.

Product modularity is often seen as a means by which a product system can be decomposed into smaller, more manageable chunks in order to better manage design, manufacturing and after-sales complexity. The most common approach is to decompose the product down to component level and then group the components to form modules. The rationale for module grouping can vary, from the more technical physical and functional component interactions, to any number of strategic objectives such as variety, maintenance and recycling. The problem lies with the complexity of product modularity under these multiple (often conflicting) objectives. The research in this thesis presents a holistic multi-objective computer aided modularity optimisation (CAMO) framework. The framework consists of four main steps: 1) product decomposition; 2) interaction analysis; 3) formation of modular architectures and; 4) scenario analysis. In summary of these steps: the product is first decomposed into a number a basic components by analysis of both the physical and functional product domains. The various dependencies and strategic similarities that occur between the product s components are then analysed and entered into a number of interaction matrixes. A specially developed multi-objective grouping genetic algorithm (MOGGA) then searches the matrices and provides a whole set of alternative (yet optimal) modular product configurations. The solution set is then evaluated and explored (scenario analysis) using the principles of Analytic Hierarchy Process. A software prototype has been created for the CAMO framework using Visual Basic to create a multi-objective genetic algorithm (GA) based optimiser within an excel environment. A case study has been followed to demonstrate the various steps of the framework and make comparisons with previous works. Unlike previous works, that have used simplistic optimisation algorithms and have in general only considered a limited number of modularisation objectives, the developed framework provides a true multi-objective approach to the product modularisation problem.

Many real-world problems are subject to uncertainty, and often solutions should not only be good, but also robust against environmental disturbances or deviations from the decision variables. While most papers dealing with robustness aim at finding solutions with a high expected performance given a distribution of the uncertainty, we examine the trade-off between the allowed deviations from the decision variables (tolerance level), and the worst case performance given the allowed deviations. In this research work, we suggest two multi-objective evolutionary algorithms to compute the available trade-offs between allowed tolerance level and worst-case quality of the solutions, and the tolerance level is defined as robustness which could also be the variations from parameters. Both algorithms are 2-level nested algorithms. While the first algorithm is point-based in the sense that the lower level computes a point of worst case for each upper level solution, the second algorithm is envelope-based, in the sense that the lower level computes a whole trade-off curve between worst-case fitness and tolerance level for each upper level solution. Our problem can be considered as a special case of bi-level optimisation, which is computationally expensive, because each upper level solution is evaluated by calling a lower level optimiser. We propose and compare several strategies to improve the efficiency of both algorithms. Later, we also suggest surrogate-assisted algorithms to accelerate both algorithms.

ENGLISH ABSTRACT: It is very seldom that a decision-making problem concerns only a single value or objective. The process of simultaneously optimising two or more con icting objectives is known as multi-objective optimisation (MOO). A number of metaheuristics have been successfully adapted for MOO. The aim of this study was to investigate the feasibility of applying an agent-based modelling approach to MOO. The (s; S) inventory problem was chosen as the application eld for this approach and Anylogic used as model platform. Agents in the model were responsible for inventory and sales management, and had to negotiate with each other in order to nd optimal reorder strategies. The introduction of concepts such as agent satisfaction indexes, aggression factors, and recollection ability guided the negotiation process between the agents. The results revealed that the agents had the ability to nd good strategies. The Pareto front generated from their proposed strategies was a good approximation to the known front. The approach was also successfully applied to a recognised MOO test problem proving that it has the potential to solve a variety of MOO problems. Future research could focus on further developing this approach for more practical applications such as complex supply chain systems, nancial models, risk analysis and economics.
AFRIKAANSE OPSOMMING: Daar is weinig besluitnemingsprobleme waar slegs 'n enkele waarde of doelwit ter sprake is. Die proses waar twee of meer doelwitte, wat in konflik staan met mekaar, gelyktydig optimiseer word, staan bekend as multi-doelwit optimisering (MOO). 'n Aantal metaheuristieke is al suksesvol aangepas vir MOO. Die doelwit van hierdie studie was om ondersoek in te stel na die lewensvatbaarheid van die toepassing van 'n agent gebasseerde modelerings benadering tot MOO. As toepassingsveld vir hierdie benadering was die (s; S) voorraad probleem gekies en Anylogic was gebruik as model platform. In die model was agente verantwoordelik vir voorraad- en verkope bestuur. Hulle moes onderling met mekaar onderhandel om die optimale bestelling strategiee te verkry. Konsepte soos agentbevrediging, aggressie faktore en herinneringsvermoens is ingestel om die onderhandeling tussen die agente te bewerkstellig. Die resultate het gewys dat die agente oor die vermoe beskik om met goeie strategiee vorendag te kom. Die Pareto fronte wat gegenereer is deur hul voorgestelde strategiee was 'n goeie benadering tot die bekende front. Die benadering was ook suksesvol toegepas op 'n erkende MOO toets-probleem wat bewys het dat dit oor die potensiaal beskik om 'n verskeidenheid van MOO probleme op te los. Toekomstige navorsing kan daarop fokus om hierdie benadering verder te ontwikkel vir meer praktiese toepassings soos komplekse voorsieningskettingstelsels, finnansiele modelle, risiko-analises en ekonomie.

Thesis (MSc)--University of Stellenbosch, 2007.
ENGLISH ABSTRACT: We use Evolutionary Multi-Objective Optimisation (EMOO) algorithms to optimise objective functions that reflect situations in communication networks. These include functions that optimise Network Engineering (NE) objective functions in core, metro and wireless sensor networks. The main contributions of this thesis are threefold. Routing and Wavelength Assignment (RWA) for IP backbone networks. Routing and Wavelength Assignment (RWA) is a problem that has been widely addressed by the optical research community. A recent interest in this problem has been raised by the need to achieve routing optimisation in the emerging generation multilayer networks where data networks are layered above a Dense Wavelength Division Multiplexing (DWDM) network. We formulate the RWA as both a single and a multi-objective optimisation problem which are solved using a two-step solution where (1) a set of paths are found using genetic optimisation and (2) a graph coloring approach is implemented to assign wavelengths to these paths. The experimental results from both optimisation scenarios reveal the impact of (1) the cost metric used which equivalently defines the fitness function (2) the algorithmic solution adopted and (3) the topology of the network on the performance achieved by the RWA procedure in terms of path quality and wavelength assignment. Optimisation of Arrayed Waveguide Grating (AWG) Metro Networks. An Arrayed Waveguide Grating (AWG) is a device that can be used as a multiplexer or demultiplexer in WDM systems. It can also be used as a drop-and-insert element or even a wavelength router. We take a closer look at how the hardware and software parameters of an AWG can be fine tuned in order to maximise throughput and minimise the delay. We adopt a multi-objective optimisation approach for multi-service AWG-based single hop metro WDM networks. Using a previously proposed multi-objective optimisation model as a benchmark, we propose several EMOO solutions and compare their efficiency by evaluating their impact on the performance achieved by the AWG optimisation process. Simulation reveals that (1) different EMOO algorithms can exhibit different performance patterns and (2) good network planning and operation solutions for a wide range of traffic scenarios can result from a well selected EMOO algorithm. Wireless Sensor Networks (WSNs) Topology (layout) Optimisation. WSNs have been used in a number of application areas to achieve vital functions in situations where humans cannot constantly be available for certain tasks such as in hostile areas like war zones, seismic sensing where continuous inspection and detection are needed, and many other applications such as environment monitoring, military operations and surveillance. Research and practice have shown that there is a need to optimise the topology (layout) of such sensors on the ground because the position on which they land may affect the sensing efficiency. We formulate the problem of layout optimisation as a multi-objective optimisation problem consisting of maximising both the coverage (area) and the lifetime of the wireless sensor network. We propose different algorithmic evolutionary multi-objective methods and compare their performance in terms of Pareto solutions. Simulations reveal that the Pareto solutions found lead to different performance patterns and types of layouts.
AFRIKAANSE OPSOMMING: Ons gebruik ”Evolutionary Multi-Objective Optimisation (EMOO)” algoritmes om teiken funksies, wat egte situasies in kommunikasie netwerke voorstel, te optimiseer. Hierdie sluit funksies in wat ”Network Engineering” teiken funksies in kern, metro en wireless sensor netwerke optimiseer. Die hoof doelwitte van hierdie tesis is dus drievuldig. RWA vir IP backbone netwerke ”Routing and Wavelength Assignment (RWA)” is ’n probleem wat al menigte kere in die optiese navorsings kringe aangespreek is. Belangstelling in hierdie veld het onlangs ontstaan a.g.v. die aanvraag na die optimisering van routering in die opkomende generasie van veelvuldige vlak netwerke waar data netwerke in ’n vlak ho¨er as ’n ”Dense Wavelength Division Multiplexing (DWDM)” netwerk gele is. Ons formuleer die RWA as beide ’n enkele and veelvuldige teiken optimiserings probleem wat opgelos word deur ’n 2-stap oplossing waar (1) ’n stel roetes gevind word deur genetiese optimisering te gebruik en (2) ’n grafiek kleuring benadering geimplementeer word om golflengtes aan hierdie roetes toe te ken. Die eksperimentele resultate van beide optimiserings gevalle vertoon die impak van (1) die koste on wat gebruik word wat die ekwalente fitness funksie definieer , (2) die algoritmiese oplossing wat gebruik word en (3) die topologie van die netwerk op die werkverrigting van die RWA prosedure i.t.v. roete kwaliteit en golflengte toekenning. Optimisering van AWG Metro netwerk ’n ”Arrayed Waveguide Grating (AWG)” is ’n toestel wat gebruik kan word as ’n multipleksor of demultipleksor in WDM sisteme. Dit kan ook gebruik word as ’n val-en-inplaas element of selfs ’n golflengte router. Kennis word ingestel na hoe die hardeware en sagteware parameters van ’n AWG ingestel kan word om die deurset tempo te maksimeer en vertragings te minimiseer. Ons neem ’n multi-teiken optimiserings benadering vir multi diens, AWG gebaseerde, enkel skakel, metro WDM netwerke aan. Deur ’n vooraf voorgestelde multi teiken optimiserings model as ”benchmark” te gebruik, stel ons ’n aantal EMOO oplossings voor en vergelyk ons hul effektiwiteit deur hul impak op die werkverrigting wat deur die AWG optimiserings proses bereik kan word, te vergelyk. Simulasie modelle wys dat (1) verskillende EMOO algoritmes verskillende werkverrigtings patrone kan vertoon en (2) dat goeie netwerk beplanning en werking oplossings vir ’n wye verskeidenheid van verkeer gevalle kan plaasvind a.g.v ’n EMOO algoritme wat reg gekies word. ”Wireless Sensor Network” Topologie Optimisering WSNs is al gebruik om belangrike funksies te verrig in ’n aantal toepassings waar menslike beheer nie konstant beskikbaar is nie, of kan wees nie. Voorbeelde van sulke gevalle is oorlog gebiede, seismiese metings waar aaneenlopende inspeksie en meting nodig is, omgewings meting, militˆere operasies en bewaking. Navorsing en praktiese toepassing het getoon dat daar ’n aanvraag na die optimisering van die topologie van sulke sensors is, gebaseer op gronde van die feit dat die posisie waar die sensor beland, die effektiwiteit van die sensor kan affekteer. Ons formuleer die probleem van uitleg optimisering as ’n veelvuldige vlak optimiserings probleem wat bestaan uit die maksimering van beide die bedekkings area en die leeftyd van die wireless sensor netwerk. Ons stel verskillende algoritmiese, evolutionˆere, veelvuldige vlak oplossings voor en vergelyk hul werkverrigting i.t.v Pareto oplossings. Simulasie modelle wys dat die Pareto oplossings wat gevind word lei na verskillende werkverrigtings patrone en uitleg tipes.

This research work developed an innovative computational approach to the preliminary design of low-thrust trajectories optimising multiple mission criteria. Low-Thrust (LT) propulsion has become the propulsion system of choice for a number of near Earth and interplanetary missions. Consequently, in the last two decades a good wealth of research has been devoted to the development of computational method to design low-thrust trajectories. Most of the techniques, however, minimise or maximise a single figure of merit under a set of design constraints. Less effort has been devoted to the development of efficient methods for the minimisation (or maximisation) of two or more figures of merit. On the other hand, in the preliminary mission design phase, the decision maker is interested in analysing as many design solutions as possible against different trade-off criteria. Therefore, in this PhD work, an innovative Multi-Objective (MO), memetic optimisation algorithm, called Multi-Agent Collaborative Search (MACS2), has been implemented to tackle low-thrust trajectory design problems with multiple figures of merit. Tests on both academic and real-world problems showed that the proposed MACS2 paradigm performs better than or as well as other state-of-the-art Multi-Objective optimisation algorithms. Concurrently, a set of novel approximated, first-order, analytical formulae has been developed, to obtain a fast but reliable estimation of the main trade-off criteria. These formulae allow for a fast propagation of the orbital motion under a constant perturbing acceleration. These formulae have been shown to allow for the fast and relatively accurate propagation of long LT trajectories under the typical acceleration level delivered by current engine technology. Various applications are presented to demonstrate the validity of the combination of the analytical formulae with MACS2. Among them, the preliminary design of the JAXA low-cost DESTINY mission to L2, a novel approach to the optimisation under uncertainty of deflection actions for Near Earth Objects (NEO), and the de-orbiting of space debris with low-thrust and with a combination of low-thrust and solar radiation pressure.

In this work we investigate the use of Multi-Objective metaheuristics for the data-mining task of clustering. We �first investigate methods of evaluating the quality of clustering solutions, we then propose a new Multi-Objective clustering algorithm driven by multiple measures of cluster quality and then perform investigations into the performance of different Multi-Objective clustering algorithms. In the context of clustering, a robust measure for evaluating clustering solutions is an important component of an algorithm. These Cluster Quality Measures (CQMs) should rely solely on the structure of the clustering solution. A robust CQM should have three properties: it should be able to reward a \good" clustering solution; it should decrease in value monotonically as the solution quality deteriorates and, it should be able to evaluate clustering solutions with varying numbers of clusters. We review existing CQMs and present an experimental evaluation of their robustness. We find that measures based on connectivity are more robust than other measures for cluster evaluation. We then introduce a new Multi-Objective Clustering algorithm (MOCA). The use of Multi-Objective optimisation in clustering is desirable because it permits the incorporation of multiple measures of cluster quality. Since the definition of what constitutes a good clustering is far from clear, it is beneficial to develop algorithms that allow for multiple CQMs to be accommodated. The selection of the clustering quality measures to use as objectives for MOCA is informed by our previous work with internal evaluation measures. We explain the implementation details and perform experimental work to establish its worth. We compare MOCA with k-means and find some promising results. We�find that MOCA can generate a pool of clustering solutions that is more likely to contain the optimal clustering solution than the pool of solutions generated by k-means. We also perform an investigation into the performance of different implementations of MOEA algorithms for clustering. We�find that representations of clustering based around centroids and medoids produce more desirable clustering solutions and Pareto fronts. We also �find that mutation operators that greatly disrupt the clustering solutions lead to better exploration of the Pareto front whereas mutation operators that modify the clustering solutions in a more moderate way lead to higher quality clustering solutions. We then perform more specific investigations into the performance of mutation operators focussing on operators that promote clustering solution quality, exploration of the Pareto front and a hybrid combination. We use a number of techniques to assess the performance of the mutation operators as the algorithms execute. We confirm that a disruptive mutation operator leads to better exploration of the Pareto front and mutation operators that modify the clustering solutions lead to the discovery of higher quality clustering solutions. We find that our implementation of a hybrid mutation operator does not lead to a good improvement with respect to the other mutation operators but does show promise for future work.

Many important modern engineering problems involve satisfying multiple objectives. Simultaneous optimization of these objectives can be difficult as they compete for the same set of any given resources. One way to solve multiple-objective optimization is with the use of genetic algorithms (GA’s).

One can break down the structure of these multi-objective genetic algorithms (MOGA’s) into two different approaches. One approach is based on incorporating multiple objectives into a single fitness function which will evaluate how well a given solution solves the issue. The other approach uses multiple fitness functions, each representing a different objective, which when combined create a solution set of possible solutions to the problem. This project focuses on combining these approaches in order to make a hybrid model, which can benefit from combining the results of the previous two methods; incorporating a level of automation that allows for inference of a final solution based on different prioritization of each objective. This solution would not have been previously attainable by either standalone method.

This project is named the Automated Inferential Multi-Objective Optimization System (AIMOS), and it can be applied to a multitude of different problem types. In order to show its capabilities, AIMOS has been applied to a theoretical optimization problem used to measure the effectiveness of GA’s.

In electromagnetic design, optimisation often involves evaluating the finite element method (FEM) – repetitive evaluation of the objective function may require hours or days of computation, making the use of standard direct search methods (e.g. genetic algorithm and particle swarm) impractical. Surrogate modelling techniques are helpful tools in these scenarios. Indeed, their applications can be found in many aspects of engineering design in which a computationally expensive model is involved. Kriging, one of the most widely used surrogate modelling techniques, has become an increasingly active research subject in recent decades. This thesis focuses on four interesting research topics in surrogate-based optimisation: infill sampling efficiency, robust optimisation, and the memory problem encountered in large datasets and multi-objective optimisation. This thesis briefly provides relevant background information and introduces a number of independent novel approaches for each topic, with the aim of increasing efficiency of optimisation process and ability to handle larger datasets.