Rapid advances in integration technology have tremendously increased the design complexity of very large scale integrated (VLSI) circuits, necessitating robust optimization techniques in many stages of VLSI design. A genetic algorithm (GA) is a stochastic optimization technique that uses principles derived from the evolutionary process in nature. In this work, genetic algorithms are used to alleviate the hardware design process of VLSI application specific integrated circuits (ASICs) and reconfigurable hardware. VLSI ASIC design suffers from high design complexity and a large number of optimization objectives requiring hierarchical design approaches and multi-objective optimization techniques. The floorplanning stage of the design cycle becomes highly important in hierarchical design methods. In this work, a multi-objective genetic algorithm based floorplanner has been developed with novel crossover operators to address the multi-objective floorplanning problem for VLSI ASICs. The genetic floorplanner achieves significant wirelength savings (>19% on average) with little or no increase in area ( < 3% penalty) over previous floorplanners that perform simultaneous area and wirelength minimization. Hardware implementation of genetic algorithms is gaining importance because of their proven effectiveness as optimization engines for real-time applications. Earlier hardware implementations suffer from major drawbacks such as absence of GA parameter programmability, rigid pre-defined system architecture, and lack of support for multiple fitness functions. A compact IP core that implements a general purpose GA engine has been designed to realize evolvable hardware in field programmable gate array devices. The designed GA core achieved a speedup of around 5.16x over an analogous software implementation. Novel reconfigurable analog architectures have been proposed to realize extreme environment analog electronics. In this work, a digital framework has been developed to realize self reconfigurable analog arrays (SRAA) where genetic algorithms are used to evolve the required analog functionality and compensate performance degradation in extreme environments. The framework supports two methods of compensation, namely, model based lookup and genetic algorithm based compensation and is scalable in terms of the number of fitness evaluation modules. The entire framework has been implemented as a digital ASIC in a leading industrystrength silicon-on-insulator (SOI) technology to obtain high performance and a small form factor.

