Tesi sul tema "Evolution Grammaticale"

Grammatical Evolution (GE) is a method of utilising a general purpose evolutionary algorithm to ???evolve??? programs written in an arbitrary BNF grammar. This thesis extends GE as follows: GE as an extension of Genetic Programming (GP) A novel method of automatically extracting information from the grammar is introduced. This additional information allows the use of GP style crossover which in turn allows GE to perform identically to a strongly typed GP system as well as a non-typed (or canonical) GP system. Two test problems are presented one which is more easily solved by the GP style crossover and one which favours the tradition GE ???Ripple Crossover???. With this new crossover operator GE can now emulate GP (as well as retaining its own unique features) and can therefore now be seen as an extension of GP. Dynamically Defined Functions An extension to the BNF grammar is presented which allows the use of dynamically defined functions (DDFs). DDFs provide an alternative to the traditional approach of Automatically Defined Functions (ADFs) but have the advantage that the number of functions and their parameters do not need to be specified by the user in advance. In addition DDFs allow the architecture of individuals to change dynamically throughout the course of the run without requiring the introduction of any new form of operator. Experimental results are presented confirming the effectiveness of DDFs. Self-Selecting (or variable) crossover. A self-selecting operator is introduced which allows the system to determine, during the course of the run, which crossover operator to apply; this is tested over several problem domains and (especially where small populations are used) is shown to be effective in aiding the system to overcome local optima. Spatial Co-Evolution in Age Layered Planes (SCALP) A method of combining Hornby???s ALPS metaheuristic and a spatial co-evolution system used by Mitchell is presented; the new SCALP system is tested over three problem domains of increasing difficulty and performs extremely well in each of them.

Evolutionary algorithms are a competent nature-inspired approach for complex computational problem solving. One recent development is Grammatical Evolution, a grammar-based evolutionary algorithm which uses genotypes of variable length binary strings and a unique genotype-to-phenotype mapping process based on a BNF grammar definition describing the output language that is able to create valid individuals of an arbitrary structure or programming language. This study surveys Grammatical Evolution, identifies its most important issues, investigates the competence of the algorithm in a series of agent-oriented benchmark problems, provides experimental results which cast doubt about its effectiveness and efficiency on problems involving the evolution of the behaviour of an agent, and presents Constituent Grammatical Evolution (CGE), a new innovative evolutionary automatic programming algorithm. CGE extends Grammatical Evolution by incorporating the concepts of constituent genes and conditional behaviour-switching. It builds from elementary and more complex building blocks a control program which dictates the behaviour of an agent and it is applicable to the class of problems where the subject of search is the behaviour of an agent in a given environment. Experimental results show that the new algorithm significantly improves Grammatical Evolution in all problems it has been benchmarked. Additionally, the investigation undertaken in this work required the development of a series of tools which are presented and described in detail. These tools provide an extendable open source and publicly available framework for experimentation in the area of evolutionary algorithms and their application in agent-oriented environments and complex systems.

This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (page 27).
Grammatical Evolution (GE) is an evolutionary algorithm that is gaining popularity due to its ability to solve problems where it would be impossible to explore every solution within a realistic time. Structured Grammatical Evolution (SGE) was developed to overcome some of the shortcomings of GE, such as locality issues as well as wrapping around the genotype to complete the phenotype. In this paper, we apply SGE to program synthesis, where the computer must generate code to solve algorithmic problems. SGE was improved upon, because the current definition of SGE does not work. Given that the solution space is very large for possible codes, we aim to improve the efficiency of GE in converging to the correct solution. We present a method in which to remove cycles from a grammar for SGE, to be able to make sure that a genotype matches to a phenotype with reusing parts of the genotype, and analyze results to shed insight on future improvements.
by Andrew H. Zhang.
M. Eng.
M.Eng. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science

