This thesis investigates the use of Bayesian analysis upon an opponent's behaviour in order to determine the desired goals or strategy used by a given adversary. A terrain analysis approach utilising the A* algorithm is investigated, where a probability distribution between discrete behaviours of an opponent relative to a set of possible goals is generated. The Bayesian analysis of agent behaviour accurately determines the intended goal of an opponent agent, even when the opponent's actions are altered randomly. The environment of Poker is introduced and abstracted for ease of analysis. Bayes' theorem is used to generate an effective opponent model, categorizing behaviour according to its similarity with known styles of opponent. The accuracy of Bayes' rule yields a notable improvement in the performance of an agent once an opponent's style is understood. A hybrid of the Bayesian style predictor and a neuroevolutionary approach is shown to lead to effective dynamic play, in comparison to agents that do not use an opponent model. The use of recurrence in evolved networks is also shown to improve the performance and generalizability of an agent in a multiplayer environment. These strategies are then employed in the full-scale environment of Texas Hold'em, where a betting round-based approach proves useful in determining and counteracting an opponent's play. It is shown that the use of opponent models, with the adaptive benefits of neuroevolution aid the performance of an agent, even when the behaviour of an opponent does not necessarily fit within the strict definitions of opponent 'style'.

This thesis addresses the problem of how the dendritic structure and other morphological properties of the neuron can determine its pattern recognition performance. The techniques used in this work for generating dendritic trees with different morphologies included the following three methods. Firstly, dendritic trees were produced by exhaustively generating every possible morphology. Where this was not possible due to the size of morphological space, I sampled systematically from the possible morphologies. Lastly, dendritic trees were evolved using an evolutionary algorithm, which varied existing morphologies using selection, mutation and crossover. From these trees, I constructed full compartmental conductance-based models of neurons. I then assessed the performance of the resulting neuronal models by quantifying their ability to discriminate between learned and novel input patterns. The morphologies generated were tested in the presence and absence of active conductances. The results have shown that the morphology does have a considerable effect on pattern recognition performance. In fact, neurons with a small mean depth of their dendritic tree are the best pattern recognizers. Moreover, the performance of neurons is anti-correlated with mean depth. Interestingly, the symmetry of the neuronal morphology does not correlate with performance. This research has also revealed that the evolutionary algorithm could find effective morphologies for both passive models and models with active conductances. In the active model, there was a considerable change in the performance of the original population of neurons, which largely resulted from changes in the morphological parameters such as dendritic compartmental length and tapering. However, no single parameter setting guaranteed good neuronal performance; in three separate runs of the evolutionary algorithm, different sets of well performing parameters were found. In fact, the evolved neurons performed at least five times better than the original hand-tuned neurons. In summary, the combination of morphological parameters plays a key role in determining the performance of neurons in the pattern recognition task and the right combination produces very well performing neurons.

Scheduling problems and constraint satisfaction problems are generally known to be extremely hard. This thesis proposes a new evolutionary al- gorithm approach to solve a constrained-based scheduling problem. In this approach, variable orderings are evolved. The variable ordering serves as a parameter for the constraint solver. Its purpose is to determine the order in which variables are labelled by the solver. Hence the evolving individuals may be encoded as permutations. Therefore, our approach can be applied to a wider range of constraint satisfaction problems. Methods for generating the initial population of individuals based on the analysis of the precedence constraints graph are proposed. New genetic operators are presented and successfully applied. Our approach succeeded in finding a range of diverse schedules with the optimal makespan. Furthermore, multi-objective opti- mization was successfully attempted with the NSGA-II. 1

A method to find solutions to multi-objective design problems that involve poor information available was proposed. The method quantified the designers intuition in a systematic manner, and utilized it to approximate inaccurate and/or vague numbers. In the context of possibility theory, uncertain values were expressed through possibility distributions, i.e. fuzzy membership functions. Based on the membership functions of the value, levels of confidence of the solutions to multi-objective problems were defined through the notions of possibility and necessity. An evolutionary algorithm was modified to find sets of solutions that allow certain levels of confidence instead of the crisp sets of the solutions. The method was applied to a design problem of the gyrodyne configuration and sets of the solutions of the specified possibility and necessity were found. The results of the design problem and the suggestions for future research were discussed.

