Dissertations / Theses on the topic 'Evolutionary computation'

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

2007/2008
Evolutionary computations, also called evolutionary algorithms, consist of several heuristics, which are able to solve optimization tasks by imitating some aspects of natural evolution. They may use different levels of abstraction, but they are always working on populations of possible solutions for a given task. The basic idea is that if only those individuals of a population which meet a certain selection criteria reproduce, while the remaining individuals die, the population will converge to those individuals that best meet the selection criteria. If imperfect reproduction is added the population can begin to explore the search space and will move to individuals that have an increased selection probability and that hand down this property to their descendants. These population dynamics follow the basic rule of the Darwinian evolution theory, which can be described in short as the “survival of the fittest”. Although evolutionary computations belong to a relative new research area, from a computational perspective they have already showed some promising features such as: • evolutionary methods reveal a remarkable balance between efficiency and efficacy; • evolutionary computations are well suited for parameter optimisation; • this type of algorithms allows a wide variety of extensions and constraints that cannot be provided in traditional methods; • evolutionary methods are easily combined with other optimization techniques and can also be extended to multi-objective optimization. From an economic perspective, these methods appear to be particularly well suited for a wide range of possible financial applications, in particular in this thesis I study evolutionary algorithms • for time series prediction; • to generate trading rules; • for portfolio selection. It is commonly believed that asset prices are not random, but are permeated by complex interrelations that often translate in assets mispricing and may give rise to potentially profitable opportunities. Classical financial approaches, such as dividend discount models or even capital asset pricing theories, are not able to capture these market complexities. Thus, in the last decades, researchers have employed intensive econometric and statistical modeling that examine the effects of a multitude of variables, such as price- earnings ratios, dividend yields, interest rate spreads and changes in foreign exchange rates, on a broad and variegated range of stocks at the same time. However, these models often result in complex functional forms difficult to manage or interpret and, in the worst case, are solely able to fit a given time series but are useless to predict it. Parallelly to quantitative approaches, other researchers have focused on the impact of investor psychology (in particular, herding and overreaction) and on the consequences of considering informed signals from management and analysts, such as share repurchases and analyst recommendations. These theories are guided by intuition and experience, and thus are difficult to be translated into a mathematical environment. Hence, the necessity to combine together these point of views in order to develop models that examine simultaneously hundreds of variables, including qualitative informations, and that have user friendly representations, is urged. To this end, the thesis focuses on the study of methodologies that satisfy these requirements by integrating economic insights, derived from academic and professional knowledge, and evolutionary computations. The main task of this work is to provide efficient algorithms based on the evolutionary paradigm of biological systems in order to compute optimal trading strategies for various profit objectives under economic and statistical constraints. The motivations for constructing such optimal strategies are: i) the necessity to overcome data-snooping and supervisorship bias in order to learn to predict good trading opportunities by using market and/or technical indicators as features on which to base the forecasting; ii) the feasibility of using these rules as benchmark for real trading systems; iii) the capability of ranking quantitatively various markets with respect to their profitability according to a given criterion, thus making possible portfolio allocations. More precisely, I present two algorithms that use artificial expert trading systems to predict financial time series, and a procedure to generate integrated neutral strategies for active portfolio management. The first algorithm is an automated procedure that simultaneously selects variables and detect outliers in a dynamic linear model using information criteria as objective functions and diagnostic tests as constraints for the distributional properties of errors. The novelties are the automatic implementation of econometric conditions in the model selection step, making possible a better exploration of the solution space on one hand, and the use of evolutionary computations to efficiently generate a reduction procedure from a very large number of independent variables on the other hand. In the second algorithm, the novelty is given by the definition of evolutionary learning in financial terms and its use in a multi-objective genetic algorithm in order to generate technical trading systems. The last tool is based on a trading strategy on six assets, where future movements of each variable are obtained by an evolutionary procedure that integrates various types of financial variables. The contribution is given by the introduction of a genetic algorithm to optimize trading signals parameters and the way in which different informations are represented and collected. In order to compare the contribution of this work to “classical” techniques and theories, the thesis is divided into three parts. The first part, titled Background, collects Chapters 2 and 3. Its purpose is to provide an introduction to search/optimization evolutionary techniques on one hand, and to the theories that relate the predictability in financial markets with the concept of efficiency proposed over time by scholars on the other hand. More precisely, Chapter 2 introduces the basic concepts and major areas of evolutionary computation. It presents a brief history of three major types of evolutionary algorithms, i.e. evolution strategies, evolutionary programming and genetic algorithms, and points out similarities and differences among them. Moreover it gives an overview of genetic algorithms and describes classical and genetic multi-objective optimization techniques. Chapter 3 first presents an overview of the literature on the predictability of financial time series. In particular, the extent to which the efficiency paradigm is affected by the introduction of new theories, such as behavioral finance, is described in order to justify the market forecasting methodologies developed by practitioners and academics in the last decades. Then, a description of the econometric and financial techniques that will be used in conjunction with evolutionary algorithms in the successive chapters is provided. Special attention is paid to economic implications, in order to highlight merits and shortcomings from a practitioner perspective. The second part of the thesis, titled Trading Systems, is devoted to the description of two procedures I have developed in order to generate artificial trading strategies on the basis of evolutionary algorithms, and it groups Chapters 4 and 5. In particular, chapter 4 presents a genetic algorithm for variable selection by minimizing the error in a multiple regression model. Measures of errors such as ME, RMSE, MAE, Theil’s inequality coefficient and CDC are analyzed choosing models based on AIC, BIC, ICOMP and similar criteria. Two components of penalty functions are taken in analysis- level of significance and Durbin Watson statistics. Asymptotic properties of functions are tested on several financial variables including stocks, bonds, returns, composite prices indices from the US and the EU economies. Variables with outliers that distort the efficiency and consistency of estimators are removed to solve masking and smearing problems that they may cause in estimations. Two examples complete the chapter. In both cases, models are designed to produce short-term forecasts for the excess returns of the MSCI Europe Energy sector on the MSCI Europe index and a recursive estimation- window is used to shed light on their predictability performances. In the first application the data-set is obtained by a reduction procedure from a very large number of leading macro indicators and financial variables stacked at various lags, while in the second the complete set of 1-month lagged variables is considered. Results show a promising capability to predict excess sector returns through the selection, using the proposed methodology, of most valuable predictors. In Chapter 5 the paradigm of evolutionary learning is defined and applied in the context of technical trading rules for stock timing. A new genetic algorithm is developed by integrating statistical learning methods and bootstrap to a multi-objective non dominated sorting algorithm with variable string length, making possible to evaluate statistical and economic criteria at the same time. Subsequently, the chapter discusses a practical case, represented by a simple trading strategy where total funds are invested in either the S&P 500 Composite Index or in 3-month Treasury Bills. In this application, the most informative technical indicators are selected from a set of almost 5000 signals by the algorithm. Successively, these signals are combined into a unique trading signal by a learning method. I test the expert weighting solution obtained by the plurality voting committee, the Bayesian model averaging and Boosting procedures with data from the the S&P 500 Composite Index, in three market phases, up-trend, down- trend and sideways-movements, covering the period 2000–2006. In the third part, titled Portfolio Selection, I explain how portfolio optimization models may be constructed on the basis of evolutionary algorithms and on the signals produced by artificial trading systems. First, market neutral strategies from an economic point of view are introduced, highlighting their risks and benefits and focusing on their quantitative formulation. Then, a description of the GA-Integrated Neutral tool, a MATLAB set of functions based on genetic algorithms for active portfolio management, is given. The algorithm specializes in the parameter optimization of trading signals for an integrated market neutral strategy. The chapter concludes showing an application of the tool as a support to decisions in the Absolute Return Interest Rate Strategies sub-fund of Generali Investments.
Gli “algoritmi evolutivi”, noti anche come “evolutionary computations” comprendono varie tecniche di ottimizzazione per la risoluzione di problemi, mediante alcuni aspetti suggeriti dall’evoluzione naturale. Tali metodologie sono accomunate dal fatto che non considerano un’unica soluzione alla volta, bens`ı trattano intere popolazioni di possibili soluzioni per un dato problema. L’idea sottostante `e che, se un algoritmo fa evolvere solamente gli individui di una data popolazione che soddisfano a un certo criterio di selezione, e lascia morire i restanti, la popolazione converger`a agli individui che meglio soddisfano il criterio di selezione. Con una selezione non ottimale, cio`e una che ammette pure soluzioni sub-ottimali, la popolazione rappresenter` a meglio l’intero spazio di ricerca e sar`a in grado di individuare in modo pi`u consistente gli individui migliori da far evolvere. Queste dinamiche interne alle popolazioni seguono i principi Darwiniani dell’evoluzione, che si possono sinteticamente riassumere nella dicitura “la sopravvivenza del più adatto”. Sebbene gli algoritmi evolutivi siano un’area di ricerca relativamente nuova, dal punto di vista computazionale hanno dimostrato alcune caratteristiche interessanti fra cui le seguenti: • permettono un notevole equilibrio tra efficienza ed efficacia; • sono particolarmente indicati per la configurazione dei parametri in problemi di ottimizzazione; • consentono una flessibilit`a nella definizione matematica dei problemi e dei vincoli che non si trova nei metodi tradizionali; • possono facilmente essere integrati con altre tecniche di ottimizzazione ed essere essere modificati per risolvere problemi multi-obiettivo. Dal un punto di vista economico, l’applicazione di queste procedure pu`o risultare utile specialmente in campo finanziario. In particolare, nella mia tesi ho studiato degli algoritmi evolutivi per • la previsione di serie storiche finanziarie; • la costruzione di regole di trading; • la selezione di portafogli. Da un punto di vista pi`u ampio, lo scopo di questa ricerca `e dunque l’analisi dell’evoluzione e della complessit`a dei mercati finanziari. In tal senso, dal momento che i prezzi non seguono andamenti puramente casuali, ma sono governati da un insieme molto articolato di eventi correlati, i modelli e le teorie classiche, come i dividend discount model e le varie capital asset pricing theories, non sono pi`u sufficienti per determinare potenziali opportunit`a di profitto. A tal fine, negli ultimi decenni, alcuni ricercatori hanno sviluppato una vasta gamma di modelli econometrici e statistici in grado di esaminare contemporaneamente le relazioni e gli effetti di centinaia di variabili, come ad esempio, price-earnings ratios, dividendi, differenziali fra tassi di interesse e variazioni dei tassi di cambio, per una vasta gamma di assets. Comunque, questo approccio, che fa largo impiego di strumenti di calcolo, spesso porta a dei modelli troppo complicati per essere gestiti o interpretati, e, nel peggiore dei casi, pur essendo ottimi per descrivere situazioni passate, risultano inutili per fare previsioni. Parallelamente a questi approcci quantitativi, si `e manifestato un grande interesse sulla psicologia degli investitori e sulle conseguenze derivanti dalle opinioni di esperti e analisti nelle dinamiche del mercato. Questi studi sono difficilmente traducibili in modelli matematici e si basano principalmente sull’intuizione e sull’esperienza. Da qui la necessit` a di combinare insieme questi due punti di vista, al fine di sviluppare modelli che siano in grado da una parte di trattare contemporaneamente un elevato numero di variabili in modo efficiente e, dall’altra, di incorporare informazioni e opinioni qualitative. La tesi affronta queste tematiche integrando le conoscenze economiche, sia accademiche che professionali, con gli algoritmi evolutivi. Pi`u pecisamente, il principale obiettivo di questo lavoro `e lo sviluppo di algoritmi efficienti basati sul paradigma dell’evoluzione dei sistemi biologici al fine di determinare strategie di trading ottimali in termini di profitto e di vincoli economici e statistici. Le ragioni che motivano lo studio di tali strategie ottimali sono: i) la necessit`a di risolvere i problemi di data-snooping e supervivorship bias al fine di ottenere regole di investimento vantaggiose utilizzando indicatori di mercato e/o tecnici per la previsione; ii) la possibilità di impiegare queste regole come benchmark per sistemi di trading reali; iii) la capacit`a di individuare gli asset pi`u vantaggiosi in termini di profitto, o di altri criteri, rendendo possibile una migliore allocazione di risorse nei portafogli. In particolare, nella tesi descrivo due algoritmi che impiegano sistemi di trading artificiali per predire serie storiche finanziarie e una procedura di calcolo per strategie integrate neutral market per la gestione attiva di portafogli. Il primo algoritmo `e una procedura automatica che seleziona le variabili e simultaneamente determina gli outlier in un modello dinamico lineare utilizzando criteri informazionali come funzioni obiettivo e test diagnostici come vincoli per le caratteristiche delle distribuzioni degli errori. Le novit`a del metodo sono da una parte l’implementazione automatica di condizioni econometriche nella fase di selezione, consentendo una migliore analisi dello EVOLUTIONARY COMPUTATIONS FOR TRADING SYSTEMS 3 spazio delle soluzioni, e dall’altra parte, l’introduzione di una procedura di riduzione evolutiva capace di riconoscere in modo efficiente le variabili pi`u informative. Nel secondo algoritmo, le novità sono costituite dalla definizione dell’apprendimento evolutivo in termini finanziari e dall’applicazione di un algoritmo genetico multi-obiettivo per la costruzione di sistemi di trading basati su indicatori tecnici. L’ultimo metodo proposto si basa su una strategia di trading su sei assets, in cui le dinamiche future di ciascuna variabile sono ottenute impiegando una procedura evolutiva che integra diverse tipologie di variabili finanziarie. Il contributo è dato dall’impiego di un algoritmo genetico per ottimizzare i parametri negli indicatori tecnici e dal modo in cui le differenti informazioni sono presentate e collegate. La tesi `e organizzata in tre parti. La prima parte, intitolata Background, comprende i Capitoli 2 e 3, ed è intesa a fornire un’introduzione alle tecniche di ricerca/ottimizzazione su base evolutiva da una parte, e alle teorie che si occupano di efficienza e prevedibilit`a dei mercati finanziari dall’altra. Più precisamente, il Capitolo 2 introduce i concetti base e i maggiori campi di studio della computazione evolutiva. In tal senso, si dà una breve presentazione storica di tre dei maggiori tipi di algoritmi evolutivi, ciò e le strategie evolutive, la programmazione evolutiva e gli algoritmi genetici, evidenziandone caratteri comuni e differenze. Il capitolo si chiude con una panoramica sugli algoritmi genetici e sulle tecniche classiche e genetiche di ottimizzazione multi-obiettivo. Il Capitolo 3 affronta nel dettaglio la problematica della prevedibilit`a delle serie storiche finanziarie mettendo in luce, in particolare, quanto il paradigma dell’efficienza sia influenzato dalle pi`u recenti teorie finanziarie, come ad esempio la finanza comportamentale. Lo scopo è quello di dare una giustificazione su basi teoriche per le metodologie di previsione sviluppate nella tesi. Segue una descrizione dei metodi econometrici e di analisi tecnica che nei capitoli successivi verrano impiegati assieme agli algoritmi evolutivi. Una particolare attenzione è data alle implicazioni economiche, al fine di evidenziare i loro meriti e i loro difetti da un punto di vista pratico. La seconda parte, intitolata Trading Systems, raggruppa i Capitoli 4 e 5 ed è dedicata alla descrizione di due procedure che ho sviluppato per generare sistemi di trading artificiali sulla base di algoritmi evolutivi. In particolare, il Capitolo 4 presenta un algortimo genetico per la selezione di variabili attraverso la minimizzazione dell’errore in un modello di regressione multipla. Misure di errore, quali il ME, il RMSE, il MAE, il coefficiente di Theil e il CDC sono analizzate a partire da modelli selezionati sulla scorta di criteri informazionali, come ad esempio AIC, BIC, ICOMP. A livello di vincoli diagnostici, ho considerato una funzione di penalità a due componenti e la statistica di Durbin Watson. Il programma impiega variabili finanziarie di vario tipo, come rendimenti di titoli, bond e prezzi di indici composti ottenuti dalle economie Statunitense ed Europea. Nel caso le serie storiche 4 MASSIMILIANO KAUCIC considerate presentino outliers che distorcono l’efficienza e la consistenza degli stimatori, l’algoritmo `e in grado di individuarle e rimuoverle dalla serie, risolvendo il problema di masking and smearing. Il capitolo si conclude con due applicazioni, in cui i modelli sono progettati per produrre previsioni di breve periodo per l’extra rendimento del settore MSCI Europe Energy sull’indice MSCI Europe e una procedura di tipo recursive estimation-window è utilizzata per evidenziarne le performance previsionali. Nel primo esempio, l’insieme dei dati `e ottenuto estraendo le variabili di interesse da un considerevole numero di indicatori di tipo macro e da variabili finanziarie ritardate rispetto alla variabile dipendente. Nel secondo esempio ho invece considerato l’intero insieme di variabili ritardate di 1 mese. I risultati mostrano una notevole capacità previsiva per l’extra rendimento, individuando gli indicatori maggiormente informativi. Nel Capitolo 5, il concetto di apprendimento evolutivo viene definito ed applicato alla costruzione di regole di trading su indicatori tecnici per lo stock timing. In tal senso, ho sviluppato un algoritmo che integra metodi di apprendimento statistico e di boostrap con un particolare algoritmo multi-obiettivo. La procedura derivante è in grado di valutare contemporaneamente criteri economici e statistici. Per descrivere il suo funzionamento, ho considerato un semplice esempio di trading in cui tutto il capitale è investito in un indice (che nel caso trattato è l’indice S&P 500 Composite) o in un titolo a basso rischio (nell’esempio, i Treasury Bills a 3 mesi). Il segnale finale di trading `e il risultato della selezione degli indicatori tecnici pi`u informativi a partire da un insieme di circa 5000 indicatori e la loro conseguente integrazione mediante un metodo di apprendimento (il plurality voting committee, il bayesian model averaging o il Boosting). L’analisi è stata condotta sull’intervallo temporale dal 2000 al 2006, suddiviso in tre sottoperiodi: il primo rappresenta l’indice in una fase al rialzo, il secondo in una fase al ribasso e il terzo sottoperiodo considera il mercato in una fase di trend non chiara. Nella terza parte, intitolata Portfolio Selection, spiego come si possano costruire modelli di ottimizzazione di portafogli sfruttando le tecniche della computazione evolutiva e i segnali prodotti da sistemi di trading artificiali. A tal fine, dapprima descrivo il significato economico delle strategie neutral market, evidenziandone rischi e benefici, successivamente introduco il GAIntegrated Neutral tool, un insieme di funzioni MATLAB che ho scritto per la gestione attiva di portafogli impiegando algoritmi evolutivi. La procedura calcola la configurazone ottimale dei segnali di trading per una strategia integrata neutral market. Il capitolo si conclude mostrando un’applicazione del tool come supporto alle decisioni nel fondo Absolute Return Interest Rate Strategies di Generali Investments.
XXI Ciclo
1979