Dans le contexte de la transition énergétique et de l'augmentation des interconnexions entre les réseaux de transport d'électricité en Europe, les opérateurs du réseau français doivent désormais faire face à davantage de fluctuations et des dynamiques nouvelles sur le réseau. Pour garantir la sûreté de ce réseau, les opérateurs s'appuient sur des logiciels informatiques permettant de réaliser des simulations, ou de suivre l'évolution d'indicateurs créés manuellement par des experts grâce à leur connaissance du fonctionnement du réseau. Le gestionnaire de réseau de transport d'électricité français RTE (Réseau de Transport d'Electricité) s'intéresse notamment aux développements d'outils permettant d'assister les opérateurs dans leur tâche de surveillance des transits sur les lignes électriques. Les transits sont en effet des grandeurs particulièrement importantes pour maintenir le réseau dans un état de sécurité, garantissant la sûreté du matériel et des personnes. Cependant, les indicateurs utilisés ne sont pas faciles à mettre à jour du fait de l'expertise nécessaire pour les construire et les analyser. Pour répondre à la problématique énoncée, cette thèse a pour objet la construction d'indicateurs, sous la forme d'expressions symboliques, permettant d'estimer les transits sur les lignes électriques. Le problème est étudié sous l'angle de la Régression Symbolique et investigué à la fois par des approches génétiques d'Evolution Grammaticale et d'Apprentissage par Renforcement dans lesquelles la connaissance experte, explicite et implicite, est prise en compte. Les connaissances explicites sur la physique et l'expertise du domaine électrique sont représentées sous la forme d'une grammaire non-contextuelle délimitant l'espace fonctionnel à partir duquel l'expression est créée. Une première approche d'Evolution Grammaticale Interactive propose d’améliorer incrémentalement les expressions trouvées par la mise à jour d'une grammaire entre les apprentissages évolutionnaires. Les expressions obtenues sur des données réelles issues de l'historique du réseau sont validées par une évaluation de métriques d'apprentissages, complétée par une évaluation de leur interprétabilité. Dans un second temps, nous proposons une approche par renforcement pour chercher dans un espace délimité par une grammaire non-contextuelle afin de construire une expression symbolique pertinente pour des applications comportant des contraintes physiques. Cette méthode est validée sur des données de l'état de l'art de la régression symbolique, ainsi qu’un jeu de données comportant des contraintes physiques pour en évaluer l'interprétabilité. De plus, afin de tirer parti des complémentarités entre les capacités des algorithmes d'apprentissage automatique et de l'expertise des opérateurs du réseau, des algorithmes interactifs de Régression Symbolique sont proposés et intégrés dans des plateformes interactives. L'interactivité est employée à la fois pour mettre à jour la connaissance représentée sous forme grammaticale, analyser, interagir avec et commenter les solutions proposées par les différentes approches. Ces algorithmes et interfaces interactifs ont également pour but de prendre en compte de la connaissance implicite, plus difficile à formaliser, grâce à l'utilisation de mécanismes d'interactions basés sur des suggestions et des préférences de l’utilisateur
In the energy transition context and the increase in interconnections between the electricity transmission networks in Europe, the French network operators must now deal with more fluctuations and new network dynamics. To guarantee the safety of the network, operators rely on computer software that allows them to carry out simulations or to monitor the evolution of indicators created manually by experts, thanks to their knowledge of the operation of the network. The French electricity transmission network operator RTE (Réseau de Transport d'Electricité) is particularly interested in developing tools to assist operators in monitoring flows on power lines. Flows are notably important to maintain the network in a safe state, guaranteeing the safety of equipment and people. However, the indicators used are not easy to update because of the expertise required to construct and analyze them.In order to address the stated problem, this thesis aims at constructing indicators, in the form of symbolic expressions, to estimate flows on power lines. The problem is studied from the Symbolic Regression perspective and investigated using both Grammatical Evolution and Reinforcement Learning approaches in which explicit and implicit expert knowledge is taken into account. Explicit knowledge about the physics and expertise of the electrical domain is represented in the form of a Context-Free Grammar to limit the functional space from which an expression is created. A first approach of Interactive Grammatical Evolution proposes to incrementally improve found expressions by updating a grammar between evolutionary learnings. Expressions are obtained on real-world data from the network history, validated by an analysis of learning metrics and an interpretability evaluation. Secondly, we propose a reinforcement approach to search in a space delimited by a Context-Free Grammar in order to build a relevant symbolic expression to applications involving physical constraints. This method is validated on state-of-the-art Symbolic Regression benchmarks and also on a dataset with physical constraints to assess its interpretability.Furthermore, in order to take advantage of the complementarities between the capacities of machine learning algorithms and the expertise of network operators, interactive Symbolic Regression algorithms are proposed and integrated into interactive platforms. Interactivity allows updating the knowledge represented in grammatical form and analyzing, interacting with, and commenting on the solutions found by the different approaches. These algorithms and interactive interfaces also aim to take into account implicit knowledge, which is more difficult to formalize, through interaction mechanisms based on suggestions and user preferences

A major goal of human genetics is the discovery and validation of genetic polymorphisms that predict common, complex diseases. It is hypothesized that complex diseases are due to a myriad of factors including environmental exposures and complex genetic models. This etiological complexity, coupled with rapid advances in genotyping technology present enormous theoretical and practical concerns for statistical and computational analysis. Specifically, the challenge presented by epistasis, or gene-gene interactions, has sparked the development of a multitude of statistical techniques over the years. Subsequently, pattern matching and machine learning approaches have been explored to overcome the limitations of traditional computational methods. Grammatical Evolution Neural Networks (GENN) uses grammatical evolution to optimize neural network architectures and better detect and analyze gene-gene interactions. Motivated by good results shown by GENN to identify epistasis in complex datasets, we have developed a new method of Grammatical Evolution Decision Trees (GEDT). GEDT replaces the black-box approach of neural networks with the white-box approach of decision trees improving understandability and interpretability. We provide a detailed technical understanding of coupling Grammatical Evolution with Decision Tress using Backus Naur Form (BNF) grammar. Further, the GEDT system has been analyzed for power results on simulated datasets. Finally, we show the results of using GEDT on two different epistatis models and discuss the direction it would take in the future.

Animals such as bees, ants, birds, fish, and others are able to efficiently perform complex coordinated tasks like foraging, nest-selection, flocking and escaping predators without centralized control or coordination. These complex collective behaviors are the result of emergence. Conventionally, mimicking these collective behaviors with robots requires researchers to study actual behaviors, derive mathematical models, and implement these models as algorithms. Since the conventional approach is very time consuming and cumbersome, this thesis uses an emergence-based method for the efficient evolution of collective behaviors. Our method, Grammatical Evolution algorithm for Evolution of Swarm bEhaviors (GEESE), is based on Grammatical Evolution (GE) and extends the literature on using genetic methods to generate collective behaviors for robot swarms. GEESE uses GE to evolve a primitive set of human-provided rules, represented in a BNF grammar, into productive individual behaviors represented by Behavior Tree (BT). We show that GEESE is generic enough, given an initial grammar, that it can be applied to evolve collective behaviors for multiple problems with just a minor change in objective function. Our method is validated as follows: First, GEESE is compared with state-of-the-art genetic algorithms on the canonical Santa Fe Trail problem. Results show that GEESE outperforms the state-of-the-art by a)~providing better solutions given sufficient population size while b)~utilizing fewer evolutionary steps. Second, GEESE is used to evolve collective swarm behavior for a foraging task. Results show that the evolved foraging behavior using GEESE outperformed both hand-coded solutions as well as solutions generated by conventional Grammatical Evolution. Third, the behaviors evolved for single-source foraging task were able to perform well in a multiple-source foraging task, indicating a type of robustness. Finally, with a minor change to the objective function, the same BNF grammar used for foraging can be shown to evolve solutions to the nest-maintenance and the cooperative transport tasks.

