We look at robotic systems made of separate discrete components that, by self-assembling, can organize into physical structures of growing size. We review 22 such systems, exhibiting components ranging from passive mechanical parts to mobile robots. We present a taxonomy of the systems, and discuss their design and function. We then focus on a particular system, the swarm-bot. In swarm-bot, the components that assemble are self-propelled modules that are fully autonomous in power, perception, computation, and action. We examine the additional capabilities and functions self-assembly can offer an autonomous group of modules for the accomplishment of a concrete task: the transport of an object. The design of controllers is accomplished in simulation using techniques from biologically-inspired computing. We show that self-assembly can offer adaptive value to groups that compete in an artificial evolution based on their fitness in task performance. Moreover, we investigate mechanisms that facilitate the design of self-assembling systems. The controllers are transferred to the physical swarm-bot system, and the capabilities of self-assembly and object transport are extensively evaluated in a range of different environments. Additionally, the controller for self-assembly is transferred and evaluated on a different robotic system, a super-mechano colony. Given the breadth and quality of the results obtained, we can say that the swarm-bot qualifies as the current state of the art in self-assembling robots. Our work supplies some initial evidence (in form of simulations and experiments with the swarm-bot) that self-assembly can offer robotic systems additional capabilities and functions useful for the accomplishment of concrete tasks.

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

Este trabalho propõe o desenvolvimento de Algoritmos Evolutivos (AEs) para estimação dos parâmetros que modelam sinais elétricos (frequência, fase e amplitude) em tempo-real. A abordagem proposta deve ser robusta a ruídos e harmônicos em sinais distorcidos, por exemplo devido à presença de faltas na rede elétrica. AEs mostram vantagens para lidar com tais tipos de sinais. Por outro lado, esses algoritmos quando implementados em software não possibilitam respostas em tempo-real para uso da estimação como relé de frequência ou Unidade de Medição Fasorial. O desenvolvimento em FPGA apresentado nesse trabalho torna possível paralelizar o cálculo da estimação em hardware, viabilizando AEs para análise de sinal elétrico em tempo real. Além disso, mostra-se que AEs multiobjetivos podem extrair informações não evidentes das três fases do sistema e estimar os parâmetros adequadamente mesmo em casos em que as estimativas por fase divirjam entre si. Em outras palavras, as duas principais contribuições computacionais são: a paralelização do AE em hardware por meio de seu desenvolvimento em um circuito de FPGA otimizado a nível de operações lógicas básicas e a modelagem multiobjetiva do problema possibilitando análises dos sinais de cada fase, tanto independentemente quanto de forma agregada. Resultados experimentais mostram superioridade do método proposto em relação ao estimador baseado em transformada de Fourier para determinação de frequência e fase / This work proposes the development of Evolutionary Algorithms (EAs) for the estimation of the basic parameters from electrical signals (frequency, phase and amplitude) in real time. The proposed approach must be robust to noise and harmonics in signals distorted, for example, due to the presence of faults in the electrical network. EAs show advantages for dealing with these types of signals. On the other hand, these algorithms when implemented in software cant produce real-time responses in order to use their estimations as frequency relay or Phasor Measurement Unit. The approach developed on FPGA proposed in this work parallelizes in hardware the process of estimation, enabling analyses of electrical signals in real time. Furthermore, it is shown that multi-objective EAs can extract non-evident information from the three phases of the system and properly estimate parameters even when the phase estimates diverge from each other. This research proposes: the parallelization of an EA in hardware through its design on FPGA circuit optimized at level of basic logic operations and the modeling of the problem enabling multi-objective analyses of the signals from each phase in both independent and aggregate ways. Experimental results show the superiority of the proposed method compared to an estimator based on Fourier transform for determining frequency and phase