The use of electricity in 21st century living has been firmly established throughout most of the world, correspondingly the infrastructure for production and delivery of electricity to consumers has matured and stabilised. However, due to recent technical and environmental–political developments, the electricity infrastructure worldwide is undergoing major restructuring. The forces driving this reorganisation are a complex interplay of technical, environmental, economic and political factors. The general trend of the reorganisation is a dis–aggregation of the previously integrated functions of generation, transmission and distribution, together with the establishment of competitive markets, primarily in generation, to replace previous regulated monopolistic utilities. To ensure reliable and cost effective electricity supply to consumers it is necessary to have an accurate picture of the expected generation in terms of the spatial and temporal distribution of prices and volumes. Previously this information was obtained by the regulated utility using technical studies such as centrally planned unit–commitment and economic–dispatch. However, in the new deregulated market environment such studies have diminished applicability and limited accuracy since generation assets are generally autonomous and subject to market forces. With generation outcomes governed by market mechanisms, to have an accurate picture of expected generation in the new electricity supply industry, it is necessary to complement traditional studies with new studies of market equilibrium and stability. Models and solution methods have been developed and refined for many markets, however they cannot be directly applied to the generation market due to the unique nature of electricity, having high inelastic demand, low storage capability and distinct transportation requirements. Intensive effort is underway to formulate solutions and models that specifically reflect the unique characteristics of the generation market. Various models have been proposed including game theory, stochastic and agent–based systems. Similarly there is a diverse range of solution methods including, Monte–Carlo simulations, linear–complimentary and quadratic programming. These approaches have varying degrees of generality, robustness and accuracy, some being better in certain aspects but weaker in others. This thesis formulates a new general model for the generation market based on the Cournot game, it makes no conjectures about producers’ behaviour and assumes that all electricity produced is immediately consumed. The new formulation characterises producers purely by their cost curves, which is only required to be piece–wise differentiable, and allows consumers’ characteristics to remain unspecified. The formulation can determine dynamic equilibrium and multiple equilibria of markets with single and multiple consumers and producers. Additionally stability concepts for the new market equilibrium is also developed to provide discrimination for dynamic equilibrium and to enable the structural stability of the market to be assessed. Solutions of the new formulation are evaluated by the use of evolutionary computation, which is a guided stochastic search paradigm that mimics the operation of biological evolution to iteratively produce a population of solutions. Evolutionary computation is employed as it is adept at finding multiple solutions for underconstrained systems, such as that of the new market formulation. Various enhancements to significantly improve the performance of the algorithms and simplify its application are developed. The concept of convergence potential of a population is introduced together with a system for the controlled extraction of such potential to accelerate the algorithm’s convergence and improve its accuracy and robustness. A new constraint handling technique for linear constraints that preserves the solution’s diversity is also presented together with a coevolutionary solution method for the multiple consumers and producers market. To illustrate the new electricity market formulation and its evolutionary computation solution methods, the equilibrium and stability of a test market with one consumer and thirteen thermal generators with valve point losses is examined. The case of a multiple consumer market is not simulated, though the formulation and solution methods for this case is included. The market solutions obtained not only confirms previous findings thus validating the new approach, but also includes new results yet to be verified by future studies. Techniques for market designers, regulators and other system planners in utilising the new market solutions are also given. In summary, the market formulation and solution method developed shows great promise in determining expected generation in a deregulated environment.