Fighter pilots often find themselves in situations where they need to make quick decisions. Therefore an intelligent decision support system that suggests how the fighter pilot should act in a specific situation is vital. The aim of this project is to investigate and evaluate grammatical evolution paired with behaviour trees to develop a decision support system. This support system should control a simulated fighter pilot during an airborne reconnaissance mission. This thesis evaluates the complexity of the evolved trees and the performance, and robustness of the algorithm. Key factors were identified for a successful system: scenario, fitness function, initialisation technique and control parameters. The used techniques were decided based on increasing performance of the algorithm and decreasing complexity of the tree structures. The initialisation technique, the genetic operators and the selection functions performed well but the fitness function needed more work. Most of the experiments resulted in local maxima. A desired solution could only be found if the initial population contained an individual with a BT succeeding the mission. However, the implementation behaved as expected. More and longer simulations are needed to draw a conclusion of the performance based on robustness, when testing the evolved BT:s on different scenarios. Several methods were studied to decrease the complexity of the trees and the experiments showed a promising variation of complexity through the generations when the best fitness was fixed. A feature was added to the algorithm, to promote lower complexity when equal fitness value. The results were poor and implied that pruning would be a better fit after the simulations. Nevertheless, this thesis suggests that it is suitable to implement a decision support system based on grammatical evolution paired with behaviour trees as framework.

The application of machine learning techniques to predict time-series continues to attract considerable attention due to the difficulty of the prediction problems compounded by the non-linear and non-stationary nature of the real world time-series. The performance of machine learning techniques, among other things, depends on suitable engineering of features. This thesis proposes a systematic way for generating suitable features using context-free grammar. The notion of grammar families as a compact representation to generate a broad class of features is exploited. Implementation issues and ways to overcome them are explained in detail. A number of feature selection criteria are investigated and a hybrid feature generation and selection algorithm using grammatical evolution is proposed. The proposed approaches are demonstrated by predicting the closing price of major stock market indices, peak electricity load and net hourly foreign exchange client trade volume. The widely and commonly employed features in practice (in previous work) for electricity and financial time-series are explored. These features are considered as a basis for comparison with the features generated and selected by the proposed framework. Other model-based approaches and naive approaches are also used as benchmarks. It is shown that the generated features can improve results, while requiring no domain-specific knowledge. The proposed method is used to determine suitable features to use in predicting previously unexplored foreign exchange client trade volume and the capabilities of the approach in automatically engineering appropriate features is highlighted. The proposed method can be applied to a wide range of machine learning architectures and applications to represent complex feature dependencies explicitly when machine learning cannot achieve this by itself.

Software testing is an expensive process, which is vital in the industry. Construction of the test-data in software testing requires the major cost and knowing which method to use in order to generate the test data is very important. This paper discusses the performance of search-based algorithms (preferably genetic algorithm) versus random testing, in software test-data generation. A factorial experiment is designed so that, we have more than one factor for each experiment we make. Although many researches have been done in the area of automated software testing, this research differs from all of them due to sample programs (SUTs) which are used. Since the program generation is automatic as well, Grammatical Evolution is used to guide the program generations. They are not goal based, but generated according to the grammar we provide, with different levels of complexity. Genetic algorithm is first applied to programs, then we apply random testing. Based on the results which come up, this paper recommends one method to use for software testing, if the SUT has the same conditions as we had in this study. SUTs are not like the sample programs, provided by other studies since they are generated using a grammar.