There is a growing interest in electronic auctions in the literature. Many researchers work on the single attribute version of the problem. Multi-attribute version of the problem is more realistic. However, this brings a substantial difficulty in solving the problem. In order to overcome the computational difficulties, we develop an Evolutionary Algorithm (EA) for the case of multi-attribute multi-item reverse auctions. We generate the whole Pareto front using the EA. We also develop heuristic procedures to find several good initial solutions and insert those in the initial population of the EA. We test the EA on a number of randomly generated problems and compare the results with the true Pareto optimal front obtained by solving a series of integer programs. We also develop an exact interactive approach that provides aid both to the buyer and the sellers for a multi-attribute single item multi round reverse auction. The buyer decides on the provisional winner at each round. Then the approach provides support in terms of all attributes to each seller to be competitive in the next round of the auction.

In this study, a bi-objective capacitated facility location problem is presented which includes partial coverage concept and relocation of facility nodes. In partial coverage, a predefined distance between a demand node and a facility node is assumed to be fully covered. After the predefined distance, the service level commences to decay linearly. The problem is designed to consider the existence of already functioning facility nodes. It is allowed to close these existing facilities and open new facilities in potential sites. However, existing facility nodes are strongly favored against new facility nodes. The objectives are the maximization of the weighted total coverage and the minimization of number of facility nodes. A novel interactive multi-objective evolutionary algorithm is proposed to solve this problem, I-TREA. I-TREA is originated from NSGA-II and designed for interactive methods benefiting from quality infeasible solutions. The performance of I-TREA is benchmarked with a modified version of NSGA-II on randomly generated problems with various sizes and utility functions.

<p>Most real-world optimization problems behave stochastically. Evolutionary optimization algorithms have to cope with the uncertainty in order to not loose a substantial part of their performance. There are different types of uncertainty and this thesis studies the type that is commonly known as noise and the use of resampling techniques as countermeasure in multi-objective evolutionary optimization. Several different types of resampling techniques have been proposed in the literature. The available techniques vary in adaptiveness, type of information they base their budget decisions on and in complexity. The results of this thesis show that their performance is not necessarily increasing as soon as they are more complex and that their performance is dependent on optimization problem and environment parameters. As the sampling budget or the noise level increases the optimal resampling technique varies. One result of this thesis is that at low computing budgets or low noise strength simple techniques perform better than complex techniques but as soon as more budget is available or as soon as the algorithm faces more noise complex techniques can show their strengths. This thesis evaluates the resampling techniques on standard benchmark functions. Based on these experiences insights have been gained for the use of resampling techniques in evolutionary simulation optimization of real-world problems.</p>

The paper "Parallel Genetic Algorithms" discusses the theoretical basics of Evolutionary Algorithms concentrating on Genetic Algorithms. Possibilities for a parallelization of these algorithms are examined and explained on the basis of concepts of parallel programming. A concrete suggestion for a practical realization of a parallel Genetic Algorithm at different levels of complexity is presented. / Die Studienarbeit zum Thema "Parallele Genetische Algorithmen" befasst sich mit den theoretischen Grundlagen Evolutionärer Algorithmen, wobei die Konzentration bei Genetischen Algorithmen liegt, und untersucht die Möglichkeiten einer parallelen Realisierung dieser Algorithmen. Des weiteren werden Konzepte der Parallelen Programmierung diskutiert sowie ein konkreter Vorschlag zur praktischen Realisierung eines parallelen Genetischen Algorithmus' auf verschiedenen Komplexitätsebenen vorgestellt.