This thesis considers genetic programming (GP) for evolving financial trading strategies. The traditional approach in the literature is to represent a trading strategy, or a program, as a single decision tree. This thesis proposes a general multiple tree framework for dynamic decision making, where evaluation is contingent on the previous output ofthe program. The conditional multiple tree structure nests the single tree as a special case. TheoreticalIy, it is a superior alternative, but in practice this is not always the case. It depends on the underlying problem, and is basically a manifestation ofOckham srazor. The framework is validated on artificial data, and hereafter it is applied to two real financial problems: statistical arbitrage and high-frequency foreign exchange trading. In contrast to a pure arbitrage, that guarantees a sure profit, a statistical arbitrage strategy only produces a riskless profit in the limit. Both schemes are self-funding. In this thesis, single and dual trees are used to evolve statistical arbitrage strategies on banking stocks within the Euro Stoxx index. Both single and dual trees are capable of discovering significant statistical arbitrage strategies, even in the presence of a realistic market impact. A finding that points to weak form market inefficiencies. Moreover, it is found that the dual trees provide a more robust response, compared to the single trees, when the market impact is increased. The foreign exchange application considers a novel quad tree structure for evolving trading strategies. Each ofthe four trees serve different functions, i.e., long entry, long exit, short entry and short exit. Within this framework, the effects of money management are investigated for investors with different utility functions. Money management refers to the way in which practitioners use stop orders to control risk and take profits. Despite being widely used, it is found that money management has a detrimental effect on utility. JEL classifications: CO, CI5, C45, C53, C6I, C63, GIl Keywords: Genetic programming, optimization, trading strategies, market efficiency, intraday data, statistical arbitrage, portfolio construction, foreign exchange and money management.