Forward planning and risk management are crucial for the success of any system or business dealing with the uncertainties of the real world. Previous approaches have largely assumed that the future will be similar to the past, or used simple forecasting techniques based on ad-hoc models. Improving solutions requires better projection of future events, and necessitates robust forward planning techniques that consider forecasting inaccuracies. This work advocates risk management through optimal control theory, and proposes several techniques to combine it with time-series forecasting. Focusing on applications in foreign exchange (FX) and battery energy storage systems (BESS), the contributions of this thesis are three-fold. First, a short-term risk management system for FX dealers is formulated as a stochastic model predictive control (SMPC) problem in which the optimal risk-cost profiles are obtained through dynamic control of the dealers’ positions on the spot market. Second, grammatical evolution (GE) is used to automate non-linear time-series model selection, validation, and forecasting. Third, a novel measure for evaluating forecasting models, as a part of the predictive model in finite horizon optimal control applications, is proposed. Using both synthetic and historical data, the proposed techniques were validated and benchmarked. It was shown that the stochastic FX risk management system exhibits better risk management on a risk-cost Pareto frontier compared to rule-based hedging strategies, with up to 44.7% lower cost for the same level of risk. Similarly, for a real-world BESS application, it was demonstrated that the GE optimised forecasting models outperformed other prediction models by at least 9%, improving the overall peak shaving capacity of the system to 57.6%.

The dissertation thesis deals with Evolution optimization of control algorithms. The first part of the thesis describes the principles and partial methods of evolution optimization methods especially those used in two-level transplant evolution method. Later the grammatical evolution method is described, which modified algorithm became impulse for creation of transplant evolution method. The transplant evolution method and its two-level modification are new evolutionary algorithms proposed in this work, which were used for optimization of structure and parameters of general controllers control algorithms. The transplant evolution algorithm and its extended two-level modification are described in detail in next chapters. The proper settings of evolutionary algorithms are important for minimization the time of optimization and for finds results approaching the global optimum. For proper setting the parameters of differential evolution was created meta-evolution algorithm that is described in chapter named meta-evolution. The basic concepts of control, chosen methods of system identification and controller parameters settings are described in next part. This part describes algorithms of digital controllers and some specific methods uses in digital control. The demonstrations of control algorithm optimizations of various types of controllers are showed in experimental part. The optimized algorithms of general controllers are compared with various types of PSD controllers which were set by various algebraic methods or differential evolution for various models of systems. In the conclusion of this work is stated a recommendation for further development of evolutionary optimization of controllers are focusing on parallel and distributed computing.

The object of my thesis is the realization of grammatical evolution in the Java programming language for solving problems of approximation of functions and synthesis of logical circuits. The application is practical used for testing and gathering data in context of using different purpose function and parallel grammatical evolution. The data are analyzed and evaluated.

This thesis focuses on the automation of scenarios creation for Portable Stimulus standard. The main goal of the work is an automatic generation of tests, which are defined as graphs for the Questa inFact tool from the Mentor company. For the automation I used an evolutionary algorithm with using a grammatical evolution.  The generated scenarios are connected to the existing verification environment based on UVM methodology, then the verification of the connected component is started. Based on the achieved functional and structural coverage, the individual's fitness value is calculated and propagated into an evolutionary algorithm.  At the end of the work, experiments are performed on the timer component and the contribution of the proposed evolutionary algorithm is evaluated. The proposed evolutionary algorithm is configurable by  grammar and user-defined basic transactions, which allows a wide range of uses. The evolutionary algorithm managed to achieve high functional and structural coverage on the verified timer component.

p, li { white-space: pre-wrap; } Evoluce v přírodě slouží jako zdroj inspirace pro tuto práci . Základní myšlenkou je využití generativní síly gramatik v kombinaci s evolučním přístupem . Nabyté znalosti jsou aplikovány na hledání strategií chování v rozmanitých prostředích . Stromy chování jsou modelem , který bývá běžně použit na řízení rozhodování různých umělých inteligencí . Tato práce se zabývá hledáním stromů chování , které budou řídit jedince řešící nasledující dva problémy : upravenou verzi problému cesty koněm šachovnicí a hraní hry Pirátské kostky . Při hledání strategie hráče kostek , byla použita konkurenční koevoluce . Důvodem je obtížnost návrhu spravedlivé fitness funkce hodnotící výkony hráčů .