Diese Arbeit beschäftigt sich mit dem Thema Evolutionäre Algorithmen und deren Verwendung für Optimierungsaufgaben. Im ersten Teil der Arbeit werden die theoretischen Grundlagen ausführlich dargelegt, die zum Verständnis der Problemstellung und der vorgeschlagenen Lösungsmöglichkeiten notwendig sind. Dazu gehören die Einführung des Konzeptes von Fitneßlandschaften, deren Eigenschaften sowie die kurze Darstellung bekannter stochastischer Optimierungsverfahren wie z.B. Simulated Annealing. Im Anschluß daran wird auf neue Verfahren - insbesondere gemischte Strategien - eingegangen und diese vergleichend gegenüber den herkömmlichen Verfahren abgegrenzt. Die neu entwickelten Verfahren werden an Modellproblemen getestet, welche im zweiten Teil der Arbeit vorgestellt werden. Verwendet wurden sowohl einfache theoretische Modelle wie Frustrierte Periodische Sequenzen als auch praktisch relevante Probleme wie das der RNA Sekundärstrukturen. Die verschiedenen Modellprobleme werden bezüglich ihrer Eigenschaften und Schwierigkeitsgrade untersucht und miteinander verglichen, um die Effizienz der verwendeten Optimierungsverfahren abschätzen zu können. Der dritte Teil der Arbeit präsentiert wichtige Ergebnisse der im Rahmen dieser Arbeit durchgeführten umfangreichen numerischen Simulationen. Es wird demonstriert, wie sensitiv die Optimierungsergebnisse von den verwendeten Parametern der Algorithmen (wie z.B. Ensemblegröße, Temperatur oder Mutationsrate) abhängen und das ein relativ scharf umrissenes evolutionäres Fenster der Parameter existiert, innerhalb dessen die Optimierungsresultate deutlich besser sind. Eine im Rahmen dieser Arbeit entwickelte adaptive Parametersteuerung wird an den im zweiten Teil vorgestellten Modellproblemen getestet und gezeigt, daß es möglich ist, den Optimierungsprozeß automatisch innerhalb des evolutionären Fensters zu halten. Der letzte Teil gibt Einblick in die im Rahmen dieser Arbeit verwendete Computer-Software und das vom Autor entwickelte Programmpaket. Es wird hervorgehoben, daß die in C++ objektorientiert und modular geschriebene Software leicht an andere Optimierungsaufgaben angepaßt werden kann und dank graphischer Benutzeroberfläche auch einfach zu bedienen ist. / This work explores Evolutionary Algorithms and their application to optimization tasks. The work's first part gives detailed theoretical background information necessary to understand the problem and proposed solutions. This theoretical part includes the introduction of fitness landscapes, the investigation of their properties, and it briefly reiterates well known stochastic optimization strategies like Simulated Annealing. Finally, new strategies, in particular mixed stategies, are introduced and compared to traditional optimization techniques. In the second part of this work, the newly developed strategies are benchmarked using model problems such as 'Frustrated Periodic Sequences', or the analysis of RNA secondary structures. To evaluate the efficiency of different optimization strategies, the introduced model problems are compared with respect to their difficulty level. The third part of this work presents results of extensive numerical simulations demonstrating how sensitive the investigated algorithms depend on their respective control parameters (ensemble size, temperature, mutation rate). It is shown that there is always a distinct parameter window, the so-called evolutionary window, that clearly leads to improved optimization results. Going back to the model problems introduced in part two, a newly developed adaptive parameter control is presented that automatically keeps the optimization algorithm's parameters within the evolutionary window. In the final part of this work not only the software used, but also the software newly developed by this work's author is illuminated. It is emphasized that the new software was designed highly flexible to allow for easy adaptation to different optimization problems. A graphical user interface is provided for convenience.

Com o surgimento da tecnologia da informação, o processo de análise e interpretação de dados deixou de ser executado exclusivamente por seres humanos, passando a contar com auxílio computacional para a descoberta de conhecimento em grandes bancos de dados. Este auxílio exige uma organização e ordenação das atividades, antes manualmente exercidas, em um processo composto de três grandes etapas. A primeira etapa deste processo conta com uma tarefa de redução da dimensionalidade, que tem como objetivo a eliminação de atributos que não contribuem para a análise dos dados, resultando portanto, na seleção de um subconjunto dos atributos originais. A seleção de um subconjunto de atributos pode ser encarada como um problema de busca, já que há inúmeras possibilidades de combinação dos atributos originais em subconjuntos. Dessa forma, uma das estratégias de busca que pode ser adotada consiste na busca randômica, executada por um algoritmo genético ou pelas suas variações. Este trabalho propõe a aplicação de duas variações do algoritmo genético, Algoritmo Genético Construtivo e Algoritmo Genético Enviesado com Chave Aleatória, no problema de seleção de atributos em agrupamento de dados, já que estas duas variações ainda não foram aplicadas em tal problema. A fim de verificar o desempenho destas duas variações, comparou-se ambas com a abordagem tradicional do algoritmo genético. Efetuou-se também a comparação entre as duas variações. Para isto, foi utilizada três bases de dados retiradas do repositório UCI de aprendizado de máquinas. Os resultados obtidos mostraram que os desempenhos, em termos de qualidade da solução, dos algoritmos: genético construtivo e genético enviesado com chave aleatório foram melhores, de maneira geral, do que o desempenho da abordagem tradicional. Constatou-se também diferença significativa em termos de eficiência entre as duas variações e a abordagem tradicional. / With the advent of information technology, the process of analysis and interpretation of data left to be run exclusively by humans, going to rely on computational support for knowledge discovery in large databases. This aid requires an organization and sequencing of activities before manually performed in a compound of three major step process. The first step of this process has a reduced dimensionality task, which aims to eliminate attributes that do not contribute to the data analysis, resulting therefore, in selecting a subset of the original attributes. Selecting a subset of attributes can be viewed as a search problem, since there are numerous possible combinations of unique attributes into subsets. Thus, one search strategies that can be adopted is to randomly search, performed by a genetic algorithm or its variants. This paper proposes the application of two variations of the genetic algorithm, Constructive Genetic Algorithm and Biased Random Key Genetic Algorithm in the feature selection problem in data grouping, as these two variations have not been applied in such a problem. In order to verify the performance of the two variations, we compare them with the traditional algorithm, genetic algorithm. It was also executed the comparison between the two variations. For this, we used three databases removed from the UCI repository of machine learning. The results showed that the performance, in term of quality solution, of algorithms: genetic constructive and genetic biased with random key are better than the performance of the traditional approach. It was also observed a significant difference in efficiency between of the two variations and the traditional approach.