Solving complex real-world problems often involves the simultaneous optimisation of multiple con icting performance criteria, these real-world problems occur in the elds of engineering, economics, chemistry, manufacturing, physics and many more. The optimisation process usually involves some design challenges in the form of the optimisation of a number of objectives and constraints. There exist many traditional optimisation methods (calculus based, random search, enumerative, etc.), however, these only o er a single solution in either adequate performance in a narrow problem domain or inadequate performance across a broad problem domain. Evolutionary Multi-objective Optimisation (EMO) algorithms are robust optimisers which are suitable for solving complex real-world multi-objective optimisation problems, as they are able to address each of the con icting objectives simultaneously. Typically, these EMO algorithms are run non-interactively with a Decision Maker (DM) setting the initial parameters of the algorithm and then analysing the results at the end of the optimisation process. When EMO is applied to real-world optimisation problems there is often a DM who is only interested in a portion of the Pareto-optimal front, however, incorporation of DM preferences is often neglected in the EMO literature. In this thesis, the incorporation of DM preferences into EMO search methods has been explored. This has been achieved through the review of EMO literature to identify a powerful method of variation, Covariance Matrix Adaptation (CMA), and its computationally infeasible EMO implementation, MO-CMA-ES. A CMA driven EMO algorithm, CMA-PAES, capable of optimisation in the presence of many objectives has been developed, benchmarked, and statistically veri ed to outperform MO-CMA-ES and MOEA/D-DRA on selected test suites. CMA-PAES and MOEA/D-DRA with the incorporation of the novel Weighted Z-score (WZ) preference articulation operator (supporting a priori, a posteriori or progressive incorporation) are then benchmarked on a range of synthetic and real-world problems. WZ-CMA-PAES is then successfully applied to a real-world problem regarding the optimisation of a classi er for concealed weapon detection, outperforming previously published classi er implementations.

An investigation has been made into hybrid systems which include stochastic and deterministic optimization. This thesis aims to provide new and relevant insights into the design of the nature-inspired hybrid optimization paradigms. It combines evolutionary and gradient-based methods. These hybrid evolutionary methods yield improved performance when applied to complex global optimization tasks and recent research has shown many of such hybridization policies. The thesis has three broad contributions. Firstly, by examination of stochastic optimization, supported by case studies, we utilised the Price's theorem to formulate a new population evolvability measure which assesses the dynamical characteristics of evolutionary operators. This leads to the development of a new convergence assessment method. A novel diversity control mechanism that uses heuristic initialisation and convergence detection mechanism is then proposed. Empirical support is provided to explicitly analyse the benefits of effective diversity control for continuous optimization. Secondly, this study utilised research relevance trees to evolve hybrid systems which combine various evolutionary computation (EC) models with the sequential quadratic programming (SQP) algorithm in a collaborative manner. We reviewed the convergence characteristics of various numerical optimization methods, and the concept of automatic differentiation is applied to design a vectorised forward derivative accumulation technique; this enables provision of accurate derivatives to the SQP algorithm. The SQP serves as a local optimizer in the deterministic phase of the hybrid models. Through benchmarking on stationary and dynamic problems, results showed that the proposed models achieved sufficient diversity control, which suggests improved exploration-exploitation balance. Thirdly, to mitigate the challenges of 'inappropriate' parameter settings, this thesis proposes closed-loop adaptive mechanisms which dynamically evolve effective step sizes for the evolutionary operators. It then examines the effect of incorporating a derivative-free algorithm which extends the hybrid model to a flexible and reusable algorithmic framework.

The manual design of microarchitecture is labour-intensive and unlikely to generate good counterintuitive solutions. A designer, guided solely by intuition, is forced to manipulate many interdependent parameters by hand, introducing simplifying assumptions that artificially limit the potential of the architecture. The sheer number of possible configurations precludes an exhaustive exploration of the entire search space. Evolutionary computation is a domain-independent, highly scalable technique capable of producing innovative designs with reasonable computational cost.
This study presents a software framework for designing microarchitecture. As a case study, a genetic algorithm is used to automatically synthesize two-level indirect branch predictors. The evolved designs routinely deliver enhanced performance as compared to the equivalent, highly optimized structures created by hand. The primary drawback associated with this method is the excessive design complexity induced by unconstrained evolution. Several methods of incorporating simplicity of design into the evolutionary process are investigated. A unified fitness metric, combining both simplicity and performance, leads to the evolution of simple and effective designs.

UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO
Síntese de Sistemas Fuzzy por Computação Evolucionária propõe uma metodologia de projeto para o desenvolvimento de sistemas fuzzy fundamentada em técnicas de computação evolucionária. Esta metodologia contempla as etapas de concepção do sistema fuzzy e a implementação em hardware do circuito eletrônico que o representa. A concepção do sistema é realizada num ambiente de projeto no qual sua base de conhecimento - composta da base de regras e demais parâmetros característicos - é evoluída, por intermédio de simulação, através do emprego de um novo algoritmo de três estágios que utiliza Algoritmos Genéticos. Esta estratégia enfatiza a interpretabilidade e torna a criação do sistema fuzzy mais simples e eficiente para o projetista, especialmente quando comparada com o tradicional ajuste por tentativa e erro. A implementação em hardware do circuito é realizada em plataforma de desenvolvimento baseada em Eletrônica Evolucionária. Um conjunto de circuitos, denominados de blocos funcionais, foi desenvolvido e evoluído com sucesso para viabilizar a construção da estrutura final do sistema fuzzy.
Synthesis of Fuzzy Systems through Evolutionary Computation proposes a methodology for the design of fuzzy systems based on evolutionary computation techniques. A three-stage evolutionary algorithm that uses Genetic Algorithms (GAs) evolves the knowledge base of a fuzzy system - rule base and parameters. The evolutionary aspect makes the design simpler and more efficient, especially when compared with traditional trial and error methods. The method emphasizes interpretability so that the resulting strategy is clearly stated. An Evolvable Hardware (EHW) platform for the synthesis of analog electronic circuits is proposed. This platform, which can be used for the implementation of the designed fuzzy system, is based on a Field Programmable Analog Array (FPAA). A set of evolved circuits called functional blocks allows the implementation of the fuzzy system.

Darwinian Evolutionary system - a system satisfying the abstract conditions: reproduction with heritable variation, in a finite world, giving rise to Natural Selection encompasses a complex and subtle system of interrelated theories, whose substantive transplantation to any artificial medium let it be mathematical model or computational model - will be very far from easy. There are two motives in bringing Darwinian evolution into computational frameworks: one to understand the Darwinian evolution, and the other is to view Darwinian evolution - that carries out controlled adaptive-stochastic search in the space of all possible DNA-sequences for emergence and improvement of the living beings on our planet - as an optimization process, which can be simulated in appropriate frameworks to solve some intractable problems. The first motive led to emerging field of study commonly referred to as Artificial Life, and other gave way to emergence of Evolutionary Computation, which is speculated to be the only practical path to the development of ontogenetic machine intelligence. In this thesis we touch upon all the above aspects. Natural selection is the central concept of Darwinian evolution and hence capturing natural selection in computational frameworks which maintains the spirit of Darwinian evolution in the sense of conventional, terrestrial and biological perspectives is essential. Naive models of evolution define natural selection as a process which brings in differential reproductive capabilities in organisms of a population, and hence, most of the evolutionary simulations in Artificial Life and Evolutionary Computation implement selection by differential reproduction: the Attest members of the population are reproduced preferentially at the expense of the less fit members of the population. Formal models in evolutionary biology often subdivide selection into components called 'episodes of selection' to capture the different complex mechanisms of nature by which Darwinian evolution can occur. In this thesis we introduce the concept of 'episodes of selection' into computational frameworks of Darwinian evolution by means of A Conceptual Evolutionary model (ACE-model). ACE-model is proposed to be simple and yet it captures the essential features of modern evolutionary perspectives in evolutionary computation framework. ACE-model is rich enough to offer abstract and structural framework for evolutionary computation and can serve as a basic model for evolutionary algorithms. It captures selection in two episodes in two phases of evolutionary cycle and it offers various parameters by which evolutionary algorithms can control selection mechanisms. In this thesis we propose two evolutionary algorithms namely Malthus evolutionary algorithms and Malthus Spencer evolutionary algorithms based on the ACE-model and we discuss the relevance of parameters offered by ACE-model by simulation studies. As an application of ACE-model to artificial life we study misconceptions involved in defining fitness in evolutionary biology, and we also discuss the importance of introducing fitness landscape in the theories of Darwinian evolution. Another important and independent contribution of this thesis is: A Mathematical Abstraction of Evolutionary process. Evolutionary process is characterized by Evolutionary Criteria and Evolutionary Mechanism which are formalized by classical mathematical tools. Even though the model is in its premature stage to develop any theory based on it, we develop convergence criteria of evolutionary process based on this model.