Dissertação de Mestrado em Engenharia Informática apresentada à Faculdade de Ciências e Tecnologia
Evolução Gramatical (GE) [1] é uma das variantes mais populares de Programação Genética(GP) [2] e tem sido utilizada com sucesso em problemas de vários domínios. Desde a pro-posta original, muitas melhorias foram introduzidas na GE para melhorar a sua perfor-mance abordando alguns dos seus principais problemas, nomeadamente a baixa localidadee a alta redundância [3, 4].Nos métodos de GP baseados em gramáticas a escolha da gramática tem um papel impor-tante na qualidade das soluções geradas, uma vez que é a gramática que define o espaçode procura [5]. Neste trabalho, propomos quatro variantes da GE, que durante o processoevolucionário realizam uma exploração do espaço de procura, alterando os pesos de cada re-gra da gramática. Estas variantes introduzem dois tipos de representação alternativas, doismétodos diferentes de ajustar a gramática e um novo método de mapeamento, utilizandouma Gramática Livre de Contexto Probabilistica (PCFG).O primeiro método é a Evolução Gramatical Probabilistica (PGE), no qual os individuossão representados por uma lista de probabilidades (genótipo), onde cada valor representa aprobabilidade de selecionar uma regra de derivação. O genótipo é mapeado numa soluçãopara o problema em questão (fenótipo), recorrendo a uma PCFG. A cada geração, as prob-abilidades de cada regra da gramática são atualizadas, com base nas regras de expansãousadas pelo melhor individuo. A Evolução Gramatical Probabilistica Co-Evolucionária(Co-PGE) utiliza a mesma representação dos individuos e introduz uma nova técnicade atualização das probabilidades da gramática onde as probabilidades de cada regra dederivação são alteradas a cada geração usando um operador semelhante à mutação. Emambos os métodos os individuos são remapeados após atualização da gramática.A Evolução Gramatical Estruturada Probabilistica (PSGE) e a Evolução Gramatical Estru-turada Probabilistica Co-Evolucionária (Co-PSGE) foram criadas adaptando a EvoluçãoGramatical Estruturada (SGE), um método que foi proposto para superar os problemas daGE melhorando a sua performance [6]. Estas variantes usam como genótipo um conjuntode listas dinâmicas, uma para cada não-terminal, em que cada elemento da lista é umaprobabilidade usada para mapear o individuo, usando uma PCFG.Analisamos e comparamos o desempenho dos métodos em seis problemas benchmark.Quando comparados com a GE, os resultados mostraram que a PGE e a Co-PGE sãoestatisticamente semelhantes ou melhores em todos os problemas, enquanto que a PSGE ea Co-PSGE foram estatisticamente melhores em todos os problemas do que a tradicionalGE. Destacamos também a Co-PSGE por superar estatisticamente a SGE em alguns prob-lemas, tornando-a competitiva com o estado da arte. Também realizamos uma análise nasrepresentações, e os resultados mostraram que a PSGE e a Co-PSGE tem menos redun-dancia, e todos os métodos apresentaram localidade mais elevada que o GE, o que permiteuma melhor exploração do espaço de procura.As análises efetuadas mostraram que as gramáticas evoluidas ajudam a guiar o processoevolucionario, e fornecem-nos informações sobre as regras de produção mais relevantespara gerar melhores soluções. Além disso, também podem ser utilizadas para gerar umaamostragem de soluções com melhor fitness médio.
Grammatical Evolution (GE) [1] is one of the most popular variants of Genetic Program-ming (GP) [2] and has been successfully used in a wide range of problem domains. Sincethe original proposal, many improvements have been introduced in GE to improve its per-formance by addressing some of its main issues, namely low locality and high redundancy[3, 4].In grammar-based GP methods the choice of the grammar has a significant impact onthe quality of the generated solutions, since it is the grammar that defines the searchspace [5]. In this work, we present four variants of GE, which during the evolutionaryprocess perform an exploration of the search space by updating the weights of each ruleof the grammar. These variants introduce two alternative representation types, two gram-mar adjustment methods, and a new mapping method using a Probabilistic Context-FreeGrammar (PCFG).The first method is Probabilistic Grammatical Evolution (PGE), in which individuals arerepresented by a list of real values (genotype), each value denoting the probability of select-ing a derivation rule. The genotype is mapped into a solution (phenotype) to the problemat hand, using a PCFG. At each generation, the probabilities of each rule in the grammarare upated, based on the expansion rules used by the best individual. Co-evolutionaryProbabilistic Grammatical Evolution (Co-PGE) employs the same representation of indi-viduals and introduces a new technique to update the grammar’s probabilities, where eachindividual is assigned a PCFG where the probabilities of each derivation option are changedat each generation using a mutation like operator. In both methods, the individuals areremapped after updating the grammar.Probabilistic Structured Grammatical Evolution (PSGE) and Co-evolutionary Probabilis-tic Structured Grammatical Evolution (Co-PSGE) were created by adapting the mappingand probabilities update mechanism from PGE and Co-PGE to Structured GrammaticalEvolution (SGE), a method that was proposed to overcome the issues of GE while improv-ing its performance [6]. These variants use as genotype a set of dynamic lists, one for eachnon-terminal of the grammar, with each element of the list being the probability used tomap the individual with the PCFG.We analyse and compare the performance of all the methods in six benchmarks. Whencompared to GE, the results showed that PGE and Co-PGE are statistically similar orbetter on all problems, while PSGE and Co-PSGE are statistically better on all problems.We also highlight Co-PSGE since it is statistically superior to SGE in some problems,making it competitive with the state-of-the-art. We also performed an analysis on therepresentations, and the results showed that PSGE and Co-PSGE have less redundancy,and all approaches exhibited better locality than GE, which allows for a better explorationof the search space.The analyses conducted showed that the evolved grammars help guide the evolutionaryprocess and provides us information about the most relevant production rules to generatebetter solutions. In addition, they can also be used to generate a sampling of solutionswith better average fitness.
FCT