Evolutionary Algorithms (EAs) have been widely used for the optimisation of both theoretical and real-world non-linear problems, although such optimisation methods have found reasonably limited utilisation in fields outside of the academic domain. While the causality of this limited uptake in non-academic fields falls outside the scope of this thesis, the core focus of this research remains strongly influenced by the notions of solution feasibility and making optimisation methods more accessible for engineers, both factors attributed to low EA adoption rates in the commercial space. This thesis focuses on the application of bespoke heuristic methods to the field of water distribution system optimisation. Water distribution systems are complex entities that are difficult to model and optimise as they consist of many interacting components each with a set of considerations to address, hence it is important for the engineer to understand and assess the behaviour of the system to enable its effective design and optimisation. The primary goal of this research is to assess the impact that incorporating water systems knowledge into an evolution algorithm has on algorithm performance when applied to water distribution network optimisation problems. This thesis describes the development of two heuristics influenced by the practices of water systems engineers when designing water distribution networks with the view to increasing an algorithm’s performance and resultant solution feasibility. By utilising heuristics based on engineering design principles and integrating them into existing EAs, it is found that both engineering feasibility and general algorithmic performance can be notably improved. Firstly the heuristics are applied to a standard single-objective EA and then to a multi-objective genetic algorithm. The algorithms are assessed on a number of water distribution network benchmarks from the literature including real-world based, large scale systems and compared to the standard variants of the algorithms. Following this, a set of extensive experiments are conducted to explore how the inclusion of water systems knowledge impacts the sensitivity of an evolutionary algorithm to parameter variance. It was found that the performance of both engineering inspired algorithms were less sensitive to parameter change than the standard genetic algorithm variant meaning that non-experts in the field of meta-heuristics will potentially be able to get much better performance out of the engineering heuristic based algorithms without the need for specialist evolutionary algorithm knowledge. In addition this research explores the notion that visualisation techniques can provide water system engineers with a greater insight into the operation and behaviour of an evolutionary algorithm. The final section of this thesis presents a novel three-dimensional representation of pipe based water systems and demonstrates a range of innovative methods to convey information to the user. The interactive visualisation system presented not only allows the engineer to visualise the various parameters of a network but also allows the user to observe the behaviour and progress of an iterative optimisation method. Examples of the combination of the interactive visualisation system and the EAs developed in this work are shown to enable the user to track and visualise the actions of the algorithm. The visualisation aggregates changes to the network over an EA run and grants significant insight into the operations of an EA as it is optimising a network. The research presented in this thesis demonstrates the effectiveness of integrating water system engineering expertise into evolutionary based optimisation methods. Not only is solution quality improved over standard methods utilising these new heuristic techniques, but the potential for greater interaction between engineer, problem and optimiser has been established.

Orientador: Silvio Alexandre de Araujo / Banca: Helenice de Oliveira Florentino Silva / Banca: Maria do Socorro Nogueira Rangel / Resumo: Este trabalho trata do problema de corte de estoque unidimensional inteiro, que consiste em cortar um conjunto de objetos disponíveis em estoque para a produção de itens menores demandados, de tal forma que se otimize uma ou mais funções objetivos. Foi estudado o caso em que existe apenas um tipo de objeto em estoque em quantidades suficiente para atender a demanda. Três adaptações de um método heurístico baseadas nos conceitos dos algoritmos evolutivos multiobjetivo são propostas para resolver o problema considerando duas funções objetivo conflitantes, a minimização do número de objetos cortados e a minimização do número de diferentes padrões de corte. As adaptações utilizam as idéias presentes no método da Soma Ponderada, no Vector Evaluated Genetic Algorithm e no Multiple Objective Genetic Algorithm. Estas heurísticas são analisadas resolvendo-se instâncias geradas aleatoriamente. / Abstract: This work deals with the one-dimensional integer cutting stock problem, which consist of cutting a set of available objects in stock in order to produce ordered smaller items in such a way as to optimize one or more objective functions. On the case studied there is just one type of object in stock available in sufficient quantity to satisfy the demand. Three adaptations of a heuristic method based on the multi-objective evolutionary algorithms concepts are proposed to solve the problem considering two conflicting objective functions, the minimization of the number of objects to be cut and the minimization of the number of different cutting patterns. The adaptations consider the ideas from the Weighted Sum method, the Vector Evaluated Genetic Algorithm and the Multiple Objective Genetic Algorithm. These heuristics are analyzed by solving randomly generated instances. / Mestre