Com o surgimento da tecnologia da informação, o processo de análise e interpretação de dados deixou de ser executado exclusivamente por seres humanos, passando a contar com auxílio computacional para a descoberta de conhecimento em grandes bancos de dados. Este auxílio exige uma organização e ordenação das atividades, antes manualmente exercidas, em um processo composto de três grandes etapas. A primeira etapa deste processo conta com uma tarefa de redução da dimensionalidade, que tem como objetivo a eliminação de atributos que não contribuem para a análise dos dados, resultando portanto, na seleção de um subconjunto dos atributos originais. A seleção de um subconjunto de atributos pode ser encarada como um problema de busca, já que há inúmeras possibilidades de combinação dos atributos originais em subconjuntos. Dessa forma, uma das estratégias de busca que pode ser adotada consiste na busca randômica, executada por um algoritmo genético ou pelas suas variações. Este trabalho propõe a aplicação de duas variações do algoritmo genético, Algoritmo Genético Construtivo e Algoritmo Genético Enviesado com Chave Aleatória, no problema de seleção de atributos em agrupamento de dados, já que estas duas variações ainda não foram aplicadas em tal problema. A fim de verificar o desempenho destas duas variações, comparou-se ambas com a abordagem tradicional do algoritmo genético. Efetuou-se também a comparação entre as duas variações. Para isto, foi utilizada três bases de dados retiradas do repositório UCI de aprendizado de máquinas. Os resultados obtidos mostraram que os desempenhos, em termos de qualidade da solução, dos algoritmos: genético construtivo e genético enviesado com chave aleatório foram melhores, de maneira geral, do que o desempenho da abordagem tradicional. Constatou-se também diferença significativa em termos de eficiência entre as duas variações e a abordagem tradicional. / With the advent of information technology, the process of analysis and interpretation of data left to be run exclusively by humans, going to rely on computational support for knowledge discovery in large databases. This aid requires an organization and sequencing of activities before manually performed in a compound of three major step process. The first step of this process has a reduced dimensionality task, which aims to eliminate attributes that do not contribute to the data analysis, resulting therefore, in selecting a subset of the original attributes. Selecting a subset of attributes can be viewed as a search problem, since there are numerous possible combinations of unique attributes into subsets. Thus, one search strategies that can be adopted is to randomly search, performed by a genetic algorithm or its variants. This paper proposes the application of two variations of the genetic algorithm, Constructive Genetic Algorithm and Biased Random Key Genetic Algorithm in the feature selection problem in data grouping, as these two variations have not been applied in such a problem. In order to verify the performance of the two variations, we compare them with the traditional algorithm, genetic algorithm. It was also executed the comparison between the two variations. For this, we used three databases removed from the UCI repository of machine learning. The results showed that the performance, in term of quality solution, of algorithms: genetic constructive and genetic biased with random key are better than the performance of the traditional approach. It was also observed a significant difference in efficiency between of the two variations and the traditional approach.