碩士
國立雲林科技大學
資訊管理系碩士班
100
This paper proposes a "grammatical evolution" approach applied to robots, the robot to imitate and create movement. Different from general robot in the market, by the user to set target action, every time evolution resulting actions are not the same, but evolution process, grammars and actions are recorded for robots, "recalls mechanism".In this study, Robotis’s company developed by the Bioloid robot as a research platform, the movement use "grammatical evolution" to could produce concept of "imitation actions " or " innovative actions ". In this research, we study to get the "imitation actions" or "innovative actions". First, using grammars generate action randomly. Use adaptive function--- longest common subsequence as the action the criteria for assessment and get "action". This "action" determine whether the "imitation action" or "innovative action". Therefore, this study explore the robot the possibility of using grammars to imitate and create action, the resulting actions to create memories of a mechanism, user can create their own robot.

碩士
國立清華大學
語言學系
83
The history of De involves two kinds of development: (1) grammaticalization and (2) lexical replacement. In this paper, we make a quantitative analysis on these two processes, based on historical colloquial texts from Zutangji (around 953 A.D.) to contemporary Mandarin. The variety of the V-De constructions and abstractness-tendency of the meanings feature the grammaticalization of De. From a diachronic perspective, we make an analysis on the statistics of three sets of linguistic variation to substantiate our claim on the grammaticalization of De. They are (1) the ratios of the three correlated constructions, i.e., V-De, V-De-O and V-De-C in each period, (2) the ratios of the 'resultative' and 'potential' meanings in the V-De-(O) constructions, and the proportion of the four types of the V-De-C forms, i.e., V- De[R]-C, V-De[P]-C, V-De[D]-C and V-De[E]-C and (3) the ratios of the two Des, i.e., De 得 and de 的 in the three V- De, V-De-O and V-De-C constructions. As for the lexical replacement, we examine in detail the delicate relationship among the three resultative complements, De, dao and zhao, sharing a common semantic feature of [telic], with close attention to the processes of co-existence, competition and decline/rise. This thesis consists of five chapters. Chapter One is an introduction. Chapter Two presents the literature reviews of the histories of De and the V-De constructions. In Chapter Three, grammaticalization of De is our major concern. Chapter Four discusses lexical replacement of De by dao and zhao. In Chapter Five, we draw a conclusion.

Tese de doutoramento em Programa de Doutoramento em Ciência da Informação e Tecnologia, apresentada ao Departamento de Engenharia Informática da Faculdade de Ciências e Tecnologia da Universidade de Coimbra
Os Algoritmos Evolucionários (AE) são métodos computacionais de procura estocástica inspirados pelos conceitos da selecção natural e da genética. Este tipo de algoritmos tem sido usado com sucesso para resolver problemas em dominios da aprendizagem, do design e da optimização. Para utilizar um AE é necessário definir as suas componentes principais, como por exemplo os operadores de variação, os operadores de selecção de pais, e os mecanismos de selecção de sobreviventes. O desempenho de um AE pode ser altamente melhorado se cada uma destas componentes for ajustada para o problema especifico que se pretende resolver. Normalmente estas modificações são feitas manualmente e requerem um grau de conhecimento elevado. Para tentar melhorar este processo, os investigadores têm vindo a propor algoritmos para automaticamente criar AE. Estes novos métodos usam um (meta-) algoritmo que combina as diversas componentes e parâmetros, de maneira a criar a estratégia que melhor se aplica ao problema em questão. Neste contexto surge a área das Híper-Heurísticas (HH), cujo principal objectivo é o desenvolvimento de meta-algoritmos que sejam eficientes. A Programação Genética (PG), e em particular as variantes baseadas em representações gramaticais são habitualmente utilizadas como motor de pesquisa nas HH. Este trabalho prentende estudar e analisar em que condições a eficácia dos métodos de pesquisa pode ser melhorada, no contexto da evolução automática de AE. As principais contribuições podem ser divididas em três aspectos. A primeira consiste na construção de uma framework de HH baseada em Evolução Gramatical (EG). A framework está dividida em duas fases complementares: Aprendizagem e Validação. Na aprendizagem, um motor de EG é usado para combinar as componentes de baixo nível que estão especificadas numa Gramática Livre de Contexto. Na validação, os melhores algoritmos encontrados são aplicados a cenários diferentes dos da aprendizagem, para analisar a sua capacidade de generalização. A segunda contribuição está relacionada com a análise do impacto que as condições de aprendizagem têm na estrutura final dos algoritmos que estão a ser aprendidos e consequentemente na sua capacidade de optimização. Além disso é feita uma análise da relação que existe entre a qualidade dos algoritmos na fase de aprendizagem, e a qualidade dos algoritmos na fase de validação. Em concreto, analisa-se se os melhores algoritmos da fase de aprendizagem mantêm o seu bom desempenho na fase de validação. Por fim, a última contribuição é uma proposta de uma nova representação para EG que permite resolver alguns problemas relacionados com a exploração do espaço de procura.
Evolutionary Algorithms (EA) are stochastic computational methods loosely inspired by the principles of natural selection and genetics. They have been successfully used to solve complex problems in the domains of learning, design and optimization. When using an EA practitioners have to define its main components such as the variation operators, the selection and replacement mechanisms. The performance of an EA can be greatly enhanced if the components are tailored to the specific situation being addressed. These modifications are usually done manually and require a reasonable degree of expertise. In order to ease the use of EAs some researchers have developed methods to automatically design this type of algorithms. Usually, these methods rely on an (meta-) algorithm that combine components and parameters, in order to learn the one that is most suited for the problem being addressed. The area of Hyper-Heuristics (HH) emerges in this context focusing on the development of efficient meta-algorithms. Genetic Programming (GP), specifically the grammar based variants, are commonly used as HH. In this work, we study and analyze the conditions in which Grammatical Evolution (GE) can be enhanced to automatically design EAs. The main contributions can be divided in three aspects. Firstly, we propose an HH framework that relies on GE as the search algorithm. The proposed framework is divided in two complementary phases: Learning and Validation. In Learning the GE engine is used to combine low level components that are specified in a Context Free Grammar. In the second phase, Validation, the best algorithms learned are selected to be applied to scenarios different from the learning, in order to evaluate their generalization capacity. Secondly we study the impact that the learning conditions have in the final structure of the algorithms that are being learned. Moreover, we analyze the relationship between the quality exhibited by the algorithms during learning and their effective optimization ability when used in unseen scenarios. In concrete we analyze if the best strategies discover in learning still have the same good behavior in validation. Our final contribution addresses some of the limitations exhibited by Grammatical Evolution. The result is a novel representation with an enhanced performance.
FCT - SFRH/BD/79649/2011