Darwinian Evolutionary system - a system satisfying the abstract conditions: reproduction with heritable variation, in a finite world, giving rise to Natural Selection encompasses a complex and subtle system of interrelated theories, whose substantive transplantation to any artificial medium let it be mathematical model or computational model - will be very far from easy. There are two motives in bringing Darwinian evolution into computational frameworks: one to understand the Darwinian evolution, and the other is to view Darwinian evolution - that carries out controlled adaptive-stochastic search in the space of all possible DNA-sequences for emergence and improvement of the living beings on our planet - as an optimization process, which can be simulated in appropriate frameworks to solve some intractable problems. The first motive led to emerging field of study commonly referred to as Artificial Life, and other gave way to emergence of Evolutionary Computation, which is speculated to be the only practical path to the development of ontogenetic machine intelligence. In this thesis we touch upon all the above aspects. Natural selection is the central concept of Darwinian evolution and hence capturing natural selection in computational frameworks which maintains the spirit of Darwinian evolution in the sense of conventional, terrestrial and biological perspectives is essential. Naive models of evolution define natural selection as a process which brings in differential reproductive capabilities in organisms of a population, and hence, most of the evolutionary simulations in Artificial Life and Evolutionary Computation implement selection by differential reproduction: the Attest members of the population are reproduced preferentially at the expense of the less fit members of the population. Formal models in evolutionary biology often subdivide selection into components called 'episodes of selection' to capture the different complex mechanisms of nature by which Darwinian evolution can occur. In this thesis we introduce the concept of 'episodes of selection' into computational frameworks of Darwinian evolution by means of A Conceptual Evolutionary model (ACE-model). ACE-model is proposed to be simple and yet it captures the essential features of modern evolutionary perspectives in evolutionary computation framework. ACE-model is rich enough to offer abstract and structural framework for evolutionary computation and can serve as a basic model for evolutionary algorithms. It captures selection in two episodes in two phases of evolutionary cycle and it offers various parameters by which evolutionary algorithms can control selection mechanisms. In this thesis we propose two evolutionary algorithms namely Malthus evolutionary algorithms and Malthus Spencer evolutionary algorithms based on the ACE-model and we discuss the relevance of parameters offered by ACE-model by simulation studies. As an application of ACE-model to artificial life we study misconceptions involved in defining fitness in evolutionary biology, and we also discuss the importance of introducing fitness landscape in the theories of Darwinian evolution. Another important and independent contribution of this thesis is: A Mathematical Abstraction of Evolutionary process. Evolutionary process is characterized by Evolutionary Criteria and Evolutionary Mechanism which are formalized by classical mathematical tools. Even though the model is in its premature stage to develop any theory based on it, we develop convergence criteria of evolutionary process based on this model.

Thesis (Ph. D.)--George Mason University, 2007.
Title from PDF t.p. (viewed Jan. 22, 2008). Thesis director: Kenneth A. De Jong. Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science. Vita: p. 422. Includes bibliographical references (p. 413-421). Also available in print.

Evolutionary computation is a field which uses natural computational processes to optimize mathematical and industrial problems. Differential Evolution, Particle Swarm Optimization and Estimation of Distribution Algorithm are some of the newer emerging varieties which have attracted great interest among researchers. This work has compared these three algorithms on a set of mathematical and machine learning benchmarks and also synthesized a new algorithm from the three other ones and compared it to them. The results from the benchmark show which algorithm is best suited to handle various machine learning problems and presents the advantages of using the new algorithm. The new algorithm called DEDA (Differential Estimation of Distribution Algorithms) has shown promising results at both machine learning and mathematical optimization tasks.

In real world many complex systems can be naturally represented as complex networks of which one distinctive feature is the community structure. The community detection, i.e., identifying the community structure, provides insight into the relationship and interaction between network function and topology and has become increasingly important in many scientific fields. In this thesis, we firstly propose a cooperative coevolutionary module identification algorithm named CoCoMi to address the scalability problem when detecting community structures in especially medium and large-scale complex networks. Secondly, we propose a consensus community detection algorithm based on the multimodal optimization and fast Surprise named CoCoMOS to detect community structures in complex networks. Thirdly, we propose an adaptive ensemble selection and multimodal optimization based consensus community detection algorithm named MASCOD to find high quality and stable consensus partitions of community structures in complex networks. The performance of these three proposed algorithms is evaluated on some well-known social, artificial and biological complex networks and experimental results demonstrate that all these three proposed algorithms have very competitive performance compared with other state-of-the-art community detection algorithms.

The objective of Evolutionary Computation is to solve practical problems (e.g.optimization, data mining) by simulating the mechanisms of natural evolution. This thesis addresses several topics related to adaptation and self-organization in evolving systems with the overall aims of improving the performance of Evolutionary Algorithms (EA), understanding its relation to natural evolution, and incorporating new mechanisms for mimicking complex biological systems. Part I of this thesis presents a new mechanism for allowing an EA to adapt its behavior in response to changes in the environment. Using the new approach, adaptation of EA behavior (i.e. control of EA design parameters) is driven by an analysis of population dynamics, as opposed to the more traditional use of fitness measurements. Comparisons with a number of adaptive control methods from the literature indicate substantial improvements in algorithm performance for a range of artificial and engineering design problems. Part II of this thesis involves a more thorough analysis of EA behavior based on the methods derived in Part 1. In particular, several properties of EA population dynamics are measured and compared with observations of evolutionary dynamics in nature. The results demonstrate that some large scale spatial and temporal features of EA dynamics are remarkably similar to their natural counterpart. Compatibility of EA with the Theory of Self-Organized Criticality is also discussed. Part III proposes fundamentally new directions in EA research which are inspired by the conclusions drawn in Part II. These changes involve new mechanisms which allow selforganization of the EA to occur in ways which extend beyond its common convergence in parameter space. In particular, network models for EA populations are developed where the network structure is dynamically coupled to EA population dynamics. Results indicate strong improvements in algorithm performance compared to cellular Genetic Algorithms and non-distributed EA designs. Furthermore, topological analysis indicates that the population network can spontaneously evolve to display similar characteristics to the interaction networks of complex biological systems.

Thesis (Ph.D.)--University of Mississippi, 2008.
Typescript. Vita. "May 2008." Major professor: Greg Easson Includes bibliographical references (leaves145-154). Also available online via ProQuest to authorized users.