Evolutionära algoritmer har visat sig vara effektiva för att utveckla spelnivåer. Dock finns fortfarande ett behov av nivåer som både uppfyller de krav som spelen har, samt att nivåerna som skapas ska vara så olika som möjligt för att uppmuntra upprepade spelomgångar. För att åstadkomma detta kan man använda Novelty Search. Dock saknar Novelty Search funktioner som gör att populationen vill uppfylla de krav som nivåerna ska ha. Arbetet fokuserar därför på att jämföra två Novelty Search baserade algoritmer som båda uppmuntrar kravuppfyllning: Feasible Infeasible Novelty Search (FINS) och Pareto based Multi-objective evolutionary algorithm (PMOEA) med två mål: krav och Novelty Search. Studien jämför algoritmerna utifrån tre värden: hur stor andel av populationen som följer de ställda kraven, hur bra dessa individer är på att lösa ett nivårelaterat problem samt diversiteten bland dessa individer. Utöver PMOEA och FINS implementeras även en Novelty Search algoritm och en traditionell evolutionär algoritm. Tre experiment genomförs där nivåernas storlek och antalet krav varierade. Resultatet visar att PMOEA var bättre på att skapa fler individer som följde alla kraven och att dessa individer överlag var bättre på att optimera lösningar än vanlig Novelty Search och FINS. Dock hade FINS högre diversitet bland individerna än alla algoritmerna som testades. Studiens svaghet är att resultatet är subjektivt till algoritmernas uppsättning i artefakten, som sådan borde framtida arbeten fokusera på att utforska nya uppsättningar för att generalisera resultatet.

This study aimed to determine whether rainfall regime has driven differentiation in the Australian perennial grass, Austrodanthonia caespitosa, resulting in local ecotypes possessing characters, such as deep rootedness or summer activity, that may be particularly useful in reducing deep drainage for salinity mitigation, or whether the species shows a plastic response in root growth to soil water distribution. Rainfall regime varies within a given annual rainfall because size and ditribution of rainfall event vary. This can have an important effect on soil water distribution, both spatially and temporally. This study investigates the relationship between rainfall regime and the structure of root systems in local populations of Austrodanthonia caespitosa (Gaudich.), Firstly, it examined a number of indices useful in quantifying variation in small-scale rainfall regime, including seasonal bias, event size, event frequency, and the clustering of events, as well as how rainfall event size may be changing over time across Australia. The variation in soil water distribution that results from different rainfall regimes is expected to interact with root distribution in plants, either acting as a selective force and driving genotypic differentiation in response to soil water availability, or through plasticity in root placement. The relationship between rainfall regime and root depth distribution was examined in Austrodanthonia caespitosa (Gaudich.), or white-top wallaby grass, a perennial grass common across southern Australia. Growth and reproductive traits of plants grown from seeds collected from across the range of this species under a single rainfall regime were compared and correlated with the rainfall indices and soil type in order to establish possible abiotic explanations for trait variability. Phenological characters were found to be particularly variable between ecotypes, but high local variation between ecotypes suggested factors operating on a spatial scale smaller than the rainfall gradients are responsible for population differentiation. In order to investigate the interaction between rainfall event size and root depth, an experiment was conducted to investigate plant response to watering pulse size and frequency, with plants grown under a range of controlled watering regimes, and root depth distribution compared. The primary response in root growth was plastic, with shallow roots being developed under small, frequent events, and deep roots developed under large, infrequent waterings. Differences between ecotypes were less important, and there was no interaction between ecotype and watering treatment, indicating the same degree of plasticity in all ecotypes. Plants from a range of populations were grown under a controlled climate, first under winter conditions, then under summer conditions, with summer water withheld from half the plants, in order to determine the response to summer watering and summer drought. Plants that were watered over summer showed a strong growth response, increasing shoot biomass significantly. This effect was particularly strong in South Australian populations, which was unexpected as they originate from a region with low, unpredictable summer rainfall. Root depth was not strongly influenced by summer watering treatment. Finally, an evolutionary algorithm model was constructed in order to examine optimal plant traits under a variety of rainfall regimes. The model highlighted the importance of the interaction between rainfall regime and soil type in determining optimal root placement. Variable root cost with depth was also found to be an important trade-off to be considered, with high root loss in the surface soil layers, due to high temperatures, making a shallow rooted strategy less efficient than if root costs were equal throughout the root system. Overall, no ecotypes of A.caespitosa could be identified that had characters particularly suited to deep drainage reduction, as the drought tolerant nature of the species, and the dormancy during times of drought, may lead to low overall water use. However, it may be a useful native component in pasture systems, due to its strong growth response to summer rainfall, a characteristic found to be particularly strong in a number of South Australian ecotypes. / Thesis (Ph.D.) -- University of Adelaide, School of Earth and Environmental Sciences, 2008

This manuscrit is a compact presentation of my research done between 1993 and 2008 and which concerns the global optimization of mechanical systems. General and specialized global optimization algorithms are presented. With respect to previously published work, an updated presentation of my work on composite optimization is given.

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