Tree-based genetic programming (GP) has several known shortcomings: difficult adaptability to specific programming languages and environments, the problem of closure and multiple types, and the problem of declarative representation of knowledge. Most of the methods that try to solve these problems are based on formal grammars. The precise effect of their distinctive features is often difficult to analyse and a good comparison of performance in specific problems is missing. This thesis reviews three grammar-based methods: context-free grammar genetic programming (CFG-GP), including its variant GPHH recently applied to exam timetabling, grammatical evolution (GE), and LOGENPRO, it discusses how they solve the problems encountered by GP, and compares them in a series of experiments in six applications using success rates and derivation tree characteristics. The thesis demonstrates that neither GE nor LOGENPRO provide a substantial advantage over CFG-GP in any of the experiments, and analyses the differences between the effects of operators used in CFG-GP and GE. It also presents results from a highly efficient implementation of CFG-GP and GE.

Dissertação de Mestrado em Engenharia Informática apresentada à Faculdade de Ciências e Tecnologia
A escolha de uma boa taxa de aprendizagem é fulcral para o bom treino e performance de Redes Neuronais. Atualmente, existem imensos métodos automáticos que facilitam a busca por uma boa taxa de aprendizagem. Apesar de estas técnicas serem eficazes e produzirem bons resultados ao longo do anos, são soluções generalistas i.e. não tem em conta as caracteristica de uma rede especifica. Dado isto, os possivéis beneficios de optimizar a taxa de aprendizagem para uma topologia de rede especifica permanece inexplorados. Como redes neuronais são sistemas complexos com muitos componentes inderdependentes, não é possivel para um humano inferir como é que um optimizador pode ser especializado para uma certa topologia. Apesar disso, técnicas de optimização heuristica como Algoritmos Evolucionários podem ser utilizados para procurar optimizadores personalizados que funcionem bem para uma arquitetura de rede neuronal especifica.Neste trabalho propomos o AutoLR, um sistema que utiliza Evolução Gramatical Estruturada para evoluir optimizadores de taxas de aprendizagem. Duas versões deste sistema são implementadas para dois tipos de optimizadores. O AutoLR Dinâmico é utilizado para evoluir optimizadores estáticos e dinâmicos. O melhor optimizador dinâmico evoluido tem melhor performance que o optimizador de controlo estabelecido e utiliza algumas técnicas encontradas na literatura. Apesar do LRD atingir bons resultados, os optimizadores evoluidos por este sistema só tem em consideração a taxa de aprendizagem anterior e a época de treino atual. De modo a superar estas limitações desenvolvemos um novo método chamado AutoLR Adaptativo. Esta versão do sistema evolui optimizadores adaptativos que tem acesso a mais informação sobre o treino. Estes optimizadores são capazes de afinar a taxa de aprendizagem para cada peso da rede individualmente, o que os faz geralmente mais eficazes. O optimizador adaptativo evoluido mais notável é capaz de competir com os melhores métodos do estado da arte, conseguindo até superá-los em alguns casos. Por último, o sistema foi capaz de descobrir um novo optimizador, ADES. Tanto quanto sabemos não existem optimizadores adaptativos na literatura que sejam semelhantes ao ADES.
The choice of a proper learning rate is paramount for good Artificial Neural Network training and performance. Currently, a plethora of state of the art automatic methods exist that make the search for a good learning rate easier, called Learning Rate Optimizers. While these techniques are effective and have yielded good results over the years, they are general solution i.e. they do not take into account the characteristics of a specific network. As a result, the possible benefits of the optimization of learning rate for specific network topologies remains largely unexplored. Since neural networks are complex systems with many interdependent components it is not possible for humans to infer how an optimizer can be specialized for a certain network topology. Nevertheless, heuristic optimization techniques such as Evolutionary Algorithms can be used to search for custom optimizers that work well for specific network architectures.In this work we propose AutoLR, a framework that uses Structured Grammatical Evolution to evolve learning rate optimizers. Two versions of this system are implemented for different types of optimizers. Dynamic AutoLR is used to evolve static and dynamic learning rate optimizers. The best evolved dynamic optimizer outperforms the established baseline and utilizes some techniques found in the literature. Even though DLR achieved good results the optimizers evolved by this system only take into account the previous learning rate and current training epoch. In order to overcome these limitations we devised a new method called Adaptive AutoLR. This version of the system evolves adaptive optimizers that have access to more information about training. These optimizers are able to fine tune a different learning rate for each network weight which makes them generally more effective. The most notable evolved adaptive optimizer is able to perform on par with the best state of the art methods, even outperforming them in some scenarios. Furthermore, the system was able to automatically discover a novel optimizer, ADES. To the best of our knowledge, no adaptive optimizers present in the literature are similar to ADES.