Simulation and game content includes the levels, models, textures, items, and other objects encountered and possessed by players during the game. In most modern video games and simulation software, the set of content shipped with the product is static and unchanging, or at best, randomized within a narrow set of parameters. However, ideally, if game content could be constantly and automatically renewed, players would remain engaged longer in the evolving stream of content. This dissertation introduces three novel technologies that together realize this ambition. (1) The first, NEAT Particles, is an evolutionary method to enable users to quickly and easily create complex particle effects through a simple interactive evolutionary computation (IEC) interface. That way, particle effects become an evolvable class of content, which is exploited in the remainder of the dissertation. In particular, (2) a new algorithm called content-generating NeuroEvolution of Augmenting Topologies (cgNEAT) is introduced that automatically generates graphical and game content while the game is played, based on the past preferences of the players. Through cgNEAT, the game platform on its own can generate novel content that is designed to satisfy its players. Finally, (3) the Galactic Arms Race (GAR) multiplayer online video game is constructed to demonstrate these techniques working on a real online gaming platform. In GAR, which was made available to the public and playable online, players pilot space ships and fight enemies to acquire unique particle system weapons that are automatically evolved by the cgNEAT algorithm. The resulting study shows that cgNEAT indeed enables players to discover a wide variety of appealing content that is not only novel, but also based on and extended from previous content that they preferred in the past. The implication is that with cgNEAT it is now possible to create applications that generate their own content to satisfy users, potentially significantly reducing the cost of content creation and considerably increasing entertainment value with a constant stream of evolving content.
Ph.D.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Science PhD

This thesis examines the application of two evolutionary computation techniques to two different aspects of open channel flow. The first part of the work is concerned with evaluating the ability of an evolutionary algorithm to provide insight and guidance into the correct magnitude and trend of the three parameters required in order to successfully apply a quasi 2D depth averaged Reynolds Averaged Navier Stokes (RANS) model to the flow in prismatic open channels. The RANS modeled adopted is the Shiono Knight Method (SKM) which requires three input parameters in order to provide closure, i.e. the friction factor (\(f\)), dimensionless eddy viscosity (λ) and a sink term representing the effects of secondary flow (Γ). A non-dominated sorting genetic algorithm II (NSGA-II) is used to construct a multiobjective evolutionary based calibration framework for the SKM from which conclusions relating to the appropriate values of \(f\), λ and Γ are made. The framework is applied to flows in homogenous and heterogeneous trapezoidal channels, homogenous rectangular channels and a number of natural rivers. The variation of \(f\), λ and Γ with the wetted parameter ratio (\(P_b\)/\(P_w\)) and panel structure for a variety of situations is investigated in detail. The situation is complex: \(f\) is relatively independent of the panel structure but is shown to vary with P\(_b\)/P\(_w\), the values of λ and Γ are highly affected by the panel structure but λ is shown to be relatively insensitive to changes in \(P_b\)/\(P_w\). Appropriate guidance in the form of empirical equations are provided. Comparing the results to previous calibration attempts highlights the effectiveness of the proposed semi-automated framework developed in this thesis. The latter part of the thesis examines the possibility of using genetic programming as an effective data mining tool in order to build a model induction methodology. To this end the flow over a free overfall is exampled for a variety of cross section shapes. In total, 18 datasets representing 1373 experiments were interrogated. It was found that an expression of form \(h_c\)=A\(h_e\)\(^{B\sqrt S_o}\), where \(h_c\) is the critical depth, \(h_e\) is the depth at the brink, \(S_o\) is the bed slope and A and B are two cross section dependant constants, was valid regardless of cross sectional shape and Froude number. In all of the cases examined this expression fitted the data to within a coefficient of determination (CoD) larger than 0.975. The discovery of this single expression for all datasets represents a significant step forward and highlights the power and potential of genetic programming.

With the enormous growth of users' reliance on the Internet, the need for secure and reliable computer networks also increases. Availability of effective automatic tools for carrying out different types of network attacks raises the need for effective intrusion detection systems. Generally, a comprehensive defence mechanism consists of three phases, namely, preparation, detection and reaction. In the preparation phase, network administrators aim to find and fix security vulnerabilities (e.g., insecure protocol and vulnerable computer systems or firewalls), that can be exploited to launch attacks. Although the preparation phase increases the level of security in a network, this will never completely remove the threat of network attacks. A good security mechanism requires an Intrusion Detection System (IDS) in order to monitor security breaches when the prevention schemes in the preparation phase are bypassed. To be able to react to network attacks as fast as possible, an automatic detection system is of paramount importance. The later an attack is detected, the less time network administrators have to update their signatures and reconfigure their detection and remediation systems. An IDS is a tool for monitoring the system with the aim of detecting and alerting intrusive activities in networks. These tools are classified into two major categories of signature-based and anomaly-based. A signature-based IDS stores the signature of known attacks in a database and discovers occurrences of attacks by monitoring and comparing each communication in the network against the database of signatures. On the other hand, mechanisms that deploy anomaly detection have a model of normal behaviour of system and any significant deviation from this model is reported as anomaly. This thesis aims at addressing the major issues in the process of developing signature based IDSs. These are: i) their dependency on experts to create signatures, ii) the complexity of their models, iii) the inflexibility of their models, and iv) their inability to adapt to the changes in the real environment and detect new attacks. To meet the requirements of a good IDS, computational intelligence methods have attracted considerable interest from the research community. This thesis explores a solution to automatically generate compact rulesets for network intrusion detection utilising evolutionary computation techniques. The proposed framework is called ESR-NID (Evolving Statistical Rulesets for Network Intrusion Detection). Using an interval-based structure, this method can be deployed for any continuous-valued input data. Therefore, by choosing appropriate statistical measures (i.e. continuous-valued features) of network trafc as the input to ESRNID, it can effectively detect varied types of attacks since it is not dependent on the signatures of network packets. In ESR-NID, several innovations in the genetic algorithm were developed to keep the ruleset small. A two-stage evaluation component in the evolutionary process takes the cooperation of rules into consideration and results into very compact, easily understood rulesets. The effectiveness of this approach is evaluated against several sources of data for both detection of normal and abnormal behaviour. The results are found to be comparable to those achieved using other machine learning methods from both categories of GA-based and non-GA-based methods. One of the significant advantages of ESR-NIS is that it can be tailored to specific problem domains and the characteristics of the dataset by the use of different fitness and performance functions. This makes the system a more flexible model compared to other learning techniques. Additionally, an IDS must adapt itself to the changing environment with the least amount of configurations. ESR-NID uses an incremental learning approach as new flow of traffic become available. The incremental learning approach benefits from less required storage because it only keeps the generated rules in its database. This is in contrast to the infinitely growing size of repository of raw training data required for traditional learning.

Thesis (M.S.)--Missouri University of Science and Technology, 2008.
Vita. The entire thesis text is included in file. Title from title screen of thesis/dissertation PDF file (viewed June 18, 2009) Includes bibliographical references (p. 62-64).

As the complexity of our society and computational resources increases, so does the complexity of the problems that we approach using evolutionary search techniques. There are recent approaches to deal with the problem of scaling evolutionary methods to cope with highly complex difficult problems. Many of these approaches are biologically inspired and share an underlying principle: a problem representation based on basic representational building blocks that interact and self-organize into complex functions or designs. The observation from the central dogma of molecular biology that proteins are the basic building blocks of life and the recent advances in proteomics on analysis of structure, function and interaction of entire protein complements, lead us to propose a unifying framework of thought for these approaches: the proteomics approach. This thesis propose to investigate whether the self-organization of protein analogous structures at the representation level can increase the degree of complexity and ``novelty'' of solutions obtainable using evolutionary search techniques. In order to do so, we identify two fundamental aspects of this transition: (1) proteins interact in a three dimensional medium analogous to a multiset; and (2) proteins are functional structures. The first aspect is foundational for understanding of the second. This thesis analyzes the first aspect. It investigates the effects of using a genome to proteome mapping on evolutionary computation. This analysis is based on a genetic algorithm (GA) with a string to multiset mapping that we call the proportional genetic algorithm (PGA), and it focuses on the feasibility and effectiveness of this mapping. This mapping leads to a fundamental departure from typical EC methods: using a multiset of proteins as an intermediate mapping results in a \emph{completely location independent} problem representation where the location of the genes in a genome has no effect on the fitness of the solutions. Completely location independent representations, by definition, do not suffer from traditional EC hurdles associated with the location of the genes or positional effect in a genome. Such representations have the ability to self-organize into a genomic structure that appears to favor positive correlations between form and quality of represented solutions. Completely location independent representations also introduce new problems of their own such as the need for large alphabets of symbols and the theoretical need for larger representation spaces than traditional approaches. Overall, these representations perform as well or better than traditional representations and they appear to be particularly good for the class of problems involving proportions or multisets. This thesis concludes that the use of protein analogous structures as an intermediate representation in evolutionary computation is not only feasible but in some cases advantageous. In addition, it lays the groundwork for further research on proteins as functional self-organizing structures capable of building increasingly complex functionality, and as basic units of problem representation for evolutionary computation.
Ph.D.
School of Computer Science
Engineering and Computer Science
Computer Science