Il a été observé que l'exécution des heuristiques de recherche aléatoire dépend d'un ou de plusieurs paramètres. Un certain nombre de résultats montrent un avantage des paramètres dynamiques, c'est-à-dire que les paramètres de l'algorithme sont modifiés au cours de son exécution. Dans ce travail, nous montrons que la complexité de la boîte noire sans biais de la classe de fonction de référence OneMax est $n ln(n) - cn pm o(n)$ pour une constante $c$ comprise entre $0.2539$ et $0.2665$. L'exécution peut être réalisé avec un algorithme simple de type-(1+1) utilisant une puissance de mutation fitness dépendant. Une fois traduite dans le cas du budget fixe, notre algorithme trouve des solutions plus proches de l'optimum de 13% que celles des meilleurs algorithmes connus.Basé sur la puissance de mutation optimale analysée pour OneMaX, nous montrons qu'un choix auto-ajusté du nombre de bits à retourner atteint le même temps d'exécution (excepté $o(n)$ termes inférieurs) et le même (asymptotique) 13% amélioration de la fitness-distance par rapport au RLS. Le mécanisme d'ajustement doit apprendre de manière adaptative la puissance de mutation actuellement optimale des itérations précédentes. Cela vise à la fois à exploiter le fait que des problèmes généralement différents peuvent nécessiter des puissances de mutation différentes et que, pour un problème fixe, différentes puissances peuvent devenir optimales à différentes étapes du processus d'optimisation.Nous étendons ensuite notre stratégie d'auto-ajustement aux algorithmes évolutifs basés sur la population dans des espaces discrets de recherche. Grosso modo, il consiste à créer la moitié de la descendance avec un taux de mutation qui est deux fois plus élevé que le taux de mutation actuel et l'autre moitié avec la moitié du taux actuel. Le taux de mutation est ensuite mis à jour au taux utilisé dans cette sous-population qui contient la meilleure descendance. Nous analysons comment l'algorithme d'évolution $(1+lambda)$ avec ce taux de mutation auto-ajustable optimise la fonction de test OneMax. Nous montrons que cette version dynamique de $(1+lambda)$~EA trouve l'optimum dans un temps d'optimisation attendu (nombre d'évaluations de la fitness) de $O(nlambda/loglambda+nlog n)$. Le temps est asymptotiquement plus petit que le temps d'optimisation de l'EA classique $(1+lambda)$. Des travaux antérieurs montrent que cette performance est la meilleure possible parmi tous les algorithmes de boîtes noires sans biais unaire basés sur des mutations $lambda$-parallèles.Nous proposons et analysons également une version auto-réglage de l'algorithme évolutionnaire $(1,lambda)$ dans lequel le taux de mutation actuel fait partie de l'individu et donc également sujet à mutation. Une analyse d'exécution rigoureuse sur la fonction de référence OneMax révèle qu'un simple schéma de mutation pour le taux conduit à un temps d'optimisation attendu du meilleur $O(nlambda/loglambda+nlog n)$. Notre résultat montre que l'auto-réglage dans le calcul évolutif peut trouver automatiquement des paramètres optimaux complexes. En même temps, cela prouve qu'un schéma d'auto-ajustement relativement compliqué pour le taux de mutation peut être remplacé par notre schéma endogène simple. / It has been observed that the runtime of randomized search heuristics depend on one or more parameters. A number of results show an advantage of dynamic parameter settings, that is, the parameters of the algorithm are changed during its execution. In this work, we prove that the unary unbiased black-box complexity of the OneMax benchmark function class is $n ln(n) - cn pm o(n)$ for a constant $c$ which is between $0.2539$ and $0.2665$. This runtime can be achieved with a simple (1+1)-type algorithm using a fitness-dependent mutation strength. When translated into the fixed-budget perspective, our algorithm finds solutions which are roughly 13% closer to the optimum than those of the best previously known algorithms.Based on the analyzed optimal mutation strength for OneMax, we show that a self-adjusting choice of the number of bits to be flipped attains the same runtime (apart from $o(n)$ lower-order terms) and the same (asymptotic) 13% fitness-distance improvement over RLS. The adjusting mechanism is to adaptively learn the currently optimal mutation strength from previous iterations. This aims both at exploiting that generally different problems may need different mutation strengths and that for a fixed problem different strengths may become optimal in different stages of the optimization process.We then extend our self-adjusting strategy to population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring. We analyze how the $(1+lambda)$ evolutionary algorithm with this self-adjusting mutation rate optimizes the OneMax test function. We prove that this dynamic version of the $(1+lambda)$~EA finds the optimum in an expected optimization time (number of fitness evaluations) of $O(nlambda/loglambda+nlog n)$. This time is asymptotically smaller than the optimization time of the classic $(1+lambda)$ EA. Previous work shows that this performance is best-possible among all $lambda$-parallel mutation-based unbiased black-box algorithms.We also propose and analyze a self-adaptive version of the $(1,lambda)$ evolutionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation. A rigorous runtime analysis on the OneMax benchmark function reveals that a simple local mutation scheme for the rate leads to an expected optimization time of the best possible $O(nlambda/loglambda+nlog n)$. Our result shows that self-adaptation in evolutionary computation can find complex optimal parameter settings on the fly. At the same time, it proves that a relatively complicated self-adjusting scheme for the mutation rate can be replaced by our simple endogenous scheme.

This thesis deals with the problem of vehicle scheduling in public transport. It contains a theoretical introduction to vehicles scheduling and evolutionary algorithms. Vehicle scheduling is analyzed with respect to the bus timetables. Analysis of evolutionary algorithms is done with emphasis on the genetic algorithms and tabu-search method After the theoretical introduction, a memetic algorithm for the given problem is analyzed. Finally, the thesis contains a description of the optimization system implementation and discusses the experiments with the system.

Achieving optimal performance of a database can be crucial for many businesses, and tuning its configuration parameters is a necessary step in this process. Many existing tuning methods involve complex machine learning algorithms and require large amounts of historical data from the system being tuned. However, training machine learning models can be problematic if a considerable amount of computational resources and data storage is required. This paper investigates the possibility of using less complex search algorithms or evolutionary algorithms to tune database configuration parameters, and presents a framework that employs Hill Climbing and Particle Swarm Optimization. The performance of the algorithms are tested on a PostgreSQL database using read-only workloads. Particle Swarm Optimization displayed the largest improvement in query response time, improving it by 26.09% compared to using the configuration parameters' default values. Given the improvement shown by Particle Swarm Optimization, evolutionary algorithms may be promising in the field of database tuning.

We demonstrate the success of recurrent neural networks in gene network inference and expression prediction using a hybrid of particle swarm optimization and differential evolution to overcome the classic obstacle of local minima in training recurrent neural networks. We also provide an improved validation framework for the evaluation of genetic network modeling systems that will result in better generalization and long-term prediction capability. Success in the modeling of gene regulation and prediction of gene expression will lead to more rapid discovery and development of therapeutic medicine, earlier diagnosis and treatment of adverse conditions, and vast advancements in life science research.

Evolutionary algorithms are machine learning techniques that can be used in many applications of optimization problems in various fields. Banking route planning is a combinatorial optimization problem. The paper proposes a genetic algorithm for planning routes for bank employees. Computational experiments have been carried out, and the effectiveness of the proposed method has been shown. / Эволюционные алгоритмы - это методы машинного обучения, которые можно использовать во многих приложениях задач оптимизации в различных областях. Планирование банковских маршрутов представляет собой задачу комбинаторной оптимизации. В работе предложен генетический алгоритм планирования маршрутов банковских работников. Проведены вычислительные эксперименты, показана эффективность предложенного метода.

No description available.

Scania has been working with statistics for a long time but has invested in becoming a data driven company more recently and uses data science in almost all business functions. The algorithms developed by the data scientists need to be optimized to be fully utilized and traditionally this is a manual and time consuming process. What this thesis investigates is if and how well evolutionary algorithms can be used to automate the optimization process. The evaluation was done by implementing and analyzing four variations of genetic algorithms with different levels of complexity and tuning parameters. The algorithm subject to optimization was XGBoost, a gradient boosted tree model, applied to data that had previously been modelled in a competition. The results show that evolutionary algorithms are applicable in finding good models but also emphasizes the importance of proper data preparation. / Scania har länge jobbat med statistik men har på senare år investerat i att bli ett mer datadrivet företag och använder nu data science i nästan alla avdelningar på företaget. De algoritmer som utvecklas av data scientists måste optimeras för att kunna utnyttjas till fullo och detta är traditionellt sett en manuell och tidskrävade process. Detta examensarbete utreder om och hur väl evolutionära algoritmer kan användas för att automatisera optimeringsprocessen. Utvärderingen gjordes genom att implementera och analysera fyra varianter avgenetiska algoritmer med olika grader av komplexitet och trimningsparameterar. Algoritmen som var målet för optimering var XGBoost, som är en gradient boosted trädbaserad modell. Denna applicerades på data som tidigare hade modellerats i entävling. Resultatet visar att evolutionära algoritmer är applicerbara i att hitta bra modellermen påvisar även hur fundamentalt det är att arbeta med databearbetning innan modellering.

This thesis concerns the development of optimisation algorithms to determine the relative co-location, (localisation), of a number of freely-flying 'Smart Dust mote' sensor platform elements using a non-deterministic data-set derived from the duplex wireless transmissions between elements. Smart dust motes are miniaturised, microprocessor based, electronic sensor platforms, frequently used for a wide range of remote environmental monitoring applications; including specific climate synoptic observation research and more general meteorology. For the application proposed in this thesis a cluster of the notional smart dust motes are configured to imitate discrete 'Radio Drop Sonde' elements of the wireless enabled monitoring system in use by meteorological research organisations worldwide. This cluster is modelled in software in order to establish the relative positions during the 'flight' ; the normal mode of deployment for the Drop Sonde is by ejection from an aeroplane into an upper-air zone of interest, such as a storm cloud. Therefore the underlying research question is, how to track a number of these independent, duplex wireless linked, free-flying monitoring devices in 3-dimensions and time (to give the monitored data complete spatio-temporal validity). This represents a significant practical challenge, the solution applied in this thesis was to generate 3-dimensional geometries using the only 'real-time' data available; the Radio Signal Strength Indicator (RSSI) data is generated through the 'normal' duplex wireless communications between motes. Individual RSSI values can be considered as a 'representation of the distance magnitude' between wireless devices; when collated into a spatio-temporal data-set it 'encodes' the relative, co-locational, 3-dimensional geometry of all devices in the cluster. The reconstruction, (or decoding), of the 3-dimensional geometries encoded in the spatio-temporal data-set is a complex problem that is addressed through the application of various algorithms. These include, Random Search, and optimisation algorithms, such as the Stochastic Hill-climber, and various forms of Evolutionary Algorithm. It was found that the performance of the geometric reconstruction could be improved through identification of salient aspects of the modelled environment, the result was heuristic operators. In general these led to a decrease in the time taken to reach a convergent solution or a reduction in the number of candidate search space solutions that must be considered. The software model written for this thesis has been implemented to generalise the fundamental characteristics of an optimisation algorithm and to incorporate them into a generic software framework; this then provides the common code to all model algorithms used.

The research work presented in this thesis describes the development and testing of a new data analysis methodology for the automated near real-time detection and approximate location of pipe bursts and other events which induce similar abnormal pressure/flow variations (e.g., unauthorised consumptions, equipment failures, etc.) in Water Distribution Systems (WDSs). This methodology makes synergistic use of several self-learning Artificial Intelligence (AI) and statistical/geostatistical techniques for the analysis of the stream of data (i.e., signals) collected and communicated on-line by the hydraulic sensors deployed in a WDS. These techniques include: (i) wavelets for the de-noising of the recorded pressure/flow signals, (ii) Artificial Neural Networks (ANNs) for the short-term forecasting of future pressure/flow signal values, (iii) Evolutionary Algorithms (EAs) for the selection of optimal ANN input structure and parameters sets, (iv) Statistical Process Control (SPC) techniques for the short and long term analysis of the burst/other event-induced pressure/flow variations, (v) Bayesian Inference Systems (BISs) for inferring the probability of a burst/other event occurrence and raising the detection alarms, and (vi) geostatistical techniques for determining the approximate location of a detected burst/other event. The results of applying the new methodology to the pressure/flow data from several District Metered Areas (DMAs) in the United Kingdom (UK) with real-life bursts/other events and simulated (i.e., engineered) burst events are also reported in this thesis. The results obtained illustrate that the developed methodology allowed detecting the aforementioned events in a fast and reliable manner and also successfully determining their approximate location within a DMA. The results obtained additionally show the potential of the methodology presented here to yield substantial improvements to the state-of-the-art in near real-time WDS incident management by enabling the water companies to save water, energy, money, achieve higher levels of operational efficiency and improve their customer service. The new data analysis methodology developed and tested as part of the research work presented in this thesis has been patented (International Application Number: PCT/GB2010/000961).