Στη Διδακτορική Διατριβή μελετώνται 3 κατηγορίες επιθέσεων άρνησης εξυπηρέτησης (Denial-of-Service). Η πρώτη κατηγορία αφορά επιθέσεις τύπου SYN Flood, μια επίθεση που πραγματοποιείται σε χαμηλό επίπεδο και αποτελεί την πιο διαδεδομένη ίσως κατηγορία. Για την αναγνώριση των επιθέσεων αυτών εξήχθησαν 9 στατιστικές παράμετροι οι οποίες τροφοδότησαν τους εξής ταξινομητές: ένα νευρωνικό δίκτυο ακτινικών συναρτήσεων, ένα ταξινομητή κ-κοντινότερων γειτόνων και ένα εξελικτικό νευρωνικό δίκτυο. Ιδιαίτερη σημασία στο σύστημα αναγνώρισης έχουν οι παράμετροι που χρησιμοποιήθηκαν. Για την κατασκευή και επιλογή των παραμέτρων αυτών, προτάθηκε μια νέα τεχνική η οποία χρησιμοποιεί ένα γενετικό αλγόριθμο και μια γραμματική ελεύθερης σύνταξης για να κατασκευάζει νέα σύνολα παραμέτρων από υπάρχοντα σύνολα πρωτογενών χαρακτηριστικών. Στη δεύτερη κατηγορία επιθέσεων, μελετήθηκαν επιθέσεις άρνησης εξυπηρέτησης στην υπηρεσία του παγκόσμιου ιστού (www). Για την αντιμετώπιση των επιθέσεων αυτών προτάθηκε η χρήση υπερσυνδέσμων-παγίδων οι οποίοι τοποθετούνται στον ιστοχώρο και λειτουργούν σαν νάρκες σε ναρκοπέδιο. Οι υπερσύνδεσμοι-παγίδες δεν περιέχουν καμία σημασιολογική πληροφορία και άρα είναι αόρατοι στους πραγματικούς χρήστες ενώ είναι ορατοί στις μηχανές που πραγματοποιούν τις επιθέσεις. Στην τελευταία κατηγορία επιθέσεων, τα μηνύματα ηλεκτρονικού ταχυδρομείου spam, προτάθηκε μια μέθοδος κατασκευής ενός πολύ μικρού αριθμού παραμέτρων και χρησιμοποιήθηκαν για πρώτη φορά νευρωνικά δίκτυα για την αναγνώριση τους.
The dissertation analyzes 3 categories of denial-of-service attacks. The first category concerns SYN Flood attacks, a low level attack which is the most common. For the detection of this type of attacks 9 features were proposed which acted as inputs for the following classifiers: a radial basis function neural network, a k-nearest neighbor classifier and an evolutionary neural network. A crucial part of the proposed system is the parameters that act as inputs for the classifiers. For the selection and construction of those features a new method was proposed that automatically selects constructs new feature sets from a predefined set of primitive characteristics. This new method uses a genetic algorithm and a context-free grammar in order to find the optimal feature set. In the second category, denial-of-service attacks on the World Wide Web service were studied. For the detection of those attacks, the use of decoy-hyperlinks was proposed. Decoy hyperlinks, are hyperlinks that contain no semantic information and thus are invisible to normal users but are transparent to the programs that perform the attacks. The decoys act like mines on a minefield and are placed optimally on the web site so that the detection probability is maximized. In the last type of attack, the email spam problem, a new method was proposed for the construction of a very small number of features which are used to feed a neural network that for the first time is used to detect such attacks.