Optimal generation scheduling attempts to minimise the cost of power production while satisfying the various operation constraints and physical limitations on the power system components. The thermal generation scheduling problem can be considered as a power system control problem acting over different time frames. The unit commitment phase determines the optimum pattern for starting up and shutting down the generating units over the designated scheduling period, while the economic dispatch phase is concerned with allocation of the load demand among the on-line generators. In a hydrothermal system the optimal scheduling of generation involves the allocation of generation among the hydro electric and thermal plants so as to minimise total operation costs of thermal plants while satisfying the various constraints on the hydraulic and power system network. This thesis reports on the development of genetic algorithm computation techniques for the solution of the short term generation scheduling problem for power systems having both thermal and hydro units. A comprehensive genetic algorithm modelling framework for thermal and hydrothermal scheduling problems using two genetic algorithm models, a canonical genetic algorithm and a deterministic crowding genetic algorithm, is presented. The thermal scheduling modelling framework incorporates unit minimum up and down times, demand and reserve constraints, cooling time dependent start up costs, unit ramp rates, and multiple unit operating states, while constraints such as multiple cascade hydraulic networks, river transport delays and variable head hydro plants, are accounted for in the hydraulic system modelling. These basic genetic algorithm models have been enhanced, using quasi problem decomposition, and hybridisation techniques, resulting in efficient generation scheduling algorithms. The results of the performance of the algorithms on small, medium and large scale power system problems is presented and compared with other conventional scheduling techniques.

COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
Esta dissertação investiga um sistema baseado em algoritmos genéticos e algoritmos culturais, aplicado ao processo de desenvolvimento de um campo de petróleo. O desenvolvimento de um campo de petróleo consiste, neste caso, da disposição de poços num reservatório petrolífero, já conhecido e delimitado, que permita maximizar o Valor Presente Líquido. Uma disposição de poços define a quantidade e posição de poços produtores e injetores e do tipo de poço (horizontalou vertical) a serem empregados no processo de exploração. O objetivo do trabalho é avaliar o desempenho de Algoritmos Genéticos e Algoritmos Culturais como métodos de apoio à decisão na otimização de alternativas de produção em reservatórios petrolíferos. Determinar a localização de novos poços de petróleo em um reservatório é um problema complexo que depende de propriedades do reservatório e critérios econômicos, entre outros fatores. Para que um processo de otimização possa ser aplicado nesse problema, é necessário definir uma função objetivo a ser minimizada ou maximizada pelo processo. No problema em questão, a função objetivo a ser maximizada é o Valor Presente Líquido (VPL). Para se estabelecer o VPL, subtrai-se os gastos com a exploração do valor correspondente ao volume de petróleo estimado da reserva. Devido à complexidade do perfil de produção de petróleo, exige-se a utilização de simuladores de reservatório para esta estimativa. Deste modo, um simulador de reservatórios é parte integrante da função de avaliação. O trabalho de pesquisa foi desenvolvido em quatro etapas: um estudo sobre a área de exploração de petróleo; um estudo dos modelos da inteligência computacional empregados nesta área; a definição e implementação de um modelo genético e cultural para o desenvolvimento de campo petrolífero e o estudo de caso. O estudo sobre a área de exploração de campo de petróleo envolveu a teoria necessária para a construção da função objetivo. No estudo sobre as técnicas de inteligência computacional definiu-se os conceitos principais sobre Algoritmo Genético e Algoritmo Cultural empregados nesta dissertação. A modelagem de um Algoritmo Genético e Cultural constitui no emprego dos mesmos, para que dado um reservatório petrolífero, o sistema tenha condições de reconhecê-lo e desenvolvê-lo, ou seja, encontrar a configuração (quantidade, localização e tipo de poços) que atinja um maior Valor Presente Líquido. Os resultados obtidos neste trabalho indicam a viabilidade da utilização de Algoritmos Genéticos e Algoritmos Culturais no desenvolvimento de campos de petróleo.
This dissertation investigates a system based in genetic algorithms and cultural algorithms, applied to the development process of a petroleum field. The development of a petroleum field consists in the placement of wells in an already known and delimited petroleum reservoir, which allows maximizing the Net Present Value. A placement of wells defines the quantity and position of the producing wells, the injecting wells, and the wells type (horizontal or vertical) to be used in the exploration process. The objective of this work is to evaluate the performance of Genetic Algorithms and Cultural Algorithms as decision support methods on the optimization of production alternatives in petroleum reservoirs. Determining the new petroleum wells location in a reservoir is a complex problem that depends on the properties of the reservoir and on economic criteria, among other factors. In order to an optimization process to be applied to this problem, it s necessary to define a target function to be minimized or maximized by the process. In the given problem, the target function to be maximized is the Net Present Value (NPV). In order to establish the NPV, the exploration cost correspondent to the estimated reservoir petroleum volume is deducted. The complexity of the petroleum s production profile implies on the use of reservoirs simulators for this estimation. In this way, a reservoir simulator is an integrant part of the evaluation function. The research work was developed in four phases: a study about the petroleum exploration field; a study about the applied computational intelligence models in this area; the definition and implementation of a genetic and cultural model for the development of petroliferous fields and the case study. The study about the petroleum exploration field involved all the necessary theory for the building of the target function. In the study about the computational intelligence techniques, the main concepts about the Genetic Algorithms and Cultural Algorithms applied in this dissertation were defined. The modeling of Genetic and Cultural Algorithms consisted in applying them so that, given a petroleum reservoir, the system is capable of evolve and find configurations (quantity, location and wells type) that achieve greater Net Present Values. The results obtained in this work, indicate that the use of Genetic Algorithms and Cultural Algorithms in the development of petroleum fields is a promising alternative.

A problem in Software Reuse (SR) is to find a software component appropriate to a given requirement. At present this is done by manual browsing through large libraries which is very time consuming and therefore expensi ve. Further to this, if the component is not the same as, but similar to a requirement, the component must be adapted to meet the requirements. This browsing and adaptation requires a skilled user who can comprehend library entries and foresee their application. It is expensive to train users and to produce these documented libraries. The specialised software design domain, chosen in this thesis, is that of Field Programmable Gate Arrays (FPGAs) programs. FPGAs are user programmable microchips that have many applications including encryption and control. This thesis is concerned with a specific technique for FGPA programming that uses Evolutionary Computing (EC) techniques to synthesize FPGA programs. Evolutionary Computing (EC) techniques are based on natural systems such as the life cycle of living organisms or the formation of crystalline structures. They can generate solutions to problems without the need for complete understanding of the problem. EC has been used to create software programs, and can be used as a knowledge-lean approach for generating libraries of software solutions. EC techniques produce solutions without documentation. To automate SR it has been shown that it is essential to understand the knowledge in the software library. In this thesis techniques for automatically documenting EC produced solutions are illustrated. It is also helpful to understand the principles at work in the reuse process. On examination of large collections of evolved programs it is shown that these programs contain reusable modules. Further to this, it is shown that by studying series of similar software components, principles of scale can be deduced. Case Based Reasoning (CBR) is a problem solving method that reuses old solutions to solve new problems and is an effective method of automatically reusing software libraries. These techniques enable automated creation, documentation and reuse of a software library. This thesis proposes that CBR is a feasible method for the reuse of EC designed FPGA programs. It is shown that EC synthesised FPGA programs can be documented, reused, and adapted to solve new problems, using automated CBR techniques.

Cloud computing is an emerging computing paradigm in which IT resources are provided over the Internet as a service to users. One such service offered through the Cloud is Software as a Service or SaaS. SaaS can be delivered in a composite form, consisting of a set of application and data components that work together to deliver higher-level functional software. SaaS is receiving substantial attention today from both software providers and users. It is also predicted to has positive future markets by analyst firms. This raises new challenges for SaaS providers managing SaaS, especially in large-scale data centres like Cloud. One of the challenges is providing management of Cloud resources for SaaS which guarantees maintaining SaaS performance while optimising resources use. Extensive research on the resource optimisation of Cloud service has not yet addressed the challenges of managing resources for composite SaaS. This research addresses this gap by focusing on three new problems of composite SaaS: placement, clustering and scalability. The overall aim is to develop efficient and scalable mechanisms that facilitate the delivery of high performance composite SaaS for users while optimising the resources used. All three problems are characterised as highly constrained, large-scaled and complex combinatorial optimisation problems. Therefore, evolutionary algorithms are adopted as the main technique in solving these problems. The first research problem refers to how a composite SaaS is placed onto Cloud servers to optimise its performance while satisfying the SaaS resource and response time constraints. Existing research on this problem often ignores the dependencies between components and considers placement of a homogenous type of component only. A precise problem formulation of composite SaaS placement problem is presented. A classical genetic algorithm and two versions of cooperative co-evolutionary algorithms are designed to now manage the placement of heterogeneous types of SaaS components together with their dependencies, requirements and constraints. Experimental results demonstrate the efficiency and scalability of these new algorithms. In the second problem, SaaS components are assumed to be already running on Cloud virtual machines (VMs). However, due to the environment of a Cloud, the current placement may need to be modified. Existing techniques focused mostly at the infrastructure level instead of the application level. This research addressed the problem at the application level by clustering suitable components to VMs to optimise the resource used and to maintain the SaaS performance. Two versions of grouping genetic algorithms (GGAs) are designed to cater for the structural group of a composite SaaS. The first GGA used a repair-based method while the second used a penalty-based method to handle the problem constraints. The experimental results confirmed that the GGAs always produced a better reconfiguration placement plan compared with a common heuristic for clustering problems. The third research problem deals with the replication or deletion of SaaS instances in coping with the SaaS workload. To determine a scaling plan that can minimise the resource used and maintain the SaaS performance is a critical task. Additionally, the problem consists of constraints and interdependency between components, making solutions even more difficult to find. A hybrid genetic algorithm (HGA) was developed to solve this problem by exploring the problem search space through its genetic operators and fitness function to determine the SaaS scaling plan. The HGA also uses the problem's domain knowledge to ensure that the solutions meet the problem's constraints and achieve its objectives. The experimental results demonstrated that the HGA constantly outperform a heuristic algorithm by achieving a low-cost scaling and placement plan. This research has identified three significant new problems for composite SaaS in Cloud. Various types of evolutionary algorithms have also been developed in addressing the problems where these contribute to the evolutionary computation field. The algorithms provide solutions for efficient resource management of composite SaaS in Cloud that resulted to a low total cost of ownership for users while guaranteeing the SaaS performance.

Thesis (M.S.)--Missouri University of Science and Technology, 2009.
Vita. The entire thesis text is included in file. Title from title screen of thesis/dissertation PDF file (viewed August 10, 2009) Includes bibliographical references (p. 49-51).

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, June 2014.
Cataloged from PDF version of thesis. "May 23, 2014."
Includes bibliographical references (page 37).
We implemented a distributed evolutionary computation system titled EvoGPJ Star (EGS) and deployed the system onto Boinc, a volunteer computing network (VCN). Evolutionary computation is computationally expensive and VCN allows more cost-effective cluster computing since resources are donated. In addition, we believe that the design similarities between EGS and our chosen VCN (Boinc) would allow for easy integration of the two systems. EGS follows a centralized design pattern, with multiple engines communicating with a central coordinator and case server. The coordinator synchronizes up engines to run experiments and also stores and distributes individual solutions among engines. The engine-coordinator model creates a scalable (engines can be easily added) and robust (can continue to operate if nodes fail) system. For our experiment we chose rule-based classification. We saw the distributed EGS solutions (standard and Boinc) outperform the single-engine system. Deploying the system to Boinc revealed some design conflicts between Boinc and EGS experimentation. These conflicts stemmed from the asynchronous and asymmetric nature of VCNs.
by Otitochi Mbagwu.
M. Eng.

Mobile ad hoc networks (MANETs) are one of the fastest growing areas of research. By providing communications in the absence of a fixed infrastructure MANETs are an attractive technology for many applications. However, this flexibility introduces new security threats. Furthermore the traditional way of protecting networks is not directy applicable to MANETs. Many conventional security solutions are ineffective and inefficient for the highly dynamic and resource-constrained environments where MANET use might be expected. Since prevention techniques are never enough, intrusion detection systems (IDSs), which monitor system activities and detect intrusions, are generally used to complement other security mechanisms. %due to the dynamic nature %of MANETs, the lack of central points, and their highly constrained nodes. How to detect intrusions effectively and efficiently on this highly dynamic, distributed and resource-constrained environment is a challenging research problem. In the presence of these complicating factors humans are not particularly adept at making good design choices. That is the reason we propose to use techniques from artificial intelligence to help with this task. We investigate the use of evolutionary computation techniques for synthesising intrusion detection programs on MANETs. We evolve programs to detect the following attacks against MANETs: ad hoc flooding, route disruption, and dropping attacks. The performance of evolved programs is evaluated on simulated networks. The results are also compared with hand-coded programs. A good IDS on MANETs should also consider the resource constraints of the MANET environments. Power is one of the critical resources. Therefore we apply multi-objective optimization techniques (MOO) to discover trade-offs between intrusion detection ability and energy consumption of programs, and optimise these objectives simultaneously. We also investigate a suitable IDS architecture for MANETs in this thesis. Different programs are evolved for two architectures: local and cooperative detection in neighbourhood. Optimal trade-offs between intrusion detection ability and resource usage (energy, bandwidth) of evolved programs are also discovered using MOO techniques.

Dissertação de Mestrado em Engenharia Informática apresentada à Faculdade de Ciências e Tecnologia da Universidade de Coimbra
The impact of Natural Selection overshadowed Darwin's Sexual Selection theory. However, over the past few decades it begun to draw the attention of researchers from several di erent elds and the amount of supporting evidence of its role in evolution rapidly increased. Today, although the dynamics aren't fully understood, the importance of sexual selection in evolution is undebatable. The enthusiasm around this eld was not followed by evolutionary computation. On the one hand, canonical evolutionary computation systems were already well-established when sexual selection re-surfaced. On the other, so far, attempts to incorporate sexual selection approaches in evolutionary computation, particularly when applied to optimization problems, have encountered several di culties and no generic tools and approaches applicable to a wide variety of problems exist. This dissertation constitutes a step towards changing this situation. Based on an embracing survey of the state of the art and following a natureinspired approach, a popular evolutionary computation framework is expanded through the incorporation of Mate Choice mechanisms { enabling the application of sexual selection models to a wide variety of problems with little e ort. The approach is tested on symbolic regression benchmark problems. The analysis of such problems indicates that sexual selection is able to outperform conventional approaches in complex problem instances. Additional testing and analysis focused on understanding how sexual selection contributes to the evolution. The experimental results show that the evolved mate choice functions are able to select mating partners in meaningful ways, contributing to the evolutionary success of the descendants.